Home

Welcome to the RSA-Encryption-Decryption wiki!

IMPLEMENTATION: This program was implemented in 3 separate parts: Key Setup: Generate a random integer with at least 100 digits Use Fermat’s Little Theorem to test for primality If prime, this will be p Do a-c to find q n = p*q Use Euclid’s Extended function to calculate private key d e is always 65537 here Write n and e to public_key.txt Write d to private_key.txt

Encryption: Read n and e from public_key.txt Read the message to encrypt from message.txt Divide the message up into blocks of <= 82 characters Convert each block from ascii into a large integer base 256 Encrypt each block using C = M^e mod n (Mod_expon function) Write the each block of ciphertext to ciphertext.txt

Decryption: Read the ciphertext from ciphertext.txt, split up each block again Read the private key d from private_key.txt Read the public key from public_key.txt Decrypt each block of ciphertext using M = C^d mod n (mod_expon function) Convert the the message M to ascii so it can be reported as a string

ALGORITHMS: In addition to the modules listed above, some sub-modules were needed to perform some operations. mod_expon(x,a,n) This algorithm calculates x^a (mod n) using the right to left binary method Follows this pseudocode (Source: Wiki): 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

is_prime(x) This algorithm determines if x is prime by using Fermat’s Primality Test Follows this pseudocode: If x is odd: return false else: result = compute 2^(x-1) if result = 1, #Do more testing if necessary return true else, return false

euclid_extended(e, n) This algorithm calculates the modular inverse of a number e mod n Follows this pseudocode (Source: Wiki): function extended_gcd(a, b) s := 0; old_s := 1 t := 1; old_t := 0 r := b; old_r := a while r ≠ 0 quotient := old_r div 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) output "Bézout coefficients:", (old_s, old_t) output "greatest common divisor:", old_r output "quotients by the gcd:", (t, s)

TESTING: Testing was done manually with test cases. Along the way I had modules which would compare the outputs of things such as the numerical version of the message before encryption and the numerical version of the message after decryption. I wrote driver functions during development to try some random inputs as well. Some example test cases: -A long message ~328 characters -A short message < 82 characters -A blank message

DIFFICULTIES: Throughout development of this program, I encountered several difficulties. The most memorable of then was early into development when I was writing the ciphertext to a file all as one huge number, then trying to divide it back up again once I read that file in my decrypt() function. Whenever I was reading the file and dividing up the pieces into their 200 digit forms, I would get lots of inconsistency since sometimes the ciphertexts were 199 digits or something of the sort. This would make it so that the message would only be correctly deciphered 1 out of 3 times or so. I solved the problem by instead just writing the numbers to the file with a ‘,’ as a delimiter so I could split the file easily.

Also, I had a problem early on where whenever I used my mod_expon function, the program would take lots of time to execute, 30 minutes +. I was using the memory efficient version of modular exponentiation instead of time efficient, thus it ran at a snail's pace. I eventually reworked this function using the right to left binary method and that ran much faster.

The most recent problem I faced was with the last character from 82 character blocks getting cut off when decrypting. Turns out I was going from 0-82 in a loop somewhere instead of 0-81, thus I was actually getting 83 character blocks.

KNOWN ERRORS: none as of yet

COMPILATION AND EXECUTION INSTRUCTIONS: Compilation: My program is in Python so it is not compiled. Execution: I have been executing my program without any flags, so: python RSA.py