# sumPrimes revenge

## 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

```python
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)
$$

2. **Prime Recovery**:

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

3. **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

```python
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}")
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zwique.gitbook.io/zwique_notes/writeups/random-ctf-writeup/local/sumprimes-revenge.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.