Blog | G5 Cyber Security

RSA Decryption with Phi(n)

G5 Cyber Security

TL;DR

Yes, you can decrypt RSA if you know phi(n) (Euler’s totient function of n), even without the private key. This is because phi(n) allows you to calculate the private exponent ‘d’. However, this is rarely practical as finding phi(n) is usually as hard as factoring n.

How it Works

RSA relies on the mathematical relationship between the public key (e, n), the private key (d, n), and the message (M). The core equation is:

M = Cd mod n

Where:

If you know phi(n), you can calculate ‘d’ using the following:

d = e-1 mod phi(n)

‘e-1 mod phi(n)’ means finding the modular multiplicative inverse of ‘e’ modulo phi(n). This is a number that, when multiplied by ‘e’, leaves a remainder of 1 when divided by phi(n).

Steps to Decrypt RSA with Phi(n)

  1. Find phi(n): If you know the prime factors p and q of n (where n = p * q), calculate phi(n) as:
    2. phi(n) = (p - 1) * (q - 1)
  2. Calculate the Private Exponent (d): Use an extended Euclidean algorithm or a modular inverse calculator to find ‘d’. Many programming languages have built-in functions for this.
from math import gcd

def modInverse(e, phi):
  m0 = phi
  y = 0
  x = 1

  if (gcd(e, m0) != 1):
    return -1 # Inverse doesn't exist

  while (e > 1):
    q = e // m0
    t = m0
    m0 = e % m0
    e = t
    t = y
    y = x - q * y
    x = t

  if (x < 0):
    x = x + phi

  return x

e = 65537 # Example public exponent
p = 61
q = 53
n = p * q
phi_n = (p-1) * (q-1)
d = modInverse(e, phi_n)
print("Private Exponent (d):", d)
  • Decrypt the Ciphertext: Once you have 'd', decrypt the ciphertext C using the RSA equation:
    • M = Cd mod n
    C = 12345 # Example Ciphertext
M = pow(C, d, n)
print("Decrypted Message (M):", M)

    Important Considerations

    Exit mobile version