HECTF 2022
流动的音符
题目
♭♭♫♭♭§‖♭∮♭♯♩‖♭♪‖♩♫‖♭‖♭‖§♭‖♩‖♬♫♭‖‖‖♬∮‖¶♩♭‖♪‖♬♯♭♯♪‖¶¶‖♬♭♭‖♪‖♬♫§=脚本
先进行音符解密
然后利用变异凯撒
c = 'EA>N?s:WZgTdPYbMSaYg'
flag=''
k=3
for i in c:
flag += chr(ord(i)+k)
k = k + 1
print(flag)
#HECTF{Caesar_is_fun}rsa2
题目
from Crypto.Util.number import *
import sympy
import random
import math
from secret import flag, hint, e1
def mygenerate():
while True:
p = getPrime(512)
if p % 8 == 5:
break
g = p-random.randint(1 << 13, 1 << 15)
q = sympy.nextprime(math.gamma(g+1) % p)
return p, g, q
p, g, q = mygenerate()
n = p*q
e2 = 65537
m1 = bytes_to_long(flag)
m2 = bytes_to_long(hint)
c1 = pow(m1, e1, p)
c2 = pow(m2, e2, n)
print('p ='+str(p))
print('g ='+str(g))
print('c1 ='+str(c1))
print('c2 ='+str(c2))
'''
p =8245512408967243371517759893329519667642119269153889262506106732818518415823601207067006537187243355250850586456796829524581895578331334132038513672846909
g =8245512408967243371517759893329519667642119269153889262506106732818518415823601207067006537187243355250850586456796829524581895578331334132038513672815766
c1 =6235217214618484469008717065109058585860810027126999050539741461978786126300064219884646722757808536523766850480291000964963856026236813451563022630637528
c2 =11968687437667021636457941077557698735979559596315355015261643918655719362366246657937192921814834456270616376603153881488026042955084056042773344426448580968726245676672896245296438903588066436834165402064132845092674100931069500643230951702318353312541552786636249326131049369846465301549915712690800690627
'''
脚本
第一步分先利用威尔逊定理求
import libnum
import gmpy2
import sympy
e2 = 65537
p = 8245512408967243371517759893329519667642119269153889262506106732818518415823601207067006537187243355250850586456796829524581895578331334132038513672846909
g = 8245512408967243371517759893329519667642119269153889262506106732818518415823601207067006537187243355250850586456796829524581895578331334132038513672815766
c1 = 6235217214618484469008717065109058585860810027126999050539741461978786126300064219884646722757808536523766850480291000964963856026236813451563022630637528
c2 = 11968687437667021636457941077557698735979559596315355015261643918655719362366246657937192921814834456270616376603153881488026042955084056042773344426448580968726245676672896245296438903588066436834165402064132845092674100931069500643230951702318353312541552786636249326131049369846465301549915712690800690627
def mydecrypt(A,B):
ans=1
temp=gmpy2.powmod(-1,1,A)
#print(temp)
for i in range(B+1,A):
ans=(ans*gmpy2.invert(i,A))%A
return (ans*temp)%A
q = sympy.nextprime(mydecrypt(p,g))
n = p*q
phi2 = (p-1)*(q-1)
d = gmpy2.invert(e2,phi2)
m2 = pow(c2,d,n)
print(libnum.n2s(int(m2)))
#b'Here, e1=2, think about whether you can still use rsa to solve problems'然后是e和phi_n不互素，用普通方法求不出来，所以利用AMM算法
import random
import time
# About 3 seconds to run
def AMM(o, r, q):
start = time.time()
print('\n----------------------------------------------------------------------------------')
print('Start to run Adleman-Manders-Miller Root Extraction Method')
print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
g = GF(q)
o = g(o)
p = g(random.randint(1, q))
while p ^ ((q-1) // r) == 1:
p = g(random.randint(1, q))
print('[+] Find p:{}'.format(p))
t = 0
s = q - 1
while s % r == 0:
t += 1
s = s // r
print('[+] Find s:{}, t:{}'.format(s, t))
k = 1
while (k * s + 1) % r != 0:
k += 1
alp = (k * s + 1) // r
print('[+] Find alp:{}'.format(alp))
a = p ^ (r**(t-1) * s)
b = o ^ (r*alp - 1)
c = p ^ s
h = 1
for i in range(1, t):
d = b ^ (r^(t-1-i))
if d == 1:
j = 0
else:
print('[+] Calculating DLP...')
j = - discrete_log(d, a)
print('[+] Finish DLP...')
b = b * (c^r)^j
h = h * c^j
c = c^r
result = o^alp * h
end = time.time()
print("Finished in {} seconds.".format(end - start))
print('Find one solution: {}'.format(result))
return result
def findAllPRoot(p, e):
print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
start = time.time()
proot = set()
while len(proot) < e:
proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
end = time.time()
print("Finished in {} seconds.".format(end - start))
return proot
def findAllSolutions(mp, proot, cp, p):
print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
start = time.time()
all_mp = set()
for root in proot:
mp2 = mp * root % p
assert(pow(mp2, e, p) == cp)
all_mp.add(mp2)
end = time.time()
print("Finished in {} seconds.".format(end - start))
return all_mp
c = 6235217214618484469008717065109058585860810027126999050539741461978786126300064219884646722757808536523766850480291000964963856026236813451563022630637528
p = 8245512408967243371517759893329519667642119269153889262506106732818518415823601207067006537187243355250850586456796829524581895578331334132038513672846909
e = 2
cp = c % p
mp = AMM(cp, e, p)
p_proot = findAllPRoot(p, e)
mps = findAllSolutions(mp, p_proot, cp, p)
print(mps)
def check(m):
h = m.hex()
if len(h) & 1:
return False
if bytes.fromhex(h).startswith(b'HECTF'):
print(bytes.fromhex(h))
return True
else:
return False
# About 16 mins to run 0x1337^2 == 24196561 times CRT
start = time.time()
print('Start CRT...')
for mpp in mps:
solution = CRT_list([int(mpp)], [p])
if check(solution):
print(solution)
print(time.time() - start)
end = time.time()
print("Finished in {} seconds.".format(end - start))
#HECTF{Happy_120th_birthday_to_Hebei_Normal_University}ezrsa
题目
from Crypto.Util.number import *
from secret import flag
flag = b'xxx'
e = 114
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
t = getPrime(1024)
n = p * q * t
p_=pow(p,2,n)
q_=pow(q,2,n)
c = pow(m,e,n)
print('p_=',p_)
print('q_=',q_)
print('c=',c)
print('n=',n)
103250903193456504828487797156339600119426718627983781348818507950292820690249893916512022417900899107394861001239868070469917609264344248820063995415895904569850389089119540586899732656654237475843876867794510865961591835076374123380618390848608809256150058832564591055349379924805506351419667057604081135349
p_= 10660749010264526666955869622200514149424664070021154725214604278423033834800955315638637946982741577976025615843487738805576629855459529381681679497064453109727962183277768658053394103348827822686515016677449953958986089293779870089604784750116267441026319440135025236091029928565442799040007751858012409498271852333017388486644053877238274838173771344350870565886676055860728949042361028753924290647753862707042472944714140635484722345522648010064713004854479094986010632316750770118044301903260988074471243247031854872785324506292730778884664223412372663828159205320038546293395502275887356885181013870536857351801
q_= 24900409366873586425973971191854411152048453357438215578406168704445779543895031579176888535442469919297663892450230816720758414920791049333275007446412352293152157437672026001378469357187698312455020558413101033543700131403373834030395855212901673914686297701313223697181049265286011127188695284002470629178098454764536315245968458622929902214839704674718996340182311301099900271312644919770585429288043854743210617868761990329037081770477261306489047429460937057125193231432195877922731165870197358946683698077175950756482605399815830687563398277515452842563143685190688865084064679712177247354049377034394880941369
157798635503839469752446717651986470734467411686145972950533703965287076311312462611586472586638209970353426866979322760898287139085723568538059792571420311212101255127104335382081281902858421593497990417294935915897371187857482102407324837122921138869143815707149289272669578185431882034384720823115075903787
c= 946358882688806235743551077996671406469185038565566907261383734984318844703303437873183869084536703835433988817350857866089668970925835657856975155167500190428922521871327955274363186305180350899397478897928581580727458938934640786146518171503388507311655160765881370401217708135845031083189007308497775864484758699096082815479602777639307812516934937183952478316508418895341680335172973583094238147073379957772209947376051520041093030641369536800448737539973770258342422560893630082723217759837690008955748444973711508371077927468399703456466637348191192859278206925769696645636969358967735037470196395844215361527039288120664704552775460536654859848091685928057224735031528303041212702445718384890182474053295656578327780048497422707815820736647212902522526653039676698263673166412650104420869762547385554961873764933774143297622712766521201037469301912471740996998228799841957283759679784569638149555093498363791420486340
n= 1677924010415009671349677258549532467848510897335579570922114838282842960143799964694977371357046837674443739542407516581076865550606801686170400793463690366665534118961173768008603133641864003317727610676872685077700753537755254540591236871020140458419596610210236431401477173114522177145982007059709616618279936170223104755776796458682957656555154039384483954754660803554302451221585280396378564648495919069459351016010016636012245082009946238467068412198769348889950331295680906811430325690102055808865038151762131291269197341984605959088829226733422023970618165958725486675321766767430347929319621215891165857544847088373700410007500868721335483070938971597851859953792409442485301373327127595552457801719192824050415833073999094005750868115932130442747899994421453654008731830580286370350900523295205445599466666709544075950517531382971246869745425091317996973135364990272852701046046315136273893166361180330563013617843
脚本
from functools import reduce
import gmpy2
import libnum
e = 114
p_= 10660749010264526666955869622200514149424664070021154725214604278423033834800955315638637946982741577976025615843487738805576629855459529381681679497064453109727962183277768658053394103348827822686515016677449953958986089293779870089604784750116267441026319440135025236091029928565442799040007751858012409498271852333017388486644053877238274838173771344350870565886676055860728949042361028753924290647753862707042472944714140635484722345522648010064713004854479094986010632316750770118044301903260988074471243247031854872785324506292730778884664223412372663828159205320038546293395502275887356885181013870536857351801
q_= 24900409366873586425973971191854411152048453357438215578406168704445779543895031579176888535442469919297663892450230816720758414920791049333275007446412352293152157437672026001378469357187698312455020558413101033543700131403373834030395855212901673914686297701313223697181049265286011127188695284002470629178098454764536315245968458622929902214839704674718996340182311301099900271312644919770585429288043854743210617868761990329037081770477261306489047429460937057125193231432195877922731165870197358946683698077175950756482605399815830687563398277515452842563143685190688865084064679712177247354049377034394880941369
c= 946358882688806235743551077996671406469185038565566907261383734984318844703303437873183869084536703835433988817350857866089668970925835657856975155167500190428922521871327955274363186305180350899397478897928581580727458938934640786146518171503388507311655160765881370401217708135845031083189007308497775864484758699096082815479602777639307812516934937183952478316508418895341680335172973583094238147073379957772209947376051520041093030641369536800448737539973770258342422560893630082723217759837690008955748444973711508371077927468399703456466637348191192859278206925769696645636969358967735037470196395844215361527039288120664704552775460536654859848091685928057224735031528303041212702445718384890182474053295656578327780048497422707815820736647212902522526653039676698263673166412650104420869762547385554961873764933774143297622712766521201037469301912471740996998228799841957283759679784569638149555093498363791420486340
n= 1677924010415009671349677258549532467848510897335579570922114838282842960143799964694977371357046837674443739542407516581076865550606801686170400793463690366665534118961173768008603133641864003317727610676872685077700753537755254540591236871020140458419596610210236431401477173114522177145982007059709616618279936170223104755776796458682957656555154039384483954754660803554302451221585280396378564648495919069459351016010016636012245082009946238467068412198769348889950331295680906811430325690102055808865038151762131291269197341984605959088829226733422023970618165958725486675321766767430347929319621215891165857544847088373700410007500868721335483070938971597851859953792409442485301373327127595552457801719192824050415833073999094005750868115932130442747899994421453654008731830580286370350900523295205445599466666709544075950517531382971246869745425091317996973135364990272852701046046315136273893166361180330563013617843
p = 103250903193456504828487797156339600119426718627983781348818507950292820690249893916512022417900899107394861001239868070469917609264344248820063995415895904569850389089119540586899732656654237475843876867794510865961591835076374123380618390848608809256150058832564591055349379924805506351419667057604081135349
q = 157798635503839469752446717651986470734467411686145972950533703965287076311312462611586472586638209970353426866979322760898287139085723568538059792571420311212101255127104335382081281902858421593497990417294935915897371187857482102407324837122921138869143815707149289272669578185431882034384720823115075903787
t = n // (p*q)
print(t)
phi = (p-1)*(q-1)*(t-1)
u = gmpy2.gcd(e//6,phi)
print(u)
d = gmpy2.invert(e//6,phi)
m = pow(c,d,n)
m = gmpy2.iroot(m,6)[0]
print(libnum.n2s(int(m)))
#HECTF{Congratulation!!you_find_flag}matrix
题目直接给出了flag
HECTF{409bd7db0eb11a54e47eb5d0c9c371900eb11a54e47eb5d02e}mixture
题目
sage
p=235322474717419
a=0
b=8856682
k=
E = EllipticCurve(GF(p), [a, b])
P = E.random_point()
P.order()==p
Q=k*P
aes_key=k
print("P:",P)
print("Q:",Q)
#P=E(180571547161769,227820272156445)
#Q=E(76765539897460,69715189045993)python
from Crypto.Cipher import AES
import base64
aes_key = b'???'
def pad(text):
while len(text) % 16 != 0:
text += b' '
return text
def pad_key(key):
while len(key) % 16 != 0:
key += b' '
return key
aes = AES.new(pad_key(aes_key), AES.MODE_ECB)
plain_text = b'???'
enc_text = aes.encrypt(pad(plain_text))
enc_text_b64=base64.b64encode(enc_text)
print(enc_text_b64)
bXaw/g8fD7taMjlL/OyqUJluD6dZI5GkZb9RrE5GQk8=sage脚本
p=235322474717419
a=0
b=8856682
E = EllipticCurve(GF(p), [a, b])
P=E(180571547161769,227820272156445)
Q=E(76765539897460,69715189045993)
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
p_times_P = p*P_Qp
p_times_Q = p*Q_Qp
x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()
phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)
r = SmartAttack(P, Q, p)
print(r)
#152675955744921
key=b'152675955744921'
from Crypto.Util.number import *
from Crypto.Cipher import AES
import base64
def pad(text):
while len(text) % 16 != 0:
text += b' '
return text
def pad_key(key):
while len(key) % 16 != 0:
key += b' '
return key
aes = AES.new(pad_key(key), AES.MODE_ECB)
c='bXaw/g8fD7taMjlL/OyqUJluD6dZI5GkZb9RrE5GQk8='
c0=base64.b64decode(c)
print(c0)
flag=aes.decrypt(c0)
print(flag)
#HECTF{N0w_you_know_ecc_and_AES!}
