W1 Flashcards
What are the two motivations of cryptography?
Communication channels:
- Spying on our data
- Modifying our data
Name three cryptographic applications in daily life
Credit cards, EC-cards, and access codes.
Electronic passports or ID cards.
Internet commerce, online tax declarations, webmail.
Give examples of applications that use encryption for communication
Facebook, WhatsApp, iMessage, PGP encrypted email, Signal, Torbrowser
What are the three security goals of cryptography?
- Confidentiality: Eve cannot read the message
- Integrity: Eve cannot modify the message without detection
- Authenticity: Eve cannot impersonate the sender
What is the simplest case of encryption?
Alice and Bob share a secret key that Eve does not know.
Encryption takes plaintext m and produces ciphertext c, while decryption does the inverse
What is cryptology?
The science that studies mathematical techniques in order to provide secrecy, authenticity, and related properties for digital information
What is cryptanalysis?
The study of security and analysis of cryptosystems, including implementation of attacks
What is cryptography?
The design of cryptosystems including their implementation and use in larger protocols
How is cryptology related to cryptography and cryptanalysis?
Cryptology = Cryptography + Cryptanalysis
How does symmetric key cryptography work?
Alice and Bob share a secret key that Eve does not know.
Encryption takes plaintext m and produces ciphertext c, while decryption takes c and produces m.
How does public-key cryptography work?
Each user has two keys, a public and a private key.
Everyone knows the public key.
Secure systems make it computationally impossible to recover the private key from the public key.
Alice uses Bob’s public key to encrypt plaintext m and Bob uses his private key to decrypt the ciphertext c.
How do public key signatures work?
Alice has a private and public key.
Alice signs messages using her privaste key and other people verify it using her public key.
Security ensured by the fact that nobody can generate messages valid under Alice’s public key without Alice’s private key.
How does the Caesar Cipher work?
A substitution cipher that shifts each letter in the plaintext by a fixed number of positions in the alphabet.
For instance, “A” becomes “D” with a shift of 3.
The process wraps around at the end of the alphabet.
What is a substitution cipher?
What is knowledge of the key?
How many different different keys for an alphabet of 26 letters?
Each letter is replaced by a symbol
Full alphabet in symbol
26!
What is the keyspace?
What is the minimum requirement for security concerning a key space?
The set from which the keys are drawn
Too large to search
How can frequency analysis be used for key search?
E.g., in English, the frequency distribution of letters shows a very strong peak at E, with strong peaks at T,A,O,I and N
What does it mean for a cipher to be information-theoretically secure?
That no information about the plaintext is in the ciphertext
How does the one-time pad work?
What is a downside to it?
You have the message as a string of l bits.
You choose a key at random also consisting of l bits.
You get the ciphertext by adding the key to the message modulo 2.
Key must be as long as message, making scheme unusable for many situations.
How does Vigenere work?
The Vigenère cipher uses a keyword to determine the shift for each letter in the plaintext.
The shifts are applied cyclically across the plaintext, with each letter shifted by the amount indicated by the corresponding letter in the keyword.
EXAMPLE:
Plaintext: HELLO
Keyword: KEY
Steps:
Repeat the keyword to match the length of the plaintext: Keyword: KEYKE
Convert the keyword letters to numerical shifts (A=0, B=1, …, Z=25): K = 10, E = 4, Y = 24
Shift each letter in the plaintext by the corresponding keyword letter shift:
H (7) + K (10) = R
(17)E (4) + E (4) = I
(8)L (11) + Y (24) = J 35 → wrap around → 9 = J)
L (11) + K (10) = V
(21)O (14) + E (4) = S (18)
Ciphertext: RIJVS
How can frequency analysis be carried out on Vigenere>
Size of key |k| must be known.
First shifting distance found by frequency analysis on letters 1, |k|+1, 2|k|+1, etc..
How does playfair cipher work?
Uses a keyword to create a 5x5 grid of letters for encryption and decryption
The keyword is written row-wise from the top left, omitting duplicate letters’’
The grid contains each letter of the alphabet exactly once, with “I” and “J” sharing a position to fit all letters
After the keyword, the remaining letters of the alphabet are filled in order
Repeated letters in the keyword are skipped
This grid is then used to encrypt or decrypt digraphs (pairs of letters) in the plaintext
Example grid with the keyword “CRYPTO”:
C R Y P T
O A B D E
F G H I/J K
L M N Q S
U V W X Z
How is message processing done in playfair?
Split message into pairs of letters starting from the left.
Insert X when encountering a pair of identical letters
Append X if there is a single letter at the end
E.g., HELLOBOB HE LX LO BO BX
What are the three cases for encryption for Playfair?
- If two letters appear in the same row, encrypt each of the two letter to the letter to the right of it.
- If the two letters appear in the same column, encrypt each of the two letters to the letter below it.
- If the two letters span a rectangle in the grid, encrypt each of them to the letter in the same row and opposite corner.
How does the Hill cipher work?
Encode the letters of the plaintext into numbers in [0,25]
Secret key S is an n by n matrix over Z/26 which is invertible.
Let plaintext be written as vector (m1,m2,…,mn) in (Z/26)^n
m gets encrypted into ciphertext c^T = Sm^t
to decrypt, we compute m^T = S^-1c^T
