[原创]RSA公钥密码的破解

ysr

调用大数除法,试编的判断大数是否素数的程序:
Public Function DeleteSpace(Tmp As String) As String
    Dim Inst As Integer
    Do
        Tmp = Replace(Tmp, " ", "")
        DoEvents
        Inst = InStr(Tmp, " ")
    Loop While Inst > 0
    DeleteSpace = Tmp
End Function
Private Sub Command1_Click()

Dim g, k As String
Dim i As Long
  
Do While Val(InStr(MPC(DeleteSpace(Text1.Text), Val(2 * i + 1)), ".")) = 0
    For i = 1 To 5000
    g = MPC(DeleteSpace(Text1.Text), Val(2 * i + 1))
     Do While Val(InStr(g, ".")) = 0
        
          If n = 0 Then
            Text3.Text = Text3.Text & Val(2 * i + 1)
            n = 1
          Else
            Text3.Text = Text3.Text & "*" & Val(2 * i + 1)
          End If
        g = MPC(Trim(g), Val(2 * i + 1))
     Loop
    Next
    k = g
    g = 1
  Loop
      
     If n = 1 Then
      Text3.Text = Text3.Text & "*" & k
     Else
      Text3.Text = "这是一个质数"
     End If

   
  
End Sub
Public Function MPC(aa1 As String, bb1 As String) As String

Open "相除结果111.txt" For Output As #1
   
   Dim a1(100000) As Long   ';……………… 被除数的各位数字
   Dim ay(100000) As Long  ';……………… 余数的各位数字（最后一次试商要修正时）
   Dim ayy(100000) As Long  ';………………余数的各位数字（最后一次试商不必修正时）
   Dim b1(100000) As Long   ';……………… 除数的各位数字
   Dim c1(100000) As Long   ';……………… 近似商与除数相乘后的各位数字
   
   Dim d(10) As Long
   
   
   Dim pp As String      ';商的每一位
   Dim ppp As String     ';作为商的输出字符串
   Dim s1(1000) As Long  ';……………… 商的各位数字
   Dim js As Long        '; js 是商的位数加一
   Dim ta, tb, j, e As Long
   Dim fa As Long  ';………………………… 被除数的位数
   Dim fb As Long  ';………………………… 除数的位数
   
   
  aa1 = aa1
   bb1 = bb1
  
GoSub sub1

999: Close
   Exit Function
   
sub1:
   Z = 8 ';100    ';需要计算的小数位数
   
   Print: Print #1,
   Print "aa1 = "; aa1: Print #1, "aa1 = "; aa1
   Print "bb1 = "; bb1: Print #1, "bb1 = "; bb1
   Print "ppp = ";: Print #1, "ppp = ";
   
   pp = "": ppp = "": mv = 0
   If Len(bb1) <= 2 Then aa1 = aa1 + "00": bb1 = bb1 + "00"  ';除数小于 3 位时
   mv = 0
   If Val(aa1) < Val(bb1) And Val(aa1) <> 0 Then       ';除数大于被除数时
      ppp = "0."
       Z = Z - 1
      aa1 = aa1 + "0"
      mv = 1
   End If
   
   If mv = 0 Then
      GoTo 2
      Else
