[Cryptohack] RSA (Manyprime, Salty)

Manyprime

문제

1개의 주요 인자를 사용하는 것은 분명 좋지 않은 생각이었기 때문에 대신 30개 이상을 사용해 보겠습니다. 💡인수 분해에 시간이 오래 걸리는 경우 인수 분해 알고리즘을 읽어보고 이 시나리오에 최적화된 알고리즘을 사용하는지 확인합니다.

풀이

일단 n의 값들이 여러 소수가 있는것을 확인할 수 있다.

https://rkdxowhd98.tistory.com/135

개인키 구하는 방법은

일단 n에서 나온 소수들을 p라고 하면

개인키는 (p1 -1)*(p2-1)*(p3-1).......(pn-1)이기에

이를 이용하여 평문값을 구하게 된다면

 

from Crypto.Util.number import long_to_bytes

n = 580642391898843192929563856870897799650883152718761762932292482252152591279871421569162037190419036435041797739880389529593674485555792234900969402019055601781662044515999210032698275981631376651117318677368742867687180140048715627160641771118040372573575479330830092989800730105573700557717146251860588802509310534792310748898504394966263819959963273509119791037525504422606634640173277598774814099540555569257179715908642917355365791447508751401889724095964924513196281345665480688029639999472649549163147599540142367575413885729653166517595719991872223011969856259344396899748662101941230745601719730556631637
e = 65537
ct = 320721490534624434149993723527322977960556510750628354856260732098109692581338409999983376131354918370047625150454728718467998870322344980985635149656977787964380651868131740312053755501594999166365821315043312308622388016666802478485476059625888033017198083472976011719998333985531756978678758897472845358167730221506573817798467100023754709109274265835201757369829744113233607359526441007577850111228850004361838028842815813724076511058179239339760639518034583306154826603816927757236549096339501503316601078891287408682099750164720032975016814187899399273719181407940397071512493967454225665490162619270814464
p= [9282105380008121879, 9303850685953812323, 9389357739583927789, 10336650220878499841, 10638241655447339831, 11282698189561966721, 11328768673634243077, 11403460639036243901, 11473665579512371723, 11492065299277279799, 11530534813954192171, 11665347949879312361, 12132158321859677597, 12834461276877415051, 12955403765595949597, 12973972336777979701, 13099895578757581201, 13572286589428162097, 14100640260554622013, 14178869592193599187, 14278240802299816541, 14523070016044624039, 14963354250199553339, 15364597561881860737, 15669758663523555763, 15824122791679574573, 15998365463074268941, 16656402470578844539, 16898740504023346457, 17138336856793050757, 17174065872156629921, 17281246625998849649]

pri = 1
for i in p:
    pri*=(i-1)

key=pow(e, -1, pri)
pt=pow(ct,key,n)
decrypted = long_to_bytes(pt)

print(decrypted)

플래그 값은 crypto{700_m4ny_5m4ll_f4c70r5}이다.

Salty

문제

가장 작은 지수가 가장 빠를 것입니다. 그렇죠?

풀이

from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes

e = 1
d = -1

while d == -1:
    p = getPrime(512)
    q = getPrime(512)
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)

n = p * q

flag = b"XXXXXXXXXXXXXXXXXXXXXXX"
pt = bytes_to_long(flag)
ct = pow(pt, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"ct = {ct}")

pt = pow(ct, d, n)
decrypted = long_to_bytes(pt)
assert decrypted == flag

output.txt

일단 n의 값이 소수이다.

그리고 공개키인 e의 값이 1이다.

https://stackoverflow.com/questions/17490282/why-is-this-commit-that-sets-the-rsa-public-exponent-to-1-problematic#:~:text=open%20Bob%27s%20padlock.-,Why%20is%201%20bad%3F,-1%20is%20a

https://stackoverflow.com/questions/17490282/why-is-this-commit-that-sets-the-rsa-public-exponent-to-1-problematic#:~:text=open%20Bob%27s%20padlock.-,Why%20is%201%20bad%3F,-1%20is%20a

해당 사이트에서 참고로 보면

공개키가 1이었을때 안좋은점은

일단 개인키를 구하게 되는 과정에서

d(개인키)*e(공개키) = 1 mod (p-1)*(q-1)

a mod b(a<b) 이면 a이고 (p-1)*(q-1)가 1보다 클때

d=1이다.

 

그리고 

c(암호문) = (p(평문) ^ e) mod n인데

e는 1이므로

c = p mod n 이게 되는데 

문제에선 n이 c보다 크기 때문에 p의 값도 보다 적다.

그러므로

c=p, 암호화가 되지 않은 상태이다.

from Crypto.Util.number import long_to_bytes

n = 110581795715958566206600392161360212579669637391437097703685154237017351570464767725324182051199901920318211290404777259728923614917211291562555864753005179326101890427669819834642007924406862482343614488768256951616086287044725034412802176312273081322195866046098595306261781788276570920467840172004530873767                                                                  
e = 1
ct = 44981230718212183604274785925793145442655465025264554046028251311164494127485



print(long_to_bytes(ct))

플래그 값은 crypto{saltstack_fell_for_this!}이다.