Skip to content

Home

Jump to bottom
Matthew Rife edited this page Apr 23, 2018 · 2 revisions

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
Clone this wiki locally