# Can you decipher the word ETP

This method, named after its inventors Rivest, Shamir and Adleman, uses a pair of keys, namely a private key and a public key. The original data is encrypted with the public key and decrypted with the private key. It is therefore an asymmetrical crypto procedure.

 Step 1: The recipient generates the private key and the public key and send the public key to the sender. Step 2: The sender encrypts his message with the public key and sends the encrypted text back. Step 3: The recipient decrypts the text with the private key.

The keys are generated with the following algorithm, which is based on number theory [more ... You can find an elementary proof in the book Barth, algorithms for beginners, Springer-Verlag].

First, two prime numbers p and q are chosen, which should have several hundred digits for a secure system. One multiplies this and forms m = p * q. From number theory we know that Euler's function φ (m) = (p-1) * (q-1) is the number of coprime numbers for m (a, b are coprime if the greatest common divisor gcd (a, b) = 1).

Next one chooses a number e that is smaller than φ and relatively prime to φ. The public key has already been created, it consists of the pair of numbers:

Public key: [m, e]

Here is an example with the small prime numbers p = 73 and q = 151:

m = 73 * 151 = 11023, & # 966 = 72 * 150 = 10800, e = 11 (chosen coprime to & # 966)

Public key: [m, e] = [11023, 11]

The private key then consists of the pair of numbers:

Private key: [m, d]

where for the number d must apply: (d * e) mod & # 966 = 1

(Since e and φ are relatively prime, Bézout's lemma from number theory says that the equation has at least one solution).

With your values ​​for e and & # 966 you can determine the number d with a simple program by trying 100,000 values ​​for d in a for loop.

e = 11 phi = 10800 for d in range (100000): if (d * e)% phi == 1: print "d", d

You will receive several solutions (5891, 16691, 27491, 49091, etc.). In principle, you only need the first one to set the private key.

Private key: [m, d] = [11023, 5891]

The calculation of the private key is only so easy here because you know the numbers p and q and thus also the number & # 966. Without knowing these numbers, the private key can only be calculated with great effort

Be using the RSA algorithm numbers encrypted. To encrypt a text, you use the ASCII code of each character and use the public key [m, e] to form the encryption value s for the ciphertext according to the formula

s = re (modulo m).

You write these encryption numbers line by line in the file secret.txt.

publicKey = [11023, 11] def encode (text): m = publicKey [0] e = publicKey [1] enc = "" for ch in text: r = ord (ch) s = int (r ** e% m ) enc + = str (s) + "\ n" return enc fInp = open ("original.txt") text = fInp.read () fInp.close () print "Original: \ n", text krypto = encode ( text) print "Krypto: \ n", krypto fOut = open ("secret.txt", "w") for ch in krypto: fOut.write (ch) fOut.close ()
Mark the program code

In the decoder you read the numbers from the file secret.txt first in a list. To decrypt, use the private key to calculate the original number from the encryption number s according to the formula

r = sd (modulo m).

This is the ASCII code of the original character.

privateKey = [11023, 5891] def decode (li): m = privateKey [0] d = privateKey [1] enc = "" for c in li: s = int (c) r = s ** d% m enc + = chr (r) return enc fInp = open ("secret.txt") krypto = [] while True: line = fInp.readline (). rstrip ("\ n") if line == "": break krypto.append (line) fInp.close () print "Krypto: \ n", krypto msg = decode (krypto) print "Message: \ n", msg fOut = open ("message.txt", "w") for ch in msg : fOut.write (ch) fOut.close ()
Mark the program code