The idea
The oldest idea in cryptography is a lock that one key both locks and opens. Alice scrambles a message with a secret, sends the scrambled version across a network where Eve can see it, and Bob unscrambles it with the same secret. Eve sees only the scrambled text.
The weak point is obvious: Alice and Bob must already share the secret. The next topic shows how public-key cryptography removes that requirement. This topic covers the shared-key case, which is still what actually encrypts bulk data.
How it works
Shared-key encryption
In symmetric-key cryptography both encryption and decryption use the same key, so sender and receiver share the same secret key. The lecture makes three points about the pieces.
- The encryption process consists of the algorithm and the key.
- The key is a value that is independent of the algorithm.
- The algorithm produces a different output depending on the key being used at that time.
How it works
Prerequisite: modular arithmetic
x mod n is the remainder of x when divided by n. The lecture gives three facts.
[(a mod n) + (b mod n)] mod n = (a + b) mod n[(a mod n) - (b mod n)] mod n = (a - b) mod n[(a mod n) * (b mod n)] mod n = (a * b) mod n
Repeating the multiplication fact gives (a mod n)^d mod n = a^d mod n. In practice this means you may reduce at every stage and never handle a huge number. RSA relies on this in the next topic.
Worked example
The lecture's modular example: x = 14, n = 10, d = 2
Reduce first:
x mod n=14 mod 10=4.Raise to the power:
4^2=16.Reduce again:
16 mod 10=6. So(x mod n)^d mod n=6.Check the other way:
x^d=14^2=196, and196 mod 10=6.
AnswerBoth routes give 6.
The lecture writes the first line as “4 squared mod 10 = 6”, with the superscript lost in extraction.
How it works
Example: shift ciphers
In the lecture’s shift cipher the plaintext is lowercase letters and the ciphertext is uppercase letters. Each letter is assigned a numerical value, so a is 0 up to z as 25. The secret key is an integer modulo 26. To encrypt, add the key to the plaintext character. To decrypt, subtract the key from the ciphertext.
- x
- Plaintext letter value, a = 0 to z = 25
- k
- Secret key, an integer modulo 26
- C
- Ciphertext letter value, A = 0 to Z = 25
The lecture sets the question: use the shift cipher with key 15 to encrypt the message “hello”. Its table gives the column headings “Recovery of x” and “(x + 15) mod 26 = Ciphertext” and the rows x = 7, 4, 11, 11, 14. The ciphertext column did not extract, so the working below is done from the stated rule.
Worked example
Encrypt hello with key 15
Letter values:
h=7,e=4,l=11,l=11,o=14. These are the lecture’s x values.Add the key to each:
7 + 15=22,4 + 15=19,11 + 15=26,11 + 15=26,14 + 15=29.Reduce mod 26:
22,19,26 mod 26=0,0,29 mod 26=3.Convert to letters:
22=W,19=T,0=A,0=A,3=D.Decrypt check:
Wis 22, and22 - 15=7=h.Ais 0, and0 - 15=-15, which is11mod 26, givingl.
AnswerWTAAD
How it works
A more sophisticated approach: polyalphabetic substitution
A shift cipher uses one substitution for every letter. The lecture’s improvement uses n substitution ciphers, M1, M2, ..., Mn, and a cycling pattern. Its example with n = 4 uses the pattern M1, M3, M4, M3, M2 repeated. For each new plaintext symbol, use the next substitution in the cyclic pattern.
- For “dog”,
dcomes fromM1,ofromM3andgfromM4. - The encryption key is the n substitution ciphers plus the cyclic pattern.
- The key need not be just an n-bit pattern.
Because the same letter can encrypt differently at different positions, a letter-frequency count of the ciphertext is no longer as direct a guide to the plaintext.
How it works
Examples of symmetric-key algorithms
| Algorithm | What the lecture says |
|---|---|
| DES | Data Encryption Standard. Adopted in 1977 by NIST as a federal information processing standard. 56-bit key, 64-bit plaintext input block. |
| 3DES | Encrypt 3 times with 3 different keys. |
| IDEA | International Data Encryption Algorithm. Developed in 1990 by the Swiss Federal Institute of Technology. |
| SKIPJACK | Designed and evaluated by the National Security Agency (NSA) in 1993. |
| AES | Advanced Encryption Standard, established by NIST in 2001 (Nov 2001 on the AES slide), supersedes DES. Based on the Rijndael cipher by Joan Daemen and Vincent Rijmen. 128-bit blocks, 128, 192 or 256-bit keys. |
On DES strength, the lecture notes that a DES Challenge decrypted a 56-bit-key-encrypted phrase by brute force in less than a day, and that there is no known good analytic attack. On AES, it says a brute-force search that takes 1 second on DES would take 149 trillion years for AES.
Where marks get lost
Reduce the final answer too
In the shift cipher a sum such as 11 + 15 = 26 is not a letter. Take it mod 26 to get 0, which is A. Writing 26 or the letter after Z loses the mark.
In the exam
- Be able to encrypt a short word with a stated shift key, writing the letter value, the sum and the reduced value for each letter.
- Memorise DES: 56-bit key, 64-bit block and AES: 128-bit block, 128/192/256-bit keys.
- 3DES means three encryptions with three different keys.
- The lecture dates DES to 1977, IDEA to 1990, SKIPJACK to 1993 and AES to 2001.
Aside
Two lecture slips to know about
The DES slide reads “US encryption standard [NIST 1993]” and “block cipher with cipher block chaining”. The adoption date given earlier in the same lecture is 1977, so the 1993 citation is inconsistent. Cipher block chaining is also a mode of operation used with a block cipher and is not a property of DES itself. Both statements are kept here as the lecture gives them. The exam marks the lecture’s wording.
Check yourself
- Symmetric means one shared secret key for both directions, independent of the algorithm.
- Reducing mod n at any stage gives the same answer as reducing at the end.
hellowith key 15 givesWTAAD.- A polyalphabetic cipher cycles through several substitutions.
- DES is 56-bit key and 64-bit block. 3DES uses three keys. AES uses 128-bit blocks and 128, 192 or 256-bit keys.