RSA & CRT
Discrete Log
Polynomial Ring
ECC
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import binasciifrom data import e1,e2,p,q1p,q1q,hint,flag n = [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L , 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L , 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L , 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L ] c = [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L , 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L , 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L , 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L ] f=lambda m,e,n,c:pow (m,e,n)==c assert (sum (map (f,[p]*4 ,[4 ]*4 ,n,c))==4 ) ee1 = 42 ee2 = 3 ce1 = 45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384 ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158 tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387 n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039 assert (pow (e1,ee1,n)==ce1)assert (pow (e2+tmp,ee2,n)==ce2) e = 46531 n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603 c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469 hint=int (binascii.hexlify(hint),16 ) assert (q1p*q1q==n)assert (q1p<q1q)assert (c==pow (hint,e,n)) flag=int (binascii.hexlify(flag),16 ) q1=q1p q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513 c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124 c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596 assert (c1==pow (flag,e1,p*q1))assert (c2==pow (flag,e2,p*q2))
1 2 f=lambda m,e,n,c:pow (m,e,n)==c assert (sum (map (f,[p]*4 ,[4 ]*4 ,n,c))==4 )
我们可以得到以下方程组
{ c 0 ≡ p 4 m o d n 0 c 1 ≡ p 4 m o d n 1 c 2 ≡ p 4 m o d n 2 c 3 ≡ p 4 m o d n 3 \begin{cases} c_{0} ≡ p^{4} \mod n_{0} \\ c_{1} ≡ p^{4} \mod n_{1} \\ c_{2} ≡ p^{4} \mod n_{2} \\ c_{3} ≡ p^{4} \mod n_{3} \end{cases}
⎩ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎧ c 0 ≡ p 4 m o d n 0 c 1 ≡ p 4 m o d n 1 c 2 ≡ p 4 m o d n 2 c 3 ≡ p 4 m o d n 3
使用CRT即可求出p的值
1 2 assert (pow (e1,ee1,n)==ce1)assert (pow (e2+tmp,ee2,n)==ce2)
c ≡ m e m o d n c ≡ m^{e} \mod n c ≡ m e m o d n m e = c + k ∗ n m^{e} = c + k*n m e = c + k ∗ n m e m^{e} m e m = m e e m = \sqrt[e]{m^{e}} m = e m e
1 2 3 4 hint=int (binascii.hexlify(hint),16 ) assert (q1p*q1q==n)assert (q1p<q1q)assert (c==pow (hint,e,n))
在线分解n得到q1p与q1q
1 2 assert (c1==pow (flag,e1,p*q1))assert (c2==pow (flag,e2,p*q2))
这里有p h i 1 = ( p − 1 ) ∗ ( q 1 − 1 ) phi1 = (p - 1)*(q_{1} - 1) p h i 1 = ( p − 1 ) ∗ ( q 1 − 1 ) p h i 2 = ( p − 1 ) ∗ ( q 2 − 1 ) phi2 = (p - 1)*(q_{2} - 1) p h i 2 = ( p − 1 ) ∗ ( q 2 − 1 )
而在求d时，e1在模phi1时不存在逆元，e2在模phi2时不存在逆元即e，phi不互素 e = a ∗ b e = a * b e = a ∗ b b = g c d ( e , p h i ) b = gcd(e, phi) b = g c d ( e , p h i ) a = e / / b a = e // b a = e / / b e ∗ d ≡ 1 m o d p h i e * d ≡ 1 \mod phi e ∗ d ≡ 1 m o d p h i a ∗ b ∗ d ≡ 1 m o d p h i a * b * d ≡ 1 \mod phi a ∗ b ∗ d ≡ 1 m o d p h i b d = i n v e r t ( a , p h i ) bd = invert(a, phi) b d = i n v e r t ( a , p h i ) c ≡ m e ≡ m a b m o d n c ≡ m^{e} ≡ m^{ab} \mod n c ≡ m e ≡ m a b m o d n c b d ≡ ( m a b ) b d ≡ m a b b d ≡ m b m o d b c^{bd} ≡ (m^{ab})^{bd} ≡ m^{abbd} ≡ m^b \mod b c b d ≡ ( m a b ) b d ≡ m a b b d ≡ m b m o d b b1 = b2 = 14
思路扩展：
若b为2则可以使用Rabin Attack
若b为特别小的值则可以使用低指数的办法进行爆破
但是14次方对于爆破来说过于困难，需要结合两个式子进行CRT
{ c 1 = m 14 m o d p ∗ q 1 c 2 = m 14 m o d p ∗ q 2 \begin{cases} c_{1} = m^{14} \mod p*q_{1} \\ c_{2} = m^{14} \mod p*q_{2} \end{cases}
{ c 1 = m 1 4 m o d p ∗ q 1 c 2 = m 1 4 m o d p ∗ q 2
那么可以对式子进行进一步的分解
{ c 1 = m 14 m o d p c 2 = m 14 m o d q 1 c 3 = m 14 m o d q 2 \begin{cases} c_{1} = m^{14} \mod p \\ c_{2} = m^{14} \mod q_{1} \\ c_{3} = m^{14} \mod q_{2} \end{cases}
⎩ ⎪ ⎨ ⎪ ⎧ c 1 = m 1 4 m o d p c 2 = m 1 4 m o d q 1 c 3 = m 1 4 m o d q 2
使用CRT可以得到 p ∗ q 1 ∗ q 2 p*q_{1}*q_{2} p ∗ q 1 ∗ q 2 m 14 m^{14} m 1 4 m 1 m_{1} m 1 m 2 ≡ m 1 m o d q 1 ∗ q 2 m_{2} ≡ m_{1} \mod q_{1}*q_{2} m 2 ≡ m 1 m o d q 1 ∗ q 2 m 2 ≡ m 14 m o d q 1 ∗ q 2 m_{2} ≡ m^{14} \mod q_{1}*q_{2} m 2 ≡ m 1 4 m o d q 1 ∗ q 2 g c d ( 14 , ( q 1 − 1 ) ∗ ( q 2 − 1 ) ) = 2 gcd(14, (q_{1} - 1)*(q_{2} - 1)) = 2 g c d ( 1 4 , ( q 1 − 1 ) ∗ ( q 2 − 1 ) ) = 2 c ≡ m 2 m o d n c ≡ m^{2} \mod n c ≡ m 2 m o d n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 import binasciiimport gmpy2 n = [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423 , 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421 , 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303 , 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791 ] c = [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569 , 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031 , 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446 , 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797 ] k0 = gmpy2.invert(n[1 ]*n[2 ], n[0 ]) k1 = gmpy2.invert(n[0 ]*n[2 ], n[1 ]) k2 = gmpy2.invert(n[0 ]*n[1 ], n[2 ]) p = gmpy2.iroot((n[1 ]*n[2 ]*k0*c[0 ] + n[0 ]*n[2 ]*k1*c[1 ] + n[0 ]*n[1 ]*k2*c[2 ])%(n[0 ]*n[1 ]*n[2 ]),4 )[0 ] ee1 = 42 ee2 = 3 ce1 = 45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384 ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158 tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387 n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039 for i in range (0 ,10000000 ): k = gmpy2.iroot(i*n+ce1, ee1) if k[1 ] == True : e1 = k[0 ] break for i in range (0 ,100000 ): k = gmpy2.iroot(i*n+ce2, ee2) if k[1 ] == True : e2tmp = k[0 ] e2 = e2tmp - tmp break e = 46531 n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603 c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469 q1p = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871 q1q = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693 phi = (q1p - 1 )*(q1q - 1 ) d = gmpy2.invert(e, phi) hint = binascii.unhexlify(hex (pow (c, d, n))[2 :].encode()) print(hint) q1=q1p q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513 c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124 c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596 phi1 = (p - 1 )*(q1 - 1 ) b1 = gmpy2.gcd(e1, phi1) a1 = e1 // b1 bd1 = gmpy2.invert(a1, phi1) flagb1 = pow (c1, bd1, p*q1) phi2 = (p - 1 )*(q2 - 1 ) b2 = gmpy2.gcd(e2, phi2) a2 = e2 // b2 bd2 = gmpy2.invert(a2, phi2) flagb2 = pow (c2, bd2, p*q2) n01 = p n02 = q1 n03 = q2 c01 = flagb1 % n01 c02 = flagb1 % n02 c03 = flagb2 % n03 k01 = gmpy2.invert(n02*n03, n01) k02 = gmpy2.invert(n01*n03, n02) k03 = gmpy2.invert(n01*n02, n03) n3 = q1 * q2 flag14 = (n02*n03*k01*c01 + n01*n03*k02*c02 + n01*n02*k03*c03)%(n01*n02*n03)%n3 phi3 = (q1 - 1 )*(q2 - 1 ) e3 = b1 b3 = gmpy2.gcd(e3, phi3) a3 = e3 // b3 bd3 = gmpy2.invert(a3, phi3) flag2 = pow (flag14, bd3, n3) flag = gmpy2.iroot(flag2, 2 )[0 ] print(binascii.unhexlify(hex (flag)[2 :].encode()))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 from Crypto.Util.number import *from gmpy2 import *from secret import flagp = getPrime(25 ) e = q = getPrime(25 ) n = p * q m = bytes_to_long(flag.strip(b"npuctf{" ).strip(b"}" )) c = pow (m, e, n) print(c) print(pow (2 , e, n)) print(pow (4 , e, n)) print(pow (8 , e, n)) ''' 169169912654178 128509160179202 518818742414340 358553002064450 '''
{ c 1 ≡ 2 e m o d n c 2 ≡ 4 e m o d n c 3 ≡ 8 e m o d n \begin{cases} c_{1} ≡ 2^{e} \mod n \\ c_{2} ≡ 4^{e} \mod n \\ c_{3} ≡ 8^{e} \mod n \end{cases}
⎩ ⎪ ⎨ ⎪ ⎧ c 1 ≡ 2 e m o d n c 2 ≡ 4 e m o d n c 3 ≡ 8 e m o d n
c 1 2 ≡ ( 2 e ) 2 ≡ 4 e ≡ c 2 m o d n c_{1}^{2} ≡ (2^{e})^{2} ≡ 4^{e} ≡ c_{2} \mod n c 1 2 ≡ ( 2 e ) 2 ≡ 4 e ≡ c 2 m o d n c 1 2 − c 2 ≡ 0 m o d n c_{1}^{2} - c_{2} ≡ 0 \mod n c 1 2 − c 2 ≡ 0 m o d n c 1 2 − c 2 = k 1 ∗ n c_{1}^{2} - c_{2} = k_{1}*n c 1 2 − c 2 = k 1 ∗ n
c 1 3 ≡ ( 2 e ) 3 ≡ 8 e ≡ c 3 m o d n c_{1}^{3} ≡ (2^{e})^{3} ≡ 8^{e} ≡ c_{3} \mod n c 1 3 ≡ ( 2 e ) 3 ≡ 8 e ≡ c 3 m o d n c 1 3 − c 3 ≡ 0 m o d n c_{1}^{3} - c_{3} ≡ 0 \mod n c 1 3 − c 3 ≡ 0 m o d n c 1 2 − c 2 = k 2 ∗ n c_{1}^{2} - c_{2} = k_{2}*n c 1 2 − c 2 = k 2 ∗ n
g c d ( k 1 ∗ n , k 2 ∗ n ) = g c d ( k 1 , k 2 ) ∗ n gcd(k_{1}*n, k_{2}*n) = gcd(k_{1}, k_{2})*n g c d ( k 1 ∗ n , k 2 ∗ n ) = g c d ( k 1 , k 2 ) ∗ n
1 2 3 4 5 F = IntegerModRing(n) e = bsgs(F(2 ), F(c1), (0 , 2 **32 )) import sympysympy.discrete_log(n, c1, 2 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c = 169169912654178 c1 = 128509160179202 c2 = 518818742414340 c3 = 358553002064450 import gmpy2import sympyfrom Crypto.Util.number import *n1 = gmpy2.gcd(c1*c1 - c2,c1**3 - c3) n = n1 // 2 p = 18195301 q = 28977097 F = IntegerModRing(n) e = bsgs(F(2 ), F(c1), (0 , 2 **32 )) phi = (p - 1 )*(q - 1 ) d = gmpy2.invert(e, phi) flag = pow (c, d, n) print(long_to_bytes(flag))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 flag = bytearray (raw_input()) flag = list (flag) length = len (flag) bits = 16 p = random_prime(2 ^bits-1 , False , 2 ^(bits-1 )) file_out = open ("downloads/polynomial_rsa.txt" , "w" ) file_out.write("Prime: " + str (p) + "\n" ) R.<y> = PolynomialRing(GF(p)) def gen_irreducable_poly (deg ): while True : out = R.random_element(degree=deg) if out.is_irreducible(): return out P = gen_irreducable_poly(ZZ.random_element(length, 2 *length)) Q = gen_irreducable_poly(ZZ.random_element(length, 2 *length)) e = 65537 N = P*Q file_out.write("Modulus: " + str (N) + "\n" ) S.<x> = R.quotient(N) m = S(flag) c = m^e file_out.write("Ciphertext: " + str (c)) file_out.close() Prime: 43753 Modulus: 34036 *y^177 + 23068 *y^176 + 13147 *y^175 + 36344 *y^174 + 10045 *y^173 + 41049 *y^172 + 17786 *y^171 + 16601 *y^170 + 7929 *y^169 + 37570 *y^168 + 990 *y^167 + 9622 *y^166 + 39273 *y^165 + 35284 *y^164 + 15632 *y^163 + 18850 *y^162 + 8800 *y^161 + 33148 *y^160 + 12147 *y^159 + 40487 *y^158 + 6407 *y^157 + 34111 *y^156 + 8446 *y^155 + 21908 *y^154 + 16812 *y^153 + 40624 *y^152 + 43506 *y^151 + 39116 *y^150 + 33011 *y^149 + 23914 *y^148 + 2210 *y^147 + 23196 *y^146 + 43359 *y^145 + 34455 *y^144 + 17684 *y^143 + 25262 *y^142 + 982 *y^141 + 24015 *y^140 + 27968 *y^139 + 37463 *y^138 + 10667 *y^137 + 39519 *y^136 + 31176 *y^135 + 27520 *y^134 + 32118 *y^133 + 8333 *y^132 + 38945 *y^131 + 34713 *y^130 + 1107 *y^129 + 43604 *y^128 + 4433 *y^127 + 18110 *y^126 + 17658 *y^125 + 32354 *y^124 + 3219 *y^123 + 40238 *y^122 + 10439 *y^121 + 3669 *y^120 + 8713 *y^119 + 21027 *y^118 + 29480 *y^117 + 5477 *y^116 + 24332 *y^115 + 43480 *y^114 + 33406 *y^113 + 43121 *y^112 + 1114 *y^111 + 17198 *y^110 + 22829 *y^109 + 24424 *y^108 + 16523 *y^107 + 20424 *y^106 + 36206 *y^105 + 41849 *y^104 + 3584 *y^103 + 26500 *y^102 + 31897 *y^101 + 34640 *y^100 + 27449 *y^99 + 30962 *y^98 + 41434 *y^97 + 22125 *y^96 + 24314 *y^95 + 3944 *y^94 + 18400 *y^93 + 38476 *y^92 + 28904 *y^91 + 27936 *y^90 + 41867 *y^89 + 25573 *y^88 + 25659 *y^87 + 33443 *y^86 + 18435 *y^85 + 5934 *y^84 + 38030 *y^83 + 17563 *y^82 + 24086 *y^81 + 36782 *y^80 + 20922 *y^79 + 38933 *y^78 + 23448 *y^77 + 10599 *y^76 + 7156 *y^75 + 29044 *y^74 + 23605 *y^73 + 7657 *y^72 + 28200 *y^71 + 2431 *y^70 + 3860 *y^69 + 23259 *y^68 + 14590 *y^67 + 33631 *y^66 + 15673 *y^65 + 36049 *y^64 + 29728 *y^63 + 22413 *y^62 + 18602 *y^61 + 18557 *y^60 + 23505 *y^59 + 17642 *y^58 + 12595 *y^57 + 17255 *y^56 + 15316 *y^55 + 8948 *y^54 + 38 *y^53 + 40329 *y^52 + 9823 *y^51 + 5798 *y^50 + 6379 *y^49 + 8662 *y^48 + 34640 *y^47 + 38321 *y^46 + 18760 *y^45 + 13135 *y^44 + 15926 *y^43 + 34952 *y^42 + 28940 *y^41 + 13558 *y^40 + 42579 *y^39 + 38015 *y^38 + 33788 *y^37 + 12381 *y^36 + 195 *y^35 + 13709 *y^34 + 31500 *y^33 + 32994 *y^32 + 30486 *y^31 + 40414 *y^30 + 2578 *y^29 + 30525 *y^28 + 43067 *y^27 + 6195 *y^26 + 36288 *y^25 + 23236 *y^24 + 21493 *y^23 + 15808 *y^22 + 34500 *y^21 + 6390 *y^20 + 42994 *y^19 + 42151 *y^18 + 19248 *y^17 + 19291 *y^16 + 8124 *y^15 + 40161 *y^14 + 24726 *y^13 + 31874 *y^12 + 30272 *y^11 + 30761 *y^10 + 2296 *y^9 + 11017 *y^8 + 16559 *y^7 + 28949 *y^6 + 40499 *y^5 + 22377 *y^4 + 33628 *y^3 + 30598 *y^2 + 4386 *y + 23814 Ciphertext: 5209 *x^176 + 10881 *x^175 + 31096 *x^174 + 23354 *x^173 + 28337 *x^172 + 15982 *x^171 + 13515 *x^170 + 21641 *x^169 + 10254 *x^168 + 34588 *x^167 + 27434 *x^166 + 29552 *x^165 + 7105 *x^164 + 22604 *x^163 + 41253 *x^162 + 42675 *x^161 + 21153 *x^160 + 32838 *x^159 + 34391 *x^158 + 832 *x^157 + 720 *x^156 + 22883 *x^155 + 19236 *x^154 + 33772 *x^153 + 5020 *x^152 + 17943 *x^151 + 26967 *x^150 + 30847 *x^149 + 10306 *x^148 + 33966 *x^147 + 43255 *x^146 + 20342 *x^145 + 4474 *x^144 + 3490 *x^143 + 38033 *x^142 + 11224 *x^141 + 30565 *x^140 + 31967 *x^139 + 32382 *x^138 + 9759 *x^137 + 1030 *x^136 + 32122 *x^135 + 42614 *x^134 + 14280 *x^133 + 16533 *x^132 + 32676 *x^131 + 43070 *x^130 + 36009 *x^129 + 28497 *x^128 + 2940 *x^127 + 9747 *x^126 + 22758 *x^125 + 16615 *x^124 + 14086 *x^123 + 13038 *x^122 + 39603 *x^121 + 36260 *x^120 + 32502 *x^119 + 17619 *x^118 + 17700 *x^117 + 15083 *x^116 + 11311 *x^115 + 36496 *x^114 + 1300 *x^113 + 13601 *x^112 + 43425 *x^111 + 10376 *x^110 + 11551 *x^109 + 13684 *x^108 + 14955 *x^107 + 6661 *x^106 + 12674 *x^105 + 21534 *x^104 + 32132 *x^103 + 34135 *x^102 + 43684 *x^101 + 837 *x^100 + 29311 *x^99 + 4849 *x^98 + 26632 *x^97 + 26662 *x^96 + 10159 *x^95 + 32657 *x^94 + 12149 *x^93 + 17858 *x^92 + 35805 *x^91 + 19391 *x^90 + 30884 *x^89 + 42039 *x^88 + 17292 *x^87 + 4694 *x^86 + 1497 *x^85 + 1744 *x^84 + 31071 *x^83 + 26246 *x^82 + 24402 *x^81 + 22068 *x^80 + 39263 *x^79 + 23703 *x^78 + 21484 *x^77 + 12241 *x^76 + 28821 *x^75 + 32886 *x^74 + 43075 *x^73 + 35741 *x^72 + 19936 *x^71 + 37219 *x^70 + 33411 *x^69 + 8301 *x^68 + 12949 *x^67 + 28611 *x^66 + 42654 *x^65 + 6910 *x^64 + 18523 *x^63 + 31144 *x^62 + 21398 *x^61 + 36298 *x^60 + 27158 *x^59 + 918 *x^58 + 38601 *x^57 + 4269 *x^56 + 5699 *x^55 + 36444 *x^54 + 34791 *x^53 + 37978 *x^52 + 32481 *x^51 + 8039 *x^50 + 11012 *x^49 + 11454 *x^48 + 30450 *x^47 + 1381 *x^46 + 32403 *x^45 + 8202 *x^44 + 8404 *x^43 + 37648 *x^42 + 43696 *x^41 + 34237 *x^40 + 36490 *x^39 + 41423 *x^38 + 35792 *x^37 + 36950 *x^36 + 31086 *x^35 + 38970 *x^34 + 12439 *x^33 + 7963 *x^32 + 16150 *x^31 + 11382 *x^30 + 3038 *x^29 + 20157 *x^28 + 23531 *x^27 + 32866 *x^26 + 5428 *x^25 + 21132 *x^24 + 13443 *x^23 + 28909 *x^22 + 42716 *x^21 + 6567 *x^20 + 24744 *x^19 + 8727 *x^18 + 14895 *x^17 + 28172 *x^16 + 30903 *x^15 + 26608 *x^14 + 27314 *x^13 + 42224 *x^12 + 42551 *x^11 + 37726 *x^10 + 11203 *x^9 + 36816 *x^8 + 5537 *x^7 + 20301 *x^6 + 17591 *x^5 + 41279 *x^4 + 7999 *x^3 + 33753 *x^2 + 34551 *x + 9659
第一次见到RSA与多项式环结合的题
1 (34036) * (y^65 + 39688*y^64 + 22199*y^63 + 41942*y^62 + 7803*y^61 + 19710*y^60 + 14794*y^59 + 41388*y^58 + 2418*y^57 + 19208*y^56 + 39941*y^55 + 36392*y^54 + 19813*y^53 + 33864*y^52 + 29099*y^51 + 15484*y^50 + 27185*y^49 + 27721*y^48 + 31508*y^47 + 19404*y^46 + 10134*y^45 + 43481*y^44 + 3899*y^43 + 32849*y^42 + 3534*y^41 + 32086*y^40 + 14221*y^39 + 42982*y^38 + 1403*y^37 + 1619*y^36 + 36054*y^35 + 33615*y^34 + 6628*y^33 + 31709*y^32 + 6968*y^31 + 28517*y^30 + 12938*y^29 + 21124*y^28 + 10400*y^27 + 28889*y^26 + 7273*y^25 + 36442*y^24 + 14935*y^23 + 29365*y^22 + 4869*y^21 + 43562*y^20 + 6435*y^19 + 4403*y^18 + 32311*y^17 + 7575*y^16 + 28199*y^15 + 28065*y^14 + 23870*y^13 + 37314*y^12 + 15299*y^11 + 7082*y^10 + 36230*y^9 + 18367*y^8 + 12531*y^7 + 25906*y^6 + 26878*y^5 + 43073*y^4 + 11582*y^3 + 4482*y^2 + 35044*y + 31388) * (y^112 + 31097*y^111 + 15815*y^110 + 17170*y^109 + 43684*y^108 + 16873*y^107 + 17269*y^106 + 10853*y^105 + 10690*y^104 + 24864*y^103 + 10224*y^102 + 28704*y^101 + 16049*y^100 + 1154*y^99 + 40034*y^98 + 29922*y^97 + 27404*y^96 + 32514*y^95 + 40962*y^94 + 32858*y^93 + 36590*y^92 + 41302*y^91 + 20803*y^90 + 43521*y^89 + 13746*y^88 + 19857*y^87 + 21539*y^86 + 36888*y^85 + 16032*y^84 + 35825*y^83 + 24705*y^82 + 31143*y^81 + 22088*y^80 + 6686*y^79 + 37947*y^78 + 5661*y^77 + 29405*y^76 + 36071*y^75 + 35492*y^74 + 28985*y^73 + 36015*y^72 + 24095*y^71 + 34920*y^70 + 6615*y^69 + 9606*y^68 + 4255*y^67 + 22981*y^66 + 3910*y^65 + 23897*y^64 + 22711*y^63 + 23350*y^62 + 7969*y^61 + 8558*y^60 + 8001*y^59 + 8431*y^58 + 3314*y^57 + 23364*y^56 + 39391*y^55 + 32722*y^54 + 2543*y^53 + 22196*y^52 + 24189*y^51 + 19420*y^50 + 10649*y^49 + 19070*y^48 + 23863*y^47 + 19597*y^46 + 39699*y^45 + 7620*y^44 + 25067*y^43 + 29912*y^42 + 14998*y^41 + 14492*y^40 + 31322*y^39 + 43145*y^38 + 32006*y^37 + 38976*y^36 + 32534*y^35 + 6972*y^34 + 37351*y^33 + 30104*y^32 + 6032*y^31 + 33729*y^30 + 27110*y^29 + 5268*y^28 + 2974*y^27 + 2985*y^26 + 31610*y^25 + 28364*y^24 + 34924*y^23 + 17414*y^22 + 28813*y^21 + 43680*y^20 + 32175*y^19 + 18248*y^18 + 25171*y^17 + 31185*y^16 + 30125*y^15 + 36836*y^14 + 7218*y^13 + 11292*y^12 + 31123*y^11 + 40360*y^10 + 34093*y^9 + 39606*y^8 + 2788*y^7 + 27277*y^6 + 21835*y^5 + 1331*y^4 + 32614*y^3 + 25020*y^2 + 20981*y + 12108)
如果对多项式环不清楚的话，可能就直接计算 p h i = ( p − 1 ) ∗ ( q − 1 ) phi=(p - 1)*(q - 1) p h i = ( p − 1 ) ∗ ( q − 1 ) p h i ( n ) phi(n) p h i ( n ) p h i ( a ∗ b ) = p h i ( a ) ∗ p h i ( b ) phi(a*b)=phi(a)*phi(b) p h i ( a ∗ b ) = p h i ( a ) ∗ p h i ( b ) p h i ( n ) phi(n) p h i ( n ) p h i ( p ) phi(p) p h i ( p ) p h i ( q ) phi(q) p h i ( q ) p h i ( p ) phi(p) p h i ( p ) p h i ( p ) = ( 4375 3 65 − 1 ) phi(p) = (43753^{65} - 1) p h i ( p ) = ( 4 3 7 5 3 6 5 − 1 ) p h i ( q ) = ( 4375 3 112 − 1 ) phi(q) = (43753^{112} - 1) p h i ( q ) = ( 4 3 7 5 3 1 1 2 − 1 ) p h i ( n ) = p h i ( p ) ∗ p h i ( q ) = ( 4375 3 65 − 1 ) ∗ ( 4375 3 112 − 1 ) phi(n) = phi(p)*phi(q) = (43753^{65} - 1)*(43753^{112} - 1) p h i ( n ) = p h i ( p ) ∗ p h i ( q ) = ( 4 3 7 5 3 6 5 − 1 ) ∗ ( 4 3 7 5 3 1 1 2 − 1 )
值得一提的是，解出的明文以多项式的形式给出
1 125*y^62 + 111*y^61 + 114*y^60 + 117*y^59 + 53*y^58 + 51*y^57 + 51*y^56 + 100*y^55 + 106*y^54 + 110*y^53 + 102*y^52 + 106*y^51 + 100*y^50 + 104*y^49 + 101*y^48 + 117*y^47 + 52*y^46 + 52*y^45 + 57*y^44 + 48*y^43 + 50*y^42 + 107*y^41 + 35*y^40 + 101*y^39 + 114*y^38 + 117*y^37 + 99*y^36 + 101*y^35 + 115*y^34 + 110*y^33 + 105*y^32 + 95*y^31 + 116*y^30 + 117*y^29 + 98*y^28 + 95*y^27 + 110*y^26 + 117*y^25 + 102*y^24 + 95*y^23 + 115*y^22 + 105*y^21 + 95*y^20 + 97*y^19 + 101*y^18 + 107*y^17 + 105*y^16 + 95*y^15 + 109*y^14 + 111*y^13 + 114*y^12 + 102*y^11 + 95*y^10 + 65*y^9 + 83*y^8 + 82*y^7 + 123*y^6 + 114*y^5 + 118*y^4 + 101*y^3 + 116*y^2 + 97*y + 119
幂代表位数，系数即为flag的内容
1 2 3 4 5 6 7 8 9 10 11 12 R.<y> = PolynomialRing(GF(43753 )) n = R("34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814" ) c = R("5209*y^176 + 10881*y^175 + 31096*y^174 + 23354*y^173 + 28337*y^172 + 15982*y^171 + 13515*y^170 + 21641*y^169 + 10254*y^168 + 34588*y^167 + 27434*y^166 + 29552*y^165 + 7105*y^164 + 22604*y^163 + 41253*y^162 + 42675*y^161 + 21153*y^160 + 32838*y^159 + 34391*y^158 + 832*y^157 + 720*y^156 + 22883*y^155 + 19236*y^154 + 33772*y^153 + 5020*y^152 + 17943*y^151 + 26967*y^150 + 30847*y^149 + 10306*y^148 + 33966*y^147 + 43255*y^146 + 20342*y^145 + 4474*y^144 + 3490*y^143 + 38033*y^142 + 11224*y^141 + 30565*y^140 + 31967*y^139 + 32382*y^138 + 9759*y^137 + 1030*y^136 + 32122*y^135 + 42614*y^134 + 14280*y^133 + 16533*y^132 + 32676*y^131 + 43070*y^130 + 36009*y^129 + 28497*y^128 + 2940*y^127 + 9747*y^126 + 22758*y^125 + 16615*y^124 + 14086*y^123 + 13038*y^122 + 39603*y^121 + 36260*y^120 + 32502*y^119 + 17619*y^118 + 17700*y^117 + 15083*y^116 + 11311*y^115 + 36496*y^114 + 1300*y^113 + 13601*y^112 + 43425*y^111 + 10376*y^110 + 11551*y^109 + 13684*y^108 + 14955*y^107 + 6661*y^106 + 12674*y^105 + 21534*y^104 + 32132*y^103 + 34135*y^102 + 43684*y^101 + 837*y^100 + 29311*y^99 + 4849*y^98 + 26632*y^97 + 26662*y^96 + 10159*y^95 + 32657*y^94 + 12149*y^93 + 17858*y^92 + 35805*y^91 + 19391*y^90 + 30884*y^89 + 42039*y^88 + 17292*y^87 + 4694*y^86 + 1497*y^85 + 1744*y^84 + 31071*y^83 + 26246*y^82 + 24402*y^81 + 22068*y^80 + 39263*y^79 + 23703*y^78 + 21484*y^77 + 12241*y^76 + 28821*y^75 + 32886*y^74 + 43075*y^73 + 35741*y^72 + 19936*y^71 + 37219*y^70 + 33411*y^69 + 8301*y^68 + 12949*y^67 + 28611*y^66 + 42654*y^65 + 6910*y^64 + 18523*y^63 + 31144*y^62 + 21398*y^61 + 36298*y^60 + 27158*y^59 + 918*y^58 + 38601*y^57 + 4269*y^56 + 5699*y^55 + 36444*y^54 + 34791*y^53 + 37978*y^52 + 32481*y^51 + 8039*y^50 + 11012*y^49 + 11454*y^48 + 30450*y^47 + 1381*y^46 + 32403*y^45 + 8202*y^44 + 8404*y^43 + 37648*y^42 + 43696*y^41 + 34237*y^40 + 36490*y^39 + 41423*y^38 + 35792*y^37 + 36950*y^36 + 31086*y^35 + 38970*y^34 + 12439*y^33 + 7963*y^32 + 16150*y^31 + 11382*y^30 + 3038*y^29 + 20157*y^28 + 23531*y^27 + 32866*y^26 + 5428*y^25 + 21132*y^24 + 13443*y^23 + 28909*y^22 + 42716*y^21 + 6567*y^20 + 24744*y^19 + 8727*y^18 + 14895*y^17 + 28172*y^16 + 30903*y^15 + 26608*y^14 + 27314*y^13 + 42224*y^12 + 42551*y^11 + 37726*y^10 + 11203*y^9 + 36816*y^8 + 5537*y^7 + 20301*y^6 + 17591*y^5 + 41279*y^4 + 7999*y^3 + 33753*y^2 + 34551*y + 9659" ) import gmpy2f = 43753 e = 65537 phi = (f**65 - 1 )*(f**112 - 1 ) d = gmpy2.invert(e, phi) m = pow (c, Integer(d), n) for i in range (63 ): print(chr (m[i]), end='' )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 from fastecdsa.curve import P521 as Curvefrom fastecdsa.point import Pointfrom Crypto.Util.number import bytes_to_long, isPrimefrom os import urandomfrom random import getrandbits def gen_rsa_primes (G ): urand = bytes_to_long(urandom(521 //8 )) while True : s = getrandbits(521 ) ^ urand Q = s*G if isPrime(Q.x) and isPrime(Q.y): print("ECC Private key:" , hex (s)) print("RSA primes:" , hex (Q.x), hex (Q.y)) print("Modulo:" , hex (Q.x * Q.y)) return (Q.x, Q.y) flag = int .from_bytes(input (), byteorder="big" ) ecc_p = Curve.p a = Curve.a b = Curve.b Gx = Curve.gx Gy = Curve.gy G = Point(Gx, Gy, curve=Curve) e = 0x10001 p, q = gen_rsa_primes(G) n = p*q file_out = open ("downloads/ecc-rsa.txt" , "w" ) file_out.write("ECC Curve Prime: " + hex (ecc_p) + "\n" ) file_out.write("Curve a: " + hex (a) + "\n" ) file_out.write("Curve b: " + hex (b) + "\n" ) file_out.write("Gx: " + hex (Gx) + "\n" ) file_out.write("Gy: " + hex (Gy) + "\n" ) file_out.write("e: " + hex (e) + "\n" ) file_out.write("p * q: " + hex (n) + "\n" ) c = pow (flag, e, n) file_out.write("ciphertext: " + hex (c) + "\n" )
y 2 ≡ x 3 + a ∗ x + b m o d e c c _ p r i m e y^{2} ≡ x^{3} + a*x + b \mod ecc\_prime y 2 ≡ x 3 + a ∗ x + b m o d e c c _ p r i m e q 2 ≡ p 3 + a ∗ p + b m o d e c c _ p r i m e q^{2} ≡ p^{3} + a*p + b \mod ecc\_prime q 2 ≡ p 3 + a ∗ p + b m o d e c c _ p r i m e p 2 ∗ q 2 ≡ ( p 3 + a ∗ p + b ) ∗ p 2 m o d e c c _ p r i m e p^{2} * q^{2} ≡ (p^{3} + a*p + b) * p^{2} \mod ecc\_prime p 2 ∗ q 2 ≡ ( p 3 + a ∗ p + b ) ∗ p 2 m o d e c c _ p r i m e n 2 ≡ ( p 3 + a ∗ p + b ) ∗ p 2 m o d e c c _ p r i m e n^{2} ≡ (p^{3} + a*p + b) * p^{2} \mod ecc\_prime n 2 ≡ ( p 3 + a ∗ p + b ) ∗ p 2 m o d e c c _ p r i m e 0 ≡ ( p 3 + a ∗ p + b ) ∗ p 2 − n 2 m o d e c c _ p r i m e 0 ≡ (p^{3} + a*p + b) * p^{2} - n^{2} \mod ecc\_prime 0 ≡ ( p 3 + a ∗ p + b ) ∗ p 2 − n 2 m o d e c c _ p r i m e
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ep = 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff a = -0x3 b = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00 Gx = 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66 Gy = 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650 e = 0x10001 n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f c = 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e import gmpy2from Crypto.Util.number import *F.<x> = Zmod(ep)[] f = (x**3 + a * x + b)*(x**2 ) - n**2 pset = f.roots() for _ in pset: p = Integer(_[0 ]) q = n // p phi = (p - 1 )*(q - 1 ) d = gmpy2.invert(gmpy2.mpz(e), gmpy2.mpz(phi)) m = pow (c, d, n) print(long_to_bytes(m))