Cryptography

1 Implementing public key cryptography in Python

Learn It

• Last lesson you learned a little about public key cryptography.
• To recap, public key cryptography involves two keys - a public and a private key.
• Anyone can encrypt a message using the public key.
• Only the holder of the private key can decrypt the message.

Learn It

• Public Key cryptography relies on prime numbers.
• Prime numbers are numbers that are only divisible by 1 and themselves.
• So the first few primes are 2,3,5,7,11.
• And here is a list of the first 1000 primes.
• We're going to implement a very poor version of the RSA encryption algorithm.
• It would not be a good idea to encrypt data that you really wanted to keep secret using our implementation.
• You have learned The answer to Life, the Universe and Everything and naturally you want to tell a few close friends, but you don't want everyone to know the answer.
• You're going to write a script that will enable your friends to get their very own private keys. You can then encrypt The Answer with their public key, so only they can see it.

Code It

• The first thing we need to do is pick two prime numbers and a third that is smaller than the other two.
```#Choose three primes
prime1 =
prime2 =
prime3 =
```
• Use the list linked above to choose any three primes below 100.
• Now we need to generate a public key. This is actually really easy.
• It's just the product of the first two primes, and the third prime.
```#Create the public key
publicKey = (prime1*prime2,prime3)
```
• Of course, we'll also need to generate a private key. This is a little trickier.

Learn It

• We're going to need to get into some fairly tricky maths now.
• We'll start by learning about the modulo operator in maths.
• If you were asked what is `5/2` then you'd probably come up with the answer `2.5`
• When we first learn to divide though, we often talk about remainders.
• So `2/5` is equal to `2` with a remainder of `1`
• The modulo operator will tell you the remainder when two integers are divided.
• In Python we use the `%` symbol.

Code It

• Try typing the following into the interpreter
```15%5
15%7
15%13
15%4
15%11
```
• Each one gives the remainder of the division.

Learn It

• The next stage is to find what is known as the totient function of each prime.
• Coprime numbers are pairs of numbers where both numbers can only be exactly divided by 1.

Try It

• Lets look at the number 10.
• To calculate the totient function of the number 10, first list all the numbers below it.
• `9,8,7,6,5,4,3,2,1`
• For each number, see if it is coprime with 10. Have a go at filling in the question marks.
• `9 and 10` can both only be divide by 1.
• `8 and 10` can be divided by ?
• `7 and 10` can only be divided by 1.
• `6 and 10` can be divided by ?
• `5 and 10` can be divided by ?
• `4 and 10` can be divided by ?
• `3 and 10` can only be divided by 1
• `2 and 10` can be divided ?
• `1 and 10` can only be divided by 1
• So counting up we have 4 coprimes, so the totient function of 10 is 4.

• Calculate the totient function of the following numbers.
1. 7
2. 12
3. 13
4. 23
• Both 13 and 23 are prime numbers. Look carefully at the totient values you calculated.
• What do you think the totient of the following primes would be?
1. 43
2. 107
3. 7919
• Write down the rule for calculating the totient function of prime numbers.

Code It

• Now let's add in our totient function
```phi1 = prime1 - 1
phi2 = prime2 - 1
```

Learn It

• Now we need to find a magic number (called `d`).
• d is a number such that when it is multiplied by our third prime and then divided by the product of our two totient functions, the remainder will be exactly 1.
$\frac{dx\mathrm{prime3}}{\mathrm{phi1}x\mathrm{phi2}}=1$
• There are various ways to calculate `d`, but we're going to go for the simplest solution.
• We'll just test every value from 1 upwards until we hit a value for d.

Code It

• Let's start by creating a for loop that counts from d up to the product of our two totient.
```for d in range(phi1*phi2):
print(d)
```
• What's the first number in the list of printed numbers?
• Why might this be a problem? (What does division by 0 give you?)
• Let's fix the code then and give our for loop a starting point.
```for d in range(1,phi1*phi2):
print(d)
```
• Does that fix the issue?
• Now we need to test the equation written above.
```for d in range(1,phi1*phi2):
if (d * prime3)%(phi1 * phi2) == 1:
print(d)
```
• The number (or first of the numbers) listed is the value we want for d.
• So if d is found, we should stop the loop.
```for d in range(1,phi1*phi2):
if (d * prime3)%(phi1 * phi2) == 1:
print(d)
break
```
• Let's make sure that we save the value of d along with the product of our original primes, as this will be our private key.
```for d in range(1,phi1*phi2):
if (d * prime3)%(phi1 * phi2) == 1:
privateKey = prime1*prime2,d
break
```
• So now we have both public and private keys.
• Try running your program and then typing `publicKey` into the interpreter. Then try `privateKey`.

• Now we have the public and private keys, we can encrypt and decrypt numbers.
• The algorithm for encryption is as follows.
1. Take the secret number you want to encrypt (42).
2. Raise it to the power of the second part of your public key.
3. Calculate the remainder when the result is divided by the first part of your public key.
• The algorithm for decryption is as follows.
1. Take the encrypted secret number.
2. Raise it to the power of the second part of your private key.
3. Calculate the remainder when the result is divided by the first part of your public key.
• Try and write two lines of code that will encrypt the number (and save it as `cipherText`) then decrypt `cipherText` and save it as `plainText`.
• Hints
1. To raise one number to the power of another use `**`
• 6**2 = 36
• 10**5 = 100000
2. To get the first element of publicKey use `publicKey[0]`, to get the second element use `publicKey[1]`
• `publicKey =(187,7)`
• `publicKey[0] = 187`
• `publicKey[1] = 7`
3. Use modulo `%` to get the remainder of the division.
• Test your code when you are finished by printing `cipherText` and `plainText`

Test It

• Our algorithm is actually pretty poor, and should never be used for real cryptography.
• While it might encrypt the number 42 well enough, try it with a much larger number.
• What happens?
• Try increasing the size of your prime numbers, using the linked list we used at the start.
• What happens when you use three large primes?
• Real cryptography uses extremely large primes. Why would this be a problem for our algorithm.