(Note: This post has nothing to do with literature or South America. Our editor studied mathematics in college and continues with that, because David Foster Wallace did.)
Here I give an example of how to create a public and private key and encrypt and decrypt a message using the RSA encryption algorithm. I am writing this, because I have found no example on the Internet that is complete, meaning nothing you can understand from beginning to end. Examples on the internet give the theory and walk the user most of the way through an example, but the user gets stuck trying to calculate the private key. They say things like, “This can be done very easily and quickly with the Extended Euclidean Algorithm.” and then leave out the details.
Here we use a Python program to calculate the Extended Euclidean Algorithm. I am not going to explain how to do that by hand here. You can find that on YouTube here.
First, pick two prime numbers:
Find an e such that 1 < e < Φ(n) and gcd(e,Φ(n))=1. We pick e=7. That is our public key. Check that gcd(7,120)=1.
Now is the hard part, finding the private key. We need to find d such d * e mod Φ (n) = 1. That is where we need the Extended Euclid Algorithm. We copied the Python code to do that from here.
Now calculate the public key like this:
Let’s try to encrypt and decrypt something.
let m=8 be our message.
To encrypt m solve:
m^e mod n=c=(8**7)%143=57
To decrypt c solve:
c^d mod n=m=(57**103)%143=8=m
Here is the Python code:
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
return b, x, y
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
return None # modular inverse does not exist
return x % m
(2) Readers Comments
February 21, 2017
February 05, 2017
January 26, 2017
Thank you, K.C. You are the first person to tell me that s/he caught
Jordan is clearly an intellectual omnivore who can laugh at himself an
I've been here 6 years so have had plenty of opportunities to eat Chil
Sorry, but what a load of bollocks. It is a real shame that you seem t
I spend several months every year in Argentina and Chile. Buenos Aires