首页
论坛
课程
招聘
[讨论]关于1024位RSA的破解
2011-3-16 13:14 32175

[讨论]关于1024位RSA的破解

2011-3-16 13:14
32175
最近调试一个程序,发现里面采用了RSA 1024 bits加密,所以想咨询下现在对1024位RSA加密的破解是不是几乎不可能?

我用工具大致扫了扫,貌似没有啥漏洞可以利用,看来加密的人也比较了解RSA了,所以选用的数值应该没啥问题了。

N=
122716345539884565618424689845039796079433305032867745725508545808412166389869000674498989722929559053852742485683796922121417192123947006097495183681830392659725471507248876052923625829959461590885753602194496245599546670907842541466479199541710267192549374916305019349322336814984855926541154999659948379823

各位密码学的高手再帮着看看,希望能看出点端倪来。先谢谢了!

【公告】看雪招聘大学实习生!看雪20年安全圈的口碑,助你快速成长!

收藏
点赞0
打赏
分享
最新回复 (27)
雪    币: 314
活跃值: 活跃值 (79)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
NoFlexlm 活跃值 2011-3-16 15:50
2
0
转成16进制后的数

N=
AEC0FE119D2A4E32ADAF881EBB0E0AD4128EA4A64F76B3594772A4213C86419F
E4A2AE51E0D8ACF812E2AEE50573B848F980CF53889A84B928493EDFB92EFBF9
035FA741B0C027BB11BBC2EF5A6E20B29635BD17485D91530465C1F956248FFA
035DBBF1FE74AFA99D1CC9FE4C8C5C0FE6325CDA405DE880BCB0351A939B8EAF
雪    币: 56
活跃值: 活跃值 (12)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 活跃值 2011-3-16 16:04
3
0
能够求解这个问题的计算机或计算机组还没问世。
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-3-16 20:14
4
0
Z := IntegerRing();

N:=
122716345539884565618424689845039796079433305032867745725508545808412166389869000674498989722929559053852742485683796922121417192123947006097495183681830392659725471507248876052923625829959461590885753602194496245599546670907842541466479199541710267192549374916305019349322336814984855926541154999659948379823
;
IsPrime(N);
Ilog2(N);
Ilog(10,N);

false
1023
308

好像少一位。。。。。。。
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-3-16 20:37
5
0
试了啊:
N:=
122716345539884565618424689845039796079433305032867745725508545808412166389869000674498989722929559053852742485683796922121417192123947006097495183681830392659725471507248876052923625829959461590885753602194496245599546670907842541466479199541710267192549374916305019349322336814984855926541154999659948379823

少头一位:

time PollardRho(22716345539884565618424689845039796079433305032867745725508545808412166389869000674498989722929559053852742485683796922121417192123947006097495183681830392659725471507248876052923625829959461590885753602194496245599546670907842541466479199541710267192549374916305019349322336814984855926541154999659948379823) ;
[ <3, 1>, <11, 1>, <7400243, 1> ]
[ 93020473418133601986365115410234731396896942327138511063834254387904298875087\
3110129073596183979488972175909001734988977631287043196849571819145860309787479\
1624050440067193720171664727340285083302589503498038795195970477491913376303371\
5938466829245245011282435836062161915890300821186082923652886517 ]
Time: 0.040

少尾一位:

[ <2, 1>, <139, 1>, <353, 1>, <2039, 1>, <15061, 1>, <6358591, 1> ]
[ 64039950419263281142667937980578696743630972204552186441340531871876629610146\
2617525731936502701233860660400514662207063639059388629125320276929846635216611\
3763346939520137816285212002297528742601692677227414841951513384782411829061966\
97976490177638463722046204392444405713198314116143057 ]
Time: 0.050
雪    币: 314
活跃值: 活跃值 (79)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
NoFlexlm 活跃值 2011-3-16 21:31
6
0
数值没有问题,程序里是16进制的数。

想问下,如果改程序的e值,是否容易算出d值呢?比如可以改成2或者3。

当然改N值肯定是可以的。
雪    币: 56
活跃值: 活跃值 (12)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 活跃值 2011-3-16 22:29
7
0
N和e之间根本就毫无关系,这个破解的难度完全依赖于N的素数分解。
雪    币: 314
活跃值: 活跃值 (79)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
NoFlexlm 活跃值 2011-3-16 23:53
8
0
看来可行的方法就只能是替换掉这个N值了。。。
雪    币: 37
活跃值: 活跃值 (185)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
skypismire 活跃值 1 2011-3-17 11:04
9
0
替换N值,有何用....
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-3-17 12:38
10
0
PollardRho分解程序都没反应,NFS/QS/ECM吧

PollardRho能算出素因子40以下的,再大看来这是真的RSA质数积,素因子153-156,很大。。。

N1:=(N-1)/2;
time PollardRho(6135817276994228280921234492251989803971665251643387286275427290420608319493450\
0337249494861464779526926371242841898461060708596061973503048747591840915196329\
8627357536244380264618129149797307954428768010972481227997733354539212707332395\
99770855133596274687458152509674661168407492427963270577499829974189911);

[ <3, 1>, <11, 1> ]
[ 18593385687861297820973437855309060012035349247404203897804325122486691877252\
8788900756045034741756142201124978308783215335480594127192433481053308608833928\
2723113204655286000801873118635749418043723539427189337054538585922846099113128\
472720328943442311354165398560899232156618408861453432441742419090126967 ]
Time: 0.030

Ilog(10,
18593385687861297820973437855309060012035349247404203897804325122486691877252\
8788900756045034741756142201124978308783215335480594127192433481053308608833928\
2723113204655286000801873118635749418043723539427189337054538585922846099113128\
472720328943442311354165398560899232156618408861453432441742419090126967 );

