1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

"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?

$\endgroup$
  • 1
    $\begingroup$ It means Go? I was getting it right until the m**d (mod n) part but when I tried doing the calculation using some online tools, I got weird values. But yes, working with the code would be easier! $\endgroup$ – x89 Apr 10 '20 at 0:39
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't remember doing this kind of factoring before. An example or a reference link would be nice $\endgroup$ – x89 Apr 9 '20 at 11:57
  • $\begingroup$ You wouldn't do the factoring. Either you have the private key (which is roughly the public key factored), then you don't need it, or you don't have the private key, in which case you give up - unless the public key is 100 bits or so. $\endgroup$ – gnasher729 Apr 9 '20 at 15:58
  • $\begingroup$ That;s weird. We had a practice question where only the public key was given and we had to do the decryption..@gnasher729 $\endgroup$ – x89 Apr 9 '20 at 16:47
  • $\begingroup$ @FSJ small modulus. $\endgroup$ – vonbrand Apr 12 '20 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.