How does Public Key Cryptography work

Public Key cryptography solves one of the main problems with strong cryptography. How do you securely share the encryption/decryption key? If you have a secure channel for doing that, then why not use the same channel to send your plaintext message?

Public Key cryptography uses one key to encrypt and a different key to decrypt. This means you can share your Public Key with the world and anyone can use it to encrypt a message to you, but you are the only person with access to the Private Key to decrypt the message. Clever stuff!

This allows all sorts of exciting things – encryption, signing, non-repudiation and more.

But how does the maths behind this work? I’ve written a worked example below which shows a simplified version of how RSA encryption works. I’ve used small numbers so that you can follow along with a calculator, or a pencil and paper if you are cleverer than me!

Choose two random (large) prime numbers, p and q:
p = 13
q = 7

Multiply the numbers together to get the modulus, N, (the maximum value we can encrypt).
N = pq = 13*7 = 91 This is known as a trapdoor function – it’s easy to work out N if you know pq but very difficult to discover p and q if you only know N (for bigger numbers than we are using here)

Choose a public key, e.
e = 5 (generally chosen from {3, 5, 17, 257, 65537} which are also prime numbers)

To compute the associated private key, you need to know the two prime numbers (p and q). First compute φ (phi)
φ = (p-1)(q-1) =(13-1)(7-1) = 12*6 = 72

Then compute the private key, d.
d = (1/e) mod φ or, written differently, ed = 1 mod φ

In English, this means “find a whole number, d, which, when multiplied by ‘e’ and then divided by ‘φ’, leaves a remainder of 1” – there will be multiple values which are suitable.

Substituting the known values, we get
5d = 1 mod 72, so d = 29 (because 529/72 = 2 remainder 1) or 461 (because 5461/72 = 32 remainder 1) or 7373(because 5*7373/72 = 512 remainder 1) or other, larger, numbers…

We’ll choose the smallest number ’29’ here to make the calculations later a bit easier.

We now have all the required parts to encrypt and decrypt a message.

The public key which you share with the world is (N, e) = (N = 91, e =5)
The private key which is known only to you is (N, d) = (N = 91, d = 29)
The key pair is written ((N,e), d) – in our case ((91, 5), 29)

Before we can encrypt a message, we need to convert the message from letters to numbers. Lets use the standard Unicode Transformation Format 8-bit (UTF-8) encoding where each letter is represented by a number:

A = 65	G = 71	M = 77	S = 83	Y = 89
B = 66	H = 72	N = 78	T = 84	Z = 90
C = 67	I = 73	O = 79	U = 85
D = 68	J = 74	P = 80	V = 86
E = 69	K = 75	Q = 81	W = 87
F = 70	L = 76	R = 82	X = 88

– a space would be represented by 32

So, the message “ATTACK” would be encoded as 65, 84, 84, 65, 67, 75

To encrypt the plaintext message, m, into cypertext, c
c = me mod N
(remember, ‘e’ and ‘N’ are both public information)

A would be 655 mod 91 = 1,160,290,625 mod 91 = 39 (1,160,290,625 / 91 = 12,750,446 remainder 39)
T would be 845 mod 91 = 4,182,119,424 mod 91 = 28
C would be 675 mod 91 = 1,350,125,107 mod 91 = 58
K would be 755 mod 91 = 2,373,046,875 mod 91 = 17

Our encrypted message is now 39, 28, 28, 39, 58, 17

to decrypt the cyphertext, c, back to the plaintext, m
m = cd mod N
(remember, ‘d’ is only known to us!)

39 would be 3929 mod 91 = 1.3831637670618865315545398098597e+46 mod 91 = 65
28 would be 2829 mod 91 = 9.2807464717109449615203639109421e+41 mod 91 = 84
58 would be 5829 mod 91 = 1.37851600677743110483676343403e+51 mod 91 = 67
17 would be 1729 mod 91 = 4.8196857210675091509141182522307e+35 mod 91 = 75

Tip:
3929 mod 91 is “the remainder when 39 multiplied by itself 29 times is divided by 91” – The numbers when we worked this out above become enormous – we can keep the numbers smaller by dividing by 91 and keeping just the remainder as we go along. If we do this one step at a time, we get:
1: 3939 = 1,521 – this is bigger than N (91) so we can divide by 91 to get 16 remainder 65 (just keep the remainder!)
2: 6539 = 2,535 – we can divide by 91 to get 27 remainder 78
3: 7839 = 3,042 – we can divide by 91 to get 33 remainder 39
…and so on…
27: 6539 mod 91 = 78
28: 7839 mod 91 = 39
29: 3939 mod 91 = 65 <— the same answer we got by doing 3929 mod 91

Our decrypted message, then, is 65, 84, 84, 65, 67, 75 which decodes to ATTACK using the UTF-8 table!

Let me know in the comments below if this makes sense and is useful…