VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
查看: 445|回复: 3

RSA算法原理学习

[复制链接]
发表于 2021-9-28 12:05:32 | 显示全部楼层 |阅读模式
  1. Option Explicit

  2. Function huzhi(ByVal X As Long, ByVal Y As Long) As Boolean
  3.     Dim Z As Long
  4.     huzhi = False
  5.     Do
  6.         Z = X Mod Y
  7.         X = Y
  8.         Y = Z
  9.     Loop Until Z = 0
  10.     If X = 1 Then
  11.         huzhi = True
  12.     End If
  13. End Function

  14. Sub startCalc()
  15.     Dim s As String
  16.     Dim e As Long
  17.     Dim pq1 As Long
  18.     Dim d As Long
  19.     Dim i As Long
  20.     Dim n As Long
  21.     Dim C As Long

  22.     s = ""
  23.     pq1 = Cells(4, 2)
  24.     For e = 2 To pq1 - 1
  25.         If huzhi(e, pq1) Then
  26.             s = s & e & ","
  27.         End If
  28.     Next e
  29.     If s = "" Then
  30.         s = "无解"
  31.     Else
  32.         s = Left(s, Len(s) - 1)
  33.     End If
  34.    
  35.     e = InputBox("e=" & s, "选择e")
  36.     Cells(5, 2) = e
  37.    
  38.     '=================================================
  39.     d = 0
  40.     Do
  41.         d = d + 1
  42.     Loop Until (d * e) Mod pq1 = 1
  43.     Cells(6, 2) = d
  44.    
  45.     '=================================================
  46.     n = Cells(3, 2)
  47.     For i = 1 To n - 1
  48.         Cells(i + 1, 3) = i
  49.         C = mod_(i, e, n)
  50.         Cells(i + 1, 4) = C
  51.         Cells(i + 1, 5) = mod_(C, d, n)
  52.     Next i
  53.    
  54.     For i = n To n + 100
  55.         Cells(i + 1, 3) = ""
  56.         Cells(i + 1, 4) = ""
  57.         Cells(i + 1, 5) = ""
  58.     Next i
  59. End Sub

  60. Function mod_(a As Long, b As Long, m As Long)
  61.     Dim i As Long
  62.     Dim result As Long
  63.     result = 1
  64.    
  65.     For i = 0 To b - 1
  66.         result = (result * a) Mod m
  67.     Next
  68.     mod_ = result
  69. End Function

  70. Sub test()
  71.     Debug.Print mod_(2, 8, 300)
  72. End Sub
复制代码
附件是一个完整的 xlsm 文件,只需输入两个质数p、q,就可以执行 startCalc 看结果了。

RSA.rar

18.65 KB, 下载次数: 51

 楼主| 发表于 2021-10-31 21:46:49 | 显示全部楼层
求N次幂的模

  1. Function n_mod(n As Long, pow As Long, mod_num As Long) As Long
  2.     Dim i As Long
  3.     Dim p As Long
  4.    
  5.     p = 1
  6.     For i = 1 To pow
  7.         p = (p * n) Mod mod_num
  8.     Next i
  9.    
  10.     n_mod = p
  11. End Function

  12. Sub test()
  13.     Debug.Print n_mod(17, 767, 3120)
  14. End Sub
复制代码
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-10-31 23:29:47 | 显示全部楼层
之前在网上看了不少 RSA 算法的帖子,但是它们有几个问题没有说明白:
1. 为什么这样求得的私钥进行和加密相同的幂mod运算后就能还原出明文?
2. 欧拉定理起了什么作用?
3. 欧拉函数求了几次?
4. 求私钥d就是求mod逆元,为什么它一定可解(存在)?
5. 用穷举法求d在n非常大时显然不行,否则黑客也能这样求出d了,扩展欧几里得算法(辗转相除法)又太难理解,有没有更好理解的求d的算法?
我今晚经过一番痛苦又快乐的思考研究后,终于把这些问题都弄明白了。

欧拉函数φ(n)表示小于n的与n互质的自然数的个数,
一般公式:φ(n)=n(1-1/p1)(1-1/p2)(1-1/p3)...
特别的,当m,n互质时(m、n可以都是合数),φ(mn)=φ(m)φ(n);
当n是质数时,φ(n)=n-1;
所以当特别中的特别,m、n都是质数时(它们必然互质),φ(mn)=φ(m)φ(n)=(m-1)(n-1);
欧拉定理:若a和n互质,则 a^φ(n)≡1 (mod n)

