RSA算法过程

IT教程 9个月前 https://55wd.com
701

rsa算法

构造一个公钥密码系统的要求

  1. 产生一对密钥是计算可行的
  2. 发送方利用公钥和明文,产生密文是计算可行的
  3. 接收方利用私钥和密文,产生明文是计算可行的
  4. 对于攻击者,利用公钥来推断私钥是计算不可行的
  5. 已知公钥和密文,恢复明文是计算不可行的
  6. (可选) 加密和解密的顺序可交换

RSA 算法的起源

  1. RSA 算法在1977年由MIT 的Ron Rivest、Adi Shamir 和Leonard Adleman 一起提出,并以他们三人姓氏开头字母命名,是一种获得广泛使用的非对称加密算法。
  2. 1983年麻省理工学院在美国为RSA 算法申请了专利。这个专利2000年9月21日失效。由于该算法在申请专利前就已经发表,在世界上大多数其它地区这个专利权不被承认。

RSA 算法的安全性概述

  1. 对极大整数进行因数分解的难度(The Factoring Problem) 决定了RSA 算法的可靠性。换言之,对一个极大整数做因数分解愈困难,RSA 算法就愈可靠。假如有人找到一种快速因数分解的算法的话,那么用RSA 加密的信息的可靠性就肯定会极度下降。目前看来找到这样的算法的可能性非常小。

  2. 目前还没有可靠的攻击RSA 算法的方式。短的RSA 钥匙可能被强力方式解破(比如768-bit,即232个十进制位以下的整数)。只要其钥匙的长度足够长(比如1024-15360-bit),用RSA 加密的信息看来很难被破解。

  3. 在分布式计算技术和量子计算理论日趋成熟的今天,RSA 加密的安全性受到了挑战。

RSA公钥和密钥的生成

  1. 挑选两个不同的大素数 p , q p,q p,q,令 N = p ∗ q 。 N= p*q。 N=p∗q。

  2. 利用欧拉 ϕ \phi ϕ函数来计算$\phi (N) $。 有 ϕ ( N ) = ϕ ( q ) ϕ ( p ) = ( p − 1 ) ( q − 1 ) \phi(N) = \phi(q)\phi(p) = (p - 1)(q - 1) ϕ(N)=ϕ(q)ϕ(p)=(p−1)(q−1)。

  3. 挑选一个整数 e e e ,满足条件:小于 ϕ ( N ) \phi(N) ϕ(N) 并与之互素。

  4. 通过式子 d e ≡ 1 ( m o d   ϕ ( N ) ) de \equiv 1 (mod \, \phi(N)) de≡1(modϕ(N)) 计算得到 d d d, 也就是说 d d d是 e e e的模 ϕ ( N ) \phi(N) ϕ(N)逆元。

  5. 销毁 p , q p,q p,q, 当 N N N足够大时,几乎不可能反向推导出 p , q p,q p,q。

  6. ( e , N ) (e,N) (e,N)作为公钥, ( d , N ) (d, N) (d,N)作为私钥。

RSA加密过程

  • 假设Bob发送明文M给Alice,Bob有Alice的公钥 ( e , N ) (e,N) (e,N)。

  • 要加密,Bob首先需要使用与Alice约定好的方式将明文M转换成 一个整数n, 整数n小于N。(如果信息N较大,可能需要分段加密)

  • Bob引用公钥 ( e , N ) (e,N) (e,N) 利用以下同余式,将n加密为c:

    ​ n e = c ( m o d   N ) n^e = c(mod \, N) ne=c(modN) 即 c = n e m o d   N c = n^e mod \,N c=nemodN

  • Bob算出c之后可以公开传播。

    !接收方公钥加密 !

RSA解密过程

  • Alice得到Bob的消息c,后利用Alice的私钥 ( d , N ) (d, N) (d,N) 解密。

  • 利用以下同余式将c转换为 n ′ n' n′

    ​ c d = n ′ ( m o d   N ) c^d = n' (mod \, N) cd=n′(modN) 或者 n ′ = c d m o d   N n' = c^d mod\,N n′=cdmodN

  • 得到的 n ′ n' n′ 就是 Bob的n,因此就可以按照约定的方式将信息M复原。

    ! 接收方私钥解密 !

RSA算法大素数选择问题

RSA算法中 p , q p, q p,q的选择原则

  1. (D. Coppersmith) p 和q 不能离得太近。如果N 的位数为k,那么 ∣ p − q ∣ |p - q| ∣p−q∣ 要同时满足 l o g ∣ p − q ∣ > k / 2 − 100 log|p - q|> k/2-100 log∣p−q∣>k/2−100 以及 l o g ∣ p − q ∣ > k / 3 log|p - q|> k/3 log∣p−q∣>k/3。
  2. (D. Coppersmith) 较短的e 可以提高加密算法计算ne 的速度,但可能存在计算d 的快速算法。PKCS#1 建议 e = 2 16 + 1 = 65537 e = 2^{16}+1 = 65537 e=216+1=65537。
  3. (M. Wiener) d 不能太小,否则可以通过快速算法计算得到d。如果N 的位数为k,那么d 的值要满足 d > 2 k / 2 d > 2^{k/2} d>2k/2 。
  4. (O. Schirokauer) N 的非相邻形式(Non-Adjacent Form, NAF) 的海明权重(Hamming weight, 非0元总数) 不能太小,否则应用数筛法可能会快速对N 进行质因数分解。一般要求N 的 N A F NAF NAF 表述权重大于 N / 4 N/4 N/4。

