Decryption of RSA

Question

How can we decrypt an RSA message if we only have the public key?

For example, Message: 21556870,12228498 Public Key: (e = 15852553, n = 44331583)

I know that these formulas exist:

gcd(e, φ(n)) = 1
ed mod φ(n) = 1

so my idea was that i could put the value of e in the first formula, then derive d that is a part of the private key. However, I don't think it's mathematically possible to find φ(n) here. So, how else can I decrypt an RSA message with only the public key?

Answer 1

"How can we decrypt an RSA message if we only have the public key?"

Well, we have to find the private key from the public key. This should be too hard to do in practical situations in general, since RSA algorithms are time-tested field-tested security algorithms, and people are using it carefully with long-enough bits in general.

However, the exercise assigned to you is designed for you to practice RSA algorithm. The numbers used are not large enough to prevent you from obtaining the private key given the public key. You should be able to do all the computations by simple programming using your favorite programming language and computer.

Try harder before looking at the answer below.

---

Public Key: (e = 15852553, n = 44331583)

Let us factor n. Here is a simple Python program.

def factor(n):
    for i in range(2, n-1):
        if n % i == 0:
            print(str(n) + " = " + str(i) + " * " + str(n // i))
            break

Running factor(44331583), we obtain that 44331583 = 5003 * 8861.

So φ(n) = (5003 - 1) * (8861 - 1) = 44317720

---

Find the inverse of e modulo φ(n). Here is a simple Python program.

def inverse(e, phi):
    """ display the inverse of e modulo phi """

    for i in range(1, phi):
        if i * e % phi == 1:
            print(str(e) + " * " + str(i) + " = 1 (mod " + str(phi) + ")")
            break

Running inverse(15852553, 44317720), we obtain that 15852553 * 1951097 = 1 (mod 44317720). That is, the inverse of e modulo φ(n) is d=1951097.

So, the corresponding private key is (d = 1951097, n = 44331583).

---

Compute m**d (mod n) to decrypt an RSA message (a.k.a. ciphertext) m. Here is the popular modular-exponentiation function.

def modulo_pow(base, exponent, modulus):
    """ display the result of base ** exponent % modulus """

    exp = exponent
    result = 1
    b = base % modulus

    while exp > 0:
        if exp % 2 == 1:
            result = (result * b) % modulus
        exp = exp >> 1
        b = (b * b) % modulus

    print(str(base) + " ** " + str(exponent)
          + " = " + str(result) + " (mod " + str(modulus) + ")")

Running modulo_pow(21556870, 1951097, 44331583) and modulo_pow(71, 15852553, 44331583), we obtained, respectively,

21556870 ** 1951097 = 71 (mod 44331583)
12228498 ** 1951097 = 111 (mod 44331583)

Hence, the decrypted message is 71,111. Can you find what it means?

Answer 2

You'll need to factor the base of the RSA public key to be able to decrypt. That is the whole point: cracking RSA is equivalent to factoring, and factoring is (presumed to be) very hard.