RSA算法过程

IT教程 2年前 (2019) http://www.hebbaijiu.com/
819

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算法过程
本文地址:http://www.hebbaijiu.com/60286.html