CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
All published worksheets from http://sagenb.org
Image: ubuntu2004
Cryptography Goes Pubic
Fall 2011, Willamette University
Mini University
Lets implement RSA like the pros do (well, not exactly, but closer than if we were doing these calculations by hand)
To start with, we need some large primes. Say something on the order of 100 digits. Because our need for security is only theoretical, we can be lazy and get our large primes from a website. Say this one:
http://primes.utm.edu/lists/small/small.html#100
(However, keep in mind that loose primes bust rhymes. Trying to modify "Loose lips sink ships" to minimal sucess).
Lets get a handle on what is computationally difficult and what is not. How hard is it to multiply our two large primes?
Not too bad. How about factoring?
So factoring bad, multiplying good.... Potential trap-door function: Product of two large primes.
Let's implement RSA
As Boris, we need to generate and post our public information: and such that and are relatively prime
Our private key is , which we can use to find the multiplicative inverse of .
From our knowledge of and we can calculate the euler phi function . Since , is a unit modulo , and thus there exists an element such that , i.e. , or equivalently .
Thus, we can use the euclidean algorithm to calculate the inverse of given . It's important to verify that an adversary listening in on our conversation with Natasha couldn't do the same thing, i.e. that it is hard to find without knowledge of and .
Okay, so it's at least hard enough to thwart a busy adversary with a short attention span. Check.
Now to find the multiplicative inverse of .
So
is our multiplicative inverse of modulo .
Natasha will now encipher her message and send the ciphertext to us.
How will we decrypt it?