Describe the mechanism of the Caesar shift.
Use Excel to write three versions of the Caesar shift. Write 0-25 in B2:AA2. Use 0-25 and CHAR(cell+65).
Write your name using a Caesar shift of 3 characters.
Write a short message using the Caesar shift and send it to someone. You should receive a message in return.
Plaintext:
Encrypted text:
How can a message using the Caesar shift be decoded?
Decode the message sent to you and explain how you achieved this.
Given the message ‘MSG’ find two different words that mean the same thing by shifting by different values.
Why are Caesar shifts now considered so feeble as a technique for encryption?
Create a code whose key is not a simple shift but a more random association of one letter against another. One way to do this is to use a key word in the code such as ‘MICHAEL’. Place this under e.g. ‘G’ and then continue the rest of the code from the pairing of L/M. Or add ‘FS’ for ‘FISH’ – you have already used the I and the H in MICHAEL.
Encode a message using this code.
Plaintext:
Encrypted message:
Send a message to someone using your code and challenge them to decode it.
Decode the message you receive. How do you go about this?
Choose a piece of text and construct a frequency table in Excel to determine the frequency of letters in English.
How can you use this table to decode the message?
Use Excel to complete the Vigenère cipher below.
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A |
| C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B |
How can this table be used to encrypt plaintext?
Select a key word such as ‘JACKSON’ and encrypt a message using a change of line for each letter. You should receive a similar message.
Can you decrypt the message you received? What techniques would you use?
What name is given to a code that uses the Vigenere square with a key whose length is the same as the message? What are the characteristics of this type of code?
We know that letters in digital computers have underlying numbers – computers are ‘digital’ because they turn all data into numbers. We can therefore use numeric codes in encryption, for example using addition and/or multiplication to change a letter before it is sent.
Use the codes 0-25 with addition to produce a code (in Excel). What can we do about the numbers/characters that have gone out of range?
Use the codes 0-25 with multiplication to produce a code (in Excel). What can we do about the numbers/characters that have gone out of range?
What is the obvious limitation of addition and multiplication by themselves in producing a secure code?
What is modular arithmetic?
Convert the following from minutes to hours and minutes: 65, 143, 199, 239, 300.
Convert the following from minutes to hours and minutes on both a 12 hour and a 24 hour clock: 910, 1035, 1175, 1445 .
If today is Wednesday what day will it be in 20 days time? 35 days time? 50 days time? 68 days time? 90 days time?
What operation did you use in the clock and calendar problems?
How do we use modular arithmetic with the codes produced by multiplication? Why is modular arithmetic useful in this context?
Solve the following: 3 mod 26; 15 mod 26; 18 mod 26; 37 mod 26; 53 mod 26; 72 mod 26.
Use Excel to check your answers (=mod(n, divisor))
In Excel write down 0-25 in row 2, starting in column B. These correspond to letters A-Z. Put a number that will be a multiplier in the A column of row 3 (make this 3 to begin with). Underneath 0-25 write the product of these numbers using the multiplier in A3. The formula will be something like this ‘=B2*$A$3’ – the $ signs keep the reference to the multiplier cell constant. Underneath the products enter the formula ‘=mod(B4, 26)’ – this finds the remainder after division by 26.
Not all multipliers produce a complete set of codes. In Excel, make one example of a number that produces a complete list of codes in the range 0-25 and one example of a number that produces a repeating group of codes that is incomplete (mod 26). To do this, repeat the steps above for a second multiplier in rows 6, 7 and 8, in this case 6. Note that a number that does not produce a complete set of numbers in the range 0-25 (and therefore an incomplete set of letters) is unsuitable as a multiplier in the code.
List all the numbers that will produce a complete set of codes from multiplication and modular arithmetic (mod 26).
List all the numbers that will not produce a complete set of codes from multiplication and modular arithmetic (mod 26).
What term describes those numbers that will produce a complete set of codes from multiplication and modular arithmetic? Give three further examples of such pairs of numbers (any pairs, not just one with 26).
Complete this statement: A number is a good key for a multiplicative cipher if it is (rpttsota)
How many letters are there in the Russian alphabet? Give three suitable lengths for good keys in Russian. Give three lengths for bad keys in Russian.
What are: -1 mod 26? -3 mod 26? -12 mod 26? -15 mod 26? -23 mod 26?
An affine equation includes both multiplication and addition and has the form
Y = (mx + b) mod n
We are working towards an understanding of public key cryptography, in particular the method known as RSA (after Ron Rivest, Adi Shamir and Leonard Adleman). This involves the use of modular arithmetic, modular inverses, prime numbers and numbers raised to large powers. We need to look at these in more detail.
The above procedures show how we can convert one number into another using addition and/or multiplication and thus encrypt it. But how could we decrypt the numbers by converting them back to the originals?
If we multiply a number by 3, how do we get back to the original number? What name is given to this type of number?
We need a way of finding multiplicative inverses in modular arithmetic.
If we multiply by 3 we need a way of solving:
3 x n ≡ 1 (mod 26) (≡ means ‘is congruent to’, as in triangles: equivalent)
In other words, what number, when multiplied by 3, gives 1 (mod 26).
Is 10 ≡ 1 (mod 26)? 10 mod 26 = 10, so no.
Is 27 ≡ 1 (mod 26)? 27 mod 26 = 1, so yes. Now, 27 = 3 x 9 so 3 and 9 are modular inverses (they are factors of 27).
Other numbers congruent to 1 mod 26 are: 53, 79, 105, 131. 53 and 79 are primes so have no factors. 105 has factors 5 and 21, which are also inverses mod 26. 105 also has factors 15 and 7 so these too are inverses in mod 26.
Thus if we multiply 5 by 3 ≡ 15 (mod 26) to encrypt, we can multiply by 9 (the inverse of 3) to get 135, which is ≡ 5 (mod 26), the number we encrypted.
Similarly, if we multiply 4 by 15 ≡ 8 (mod 26) we can multiply by 7 (the inverse of 15) to get 56, which is ≡ 4 (mod 26).
Again, if we multiply 12 by 7 to get 6 (mod 26) we can multiply by 15 (the inverse of 7) to get 90, which is ≡ 12 (mod 26).
In each of these cases, multiplying by the inverse mod 26 takes us back to the original number.
What is the mod 26 inverse of 2? (solve 2 x n ≡ 1 mod 26).
Which numbers do you think have inverses mod 26?
Which numbers do you think do not have inverses mod 26?
Using Excel, find all the inverses of mod 26. Try it this way: In column A make a sequence 1-255. In cell F2 enter ‘3’. In cell G2 enter ‘26’. In cell B1 enter ‘=A1*$F$2’. In cell C1 enter ‘=mod(B1,$G$2)’. Select column C and set conditional formatting so a cell is highlighted if the contents are ‘1’. You can now use this to find all multiplicative inverses for any pair of values.
A prime number is an integer that has no factors other than 1 or itself. We can find tables of prime numbers on the internet or we can use a method such as the Sieve of Eratosthenes to find them for ourselves. To test if a number is prime we need to divide it by increasing values of the divisor. For example:
Is 77 prime?
77 mod 2 =
77 mod 3 =
77 mod 4 =
Complete the sequence to show whether 77 is prime. Comment on the operations 77 mod 4 and 77 mod 6. What numbers should we use as the divisor? What upper limit can we set for the divisor?
What is the largest divisor we need to examine to decide whether 123 is prime?
What is the largest divisor we need to examine to decide whether 401 is prime?
The RSA encryption algorithm requires the use of very large numbers and the raising of those numbers by large powers. For the purposes of understanding we can work with prime numbers such as 5 and 11 and the product of 55. For real encryption, however, we need to use very large numbers, otherwise it will be too easy to break the codes.
The reason is as follows. Given 55 or 91, most people with high school maths would be able to find the primes that multiply to these numbers. The RSA encryption algorithm works by using numbers that can be multiplied but for which the result is so large that it would take a long time to find the factors from the product. This is called a ‘one way function’ because it is easy to find a result in one direction but very difficult to reverse the process. For numbers such as 10,403 or 295,927 it is harder for humans to find the factors but it is still within easy reach of a computer program. To be effective as an encryption key the numbers we need to use should have well over 100 digits and the size of number needed is increasing steadily as computers and cryptanalysis increase in power and sophistication.
We need to be able to calculate numbers such as 1823 mod 55
This involves less calculation than you might think.
Calculate 181 mod 55:
Calculate 182 mod 55:
Now 184 mod 55: it will help to rewrite 184 as (182)2 so we can square the result of the previous calculation.
Now 188 mod 55: square the previous result:
Now 1816 mod 55:
We now have enough results to calculate 1823 mod 55:
181 mod 55 x 182 mod 55 x 184 mod 55 x 1816 mod 55
You should have 18 x 49 x 36 x 26 mod 55 = ??
You have thus found the result of a large power mod 55 by using the result of a smaller calculation.
In Excel write a model that will compute large powers modulo n. Use column A and row 2 for labels. In B3 write the number that you want to raise by a given power (e.g. 18).
In C3 write the modulus you will use (e.g. 55). In D3 find the modulus of e.g. 18 mod 55. This is 181 mod 55. In D4 enter a formula to square
the result of the previous calculation mod 55 (use $C$3 to keep the reference to the modulus fixed).
This is 182 mod 55. Now you can drag down a few rows to find 184 mod 55, 188 mod 55, etc.
Now you have the results of 181 mod 55, 182 mod 55, 184 mod 55, etc. you can use these values to find the answer to 1823 mod 55 or
anything up to 1831 mod 55. Simply multiply the results of the different powers, choosing the ones that add up to 23.
What is 1823 mod 55?
We can now put our knowledge of modular arithmetic, modular inverses, prime numbers and large powers to work and show how the RSA encryption system works. The problem that the RSA system was designed to overcome was that of key distribution. It is one thing to encrypt a message but how do you send the key to the recipient? Sending it by the same system as the message is insecure: if the bad guys can read the encrypted text they can also read the key, which would be disastrous. You could send it be other means such as under armed guard but this could be complicated and expensive and vulnerable to attack.
A better means was required for distributing keys and this was found in the public-private key system. A person who wants to receive encrypted messages publishes a public key and messages to them are sent using that key. The person receiving the message has a private decryption key that only he knows so the message is secure, even in an insecure environment such as the internet. It is the invention of public key cryptography that has made it possible for the internet (a public network) to be used for secure communication and e-commerce.
The encryption key in RSA is formed from a pair of numbers, e and n.
n is calculated as the product of 2 prime numbers e.g. 55 from 5 and 11: call them p and q.
We now find the product of (p-1) x (q-1): in this case, (5-1) x (11-1) = 4 x 10=40.
The number e in the encryption pair must be relatively prime to (p-1) x (q-1) e.g. 7 (no common factors in 40 and 7).
Thus the encryption pair in this case is (55, 7).
Now we need the message as a number. Working with a single letter such as ‘J’ we have a numeric value of 9 (it is the 10th letter, numbering starts at zero).
We now calculate C = me mod n (C is notation for encrypted text)
In this case: 97 mod 55
We can find 97 with a calculator or in Excel so we have 4,783,969 mod 55. Excel can provide the answer to this:
J becomes:
What about decryption?
The decryption key is private to the person who receives a message. The decryption key is based on p and q and (p-1) x (q-1) so it is very important that p and q are kept secret.
The decryption key is derived from a modular inverse:
ed ≡ 1 (mod (p-1) x (q-1))
We know e, p and q already so we have:
7d ≡ 1 (mod (5-1) x (11-1) )
≡ 1 mod 40
Thinking back to modular inverses we try:
7 x 1 = 7 mod 40 = 7
7 x 2 = 14 mod 40 = 14
7 x 3 = 21 mod 40 = 21
7 x 4 = 28 mod 40 = 28
7 x 5 = 35 mod 40 = 35
7 x 6 = 42 ≡ 2 (mod 40)
7 x 7 = 49 ≡ 9 (mod 40)
…
7 x 22= 154 ≡ 34 (mod 40)
7 x 23 = 161 ≡ 1 (mod 40)
So the inverse or private key for (7, 55) is 23. We could have used our earlier spreadsheet on inverses to find this value (plug 7 and 40 into cells F2 and G2).
To decrypt the message (the single digit found earlier by encrypting J=9) we need to find Cd mod n (where C is the encrypted value)
423 mod 55 = ??
We can use the powers spreadsheet we created earlier to find 423 mod 55. Simply change the value in cell B3 to 4 and make sure the modulus in C3 is 55.
Thus 423 mod 55 =
The answer should be the plaintext letter/number that you started with, which was:
‘Ah’, you might say, encrypting letters in this way is very clever but surely the message is still susceptible to frequency analysis and is, therefore, no better than a simple substitution cipher? If that were the end of the RSA story this would be true but it isn’t the end. Characters in computers are numbers stored in binary and they can be joined together to make strings of characters. The computer code for A is 65 and for C is 67. If we take these two numbers as one 4 digit number and perform RSA on this using 3 digit primes and correspondingly larger values of ‘e’ then the one-for-one arrangement of a simple substitution cipher disappears. In real systems groups of 8 or more letters may be grouped and encrypted as one, using the large prime numbers mentioned earlier. Thus it becomes much harder to guess the values of p and q (hard to find the prime factors of a large number) and find the decryption key.
Write an essay about the role of cryptography in historical events.