# RSA Cryptography

Problem #152

Tags: cryptography modulo mathematics popular-algorithm

Who solved this?

You are probably already get a clear idea on principle of Public Key Cryptography from the exercise on ElGamal method.

Here is another method (perhaps, more famous) named RSA after its three authors. It was proposed in `1977` i.e. `8` years earlier than ElGamal's - though the latter is really an adaptation of curious Diffie-Hellman algorithim for key exchange which was published in `1976`.

### Algorithm idea

It is based on Euler's theorem which states that for modular exponentiation with modulo `n` it is very easy to compute the power equal to `phi(n)` for any base `a` coprime with `n`:

``````a ^ phi(n) = 1
``````

For example for `n=391` almost any `a` raised to power of `phi(n)=352` yields `1` (except for multiples of `17` or `23`).

How can we use it?

Suppose we choose a pair of values `e` and `d` such that

``````e*d = k*phi(n) + 1
``````

since such a whimsical choice gives us an interesting property:

``````(a^e)^d  =  a ^ (e*d)  =  a ^ k*phi(n) + 1  =  a * (a ^ phi(n))^k  =  a
``````

So if we want to encrypt value `a` we can raise it to the power `e`. And if we want to decrypt it we should raise it to the power `d`:

``````cipher = a ^ e
a = cipher ^ d
``````

The last thing to explain is how to choose a pair of `e` and `d`. Well, `e` could be any arbitrary prime and then `d` is calculated as its inverse modulo `phi(n)`:

``````d = inv(e)  | mod phi(n)
``````

But how to make this approach "strong" against attacking? Attacker will know `e` and `n` (they are parts of public key) but to decrypt the `cipher` he needs to take `e-th` root of it, which effectively means to find `d`!

It is easy to calculate `d` if one knows `e` and `phi(n)`. However suppose that `n` is the product of two large primes `p` and `q`, then:

``````n = p*q
phi(n) = n - p - q + 1
``````

But poor attacker may not know these `p` and `q`. So really the problem of breaking this cipher is the same as problem of factorization which currently have no general efficient solution for numbers built of large prime factors (and scientists believe such solution does not exist so the method is safe).

Resulting algorithm surprizingly works even when `a` is not coprime with `n` - you may investigate this case yourself! Anyway in practice it is highly improbable case.

### Problem Statement

Now we are going to write a program to perform RSA decryption - it will give us necessary experience before trying to hack this algorithm!

The text string is encoded as a long integer using the following approach:

• for each letter its two-digit decimal ASCII is written (so text will not use symbols with codes greater than `99`);
• these two-digit values are simply concatenated;
• then `00` followed by several randomly choosen digits is added to the tail.

For example the word `ABBA` could be encoded as `6566666500314`:

``````A    B    B    A  | end | few random digits
-----------------------------------
65   66   66   65 | 00  | 3   1   4
``````

This integer is then encrypted by `RSA` and you should decrypt it back and print the original text string.

Adding some randomization is crucial for any public key cryptography system to prevent attacker guessing the original message by trying to encrypt his guesses himself.

Input data will contain `p` and `q` at the first and second lines, while for `e` we choose popular constant value `65537`.
The third line will contain the long integer value of `cipher`.
Answer should contain the decrypted text string.

Example:

``````input data:
30762542250301270692051460539586166927291732754961
29927402397991286489627837734179186385188296382227
424236952206057066872700453503661773567827006571091351397488406910437574827532103275742945321419387

P.S. you may say It is so easy to decrypt - not a problem at all! - but remember that attacker do not know `p` and `q` and instead has only their product `n`. Follow to the task on hacking RSA to feel yourself as a hacker!