|
|
楼主 |
发表于 2012-1-4 15:30
|
显示全部楼层
[原创]RSA公钥密码的破解
谢谢老师关注!今用在线计算器做个分解因数举例,
例分解6958000001674999998647=?
解:令M=6958000001674999998647,则根号M=83 414 627 024,D=17 39500 00041 87499 99661,
令B1=10,B2=1,
则N1=9101281962,X1=95563460597,N1+X1+1=104664742560,
D1=4 55583 33344 52850 74148，
N2=24079728683 ,X2=24079728683,N2+X2+1=48195457367，
D2=17 42968 77736 74216 58200，
D-D1=12 83916 66697 34649 25513，
B3=B1-|（D-D1）（B1-B2）/（2D-D1-D2）|=10-12 83916 66697 34649 25513*9/12 80447 89002 47932 66974=10-9.024381306557847=0.9756186934421525=0.9756，
N3=24277999351，X3=23685616167,N3+X3+1=47963615519,
D3=1739 500 001 020 320 251 304,
D3-D=601570251643
带入粗化公式:
B5=(B3+B1)/2=5,
a=-11,
b=-148037526047,
c=60157025163,
判别式=21 915 109 118 116 203 446 209+2 646 909 107 172=21 915 109 120 763 112 553 381,方根=148037526055,
F1=13457956913,
N5=N3+F1=37735956264,
2N5+1=75471912529,与实际的差为4 471 912 488,是10位内的数字,带入细化公式和修正值公式则差距更小.
天山草老师的数据确实是本法弱点,但我的文中有论述的,是B值小于1的情况,在<细化公式原理>和<大素数的快速判断>2文中有,由于密码中用的是关联素数,B大于1,此情况很少甚至不会有,程序员可以自己考虑是否加入这1类,要有个条件语句,条件语句为,
当B3或B4小于1用此法,当B3或B4大于1,用原来方法.
相关公式(大素数快速判断的第4步)如下:
4：用2N11+1+-10^10,2N12+1+-10^10试除M不能整除即为质数。D5=（N5+X5）（N5+X5+1）-X5^2,(N5+X5+1)^2-X5^2-X5-1;N5=N-10,X5=(M/(2N5+1)-2N5-1)/4;B5=B2-|B2(D2-D)/(D2-D5)|,B6=|B2(D-D5)/(D2-D5)|;再求出N5和N6;即可.N5=(D/(2B5+1))^(1/2).;;D=M/4，将N5，N6，和B=1代入细化公式，得F5，F6，N11=N5+-F5，N12=N6+-F6即可。
其中B3B4B5B6均取点后七位.如下为粗化和细化公式的通用公式：
N3=(M/4(2B3+1))^(1/2),
F=(-b+-(b^2-4ac）^(1/2))/(2a),a=-(2B+1);
b=2X-2BN2-B,(当M为4D+1的形),或2X-2BN2-B+1(当4D+3型);
;c=D1-D;
D=M/4，
;X=(M/(2N2+1)-2N2-1)/4;粗化和细化公式的不同在于B值的不同;B的值由下公式给出：粗化公式用B7=（B1+B3）/2，B8=（B1+B4）/2，分别求得F1和F2，N7=N3+F1，N8=N4+F2，再代入细化公式B9=X7/N7，B10=X8/N8，由N7和B9，N8和B10，分别得F3，F4，（每个F均有两个值），N9=N7+-F3，N10=N8+-F4，数学原理：奇数可分为4D+1和4D+3两类，分别可分解如下形式：n=4D+1=(2N+1)(2N+1+4X)，n=4D+3=(2N+1)(2N+1+4X+2)，设B=X/N ，则由上述公式可求得n的值，（即将X=BN代入上式可导出N值的公式），用B带入上式，求出因数2N+1，当N值每增加1，X要减小（B+1），因为X为商的部分，除数2N+1增大，商必然减小，商实际减小4（B+1），设N增加F即为因数P=2N+2F+1，N值变为N+F，而X值变为X-F(B+1)，带入上述可导出F。
|
|
IP卡
狗仔卡
发表于 2011-11-28 21:55
显身卡