下面开始举例:
取 p=3,q=11,则n=pq=33,φ(33)=φ(3*11)=2*10=20,
这时候,网上的帖子都是这么说的,公钥e取一个1~20之间的与20互质的整数。
1~20之间可以理解,方便运算,因为如果找到一个大于20与20互质的数的话,它不断减去20,肯定能得到一个小于20的数。
但是为什么要与20互质,大多数帖子都没说,少数说了是欧拉定理的要求,但具体为什么?它们都没说。
好,我们取e=3吧,接下来要求一个d,使得ed≡1 (mod 20),这时候大多数帖子开始用穷举法了,d=1、2、3……全部算了一遍,好,d=7时,ed=3*7=21,21 % 20 = 1。
问题就在这里了,首先得证明d必然存在,然后不能用穷举,φ(n)和d很大时太慢。怎么证明和计算呢?这是我今晚研究的主要成果:
因为e与20互质,所以根据欧拉定理,e^φ(20)≡1 (mod 20),φ(20)我们暂时不用计算,只要知道它是一个大于1的整数就可以了,拆分一下,e*e^(φ(20)-1)≡1 (mod 20),因为φ(20)是一个大于1的整数,所以φ(20)-1是大于0的整数,所以 e^(φ(20)-1)也是整数,所以d=e^(φ(20)-1)是其中一个解。现在计算一下φ(20),因为20不是两个质数之积,所以计算起来没有φ(33)那么轻松,只能用通用公式,20=2^2*5, φ(20)=20(1-1/2)(1-1/5)=20*1/2*4/5=8,所以 d=3^7=2187。这样,我们既证明了d一定存在又求出了它,相当于连续求了2次欧拉函数,φ(φ(33))=φ(20)=8。这种思路非常清晰,是我(VBProFan)在网上看过的所有帖子和视频没都没提出过的。只是这样得到的d太大,我们只需mod 20就可以了,2187 % 20 = 7,和辗转相除法或者穷举法结果一致。当然,一般来说e和φ(φ(pq))-1都会很大,我们不会先求出幂再求模,而是e每自乘一次都mod n一次,计算机求解这个问题非常轻松,时间复杂度为对数函数。
再举个网上常见的例子:
p=61,q=53,n=pq=61*53=3233,φ(3233)=60*52=3120,
取e=17,又到了求私钥d的时候了,一般用扩展欧几里得算法求 17d+ 3120y = 1 的整数解,
用我发现的方法,则是先求φ(3120),
3120=2^4*3*5*13,于是φ(3120)=3120*1/2*2/3*4/5*12/13=768,于是 d=17^767 是d的一个解,它太大了,我们求
(17^767) % 3120 来代替它,用VBA编程:

Function n_mod(n As Long, pow As Long, mod_num As Long) As Long
    Dim i As Long
    Dim p As Long
   
    p = 1
    For i = 1 To pow
        p = (p * n) Mod mod_num
    Next i
   
    n_mod = p
End Function

Sub test()
    Debug.Print n_mod(17, 767, 3120)
End Sub

求得 d=2753,与扩展欧几里得算法一致。

最后证明一下为什么这样求出的d能够还原出明文:
设A为明文,B为加密后的密文,C为还原出的明文,求证A=C。
根据RSA加密、解密算法,
(A^e) % n = B
(B^d) % n = C
要证明A=C,只需证明 (B^d) % n = A,即 (((A^e) % n)^d) % n = A
即 A^(ed) % n = A,
而 ed % φ(n) = 1,即存在整数y使得 ed=1+y*φ(n)(其实y就是ed除以φ(n)的商,余数是1),
所以只需证明 A^(1+y*φ(n)) % n = A,即A*A^(y*φ(n)) % n = A,即 A^(y*φ(n)) % n = 1,
由于n是个非常大的、只有两个大质数因子的数,A是我们要加密的数据,实际应用中会切割成一个个小片段,所以不妨设A为一个字节,因此A<256,必然与n互质,因此A^y也与n互质(无论y多大,A如果没有n的因子,乘以自己多少次都不会出现n的因子),设a=A^y,因为a与n互质,根据欧拉定理,a^φ(n) % n = 1,因此A^y^φ(n) % n = 1,即 A^(y*φ(n)) % n = 1,证毕!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2021-12-4 07:09

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表