sumPrimes revenge

Cryptography · CCS Club · Tulgaaaa

Problem

This challenge involves a combination of RSA encryption and matrix operations. Here's a breakdown:

1. Prime Number Generation:

   • 8 prime numbers (512-bit) are generated and stored in a list called primes.

   • A 2D matrix (key) of size 8x8 is created with smaller 64-bit prime numbers.

2. Encryption Process:

   • For each i in the range 8, the algorithm computes an encrypted value enc[i] by performing matrix multiplication between the key matrix and the primes list, then applying modulo mod.

3. RSA Setup:

   • A modulus n is computed as the product of all primes in primes.

   • The public exponent e is set to 65537.

   • The flag (flag.txt) is read, converted into a long integer m, and encrypted using RSA (c = m^e % n).

4. Outputs:

   • The out.txt file contains the matrix key, modulus mod, encryption values enc, and the ciphertext c.

chall.py

from Crypto.Util.number import getPrime,bytes_to_long

primes = [getPrime(512) for _ in range(8)]
key = [[getPrime(64) for _ in range(8)] for i in range(8)]
mod = getPrime(513)

enc = [0] * 8

for i in range(8):
    for j in range(8):
        enc[i] += key[i][j] * primes[j]
    enc[i] %= mod

n = 1
for i in primes:
    n *= i
e = 65537

flag = open('flag.txt','rb').read()
m = bytes_to_long(flag)

c = pow(m,e,n)

with open('out.txt','w') as f:
    f.write('key = '+ str(key) +'\n')
    f.write('mod = '+ str(mod) +'\n')
    f.write('enc = '+ str(enc) +'\n')
    f.write('c = '+str(c)+'\n')

out.txt

key = [[14548313727947012731, 14365678305891344743, 14116287213222539209, 16796440867716313577, 15517642725199306243, 13962694580144773627, 13042199650511143279, 17718633332885114807], [15338924806899003169, 13651984369374114571, 16689606728790196039, 9511070921146862147, 16699493780374396709, 10617098829645742901, 16936338434770389329, 15445520822285361719], [16562013489016274519, 15885434802093615037, 10449241410210432563, 10793803892086470449, 13933427863723912153, 15945004576563101069, 16307545550405365847, 12999487348241594287], [16353691444027253317, 12551777066867170381, 17424141484740094487, 16516673948103462197, 15606054408156296573, 15949121645403367301, 9664038368199755381, 11209420989612361211], [15581381059609577497, 10029661793793578071, 10069799342285119147, 15864089052462005167, 13076050248645757049, 12174656113389693191, 12919491411670339543, 15169930869665903621], [10821062805009977501, 13430188649464331377, 11231316062017764983, 18071149585020067253, 18257991768929779891, 16358314400876229707, 16040872121721692431, 12481309449696365653], [9998475578209425731, 9684591952267740413, 9774416648199042977, 13830821751893492791, 14385996567733580921, 12701598251603566313, 10340273280988222711, 9348329284716465863], [13740924026715058171, 18010535875170013547, 13178115572023734853, 11988658796219261801, 16441644704157480323, 13784005590274781951, 12048858110701227997, 10148302553739656807]]
mod = 15918526646934990276477490142143791308871214711630662193313214769987084139565280917536935367528530211079672113343823558604383698946962268009398066642866359
enc = [10982448089302515868171633112376307135369818639915614262223212649004035181222001851400482403468248281107861466967976406425097271486664265040793385639383206, 3836030378641196700149186184252119734660174434555387934083872350095532890857241722153073620217001729213131841343579126387912840203596518314353407761048567, 13340505570322198204744313743009314012834199912512962964149220285926795695337403008186433261265085830712949893098644127896505002493569971048525820761064142, 15252028245260045048345849251804783007745893227838530111655229094011087490567384088390097333699819632251840421314174407784786342429842049169637894917425873, 15612043850033397875360000057445534564366331066878385578742509327917295057501926654468627417575604083118577567873763823836839806701987338313479884673811042, 2996815934127478542306763465711478422788871772334825399289060458594696272884636225083715743923308301705264592183113437499668474043908049546052280121639618, 836857583230401128367188368916579375442657977134459061964445646667838429474689333755061458195508984428921557125324291647587754338569970187935877898561018, 3163891396614194079558843765317871409246932665301562520933456926313402688188126512279568563711963608932785652154759332242662193659673645550988157961295916]
c = 61910726220852772990403943925274293601133451757130770777431623654656258949385039950539563247103678534222238841048669629477908458597480839175419564722128838887598350297173237960558236008662373621344163746193366734736065045125004153438285925100754469439836018011135068822829254921991915180788771228984494493102838156887714377009925337940931601622022747107176944370228654218008350607808729775686984395488253541075267684636174004112289542587885130458545134328231791557225217762511243294292469864632986449146079735660493102205531110925982458850920260102863421310942605190051166391031957424663567028674759476610495242354100433676652361682832716609990825826660464369485163928775395150099519853848228848101631033041527522042542349635358950993085856682256996788856379047423094883251167903984935149353774870829731149203158678888176761870125556009558367475734865040635891161555913353962500478408405187677975061717879282283971061793253261937973759795924204462505050344565252129569484450858304418681294048154011551986925055695121402318955033225465557960659582194306993770378022642713170018640809076635830299051428204272810880745548304324744397426958635926091896790876135202224680273156962094743793193162779882468839917116166223908407104069179713

