[资料]什么是关联素数

ysr

素数P与素数2*P+1为关联素数，P与4*P+3为双关联素数，P与8*P+7为“三连冠”，
对三连冠素数的积n,可迅速得方程P*(8*P+7)=n,不必解方程就可得P=√(n/8)取整数部分,若P为偶数则n不是三连冠素数的积,
RSA密码用到关联素数，双因子版的RSA密码的公开模数n，为两个相同位数的素数的积，B的值在1和4之间，即使位数差1或2位，B的值不超过10，设关联次数为N，则B=2^(N-1)+1/2,
可迅速得方程P(2^N*P+2N+1)=n,关联次数不多的话可迅速分解,即使是关联素数附近的因子 ,可以通过细化公式和修正值迅速找到,
当N很大时,P会很小,当P小于100多位时,即使常规法也可分解,N年前数学家已成功分解两个100多位的素数的积,
对多因子版RSA密码,由于B很大,分解n要多次迭代,等法,分解得最小素因子P,再依次得其他素因子,速度慢,
所以,RSA基本上可以淘汰,此法还没有验证,对改进版RSA密码可能安全些,但改进版目前还没有搞出来!
如下为资料,其中提到k次不动点,是什么呢?请感兴趣的朋友解释!

-----------------------------
那么这时r1,r2有什么样的特征呢？人们已经证明，关联素数有较好的密码学性质：选择关联素数r1，r2，可以增强RSA密码系统抵抗因数分解分析和模加密钥求解密钥分析的能力。所谓关联素数就是指这样一类素数：它本身为素数，它的二倍加一也为素数。受到这个结论的启发，是不是把条件在加强一点，会具有更好的密码学性质呢？假设素数p为素数，q=2*p+1为素数，r=2*q+1也为素数，那么选择这样的r[注：相关文献将之称为双重关联素数]，除了具有关联素数的好处外，是否还有其他的好处呢？
　　在讨论之前，先不加证明的引入两个定理：
　定理1：对于固定的e，同余方程的解叫做e模n的k次不动点。该k次不动点的个数为f(k)=((e^k-1,r1-1)+1)* ((e^k-1,r2-1)+1)。
　定理2：k次不动点不是j次不动点（j$#@60;k），那么该不动点叫做k阶不动点。S（K）表示所有阶数不超过K的不动点的集合。那么| S（K）|$#@62;=9。
---------------------------------------------

ysr

每个关联次数对应1个试除因子,若取N=5000,将有5000个试除因子,由于log（2^N)=log(2^5000)=5000*0.3010=1505,就是2^5000是1505位的数,即使2048位的RSA密码,已经超过公开模数的方根,此时P就很小,所以,N不可能这么大,然而5000个除数虽然数值大,由于数量少,对普通电脑也可短时间算完,如果P在这5000个之中,那密码是不堪一击的!
  欢迎探讨!

wangyangkee

先别说话，看看鲍丰武怎么讲；然后，跟着参和参和， ，，

ysr

我已搞出分解关联素数积的程序（近似的也可以分解），谁需要的可以声明，我可以给你发电子邮件，也可以发这里，免费转让技术，这个很简单，如果这个算技术的话！有的版本的RSA密码用到这个，可以破解！
验证：
输入：10082000011715000003403，
输出：71000000041*142000000083，
其他类型的分解程序还在做，只做了框架，具体程序未搞，要把粗化和细化公式做成可调用程序，任意调用，可以循环调用，以提高精确度！

ysr

没人研究这个吗？无人发言！

ysr

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

程序：http://bbs.emath.ac.cn/thread-4690-1-1.html
http://bbs.emath.ac.cn/thread-4690-1-1.html

ysr

