6 – Public Key Cryptography

Develop the Programming Learning Strand:

? Recap

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.

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.

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 =

#Create the public key
publicKey = (prime1*prime2,prime3)
print('Your public key is', publicKey,'.You can share this with your friends')

Of course, we’ll also need to generate a private key. This is a little trickier.

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.

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.

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.

phi1 = prime1 - 1
phi2 = prime2 - 1

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.

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.

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)

for d in range(1,phi1*phi2):
    print(d)

for d in range(1,phi1*phi2):
    if (d * prime3)%(phi1 * phi2) == 1:
	print(d)

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
print('Your private key is',privateKey)

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

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.

Generate a public and private key (Don’t use large prime numbers).
Write down your public key on a bit of paper and give it to your teacher.
Your teacher is then going to write you a short message, using numbers.
Decrypt each number using your private key, then translate it back into text as follows.
A = 1 up to Z = 26

Evaluate your progress in this unit.