#
FoobarCTF 2022 Crypto writeup
Crypto Challenge Writeup:
Challenge name : babyRSA
Chall file:
from Crypto.Util.number import *
flag = b"GLUG{REDACTED*****}"
p,q = getPrime(1024),getPrime(1024)
N = p * p * q
e = 0x10001
phi = p * (p-1) * (q-1)
d = inverse(e, phi)
m = bytes_to_long(flag)
c = pow(m, e, N)
x = (p * q) % 2**1337
print("N = ".format(N))
print("e = ".format(e))
print("c = ".format(c))
print("x = ".format(x))
Output:
n = 1862871955255773903015555578091085043612025268407412897302905832620896712025201897312995829553474175135190551094563297876709351981276817349813398258043249300488609960386863268339518629692154323824453110186146306010963662305861966120667538777155455159739296406335349293672176307554123622232777012514054848468930806904131960465772223360786428469291726206998215694107790773315484457273571590016126063412114288248673526367649685670511041861887410170073444517108820725764459594983621584194625078860139865684193327199600381598274487395551130322199129914933955585468166778481081659128795093350101559570647565453632652791437814144529373413332850183156364883440821142181920071845112312902857853441611155344240891225716213626273473705542052460314619334514865005147194913072907414167355710711865745558531586223316679842899089181138483727879743039536045989818393934040285179823266327242407657963285329559029697302427490888420166241313849
e = 65537
c = 1685694402585229399699468599208783295407454759540674091938668979180243955130403003626211101984152370742736211045525984316632749971433168883287383299645245330127391420455774558657472055645730820864774304037508627351147925419052692787660808285791081689100274893400562022977620012146667522246835047767037511180880573701661280754732681902586578745711467339809022597202965059918776095504683478094646033528621093492050170604923556981705249683385011326853931024569288136526731192525998067880512627462749891475398515167819479784915263417194960798808797837840025469943383251121317715074631999894894231902525637411310950615560785726619602252227413380519591407687610748182270093352374680299466331526526996398038485430377656603679759082275850216111391654800091554055155641275315162407470247790599682283615245968236163550075270783003654577185666636437073672252763233925941850862748625937949315172143452560017994833819344332542074129579377
x = 2121556837489323393830117506636485275262970334096973330971400998541061434248491797293936443932014206079161678574395103482971809478068410664024927982076981551873713173206728190862242836376526528390743086543538755826674529105687167529814363908630371800401390496769993532681737968141810119668479989445768189718574035122948285385181466041802061542422715767093719363420978170488364616302423479875250423116981
- This is an normal RSA challenge with extra value x =
p*q % 2**1337,this value help us to find the factors p,q. - Here n is of
p*p*qand my solution lies on the below equations.
- once we retrieved p,we can easily decrypt the flag.
Script:
from gmpy import *
from Crypto.Util.number import *
n = 1862871955255773903015555578091085043612025268407412897302905832620896712025201897312995829553474175135190551094563297876709351981276817349813398258043249300488609960386863268339518629692154323824453110186146306010963662305861966120667538777155455159739296406335349293672176307554123622232777012514054848468930806904131960465772223360786428469291726206998215694107790773315484457273571590016126063412114288248673526367649685670511041861887410170073444517108820725764459594983621584194625078860139865684193327199600381598274487395551130322199129914933955585468166778481081659128795093350101559570647565453632652791437814144529373413332850183156364883440821142181920071845112312902857853441611155344240891225716213626273473705542052460314619334514865005147194913072907414167355710711865745558531586223316679842899089181138483727879743039536045989818393934040285179823266327242407657963285329559029697302427490888420166241313849
e = 65537
c = 1685694402585229399699468599208783295407454759540674091938668979180243955130403003626211101984152370742736211045525984316632749971433168883287383299645245330127391420455774558657472055645730820864774304037508627351147925419052692787660808285791081689100274893400562022977620012146667522246835047767037511180880573701661280754732681902586578745711467339809022597202965059918776095504683478094646033528621093492050170604923556981705249683385011326853931024569288136526731192525998067880512627462749891475398515167819479784915263417194960798808797837840025469943383251121317715074631999894894231902525637411310950615560785726619602252227413380519591407687610748182270093352374680299466331526526996398038485430377656603679759082275850216111391654800091554055155641275315162407470247790599682283615245968236163550075270783003654577185666636437073672252763233925941850862748625937949315172143452560017994833819344332542074129579377
x = 2121556837489323393830117506636485275262970334096973330971400998541061434248491797293936443932014206079161678574395103482971809478068410664024927982076981551873713173206728190862242836376526528390743086543538755826674529105687167529814363908630371800401390496769993532681737968141810119668479989445768189718574035122948285385181466041802061542422715767093719363420978170488364616302423479875250423116981
N = 21337
#x = (p * q) % 21337
d = inverse(x,2**1337)
p = d * n % N
#print(p)
p = 139387518986826536509144049219128127758120617287987945818827279314602564142349682985769656023092456357155296439247793458178075113354440414475867450674127064081966333660528171321853175654236647699883371985059454473707508426015442275267745798448560385920139928240405884255349873045306634707812262346541658507253
p_p = p*p
q = n // p_p
phi = p * (p-1)*(q-1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))
Flag : GLUG{ded1cati0n_i5_4_tal3n7_4ll_0n_it5_0wn}
Challenge name : Daredevil's server
Description:
Matt-Murdock is one my favourite character from marvel universe.
I found his msg signing server can you help me to retrive his secret.
- We were given with an netcat connection
nc chall.nitdgplug.org 30093 - Connecting to the server gave us the below options.
- I went on with the value E to know the encryption function!
Output of encryption function:
TOKEN = b'd4r3d3v!l'
def chall():
s = Sign()
while True:
choice = input("> ").rstrip()
if choice == 'P':
print("\nN : {}".format(hex(s.n)))
print("\ne : {}".format(hex(s.e)))
elif choice == 'S':
try:
msg = bytes.fromhex(input('msg to sign : '))
if TOKEN in msg:
print('[!] NOT ALLOWED')
else:
m = bytes_to_long(msg)
print("\nsignature : {}".format(hex(s.sign(m)))) #pow(msg,d,n)
print('\n')
except:
print('\n[!] ERROR (invalid input)')
elif choice == 'V':
try:
msg = bytes.fromhex(input("msg : "))
m = bytes_to_long(msg)
signature = int(input("signature : "),16)
if m < 0 or m > s.n:
print('[!] ERROR')
if s.verify(m, signature): #pow(sign, e, n) == msg
if long_to_bytes(m) == TOKEN:
print(SECRET)
else:
print('\n[+] Valid signature')
else:
print('\n[!]Invalid signature')
except:
print('\n[!] ERROR(invalid input)')
elif choice == 'Q':
print('OK BYE :)')
exit(0)
else:
print('\n[*] SEE OPTIONS')
- Ok this is an classic RSA blinding attack,
- You can learn more about this here https://masterpessimistaa.wordpress.com/2017/07/10/blinding-attack-on-rsa-digital-signatures/
- We have to sign the message with the value
d4r3d3v!l,where we not directly allowed to sign it. - First thing i did was to convert the
d4r3d3v!lvalue to long.
>>> bytes_to_long("d4r3d3v!l")
1848453546913725555052L
- Hence the output is composite,i went on with factorization and signing. (You can also solve this with blinding factor)
{2: 2, 175143733: 1, 2638480856911: 1}
- The above is the output for factorizing the TOKEN value in long.
- The solution goes on by signing each individual integers and assign their signature in a,b,c,d.
s(m) = a*b*c*d % n
- we can get the value of n by sending the key P to the server which gives us publickey (n,e).
- Once we calculated the signature,we can send hex value of m and s(m) to retrieve the flag.
Solution:
from sympy import factorint
from Crypto.Util.number import *
TOKEN = 'd4r3d3v!l'
#1848453546913725555052
# composite number
t = str(1848453546913725555052)
#factorization
# {2: 2, 175143733: 1, 2638480856911: 1}
print(long_to_bytes(2).encode("hex"))
# send 2 times
print(long_to_bytes(175143733).encode("hex"))
print(long_to_bytes(2638480856911).encode("hex"))
a= 0x1c5db869a64fc002c8e05674ee4a2bbf9224898bb739026227631384760d8f1003749625766177219aff81f5c71f52a80be1467e494e03abf7f86edfd6d94b07d45cd8ad67866e62ada1a27c06b3d168e13a4aa47800019ee861613a22429a95da14cace342c0fcac16d94bbcddb15197a2d3ce5bc6a45b50bdbeeee2db317c5
b= 0x1c5db869a64fc002c8e05674ee4a2bbf9224898bb739026227631384760d8f1003749625766177219aff81f5c71f52a80be1467e494e03abf7f86edfd6d94b07d45cd8ad67866e62ada1a27c06b3d168e13a4aa47800019ee861613a22429a95da14cace342c0fcac16d94bbcddb15197a2d3ce5bc6a45b50bdbeeee2db317c5
c = 0x4be8e2be903156548ce7557137aff5012337a44337d1e4ac5d998a10c3a9522636e7004bc5defe9df50948fae5dc6252e9853559647283fc191ed8e291e53493f8eba8ecfb65ca85a2782355841170e9f44b6317d173a55865f5e79cd63621122a75d46b49a68bfd04dbc67737e08c07f7fddf4ed4d8c89e11e5efaf879d01dd
d = 0x4a02d85926feb2db2281335ac468ce3fc1824881610e052d2ad233b0a2cbce224beaf3c7d77eb82441d37e2253cf07b0c6cad19b7b1168766b3c3ab8ed3408726a22a07eac33c5a8144658c102b8e774d0ac404173af90997477300385b9b6e002b7858cd299c351062172c526c01d2dc287b37bfc81eb5972330163aa0e073b
n = 0x9f1a727af5b7785285056b713468039e2f109d2887154b52dbe7c182e2c3a0115e1f361ec9cf6f24b7f19e2da7b0d08a489591d106c5c4c8db07390d8d69b5eee31461a0b11b5383fdf42cdbe67c8385858aa3b7689cf8a0dd63387748c03b9918a5f0157d74fc5f02e14bf32561ded9f962b9ce8b0d6d748ab3af671321d5d3
print("[+] Hex message : "+TOKEN.encode("hex"))
sign = abc*d % n
print("[+] signature :"+str(hex(sign))[:-1])
- Flag:
GLUG{fl4g_15_53rv3d_xD_E9644V2GG0}