Solution

To recover the primes and decrypt the message:

1. Matrix Inversion:

• The matrix key is used in the encryption process. We use matrix inversion to recover the primes used in the encryption.

• The determinant of the key matrix is checked for invertibility modulo mod. If it's invertible, the inverse matrix is computed.

Equation

$$primes=key^{-1} ⋅enc\; (mod\;m)$$

1. Prime Recovery:

• The inverse of the key matrix is multiplied by the enc values (modulo mod) to recover the original primes.

1. RSA Decryption:

• Using the recovered primes, n and phi(n) are calculated.

• The private key d is computed using e and phi(n), and then the ciphertext c is decrypted using d to retrieve the flag.

solution.py

from sympy import Matrix
from Crypto.Util.number import inverse, long_to_bytes

# Key matrix and modulus (mod) initialization
key_matrix_data = [
    [14548313727947012731, 14365678305891344743, 14116287213222539209, 16796440867716313577, 
     15517642725199306243, 13962694580144773627, 13042199650511143279, 17718633332885114807],
    [15338924806899003169, 13651984369374114571, 16689606728790196039, 9511070921146862147, 
     16699493780374396709, 10617098829645742901, 16936338434770389329, 15445520822285361719],
    [16562013489016274519, 15885434802093615037, 10449241410210432563, 10793803892086470449, 
     13933427863723912153, 15945004576563101069, 16307545550405365847, 12999487348241594287],
    [16353691444027253317, 12551777066867170381, 17424141484740094487, 16516673948103462197, 
     15606054408156296573, 15949121645403367301, 9664038368199755381, 11209420989612361211],
    [15581381059609577497, 10029661793793578071, 10069799342285119147, 15864089052462005167, 
     13076050248645757049, 12174656113389693191, 12919491411670339543, 15169930869665903621],
    [10821062805009977501, 13430188649464331377, 11231316062017764983, 18071149585020067253, 
     18257991768929779891, 16358314400876229707, 16040872121721692431, 12481309449696365653],
    [9998475578209425731, 9684591952267740413, 9774416648199042977, 13830821751893492791, 
     14385996567733580921, 12701598251603566313, 10340273280988222711, 9348329284716465863],
    [13740924026715058171, 18010535875170013547, 13178115572023734853, 11988658796219261801, 
     16441644704157480323, 13784005590274781951, 12048858110701227997, 10148302553739656807]
]

