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
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
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 ^ phi(n) = 1
For example for
n=391 almost any
a raised to power of
1 (except for multiples of
How can we use it?
Suppose we choose a pair of values
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
cipher = a ^ e a = cipher ^ d
The last thing to explain is how to choose a pair of
e could be any arbitrary prime and then
is calculated as its inverse modulo
d = inv(e) | mod phi(n)
But how to make this approach "strong" against attacking? Attacker will know
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
It is easy to calculate
d if one knows
phi(n). However suppose that
n is the product of two large primes
n = p*q phi(n) = n - p - q + 1
But poor attacker may not know these
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.
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:
00followed by several randomly choosen digits is added to the tail.
For example the word
ABBA could be encoded as
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
q at the first and second lines, while for
e we choose popular constant value
The third line will contain the long integer value of
Answer should contain the decrypted text string.
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
q and instead has only their product
n. Follow to the task on hacking RSA to feel
yourself as a hacker!