Public Key Cryptography Intro
Thanks to Nicolas Patrois for bringing us the idea for this problem!
It was mentioned in the tasks about modular inverse and modular exponentiation that such operations are popular in cryptography. Now the time has come to see this in details. Revisit page on Modular Arithmetic if some of the following explanations seem vague.
Here is an example of Public Key Cryptography system which you are to hack. Funny thing about such systems is that two different keys are used for encryption and decryption. I.e. even if a person knows the key to encrypt the message he/she still could not (at least easily) decrypt it back.
Obvious use-case for such system is the elimination of the problem of exchanging the encryption key between two sides. Really suppose Alice wants to tell something to Bob privately. She generates two keys - public key and secret key and sends the first of them to Bob. She does not care if attacker (for example, evil Bob's wife Eve) intercepts the key! Bob encrypts his message and sends the cipher back to Alice, who is able to decrypt it since she posess the secret key. But Eve could not do this since she have no idea what this secret key is.
The method described below is known as ElGamal encryption named
after the Egyptian scientist who proposed it in
Alice and Bob choose some large prime number
n to be the modulo of all the following modular operations. This value
is not a secret. (i.e. all math described below is performed in
Alice then chooses any value
n-1 and some sufficiently large
e not exceeding
She tells Bob values of
pe = p^e (
p raised to power of
n) as her public key. Meanwhile the value
remains her secret key (there is no easy way to calculate it from
Bob converts his message to value (or several values) of
Z/nZ field (i.e. integers between
encrypts each of them separately.
To encrypt the value
m he chooses some random (also sufficiently large)
n-1) and calculates
pk = p^k c = m * (pe)^k
and writes down the pair of these values. Here
k is added as a salt to provide randomness
in the encrypted message.
To decrypt the message Alice (who do not know
k but knows
e) uses the following formula on these two values:
m = c * inv((pk)^e)
inv means a modular inversion function (prove this formula yourself, please!)
We will use this method to encrypt several
4-letter words. Each word is converted into value
m with the following
A*31^3 + B*31^2 + C*31 + D
D are zero-based indices of the letters (i.e.
So that word
math for example is converted into
358088. This encoding allows us to add special symbols for
space, some punctuation marks and one additional for switching to digits, for example...
n for our exercise will be about
1000000 so it allows to encrypt any four-letter word in such manner -
and on the other hand allows to use brute-force for hacking! However in real systems this value could be
long i.e. about
700 decimal digits!
pe- info published by Alice;
ceach - encryption of a single word send by Bob.
Answer should contain space separated words which were send by Bob.
input data: 3 1000133 372453 464079 615510 932705 919640 902107 982800 247781 answer: pair cake boot
You may find several approaches to brute-force hacking the cipher. Perhaps some more whimsical methods could be
found allowing to reduce the number of iterations to