[羊城杯2020]Invitations
RSA Hastad Attack with non-linear padding and different public keys
注意点：
虽然题目给了14组数据，但是e=3的只有4组，只用那4组即可，因为Hastad攻击的条件是要选择相同值的e
bit_length为431，长度为54位的flag转成long之后的bit_length是430啊，不知为啥
epsilon设置问题，默认是1/8，这里要用1/20，不知怎么算的
Small_roots的解并不唯一，第二个正好是，所以不能return roots[0]
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
import gmpy2
import random
def pad(s,i):
return i * pow(3,s.bit_length()) + s**2
def gen_N():
return getPrime(512) * getPrime(512)
assert len(flag) == 54
invite = bytes_to_long(flag)
e_list = [random.choice([3,5,7]) for i in range(14)]
N_list = [gen_N() for i in range(14)]
with open('./invitations','w') as f:
for i in range(14):
invis = pow(pad(invite,i+1),e_list[i],N_list[i])
f.write('Invitation%d: %d \n'%(i+1,invis))
f.write('Wait a minute! \n')
for i in range(14):
f.write('[e%d,N%d]: [%d,%d]\n'%(i+1,i+1,e_list[i],N_list[i]))from Crypto.Util.number import *
def linearPaddingHastads(cArray, nArray, aArray, bArray, eArray, eps):
if(len(cArray) == len(nArray) == len(aArray) == len(bArray) == len(eArray)):
for i in range(4):
cArray[i] = Integer(cArray[i])
nArray[i] = Integer(nArray[i])
aArray[i] = Integer(aArray[i])
bArray[i] = Integer(bArray[i])
eArray[i] = Integer(eArray[i])
TArray = [-1]*4
for i in range(4):
arrayToCRT = [0]*4
arrayToCRT[i] = 1
TArray[i] = crt(arrayToCRT, nArray)
P.<x> = PolynomialRing(Zmod(prod(nArray)))
gArray = [-1]*4
for i in range(4):
gArray[i] = TArray[i]*(pow(aArray[i]*x**2 + bArray[i], eArray[i]) - cArray[i])
g = sum(gArray)
g = g.monic()
# Use Sage's inbuilt coppersmith method
roots = g.small_roots(epsilon=eps)
if(len(roots) == 0):
print("No Solutions found")
return -1
return roots
else:
print("CiphertextArray, ModulusArray, and the linear padding arrays need to be of the same length," +
"and the same size as the public exponent")
c = [129274519334082165644106292383763271862424981496822335330342328217347928093592453953990448827969549377883054831490973006383371688359344675312001881631556371220779971357039899721241880304156884612458373310254854821837978876725801047977081900824202659636258168216028784656056334358157381820784576207338479493823
,8140023566779187828652447593867705813386781164538611122714708931585587727699213769519135028841126072130625547328311301696554048174772606261707345115571968105138543476580875347239912760797035694220505996377127309341770427102697008350472060971360460756799310951343070384766137332401117333917901167639276168214
,25434511525127530194830986592289179576070740435049947678930286998924519588985583799757299734846614343604661534391991096353170465467791358514448923161460366596251448937540153262731348684727026598527904328268639060306102090278287818149679940661579357649191023269947102746200467430583428889484549034314463114080
,9435583236354598287661880148272717764447540972316605192855157484524753847806158586224733743434644389385148450722945845355791145016665856388503878165725148745517696840251674049929524448078129458846254866804153080766917319923905682824180976106679633180818527967145571143203594244851742143986040226240019541346
]
e = [3]*4
n = [146694460234280339612721415368435987068740712812770728817136582256341063038147863645902264969297892447333024201649306207442798919845916187823646745721109151386096190207317810424580842120750075213595282979568495342617919336417068886973047979116994072272482630372638964064972815256237040541007947708358680368391
,65031485534704406281490718325237831433086480239135617407356760819741796565231283220528137697949585150709734732370203390254643835828984376427852793969716489016520923272675090536677771074867975287284694860155903327351119710765174437247599498342292671117884858621418276613385329637307269711179183430246951756029
,126172075578367446151297289668746433680600889845504078949758568698284471307000358407453139846282095477016675769468273204536898117467559575203458221600341760844973676129445394999861380625435418853474246813202182316736885441120197888145039130477114127079444939102267586634051045795627433724810346460217871661901
,75691424835079457343374072990750986689075078863640186724151061449621926239051140991748483370587430224317778303489124525034113533087612981452189061743589227565099659070008017454957304620495920813121234552401715857719372861565651204968408267740732475458128601061676264465241188491988485848198323410127587280471
]
a = [1]*4
b = [i*3**431 for i in [3,8,10,11]]
m = linearPaddingHastads(c, n, a, b, e, 1/20)
print(len(m))
print(m)
for i in m:
print(long_to_bytes(i))
# b'GWHT{e959e3f8e7242954b43e1b91de9886e1}Welc0metomyp4rty'[红明谷]RSA attack
from gmpy2 import *
from Crypto.Util.number import *
import sympy
import random
from secret import flag
p1 = getPrime(1024)
print(p1)
#p1=172071201093945294154292240631809733545154559633386758234063824053438835958515543354911249971174172649606257936857627547311760174511316984409767738981247877005802155796623587461774104951797122995266217334158736848307655543970322950339988489801672160058805422153816950022590644650247595501280192205506649936031
p2 = p1 - random(999,99999)
print(p2)
#p2=172071201093945294154292240631809733545154559633386758234063824053438835958515543354911249971174172649606257936857627547311760174511316984409767738981247877005802155796623587461774104951797122995266217334158736848307655543970322950339988489801672160058805422153816950022590644650247595501280192205506649902034
p_1=1
for i in range(1,p1+1):
p_1*=i
p3 = sympy.nextPrime(p_1 % p2 )
p4 = p3 >> 50 << 50
p = p4
while(isPrime(P)!=1):
P = p + random.randint(0,2**50)
Q = getPrime(1024)
e = 1+1+1
N = P * Q
print(N)
#N=28592245028568852124815768977111125874262599260058745599820769758676575163359612268623240652811172009403854869932602124987089815595007954065785558682294503755479266935877152343298248656222514238984548734114192436817346633473367019138600818158715715935132231386478333980631609437639665255977026081124468935510279104246449817606049991764744352123119281766258347177186790624246492739368005511017524914036614317783472537220720739454744527197507751921840839876863945184171493740832516867733853656800209669179467244407710022070593053034488226101034106881990117738617496520445046561073310892360430531295027470929927226907793
flag=bytes_to_long(flag)
c = pow(flag,e,N)
print(c)
#c=15839981826831548396886036749682663273035548220969819480071392201237477433920362840542848967952612687163860026284987497137578272157113399130705412843449686711908583139117413
求阶乘模，相差不多，用威尔逊定理和invert函数，将p2一步步推成p1，最后爆破一下p4加的随机数
from gmpy2 import *
from Crypto.Util.number import *
from libnum import *
p1=172071201093945294154292240631809733545154559633386758234063824053438835958515543354911249971174172649606257936857627547311760174511316984409767738981247877005802155796623587461774104951797122995266217334158736848307655543970322950339988489801672160058805422153816950022590644650247595501280192205506649936031
p2=172071201093945294154292240631809733545154559633386758234063824053438835958515543354911249971174172649606257936857627547311760174511316984409767738981247877005802155796623587461774104951797122995266217334158736848307655543970322950339988489801672160058805422153816950022590644650247595501280192205506649902034
n = 28592245028568852124815768977111125874262599260058745599820769758676575163359612268623240652811172009403854869932602124987089815595007954065785558682294503755479266935877152343298248656222514238984548734114192436817346633473367019138600818158715715935132231386478333980631609437639665255977026081124468935510279104246449817606049991764744352123119281766258347177186790624246492739368005511017524914036614317783472537220720739454744527197507751921840839876863945184171493740832516867733853656800209669179467244407710022070593053034488226101034106881990117738617496520445046561073310892360430531295027470929927226907793
c=15839981826831548396886036749682663273035548220969819480071392201237477433920362840542848967952612687163860026284987497137578272157113399130705412843449686711908583139117413
def wilson(A,B):
t=A-B-1
res=-1
k=A-1
for i in range(t):
res=(res*invert(k,A))%A
k=k-1
if(res<0):
return res+A
else:
return res
p3 = next_prime(wilson(p2, p1))
p4 = p3 >> 50 << 50
e = 3
for i in range(2**20):
p = p4 + i
if isPrime(p) and gcd(e, p-1) == 1:
d = invert(e, p-1)
m = n2s(pow(c,d,p))
if m[:5] == 'flag{':
print m
break
# flag{w0_x1hu1n_y0u_b5st}[红明谷]ezCRT
from Crypto.Util.number import *
import gmpy2
from random import shuffle
flag = b"flag is here"
def shuffle_flag(s):
str_list = list(s)
shuffle(str_list)
return ''.join(str_list)
nl = []
el = []
count = 0
while count != 5:
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.next_prime(bytes_to_long(flag))
e = gmpy2.invert(d, phi)
nl.append(n)
el.append(int(e))
count += 1
print(nl)
print(el)
cl = []
flag = shuffle_flag(flag.decode()).encode()
for i in range(len(nl)):
cl.append(pow(bytes_to_long(flag), el[i], nl[i]))
print(cl)
d相同，用Common Private Exponent共私钥指数攻击
构造格子然后用LLL算法规约得到d
# sage
from gmpy2 import *
from Crypto.Util.number import *
e0=69312028009355287369151190914681978515224902099126626288106202481561083869512381976466800912049172557479956400189281179789850182367192324370292880508005951892909864237831856642160554901550928757105750738313195248541515727624216048436593804176317465366380022764459799506858495981817822670957526705611211712923
n0=92568419674731290088321621356482160506897805615722568594108449347104924357404183476911642777855820991398881156764068184840768873749718093598712551142529474514837161712525386555067489900887826033760157015587905876891826276883359425048106383489316555600680137377034136599761900203863336332834524981581608546277
c0=706565317398633346290694952311166623770389747503953970254889622211015097472765489676349936599997109100148837713409666075736711752497174928509516666210124850782396573268200919345005742905131769799719677758163730270857245509037860252700476102090438501579886321486095767737006847692632649652528793934802014895
e1=75652848678989239962391202584125835503829570694373189157636155436633908234362973839251550542975725789188895010096917574118924190081886365041870173203566890015476761857546914959928731140619341634983144909962106759048918025248827973161384045263311189477657141886093632791593341193393085433749877270828641736687
n1=156396473818563541024482014372866929605198443382524196879362284224099117401220679011156723462510565131555949471059964179767945960498473012008220045105490122503438703770112687917922899337041421537937431868908340506324082719417747902320117904166584374628828367801012533926776313544525573302674702867896838756349
c1=39976293505792731417500342473259466413746324373570160856607039564687056797068114044891309890160001547746290678089875953230720229396293686037539133378586045964793387433679304899158546834837314101138069400994334720071006048815998660691472991971598192116289517127819703723844842002711298154106615035755646791235
e2=33787880341418355427411601538315129862488529656310145182009801227014512555036822623215545927750632031483856865027938518144081751233475248361490189179988637342429805607352670543555743822390555949569061340741015073482051059972283793490798701339277926430357560613555427570475360496737455291914090967005368044847
n2=158394833243620345170313957479796081390446308753163267294427471181012679879060921676287361174926310080500003540773261012005682050743188110335872216992843352902160171999286576526304619756655278142788064189969927027027650043645613441449926633380809295720977302961310978360575684689811662689798196832145977450067
c2=82622936948791971063481195310587447614375265630407688161651173440160941964839173273115526802240672776681580169092371677673709037579318090622040018030730165371997331146171751228791524747622285256591779419274845659567001522182995468819720594650389854677582186770321424062935881407083956991646633760500152137305
e3=45894271603047945281790624112313938740541711331584775481261776728213544262108835859642003140814571796838418889270625806159755478669858113687476417240730385707171289922064965084283027730393146219788228689778873266618663473231744646293406030907691363263939114550226424730102211751706087680590823466426973879111
n3=160088237013152996062303719345275590040820298863729670660621544625451638541931139026114480452748397901155923890465415946150076272684251867169893163248736673419035618274961179288085209456220719404244194802327491684233804878013160262798831738441790443743813368173495029170393018727204042599457829167334217403039
c3=47924672523033740219454774309397006543851002473271747603676349322670782245519637286314088457132590816165876451615235937683074852920250584155682791595116359054889940842281324709426616771765312825842634237678243213350551342690870568516232078792788925700389762945955053433276153136302757700081859531596237286407
e4=39462780066564051085365889083337472288277223628014907704844994419242541623368920096395581667207909872944692627394665038729398405841875334128211337544205143876652949004817962123951132753801707134333132359039376283331685997619531570270269964807335633423631078057345827010794671894948828680193958561375351954627
n4=176125361422384852665447804150030174008849487020728296169340093618559367127086381778331613043595010796295772394708222184703701230685609172767761426620379001062695169120599393984950488304290958534830276649464003949555105491117656796777657620812669612752464591728873199832200616338112460100967288829163217253937
c4=157462720644970256050843434459828247139256140406409429896418317109064365936294939244159292550184482469972819258184119865598346921909220060266145241164734603316978286567811044606538176157224828857158099074286931716459626013079677895357212211176535500327064375073662684801175545519382470886239209020257096407424
M=iroot(int(n4),int(2))[0]
a=[0]*6
a[0]=[M,e0,e1,e2,e3,e4]
a[1]=[0,-n0,0,0,0,0]
a[2]=[0,0,-n1,0,0,0]
a[3]=[0,0,0,-n2,0,0]
a[4]=[0,0,0,0,-n3,0]
a[5]=[0,0,0,0,0,-n4]
Mat = matrix(ZZ,a)
Mat_LLL=Mat.LLL()
d = abs(Mat_LLL[0][0])//M
d = int(d)
print(long_to_bytes(d))
# b'flag{9b73a84b-5e32-433a-bc8f-6f8a6d2793db}paddip\x0f'[虎符2021]cubic
#!/usr/bin/env python3
from math import gcd
from functools import reduce
from fractions import Fraction as Frac
N = 6
def read_num(prompt):
try:
num = int(input(prompt))
except:
return 0
return num if num > 0 else 0
print(f"Please give me {N} pairs of positive integers (x,y,z) "
f"satisfying the equation `x/(y+z) + y/(z+x) + z/(x+y) = {N}`\n")
anss = []
mark = 0
for i in range(N):
x = read_num("[>] x: ")
y = read_num("[>] y: ")
z = read_num("[>] z: ")
if x * y * z == 0: # positive integer
mark = 1
print("This is not what i want!\n")
break
if reduce(gcd, [x, y, z]) != 1: # (kx, ky, kz)
mark = 1
print("This is not what i want!\n")
break
if Frac(x, y+z) + Frac(y, z+x) + Frac(z, x+y) != N:
mark = 1
print("This is not what i want!\n")
break
ans = tuple(sorted([x, y, z])) # (y, x, z)
if ans in anss:
mark = 1
print("This is not what i want!\n")
break
else:
print("You are right!\n")
anss.append(ans)
if mark == 0:
flag = open('/flag', 'r').read()
print("flag is: " + flag + "\n")
else:
print("Something wrong!\n")
$$
\frac{x}{y+z}+\frac{y}{x+z}+\frac{z}{x+y}=6
$$
$$
a^{3}+b^{3}+c^{3}-5(a^{2}b+ab^{2}+a^{2}c+ac^{2}+b^{2}c+bc^{2})-9abc=0
$$
$$
x=\frac{-36(a+b+2c)}{8a+8b-c}
$$
$$
y=\frac{612(a-b)}{8a+8b-c}
$$
$$
(a,b,c)=(1,-1,0)
$$
$$
y^{2}=x^{3}+213x^{2}+288x
$$
$$
\frac{a}{a+b+c}=\frac{8(N+3)-x+y}{2(4-x)(N+3)}
$$
$$
\frac{b}{a+b+c}=\frac{8(N+3)-x-y}{2(4-x)(N+3)}
$$
$$
\frac{c}{a+b+c}=\frac{-4(N+3)-(N+2)x}{(4-x)(N+3)}
$$
#Sage
ee = EllipticCurve([0, 4*6^2+12*6-3, 0, 32*(6+3), 0])
#print(ee)
#print(ee.gens())
#P = ee(-200,680)
#print(P)
def orig(P,N):
x = P[0]
y = P[1]
a = (8*(N+3)-x+y)/(2*(N+3)*(4-x))
b = (8*(N+3)-x-y)/(2*(N+3)*(4-x))
c = (-4*(N+3)-(N+2)*x)/((N+3)*(4-x))
da = denominator(a)
db = denominator(b)
dc = denominator(c)
l = lcm(da,lcm(db,dc))
return [a*l, b*l, c*l]
ans = []
for k in range(200):
u = orig(k*P, 6)
(a,b,c) = (u[0],u[1],u[2])
if a>0 and b>0 and c>0:
print('k:', k)
#print(a)
#print(b)
#print(c)
print('he:', a/(b+c)+b/(a+c)+c/(a+b))
#print()
ans.append((a,b,c))
print('len:', len(ans))s[VNCTF2021]factor
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
def get_public_key(d):
while 1:
p, q = getPrime(512), getPrime(512)
N, phi, not_phi = p * q, (p - 1) * (q - 1), (p + 1) * (q + 1)
try:
e = inverse(d, not_phi)
assert gcd(e, phi) == 1
break
except:
pass
return (N, e)
def encrypt(pubkey, m):
N, e = pubkey
c = pow(m, e, N)
return c
m = bytes_to_long(flag)
d = getPrime(300)
pubkeys = [get_public_key(d), get_public_key(d)]
cs = encrypt(pubkeys[0], m), encrypt(pubkeys[1], m)
print(pubkeys)
print(cs)
'''
[(115483338707853323510117244601663937653032657454816581880428779391136584508645415322441921678179684904267659942318581245589538093236558206867210468172871004098796706517288570963560499418427771831765342801956281881820593084352360716457591198748797415842971188690055630073433785996545367137242661591939632740177, 57942961120648999071495995119939754708884253716257622598699627649519120883383654560602196191747110519111036450217116739928381611061803307053632035548944075112790103258912149703053932492832060534126356062378027983000713091223894604748395826345780826674822582205573649323340945351657354960324397873669889767611), (53622548101803784449246949981043962044702821559359430270342163843702543781580388956841660273746825211912789196955019345268896290156568895362182295889379787233440464948232717888315385094207004043907898658611926470834448875571292174245716821120409044389816082878077188546182422805778560826667364235348059795229, 37629174280947918845570975617525141920002123382327456934545962737176558640617579710289304146119507880547361939594011152968663070025066085778798378563965349218834887746411017240322083056673687330052590220772859205859051875687741541958997904176801239206348298021023694604932588913541173039972303193792987583003)]
(51861394323132582263685584977796608641129485967610029542263453128833142621927008505594685713111162217651119546991411861320042282788909858323941435593508384080858965324662410947546608051702238057613339996124961723578887443100478753831786550701578678090466528863014222331341645240511640398819027209200809466160, 53200507591144017820710284362261363695745231005527161900426580605551005076410241969689161754211964469126847594337121140420040532547631617290907291418063708630323838133357597795892690304405706577096504918510233628396424543417886828387510407109281423448827267022542075484645277275676556239547911837897827866040)
'''$$
e_{0}d = k_{0}(n_{0}+p_{0}+q_{0}+1)+1
$$
$$
e_{1}d=k_{1}(n_{1}+p_{0}+q_{0}+1)+1
$$
设$ M=\sqrt{n_{0}}, s=p_{0}+q_{0} $
构造格子如下：
$$
X=\begin{pmatrix}d&k_{0}&k_{1}\end{pmatrix}
$$
$$
A=\begin{pmatrix}M&e_{0}&e_{1}\0&-n_{0}&0\0&0&-n_{1}\end{pmatrix}
$$
$$
XA=B
$$
$$
B=\begin{pmatrix}dM&e_{0}d-k_{0}n_{0}&e_{1}d-k_{1}n_{1}\end{pmatrix}
$$
对A用LLL算法进行格基规约得到B
# sage
from gmpy2 import *
from Crypto.Util.number import *
e0 = 57942961120648999071495995119939754708884253716257622598699627649519120883383654560602196191747110519111036450217116739928381611061803307053632035548944075112790103258912149703053932492832060534126356062378027983000713091223894604748395826345780826674822582205573649323340945351657354960324397873669889767611
n0 = 115483338707853323510117244601663937653032657454816581880428779391136584508645415322441921678179684904267659942318581245589538093236558206867210468172871004098796706517288570963560499418427771831765342801956281881820593084352360716457591198748797415842971188690055630073433785996545367137242661591939632740177
c0 = 51861394323132582263685584977796608641129485967610029542263453128833142621927008505594685713111162217651119546991411861320042282788909858323941435593508384080858965324662410947546608051702238057613339996124961723578887443100478753831786550701578678090466528863014222331341645240511640398819027209200809466160
e1 = 37629174280947918845570975617525141920002123382327456934545962737176558640617579710289304146119507880547361939594011152968663070025066085778798378563965349218834887746411017240322083056673687330052590220772859205859051875687741541958997904176801239206348298021023694604932588913541173039972303193792987583003
n1 = 53622548101803784449246949981043962044702821559359430270342163843702543781580388956841660273746825211912789196955019345268896290156568895362182295889379787233440464948232717888315385094207004043907898658611926470834448875571292174245716821120409044389816082878077188546182422805778560826667364235348059795229
c1 = 53200507591144017820710284362261363695745231005527161900426580605551005076410241969689161754211964469126847594337121140420040532547631617290907291418063708630323838133357597795892690304405706577096504918510233628396424543417886828387510407109281423448827267022542075484645277275676556239547911837897827866040
M = iroot(int(n1),int(2))[0]
a = [0]*3
a[0] = [M,e0,e1]
a[1] = [0,-n0,0]
a[2] = [0,0,-n1]
Mat = matrix(ZZ,a)
res = Mat.LLL()[0]
d = int(abs(res[0])//M)
k = (e0 * d - res[1]) // n0
s = (res[1] - 1) // k - 1
# var("p,q")
# eq1=p*q==n1
# eq2=p+q==s
# solve([eq1,eq2],p,q)
p = 12142923211780390949278028555254354690367508997633592218490684570880648120995591724323182740048952281742212656089623106601110432188891734994648474592945523
q = 9510340853989572312310219508407369314311536350226735639404605504254271288587514209474334748428705386324794069855863782259924949801740767334888452847705899
phi = (p-1)*(q-1)
d0 = invert(e0, phi)
print(long_to_bytes(pow(c0, d0, n0)))
# b'vnctf{7d47956b-bc55-4897-a550-cda0b221ce67}'[VNCTF2021]whitegive
m = e
p = getPrime(512)
q = getPrime(512)
n = p * p * q
e = 0x10001
d = inverse(e,lcm(p,lcm(p-1,q-1)))
c = pow(m,e,n)
hint = pow(d,e,n)
print(n)
print(c)
print(hint)
$$
ed\equiv1\bmod(lcm(p,lcm(p-1,q-1)))
$$
$$
(ed)^{e}\equiv1\bmod(lcm(p,lcm(p-1,q-1)))
$$
$$
(ed)^{e}=kp(p-1)(q-1)/gcd(p-1, q-1)+1
$$
$$
gcd(p-1, q-1)((ed)^{e}-1)=kp(p-1)(q-1)
$$
$$
p=gcd(e^{e}d^{e}-1,n)
$$
from gmpy2 import *
n=
c=
hint=
e=
p=gcd(hint*(e**e)-1,n)
q=n//p//p
phi=p*(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(m)[V&N2020公开赛]Fast
from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
N = p * q
g, r1, r2 = [getRandomRange(1, N) for _ in range(3)]
g1 = pow(g, r1 * (p-1), N)
g2 = pow(g, r2 * (q-1), N)
def encrypt(m):
s1, s2 = [getRandomRange(1, N) for _ in range(2)]
c1 = (m * pow(g1, s1, N)) % N
c2 = (m * pow(g2, s2, N)) % N
return (c1, c2)
def decrypt(c1, c2):
xp = c1 % p
xq = c2 % q
# Chinese Remainder Theorem
m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N
return m
c = encrypt(bytes_to_long(flag))
# N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283
# g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208
# g2 = 14068322834597276347776814624877614869834816383564391664570268934537693322688875343215293618493363798985047779057952636529313879548457643220996398640913517182122425631198219387988691569709691279442005545716133131472147592456812502863851227108284027033557263611949365667779259585770738623603814004666845554284808166195201470503432803440754207350347128045893594280079379926676477680556845095378093693409219131090910168117334308781843178748431526974047817218228075136005979538773141427004682344298827618677773735288946271346252828348742296301538573408254015281232250841148556304927266143397565889649305095857756884049430
# c1, c2 = (3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534, 18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344)$$
g1\equiv g^{r1(p-1)}\bmod N
$$
$$
g2\equiv g^{r2(q-1)}\bmod N
$$
费马小定理
$$
1\equiv g^{r1(p-1)}\bmod p
$$
$$
1\equiv g^{r2(q-1)}\bmod q
$$
$$
p=gcd(g1-1,N)
$$
$$
q=gcd(g2-1,N)
$$
N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283
g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208
g2 = 14068322834597276347776814624877614869834816383564391664570268934537693322688875343215293618493363798985047779057952636529313879548457643220996398640913517182122425631198219387988691569709691279442005545716133131472147592456812502863851227108284027033557263611949365667779259585770738623603814004666845554284808166195201470503432803440754207350347128045893594280079379926676477680556845095378093693409219131090910168117334308781843178748431526974047817218228075136005979538773141427004682344298827618677773735288946271346252828348742296301538573408254015281232250841148556304927266143397565889649305095857756884049430
c1, c2 = (3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534, 18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344)
p = gcd(g1-1, N)
q = gcd(g2-1, N)
m = decrypt(c1, c2)
print n2s(m)[NPUCTF2020]babyLCG
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag
class LCG:
def __init__(self, bit_length):
m = getPrime(bit_length)
a = getRandomRange(2, m)
b = getRandomRange(2, m)
seed = getRandomRange(2, m)
self._key = {'a':a, 'b':b, 'm':m}
self._state = seed
def next(self):
self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
return self._state
def export_key(self):
return self._key
def gen_lcg():
rand_iter = LCG(128)
key = rand_iter.export_key()
f = open("key", "w")
f.write(str(key))
return rand_iter
def leak_data(rand_iter):
f = open("old", "w")
for i in range(20):
f.write(str(rand_iter.next() >> 64) + "\n")
return rand_iter
def encrypt(rand_iter):
f = open("ct", "wb")
key = rand_iter.next() >> 64
key = (key << 64) + (rand_iter.next() >> 64)
key = long_to_bytes(key).ljust(16, b'\x00')
iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
ct = cipher.encrypt(pt.encode())
f.write(ct)
def main():
rand_iter = gen_lcg()
rand_iter = leak_data(rand_iter)
encrypt(rand_iter)
if __name__ == "__main__":
main()就是要求seed，只有20组的高位，设高位为c，低位为d
$$
c_{2}+d_{2}\equiv a(c_{1}+d_{1})+b(\bmod m)
$$
$$
c_{2}+d_{2}=a(c_{1}+d_{1})+b+km
$$
$$
d_{2}=mk+ad_{1}+ac_{1}+b-c_{2}=f(k,d_{1})+C
$$
构造格子如下：
$$
\begin{pmatrix}k&d_{1}&0\end{pmatrix}\begin{pmatrix}m&0&0\a&1&0\ac_{1}+b-c_{2}&0&2^{64}\end{pmatrix}=\begin{pmatrix}d_{2}&d_{1}&…\end{pmatrix}
$$
# sage
b = 153582801876235638173762045261195852087
a = 107763262682494809191803026213015101802
m = 226649634126248141841388712969771891297
c1 = 7800489346663478448<<64
c2 = 11267068470666042741<<64
M = matrix(ZZ, 3, 3, [m, 0, 0, a, 1, 0, (a*c1+b-c2)%m, 0, 2^64])
for i in range(3):
res = M.LLL()[i]
d2 = abs(res[0])
d1 = abs(res[1])
s2 = c2+d2
s1 = c1+d1
if (a*s1+b)%m == s2:
seed = ((s1 - b)*inverse_mod(a,m))%m
print(seed)
# 73991202721494681711496408225724067994from Crypto.Util.number import *
from Crypto.Cipher import AES
class LCG:
def __init__(self, bit_length):
b = 153582801876235638173762045261195852087
a = 107763262682494809191803026213015101802
m = 226649634126248141841388712969771891297
seed = 73991202721494681711496408225724067994
self._key = {'a':a, 'b':b, 'm':m}
self._state = seed
def next(self):
self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
return self._state
def export_key(self):
return self._key
def gen_lcg():
rand_iter = LCG(128)
key = rand_iter.export_key()
return rand_iter
def leak_data(rand_iter):
for i in range(20):
print(str(rand_iter.next() >> 64) + "\n")
return rand_iter
def decrypt(rand_iter):
flag = open("ct.txt", "rb").read()
key = rand_iter.next() >> 64
key = (key << 64) + (rand_iter.next() >> 64)
key = long_to_bytes(key).ljust(16, b'\x00')
iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.decrypt(flag))
def main():
rand_iter = gen_lcg()
rand_iter = leak_data(rand_iter)
decrypt(rand_iter)
if __name__ == "__main__":
main()
# b'npuctf{7ruc4t3d-L(G-4nd-LLL-4r3-1nt3r3st1ng}\x04\x04\x04\x04'[CISCN2018]sm
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
import hashlib
from random import randint
def gen512num():
order=[]
while len(order)!=512:
tmp=randint(1,512)
if tmp not in order:
order.append(tmp)
ps=[]
for i in range(512):
p=getPrime(512-order[i]+10)
pre=bin(p)[2:][0:(512-order[i])]+"1"
ps.append(int(pre+"0"*(512-len(pre)),2))
return ps
def run():
choose=getPrime(512)
ps=gen512num()
print "gen over"
bchoose=bin(choose)[2:]
r=0
bchoose = "0"*(512-len(bchoose))+bchoose
for i in range(512):
if bchoose[i]=='1':
r=r^ps[i]
flag=open("flag","r").read()
key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))
aes_obj = AES.new(key, AES.MODE_ECB)
ef=aes_obj.encrypt(flag).encode("base64")
open("r", "w").write(str(r))
open("ef","w").write(ef)
gg=""
for p in ps:
gg+=str(p)+"\n"
open("ps","w").write(gg)
run()$$
0\oplus ps[i]\oplus … = r
$$
设bchoose的矩阵是C，ps矩阵是A，r矩阵是B
$$
C*A=B
$$
$$
C=B*A^{-1}
$$
# sage
ps = open('/Users/lizihan/Downloads/attachment (1)/ps.txt').readlines()
#print(ps)
p = [i for i in ps]
A = []
for i in p:
A.append([int(x) for x in bin(int(i))[2:].zfill(512)])
#print(A)
r = open('/Users/lizihan/Downloads/attachment (1)/r.txt').read()
B = [int(x) for x in bin(int(r))[2:].zfill(512)]
A = matrix(GF(2), A)
B = matrix(GF(2), B)
key = B*A.inverse()
l = []
for i in key:
l.append(i)
print(l)from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
from Crypto.Cipher import AES
import hashlib
import base64
l = [1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1]
bchoose = '0b'
for i in l:
bchoose += str(i)
choose = int(bchoose, 2)
key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16))
aes_obj = AES.new(key, AES.MODE_ECB)
ef = base64.b64decode(b'5eFo3ANg2fu9LRrFktWCJmVvx6RgBFzd0R8GXQ8JD78=')
flag = aes_obj.decrypt(ef)
print(flag)
# b'flag{shemir_alotof_in_wctf_fun!}'[watevrCTF2019]ECC-RSA
from fastecdsa.curve import P521 as Curve
from fastecdsa.point import Point
from Crypto.Util.number import bytes_to_long, isPrime
from os import urandom
from 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")$$
q^{2} = p^{3} + ap + b
$$
$$
p^{5}+ap^{3}+bp^{2}-n^{2}\equiv0(\bmod eccp)
$$
from gmpy2 import *
from Crypto.Util.number import *
eccp = 0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
a = -0x3
b = 0x51953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
e = 0x10001
n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
c = 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e
P.<x> = Zmod(eccp)[]
f = x^5 + a*x^3 + b*x^2 - n^2
# print(f.roots())
p = 4573744216059593260686660411936793507327994800883645562370166075007970317346237399760397301505506131100113886281839847419425482918932436139080837246914736557
q = n // p
d = invert(e, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, n)))
# b'watevr{factoring_polynomials_over_finite_fields_is_too_ez}'[watevrCTF2019]Swedish RSA
flag = bytearray(raw_input())
flag = list(flag)
length = len(flag)
bits = 16
## Prime for Finite Field.
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")
## Univariate Polynomial Ring in y over Finite Field of size p
R.<y> = PolynomialRing(GF(p))
## Analogous to the primes in Z
def gen_irreducable_poly(deg):
while True:
out = R.random_element(degree=deg)
if out.is_irreducible():
return out
## Polynomial "primes"
P = gen_irreducable_poly(ZZ.random_element(length, 2*length))
Q = gen_irreducable_poly(ZZ.random_element(length, 2*length))
## Public exponent key
e = 65537
## Modulus
N = P*Q
file_out.write("Modulus: " + str(N) + "\n")
## Univariate Quotient Polynomial Ring in x over Finite Field of size 659 with modulus N(x)
S.<x> = R.quotient(N)
## Encrypt
m = S(flag)
c = m^e
file_out.write("Ciphertext: " + str(c))
file_out.close()# sage
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)
# print(factor(N))
e = 65537
phi = (43753^65-1)*(43753^112-1)
d = inverse_mod(e, phi)
ans = R("1")
temp= c
# while(True):
# if(d % 2 == 1):
# ans = (ans * temp) % N
# d = d - 1
# d = d / 2
# temp = (temp * temp) % N
# if(d == 0):
# break
# #快速幂
# print (ans)
flag = 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
res = ''
for i in flag:
res += chr(i)
print(res)
# watevr{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}[GUET-CTF2019]Uncle Sam
from Crypto.Util.number import *
def generkey(k):
p, q = getPrime(k), getPrime(k)
pubkey = p**2 * q
n = pubkey
l = (p-1)*(q-1) / gcd(p-1, q-1)
privkey = inverse(n, l)
return pubkey, privkey
def encrypt(m, pubkey):
return pow(bytes_to_long(m), pubkey, pubkey)
# pubkey = 2188967977749378274223515689363599801320698247938997135947965550196681836543275429767581633044354412195352229175764784503562989045268075431206876726265968368605210824232207290410773979606662689866265612797103853982014198455433380266671856355564273196151136025319624636805659505233975208570409914054916955097594873702395812044506205943671404203774360656553350987491558491176962018842708476009578127303566834534914605109859995649555122751891647040448980718882755855420324482466559223748065037520788159654436293431470164057490350841209872489538460060216015196875136927502162027562546316560342464968237957692873588796640619530455268367136243313422579857823529592167101260779382665832380054690727358197646512896661216090677033395209196007249594394515130315041760988292009930675192749010228592156047159029095406021812884258810889225617544404799863903982758961208187042972047819358256866346758337277473016068375206319837317222523597
# privkey = 1430375790065574721602196196929651174572674429040725535698217207301881161695296519567051246290199551982286327831985649037584885137134580625982555634409225551121712376849579015320947279716204424716566222721338735256648873164510429206991141648646869378141312253135997851908862030990576004173514556541317395106924370019574216894560447817319669690140544728277302043783163888037836675290468320723215759693903569878293475447370766682477726453262771004872749335257953507469109966448126634101604029506006038527612917418016783711729800719387298398848370079742790126047329182349899824258355003200173612567191747851669220766603
# enc = 1491421391364871767357931639710394622399451019824572362288458431186299231664459957755422474433520889084351841298056066100216440853409346006657723086501921816381226292526490195810903459483318275931326433052468863850690793659405367902593999395060606972100169925074005992478583035226026829214443008941631771292291305226470216430735050944285543542354459162474346521327649934512511202470099020668235115245819634762067338432916012664452035696422865651002305445711778476072004708256200872226475346448360491248823843688268126341094612981308791499434770936360676087490303951728563482686307164877000300082742316368597958297217061375140696272398140310043942637287763946305961019518639745426370821124559939597559475362769382796386720030343305889701616194279058139516811941262747298761646317383112470923295543635754747288259324745583689440061956478083777663996487389553238481759103908588004219390662578446313004404784835263543083088327198$$
\because n=p^{2}q
$$
$$
\therefore\phi(n)=p(p-1)(q-1)
$$
费马小定理：
$$
a^{p(p-1)(q-1)}\equiv1(\bmod n)
$$
由题目：
$$
nd\equiv1(\bmod (p-1)(q-1))
$$
$$
a^{nd}\equiv a^{nd\bmod((p-1)(q-1))}\equiv a\bmod(pq)
$$
$$
a^{nd}-a\equiv0(\bmod pq)
$$
$$
pq=gcd(a^{nd}-a, n)
$$
这里取a=2
from gmpy2 import *
from libnum import *
n = 2188967977749378274223515689363599801320698247938997135947965550196681836543275429767581633044354412195352229175764784503562989045268075431206876726265968368605210824232207290410773979606662689866265612797103853982014198455433380266671856355564273196151136025319624636805659505233975208570409914054916955097594873702395812044506205943671404203774360656553350987491558491176962018842708476009578127303566834534914605109859995649555122751891647040448980718882755855420324482466559223748065037520788159654436293431470164057490350841209872489538460060216015196875136927502162027562546316560342464968237957692873588796640619530455268367136243313422579857823529592167101260779382665832380054690727358197646512896661216090677033395209196007249594394515130315041760988292009930675192749010228592156047159029095406021812884258810889225617544404799863903982758961208187042972047819358256866346758337277473016068375206319837317222523597
d = 1430375790065574721602196196929651174572674429040725535698217207301881161695296519567051246290199551982286327831985649037584885137134580625982555634409225551121712376849579015320947279716204424716566222721338735256648873164510429206991141648646869378141312253135997851908862030990576004173514556541317395106924370019574216894560447817319669690140544728277302043783163888037836675290468320723215759693903569878293475447370766682477726453262771004872749335257953507469109966448126634101604029506006038527612917418016783711729800719387298398848370079742790126047329182349899824258355003200173612567191747851669220766603
c = 1491421391364871767357931639710394622399451019824572362288458431186299231664459957755422474433520889084351841298056066100216440853409346006657723086501921816381226292526490195810903459483318275931326433052468863850690793659405367902593999395060606972100169925074005992478583035226026829214443008941631771292291305226470216430735050944285543542354459162474346521327649934512511202470099020668235115245819634762067338432916012664452035696422865651002305445711778476072004708256200872226475346448360491248823843688268126341094612981308791499434770936360676087490303951728563482686307164877000300082742316368597958297217061375140696272398140310043942637287763946305961019518639745426370821124559939597559475362769382796386720030343305889701616194279058139516811941262747298761646317383112470923295543635754747288259324745583689440061956478083777663996487389553238481759103908588004219390662578446313004404784835263543083088327198
x = gcd(n, pow(2, n*d, n)-2)
print n2s(pow(c, d, x))
# flag{61e19444-7afb-11e9-b704-4ccc6adfc6f0}s[b01lers2020]safety_in_numbers
n很大，直接对c开e次方得到m，因为小端序存储，所以最后[::-1]反序
cryptoku
11littlersa
from Crypto.Util.number import bytes_to_long, getPrime
from secret import flag
p, q = getPrime(1024), getPrime(1024)
n = p*q
e = 0x10001
s = pow(1314*p - 520*q, n - p - q, n)
c = pow(bytes_to_long(flag), e, n)
print(f'n = {n}')
print(f's = {s}')
print(f'c = {c}')$$
\phi(n)=(p-1)(q-1)=pq-p-q+1
$$
$$
(1314p-520q)^{\phi(n)}\equiv 1(\bmod n)
$$
$$
s\equiv(1314p-520q)^{n-p-q}(\bmod n)\equiv(1314p-520q)^{-1}(\bmod n)
$$
$$
1314p-520q\equiv s^{-1}(\bmod n)
$$
from gmpy2 import *
from libnum import *
n = 21527992586049890742463208685084056886310965008510150149662539465508522110836141118201993905501496573947758250830179174167767904598851246246883313258119194517451136464061754012857201163557130509549702608281712944282522512395405915342449680305392687437622431284142745065375302709310557854831484673680407778594714529585782056415778141766213407370997672554723753202013563817286448850181916119501687341489042612085905005774185877110170473521083991709238570129700236355021759838698301009539406493513673267448754800055385494881665134028236347565559420582088784168876596273511904770078853805492034067652075997160067097096389
s = 689371464378603954186279564342194575991521192704684277207288178599489794962450715850049002302487534260512846768904192932944096786449367699010863982182323679968386484011474068581844681990765999053322562552934116860156681394692018958475994862295885631931726039769250893352710917976460230207966276224955917433141021398552482066127690546179606369096409983860114624081300199440661763939814014217903483843133317053237884070077730674376541753789775676614501869056220897164107160298416764019915900754814865340973490933257727198707945012160497462607376733744883748828632202067199804149859997895800374289404967684151848041078
c = 16018690856580134963499619732983511637301063037736211987652823346056397737077114122360038377367134402506313854843001130337277242449318875422253234028539504328893925016557601740495977176944226657312832415247368764132804576588715682110651105761722000223962198274728394855418102910814601509869869023753969580176908357542029260491093770925557678492025234534301611764843254092935308547079513469696933137356279998386197451965233193792656124337741310279640692073770305956685952966109064967232736373641126701147376387370878674943061250794501317147835670604279925388762127236579127880834986244206920182304311470798055226190212
# from sympy import *
# s = invert(s, n)
# p = Symbol('p')
# q = Symbol('q')
# p, q = solve([p*q-n, 1314*p-520*q-s], [p, q])
# print(p, q)
p = 154284076004209590955001376421515345266804896344881716639416022056900642771581349207838844600803873059250955811948664771306587899601011067929479621101844021172358446324898774632702069255293306160485960431628918978692153936045835115287574063945828069016255778095497627064585169033677372120904914719277876790361
q = 139534766928652484198642301870530258382621694742867470419339097644217217548670323347872788454147801929413925661162297845232088692598434720859485702680791518176068930632495796027974231708386994067530792729112431398309511627474634552488231112040611112002376565831994653508566728340240409080110236842144836956749
d = invert(e, (p-1)*(q-1))
print(n2s(pow(c, d, n)))12eeeeezrsa
from Crypto.Util.number import getPrime,bytes_to_long
from gmpy2 import powmod,is_prime,invert,bit_length
from FLAG import flag
def RSA_genParameter():
(p,q,n,e,d) = (0 for _ in range(5))
p = getPrime(200)
q = p + 1
while(True):
q += 2 if q & 1 else 1
if is_prime(q, 30):
break
assert p < q
n = p*q
e = 0x10001
d = invert(e, (p-1)*(q-1))
cipherParameter = (p,q,n,e,d)
return cipherParameter
def leak_info(cipherParameter,c):
assert len(cipherParameter) == 5
(p,q,n,e,d) = cipherParameter
print("Here's sthg you may want to know.")
print("n =",n)
print("e =",e)
print("c_mod_p =",c % p)
print("c_mod_q =",c % q)
def RSA_encryption(message,cipherParameter):
assert len(cipherParameter) == 5
(p,q,n,e,d) = cipherParameter
m = bytes_to_long(message)
assert bit_length(q) < bit_length(m) < bit_length(n)
c = powmod(m,e,n)
return c
if __name__ == '__main__':
cipherParameter = RSA_genParameter()
c = RSA_encryption(flag,cipherParameter)
leak_info(cipherParameter,c)pq相差不大，对n开方爆破，最后中国剩余定理
from gmpy2 import *
from libnum import *
from tqdm import tqdm
n = 1868334156775298896231812470739357521959374975890291444695640351814139728754262335708297349257391991779446164262218985159
e = 65537
c_mod_p = 1062384575136942194457401502734355664153040886120004084031121
c_mod_q = 255520115722444172168148366934668388396463537147929322939703
# p = iroot(n, 2)[0]
# for i in tqdm(range(1000)):
# p -= 1
# if is_prime(p):
# q = next_prime(p)
# if p*q == n:
# print(p)
# print(q)
# exit()
p = 1366870204801940547527182701310518853392777286350885464974949
q = 1366870204801940547527182701310518853392777286350885464975291
d = invert(e, (p-1)*(q-1))
c = (c_mod_p*invert(q, p)*q + c_mod_q*invert(p, q)*p) % n
print(n2s(pow(c, d, n)))1ezDLP1
from Crypto.Util.number import *
from secret import FLAG
x=bytes_to_long(FLAG)
g=19
p=335215034881592512312398694238485179340610060759881511231472142277527176340784432381542726029524727833039074808456839870641607412102746854257629226877248337002993023452385472058106944014653401647033456174126976474875859099023703472904735779212010820524934972736276889281087909166017427905825553503050645575935980580803899122224368875197728677516907272452047278523846912786938173456942568602502013001099009776563388736434564541041529106817380347284002060811645842312648498340150736573246893588079033524476111268686138924892091575797329915240849862827621736832883215569687974368499436632617425922744658912248644475097139485785819369867604176912652851123185884810544172785948158330991257118563772736929105360124222843930130347670027236797458715653361366862282591170630650344062377644570729478796795124594909835004189813214758026703689710017334501371279295621820181402191463184275851324378938021156631501330660825566054528793444353
h=pow(g,x,p)
print(h)用discrete_log函数求解离散对数，第一个参数是模数，第二个参数是余数，第三个参数是底数
print(long_to_bytes(discrete_log(p, h, g)))3friends8470
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime
FLAG = b"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)
my_key = (N, d)
friends = 8470
friend_keys = [(N, getPrime(17)) for _ in range(friends)]
cipher = bytes_to_long(FLAG)
for key in friend_keys:
cipher = pow(cipher, key[1], key[0])
f=open(r'C:\Users\dell\Desktop\新建文件夹\output.txt','w')
f.write("My private key: {}\n".format(my_key))
f.write("My Friend's public keys: {}\n".format(friend_keys))
f.write("Encrypted flag: {}".format(cipher))
f.close()先用d分解n得到pq，再用8470组随机的e来循环解密
from gmpy2 import *
from random import *
from libnum import *
n = 9297128283983941432045234147703287250798904268213511485649937145473424112522632091170463801330377126937076682880003270817044620519588692217610024692461756476752594502866379940325928306678497619609001865840258345351699434491103889835804179223493975567452456409725769747131345103948177587204595896812289690514961222948520456725050008127602344945524085088187909363361785959139547611544443308370415769438618596524731053548712520584571294810550954901279297527175272717793850043803267593549272731006423249152834079138241719534660665593188796158286929076617604721784539091610652167054547455662364998461130576136393569033813
# e = 0x10001
# d = 6770020798885601064459690086986648419516854729266725798093778329698158580983529476279476387245213965070389406550229581659243182096469645523917835854530302033051010382841635257826483918696582722745935823176139417660545220443702808102813416010540656362139456753304895091968646450031568106476722004113293267931645917258893154445063272866515222067643284609528131590504180360042380847074388715109170360380897549117453522559309939506123630622924554811758586737785047436321787103828109958069019456723464178418058164853262404820775941088122590290160976865610244219489885823711823941542135342825622883363168882921952842121633
# def getpq(n, e, d):
# while True:
# k = e * d - 1
# g = randint(0, n)
# while k % 2 == 0:
# k = k // 2
# temp = pow(g, k, n) - 1
# if gcd(temp, n) > 1 and temp != 0:
# return gcd(temp, n)
# p = getpq(n, e, d)
# q = n // p
# print(p, q)
p = 101665011582651453374639803565481302049981406968172618891916121842144444187702507883777930908263676281802852505341671701004463488880202765828561612794953216299967043485152863592862914928641800350504709331953141076969087534525669455464181441497270220049964519511886797924686414128228303396106049236567397802253
q = 91448652188718607674536149764330302168277487253616424144817592968724886973818242765838687004195988983146722344012143324133761729763148910627851790703713801218943004433890303118840339404360417832267178619895052804669076307048806566907571706501040337228809066397074242066455053587803754827151822332719673020521
c = 2140180080934141827450126364391018115860389226884426757770714360018926009963088161257799535546140166149364676631283332158950547864614389850798718187432074087541976429222957826470201323917675604895134829043587019669199783408789746196365136682199920323822099947472839409935007795402592449380881687184818261811177333059582900044459905652841833575554703149217878353476815356254727032482879912733566474034636632524362926394011231323451701169715998263415893218582682966676188175274811817023283479089335113330942129729688827121339968304170401548272904535035612550021543429243345521989994397488226013103294945141772283585871
e =
e = e[::-1]
from tqdm import tqdm
for i in tqdm(e):
d = invert(i, (p-1)*(q-1))
c = pow(c, d, n)
print(n2s(c))15FwRSA1
from Crypto.Util.number import *
from os import urandom
from random import randint
from secret import flag
m=bytes_to_long(flag)
p=getPrime(256)
q=getPrime(2048)
e=10007
n=p*q
f=getPrime(200)
c=pow(m,e,n)
r=348839131610151502497259090343608859521638225585948539355235805416998922506252838526137107642248922957945029984864898040083389762927448651701934862548862243576769546778107847452918384857322265982526840217472192128124528285918345330110723123433656768664899422877893087552183627675058904910388326441867525988276987265395780819178852504141769404291727430703468489502342212147446099165213452396270310114148938660411646174364616328990161600167229258203782409553365813379255237357273330004080769083627285528263323766522062801308515349668978595752320407544952912547157680347320670156733011984612736871189579240255899393186551853745958340396834063474144474999600546323965307387862449136280226873741996433230472616299022027512571576609288751470982626619954105037930619399475215320588316683586987187571797605468130139607830931194115605143664746831017839122419503652878578762022011266540177318575415788308050665106331551844524585012870487813810607617422536650365491146285696876926188995154449860004922949730904320705772054601052781208968873449657164701848998563087238767195491607087750944267163721274679321454451772574982106455686603260593968904504261107423334079578666110521816206168880831013715650059006028362724318932856902542115065802613405089419492547393548641346438052909352742641202034829737046695805732331925243748516214791227685903754750563838997575837898379170873992023639274795144036895836861639527076861155907115597701350403372007773865437618084954365027859717120052135447470120382123882602757439306701374395747663873
h=p*inverse(f,r)%r
ooo=open("given.py","w")
ooo.write("e="+str(e)+'\n')
ooo.write("n="+str(n)+'\n')
ooo.write("r="+str(r)+'\n')
ooo.write("h="+str(h)+'\n')
ooo.write("c="+str(c)+'\n')
ooo.close()格
h =
p =
c =
v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
m = matrix([v1,v2]);
shortest_vector = m.LLL()[0]
f, g = shortest_vector
print(f, g)
f =
g =
a = f*c % p % g
m = a * inverse_mod(f, g) % g
print(m)
from gmpy2 import *
from libnum import *
p =
n =
c =
q = n // p
d = invert(e, (p-1)*(q-1))
print(n2s(pow(c, d, n)))14boom
from Crypto.Util.number import*
from secret import flag
assert flag[:5] == "aflag"
class LCG:
def __init__(self):
self.a = getRandomNBitInteger(32)
self.b = getRandomNBitInteger(32)
self.m = getPrime(32)
self.seed = getRandomNBitInteger(32)
def next(self):
self.seed = (self.a*self.seed+self.b) % self.m
return self.seed >> 16
def output(self):
print("a = {}\nb = {}\nm = {}".format(self.a, self.b, self.m))
print("state1 = {}".format(self.next()))
print("state2 = {}".format(self.next()))
lcg = LCG()
lcg.output()
c = b''.join([long_to_bytes(ord(flag[i]) ^ (lcg.next() % 10))
for i in range(len(flag))])
print(bytes_to_long(c))
'''
a = 2901797069
b = 3983697489
m = 3156268457
state1 = 46432
state2 = 37133
555944023803039445280183217695573804405851318132
'''
#hint :题目名字不需要求出种子，只需要还原移位爆破满足条件的
a = 2901797069
b = 3983697489
m = 3156268457
se=[]
for i in range(65536):
s=(46432<<16)+i
s = (a*s+b) % m
if (s>>16)==37133:
se.append(s)
from Crypto.Util.number import*
class LCG:
def __init__(self):
self.a = 2901797069
self.b = 3983697489
self.m = 3156268457
self.seed =0
def next(self):
self.seed = (self.a*self.seed+self.b) % self.m
return self.seed >> 16
lcg = LCG()
c=555944023803039445280183217695573804405851318132
c=long_to_bytes(c)
for _ in se:
lcg.seed=_
t=b''.join([long_to_bytes((c[i]) ^ (lcg.next() % 10))
for i in range(len(c))])
if t[:5]==b'aflag':
print(t)
[INSHack2019]Yet Another RSA Challenge - Part 1
import subprocess
p = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
q = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
flag = int('INSA{REDACTED}'.encode('hex'), 16)
N = int(p,16) * int(q,16)
print N
print '0x'+p.replace('9F','FC')
print pow(flag,65537,N)p的所有9f被替换成fc，切片再爆破插入即可
from gmpy2 import *
from libnum import *
n = 719579745653303119025873098043848913976880838286635817351790189702008424828505522253331968992725441130409959387942238566082746772468987336980704680915524591881919460709921709513741059003955050088052599067720107149755856317364317707629467090624585752920523062378696431510814381603360130752588995217840721808871896469275562085215852034302374902524921137398710508865248881286824902780186249148613287250056380811479959269915786545911048030947364841177976623684660771594747297272818410589981294227084173316280447729440036251406684111603371364957690353449585185893322538541593242187738587675489180722498945337715511212885934126635221601469699184812336984707723198731876940991485904637481371763302337637617744175461566445514603405016576604569057507997291470369704260553992902776099599438704680775883984720946337235834374667842758010444010254965664863296455406931885650448386682827401907759661117637294838753325610213809162253020362015045242003388829769019579522792182295457962911430276020610658073659629786668639126004851910536565721128484604554703970965744790413684836096724064390486888113608024265771815004188203124405817878645103282802994701531113849607969243815078720289912255827700390198089699808626116357304202660642601149742427766381
p = 'DCC5A0BD3A1FC0BEB0DA1C2E8CF6B474481B7C12849B76E03C4C946724DB577D2825D6AA193DB559BC9DBABE1DDE8B5E7805E48749EF002F622F7CDBD7853B200E2A027E87E331AFCFD066ED9900F1E5F5E5196A451A6F9E329EB889D773F08E5FBF45AACB818FD186DD74626180294DCC31805A88D1B71DE5BFEF3ED01F12678D906A833A78EDCE9BDAF22BBE45C0BFB7A82AFE42C1C3B8581C83BF43DFE31BFD81527E507686956458905CC9A660604552A060109DC81D01F229A264AB67C6D7168721AB36DE769CEAFB97F238050193EC942078DDF5329A387F46253A4411A9C8BB71F9AEB11AC9623E41C14FCD2739D76E69283E57DDB11FC531B4611EE3'
c = 596380963583874022971492302071822444225514552231574984926542429117396590795270181084030717066220888052607057994262255729890598322976783889090993129161030148064314476199052180347747135088933481343974996843632511300255010825580875930722684714290535684951679115573751200980708359500292172387447570080875531002842462002727646367063816531958020271149645805755077133231395881833164790825731218786554806777097126212126561056170733032553159740167058242065879953688453169613384659653035659118823444582576657499974059388261153064772228570460351169216103620379299362366574826080703907036316546232196313193923841110510170689800892941998845140534954264505413254429240789223724066502818922164419890197058252325607667959185100118251170368909192832882776642565026481260424714348087206462283972676596101498123547647078981435969530082351104111747783346230914935599764345176602456069568419879060577771404946743580809330315332836749661503035076868102720709045692483171306425207758972682717326821412843569770615848397477633761506670219845039890098105484693890695897858251238713238301401843678654564558196040100908796513657968507381392735855990706254646471937809011610992016368630851454275478216664521360246605400986428230407975530880206404171034278692756
e = 65537
p1 = p.split('FC')
# print(p1)
# print(len(p1))
# print(int(p, 16))
# s = ['9F', 'FC']
# salt = []
# for a in range(2):
# for b in range(2):
# for c in range(2):
# for d in range(2):
# salt.append(s[a]+s[b]+s[c]+s[d])
# print(salt)
# print(len(salt))
salt = ['9F9F9F9F', '9F9F9FFC', '9F9FFC9F', '9F9FFCFC', '9FFC9F9F', '9FFC9FFC', '9FFCFC9F', '9FFCFCFC', 'FC9F9F9F', 'FC9F9FFC', 'FC9FFC9F', 'FC9FFCFC', 'FCFC9F9F', 'FCFC9FFC', 'FCFCFC9F', 'FCFCFCFC']
for i in range(16):
p = p1[0] + salt[i][0:2] + p1[1] + salt[i][2:4] + p1[2] + salt[i][4:6] + p1[3] + salt[i][6:8] + p1[4]
p = int(p, 16)
if is_prime(p):
q = n // p
d = invert(e, (p-1)*(q-1))
print(n2s(pow(c, d, n)))
break
# INSA{I_w1ll_us3_OTp_n3xT_T1M3}[MRCTF2020]Easy_RSA
import sympy
from gmpy2 import gcd, invert
from random import randint
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
import base64
from zlib import *
flag = b"MRCTF{XXXX}"
base = 65537
def gen_prime(N):
A = 0
while 1:
A = getPrime(N)
if A % 8 == 5:
break
return A
def gen_p():
p = getPrime(1024)
q = getPrime(1024)
assert (p < q)
n = p * q
print("P_n = ", n)
F_n = (p - 1) * (q - 1)
print("P_F_n = ", F_n)
factor2 = 2021 * p + 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
return sympy.nextprime(factor2)
def gen_q():
p = getPrime(1024)
q = getPrime(1024)
assert (p < q)
n = p * q
print("Q_n = ", n)
e = getRandomNBitInteger(53)
F_n = (p - 1) * (q - 1)
while gcd(e, F_n) != 1:
e = getRandomNBitInteger(53)
d = invert(e, F_n)
print("Q_E_D = ", e * d)
factor2 = 2021 * p - 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
return sympy.nextprime(factor2)
if __name__ == "__main__":
_E = base
_P = gen_p()
_Q = gen_q()
assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1)
_M = bytes_to_long(flag)
_C = pow(_M, _E, _P * _Q)
print("Ciphertext = ", _C)p和q由两种方式生成，p由n和phi解方程组得到，求q转化为已知ed和n的问题
from gmpy2 import *
from libnum import *
#from sympy import *
# p_q = P_n - P_F_n + 1
# p = Symbol('p')
# q = Symbol('q')
# p1, q1 = solve([p*q - P_n, p+q - p_q], [p ,q])
# print(p1, q1)
p1 = 118153578345562250550767057731385782963063734586321112579869747650001448473633860305142281504862521928246520876300707405515141444727550839066835195905927281903880307860942630322499106164191736174201506457157272220802515607939618476716593888428832962374494147723577980992661629254713116923690067827155668889571
q1 = 118975085954858660642562584152139261422493348532593400307960127317249511761542030451912561362687361053191375307180413931721355251895350936376781657674896801388806379750757264377396608174235075021854614328009897408824235800167369204203680938298803752964983358298299699273425596382268869237139724754214443556383
P = next_prime(2021*p1+2020*q1)
K=((Q_E_D-1)//Q_n)+1
phi=(Q_E_D-1)//K
# p_q = Q_n - phi + 1
# p2 = Symbol('p2')
# q2 = Symbol('q2')
# p2, q2 = solve([p2*q2 - Q_n, p2+q2 - p_q], [p2 ,q2])
# print(p2, q2)
p2 = 120538849514661970159855851547577637711900368732462953774738483480759950867244867240401273864984981385806453735655967797329769252143125966966236767391995563418243748302685348336642872306042286401427581501609713577329945760930395130411743322595026287853073310150103535873078436896035943385067893062698858976291
q2 = 171847486694659608706336923173786708071603689972942289760669690002615525263534483261477699540482615520223300780778172120221008417518590133753701145591943840552802072474293556608389677806415392384924913911677288126066245025731416399656855625839288752326267741979436855441260177305707529456715625062080892327017
factor2 = 2021 * p2 - 2020 * q2
if factor2 < 0:
factor2 = (-1) * factor2
Q = next_prime(factor2)
d = invert(65537, (P-1)*(Q-1))
print(n2s(pow(Ciphertext, d, P*Q)))
# MRCTF{Ju3t_@_31mp13_que3t10n}[NPUCTF2020]EzRSA
from gmpy2 import lcm , powmod , invert , gcd , mpz
from Crypto.Util.number import getPrime
from sympy import nextprime
from random import randint
p = getPrime(1024)
q = getPrime(1024)
n = p * q
gift = lcm(p - 1 , q - 1)
e = 54722
flag = b'NPUCTF{******************}'
m = int.from_bytes(flag , 'big')
c = powmod(m , e , n)
print('n: ' , n)
print('gift: ' , gift)
print('c: ' , c)phi是gift的倍数，爆破求解，还要注意e和phi不互素，转化成这个问题：
$$
(m^{gcd(e,\phi(n))})^{\frac{e}{gcd(e,\phi(n))}}\equiv c(\bmod n)
$$
即先用e//gcd(e, phi)求得的d求m，再开gcd(e, phi)次方即可
n = 17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
gift = 2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
c = 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
from gmpy2 import *
from libnum import *
from sympy import Symbol, solve
from tqdm import tqdm
e1 = e // 2
for i in tqdm(range(1000)):
try:
phi = gift * i
if gcd(e1, phi) == 1:
p = Symbol('p')
q = Symbol('q')
p_q = n - phi + 1
p, q = solve([p*q-n, p+q-p_q], [p, q])
d = invert(e1, phi)
print(n2s(iroot(pow(c, d, n), 2)[0]))
exit()
except Exception as ee:
pass
# NPUCTF{diff1cult_rsa_1s_e@sy}[MRCTF2020]babyRSA
import sympy
import random
from gmpy2 import gcd, invert
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
from z3 import *
flag = b"MRCTF{xxxx}"
base = 65537
def GCD(A):
B = 1
for i in range(1, len(A)):
B = gcd(A[i-1], A[i])
return B
def gen_p():
P = [0 for i in range(17)]
P[0] = getPrime(128)
for i in range(1, 17):
P[i] = sympy.nextprime(P[i-1])
print("P_p :", P[9])
n = 1
for i in range(17):
n *= P[i]
p = getPrime(1024)
factor = pow(p, base, n)
print("P_factor :", factor)
return sympy.nextprime(p)
def gen_q():
sub_Q = getPrime(1024)
Q_1 = getPrime(1024)
Q_2 = getPrime(1024)
Q = sub_Q ** Q_2 % Q_1
print("Q_1: ", Q_1)
print("Q_2: ", Q_2)
print("sub_Q: ", sub_Q)
return sympy.nextprime(Q)
if __name__ == "__main__":
_E = base
_P = gen_p()
_Q = gen_q()
assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1)
_M = bytes_to_long(flag)
_C = pow(_M, _E, _P * _Q)
print("Ciphertext = ", _C)for循环prevprime和nextprime即可
P_p = 206027926847308612719677572554991143421
P_factor = 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839
Q_1 = 103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521
Q_2 = 151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743
sub_Q = 168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651
Ciphertext = 1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832
e = 65537
from gmpy2 import *
from libnum import *
from sympy import prevprime, nextprime
from tqdm import tqdm
P = []
for i in range(9):
P_p = prevprime(P_p)
P.append(P_p)
for i in range(1,17):
P.append(nextprime(P[i-1]))
n = 1
phi = 1
for i in range(17):
n *= P[i]
phi *= (P[i]-1)
d = invert(e, phi)
p = nextprime(pow(P_factor, d, n))
q = nextprime(pow(sub_Q, Q_2, Q_1))
d = invert(e, (p-1)*(q-1))
print(n2s(pow(Ciphertext, d, p*q)))
# MRCTF{sti11_@_b@by_qu3st10n}困惑的总结
重难点主要集中在LFSR，ECC，Lattice
有关原理方面的困惑在于coppersmith，Polynomial Ring，Lattice的LLL算法