mod = 15918526646934990276477490142143791308871214711630662193313214769987084139565280917536935367528530211079672113343823558604383698946962268009398066642866359

# Encrypted values
enc_data = [
    10982448089302515868171633112376307135369818639915614262223212649004035181222001851400482403468248281107861466967976406425097271486664265040793385639383206,
    3836030378641196700149186184252119734660174434555387934083872350095532890857241722153073620217001729213131841343579126387912840203596518314353407761048567,
    13340505570322198204744313743009314012834199912512962964149220285926795695337403008186433261265085830712949893098644127896505002493569971048525820761064142,
    15252028245260045048345849251804783007745893227838530111655229094011087490567384088390097333699819632251840421314174407784786342429842049169637894917425873,
    15612043850033397875360000057445534564366331066878385578742509327917295057501926654468627417575604083118577567873763823836839806701987338313479884673811042,
    2996815934127478542306763465711478422788871772334825399289060458594696272884636225083715743923308301705264592183113437499668474043908049546052280121639618,
    836857583230401128367188368916579375442657977134459061964445646667838429474689333755061458195508984428921557125324291647587754338569970187935877898561018,
    3163891396614194079558843765317871409246932665301562520933456926313402688188126512279568563711963608932785652154759332242662193659673645550988157961295916
]

# Convert the key matrix into a sympy Matrix for easier operations
key_matrix = Matrix(key_matrix_data)

# Check if the key matrix is invertible modulo 'mod'
if key_matrix.det() % mod != 0:
    # Calculate the modular inverse of the key matrix
    key_inv = key_matrix.inv_mod(mod)
    
    # Convert encrypted data to a sympy Matrix
    enc_matrix = Matrix(enc_data)
    
    # Recover the primes by multiplying the inverse key matrix with the encrypted matrix
    primes_matrix = key_inv * enc_matrix % mod

    # Convert the result to a list of primes
    primes = primes_matrix.T.tolist()[0]
    print("Recovered primes:", primes)
else:
    print("The matrix is not invertible modulo 'mod'.")
    exit()

# Calculate n as the product of all recovered primes
n = 1
for prime in primes:
    n *= prime
print("N:", n)

# Calculate Euler's Totient function phi(n)
phi_n = 1
for prime in primes:
    phi_n *= (prime - 1)
print("Calculated phi(n):", phi_n)

# Ensure phi_n is treated as a Python integer
phi_n = int(phi_n)

# Public exponent
e = 65537

# Calculate the private key 'd' using the modular inverse of e modulo phi(n)
d = inverse(e, phi_n)
print("Private key:", d)

# Ciphertext (c) to be decrypted
c = 61910726220852772990403943925274293601133451757130770777431623654656258949385039950539563247103678534222238841048669629477908458597480839175419564722128838887598350297173237960558236008662373621344163746193366734736065045125004153438285925100754469439836018011135068822829254921991915180788771228984494493102838156887714377009925337940931601622022747107176944370228654218008350607808729775686984395488253541075267684636174004112289542587885130458545134328231791557225217762511243294292469864632986449146079735660493102205531110925982458850920260102863421310942605190051166391031957424663567028674759476610495242354100433676652361682832716609990825826660464369485163928775395150099519853848228848101631033041527522042542349635358950993085856682256996788856379047423094883251167903984935149353774870829731149203158678888176761870125556009558367475734865040635891161555913353962500478408405187677975061717879282283971061793253261937973759795924204462505050344565252129569484450858304418681294048154011551986925055695121402318955033225465557960659582194306993770378022642713170018640809076635830299051428204272810880745548304324744397426958635926091896790876135202224680273156962094743793193162779882468839917116166223908407104069179713

# Decrypt the ciphertext 'c' using the private key 'd' and modulus 'n'
m = pow(c, d, n)

# Convert the decrypted message to a readable flag
flag = long_to_bytes(m).decode()
print(f"The flag is: {flag}")