[ <3, 1>, <11, 1> ]
[ 18593385687861297820973437855309060012035349247404203897804325122486691877252\
8788900756045034741756142201124978308783215335480594127192433481053308608833928\
2723113204655286000801873118635749418043723539427189337054538585922846099113128\
472720328943442311354165398560899232156618408861453432441742419090126967 ]

306
雪    币: 314
活跃值: 活跃值 (79)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
NoFlexlm 活跃值 2011-3-17 13:54
11
0
楼上的太高深了,不懂。
雪    币: 314
活跃值: 活跃值 (79)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
NoFlexlm 活跃值 2011-3-17 13:55
12
0
直接解掉程序,用自己的私钥来做注册机。
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-3-17 14:42
13
0
我也很菜。。。

RSA1024产生的算法有项要(N-1)/2也要有大素因子,还有些别的项更严格,就为防已知攻击,你这N强啊,素因子都有306

RSA1024是两155位左右素乘积,153---157位左右素数有天文个,有素数公式可估算,虽说越来越少,看看2到4位的就知道了,说解RSA1024最快得3年,也有说2018年的,现在攻RSA1024也没用分解它的,帐篷上金锁,别撬锁,我见过秏牛帐篷防雨但都透光

PrimesInInterval(10^2, 10^4);
[ 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569,
571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881,
883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181,
1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279,
1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471,
1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637,
1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867,
1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973,
1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063,
2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143,
2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269,
2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447,
2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,
2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683,
2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753,
2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857,
2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969,
2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083,
3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319,
3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529,
3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617,
3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719,
3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833,
3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929,
3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
4051, 4057, 4073, 4079, 4091, 。。。。。。。。。。。。

9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547,
9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679,
9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791,
9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901,
9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973 ]
雪    币: 314
活跃值: 活跃值 (79)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
NoFlexlm 活跃值 2011-3-17 15:57
14
0
今天关于这个RSA 1024位的加密,自己有了点想法,也许早就有人验证过是不可行的了,否则RSA的应用也不会如此广泛了。但还是想把自己的想法在这里晒一晒。。。

RSA中的N为两大素数的乘积,如果两大素数相对比较接近,那是不是可以做如下的尝试。

算出N^(1/2),然后以此数为基础,向后遍历寻找素数P,如果N mod P不为零,自然不是真的P值,然后寻找下一个素数去尝试。如果P和Q的值都非常大,那对于N为1024位的情况,P和Q也应该在512位左右。如果两数差距不是非常巨大,那是不是最多遍历n*(2^512)次会有收获?而这个n应该不会太大吧?

不知这样的想法可行不?是不是能把RSA 1024的强度降低到512位可接受的程度呢?
雪    币: 56
活跃值: 活跃值 (12)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 活跃值 2011-3-17 16:20
15
0
通常,RSA要求的两素数p,q满足|p-q|>2^32,且p-1和q-1的素因子尽可能少。
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-3-17 18:50
16
0
证书里的RSA1024数都不同,这些1024bit数有多少个?
难道都不容易分解吗?

顶端 Posted: 2010-06-17 19:17 | [楼 主]  

哪位帮算下:10^309/(in10^309)-10^308/(in10^308)=10^308*in10(10/309-1/308)=10^308*in10*(0.032362459546925566343042071197411-0.0032467532467532467532467532467532)=10^308*0.06704139129876960230334399110038=?

100000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000000000000000000000000000\
000000*0.06704139129876960230334399110038=

(6.704139129876960230334399110038`30.82634301855642*10^307

顶端 Posted: 2010-06-18 20:29 | 2 楼
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-3-17 18:52
17
0
几月前我在别处问过的
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-3-17 18:57
18
0
你可算算只155位就有多少素数。。。。。。

感觉这是个密码学理论和密码学实践差距问题
雪    币: 223
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
dINO 活跃值 2011-3-17 19:54
19
0
RSA-512行,RSA-768也可行,1024还是算了吧~
雪    币: 314
活跃值: 活跃值 (79)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
NoFlexlm 活跃值 2011-3-18 14:40
20
0
其实关于软件的破解,我基本已经做完了。替换掉N值,用自己的d值信息已经可以做license了。

对于RSA 1024bits的破解,也希望能在不久的将来,有所突破吧。
雪    币: 211
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
chonhuang 活跃值 2011-3-30 19:58
21
0
你用的是什么软件?
雪    币: 0
活跃值: 活跃值 (14)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
一鸿 活跃值 2011-3-31 23:28
22
0
把fishwater的箱底货翻出来,这个对你应该会有些启发:
http://bbs.pediy.com/showthread.php?t=101391&highlight=

可以考虑把n替换掉,我现在做了一个软件注册保护程序也是采用RSA算法的。
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-4-1 14:30
23
0
SAGE ,maxma
雪    币: 414
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
lilianjie 活跃值 1 2011-4-1 14:35
24
0
[QUOTE=lilianjie;937179]证书里的RSA1024数都不同,这些1024bit数有多少个?
难道都不容易分解吗?

顶端 Posted: 2010-06-17 19:17 | [楼 主]  

哪位帮算下:10^309/(in10^309)-10^308/(in10^308)=10^308*in10(10/309-...[/QUOTE]

那时水平有限,算成2048位的两素因子了,不过现在知道maple里有个PRIMEPI命令可算
雪    币: 0
活跃值: 活跃值 (373)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
123rsf 活跃值 2021-10-1 15:44
25
0
请问楼主用的漏洞扫描工具是什么,可否推荐一下
游客
登录 | 注册 方可回帖
返回