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*q and 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 = 2**1337
#x = (p * q) % 2**1337

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')
     >>> 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 = a*b*c*d % n

print("[+] signature :"+str(hex(sign))[:-1])



Flag: GLUG{fl4g_15_53rv3d_xD_E9644V2GG0}