数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 27459|回复: 158

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

[复制链接]
发表于 2011-4-28 12:57 | 显示全部楼层 |阅读模式
[watermark]以下方法可破解公钥密码,没有编称,是否可行请看一下。对其中的公式参数保留解释修改权。1.由公开模数N及以下数学原理求质因数pq
由于n=pq 用如下公式所得数试除n即可快速分解n得到n=pq从2N7+1-10^8 至2N7+1+10^8
从2N2+1-10^8 至2N2+1+10^8 从2N8+1-10^8至 2N8+1+10^8试除n
   2.由公开密钥e用如下公式用辗转相除法求保密密钥d.
设x1=(w/e),r1=(x1+1)*e-(p-1)(q-1),w=(p-1)*(q-1),x2=e/r1余r2,等等,依次用余数去除上次的除数.x1x2x3, Xw,等为商, r2r3,rw,等为余数.
   当r1=1,  则d=e*x1^2 ,  当r2=1, 则d=x1+1,r3=1,d=x1*(x2+1)+1,r4=1,d=x1*(x2+x3+1)+2,等等,当第w+1个余数为1时,则d=x1*(x2+x3+x4+等等+xw)+w-1,注w为倒数第2个商和余数的下脚码
3.由密文c用以下公式求明文m.  m=c的d次方modn
如下为N2N7N8的求法:
(公式1)求B1与B2之间的因数N值的算法:N1=(D/(2B1+1))^(1/2),D=M/4,D1=(2B1+1)N1^2+(B1+1)N1,或(2B1+1)N1^2+(B1+2)N1;D2=(2B2+1)N1^2+(B2+1)N1,或(2B2+1)N1^2+(B2+2);B3=B1-|(D-D1)(B1-B2)/(2D-D1-D2)|,B4=B2+|(D-D2)(B1-B2)/(2D-D1-D2)|,再由B3求出N3;由B4求出N4;B1=5,B2=1,D1D2各有两种算法,分别与M=4D+1(前者),4D+3形(后者)的数对应.
(公式2)将B5=(B3+B1)/2,和N3;B6=(B4+B1)/2,和N4;代入粗化公式求出F1,F2值,N5=N3+F1因数为2N5+1,N6=N4+F2因数为2N6+1。粗化和细化公式的通用公式:
N=(n/(4(2B+1))),x=(n/(2N+1)-(2N+1))/4,F=(b+ -(b^2-4(2B+1)R/(4B+2),R=D-D1,D=(n/4),D1=(N+x)(N+x+1)-x^2,(N+x+1)^2-x^2-x-1,前式当n=4w+1,后式n=4w+3
b=2x-2BN-B,2x-2BN-B+1,前n=4w+1,后式当n=4w+3时,所有字母均取整数
(公式3)将N5及B7=X5/N5,N6及B8=X6/N6(四舍五入后取整数)代入细化公式求出F3,F4即可。该值不能整除M时,可用细化公式的修正值修正一下试试,按此顺序算一次,看看效果。注:注意细节,粗化公式F为两个值,细化公式F为四个值(即在F前加“+-”号,如N7=N5+-F3,N8=N6+-F4)。此法B值可取的大些,如B=10,或100,或1000,……,可用于分解有多个素因数的公开模数,先求出最小的一个素因子,再依次求出其他素因子。

补充B1和B2的分段公式:算1000位的质数用B1=10^(99K),B2=10^(99(K-1)),K=10至2
补充修正值公式:将N7B7和N8B8代入下式
F=((-b+-(b^2-4ac)^(1/2))/(2a),对于M=4D=1形的,为a=-(2B+1),b=2X-2BN-B-2H,c=-R-H(2N+1),对于M=4D+3形的,为a=-(2B+1),b=2X-2BN-B-2H+1,c=-R-H(2N+1),
设F(B+1)比实际多跳过了H,则H的通用(两种类型通用)计算公式为H=X-F(B+1)-(M/(2N+1)-(2N+1))/4,D=M/4,R=D-D8,D8=
(N8+X8)(N8+X8+1)-X8^2,或(N8+X8+1)^2-X8^2-X8-1,(前者为4D+1后者为4D+3形)X8=(M/(2N8+1)-(2N8+1))/4
请大侠免费试验,谁也不向谁要钱,谢谢参与!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
 楼主| 发表于 2011-4-29 14:12 | 显示全部楼层

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

我的问题希望朋友探讨,顶一下!
 楼主| 发表于 2011-11-9 17:47 | 显示全部楼层

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

[这个贴子最后由ysr在 2011/11/09 05:56pm 第 1 次编辑]

发细化公式原理和RSA密码体制的附件,粗化公式与细化公式原理相同,只B值取法不同,粗化公式B值用平均值,用中位线原理,希望大侠帮忙看看,编称试试,图片如下:

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2011-11-9 17:48 | 显示全部楼层

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

为什么不发表
 楼主| 发表于 2011-11-9 17:59 | 显示全部楼层

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

谢谢关注!没有实验,不会编称,不知谁要?
发表于 2011-11-9 19:08 | 显示全部楼层

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

下面引用由ysr2011/11/09 05:59pm 发表的内容:
谢谢关注!没有实验,不会编称,不知谁要?
要是认可,就不得了
发表于 2011-11-10 20:45 | 显示全部楼层

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

[这个贴子最后由天山草在 2011/11/10 08:47pm 第 1 次编辑]

下面这数是二个素数之积,如何分解?
6958000001674999998647
发表于 2011-11-11 07:52 | 显示全部楼层

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

[这个贴子最后由重生888在 2011/11/12 06:32am 第 1 次编辑]
下面引用由天山草2011/11/10 08:45pm 发表的内容:
下面这数是二个素数之积,如何分解?
6958000001674999998647
6958000001674999998647可用下面四个公式分解:
(30n+31)*(30m+17)=A    A=6958000001674999998647
(30n+11)*(30m+7)=A
(30n+13)*(30m+29)=A
(30n+23)*(30m+19)=A
任选一个就有可能性!最多把四个全用上!
 楼主| 发表于 2011-11-11 08:38 | 显示全部楼层

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

由于不知2素数是否位数相同,所以B值选大1些如100,1000就足够,因为才22位,用上面的方法可迅速分解!
 楼主| 发表于 2011-11-11 08:42 | 显示全部楼层

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

不会编称用计数器算1个小的,
举例:
M=14585113,(注:粗化和细化公式已省略)
1,D=14585113/4=3646278,B1=10,则N1=416,X1=4169,D1=3646249,试除833,831,……
2,B2=1,则N2=1102,X2=1102,D2=3645416,则B3=B4=9.707,则N3=N4=422,X3=4103,D3=3645541,
3,代入粗化公式B5=(9.707+1)/2=5,a=-11,b=3981,c=-737,判别式=15815933(取绝对值),则F=0,或-723由于422-723小于0可不算
4,422代入细化公式B6=9,则a=-19,b=601,c=-737,F=2,或60
5,试除2(422+60)+1=965,967,……,997,得14585113=997*14629
6,最大值计算,M=14585113=4((1910*1911)-3732)+1,则3732^(1/2)=61,N=1910-61=1849,2N+1=3699.
第3步改为迭代:
3,B1=B3=9.707,B2=B4=1.293,则迭代后B3=3.213,B4=7.769,
4,令B5=7,则N5=493,则代入细化公式,a=-15,b=-15,c=-547,则F=5,或-6
5,2(N5+F)+1=2(493+5)+1=997,试除得14585113=997*14629,完毕!公式和步骤由称序员掌握自己据试验数据灵活选择
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 07:48 , Processed in 0.073243 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表