欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

密码学RSA解密之Pollard_rho分解

程序员文章站 2022-12-07 09:16:42
对于Pollard_rho,它可以在O(sqrt§)的时间复杂度内找到n的一个小因子p,所以当n的两个素因子差距过大,即有一方过小的话都可以通过Pollard_rho进行分解例题:n = 1141976890333971618926153237155970525208639827587600850504737512307472709358968061186974826335155409395796814234383133165460693268476704295842740957911543544518...

对于Pollard_rho,它可以在O(sqrt(p))的时间复杂度内找到n的一个小因子p,所以当n的两个素因子差距过大,即有一方过小的话都可以通过Pollard_rho进行分解
例题:

n = 11419768903339716189261532371559705252086398275876008505047375123074727093589680611869748263351554093957968142343831331654606932684767042958427409579115435445187908134556329979271179879129295667476493886787230948520371350715808988496083694717544298343260369816980228394498856751096191942011545898984240281874509791880690092840536597771674772617299407710771426964764347566008897012753022763270832647775571317162594044338095870404550665457899223394942640876850692848671826594750236910363027949459768124646230555766323417693441861436560072288812137944884954974348317322412816157152702695143094487806945533233359294549423
e = 65537
c = 575061710950381118206735073806398116370706587076775765253483131078316908073202143802386128272374323616239083134747318254436706806781744501903333604772961927966747648954315962269321297121495398057938617145017999482722197661065698707836824505023856306403892307944203245563411961302499347604417024064678999003637933185177922884103362203639349298263339808508185861692596967147081382566246627668898774233029198694500565511361867375668367875805985660705137109665107860799277624050210666866958502948062330037309873148963011192405012811945540153592090345668265964477204465327474208098404082920129178960510763496025906621820

首先对n进行分解,得到p和q
密码学RSA解密之Pollard_rho分解再把 n,e,c,p,q放到python2的脚本中进行解密,脚本用到了Python2的primefac库和pycrypto库,请使用pip进行安装

from Crypto.Util.number import long_to_bytes,bytes_to_long,getPrime,isPrime
import primefac
def modinv(a,n):
	return primefac.modinv(a,n)%n
n=11419768903339716189261532371559705252086398275876008505047375123074727093589680611869748263351554093957968142343831331654606932684767042958427409579115435445187908134556329979271179879129295667476493886787230948520371350715808988496083694717544298343260369816980228394498856751096191942011545898984240281874509791880690092840536597771674772617299407710771426964764347566008897012753022763270832647775571317162594044338095870404550665457899223394942640876850692848671826594750236910363027949459768124646230555766323417693441861436560072288812137944884954974348317322412816157152702695143094487806945533233359294549423
e = 65537
c = 575061710950381118206735073806398116370706587076775765253483131078316908073202143802386128272374323616239083134747318254436706806781744501903333604772961927966747648954315962269321297121495398057938617145017999482722197661065698707836824505023856306403892307944203245563411961302499347604417024064678999003637933185177922884103362203639349298263339808508185861692596967147081382566246627668898774233029198694500565511361867375668367875805985660705137109665107860799277624050210666866958502948062330037309873148963011192405012811945540153592090345668265964477204465327474208098404082920129178960510763496025906621820
p=2499568793
q=4568695582742345507136251229217400959960856046691733722988345503429689799935696593516299458516865110324638359470761456115925725067558499862591063153473862179550706262380644940013531317571260647226561004191266100720745936563550699000939117068559232225644277283541933064331891245169739139886735615435506152070330233107807124410892978280063993668726927377177983100529270996547002022341628251905780873531481682713820809147098305289391835297208890779643623465917824350382592808578978330348769060448006691307027594085634520759293965723855183484366752511654099121387261343686017189426761536281948007104498017003911

d=modinv(e,(p-1)*(q-1))
m=pow(c,d,n)
print long_to_bytes(m)

得到flag
密码学RSA解密之Pollard_rho分解

注:在安装pip库的时候遇到了一些问题,在这里记录一下
在pip install pycrypto的时候,出现了error: command 'x86_64-linux-gnu-gcc' failed with exit status 1错误
密码学RSA解密之Pollard_rho分解

解决方法:对python2的包进行更新

sudo apt-get install python2.7-dev

然后重新使用pip install pycrypto命令进行安装就可以了

本文地址:https://blog.csdn.net/weixin_44145452/article/details/109924843