## RSA encryption from a novice point of view – 1

I mentioned in a previous post that I covered RSA encryption in the liberal arts math course I teach.  It was part of a progression of exposing the students to larger and larger finite numbers before tackling the concept of infinity.  RSA is a neat idea because you give out certain public information that allows anyone to encrypt a message and send it to you but you possess the only means of decrypting the message.  This sort of encryption is called asymmetric for that reason.

The basic idea is to take a couple of large prime numbers p and q and multiply them to form the RSA modulus, n.  This will be a public number.  The size of these numbers depends on the level of security you’re interested in.   Next you calculate the totient of n, $\phi$ which is generally difficult to do except when you know the prime factorization of the number.  In that case $\phi(n) = (p-1)(q-1)$.  This totient is then used to create the other public number, the public exponent.  We look for a number e such that $1 and that $GCD(e,\phi(n))=1$.  I’ve read that general practice is to use $e=65,537$ as long as it’s relatively prime to $\phi(n)$.  In class I had the students start with 3 and work their way through the primes checking divisibility of the totient $\phi(n)$.

EXAMPLE: choose p=19 and q=41.  Then n=779 is the RSA modulus.  The totient is $\phi(779)=(19-1)(779-1)=720$.  At this point any prime that doesn’t divide the totient will work as our public key, so e=7 would work.  The private key depends on this value and sometimes can be awkwardly large for casual calculations even for the large integer calculator I’ll be using (for example using 7 will result in a private exponent of 103).  So our public key is (7,779)

EXAMPLE: Suppose we want to send the  message “To be?”  We’ll need to convert the 6 characters in this message to their numerical value.

084  111  032  098  101  063

concatenating,

084111032098101063

Which is a number bigger than n (which is three digits) so we’ll chop it up into strings 2 digits long.

08  41  11  03  20  98  10  10  63

Pretty neat eh?  The numbers we end up exponentiating don’t directly represent the encoded characters we wish to send.  The next step is to exponentiate the message modulo n.  As you might imagine, there are clever ways of implementing modular exponentiation (try figuring out $3^{3827616842}=??mod(5)$ for example) but that’s not the focus of the post. Our goal now is to take our numerical message m and create our encrypted version $c=m^e mod(n)$.

EXAMPLE: Our public exponent is e=7 and our RSA modulus is n=779 so we compute such things as,

$08^7=84 mod(779)$

Doing this for nine strings results in,

084  287  486  629  172  420  756  756  503

Notice I added a leading zero to the first number, 84 to make it a string of three digits, 084, the same length as the RSA modulus n.  Now concatenate the numbers into the string we’ll send.

084287486629172420756756503

Now we have our encrypted message.  We then send this in plain sight of any nefarious individuals.  As long as our modulus is sufficiently large it will be impossible to factor on any reasonable time scale and as long as our implementation of the encryption scheme is sound the strength of the encryption will be that of the mathematics.

The individual who gave us the public key has a private key, which is a single number that only they know.  The process of decryption is essentially identical to the process of encryption.  The receiver uses their private key as an exponent and exponentiates our encrypted message modulo n.  This will result in the original message.  How do we find this private key?  Let the private exponent be called d.  Then we require d be such that $ed=1 \mbox{mod}(\phi(n))$.  This essentially means that our original message m when raised in succession to those two exponents, $m^{ed}=m \mbox{mod}(n)$ returns the original message.  There are clever ways of doing this and then there are easy ways to show your students.  Essentially we’re requiring that $ed-1$ be a multiple of the totient so $ed-1=k\phi(n)$ for some natural number k.  Solving for d, $d=(k\phi(n)+1)/e$ where d must be a natural number as well.  You can just try values for k until d ends up an integer.  Not practical for an actual implementation of RSA but easier for students than explaining the extended Euclidean algorithm.  My students were very successful with this approach.  It’s true that I tested all the exercises to make sure they never had to try anything larger than k=10 (and often much less) but I wanted the focus to be on the encryption process which is essentially very straight forward.

EXAMPLE: We’re looking for $d=(k(720)+1)/7$.  Try $k=1,2,3$ etc.  We happen to get lucky and when k=1 we have our private exponent, d=103

Let’s decrypt the message we received, 084287486629172420756756503

The recipient knows that this is a concatenated series of strings all of string length equal to the number of digits in the RSA modulus, n, that all parties know.  So they break up the message and remove any leading zeroes.

84 287 486 629 172 420 756 756 503

Each of these numbers is exponentiated modulo n using the private exponent, d.  So for example,

$84^{103} = 8 \mbox{mod}(779)$

Do this for all nine strings, adding in leading zeroes to keep string length to equal one digit less than the RSA modulus.

08 41 11 03 20 98 10 10 63

Concatenate these strings and then break up into blocks of length three, the length of the ASCII code,

084 111 032 098 101 063

Which yields “To be?”

The mathematics behind this is surprisingly accessible, though the implementations seem to possess endless details, pitfalls, and tricks to avoid the nefarious from gaining advantage in the application of the mathematics to this attempt to protect information.  It’s also incredible, as I’ve already talked about, that some of the largest numbers used in any application are used in this application.  Safe browsing of the internet relies, in part, on the massive numbers used in RSA encryption.  This realization has certainly pushed me down a path of philosophical reflection over the nature of large numbers and their existence.

If I had a wish list of things to follow this post with it would be (1) learning enough about sniffing wifi networks to ‘see’ this encryption happening and ‘see’ the public key given to my browser (I’d like to show my classes), (2) learn more about how secure certificates are made using encryption so that you know that the website you’re looking at really is the website you’re looking at and (3) A bit about alternative encryption schemes such as Elliptic Curve Cryptography, or ECC which is supposed to be ‘stronger per digit’ if you will. Meaning that you can use smaller numbers without sacrificing encryption strength, something which is supposed to be helpful in this mobile computing age where we want to be able to securely interact with the internet on smaller devices while at the same time nefarious agents are constantly looking for vulnerabilities and all the time gaining more powerful computing hardware.

I’m a novice at this to be sure but hopefully this whets your appetite for more and enables  you to share these ideas with your students with less leg work than I have had to do.

If you’d like to see this done a bit more realistically you can find RSA key generators online.