寧波市第八屆網絡安全大賽 – Crypto – WriteUp

Three-prime RSA

task

import gmpy2
from Crypto.Util.number import *from secret import flagp = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
random_num = getPrime(28)
D = ((p + q + r) * random_num) % n
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1)*(r-1))
m = bytes_to_long(flag)
c = pow(m,e,n)
m = long_to_bytes(pow(c,d,n))
print(f'n = {n}')
print(f"c = {c}")
print(f'e = {e}')
print(f'D = {D}')
print(f'r_cubed = {r**3}')
#n = 1797464363937803574178366635456301143459899987065195402238965688630854838574693129181564969286593529451541315147307698518248164419022745845149367101229289853511043305315113437055463741220310201972952525360384401292742908307617104187282410207011086837143526628825853819176582961596474273863005403315519262514987973727415369569624782351302222624317374956732149792365793683939133163240811987601690584296532495636077337007058250072691770687934895196018165482285074087
#c = 334735157214244327583157709091138850291255337497549444727968382625552814752420162774889355435597239850801444255501536062808665271447071394852127129645007823666189408974242614895090473463544656321304260276646862158621490436794225048527190465633048027777929676430778187663379548454777508032938086766087680923109105263450337252432956611495124284902807201570660674571972801630769083508865730870372239801449723990206104741555109361529711228109643651552666016767418334
#e = 65537
#D = 9293355851986591081591521098987501845963630839756264676294309115767555607188666083544593308349243222711109037704690481694680479223233813272567476445999227440933917
#r_cubed = 1733587395810445026263077101568701832386760527292029091732688691632302263295044364907002644024851393182111273947443724875261726589148427101911382909265190107241975414590360694235677890202731336061400362438326929279259311961356096293232720988325040307146370196619971302229486629240899410846744560517421971004381582157573816044985536221126650590038003165043945929284756476920639015271502102636205225479117479735091470661892665348612065863317686928100311559126824531

exp

from Crypto.Util.number import *
from gmpy2 import irootn = 1797464363937803574178366635456301143459899987065195402238965688630854838574693129181564969286593529451541315147307698518248164419022745845149367101229289853511043305315113437055463741220310201972952525360384401292742908307617104187282410207011086837143526628825853819176582961596474273863005403315519262514987973727415369569624782351302222624317374956732149792365793683939133163240811987601690584296532495636077337007058250072691770687934895196018165482285074087
c = 334735157214244327583157709091138850291255337497549444727968382625552814752420162774889355435597239850801444255501536062808665271447071394852127129645007823666189408974242614895090473463544656321304260276646862158621490436794225048527190465633048027777929676430778187663379548454777508032938086766087680923109105263450337252432956611495124284902807201570660674571972801630769083508865730870372239801449723990206104741555109361529711228109643651552666016767418334
e = 65537
D = 9293355851986591081591521098987501845963630839756264676294309115767555607188666083544593308349243222711109037704690481694680479223233813272567476445999227440933917
r_cubed = 1733587395810445026263077101568701832386760527292029091732688691632302263295044364907002644024851393182111273947443724875261726589148427101911382909265190107241975414590360694235677890202731336061400362438326929279259311961356096293232720988325040307146370196619971302229486629240899410846744560517421971004381582157573816044985536221126650590038003165043945929284756476920639015271502102636205225479117479735091470661892665348612065863317686928100311559126824531
r = iroot(r_cubed, 3)[0]
phi = r - 1
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, r)))
# b'DASCTF{5521a971-9bed-11ef-bfda-14ac6024b6a8}'

earsa_6

task

from sage.all import *
# from secret import flag
flag = b'flag{this_is_a_test_flag_lalala~~~}'
from Crypto.Util.number import *p = next_prime(ZZ.random_element(2 ** 512))
q = next_prime(ZZ.random_element(2 ** 512))m = bytes_to_long(flag) 
n = p * q
print(f"p = {p}")
print(f"q = {q}")
phi_n = (p+1)*(q+1)e = ZZ.random_element(phi_n)
while gcd(e, phi_n) != 1:e = ZZ.random_element(phi_n)d = inverse_mod(e, phi_n)c = pow(m, e, n) # c = (mod(m ** 2, n) * power_mod(e, 2, n)) % nprint(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
# "n = 103290940605767097772547367608381852550255311740089066062370678669736584831966972390296508499564302740251039905216525828381026059914694968711341442279592794179645755109637276941753470671672492643863307674183032056063497595618158607559032052302672569850017317721983409928424751468273419269585837187792579680441"
# "e = 4153390199995099394559502199356876987641001700181798065618463687883377896662802735692294514592974848815256220220567520414785101204978084883084168277609953983317089255372031928914225544973810429741972241310760306291217083076283386527880407979441234845945200062237779009000326020732264366320464844100039711500073849140628815801055506193561725597087896534906132971553150940778821878782222775892376719019037312704365897736892636528690951714686191932520762021674718730306167017168655476030445903413293206451445350127989832224321862119769332948547212450481322973363484001293075189230923276019258476580885163774258459928467"
# "c = 100933162705070380579705358896231615705264597351634019368382319632347917048149032133717183415739431564428093428992978229723659108455837366449426780119900838833128284699424510443364272415543344735540591444863458191423494866766098524960586274161507718151409519858841560317649453200969001613445259145496747256869"

