How does Public Key Cryptography work
Published: Wed, 06 Nov 2013 22:04:00 GMTPublic 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…