RSA算法过程

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算法过程能帮助到你， 小编会一直给你带来更多教程资源文章信息。