标题: 求解一个简单的RSA题目
创建: 2023-09-29 17:11 更新: 2024-09-04 10:10 链接: https://scz.617.cn/python/202309291711.txt https://bbs.kanxue.com/thread-279074.htm
在看雪上看到这篇，应该是某个CTF题，已知条件用Python代码给出来，求flag。
https://bbs.kanxue.com/thread-279050.htm
from Crypto.Util.number import * import gmpy2 from jx2023 import flag, N, E
p = getPrime(1024) q = getPrime(1024) n = p*q e1 = 65537 m = bytes_to_long(flag) flagenc = pow(m, e1, n) print("n is %d"%n) print("flagenc is %d"%flagenc)
e2 = getPrime(122) d2 = gmpy2.invert(e2,(p-1)*(q-1))
c1 = pow(e2, 17, n) print("c1 is %d"%c1) c2 = pow(d2, E, N) print("N is %d"%N) print("E is %d"%E) print("c2 is %d"%c2)
n is 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017
flagenc is 1832021020586052459314800741399454951500982061634041208695770794636942946870944684781204845687614819955481692885982545657535952608100558061853098768890990198808258902800083671402999197944855469054517686346352932015639347886120547093778527571008483890754044661117042113616196224634409728684137167049242919543742476300792865668127981523314258326046469003175979484948578219765126696355000799390683333335678236115175267218556919253045561467791607635318317825080003594243366362225620291777807071774013296604063473075790067769213249767073197915283384750139985842145668772180552896467043807903712438253502782564391233381742
c1 is 7501185876834032332235110133210399479682524972321262801050956129090974843598848916000280794969942298848478394986779571489577405391165372124215072990382219817624500948789393550575823082225944683449240150364401487955484843961943987266467050723988657081468393104862383181698999645914573683498375228946881234015678337769955671069215094086232377038727627179660862997067062391991524231807127953937881102711759932207432989764529075450526104070640765094626829603546052250863300827172150912585791552174463067989228539713261075253602907390439036055716154404417991482262846355144755622306307102084492476950657455416297047328320
N is 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767755161686549607991960624754677443327266743771304424298446433734879681913848286620429175461870451099771965936783237191184798864363652633155779478727580408625494617809961465590055999661472563150275608218351797354628429061984878432442357241449134341597647749840966740944318445550768334070331490455379767889443973947
E is 3527492693
c2 is 11237333233288323887902003767693284822911839921763421974808265907264411495367936669799604082222415065052099486867383635886650443299459413288200494593477575168578514325691333043832168789236017314435940348619410775859032696755081680003338452277759483862961120696587307757666691557048088894021864124052243936836752825473836552342254367444581003605318145868368417247224184184040226260236268012375524575700053732026218766291274077482132408824236096242385408780811520890742688121731805867574680433796282417791570436991022839930635640379142355212121030479526679958801911687722402447690578345774902440346290388183936888977900
网友「hypersine」评论回复
这个应该还是很好办的
N是一个不安全的大合数，可以用yafu快速分解得到P、Q，因此可以算出E对应的D， 从而解密c2得到d2。题目中N的两个因数P、Q靠得太近了，两者之差未超过10000(实 际是2214)，所以很容易分解。如果P、Q很近，对N开方得到sqrt(N)，接着往sqrt(N) 下面穷举，很快就能找到因数。
c1 = pow(e2, 17, n)，但e2是一个122位的质数，因此e2^17应该有122 * 17 = 2074 位，太接近于n的2048位。这里可以暴力破解，因为c1 = pow(e2, 17, n)，所以存在 k使得e2^17 == k * n + c1，这个k范围不大，不超过2^(2074 - 2048 + 1) = 2^27， 自己写个程序穷举k就好，穷举到k * n + c1是一个完全17次方数就行，然后开17次 方得到e2。
现在知道d2、e2那就能分解n了，自己写个程序分解n得到p、q，最后解密flagenc。
他这个回复写得非常清楚，我第一次听说yafu，照着他说的做了一遍，挺有意思。后 文假设对RSA算法门儿清，不做科普，直接演示具体实现。
yafu在这里:
https://sourceforge.net/projects/yafu/
1) 用yafu分解N
yafu-x64.exe factor(...)
N = 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767755161686549607991960624754677443327266743771304424298446433734879681913848286620429175461870451099771965936783237191184798864363652633155779478727580408625494617809961465590055999661472563150275608218351797354628429061984878432442357241449134341597647749840966740944318445550768334070331490455379767889443973947 P = 173078108398797693665135881829236075381385640386270681597614075449385160047192826549689858183180936639070064309925929218966667262650552855318783567546131862440848767306600252044834602371191453881522882233745590790067041490962165388372445595736465527512700919336312857203007896777270237470242797091626699715021 Q = 173078108398797693665135881829236075381385640386270681597614075449385160047192826549689858183180936639070064309925929218966667262650552855318783567546131862440848767306600252044834602371191453881522882233745590790067041490962165388372445595736465527512700919336312857203007896777270237470242797091626699712807
2) 已知PHIN、E求D
PHIN = ( P - 1 ) * ( Q - 1 ) = 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767754815530332810396573294482913784855115981000023651757083238506728783143528192234776076082154084737898687796654617339326360931029127332050068841160445316361769736112426852389551909992267820767367845172587329863446848927901896508111580496557942868666592724439128068318604039534974779529856549969785584636044546120 E = 3527492693 D = pow( E, -1, PHIN ) = 11714295081028872095829649166462229534600990710051935510446747726812850082248692172993712813876838631530131841002864405509809020642090830057480563098086105449080792559844536414801734203530804966201381422491474684930923968884279519098355698332242744379775874767776071264516751080436520394348871721340176066921420286921422058287034111670045372227822407191894590900146761623610897328261136348388566000514394645573157244495497931592466836405935725526366908335327195113887202308698472178807611689040253147826886972580034858628911446318134969278899776543868656799330072299690972211680722019638416076131152808496762522693477
3) 已知N、D、c2求d2
c2 = 11237333233288323887902003767693284822911839921763421974808265907264411495367936669799604082222415065052099486867383635886650443299459413288200494593477575168578514325691333043832168789236017314435940348619410775859032696755081680003338452277759483862961120696587307757666691557048088894021864124052243936836752825473836552342254367444581003605318145868368417247224184184040226260236268012375524575700053732026218766291274077482132408824236096242385408780811520890742688121731805867574680433796282417791570436991022839930635640379142355212121030479526679958801911687722402447690578345774902440346290388183936888977900 c2 = pow( d2, E, N ) d2 = pow( c2, D, N ) = 1465609176542763075940181962864772219331485015754212502937973493443861834882896923514247538047873222749277952886635121836117307545036562427772437806854340361074148192771473277727294143006055601401312427467541596180527496770619498342429377442434816909227051361516850883374420088718381665893195779978368015188860126495766884766922749307806795261008469763388207146667293445107027754446987485763318465318384962761520682566768934401101857441607051135056991848789269185392218296823177075051007900064049736104615073193811802036090426977600680928083396357891022205464091444388907654190936465902019121558566966912994707102641
4) 已知n、c1求e2
c1 = pow( e2, 17, n ) e2 = getPrime( 122 )
pip3 install gmpy2
import gmpy2
c1 = 7501185876834032332235110133210399479682524972321262801050956129090974843598848916000280794969942298848478394986779571489577405391165372124215072990382219817624500948789393550575823082225944683449240150364401487955484843961943987266467050723988657081468393104862383181698999645914573683498375228946881234015678337769955671069215094086232377038727627179660862997067062391991524231807127953937881102711759932207432989764529075450526104070640765094626829603546052250863300827172150912585791552174463067989228539713261075253602907390439036055716154404417991482262846355144755622306307102084492476950657455416297047328320 n = 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017
for k in range( 1, 2 ** 26 + 1 ) : candidate_e2 = gmpy2.iroot( c1 + k * n, 17 ) if candidate_e2[1] : e2 = int( candidate_e2[0] ) break
print( e2 )
e2 = 3114339948601620171033737415539895793
5) 已知d2、e2求phin
phin = ( p - 1 ) * ( q - 1 ) d2 = gmpy2.invert( e2, ( p - 1 ) * ( q - 1 ) ) = gmpy2.invert( e2, phin ) = 1465609176542763075940181962864772219331485015754212502937973493443861834882896923514247538047873222749277952886635121836117307545036562427772437806854340361074148192771473277727294143006055601401312427467541596180527496770619498342429377442434816909227051361516850883374420088718381665893195779978368015188860126495766884766922749307806795261008469763388207146667293445107027754446987485763318465318384962761520682566768934401101857441607051135056991848789269185392218296823177075051007900064049736104615073193811802036090426977600680928083396357891022205464091444388907654190936465902019121558566966912994707102641 phin = d2 * e2 - 1 = 4564405207544251621160138521706538594591784054549538038692015318448340060945594510240871241985116895061629335549085777512188622521933821640819214402972309080980101472729575101642738824863473723503841109828134042994208926579706530001337866814284613148761778236517745008488863858493336754425945969109191308539573113018399570409432491059671276224719844411075725059282216645249950347005535736283487807684943380670169841615202868719656631327521626280108728698099730736885638610021004467364144372676841478360285710205019233880849492164726462754974464448072252673660705407944718572359537230563100649714802350999623686904206314914914672843032286408998095089312
此处我直接求phin，并不需要分解n，不需要知道p、q。
6) 已知phin、e1求d1
e1 = 65537 d1 = pow( e1, -1, phin ) = 1337625561378990442589706889968960743514805446567258610725526743764878148382151886166381938043641837230170026375264986845584855641183773722226739579527384045795563252593866356442169184892928823925641581936297700989468188105800442730147780185775215223997416921899992532966677133012237754329687325979387647768604623474241758842845422025604567361520504932467466858241516286810054570160189196195441763193265217650354486443712502809553767509595806251976261400059560683775967394663524601373205316411056615856503156235372376000054859796996146355067207290380635135119512764773887497150270412899505791818705371825057181907658063143809622146623710160233416456129
7) 已知n、d1、flagenc求m
n = 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017 flagenc = pow( m, e1, n ) = 1832021020586052459314800741399454951500982061634041208695770794636942946870944684781204845687614819955481692885982545657535952608100558061853098768890990198808258902800083671402999197944855469054517686346352932015639347886120547093778527571008483890754044661117042113616196224634409728684137167049242919543742476300792865668127981523314258326046469003175979484948578219765126696355000799390683333335678236115175267218556919253045561467791607635318317825080003594243366362225620291777807071774013296604063473075790067769213249767073197915283384750139985842145668772180552896467043807903712438253502782564391233381742 m = pow( flagenc, d1, n ) = 13040004482820175097649030762837021876498280967062558556361414290853656516097063334199255421
8) 已知m的long求bytes
m = bytes_to_long( flag )
import Crypto.Util.number
m = 13040004482820175097649030762837021876498280967062558556361414290853656516097063334199255421 Crypto.Util.number.long_to_bytes( m )
b'flag{616fa39c8781aa45031e15651228489a}'
9) 完整求解代码
import gmpy2 import Crypto.Util.number
N = 29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767755161686549607991960624754677443327266743771304424298446433734879681913848286620429175461870451099771965936783237191184798864363652633155779478727580408625494617809961465590055999661472563150275608218351797354628429061984878432442357241449134341597647749840966740944318445550768334070331490455379767889443973947
from yafu
P = 173078108398797693665135881829236075381385640386270681597614075449385160047192826549689858183180936639070064309925929218966667262650552855318783567546131862440848767306600252044834602371191453881522882233745590790067041490962165388372445595736465527512700919336312857203007896777270237470242797091626699715021 Q = 173078108398797693665135881829236075381385640386270681597614075449385160047192826549689858183180936639070064309925929218966667262650552855318783567546131862440848767306600252044834602371191453881522882233745590790067041490962165388372445595736465527512700919336312857203007896777270237470242797091626699712807 PHIN = ( P - 1 ) * ( Q - 1 ) E = 3527492693 D = pow( E, -1, PHIN ) c2 = 11237333233288323887902003767693284822911839921763421974808265907264411495367936669799604082222415065052099486867383635886650443299459413288200494593477575168578514325691333043832168789236017314435940348619410775859032696755081680003338452277759483862961120696587307757666691557048088894021864124052243936836752825473836552342254367444581003605318145868368417247224184184040226260236268012375524575700053732026218766291274077482132408824236096242385408780811520890742688121731805867574680433796282417791570436991022839930635640379142355212121030479526679958801911687722402447690578345774902440346290388183936888977900 d2 = pow( c2, D, N ) c1 = 7501185876834032332235110133210399479682524972321262801050956129090974843598848916000280794969942298848478394986779571489577405391165372124215072990382219817624500948789393550575823082225944683449240150364401487955484843961943987266467050723988657081468393104862383181698999645914573683498375228946881234015678337769955671069215094086232377038727627179660862997067062391991524231807127953937881102711759932207432989764529075450526104070640765094626829603546052250863300827172150912585791552174463067989228539713261075253602907390439036055716154404417991482262846355144755622306307102084492476950657455416297047328320 n = 8783117353228609820060025773720048836109116296720444291318682193328216575376903671782151675801584925066872219021319381163804239505579013818679255656402117567158378369967703317919205364480806143209934093723468591544792794708122025724968669241594029740047941933910596214170603520800531302474255823072859735679699558933009869241259760910402379740926512037606096020308081609477145816657118917642443176163860564823645522254412566891344745856141731910712040298787696382973824645074768059896153817964229975814742137600918515702471008251376697190058997187350022140633621955761877009643524289144711721902192261617574896449017
for k in range( 1, 2 ** 26 + 1 ) : candidate_e2 = gmpy2.iroot( c1 + k * n, 17 ) if candidate_e2[1] : e2 = int( candidate_e2[0] ) break
phin = d2 * e2 - 1 e1 = 65537 d1 = pow( e1, -1, phin ) flagenc = 1832021020586052459314800741399454951500982061634041208695770794636942946870944684781204845687614819955481692885982545657535952608100558061853098768890990198808258902800083671402999197944855469054517686346352932015639347886120547093778527571008483890754044661117042113616196224634409728684137167049242919543742476300792865668127981523314258326046469003175979484948578219765126696355000799390683333335678236115175267218556919253045561467791607635318317825080003594243366362225620291777807071774013296604063473075790067769213249767073197915283384750139985842145668772180552896467043807903712438253502782564391233381742 m = pow( flagenc, d1, n ) flag = Crypto.Util.number.long_to_bytes( m )
print( flag )
2024-09-04 10:10
https://sourceforge.net/projects/yafu/
yafu是个Windows平台的RSA工具，对P、Q特别接近的情形，有特别算法分解N。比如 这个
29956031606905964747690208452463077877156885038545111351508842927295510069375356079358289621922278316223452695576175299757472345749152582617292471487006177231261463793638998998552474423214925625798531662484883149899251884707864709821973208465998076621327151198438158796296778838657562126343551661323471767755161686549607991960624754677443327266743771304424298446433734879681913848286620429175461870451099771965936783237191184798864363652633155779478727580408625494617809961465590055999661472563150275608218351797354628429061984878432442357241449134341597647749840966740944318445550768334070331490455379767889443973947
用常规办法分解，有生之年系列。用yafu分解，我用一台四年前的PC，大概6、7秒。 所以在一些CTF中，有人提及yafu。
但是，今天在kanxue有位网友shuax用readyu开发的RDLP，用FERMAT分解N，47ms分解 成功，显示
Done Fermat factor successfully! with 1 tries,found bits of (P-Q) = 12
RDLP的FERMAT比yafu快出数量级去了，以前我真没用过，长见识了。