# How does Public Key Cryptography work

*Published: Wed, 06 Nov 2013 22:04:00 GMT*

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 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 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: 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: 6539 mod 91 = 78

…and so on…

27: 65

28: 78

*39 mod 91 = 39*

29: 3939 mod 91 = 65 <— the same answer we got by doing 3929 mod 91

29: 39

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…