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:

Start with two big primes, p and q. Multiply them to get a "public key modulus" n=p*q
Pick a "public key exponent" e. For big primes, everybody's settled on e=65537

n and e are published.

Choose a "private key exponent" d. Pick this so d*e=1 mod (p-1)*(q-1)

You can use the Extended Euclidean Algorithm for this.
You should shred p and q after picking d, and keep d secret.

Surprisingly, m^e*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 = m^e mod n
To decrypt ciphertext c back into the message m, use your private key d: m=c^d 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 = m^d mod n
To verify a signature s, decrypt it using the public key e: m=s^e 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 14
68 98 0A 1E FE DA 04 6F 13 84 62 21 C3 D1 7C CE
9F 05 E0 B8 01 F0 4E 34 EC E2 8A 95 04 64 AC F1
6B 53 5F 05 B3 CB 67 80 BF 42 02 8E FE DD 01 09
EC E1 00 14 4F FC FB F0 0C DD 43 BA 5B 2B E1 1F
80 70 99 15 57 93 16 F1 0F 97 6A B7 C2 68 23 1C
CC 4D 59 30 AC 51 1E 3B AF 2B D6 EE 63 45 7B C5
D9 5F 50 D2 E3 50 0F 3A 88 E7 BF 14 FD E0 C7 B9

Public 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";

(Try this in NetRun now!)

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.

The right answer is:
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

This prints the correct answer:
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*1
lK[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 -s
do '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:

Java's BigInteger library supports "modPow": this^exponent mod m
Perl's Math::BigInt supports "bmodpow"
Poskanzer's C bigint supports "bi_mod_power"

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 -> 536870912
536870913 -> 277362009814313573 -> 536870913
536870914 -> 316604608543652290 -> 536870914
... more gibberish here ...
536871008 -> 377529246580768846 -> 536871008
536871009 -> 6211382552255542 -> 536871009
536871010 -> 6601028794504318 -> 536871010
536871011 -> 431110999340947002 -> 536871011
p=668683849 (SHRED!)
q=707463901 (SHRED!)
n=473069684349234949
e=65537
d=175355628247634273 (SECRET)
e*d=1 mod (p-1)*(q-1)

Try the code on your machine: Zip, Tar-gzip. (License is BSD.)