1:   If (Len(aa1) = Len(bb1) And aa1 < bb1) Or Len(Trim&#36;(aa1)) < Len(Trim&#36;(bb1)) Then ';被除数小于除数时
      ppp = ppp + "0"
      aa1 = aa1 + "0"
      Z = Z - 1
      GoTo 1
      Else
      GoSub sub3
      If Val(sy&#36;) * Val(aa1) = 0 Then GoTo 4  ';余数或被除数为零停止计算
      GoTo 3
   End If
   End If
2:
   GoSub sub3
   
   If Val(sy&#36;) * Val(aa1) = 0 Then GoTo 4     ';余数或被除数为零停止计算
                                          
   ppp = ppp + "."                            ';以下计算小数部分
  
3:   For iv = 1 To Z                           '; Z 是事先设定的小数位数
   If Val(sy&#36;) * Val(aa1) = 0 Then GoTo 4     ';余数或被除数为零停止计算
   aa1 = sy&#36; + "0"
   GoSub sub3
   Next iv
4:  Print ppp: Print &#35;1, ppp
   MPC = ppp
   Return
   
  
  
sub3:      ';大数相除
   ccc = 0
   vvv = 0  ';试余数不大于除数时的标志
   If (Len(aa1) = Len(bb1) And aa1 = bb1) Then pp = "1": sy&#36; = "0": GoTo 50
   If (Len(aa1) = Len(bb1) And aa1 < bb1) Or Len(Trim&#36;(aa1)) < Len(Trim&#36;(bb1)) Then ';被除数小于除数时
     pp = "0"
     sy&#36; = aa1
     GoTo 50
   End If
   
   
  mv = 0   ';如果除数位数小于 3 位，则分子分母同放大 100 倍：
  If Len(bb1) <= 2 Then aa1 = aa1 + "00": bb1 = bb1 + "00": mv = 1
  fa = Len(aa1)  ';把被除数的各位数码放在数组 a1(i)中
  For i = 1 To fa  ';a1(1)为最低位，a1(fa)为最高位
    a1(i) = Mid(aa1, fa - i + 1, 1)
  Next i
  
   fb = Len(bb1)  ';把除数的各位数码放在数组 b1(i)中
  For i = 1 To fb   ';b1(1)为最低位，b1(fb)为最高位
    b1(i) = Mid(bb1, fb - i + 1, 1)
  Next i
  
   ';以下取除数的近似数
  e = b1(fb) * 1000 + (b1(fb - 1)) * 100 + b1(fb - 2) * 10 + b1(fb - 3) + 1
  ta = fa: js = 0
  
  For j = fa - fb + 1 To 1 Step -1     ';………… 做除法求商，求余数
    js = js + 1
    f = a1(ta) * 1000 + a1(ta - 1) * 100 + a1(ta - 2) * 10 + a1(ta - 3)
  ';取被除数的近似数
    s1(js) = Int(f / e)   ';…………………………………… 试商
  For i = 1 To fb      ';…………………………………… 求试商的积
  c1(i) = b1(i) * s1(js)  ';…… 近似商与除数相乘后的各位数字
  Next i
  
  d(0) = 0
  For i = 1 To fb - 1  ';…………………………………… 满 10 进位
    d(1) = Int((c1(i) + d(0)) / 10): c1(i) = c1(i) + d(0) - d(1) * 10
    d(0) = d(1)
  Next i
  c1(fb) = c1(fb) + d(0)
  
  qq&#36; = ""
  For i = fb To 1 Step -1     ';……………… 求试商的精确积
  qq&#36; = qq&#36; & c1(i)           ';…… 试商与除数相乘后的精确积
  Next i
  
  For i = fb To 1 Step -1
     a1(ta - fb + i) = a1(ta - fb + i) - c1(i)
  Next i
  For i = 1 To fb
      If a1(ta - fb + i) < 0 Then
      a1(ta - fb + i) = a1(ta - fb + i) + 10
      a1(ta - fb + i + 1) = a1(ta - fb + i + 1) - 1
    End If
  Next i
    a1(ta - 1) = a1(ta - 1) + a1(ta) * 10
    ta = ta - 1
  Next j   ';至此，已初步算出最后的试商
  
  a1(fb - 1) = a1(fb - 1) Mod (10)
  
  For i = fb To 1 Step -1
  ayy(i) = a1(i)          ';试余数的各位数码
  Next
  
  ssy&#36; = ""    ';以下做出试余数的字符串 ssy&#36;
  For i = fb To 1 Step -1
  ssy&#36; = ssy&#36; & ayy(i)
11: Next i
  
  If (Len(ssy&#36;) = Len(bb1) And ssy&#36; > bb1) Or Len(Trim&#36;(ssy&#36;)) > Len(Trim&#36;(bb1)) Then
     vvv = 1    ';试余数大于除数时的标志
     For i = 1 To fb   ';试余数减去除数，得到正确余数 sy&#36;
     ay(i) = ayy(i) - b1(i)
      If ay(i) < 0 Then
        ay(i) = ay(i) + 10
        ayy(i + 1) = ayy(i + 1) - 1
      End If
     Next i
    sy&#36; = ""             ';把 ay(i) 组装成 sy&#36;
    For i = 1 To fb
     sy&#36; = Trim&#36;(Str&#36;(ay(i))) & sy&#36;
    Next i
71: If Mid&#36;(sy&#36;, 1, 1) = " " Or Mid&#36;(sy&#36;, 1, 1) = "0" Then sy&#36; = Mid&#36;(sy&#36;, 2) Else GoTo 72
  GoTo 71   ';去掉结果中的多余 0
  End If
72:
  For i = 1 To fb - 1
    c1(1) = a1(i) - b1(i)
    ay(i) = c1(1)   ';最后一次试商要修正时，这就是余数各位数（除最高位）
  If c1(1) < 0 Then
    ccc = -1
    c1(1) = c1(1) + 10: a1(i + 1) = a1(i + 1) - 1
  End If
  Next i
  c1(1) = a1(fb) - b1(fb)
  
  ay(fb) = c1(1)  ';最后一次试商要修正时，这就是余数的最高位
  
  If c1(1) >= 0 Then         '; c(1) 不是负数时最后一次试商要修正
     s1(js) = s1(js) + 1     '; 所谓修正就是加一
  End If
  
  For i = js To 1 Step -1
  If s1(i) >= 10 Then   ';由于修正，商的某一位有大于10者，要调整进位
    s1(i) = s1(i) - 10: s1(i - 1) = s1(i - 1) + 1
  End If
  Next i
  If js = 1 Then       ';以下做出商的字符串 pp
    pp = s1(js)
  End If
  If js >= 2 Then
    pp = 10 * s1(1) + s1(2)
  End If
  For i = 3 To js
  pp = pp & s1(i)
  Next i
     
  If vvv = 1 Then GoTo 50  ';试余数大于除数
  
10: sy&#36; = ""    ';以下做出余数的字符串 sy&#36;
  If ccc = -1 Then    ';最后一次试商不必修正时的余数
  For i = fb To 1 Step -1
  If ayy(i) <> 0 Then yyy = 1
  If ayy(i) = 0 And yyy = 0 Then GoTo 20
  sy&#36; = sy&#36; & ayy(i)
20: Next i
  End If
  
  If ccc = 0 Then    ';最后一次试商须修正时的余数
  For i = fb To 1 Step -1
  If ay(i) <> 0 Then yyy = 1
  If ay(i) = 0 And yyy = 0 Then GoTo 30
  sy&#36; = sy&#36; & ay(i)
30: Next
  End If
  If Mid(sy&#36;, 1, 1) = "-" Then ccc = -1: GoTo 10   ';余数为负，重做余数
40: If Mid(sy&#36;, 1, 1) = "0" Then sy&#36; = Mid(sy&#36;, 2)   ';去掉余数前面的多余零
  If Mid(sy&#36;, 1, 1) = "0" Then GoTo 40
  
50: If sy&#36; = "" Then sy&#36; = "0"
  If mv = 1 And sy&#36; <> "0" Then sy&#36; = Mid(sy&#36;, 1, Len(sy&#36;) - 2)
  If mv = 1 And sy&#36; = "0" Then sy&#36; = "0"
  ppp = ppp + pp     ';包括整数及小数的商
  
90: Return
End Function
  

Private Sub Command2_Click()
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
End Sub

实验
1153103961384478448404925715924378885327554202134226047348028294505040
7344673361246564525252797971663975673998509009851407680713917156735472
7268047500902273102554085125377896253703900452077670802123470134036823
1774597408929744933116431873027001298810225982471847
结果:这是素数,但由于程序没有编完,不能分解大数,把另外两种情况编出就可以了,
需要解2次方程的程序,复杂,没有完,
只能实验大数,小的整数是会出错的,只实验5000个因子,在20秒内,再多时间就长了,
分解素因数的小程序(10位内的数),网上复制的:
Dim x, a, b, k As String
Private Sub Command1_Click()
a = Val(Text1.Text)
x = 2
If a <= 1 Or a > Int(a) Then
  If a = 1 Then
   Text2.Text = "它既不是质数，也不是合数"
  Else
   MsgBox "请您先输入数据", vbOKOnly + vbInformation, "友情提示"
  End If
  
Else
  Do While a / 2 = Int(a / 2) And a >= 4
   
      If b = 0 Then
        Text2.Text = Text2.Text & "2"
        b = 1
      Else
        Text2.Text = Text2.Text & "*2"
      End If
    a = a / 2
    k = a
  Loop
  Do While a > 1
    For x = 3 To Sqr(a) Step 2
     Do While a / x = Int(a / x) And a >= x * x
        
          If b = 0 Then
            Text2.Text = Text2.Text & x
            b = 1
          Else
            Text2.Text = Text2.Text & "*" & x
          End If
        a = a / x
     Loop
    Next
    k = a
    a = 1
  Loop
      
     If b = 1 Then
      Text2.Text = Text2.Text & "*" & k
     Else
      Text2.Text = "这是一个质数"
     End If
End If
End Sub
Private Sub Command2_Click()
Text1.Text = ""
Text2.Text = ""
End Sub

ysr

41楼的时间是我用手机秒表功能计时的,求做大正整数运算VB代码和VB程序计时代码,希望老师帮忙!

ysr

求各位老师兼朋友帮忙做个大数加法VB程序(正整数就行)!
  感谢老师的指导!回报大恩!

ysr

由于作者是业余水平,无时间和精力继续学习编程,搞个程序很难,还有如下编程问题:
大数加法,大数减法,大数开平方,辗转相除法求模的逆元,蒙格马力快速幂模算法,
象座座难关,铁桶一般,
对高手来说可能很简单,欢迎免费试验,不做黑客,不以盈利为目的扩散程序,最好把试验结果反馈作者,试验程序是不算侵权的,我保留原创权,这样才有修改解释权,和与朋友沟通的发言权!
希望高手帮忙!

ysr

[这个贴子最后由ysr在 2012/08/25 02:33pm 第 1 次编辑]


好不容易做个大数加法,代码如下,朋友看看有没有问题?
Private Sub Command1_Click()
D1 = Text1.Text
D2 = Text2.Text
Text3.Text = MPC1(Text1.Text, Text2.Text)
End Sub
Public Function MPC1(D1 As String, D2 As String) As String ';jiafa
Dim X, Y ';两数长度
If Len(D1) >= Len(D2) Then
D4 = String(Len(D1) - Len(D2), "0") & D2
D3 = D1
Else
D4 = D2
D3 = String(Len(D2) - Len(D1), "0") & D1
End If
X = Len(D3): Y = Len(D4)
Dim A() As Integer, B1() As Integer, C1() As Integer, E1() As Integer
ReDim A(1 To X)
ReDim B1(1 To Y)
ReDim C1(1 To X)
ReDim E1(1 To X)
Dim I, J, C2, CJ, JW
For J = Y To 1 Step -1 ';D2
JW = 0 ';进位清0
B1(J) = Mid&#36;(D4, J, 1) ';每位数
For I = X To 1 Step -1  ';D1
   A(I) = Mid&#36;(D3, I, 1) ';每位数
   C1(I) = A(I) + B1(I) + JW ';计算jia
   JW = C1(I) \ 10
   E1(I) = C1(I) Mod 10
  Next
  Next
  For r = 1 To X
  If JW = 0 Then
  MPC1 = MPC1 & E1(r)
  Else
  jc = jc & E1(r)
  MPC1 = JW & jc
  End If
  Next
  
End Function


Private Sub Command2_Click()
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
End Sub
验证;
加数:12345,
加数:12345,
和:24690,
加数:12345,
加数:234,
和:12579,
加数:123456789,
加数:123456789,
和:246913578,

ysr

我做的大数减法,请教结果中开首多余的0如何去掉?
我的代码:
Private Sub Command1_Click()
D1 = Text1.Text
D2 = Text2.Text
Text3.Text = MPC(Text1.Text, Text2.Text)
End Sub
Public Function MPC(D1 As String, D2 As String) As String ';jianfaqi
Dim X, Y ';两数长度
If Len(D1) >= Len(D2) Then
D4 = String(Len(D1) - Len(D2), "0") & D2
D3 = D1
Else
D4 = D2
D3 = String(Len(D2) - Len(D1), "0") & D1
End If
X = Len(D3): Y = Len(D4)
Dim A() As Integer, B1() As Integer, C1() As Integer, E1() As Integer
ReDim A(1 To X)
ReDim B1(1 To Y)
ReDim C1(1 To X)
ReDim E1(1 To X)
Dim I, J, C2, CJ, JW
For J = Y To 1 Step -1 ';D2
JW = 1 ';yu jie weichuzhi
B1(J) = Mid&#36;(D4, J, 1) ';每位数
For I = X To 1 Step -1  ';D1
   A(I) = Mid&#36;(D3, I, 1) ';每位数
   C1(I) = 10 + A(I) - B1(I) - 1 + JW ';计算jia
   JW = C1(I) \ 10
   E1(I) = C1(I) Mod 10
  Next
  Next
  For r = 1 To X
  MPC = MPC & E1(r)
  Next
  
End Function


Private Sub Command2_Click()
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
End Sub

验证:
被减数:123456789,
减数:114567893,
差:008888896,
被减数:123456789123456789,
减数:123456789123456788,
差:000000000000000001,

ysr

[这个贴子最后由ysr在 2012/05/17 09:41pm 第 1 次编辑]

去掉前导0的减法,代码如下(又修改了1下,因为当结果为0时无输出,修改后代码如下):
Private Sub Command1_Click()
D1 = Text1.Text
D2 = Text2.Text
Text3.Text = MPC(Text1.Text, Text2.Text)
End Sub
Public Function MPC(D1 As String, D2 As String) As String ';jianfaqi
Dim X, Y ';两数长度
If Len(D1) >= Len(D2) Then
D4 = String(Len(D1) - Len(D2), "0") & D2
D3 = D1
Else
D4 = D2
D3 = String(Len(D2) - Len(D1), "0") & D1
End If
X = Len(D3): Y = Len(D4)
Dim A() As Integer, B1() As Integer, C1() As Integer, E1() As Integer
ReDim A(1 To X)
ReDim B1(1 To Y)
ReDim C1(1 To X)
ReDim E1(1 To X)
Dim I, J, C2, CJ, JW
For J = Y To 1 Step -1 ';D2
JW = 1 ';yu jie weichuzhi
B1(J) = Mid&#36;(D4, J, 1) ';每位数
For I = X To 1 Step -1  ';D1
   A(I) = Mid&#36;(D3, I, 1) ';每位数
   C1(I) = 10 + A(I) - B1(I) - 1 + JW ';计算jia
   JW = C1(I) \ 10
   E1(I) = C1(I) Mod 10
  Next
  Next
  For r = 1 To X
  MPC = MPC & E1(r)
  For I = 1 To Len(MPC)
    If Not Mid(MPC, I, 1) = "0" Then
        Exit For
    End If
Next
strtmp = Mid(MPC, I)
  If Len(strtmp) = 0 Then
  MPC = "0"
  Else
MPC = strtmp
End If
  Next
  
  
End Function


Private Sub Command2_Click()
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
End Sub



验证:
被减数:123456789,
减数:123456788,
差:1,
被减数:12345,
减数:12345,
差:0,

ysr

加减乘除开平方,道道难关铁桶1般,3脚猫的功夫不能与高手相提并论,只要哥们努力干,铁桶也要钻个眼,那位老师帮帮忙,一道一道往前钻!

ysr

[这个贴子最后由ysr在 2012/06/06 01:33pm 第 2 次编辑]

除数小于8位的大数除法程序：
Private Sub Command1_Click()
Text3.Text = MCC(Text1.Text, Text2.Text)
End Sub
Public Function MCC(D1 As String, D2 As String) As String ';除数少于8位的除法
If Len(D1) < Len(D2) Then
   MCC = "0" & "/" & D1
   Else
   If Len(D1) < 9 Then
    MCC = Val(D1) \ Val(D2) & "/" & Val(D1) - (Val(D1) \ Val(D2)) * Val(D2)
    Else
   
   Dim X ';fen duan changdu
   X = Len(D1)
   
     
   
     Dim A() As String
      ReDim A(1 To X)  ';定义数组的储存空间
      For i = 1 To X Step 1  ';把被除数各位放在a()中
       A(i) = Mid(D1, i, 1)
        
      
       Next i
      Dim B() As String
      jw = 0
     ReDim B(1 To X)
     For j = 1 To X Step 1
    B(j) = Val(jw & A(j)) \ Val(D2)
      jw = Val(jw & A(j)) - Val(B(j)) * Val(D2)
       Next j
       For r = 1 To X
       If jw = 0 Then
          MCC = MCC & B(r)
          Else
          cj = cj & B(r)
          MCC = cj & "/" & jw
      
    End If
   
   Next
   
   End If
     
     End If
   
End Function

Private Sub Command2_Click()
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
End Sub



验证：
被除数：123456789123456789，
除数：123，
输出：001003713732711030/99，
符号“/”后面的是余数。

ysr

去掉了前导0的大数除法（除数小于8位）：
Private Sub Command1_Click()
Text3.Text = MCC(Text1.Text, Text2.Text)
End Sub
Public Function MCC(D1 As String, D2 As String) As String ';除数少于8位的除法
If Len(D1) < Len(D2) Then
   MCC = "0" & "/" & D1
   Else
   If Len(D1) < 9 Then
    MCC = Val(D1) \ Val(D2) & "/" & Val(D1) - (Val(D1) \ Val(D2)) * Val(D2)
    Else
   
   Dim X ';fen duan changdu
   X = Len(D1)
   
     
   
     Dim A() As String
      ReDim A(1 To X)  ';定义数组的储存空间
      For I = 1 To X Step 1  ';把被除数各位放在a()中
       A(I) = Mid(D1, I, 1)
        
      
       Next I
      Dim B() As String
      jw = 0
     ReDim B(1 To X)
     For j = 1 To X Step 1
    B(j) = Val(jw & A(j)) \ Val(D2)
      jw = Val(jw & A(j)) - Val(B(j)) * Val(D2)
       Next j
       For r = 1 To X
       If jw = 0 Then
          MCC = MCC & B(r)
          Else
          cj = cj & B(r)
          MCC = cj & "/" & jw
      
    End If
   
    For I = 1 To Len(MCC)
   If Not Mid(MCC, I, 1) = "0" Then
       Exit For
   End If
Next
strtmp = Mid(MCC, I)
If Len(strtmp) = 0 Then
MCC = "0"
Else
MCC = strtmp
End If
   
   Next
   
   End If
     
     End If
   
End Function

Private Sub Command2_Click()
Text1.Text = ""
Text2.Text = ""
Text3.Text = ""
End Sub


验证：
被除数：123456789123456789，
除数：123，
输出：1003713732711030/99，