RSA Cryptography - CodeAbbey

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

answer:
TOWEL BEANS SWORD STOCK STORM CHECK

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!