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, nonrepudiation 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)
φ = (p1)(q1) =(131)(71) = 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 5*29/72 = 2 remainder 1) or 461 (because 5*461/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 8bit (UTF8) 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 = m^{e} mod N
(remember, ‘e’ and ‘N’ are both public information)
A would be 65^{5} mod 91 = 1,160,290,625 mod 91 = 39 (1,160,290,625 / 91 = 12,750,446 remainder 39)
T would be 84^{5} mod 91 = 4,182,119,424 mod 91 = 28
C would be 67^{5} mod 91 = 1,350,125,107 mod 91 = 58
K would be 75^{5} 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 = c^{d} mod N
(remember, ‘d’ is only known to us!)
39 would be 39^{29} mod 91 = 1.3831637670618865315545398098597e+46 mod 91 = 65
28 would be 28^{29} mod 91 = 9.2807464717109449615203639109421e+41 mod 91 = 84
58 would be 58^{29} mod 91 = 1.37851600677743110483676343403e+51 mod 91 = 67
17 would be 17^{29} mod 91 = 4.8196857210675091509141182522307e+35 mod 91 = 75
Tip:
39^{29} 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: 39*39 = 1,521 – this is bigger than N (91) so we can divide by 91 to get 16 remainder 65 (just keep the remainder!)
2: 65*39 = 2,535 – we can divide by 91 to get 27 remainder 78
3: 78*39 = 3,042 – we can divide by 91 to get 33 remainder 39
…and so on…
27: 65*39 mod 91 = 78
28: 78*39 mod 91 = 39
29: 39*39 mod 91 = 65 <— the same answer we got by doing 39^{29} mod 91
Our decrypted message, then, is 65, 84, 84, 65, 67, 75 which decodes to ATTACK using the UTF8 table!
Let me know in the comments below if this makes sense and is useful…