Crypto系列--RSA
Crypto系列--RSA(一)
[RSA1]P1
from Crypto.Util.number import long_to_bytes,inverse
p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720
def solve(p,q,e,c,n):
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
return m,flag
n = p*q
flag = solve(p,q,e,c,n)[1]
print(flag)[RSA1]P2
from Crypto.Util.number import long_to_bytes,inverse
n = 7382582015733895208810490097582153009797420348201515356767397357174775587237553842395468027650317457503579404097373070312978350435795210286224491315941881
e = 65537
c = 6511001389892474870028836129813814173158254564777610289284056550272120510686249909340499673868720839756059423749304765055919251717618117507007046973023557
p = 70538125404512947763739093348083497980212021962975762144416432920656660487657
q = n//p
def solve(p,q,e,c,n):
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
return m,flag
n = p*q
flag = solve(p,q,e,c,n)[1]
print(flag)[RSA1]P3
from Crypto.Util.number import long_to_bytes,inverse
n = 53690629441472827148854210396580805205350972614395425306316047967905824330731
e = 65537
c = 22130296334673852790451396673112575082637108306697684532954477845025885087040
p = 193584665240506752994134779660255197091
q = n//p
def solve(p,q,e,c,n):
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
return m,flag
n = p*q
flag = solve(p,q,e,c,n)[1]
print(flag)[RSA1]P4
from gmpy2 import iroot,mpz,gcd
from Crypto.Util.number import long_to_bytes,isPrime,inverse,bytes_to_long
from sympy import prevprime,nextprime
n = 115637000420176820831322601039129424406844427046456738651883381559357542765613732363445112111006849040385859313572091386802534464534403117787314180179562651607533039692795522388596550968316951090748054495960090527479954143448774136390568881020918710834542819900918984139672802889774720153267841255456602500057
e = 65537
c = 98161406745910866780822530171878255235776133393411573803496865047700715941955255328757920065032397556905095591171977170479344602512244671081108703687450560269408412671849929423399172588599903975793985819498354819305128607934552101433664794909855378636055525016664559476808490723554481335856183927702549281730
p_ = iroot(n,2)[0]
q = nextprime(p_)
p = n//q
def solve(p,q,e,c,n):
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
return m,flag
n = p*q
flag = solve(p,q,e,c,n)[1]
print(flag)[RSA1]P5
from gmpy2 import iroot,mpz,gcd,isqrt
from Crypto.Util.number import long_to_bytes,isPrime,inverse,bytes_to_long
# feima_attack 费马分解
n = 148841588941490812589697505975986386226158446072049530534135525236572105309550985274214825612079495930267744452266230141871521931612761645600600201983605957650711248808703757693378777706453580124982526368706977258199152469200838211055230241296139605912607613807871432800586045262879581100319519318390454452117
e = 65537
c = 69038543593219231496623016705860610154255535760819426453485115089535439537440188692852514795648297200067103841434646958466720891016026061658602312900242658759575613625726750416539176437174502082858413122020981274672260498423684555063381678387696096811975800995242962853092582362805345713900308205654744774932
p_1 = iroot(n,2)[0]
p_2 = int(p_1)
def feima_attack(n):
a = isqrt(n)
b = isqrt(n)
b2 = a*a - n
while(b*b != b2):
a = a + 1
b2 = a * a - n
b = isqrt(b2)
return a,b
a,b = feima_attack(n)
p = a + b
q = a - b
def solve(p,q,e,c,n):
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
return m,flag
flag = solve(p,q,e,c,n)[1]
print(flag)[RSA1]P6
from gmpy2 import iroot,mpz,gcd,gcdext
from Crypto.Util.number import long_to_bytes,isPrime,inverse
n1 = 143348646254804947818644803938588739009782265465565896704788366218178523508874903492905378927641178487821742289009401873633609987818871281146199303052141439575438691652893995423962176259643151111739185844059243400387734688275416379337335777994990138009973618431459431410429980866760075387393812720247541406893
n2 = 138110854441015362783564250048191029327770295545362614687087481715680856350219966472039006526758450117969049316234863489558254565946242898336924686721846675826468588471046162610143748100096038583426519355288325214365299329095841907207926280081868726568947436076663762493891291276498567791697978693639037765169
e = 65537
c1 = 54957154834913405861345262613986460384513988240935244315981524013378872930144117440787175357956479768211180412158274730449811947349624843965933828130932856052315165316154486515277625404352272475136003785605985702495858150662789554694910771308456687676791434476722168247882078861234982509648037033827107552029
c2 = 122221335585005390437769701090707585780333874638519916373585594040154234166935881089609641995190534396533473702495240511296379249872039728112248708182969185010334637138777948970821974238214641235158623707766980447918480715835847907220219601467702961667091318910582445444058108454023108157805147341928089334736
p = gcd(n1,n2)
q = n1//p
def solve(p,q,e,c,n):
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
return m,flag
n = p*q
flag = solve(p,q,e,c1,n)[1]
print(flag)[RSA1]P7
from Crypto.Util.number import long_to_bytes,isPrime,inverse
from sympy import prevprime,nextprime
p = 10666139331774428325755287635566473140804481321882464031499529816800186578792308674238646794969384836340484775213796013129603472328582005363876462361316357
q = 8419311673449738061914489023962717718536471719688567807316495262754711350004888752049108347226115000749280146228195893953964759818878155006622123533942989
r = 12875078327453384158245832541544758526474680184252540739652077682353277702054275525591573258723948221345537075374635382175740236093131628077747126356403959
e = 65537
c = 424552463648937499189041230155623101311087334789253159440707211761796081289342164253743235182597460622581134089949035117444838205449163269030784233435435681797627188717450074808905561404960693227573181548281296514743775615606388692910356320667720308219275107443303501165027740512539959960217657836317351146520079753390346207659007421416917274795119021374032194294225350901136669304225010974617136606299060486198480556729770211945777266366417547752798441211059402
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))[RSA1]P8
from Crypto.Util.number import long_to_bytes,isPrime,inverse
p = 80505091208742938705306670241621545375764148093711243653439069254008824979403
q = 67599990875658931406915486208971556223245451500927259766683936131876689508521
e = 65537
c = 7958690969908064264211283192959937430539613460471121984649054121171267262097603091410178042319139582772142226087020110084551158367679146616732446561228522673699836019156243452069036383047309578614662564794584927846163157472211089368697387945469398750955336949678910159585015004994620777231073804301249774041
n = (p**3) * q
phi = p*p*(p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))[RSA1]P9
from Crypto.Util.number import long_to_bytes,isPrime,inverse
p = 7478755670255767435237487693415479182290330775502792675052667363676831056436638619069277770540533350723045234676443621124912287506103439704868369839725279
q = 9232828888049557325429111621080998490274442347556398052322580869768941301413255711626092627273543579067597113958627672298942570149816938335701615759283713
r = 102909133680612532601801231903654039
e = 65537
c = 142893174944324070830219394465469685943669308818639857030565389839224452373848570577201378981080333784852764502832587008270072323948511579823852437852643609820245476634896477031076952735298279618952398460203032125853063235638358942643559551563899381032067185778629120272032518475352761100115057449043142848203976076694124978394099839339406197
n = p * q * r
print(c.bit_length(),n.bit_length())
n1 = p * q
def solve(p,q,e,c,n):
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
return m,flag
n = p*q
flag = solve(p,q,e,c,n1)[1]
print(flag)[RSA1]P10
from gmpy2 import iroot,mpz,gcd,gcdext
from Crypto.Util.number import long_to_bytes,inverse
p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 131074
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
mm = pow(c,d,n)
m = iroot(mm,2)
print(long_to_bytes(m[0]))Crypto系列--RSA(二)
[RSA2]P1
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
# 小指数
e = 97
c = 79418540691422578656139651796213224829563266521211325595707569487401417030874358531413674275017334363641194166574500833916574827523075402219754470871728896772312056257743844227927800121160288525434484105786180547178403828613331285574461293211150728313415280329153597549251599876668080073528625299164784405291297754331374420687599875173508778209038236713812747215157059659564867241144529476211694011692007565732793105429228730285249025627762831080251661835294067942958070742202862164086250986988784472568266652325462247009294865764533077164470382743735937483173523682749295196383707694876943634298051820105410771024861599560176707940488888601355473498847493259474613261665538825299531665650233837474894442826242097663456648233384047622152817959729025415665280499618951478005159820575701483220155180955748454167435711033379910310483689839303198822665341421591234243891877857520663120183063591818656508336831518527692847950877186870610083654117153248336928856886934232488927132245720058243202637258025864487122393335118118013444397135476780564523166548571927547341556616683070253790368891423731046742936358877118104790084195711730135202600692806999992373490439385845158780392894927697171401722699273071306493916233696254958735540772870249139252741670476667099529502282392011715616110876451102234600267482991583515122052976378641894214562203326290939184469206074418127906704847146567350085797480500249400491003993809769407575997740985283755035509654310797061339563655229926356893455738361409861102662109994984398860070584568014471082484198504331014073023689622378943694856212172718725529473812336321642429261822836311084518735006587545920946664595488768239633950124822001162595168106106356115962424210028401369438479550293237915944302351566624339603616714683958384871326105542659559877758488581425288668613061792514360263277530824203967659102107889148367539858141289229124274098921748855341045565232484417195620758495861456624842263649414501657786484816662971421962216348340311859717286253287173293151613310383128702607971580042308515018120559903265609733911340589091613087560931098833849573462572181625894166772788435459280323623477689159384354671220634694792005231505741029567734616435905915192606539962414882105254409847885996949466940350184140166614950171110955365828033747003120697209120916652982201967537088553504504252785632280900095976870510754563400828951684036526240669112248351928072177486091157562600003336544767896806392523395037345770580482363058065676920013089896399387769312374871419827762872050800055872960573607645266626972865053489632548224840580503746879607167797904430560935476705014800973841917939689270919224595772574781478285359220463175042728750523639669204218676238297875644055563803457896409252533724486937378974745777400567080239687055154021761534918106133195512030935957251049812753269173090858930245212145938555697547499155977225759702066548720079477737104010668116693232798415289735481194922014811945312893853446826780868861295203942063380964100360870361328125
m = iroot(c,97)[0]
print(long_to_bytes(m))[RSA2]P2
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
# 小指数
n = 111573371787314339229652810703380127177507745009618224416171957526984270337589283887959174610818933914845556276472159360153787395638087723501889651641965684241070152541291185349571453536221312112508437223801640552330390095266644485311958102687735113533739324296417077804219395793942670324182191309872918900717
e = 3
c = 90782646242308381145716338972639920044710403094882163620436540965475107006005657722222634294458956650085252212452241377251397323707019480880284004845674260662647720809672266571040936376737882878688872281858048646517100139303896804340224961592424635124272549514473232731744884837572128596217771005209683966262
k = 1
m = 1
for i in range(0,1000):
if(iroot(c+i*n,3)[1]):
k = i
m = iroot(c+i*n,3)[0]
break
print(k)
print(m)
flag = long_to_bytes(m)
print(flag)[RSA2]P3
from gmpy2 import iroot,mpz,gcd,gcdext
from Crypto.Util.number import long_to_bytes,inverse
# rabin算法
p = 67711062621608175960173275013534737889372437946924512522469843485353704013203
q = 91200252033239924238625443698357031288749612243099728355449192607988117291739
e = 2
c = 5251890478898826530186837207902117236305266861227697352434308106457554098811792713226801824100629792962861125855696719512180887415808454466978721678349614
n = p*q
mp = pow(c,(p+1)//4,p)
mq = pow(c,(q+1)//4,q)
g,x,y = gcdext(p,q)
r = (x*p*mq + y*q*mp)% n
r_ = n-r
s = (x*p*mq - y*q*mp)% n
s_ = n-s
print(long_to_bytes(r))
print(long_to_bytes(r_))
print(long_to_bytes(s))
print(long_to_bytes(s_))[RSA2]P4
from Crypto.Util.number import long_to_bytes
from xenny.ctf.crypto.modern.asymmetric.rsa import wiener
# e很大 wiener攻击
n = 6969872410035233098344189258766624225446081814953480897731644163180991292913719910322241873463164232700368119465476508174863062276659958418657253738005689
e = 3331016607237504021038095412236348385663413736904453330557803644384818257225138777641344877202234881627514102078530507171735156112302207979925588113589669
c = 1754994938947260364311041300467524420957926989584983693004487724099773647229373820465164193428679197813476633649362998772470084452129370353136199193923837
d,p,q = wiener.attack(n,e)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)[RSA2]P5
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
from pwn import *
import re
# 和pwn交互 获得64组数据 crt求解
host = 'node4.anna.nssctf.cn'
port = 28882
conn = remote(host, port)
# conn.interactive()
def interact_with_server(conn):
conn.recvuntil(b"input> ")
conn.sendline(b"1")
data1 = conn.recvline().decode()
data2 = conn.recvline().decode()
n = int(re.findall(r'n: (\d+)', data1)[0])
c = int(re.findall(r'c: (\d+)', data2)[0])
return n, c
n_value = []
c_value = []
for i in range(64):
n, c = interact_with_server(conn)
n_value.append(n)
c_value.append(c)
e = 127
m_127 = crt(n_value,c_value)[0]
m = iroot(m_127,e)[0]
flag = long_to_bytes(m)
print(flag)[RSA2]P6
from gmpy2 import gcd,powmod
from Crypto.Util.number import long_to_bytes,inverse
# p-1 光滑
N = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618
a = 2
n = 2
while True:
a = powmod(a, n, N)
res = gcd(a-1, N)
if res != 1 and res != N:
q = N // res
print("p =",res)
print("q =",q)
break
n += 1
p = 27129468931474722768194257677072900116691863938437565023930764029944386941648043
q = 1981739118154369511414154577570801106446227313943655568841825492553695755235903
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,N)
flag = long_to_bytes(m)
print(flag)[RSA2]P7
环境: ubuntu-22.04
SageMath version 9.5
from sage.all_cmdline import *
from xenny.ctf.crypto.modern.asymmetric.rsa import williams_pp1
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert,powmod
# p+1光滑
n = 63398538193562720708999492397588489035970399414238113344990243900620729661046648078623873637152448697806039260616826648343172207246183989202073562200879290937
e = 65537
c = 26971181342240802276810747395669930355754928952080329914687241779532014305320191048439959934699795162709365987652696472998140484810728817991804469778237933925
p,q = williams_pp1.attack(n,55)
phi = (p-1)*(q-1)
d = invert(e,phi)
m = powmod(c,d,n)
flag = long_to_bytes(m)
print(flag)[RSA2]P8
from gmpy2 import gcdext
from Crypto.Util.number import long_to_bytes
#共模攻击
n = 120294155186626082670474649118722298040433501930335450479777638508444129059776534554344361441717048531505985491664356283524886091709370969857047470362547600390987665105196367975719516115980157839088766927450099353377496192206005171597109864609567336679138620134544004766539483664270351472198486955623315909571
e1 = 38317
e2 = 63409
c1 = 42703138696187395030337205860503270214353151588149506110731264952595193757235229215067638858431493587093612397165407221394174690263691095324298012134779703041752810028935711214038835584823385108771901216441784673199846041109074467177891680923593206326788523158180637665813642688824593788192044139055552031622
c2 = 50460092786111470408945316270086812807230253234809303694007902628924057713984397041141665125615735752600114964852157684904429928771531639899496987905067366415806771003121954852465731110629459725994454904159277228514337278105207721011579794604761255522391446534458815389983562890631994726687526070228315925638
g,x,y = gcdext(e1,e2)
m = pow(c1,x,n)*pow(c2,y,n)%n
flag = long_to_bytes(m)
print(flag)[RSA2]P9
from Crypto.Util.number import long_to_bytes,inverse
#dp dq 泄露
p = 13070310882303377463944295715444821218324151935347454554272870042925400761984585838979931730897626589859098834802923539617244712852188293321626061072925723
q = 10411551818233737389114520103233235272671271111546186997024935593000298916988792710521511848414549553426943998093077337023514210631662189798921671306236009
c = 62492280219693914005334023569480350249964827909276875032578276064973191654731196407886841145547165693859745313398152742796887457192397932684370631253099255490064673499746314452067588181106154875239985334051909867580794242253066085627399488604907196244465911471895118443199543361883148941963668551684228132814
dp = 11568639544706374912496682299967972464196129347160700749666263275305083977187758414725188926013198988871173614336707804756059951725809300386252339177953017
dq = 3455040841431633020487528316853620383411361966784138992524801280785753201070735373348570840039176552952269927122259706586236960440300255065994052962742469
n = p*q
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
m = ( m1 + ( (m2 - m1) * inverse(p,q) % q )*p ) %n
flag = long_to_bytes(m)
print(flag)[RSA2]P10
环境: ubuntu-22.04
SageMath version 9.5
from xenny.ctf.crypto.modern.asymmetric.rsa import dpleak
from Crypto.Util.number import long_to_bytes
# dp泄露
e = 65537
n = 79201858340517902370077926747686673001645933420450220163567700296597652438275339093680329918615445030212417351430952656177171126427547284822789947152085534939195866096891005587613262293569611913019639653984932469691636338705418303482885987114085769045348074530172292982433373154900841135911548332400167290083
c = 70109332985937768446301118795636999352761371683181615470371772202170324747707233792154935611826981798791499937601162039878070094663516868746240133223110650205575807753345252087103328657073552992431511929172241702073381723302143955977662087561904058172777520360991685289300855900793806183473523998422682944404
dp = 3098334089252415941833934532457314870210700261428241562420857845879512952043729097866485406309479489101668423603305497982177150304625615059119312238777275
m = dpleak.attack(dp,c,e=e,n=n)
print(long_to_bytes(m))[RSA2]P11
环境: ubuntu-22.04
SageMath version 9.5
from sage.all_cmdline import *
from Crypto.Util.number import long_to_bytes
from xenny.ctf.crypto.modern.asymmetric.rsa import dpleak
# 大指数dp泄露
n = 108280026722298796068968170303156759745471686664814404724171434502249429011870583595808692893118419248225924869164875379709992190884930717654004006466664403479467573176438601715156464950045121937338569942817256182277141174728470067308962244296992229214749863655518517510026063088263849891990324547823192559069
e = 305691242207901867366357529364270390903
c = 26537258289122728220745496185201994733321402056894636636642710319261241111675937946139938310952968353253866895253865273981912174303818938005932883052177988834834575591342856235464380238486868448329727891268391728758132913642966389278296932186703733187105516710825918064228397602264185334108934765627411913661
dp = 2656631506624565349527023729530989647164022271235521672257622068579788839123502046687139927161669209201953909023994372208117081512139181611949631467292513
m = dpleak.attack(dp,c,e=e,n=n)
flag = long_to_bytes( m )
print(flag)[RSA2]P12
d泄露求p
首先Xenny师傅介绍一个定理
\(r \equiv s\pmod{\phi(n)}\) \(\Leftrightarrow\) \(a^{r} \equiv a^{s} \pmod{n}\)\(e*d \equiv 1\pmod{\phi(n)}\) \(\Rightarrow\) \(a^{e*d} \equiv a \pmod{n}\)
我们令\(e*d -1 = 2^{s}*t\)
使得 \(t\) 是一个奇数，这样我们遍历 \([\ 1,\ s]\) ，假设能够找到满足下列关系式的式子
\(a^{2 ^ {i} * t}\equiv 1 \pmod{n}\) 且 \(a^{2 ^ {i - 1 } * t}\not \equiv \pm{1} \pmod{n}\)
就会有 \(gcd(a^{2 ^ {i-1} * t} - 1,n) = p\)
- 证明如下
\(a^{2 ^ {i } * t} \equiv 1 \pmod{n}\)
\(\Rightarrow\) \(2 ^ {i }* t\equiv 0 \pmod{\phi(n)}\)
\(\Rightarrow\) \(2 ^ {i - 1}* t = 2^{-1} * k *(p-1)*(q-1) = k*(p-1)*\frac{(q-1)}{2}\)
\(\Rightarrow\) \(2 ^ {i - 1 }* t\equiv 0 \ (mod \ p-1 )\)
\(\Rightarrow\) \(a^{2 ^ {i-1 }* t}\equiv 1 \pmod{p}\)
\(\Rightarrow\) \(a^{2 ^ {i-1 } * t} - 1\ \equiv 0 \pmod{p}\)
\(\Rightarrow\) \(a^{2 ^ {i-1 } * t} - 1\ = k*p\)
那么有 \(gcd(k*p,n) = p\)
也就是 \(gcd(a^{2 ^ {i-1} * t} - 1,n) = p\)
from gmpy2 import *
from hashlib import md5
#d泄露 分解n
n = 113917408220469425995764932761465306974540330325378601642830241920567032775895088098706711486764203845425248022960733155994427766750033219106642310531864450654102562104771892268897793145789045570107312401570269581223945259704851104645493075550316424129401227653740942495625720165869565257394427181127734628103
d = 15762135247924329080208071933121250646888501386858311483546464344350547831176536290630826247188272280853810047335214127264865205744683174860903496832368687060941437002920094364116706593296591581117381565805322046922482804679245558495134876677733584718947309975077159564300049936769192724856722338627154192353
e = 65537
t = e * d - 1
s = 0
while(t % 2 == 0):
t = t // 2
s += 1
# 此时 e * d - 1 = ( 2 ** s ) * t
p = 2
q = 2
for i in range(1,s):
c1 = powmod(2,powmod(2,i,n) * t , n )
c2 = powmod(2,powmod(2,(i-1),n) * t, n )
if(c2 != 1 and c2 != n-1 and c1 == 1 ):
kp = c2 - 1
p = gcd(kp,n)
break
q = n // p
print(p<q) # True
flag = md5(str(p).encode()).hexdigest()
print("NSSCTF{"+flag+"}")