analysis

• 根據題目描述信息搜集到相關的題型，先前也沒有見過，但是有類似的題型以及攻擊策略。
• 再利用現有的attack分解n之后，我們進行下一步的求解。這里前面按照原有的題目，發現這里的e并非題目腳本生成的。這里和賽事方進行了很長時間的溝通，按照原有的思路，我會進行有限域內開放求解m但是這里并沒有解，知道比賽題目難度降低，分解n之后直接RSA解密即可。

exp

from Crypto.Util.number import *
from sage.all import *def attack(N, e):"""Recovers the prime factors of a modulus and the private exponent if two prime factors share most significant bits:param N: the modulus:param e: the public exponent:return: a tuple containing the prime factors and the private exponent, or None if the private exponent was not found"""PR = PolynomialRing(ZZ, 'x')x = PR.gen()convergents = continued_fraction(ZZ(e) / ZZ((N - 1) ** 2)).convergents()for c in convergents:k = c.numerator()d = c.denominator()try:f = x ** 2 - x * (N ** 2 + 1 - int((e * d - 1) / k)) + N ** 2if f.discriminant() > 0:root = f.roots()p2 = root[0][0]; q2 = root[1][0]if is_square(p2) and is_square(q2):p = isqrt(p2); q = isqrt(q2)if p * q == N:return p, q, dexcept:continuereturn Nonen = 103290940605767097772547367608381852550255311740089066062370678669736584831966972390296508499564302740251039905216525828381026059914694968711341442279592794179645755109637276941753470671672492643863307674183032056063497595618158607559032052302672569850017317721983409928424751468273419269585837187792579680441
e = 4153390199995099394559502199356876987641001700181798065618463687883377896662802735692294514592974848815256220220567520414785101204978084883084168277609953983317089255372031928914225544973810429741972241310760306291217083076283386527880407979441234845945200062237779009000326020732264366320464844100039711500073849140628815801055506193561725597087896534906132971553150940778821878782222775892376719019037312704365897736892636528690951714686191932520762021674718730306167017168655476030445903413293206451445350127989832224321862119769332948547212450481322973363484001293075189230923276019258476580885163774258459928467
c = 100933162705070380579705358896231615705264597351634019368382319632347917048149032133717183415739431564428093428992978229723659108455837366449426780119900838833128284699424510443364272415543344735540591444863458191423494866766098524960586274161507718151409519858841560317649453200969001613445259145496747256869# print(attack(n, e))
p, q, d = attack(n, e)
assert n % p == 0
flag = long_to_bytes(int(pow(c, d, n)))
print(flag)

寫在最后

• 第一題不知道是出題人故意而為之還是沒有考慮到flag過短導致可以直接開方r下轉素數進行求解。

• 第二題未修正之前有點看不懂加密，修正的時候說是為了降低難度，后續針對于賽事方的數據進行了測試，感覺很…

  from sage.all import *
  from Crypto.Util.number import *# 提交正確的flag
  flag = b'DASCTF{5e1eddfb-dda2-11ed-8d28-ac675d417bad}'
  m = bytes_to_long(flag)# 題目附件給出的n
  n = 103290940605767097772547367608381852550255311740089066062370678669736584831966972390296508499564302740251039905216525828381026059914694968711341442279592794179645755109637276941753470671672492643863307674183032056063497595618158607559032052302672569850017317721983409928424751468273419269585837187792579680441# 題目附件給出的e
  e = 4153390199995099394559502199356876987641001700181798065618463687883377896662802735692294514592974848815256220220567520414785101204978084883084168277609953983317089255372031928914225544973810429741972241310760306291217083076283386527880407979441234845945200062237779009000326020732264366320464844100039711500073849140628815801055506193561725597087896534906132971553150940778821878782222775892376719019037312704365897736892636528690951714686191932520762021674718730306167017168655476030445903413293206451445350127989832224321862119769332948547212450481322973363484001293075189230923276019258476580885163774258459928467# 題目附件給出的c
  c = 100933162705070380579705358896231615705264597351634019368382319632347917048149032133717183415739431564428093428992978229723659108455837366449426780119900838833128284699424510443364272415543344735540591444863458191423494866766098524960586274161507718151409519858841560317649453200969001613445259145496747256869
  # print(pow(m, e, n) == c1) True# 未降低難度前給出的加密流程
  """😀😀😀😀😀"""
  c2 = (mod(m ** 2, n) * power_mod(e, 2, n)) % n
  print(c2 == c) # False