RSA tutorial

Cryptography · Mazala · Superior

Problem

1. Source code

from Crypto.Util.number import getPrime
from Crypto.Util.number import bytes_to_long as b2l

from secret import flag


p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65536

print(p)
print(q)
print(pow(b2l(flag), e, n))

1. Output

79565304973649738046890929641550086406229645142982116252431882783628570446741
104895446414749804110599905404014579424417002368568255490767700901764221803853
4540356813631057206329938934275504497042552943607683102015080934372428231345551929844529058302190596843384780497234278626232722159254772622184794355722055

When I tried to decode it with simple RSA steps, the e wasn't invertible for the phi (gcd(e,phi) > 1). In RSA, the public exponent 𝑒 must be chosen such that it is coprime to 𝜑 ( 𝑛 ) (Euler's totient function of 𝑛). This ensures that 𝑒 has a modular inverse, which is necessary for computing the private exponent 𝑑 using the modular inverse:

$$d≡e ^{−1}\space mod\spaceφ(n)$$

from Crypto.Util.number import long_to_bytes
from math import gcd

# Given values
p = 79565304973649738046890929641550086406229645142982116252431882783628570446741
q = 104895446414749804110599905404014579424417002368568255490767700901764221803853
n = p * q
e = 65536
c = 4540356813631057206329938934275504497042552943607683102015080934372428231345551929844529058302190596843384780497234278626232722159254772622184794355722055

# Compute phi(n)
phi = (p - 1) * (q - 1)

# Compute d (modular inverse of e mod phi)
if gcd(e, phi) != 1:
    print("e and phi(n) are not coprime. Cannot compute d directly.")
else:
    d = pow(e, -1, phi)  # Compute modular inverse

    # Decrypt ciphertext
    m = pow(c, d, n)
    
    # Convert to bytes and print flag
    flag = long_to_bytes(m)
    print(flag.decode())

Reduce the Problem

• Divide e and ϕ(n) by g:

  • e′=e/g

  • ϕ′=ϕ(n)/g

• Compute the modular inverse of e′ modulo ϕ′:

  • d′=e′^(-1)mod  ϕ′

• Find gg-th Roots Modulo pp and qq:

  • Use the nthroot_mod function to compute:

    mp=nthroot_mod(c′,g,p) & mq=nthroot_mod(c′,g,q)

• Combine Results Using CRT:

  • Use the Chinese Remainder Theorem (CRT) to combine mp​ and mq:

    m=crt([p,q],[mp,mq])[0]

By reducing e and ϕ ( n ), we create new values e ′ , ϕ ′ , and c ′ that allow us to solve the problem despite the non-coprime issue.

What does nthroot_mod do?

$$m^{e}≡c\space mod \space (p \space OR \space q)$$

It Checks if a Solution Exists for flag and Solves.

• Once m_p​ (solution modulo p) and m_q(solution modulo q) are found, the Chinese Remainder Theorem (CRT) combines them to get m.

Chinese Remainder Theorem

Combining m_p and m_q into one solution m.

Example

CRT

Example

Let’s say:

• p=7, q=11, n=77.

• e=16, c=23.

1. Compute ϕ(n)=(7−1)(11−1)=60.

2. Compute g=gcd⁡(16,60)=4.

3. Reduce e′=16/4=4, ϕ′=60/4=15

4. Compute d′=4^{-1}mod  15=4(since 4⋅4=16≡1mod  15).

5. Compute c′=23^{4}mod  77.

6. Compute mp=nthroot_mod(c′,4,7) and mq=nthroot_mod(c′,4,11).

7. Combine mp​ and mq​ using CRT to get m mod  77.

8. Convert m to bytes to recover the flag.

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from math import gcd
from sympy.ntheory.residue_ntheory import nthroot_mod
from sympy.ntheory.modular import crt

# Given values
p = 79565304973649738046890929641550086406229645142982116252431882783628570446741
q = 104895446414749804110599905404014579424417002368568255490767700901764221803853
n = p * q
e = 65536
c = 4540356813631057206329938934275504497042552943607683102015080934372428231345551929844529058302190596843384780497234278626232722159254772622184794355722055

# Compute phi(n)
phi = (p - 1) * (q - 1)

# Compute gcd(e, phi(n))
g = gcd(e, phi)

# Reduce the problem
e_prime = e // g
phi_prime = phi // g
d_prime = pow(e_prime, -1, phi_prime)

# Compute c' = c^d_prime mod n
c_prime = pow(c, d_prime, n)

# Compute g-th root modulo p and q
m_p = nthroot_mod(c_prime, g, p)
m_q = nthroot_mod(c_prime, g, q)

# Combine using CRT
m = crt([p, q], [m_p, m_q])[0]

flag = long_to_bytes(m)
print(flag.decode())

Flag: mazala{m0dul4r_Square_r00t}