Code in Python

RSA Encryption/Decryption

Encrypt and decrypt messages using a ??????(??, ??), where ?? = ????, and ?? and ?? are prime numbers with 10 digits each, and ?? is relatively prime to (?? ? 1)(?? ? 1). Two numbers are relatively prime if their greatest common divisor is 1.

Use the Euclidean Algorithm to verify: gcd(??, (?? ? 1)(?? ? 1)) = 1.

function gcd(e, m) x = e, y = m

while y =? 0 r = x mod y

x=y

y=r return x

Encrypt the following message:

The camera is hidden in the bushes

Concatenate the letters in the message into groups of 10 letters.

For example: thecamerai, would be the first group to encrypt. Notice, we will concatenate the letters after removing spaces. If there are empty spaces at the end of a group, pad with Xs.

We create groups of 10 letters, because each letter is encoded using 0 to 25 (0 A, 1 B, ..., 25 Z), and since n is 20 digits, our max encoded group would be 25252525252525252525. This group, modulo n, is a 20 digit number. Therefore, the encryption will remain within our domain of 10 letters. Notice our group has ten 25s and our max encoded letter is 25.

Encryption:

?? = the encoded group of 10 letters ?? = the encrypted group of 10 letters

?? = ?????????? ?? Use the following algorithm for fast modular exponentiation to compute ????:

Schneier:

function modular_pow(base, exponent, modulus) if modulus = 1 then return 0 Assert :: (modulus - 1) * (modulus - 1) does not overflow base result := 1 base := base mod modulus

while exponent > 0 if (exponent mod 2 == 1):

result := (result * base) mod modulus exponent := exponent >> 1 base := (base * base) mod modulus

return result Decryption:

?? = inverse of ?? modulo (?? ? 1)(?? ? 1) ?? = ?????????? ??

If we solve the following identity ???? + ???? = 1 for ?? and ??, where ?? = ?? and ?? = (?? ? 1)(?? ? 1), ?? will be the inverse of ?? (?? = ??).

Use the Extended Euclidean Algorithm to compute d which is a positive integer (d will assume the value of old_s, which is the return value of this function):

function extended_gcd(a, n) s = 0, old_s = 1, t = 1, old_t = 0, r = n, old_r = a while r =? 0

 quotient = old_r/r old_r = r r = old_r  quotient * r old_s = s 

 s = old_s  quotient * s old_t = t t = old_t  quotient * t 

return old_s Review the Be?zouts Identity Example for another explanation of how to find the inverse d (Be?zout

Coefficients). This will help you understand how the algorithm above works. Now decrypt in groups of 10 letters. Because this cryptosystem scheme uses blocks of letters, it is referred to as a block cipher.

Your program will output the encrypted message to a file (encrypt.rsa). Finally, read the file (encrypt.rsa) with the encrypted message, decrypt it, and then output the results to a new file (decrypt.rsa).