RSA 算法中p 和q 的选择流程:

  1. 确定RSA 所要求N 的位数k。k = 1024、2048、3072、4096 …

  2. 随机选择一个位数为 ( k + 1 ) / 2 (k + 1)/2 (k+1)/2 的素数p。

    即 p ∈ [ 2 ( k + 1 ) / 2 − 1 , 2 ( k + 1 ) / 2 − 1 ] p∈[2(k + 1)/2 - 1, 2(k + 1)/2 - 1] p∈[2(k+1)/2−1,2(k+1)/2−1]。

  3. 选择一个位数为 k − ( k + 1 ) / 2 = ( k − 1 ) / 2 k - (k + 1)/2 = (k - 1)/2 k−(k+1)/2=(k−1)/2 的素数q。

  4. 求|p - q|;如果log|p - q| 过小,则返回(2),重新选取p。

  5. 计算 N = p q N = pq N=pq,确认N 的位数为 k ( N ∈ [ 2 k − 1 , 2 k − 1 ] ) k (N∈[2^{k-1}, 2^k - 1]) k(N∈[2k−1,2k−1]);否则返回(2),重新选取p。

  6. 计算N 的NAF 权重;如果权重过小,则返回(2),重新选取p。

  7. 计算 ϕ \phi ϕ(N),选择公钥e, 2 16 &lt; e &lt; ϕ ( N ) 2^{16} &lt; e &lt;\phi(N) 216<e<ϕ(N) 且 g c d ( e , ϕ ( N ) ) = 1 gcd(e, \phi(N)) =1 gcd(e,ϕ(N))=1。

​ 一般建议选择素数 e = 2 16 + 1 = 65537 e = 2^{16}+1 = 65537 e=216+1=65537。

  1. 求e 的模 ϕ ( N ) \phi(N) ϕ(N) 逆元d;如果d 过小,则返回(2),重新选取p。
  2. 返回RSA 的参数p、q、e、d。或者销毁p、q,返回N、e、d。

大素数的生成

  • 素数的存在性 – 素数理论:在正整数N 附近,每ln(N) 个整数中有一个素数。
  • 素数的生成过程:
    1. 随机选择一个奇数n (比如通过伪随机数发生器);
    2. 随机选择a, 使0<a<n;
    3. 进行素性测试(例如用Miller-Rabin 算法),若n 没有通过测试,抛弃n,转到(1);
    4. 如果通过了足够次数的测试,概率上可以认为n 是素数,算法结束;否则转(2)。

AI图像识别:人类看的是形状,算法看的是纹理

人类会关注图中对象的形状,深度学习计算机系统所用的算法不一样,它会研究对象的纹理。图片中的动物轮廓是猫,但是猫披着大象皮肤纹理

算法(六):图解贪婪算法

算法简介 参考:https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html 贪婪算法(贪心算法)是指在对问题进行求解

遗传算法的基本原理和matlab实现

2016年9月7日星期三T.s.road 总结笔记遗传算法解决全局优化(即为最值点如图中C,D),而局部最优解决的是极值点问题(如图中A,B)1.    

A/B测试算法大揭秘第三篇:如何分析试验数据(下)

希望通过我们的几篇文章,能够帮助你更好的了解A/B测试和置信区间,一起实现用A/B测试驱动产品优化。P-value定义P-value(以下简称P值),

多层神经网络BP算法解释

# 多层神经网络BP算法解释 ## 前向传播 *** * 该项目采用反向传播算法描述了多层神经网络的教学过程。 为了说明这个过

文章回顾

大家看了本文RSA算法过程的精彩教程资源内容,是不是对RSA算法过程了解更多,真心希望RSA算法过程能帮助到你, 小编会一直给你带来更多教程资源文章信息。

版权声明:8f8f91a056bde582 发表于 2019-12-26 22:20:17。

本文由第三方用户分享仅代表作者观点,不代表本网站立场,秉承互联网开放分享的精神,目的在于传递更多信息,加强各行业互通交流,但对内容不作任何保证或承诺,请读者自行参考斟酌。网站发布的信息(包含但不限于版式、图片、字体、文章等素材)由第三方用户分享,版权归原作者所有,本站不承担任何相关的版权纠纷等相关责任。如您认为本篇内容侵犯了您的权益,请与我们联系,我们会及时处理。

豌豆资源网专注分享全网综合资源网站大全,致力于超实用的内容资源搜索。

转载请注明:
本文标题:RSA算法过程
本文地址:https://55wd.com/s60286/

你可能感兴趣

随便逛逛