Coinc1dens's lessons for cryptography beginner
10分题懒得写，赛后浅写一下（有些还真写不出来）太屑了
古典懒得写，相信都写的出来
1.child exgcd
i 即为m在模p情况下的乘法逆元，反着求i在模p下的乘法逆元即可。
2.child_quadratic_residue
p 1024位，flag160位，p>>flag，直接开方
from Crypto.Util.number import *
from gmpy2 import iroot
p = 92514668543122735752371270312562927033333784558218172827882746297130751282337768353244176170371267417126292468877685711835064518828362290725503081237676172797761025897668830938846775719804590062950271155237320408576251153507336919751071518361423760807270332690021771143981485402084845399742269025273998595431
tmp = 205840081872741614533018920392769203485102161354394579376850093717710932843926743420261035196159236788699786704721272784083171485301715527552338861282446970643372396898033472140600377881068935045649635754249798345769
ff = iroot(tmp,2)[0]
print(long_to_bytes(ff))
3.baby proof of work
简单brute-force
from hashlib import md5
from itertools import product
from string import hexdigits
space = hexdigits[:-6]+'-'
head = 'HZNUCTF{75920709-9c50-4337-90c9-0893f9b'
for i in product(space, repeat=5):
tail = ''.join(i)
flag = head + tail + '}'
if md5(flag.encode()).hexdigest() == '02195c68e0af460e431d8076aeda74d2':
print(flag)
break
4.child stream
c = [38, 51, 47, 60, 52, 59, 63, 26, 27, 94, 21, 29, 2, 12, 50, 5, 73, 1, 17, 14, 12, 49, 67, 23, 26, 86, 15, 10, 7, 54, 15, 93, 27, 90, 31, 54, 91, 29, 85, 16, 40, 9, 73, 19, 40, 95, 15, 12, 49, 4, 93, 4, 29, 27, 17, 31]
key = 'niaiwoyawoainimixuebingchengtianmimi'
f = []
for i in range(len(c)):
f.append(c[i]^ord(key[i%len(key)]))
flag = ''.join([chr(i)for i in f])
print(flag)
5.child gcd
简单的fermat
from Crypto.Util.number import *
from gmpy2 import gcd
e = 65537
n = 13738203833888223857975004809527054170730273366580569709887064476724844829239334926971229398937927727269078648739065881142543314434996373949863203565347334444249904461315463101889503175591648893415760658231943108594137013014616710265378570187435090854096622433598746876924505227494938705014191096368744298373776021084414166841059737596353548357315373897346157785452315099121168558198841367421913509809009384798883580908823738613449245212281713322991173915104883692129931651000984593271411758823416270472426146134625396200912447731883297339491149594216982062541016095285976933523436020034465019839589483763307950773921
c1 = 4119566649646372514375034377445431016534453084292249705712956212949164725780924626854268155256205755612907442220722434919677442528796872037619108857146048991165139575470836491610395951901875493141743643443617221231859597718067854782119844342581656142997804940930064336431509233125279217473019195702748593794727625343279768623056515958462901181806636810038405330945208707109968247427406698445352129796588219016017724993184734209437396262649878184058595127233706036720286397544331724198658358325113988224292145209980914448043725499937915914701214592529718408316174427404981355365930612034291609518156503812336925750686
c2 = 12336384588945193928590817030599708565198779227041828563123804703284188757766690891054375025756078188480801011924832253766309600214953307506639266254960111493910923217553671493793774927430308057347936984488831385572059084080829248263567296843552272346998029090761039578484266971225497295309733573261662020578670668501398457293413997781070442423106857970726106150480887937181249559226389039214930318153030473542474274775888980559141107399057398550162764061182248567179802128225431207798958679197745639433584158138976442862918534102830004326362486719329016661116551536915278366738835646338571606076882953784057711094792
data = bytes_to_long(b'HZNUCTF{')
p = gcd(c2-data,n)
print(p)
q = n//p
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c1,d,n)))
6.child rsa
from Crypto.Util.number import *
e = 65537
c =16041430868820490741771882844013789159571184474605655516247475199888220509034471810934128434588237017071108742577376254566488135884501917057014173509154182762366486394385522207425514072457322837481901923035887293696065698275581009450245271613936314021778197888867395535414366296503796833773796872854616832401650755452407501458489538678718231613553427365115711174016628929120421057478908888730110816285634101547892532989234308112062734995396230991816066603677062899398458018655246210170118613772205286000164766713829400492381726322769338281964550474720344970674903629438176581586646984535415086063409870873623403637161
vul=(168009517112362377449164544338168297587236138698864933557690332239955301291609657577009479197972613355246359995617045603297723054226520723166886734360813831624709233773680820806218764424422774271652121921313925026153278620846194530453971736985756678181161479702260131841302122843924801699275593907790562411351, 108794147561144577802171876747706899910964433464939313504838776034072545978114730155697441642840403762588086568149029322754094862419716600749652335079349768070533154150178763910786849293921803661426089938524154777364737989412101938162378659672868561399302734703205717457974437103370605002834789356039086372233)
p =vul[0]
q = vul[1]
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,p*q)))
7.LCG
有待商榷
8.rsa1
标准的wiener attack,不妨假设p>q满足
连分数展开即可
from Crypto.Util.number import *
import gmpy2
c = 9317127157207764313577260037028164989113868771942543780384280129974642980016359499375110766172547912576065150353885371765890550717906267600639287962504733377789373730036179179575830604617678305655948985281242679190433581785932436544623904311551759080381850497874154146085746912950780592447122175305793697912081715092026188688889781995177992879509993453641884314085251941346179147129092035360861713493476724759534127698890847348726032015570292038279184514652956431387259284296324244773314670850329741144900167251377209619541174834245637214563221950579609634969485305361921927840052357341591007514743472609570124326522
N = 13128768701427441833068297523013876856863497653331827065092886678806551735278720121245856672859945009380991550826213455841967239908658656680890483788084994412694301500867379843829955845652312579305464159078532911665773523444930829392300747303618517884806497754262898272489020444430175781477139337523779726080255797651664905881862330513885843267278358221711408176828580905772982009897619875631660412201747434611120388654478603574942765627500766265984812301366055976341752267279219587370064904404481133032214199810664179729278929595251280558735429556414596434499852080514277396624086980008851664375304143525633087133483
e = 1016312548644607559035990042533682167404878486075298686875531279796839711875919475005923436413513653327398507298281530694620154776665181579407005233063683419650568492132529461150237677088690349366252713853738369870772046301621029264521152741616687363923617496242415660918595594248626096395352606098523614921406516412636188348015528273758851325990526239846852527295035460011096357782936135686807212941539161096156008853997497058129703970016359815615772776949834066524159021857309866024066809264178573661439185456103027667222286018380009015515484439838259385417150389568644350839159558764562686650631546903315639211873
def continuedFra(x, y):
cf = []
while y:
cf.append(x // y)
x, y = y, x % y
return cf
def gradualFra(cf):
numerator = 0
denominator = 1
for x in cf[::-1]:
numerator, denominator = denominator, x * denominator + numerator
return numerator, denominator
def solve_pq(a, b, c):
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
gf = []
for i in range(1, len(cf) + 1):
gf.append(gradualFra(cf[:i]))
return gf
def wienerAttack(e, n):
cf = continuedFra(e, n)
gf = getGradualFra(cf)
for d, k in gf:
if k == 0: continue
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return d
d = wienerAttack(e,N)
print(long_to_bytes(pow(c,d,N)))
9.RSA2
也可以费马分解，这里仅展示费马分解
from Crypto.Util.number import *
from gmpy2 import iroot
from sympy import *
c =17495422915294827741904542028567720072258500321441084423551336456341424186738129419781823269851716691763230154484575675777758790287248519590242148935506967089255103580351707558553454057275981893812191148487881269505054787842300992644568241780895541713274012539866390132259083269532993947743591071406548123291203851032238534539289742037269023692362888953126635074559999456023275664670805121512054430116558877548302087033976099786949234405880200096311759848094187396797741889596735080096136132138829866291718806658094865236547491071025297893415984702434412698276419842078625782979356504253276034817384559442148576549256
N = 18937193919997317153946537868203703628077509329879889728877862655684796091119975113212317303707391338024684488267674922048284525496344550085896447310738759506108482933551382573389098241376052737995323272601521652446491829955896507359200585439213672834804306339292440680090572367343742933534237723999144729381773743267669838284976291354097802611840718127160791914407436981619155049185634625673532147901876050342637367445137414596373226861536902497656791098671179504581373455536709051209379375610293912454568946497549138749899944774235565613763432555478681161173147787955407824271343053265389971038903038772818126386287
e = 65537
a = iroot(N, 2)[0]
while True:
if iroot(abs(a ** 2 - N), 2)[1]:
x = iroot(abs(a ** 2 - N), 2)[0]
p = symbols('p')
q = symbols('q')
ans = solve([ p * q - N, p - q - 2 * x], [p, q])[0]
p = int(abs(ans[0]))
q = int(abs(ans[1]))
print(p,q)
break
a += 1
p = 137612477341254623436114080889916987395415336174736566651668252215321363241723246396805576964715599843444869387339696002768812868136251349820750058348166105361579781267360920691735697534595636600480071717367531944930396429795300442349570542992557645515878891724566217740078093842584454472548208447796637141431
q = N//p
assert p*q==N
phi =(p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,N)))
10.RSA3
已知
其中k为展开式中对应k1，k2的公约数，就出n，再用离散对数求出e即可
from gmpy2 import iroot
from Crypto.Util.number import *
from tqdm import tqdm
from sympy import *
c= 9219741073542293
vul = [7881951730741780, 4599083407040344, 3939540884944030]
x = vul[0]**4-vul[1]**2
y = vul[1]**3-vul[2]**2
n = gcd(x,y)
print(n)
n = 80607070889814954 #[2, 3, 101087743, 132899513]
n = n//6
p =101087743
q = 132899513
phi = (p-1)*(q-1)
#sgameth
# e = discrete_log_lambda(mod(vul[0],n),mod(2,n),(ZZ(2^22),ZZ(2**24)))
e = 4551227
print(pow(2,e,n))
print(gcd(e,phi))
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))
11.RSA4
提示了d<N^0.292,即为boneh_durfee attack,跑个脚本，版子题。
from __future__ import print_function
import time
############################################
# Config
##########################################
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
############################################
# Functions
##########################################
# display stats on helpful vectors
def helpful_vectors(BB, modulus):
nothelpful = 0
for ii in range(BB.dimensions()[0]):
if BB[ii, ii] >= modulus:
nothelpful += 1
print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii, jj] == 0 else 'X'
if BB.dimensions()[0] < 60:
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print(a)
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
# end of our recursive function
if current == -1 or BB.dimensions()[0] <= dimension_min:
return BB
# we start by checking from the end
for ii in range(current, -1, -1):
# if it is unhelpful:
if BB[ii, ii] >= bound:
affected_vectors = 0
affected_vector_index = 0
# let's check if it affects other vectors
for jj in range(ii + 1, BB.dimensions()[0]):
# if another vector is affected:
# we increase the count
if BB[jj, ii] != 0:
affected_vectors += 1
affected_vector_index = jj
# level:0
# if no other vectors end up affected
# we remove it
if affected_vectors == 0:
print("* removing unhelpful vector", ii)
BB = BB.delete_columns([ii])
BB = BB.delete_rows([ii])
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii - 1)
return BB
# level:1
# if just one was affected we check
# if it is affecting someone else
elif affected_vectors == 1:
affected_deeper = True
for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
# if it is affecting even one vector
# we give up on this one
if BB[kk, affected_vector_index] != 0:
affected_deeper = False
# remove both it if no other vector was affected and
# this helpful vector is not helpful enough
# compared to our unhelpful one
if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(
bound - BB[ii, ii]):
print("* removing unhelpful vectors", ii, "and", affected_vector_index)
BB = BB.delete_columns([affected_vector_index, ii])
BB = BB.delete_rows([affected_vector_index, ii])
monomials.pop(affected_vector_index)
monomials.pop(ii)
BB = remove_unhelpful(BB, monomials, bound, ii - 1)
return BB
# nothing happened
return BB
"""
Returns:
* 0,0 if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
"""
Boneh and Durfee revisited by Herrmann and May
finds a solution if:
* d < N^delta
* |x| < e^delta
* |y| < e^0.5
whenever delta < 1 - sqrt(2)/2 ~ 0.292
"""
# substitution (Herrman and May)
PR.< u, x, y > = PolynomialRing(ZZ)
Q = PR.quotient(x * y + 1 - u) # u = xy + 1
polZ = Q(pol).lift()
UU = XX * YY + 1
# x-shifts
gg = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
xshift = x ^ ii * modulus ^ (mm - kk) * polZ(u, x, y) ^ kk
gg.append(xshift)
gg.sort()
# x-shifts list of monomials
monomials = []
for polynomial in gg:
for monomial in polynomial.monomials():
if monomial not in monomials:
monomials.append(monomial)
monomials.sort()
# y-shifts (selected by Herrman and May)
for jj in range(1, tt + 1):
for kk in range(floor(mm / tt) * jj, mm + 1):
yshift = y ^ jj * polZ(u, x, y) ^ kk * modulus ^ (mm - kk)
yshift = Q(yshift).lift()
gg.append(yshift) # substitution
# y-shifts list of monomials
for jj in range(1, tt + 1):
for kk in range(floor(mm / tt) * jj, mm + 1):
monomials.append(u ^ kk * y ^ jj)
# construct lattice B
nn = len(monomials)
BB = Matrix(ZZ, nn)
for ii in range(nn):
BB[ii, 0] = gg[ii](0, 0, 0)
for jj in range(1, ii + 1):
if monomials[jj] in gg[ii].monomials():
BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU, XX, YY)
# Prototype to reduce the lattice
if helpful_only:
# automatically remove
BB = remove_unhelpful(BB, monomials, modulus ^ mm, nn - 1)
# reset dimension
nn = BB.dimensions()[0]
if nn == 0:
print("failure")
return 0, 0
# check if vectors are helpful
if debug:
helpful_vectors(BB, modulus ^ mm)
# check if determinant is correctly bounded
det = BB.det()
bound = modulus ^ (mm * nn)
if det >= bound:
print("We do not have det < bound. Solutions might not be found.")
print("Try with highers m and t.")
if debug:
diff = (log(det) - log(bound)) / log(2)
print("size det(L) - size e^(m*n) = ", floor(diff))
if strict:
return -1, -1
else:
print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
# display the lattice basis
if debug:
matrix_overview(BB, modulus ^ mm)
# LLL
if debug:
print("optimizing basis of the lattice via LLL, this can take a long time")
BB = BB.LLL()
if debug:
print("LLL is done!")
# transform vector i & j -> polynomials 1 & 2
if debug:
print("looking for independent vectors in the lattice")
found_polynomials = False
for pol1_idx in range(nn - 1):
for pol2_idx in range(pol1_idx + 1, nn):
# for i and j, create the two polynomials
PR.< w, z > = PolynomialRing(ZZ)
pol1 = pol2 = 0
for jj in range(nn):
pol1 += monomials[jj](w * z + 1, w, z) * BB[pol1_idx, jj] / monomials[jj](UU, XX, YY)
pol2 += monomials[jj](w * z + 1, w, z) * BB[pol2_idx, jj] / monomials[jj](UU, XX, YY)
# resultant
PR.< q > = PolynomialRing(ZZ)
rr = pol1.resultant(pol2)
# are these good polynomials?
if rr.is_zero() or rr.monomials() == [1]:
continue
else:
print("found them, using vectors", pol1_idx, "and", pol2_idx)
found_polynomials = True
break
if found_polynomials:
break
if not found_polynomials:
print("no independant vectors could be found. This should very rarely happen...")
return 0, 0
rr = rr(q, q)
# solutions
soly = rr.roots()
if len(soly) == 0:
print("Your prediction (delta) is too small")
return 0, 0
soly = soly[0][0]
ss = pol1(q, soly)
solx = ss.roots()[0][0]
#
return solx, soly
def example():
############################################
# How To Use This Script
##########################################
#
# The problem to solve (edit the following values)
#
# the modulus
# the public exponent
N = 14065592081553586649677362809593677808947615098376097590013091148339432844782610190106320045740456328747296931897034090938692923386281174613512781428227462688662680787855438971160769451849995604483501735803832462340126334244995833776362375743254753422272045748341052946851110948805476247180814658530788441490550771452218664392998802182793192557776816892473835916951043922393685580503085621396828663711115447484461987461493717888966837581280110157257964308321126456108710043159884215224944601423203389425009586903863156955702221704039875864764855680733403972798821654638019383211954533671085927462696278553451988394541
e = 5069588906926839416385334689536472096537148140361958136707736655546822194145808240425147597021218379893199694789706004259140485763778799224196246230551884907317969154048058949200950211948948536933798014946353751482336207553761123838481917059046427400474338001327463635454061264600132201025452332535462558687893275809176408183620997988062559295171160329687175692806547722085225496982790032109762077333061750062609767021080146957909430480684067713028202275406618892981419884684805566296352031173988906239390253937241476396296944042886975106574493456234472136621441794501145011662314326765410439530668767410323321962683
# the hypothesis on the private exponent (the theoretical maximum is 0.292)
delta = 0.26 # this means that d < N^delta
#
# Lattice (tweak those values)
#
# you should tweak this (after a first run), (e.g. increment it until a solution is found)
m = 4 # size of the lattice (bigger the better/slower)
# you need to be a lattice master to tweak these
t = int((1 - 2 * delta) * m) # optimization from Herrmann and May
X = 2 * floor(N ^ delta) # this _might_ be too much
Y = floor(N ^ (1 / 2)) # correct if p, q are ~ same size
#
# Don't touch anything below
#
# Problem put in equation
P.< x, y > = PolynomialRing(ZZ)
A = int((N + 1) / 2)
pol = 1 + x * (A + y)
#
# Find the solutions!
#
# Checking bounds
if debug:
print("=== checking values ===")
print("* delta:", delta)
print("* delta < 0.292", delta < 0.292)
print("* size of e:", int(log(e) / log(2)))
print("* size of N:", int(log(N) / log(2)))
print("* m:", m, ", t:", t)
# boneh_durfee
if debug:
print("=== running algorithm ===")
start_time = time.time()
solx, soly = boneh_durfee(pol, e, m, t, X, Y)
# found a solution?
if solx > 0:
print("=== solution found ===")
if False:
print("x:", solx)
print("y:", soly)
d = int(pol(solx, soly) / e)
print("private key found:", d)
else:
print("=== no solution was found ===")
if debug:
print(("=== %s seconds ===" % (time.time() - start_time)))
if __name__ == "__main__":
example()
求出d，标准rsa
12.UniqueRSA
很直接的想法，由低到高逐位爆破。已知异或的结果，每位只有两种情况，即异或结果为0，则pq对应位置不是00就是11，结果为1，不是01就是10。可以通过n来判断是哪种情况，但实际上应用结论2对于n的筛选能力有限，即存在前面一大串比特位都满足异或与结论2，但到下一位就不行了，需要有类似回滚的机制。而深度搜索的核心思想就是，当不能再继续向下访问时，依次退回到最近被访问的点。于是要解出本题就只需要解决下面两个问题
如何退回：用列表保存上一次的所有路径。
如何判断能否继续往下访问：在判断第b位时，如果当前p乘以q的低b位等于n的低b位，则能继续往下访问，否则不能。
from Crypto.Util.number import *
from tqdm import tqdm
n = 17325819141803886246121180660999833445499973739961586452045664353437850410303903264163992983095651264204862589468889900706765222077130679740586949319226547116248002433590507935228144143914908179717209375961540127990426941081532100788762116322576835761495301798726729508015719886193856160842732734360611408431692858357428692724969621159249820772587237099086951071150944985334208103270455644056399752409037564406841043853540848030476311924226553451056143116875192146390966750979052377144354290053918528213624636863475184109170426850104213272768492887187051186664664987924428883110727761003180696765204635989114299712529
x = 47635807301880768328278219673275916715123995405104145227492171981816029326102764933597842002178523932597103491576613824355015140539416815142819391991865430988453616399036460208864029248353308513627101539042048986625206858336967362427051459913726781911644824268570390700981722263472544138095197240541341491984
c = 15617108836696809497142478054184373095670931665414095087667823343032424507606289300965055049597582617402012107396829788946303130532463780132981228308050361498289955425835767511672117944466555649163617822105493424927194779153359974747742869279553303147207585202883489570546322868702921416147346094957323023803951476507736662670647405343462481673194567063581366266345266329475215059463436585171490085946870524233258656491785607730579098119357625976429015860743883897109847567997676755889569568301094741453648211008304494710900296183375204571818839992075171699674832450489767071312452540039936092580652998794886103095211
e = 65537
pre_sol = [(1, 1)]
for i in tqdm(range(1, 1024)):
cur_pow = (1 << (i+1))
cur_sol = []
for pre_p, pre_q in pre_sol:
for s in range(2):
for t in range(2):
cur_p = pre_p + s * (1 << i)
cur_q = pre_q + t * (1 << i)
if (cur_p ^ cur_q == x % cur_pow and cur_p * cur_q % cur_pow == n % cur_pow):
cur_sol.append((cur_p, cur_q))
pre_sol = cur_sol
print(pre_sol)
for p,q in pre_sol:
if n%p==0 or n%q==0:
assert p*q==n
phi = (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))
13.fuckpython
from pwn import *
import string
from hashlib import sha256
from Crypto.PublicKey import RSA
from itertools import product
host = '43.156.230.30'
port = 77
re = remote(host,port)
table = string.digits+string.ascii_letters
# context.log_level = "DEBUG"
def proof_of_work():
re.recvuntil(b'sha256(XXXX+')
tail =re.recv(16).decode()
re.recvuntil(b') == ')
proof = re.recv(64).decode()
for i in product(table, repeat=4):
head = ''.join(i)
x = head + tail
t = sha256(x.encode()).hexdigest()
if t == proof:
re.sendline(head.encode())
break
proof_of_work()
re.recvuntil(b'[-] ')
re.sendline(b'2')
re.recvuntil(b'[-] ')
re.sendline('yes'.encode())
# print(re.recvuntil(b'[1]'))
re.recvuntil(b'[-] ')
re.sendline(b'1')
pem = re.recvuntil(b'-----END RSA PRIVATE KEY-----')[1:]
print(pem)
re.interactive()
手撸一下
14.math1
什么哈皮二次剩余，直接开
from Crypto.Util.number import *
from tqdm import tqdm
c = 2660017383252727614572964032298372293942822109752307411751284055535656581159201400964647759898649179100940612183494529343500493313972988718618109319080556
p = 11724686149875018381319093570203546523969447965821888917032773056114629747530196714947910993013619657768884356655966677779005325066651932348742388568485961
e = 1<<20
PR.<x> = Zmod(p)[]
cs = [c]
for i in tqdm(range(4)):
tmp, cs = cs, []
print(cs)
for c in tmp:
f = x ^ 32 - c
res = f.roots()
if res != []:
cs += [i[0] for i in res]
for m in cs:
mm = long_to_bytes(int(m))
if b'HZNU' in mm:
print(mm)
15.math2
简单的离散对数求解
from Crypto.Util.number import *
from functools import reduce
factors = [2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37]
power = [62, 12, 12, 10, 10, 9, 9, 8, 8, 6, 5, 5, 3]
m = 2
N = reduce(lambda x, y: x * y, [factors[i] ** power[i] for i in range(len(factors))]) + 1
c = 3558696007093002034816187055439537171713283213345173044193665277228385057195377323635032852512758016543007972702434903
c = Mod(c, N)
m = Mod(m, N)
print(long_to_bytes(discrete_log(c, m)))
16.hardmath0
有待商榷