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

ysr · 发表于 2021-10-26 08:55

xyaoy 发表于 2021-10-26 00:48
二分的结果也很可靠，毕竟他找到的数字满足了不等式就必然是整数的平方根，并且把除法转成了乘法，速度很 ...

那就很好，我还需要学习，计算大整数必须用到快速的程序，谢谢！

ysr · 发表于 2021-10-26 09:00

xyaoy 发表于 2021-10-26 00:53
我这个数字:
1412009342033481003982372030920566038104976659538665039384361854531886531575348415424 ...

这个需要计算的，我的方法适用于部分类型，超出了这几个类型原理就失效了，其它类型是不管的因为RSA可能不用其它类型，你可以用网上的分解软件试试能分解的话就是其它类型，不能分解的话可以试试我的方法。
我在家养伤呢，不方便计算，需要出去锻炼身体。

xyaoy · 发表于 2021-10-26 09:03

ysr 发表于 2021-10-26 09:00
这个需要计算的，我的方法适用于部分类型，超出了这几个类型原理就失效了，其它类型是不管的因为RSA可能 ...

网上当然分解不了。。。。factordb上有这个数字但是没有分解结果，另外，我看你的帖子，没有能找到可行的计算方法（也可能是我读的还不透彻）

xyaoy · 发表于 2021-10-26 09:13

ysr 发表于 2021-10-26 09:00
这个需要计算的，我的方法适用于部分类型，超出了这几个类型原理就失效了，其它类型是不管的因为RSA可能 ...

由于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

2N? 请问是什么计算？

ysr · 发表于 2021-10-26 10:03

xyaoy 发表于 2021-10-26 01:13
由于n=pq 用如下公式所得数试除n即可快速分解n得到n=pq从2N7+1-10^8 至2N7+1+10^8
从2N2+1-10^8 至2N2+1 ...

我回来了，先把你的那个数进行素性判断。

N值是这样的《把B=1和B=10000代如分别得到N1和N2，然后据前面的公式可以得到在N1和N2之间的N值。
对于大数计算比较复杂，需要程序。

ysr · 发表于 2021-10-26 10:33

素性判断结果还没有出来，发一下对该数的试除因子的一种估算（这个是大的减去估计值f，另一个是小的加上估计值f，二者程序不同需要重新复制黏贴，都已经传上来了在《素性判断》一文中）
141200934203348100398237203092056603810497665953866503938436185453188653157534841542476799951117838232625775007972565407157639296613520419503480411605352582268797113156766586228582255481135809096970885597928003710586870460226020496368765994413857405308613414568674463104615847526186185331402709548604450804313的试除因子：
39999999996/-137205713341143166483599225370532451267484561853724622212431170202475709169811398958085599586406517109450176144741449341372492851750511124086693917561760965255241722/-5764362799251646393531010740864731961018516432318491005256177966211797215781696810599040700910065661891477374965133513738728789032057774107670629312646511672268370219351781400012988161904801605236198016274123174107932245547191695673957092512879079420714878243837039920272668513469621996304706285369554012552598862/-343022685744116519211717973150314437265880026965259550560154276828730907582209881819060358994974454137462804001931065555125326116563665897134484582517688637325825284299019495609155302925263725115448126554599415854413277548928407293381228569053885882970986334195696958808516499828395736403370702646783040833709137620480825250195332066346029705751616485729388228307272110395904471919314384352968003601692669069833053832709792004120727569872635122483280978485241472n2=3430268869483218079771013698691373808151044934173029953940282857373929827226350542345813032964821382244066155841007379142376169849467221803457567525837549（就是n2再减去一个数，需要解3次方程求f值）

xyaoy · 发表于 2021-10-26 10:48

ysr 发表于 2021-10-26 10:33
素性判断结果还没有出来，发一下对该数的试除因子的一种估算（这个是大的减去估计值f，另一个是小的加上估 ...

数域筛么？

ysr · 发表于 2021-10-26 10:49

本帖最后由 ysr 于 2021-10-26 02:50 编辑

这个结果出来了：
输入1: a=39999999996, b=-137205713341143166483599225370532451267484561853724622212431170202475709169811398958085599586406517109450176144741449341372492851750511124086693917561760965255241722, c=-5764362799251646393531010740864731961018516432318491005256177966211797215781696810599040700910065661891477374965133513738728789032057774107670629312646511672268370219351781400012988161904801605236198016274123174107932245547191695673957092512879079420714878243837039920272668513469621996304706285369554012552598862, d=-343022685744116519211717973150314437265880026965259550560154276828730907582209881819060358994974454137462804001931065555125326116563665897134484582517688637325825284299019495609155302925263725115448126554599415854413277548928407293381228569053885882970986334195696958808516499828395736403370702646783040833709137620480825250195332066346029705751616485729388228307272110395904471919314384352968003601692669069833053832709792004120727569872635122483280978485241472; 输出结果1: x1=3430184846642470029553885361127601029082111505879803923578836060594504759670960315206202668093834591217511419973824928597233260612031648294871547573910890.3189972129, x2=-21006385438292038372691158287874756947465789933355419031542129267366396039169283087240384834422374420220854210798618190303091091802374859697640175825.4791301230+45373586914982073553502967784909467415842396496667032387268643165023177825524506118249408673695309433342697458492400641149807964866735618478349158916.2858663382i, x3=-21006385438292038372691158287874756947465789933355419031542129267366396039169283087240384834422374420220854210798618190303091091802374859697640175825.4791301230-45373586914982073553502967784909467415842396496667032387268643165023177825524506118249408673695309433342697458492400641149807964866735618478349158916.2858663382i m=322886984163793801382632105260232974195253695992949905678895199768816633249462763844721657370882125667752118048472287989973072148593238716971901969900244368987724491007950225286633009366542975545554779297878464777261417586422010481444413033258262098523143608594376885284487255659871379050002139215177031291574868051010451821041562711412553396667715464003694226071553849557586983284653895194328983606100352344506500123553313407845363747137069816234443647237942442.7878647554 n=22192966076679152281859647937967862623671711145202373987970280916811750489286979910084925258039322680792539210419652420079252560623567692863172442708157338868592338905594288865131195610877309912152295419894186123102182130944367387103779912802116929803872883547217912545106030148112419842691151907341154460100178550616633594431166509031077944883402542118441491791586885952068185488483733108139682302040330496576053560337260566669344164315511006881658631055638.1911201654

f值取整数部分，就是f=3430184846642470029553885361127601029082111505879803923578836060594504759670960315206202668093834591217511419973824928597233260612031648294871547573910890

f和n2不知道哪个大？看不出来，减一下试试

ysr · 发表于 2021-10-26 10:53

xyaoy 发表于 2021-10-26 02:48
数域筛么？

不是数域筛，是其他方法，利用了欧拉原理等，就是前面的密码原理改变了功能而已。

ysr · 发表于 2021-10-26 10:54

ysr 发表于 2021-10-26 02:53
不是数域筛，是其他方法，利用了欧拉原理等，就是前面的密码原理改变了功能而已。

判断结果出来了：

*这是合数，有309位，用时2321.023秒

		自动登录	找回密码
密码			注册