[这个贴子最后由ysr在 2013/03/07 02:04pm 第 1 次编辑] 如下为该程序的代码： Private Sub Command1_Click() Dim D1, D2, jcc D1 = DeleteSpace(Text1.Text) If Len(D1) < 3 Then ja = 2 Else If Len(D1) < 20 Then ja = Len(D1) \ 2 Else ja = Len(D1) \ 4 End If End If d3 = 2 Do While Len(d3) <= ja jcc = MCC1(Trim(D1), Trim(d3)) If InStr(jcc, "/") = 0 Then jcs = jcc Else jcs = Left(jcc, InStr(jcc, "/") - 1) End If q1 = MBBC(Trim(jcs)) If InStr(q1, "/") = 0 Then jcs1 = q1 Else jcs1 = Left(q1, InStr(q1, "/") - 1) End If If jcs1 = 0 Then jcs1 = 1 Else jcs1 = jcs1 End If Do While InStr(MCC1(Trim(D1), Trim(jcs1)), "/") = 0 And MBJC(Trim(jcs1), 1) > 0 If B = 0 Then Text2.Text = Text2.Text & jcs1 B = 1 Else Text2.Text = Text2.Text & "*" & jcs1 End If D1 = MCC1(Trim(D1), Trim(jcs1)) k = D1 Loop d3 = MbC(Trim(d3), 2) Loop If B = 1 Then Text2.Text = Text2.Text & "*" & k Else Text2.Text = "zhe shi sushu" End If End Sub Public Function MBBC(D1 As String) As String ';kai pingfang If Len(D1) < 10 Then jss = Int(Sqr(Val(D1))) JW = Val(D1) - (jss) ^ 2 If JW = 0 Then MBBC = jss Else MBBC = jss & "/" & JW End If Else Dim X ';shuju changdu X = Len(D1) \ 4 D2 = String(4 - Len(D1) + 4 * X, "0") & D1 Dim A() As String ReDim A(4 To 4 * X + 4) Dim B() As String ReDim B(2 To 2 * X) Dim I, J, js For I = 4 To 4 * X + 4 Step 4 A(I) = Mid(D2, I - 3, 4) js = Int(Sqr(Val(A(4) & A(8)))) JW = Val(A(4) & A(8)) - (js) ^ 2 Next J = 4 Do While J <= 2 * X jws = MPC1(JW & "0000", A(2 * J + 4)) If MBJC(Trim(jws), MbC(Trim(js), 200)) <= 0 Then B(J) = "00" Else jwc = Left(jws, Len(jws) - Len(MbC(Trim(js), 200)) + 2) \ Left(MbC(Trim(js), 200), 2) If Len(jwc) > 2 Then B(J) = 99 Else B(J) = jwc End If Do While MBJC(Trim(jws), MbC(MPC1(B(J), MbC(Trim(js), 200)), B(J))) = -1 B(J) = B(J) - 1 Loop End If JW = MPC(Trim(jws), MbC(MPC1(MbC(200, Trim(js)), B(J)), B(J))) js = MPC1(MbC(Trim(js), 100), Trim(B(J))) J = J + 2 If JW = 0 Then MBBC = js Else MBBC = js & "/" & JW End If Loop End If End Function Public Function MBJC(D1 As String, D2 As String) As String ';bijiao If Len(D1) > Len(D2) Then MBJC = 1 Else If Len(D1) < Len(D2) Then MBJC = -1 Else If Len(D1) = Len(D2) And Len(D1) >= 10 Then Dim X, Y X = Len(D1) \ 4: Y = Len(D2) \ 4 Dim A() As String, B() As String ReDim A(4 To 4 * X + 4) ReDim B(4 To 4 * Y + 4) If Val(Left(D1, Len(D1) - 4 * X)) > Val(Left(D2, Len(D2) - 4 * Y)) Then MBJC = 1 Else If Val(Left(D1, Len(D1) - 4 * X)) < Val(Left(D2, Len(D2) - 4 * Y)) Then MBJC = -1 Else For I = 4 To 4 * X Step 4 A(I) = Mid(D1, Len(D1) - I + 1, 4) B(I) = Mid(D2, Len(D2) - I + 1, 4) Next J = 4 * X Do While A(J) = B(J) And J >= 8 J = J - 4 Loop If Val(A(J)) - Val(B(J)) > 0 Then MBJC = 1 Else If Val(A(J)) - Val(B(J)) < 0 Then MBJC = -1 Else MBJC = 0 End If End If End If End If End If If Len(D1) < 10 Then ja = Val(D1) - Val(D2) If ja > 0 Then MBJC = 1 Else If ja = 0 Then MBJC = 0 Else MBJC = -1 End If End If End If End If End If End Function Public Function MbC(D1 As String, D2 As String) As String ';乘法 Dim X, Y ';两数长度 X = Len(D1): Y = Len(D2) Dim A() As Integer ReDim A(1 To X + Y, 1 To Y) Dim I, J, C1, C2, CJ, JW For J = Y To 1 Step -1 ';D2 JW = 0 ';进位清0 C2 = Mid$(D2, J, 1) ';每位数 For I = X To 1 Step -1 ';D1 C1 = Mid$(D1, I, 1) ';每位数 CJ = C1 * C2 + JW ';计算乘积 C = I + J: r = Y + 1 - J A(C, r) = CJ Mod 10 ';本位 JW = CJ \ 10 ';进位 Next A(C - 1, r) = JW Next Dim B() As Integer ReDim B(1 To X + Y) JW = 0 For I = X + Y To 1 Step -1 Bit = JW For J = 1 To Y Bit = Bit + A(I, J) Next B(I) = Bit Mod 10 JW = Bit \ 10 Next If B(1) > 0 Then MbC = MbC & B(1) Else MbC = MbC End If For I = 2 To X + Y MbC = MbC & B(I) Next End Function 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$(D4, J, 1) ';每位数 For I = X To 1 Step -1 ';D1 A(I) = Mid$(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 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 Public Function MCC1(D1 As String, D2 As String) As String ';大整数的除法 Dim ss ss = MBJC(D1, D2) If ss = -1 Then MCC1 = "0" & "/" & D1 Else If ss = 0 Then MCC1 = 1 Else If Len(D1) = Len(D2) Then MCC1 = "1" & "/" & MPC(D1, D2) Else If Len(D2) < 9 Then MCC1 = MCC(D1, D2) Else Dim X, Y ';定义分段长度 X = Len(D1): Y = Len(D2) Dim JW, jcc, jss, jcs Dim A() As String, B() As String ReDim A(1 To X) ReDim B(1 To Y) For I = 1 To X A(I) = Mid(D1, I, 1) Next For J = 1 To Y B(J) = Mid(D2, J, 1) Next jcc = Val(A(1) & A(2)) \ Val(B(1) & B(2)) jss = MbC(Trim(jcc), D2) For i1 = 1 To Y jws = jws & A(i1) Next JW = MPC(Trim(jws), Trim(jss)) Z = X - Y Dim C() As String ReDim C(1 To Z) For s = 1 To Z If MBJC(JW & A(s + Y), D2) = -1 Then C(s) = "0" Else jwc = Val(Left(JW & A(s + Y), 3)) \ Val(Left(D2, 2)) If Len(jwc) > 1 Then C(s) = "9" Else C(s) = jwc End If Do While MBJC(JW & A(s + Y), MbC(Val(C(s)), D2)) = -1 C(s) = Right(10000 + Val(C(s) - 1), 1) Loop End If JW = MPC(JW & A(s + Y), MbC(Val(C(s)), D2)) jcc = jcc & C(s) Next s If JW = 0 Then MCC1 = jcc Else MCC1 = jcc & "/" & JW End If For I = 1 To Len(MCC1) If Not Mid(MCC1, I, 1) = "0" Then Exit For End If Next strtmp = Mid(MCC1, I) If Len(strtmp) = 0 Then MCC1 = "0" Else MCC1 = strtmp End If End If End If End If End If End Function 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 ja = Val(D1) \ Val(D2) If Val(D1) - (Val(D1) \ Val(D2)) * Val(D2) = 0 Then MCC = ja Else MCC = ja & "/" & Val(D1) - (Val(D1) \ Val(D2)) * Val(D2) End If 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 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$(D4, J, 1) ';每位数 For I = X To 1 Step -1 ';D1 A(I) = Mid$(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 = "" End Sub

ysr

[这个贴子最后由ysr在 2013/11/27 09:11am 第 1 次编辑]


如下为代码:

ysr

如下为关联素数积的分解程序:

熊一兵

RSA密码比较专业,搞得懂的人希缺,作为专门研究前期要投入不少精力时间,可能有人心有余,却力不足,意义确实大,你先行,等我有能力了一定很很地支持你!!!