# Encrypt/decrypt a test message plaintext=1234567 # Secret message, mod n (DANGER! must pad a real message!) ciphertext=pow(plaintext,e,n) # Encrypted (using public key e and public modulus n) decrypted=pow(ciphertext,d,n) # Decrypted (using secret key d)
The hard part
about the implementation is creating a public modulus n and your
secret key d. One option is to use an existing program to
generate them, such as OpenSSL:
openssl genrsa -out private_key.pem 1024
openssl rsa -pubout -in private_key.pem -out public_key.pem
openssl rsa -text -in private_key.pem
One run of
this on my machine produced this private key:
Private-Key: (1024 bit)
publicModulus:
00:e0:ae:82:8f:6a:92:0a:bb:66:95:34:04:e6:82:
03:9a:fd:93:1d:6c:ed:e7:50:7a:74:da:ba:70:8f:
f9:a4:b4:16:de:f9:9c:30:bf:15:d5:0e:6d:27:24:
9f:ea:69:4d:a2:21:22:6e:47:fe:cc:9f:8d:b0:84:
3f:f3:8e:fc:04:83:44:71:0d:ba:fd:7d:3f:f3:28:
05:49:1e:47:a9:a7:14:94:57:71:5f:47:4f:4a:54:
9f:b3:e4:48:6d:28:13:50:48:37:56:8b:33:d5:fa:
b1:f5:89:b9:a6:16:2f:47:c2:9b:fd:14:0d:d1:ba:
3a:41:4b:88:88:ed:a8:a1:ef
publicExponent: 65537 (0x10001)
privateExponent:
26:7d:5e:ba:68:dc:49:e0:5e:ab:72:b4:e0:34:27:
9f:f6:8e:ac:3c:cb:e8:93:7d:d6:e4:dd:89:88:f0:
90:49:95:9d:6f:0f:55:be:76:64:00:4b:ac:a7:f6:
89:36:ae:e8:f6:5a:2a:a0:44:c3:13:16:37:c6:00:
1a:9e:45:07:c2:af:c7:0b:66:a0:ef:60:01:c1:e1:
e8:d2:c7:f5:bb:f0:f9:82:3a:67:f8:08:46:1e:76:
63:29:94:c8:3b:d3:ce:0a:fb:90:84:ce:f8:b2:a5:
17:2c:73:3e:c4:fd:7f:b1:08:61:be:0b:6c:b3:81:
f8:50:fe:20:62:09:b0:31
You can test
this key pair for encryption/decryption in Python like this:
# Convert a string with hex digits, colons, and whitespace to a long integer
def hex2int(hexString):
return int("".join(hexString.replace(":","").split()),16)
# Get modulus and key from: openssl rsa -text -in private_key.pem
n=hex2int("""
00:e0:ae:82:8f:6a:92:0a:bb:66:95:34:04:e6:82:
03:9a:fd:93:1d:6c:ed:e7:50:7a:74:da:ba:70:8f:
f9:a4:b4:16:de:f9:9c:30:bf:15:d5:0e:6d:27:24:
9f:ea:69:4d:a2:21:22:6e:47:fe:cc:9f:8d:b0:84:
3f:f3:8e:fc:04:83:44:71:0d:ba:fd:7d:3f:f3:28:
05:49:1e:47:a9:a7:14:94:57:71:5f:47:4f:4a:54:
9f:b3:e4:48:6d:28:13:50:48:37:56:8b:33:d5:fa:
b1:f5:89:b9:a6:16:2f:47:c2:9b:fd:14:0d:d1:ba:
3a:41:4b:88:88:ed:a8:a1:ef
""")
d=hex2int("""
26:7d:5e:ba:68:dc:49:e0:5e:ab:72:b4:e0:34:27:
9f:f6:8e:ac:3c:cb:e8:93:7d:d6:e4:dd:89:88:f0:
90:49:95:9d:6f:0f:55:be:76:64:00:4b:ac:a7:f6:
89:36:ae:e8:f6:5a:2a:a0:44:c3:13:16:37:c6:00:
1a:9e:45:07:c2:af:c7:0b:66:a0:ef:60:01:c1:e1:
e8:d2:c7:f5:bb:f0:f9:82:3a:67:f8:08:46:1e:76:
63:29:94:c8:3b:d3:ce:0a:fb:90:84:ce:f8:b2:a5:
17:2c:73:3e:c4:fd:7f:b1:08:61:be:0b:6c:b3:81:
f8:50:fe:20:62:09:b0:31
""")
e=65537 # encryption exponent
m=123456789 # message
enc=pow(m,e,n) # m^e mod n (encryption)
dec=pow(enc,d,n) # m^e^d mod n (decryption)
print("Encrypted: enc = ",enc);
print("Decrypted: dec = ",dec);
Here's the
process for making your own modulus n and key d:
# Set up RSA keys (do this once, beforehand, because it's slow!)
nbits=1024 # Use at least 1024 bits for security
p=random_prime(nbits//2) # secret primes each have half the bits
q=random_prime(nbits//2)
print("Secret random primes p =",p," q =",q);
n=p*q # Public modulus
e=65537 # Public encryption exponent
print("Public modulus n = p*q = ",n);
print("Public encryption exponent e =",e);
totient=(p-1)*(q-1) # == Euler's totient function of n
d=modular_inverse(e,totient) # Secret key
print("Secret key d=",d);
This works
because the modulus used to pick d, (p-1)*(q-1), is actually the Euler
totient function of n, where totient(k) counts the number of
integers between 1 and k that are relatively prime to k. For
a prime P, totient(P)=P-1, because everything between 1 and P-1 is
relatively prime to P (relatively prime means gcd(a,P)=1).
If n was prime, totient(n)=n-1, but we built n=p*q from the
product of two primes, so our count of relative primes is missing
all the multiples of p or q up to n; there are p-1 and q-1 of
each, for a total of n-1-(p-1)-(q-1) relative primes, which is
algebraically equal to (p*q-p-q+1)=(p-1)*(q-1)=totient(n).
Euler's
theorem states that for any integer a coprime to n,
the totient function gives the "order of the multiplicative
group", meaning:
atotient(n) = 1 (mod n)
Both sides are
equal to 1. We can raise 1 to any power and still get 1:
ah*totient(n) = 1 (mod n)
We can now
multiply both sides by a to get back to a again (this equation
will come in handy in a moment!).
a1+h*totient(n) = a (mod n)
This is true
for any numbers a and n that are relatively prime.
In RSA, we
start with a message m, raise it to the power e, then raise it to
the power d to recover the original message:
(me)d = m (mod n)
We picked d so it's the multiplicative inverse of e, modulo
totient(n), or
ed = 1 (mod totient(n))
Because of the way modular arithmetic works, this means there's
some integer h with:
ed = 1 + h*totient(n)
But now we can
just substitute the message m into Euler's theorem to get:
m1+h*totient(n) = med = m
(mod n)
This means
picking e and d correctly will allow us to encrypt and decrypt
data correctly. We can do this because we know
totient(n)=(p-1)*(q-1). It's hard for other people because
factoring a big number into primes is hard.
from time import time; # timing
from random import SystemRandom; # cryptographic random byte generator
rand=SystemRandom(); # create strong random number generator
# This is the prime modulus used by SECG secp256k1, the BitCoin elliptic curve
P=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F;
start=time();
for repeat in range(10):
a=rand.getrandbits(100); # random potential "witness"
print("a = ",a);
res=pow(a,P-1,P);
print("a^P-1 mod P = ",res);
elapsed=time()-start;
print("Elapsed=",elapsed," seconds");
Carmichael
numbers are not prime, but (almost like mafia numbers) do
not have any surviving Fermat witnesses, they're all liars that
output 1. To avoid accidentally getting a Carmichael number
instead of a prime, we use the more complex Miller-Rabin
primality test, which has a 3/4 probability of failing per
pass on composite numbers, so running it 64 times gives a 2-128
chance of declaring a composite number as prime.
import math
from time import time # timing
from random import SystemRandom # cryptographic random byte generator
rand=SystemRandom() # create strong random number generator
# This is the prime modulus used by SECG secp256k1, the BitCoin elliptic curve
P=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
# Miller-Rabin primality test (NIST FIPS 186-4 Appendix C)
# w is the number to test for primality.
# iterations is the number of tests (64 is reasonable)
def Miller_Rabin(w,iterations):
a=0 # largest integer such that 2^a divides w-1
while (0==((w-1)%(1<<(a+1)))):
a=a+1
m=(w-1)//(1<<a) # w-1 = 2^a * m
# print("w=",w," m=",m," a=",a)
wlen=int(math.log(w,2)) # counts bits in w
for iter in range(iterations):
# Pick a random potential witness b, 1<b<w-1
foundB=False
while (not foundB):
b=rand.getrandbits(wlen)
foundB=(b>1) and (b<w-1)
# Main Miller-Rabin test:
z=pow(b,m,w)
# print("z=",z)
if (z==+1 or z==w-1): continue # quick pass
# We may need a cleanup pass:
for j in range(1,a-1):
z=pow(z,2,w)
# print(" j=",j," z=",z)
if (z==w-1): break # pass
if (z==1): return False # fail
return False; # fail
# It passed all the tests--it's probably prime!
return True
start=time()
for j in range(10):
print("Miller-Rabin test(P -",j,"): ",Miller_Rabin(P-j,64))
elapsed=time()-start
print("Elapsed=",elapsed," seconds")
Finding large
primes is the most time-inefficient part of RSA setup, taking 100x
longer than an encryption operation!
Here's how the
openssl key generation implementation scales with key size, the
number of bits in the product of the two primes:
| Key Size |
Generation Time (sec) |
Security |
| 512 bits |
0.01 |
Poor--crackable in a
few months on a small cluster. |
| 1024 bits |
0.04 |
OK--nobody has ever admitted factoring
numbers this big. |
| 2048 bits |
0.09 |
Good |
| 4096 bits |
1.2 |
Excellent |
| 8192 bits |
20 |
Overkill--if efficient factoring algorithms
exist, this won't help much |
| 16384 bits |
100 |
Total overkill |