# Public Key Encryption: RSA

CS 463 Lecture, Dr. Lawlor

Back in the 1970's Rivest, Shamir, and Adleman figured out an interesting little mathematical trick:
1. Start with two big primes, p and q.  Multiply them to get a "public key modulus" n=p*q
2. Pick a "public key exponent" e.  For big primes, everybody's settled on e=65537
• n and e are published.
3. Choose a "private key exponent" d.  Pick this so d*e=1 mod (p-1)*(q-1)
4. Surprisingly, me*d=m mod n.  That is, we can raise a number to the e power, then the d power, and mod n, we're back where we started.
To encrypt a message m into ciphertext c, using the public key e: c = me mod n
To decrypt ciphertext c back into the message m, use your private key d: m=cd mod n
This means anybody can encrypt a message for you, but only you can read it.

To "sign" a message m into a signature s, using your private key d: s = md mod n
To verify a signature s, decrypt it using the public key e: m=se mod n

Anybody can decrypt a message you've encrypted with your private key, but only you could have encrypted it.

## Example

For example, here's the Equifax Certificate Authority public key, consisting of a modulus (n) and exponent (e).  If you could factor this 1024-bit number into big primes p and q, you could use them to calculate Equifax's private key d, and use it to sign https certificates that would be accepted by any browser:
`Modulus (1024 bits):C1 5D B1 58 67 08 62 EE A0 9A 2D 1F 08 6D 91 1468 98 0A 1E FE DA 04 6F 13 84 62 21 C3 D1 7C CE9F 05 E0 B8 01 F0 4E 34 EC E2 8A 95 04 64 AC F16B 53 5F 05 B3 CB 67 80 BF 42 02 8E FE DD 01 09EC E1 00 14 4F FC FB F0 0C DD 43 BA 5B 2B E1 1F80 70 99 15 57 93 16 F1 0F 97 6A B7 C2 68 23 1CCC 4D 59 30 AC 51 1E 3B AF 2B D6 EE 63 45 7B C5D9 5F 50 D2 E3 50 0F 3A 88 E7 BF 14 FD E0 C7 B9Public Exponent (24 bits):01 00 01`
That exponent is 0x1001, i.e., 65537.  It's the official standard public key exponent that everybody seems to use.

Luckily, multiplying is easy, but factoring big numbers seems to be hard!  Currently, primes of about 500 bits (making a public key modulus of about 1000 bits) are considered commercially secure.

## Computing with really big numbers

Take two 50 decimal digit primes, and multiply them:

37975227936943673922808872755445627854565536638199 * 40094690950920881030683735292761468389214899724061

Clearly, if you multiply two odd numbers, you should never get an even number back.

But try this in C++:
```std::cout<<std::setprecision(100)<<
37975227936943673922808872755445627854565536638199.0 *
40094690950920881030683735292761468389214899724061.0<<"\n";```
This prints an even number, which can't possibly be right.
1522605027922533518260457400714874678658400574018662242210976145948887793656784833912073618129420288

Or try this in Octave (free version of Matlab):
```format bank
37975227936943673922808872755445627854565536638199
* 40094690950920881030683735292761468389214899724061
= 1522605027922533518260457400714874678658400574018662242210976145948887793656784833912073618129420288.00```
Still wrong.

1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
(This is RSA-100.)

Many programs will give you the correct first 15 or so digits of this number, because they use double precision internally.  That's only 64 bits overall, and the fraction field is only 53 bits or about 15 decimal digits.

We need more.

UNIX-type systems often ship with "dc", an arbitrary-precision decimal calculator.  It's in RPN, like an HP calculator:
```37975227936943673922808872755445627854565536638199
40094690950920881030683735292761468389214899724061*p```
1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139

The famous "RSA .sig" uses a mix of perl and dc:
`#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj\$/=unpack('H*',\$_);\$_=`echo 16dio\U\$k"SK\$/SM\$n\EsN0p[lN*1lK[d2%Sa2/d0\$^Ixp"|dc`;s/\W//g;\$_=pack('H*',/((..)*)\$/)`
This... isn't very informative.  A 5-line version can be built in pure perl:
`#!/usr/local/bin/perl -sdo 'bigint.pl';(\$_,\$n)=@ARGV;s/^.(..)*\$/0\$&/;(\$k=unpack('B*',pack('H*',\$_)))=~s/^0*//;\$x=0;\$z=\$n=~s/./\$x=&badd(&bmul(\$x,16),hex\$&)/ge;while(read(STDIN,\$_,\$w=((2*\$d-1+\$z)&~1)/2)){\$r=1;\$_=substr(\$_."\0"x\$w,\$c=0,\$w);s/.|\n/\$c=&badd(&bmul(\$c,256),ord\$&)/ge;\$_=\$k;s/./\$r=&bmod(&bmul(\$r,\$r),\$x),\$&?\$r=&bmod(&bmul(\$r,\$c),\$x):0,""/ge;(\$r,\$t)=&bdiv(\$r,256),\$_=pack(C,\$t).\$_ while\$w--+1-2*\$d;print}`
Not much better.

Note that the key operation in RSA encryption is modular exponentiation with arbitrary precision numbers:
Each of these libraries also supports a modular inverse, used to compute d from e.

## Try It!

I wrapped Poskanzer's C bigint library in a brand-new C++ "BigInteger" interface.  Here's RSA encryption code using this interface:
`#include <iostream>#include "bigint.h"int main(int argc,char *argv[]) {	bi_initialize();	srandom(3);	int bits=30; // number of bits in each prime		// Generate p and q	BigInteger p=BigInteger::probablePrime(bits); // SHRED!	BigInteger q=BigInteger::probablePrime(bits); // SHRED!	BigInteger n=p*q; // publish	BigInteger e=65537;  // publish	BigInteger d=e.modInverse((p-1)*(q-1)); // our secret key		// Setting the high bit of each message makes it more secure	BigInteger highbit=BigInteger(2).pow(bits-1); // ==2<<(bits-1)		// Try some test encryptions	BigInteger i;	for (i=0;i<100;i++) {		BigInteger m=i+highbit; // message		BigInteger c=m.modPow(e,n); // encrypt		BigInteger m2=c.modPow(d,n); // decrypt		std::cout<<m<<" -> "<<c<<" -> "<<m2;		if (m != m2) std::cout<<"(FAIL!)";		std::cout<<"\n";	}		// Print lots of stuff (even stuff you shouldn't!)	std::cout<<"p="<<p<<" (SHRED!)\n";	std::cout<<"q="<<q<<" (SHRED!)\n";	std::cout<<"n="<<n<<"\n";	std::cout<<"e="<<e<<"\n";	std::cout<<"d="<<d<<" (SECRET)\n";	std::cout<<"e*d="<<(e*d).mod((p-1)*(q-1))<<" mod (p-1)*(q-1)\n";	return 0;}`
Here's an example run:
`536870912 -> 299808987622408897 -> 536870912536870913 -> 277362009814313573 -> 536870913536870914 -> 316604608543652290 -> 536870914... more gibberish here ...536871008 -> 377529246580768846 -> 536871008536871009 -> 6211382552255542 -> 536871009536871010 -> 6601028794504318 -> 536871010536871011 -> 431110999340947002 -> 536871011p=668683849 (SHRED!)q=707463901 (SHRED!)n=473069684349234949e=65537d=175355628247634273 (SECRET)e*d=1 mod (p-1)*(q-1)`