Classical encryption Flashcards
What is cryptography?
The study of designing crypto-systems
What is cryptoanalysis?
The study of breaking cryptosystems
What is secret writing?
Transformation of data using a secret called the key
What can cryptography provide?
Confidentiality: A key is needed in order to read the message
Authentication/ (integrity): A key is needed in order to write the message
What does a cryptosystem consist of?
Plaintext
Ciphertext
Keys
Encryption function
Decryption (inverse function)
What is symmetric key cipher (private key cipher)?
Enc and Dec keys only known to sender and receiver
The key must be communicated over a secure channel,
single-key
P -> (key) -> C -> (key) -> P
What is asymmetric key cipher (public key)?
Each participant has private and public key
Used for encryption of messages, and creation of digital signatures
P -> (public key) -> C -> (private key) -> P
How does digital signatures work?
Message -> Hash
Sign w/private key
Verify with public key
What is brute force attack (exhaustive key search)?
An attack where the adversary tries all keys.
This attack cannot be prevented, so all cryptosystems must have enough keys to make this too difficult computationally.
Prevention of this attack is a minimum standard
What are the 4 types of attacks?
Known ciphertext: Know only C
Known plaintext: Know small amount of P, and its equivalent C
Chosen plaintext: Attacker can obtain the C of some chosen P. Has inside encryptor
Chosen ciphertext: Attacker can obtain some P of some chosen C. Has inside decryptor.
Which attacks should cryptosystems prevent, by the modern standard?
Chosen plaintext and chosen ciphertext
What is Kerckhoffs principle?
An attacker has complete knowledge of how the cryptosystem works. The key is the only unknown thing.
What is security through obscurity?
Systems that tries to be secure by going against Kerckhoffs principle. Meaning they try to stay secure by keeping parts of their cryptosystem hidden, and relying on this to be enough to be secure.
What is transposition?
The characters in the plaintext are mixed up with each other (permuted)
What is substitution?
Each character (or set of characters) is replaced by a different character (or set of characters)
How does transposition ciphers work?
Permutes characters usually in a fixed period d and permutation f
The plaintext can be seen as a matrix of rows of length d
Generally transposition ciphers can permute rows or columns and output in row or column order.
Key: the pair d and f, where f is a certain permutation of the plaintext, and d is the length of the permutation (period ?)
Each block of d characters is re-ordered using the permutation f
Do a cryptanalysis of transposition ciphers
Frequency of distribution of chars are the same.
If the period d is small, then the ciphers can be solved by hand using the process of anagramming (restoring disarranged characters to their original position).
we can guess the value of d and write the ciphertext in columns so that there are d columns
Knowledge of plaintext lamguage digrams and trigrams can optimize trials.
This process can be automated.
Describe substitution ciphers
Each char is replaced by a char in the Y-alphabet, as defined by a substitution table
Simple ciphers are called monoalphabetic sub. ciphers
What is the difference between transposition and substitution ciphers?
t permute plaintext chars, while s permute alphabet chars
How does the Caesar cipher work?
Move the ith letter of the alphabet to the (i+j)th letter.
Key: j
Enc: c_i = (ai + j) mod n
Dec ai = (ci - j) mod n
where n is the size of the alphabet
Do a cryptanalysis of the Caesar cipher
We only need to find where one of the most frequent chars is shifted to.
See what the key becomes when shifting the most common char to the theoretically most common alphabet char. Then use this key to decrypt.
This can be tried until the correct plaintext has been found
What is the random simple substitution cipher?
A cipher that assigns a random char of the alphabet to another char of the alphabet.
Enc and Dec are defined by the substitution table which randomly permutes the alphabet
If alphabet has 26 chars, there are 26! keys
Caesar is a special type of this cipher
Is still vulnerable to statistical methods of cryptoanalysis
What is polyalphabetic substitution?
Use multiple mappings from P to C
Effect: Smooth the frequency distribution, so direct frequency analysis is no longer effective
Typical ciphers are periodic substitution ciphers, based on a period d
How does random polyalphabetic substitution cipher work?
Key generation: Select block length d, generate d random simple substitution tables
Enc: Encrypt ith char, use sub-table number j where i≡j (mod d)
Dec: Use same sub-table as in enc in order to reverse simple substitution.
What is the vignere cipher?
Periodic substitution cipher based on shifted alphabets
K is specified by a sequence of characters:
K = k1 k2…k_(d-1)
ki gives the amount of shift in the ith alphabeth, i.e.
Enc(p) = (p + ki) mod n
Do a cryptoanalysis of the Vignere cipher
Identify period length
Attack seperately using d different substitution tables (alphabets). Since each substitution is just a shift, this is straight forward if there are sufficient ciphertext
What is a method that can be used to find the period of the vignere cipher?
Autocorrelation
Kasiski method
Index of coincidence
What do we need to consider in regards to an adversary who wishes to break a cryptosystem?
What resources the adversary has available:
- access to input/output
- computational capability
What the adversary is aiming to achieve
- retrieve the whole key
- distinguishing two messages (i.e. yes or no)
How can you identify the Vigenére period using autocorrelation?
- For a ciphertext C, compute the correlation between C and its shift Ci for all plausible values i of the period
- There is a better correlation between two texts with the same size shift than between two texts with different size shifts
- We therefore expect to see peaks in the value of Ci when i is a multiple of the period
- Plot result in histogram to identify the period
How can cryptoanalysis be done on Vigenére.
Identify the period length d
Divide the ciphertext into d different texts, and attack these separately using d different alphabets
Only need to find the shift for each alphabet (as in Caesar)
Can use frequency analysis on each text part
Describe the Kasiski method of finding the period of a Vigenére cipher
See if you can find sequences of repeating characters in the ciphertext
Calculate how many characters these are apart
If there are different distances between the repeating sequences, look for common divisors of the different lengths
What is the autokey cipher?
Starts off as Vigenére
Once the alphabet defined by the kay have been used once, use the plaintext to define subsequent alphabets
This cipher is not periodic
What is the running key cipher?
Uses a (practically) infinite set of alphabets from a shared key.
In practice, the shared key can be extracted from a book.
Often called a book cipher
What are the two most used symmetric ciphers?
AES and DES
What are the 2 requirements of conventional encryption?
Strong enc algorithm
Sender and receiver must obtain the secret key in a secure fashion, and the key must be kept secure
What feature of symmetric encryption makes it feasible for widespread use?
Only the key must be kept secret, not the algorithm
What is the principal security problem in symmetric encryption?
Keeping the key secret
What are the 3 dimensions for which cryptographic systems are characterized along?
Type of algorithm (substitution, transformation)
Number of keys (symmetric, private/public)
Way of processing plaintext (block, stream)
For what problem is cryptoanalysis most difficult?
Ciphertext only
What is an encryption algorithm designed to withstand?
Know-plaintext
When is an algorithm unconditionally secure?
The ciphertext generated does not contain enough information to determine uniquely corresponding plaintext, no matter how much ciphertext is available. Meaning no matter how much time the attacker has.
What algorithm provides unconditional security?
One-time pad
When is an algorithm said to be computationally secure?
Meets one of the requirements:
- Cost of breaking exceeds the value of the information
- Time it takes to break exceeds the useful lifetime of the information
Why is the ceasar cipher easy to break?
Only 25 keys need to be tried
The plaintext is recognizable
enc and dec algorithms are known
What can cause plaintext to not be easily recognizable?
If the input is abbreviated or compressed
How many permutations are there of a set of n elements?
n!
What is a monoalphabetic substitution cipher?
Uses a single cipher alphabet, meaning a single mapping from the plaintext alphabet to the ciphertext alphabet is used per message.
What are digrams?
Two-letter combinations
Why are monoalphabetic ciphers easy to break?
They reflect the frequency data of the original alphabet
What is the strength of the Hill-cipher?
It hides single-letter frequencies
3x3 hides digrams
It is string against ciphertext only attacks
What types of attack is the Hill cipher weak for?
known plaintext attack
Can use matrix equations to calculate the key
What are polyalphabetic substitution ciphers?
Uses different monoalphabetic substitutions through the plaintext
How does the Vigenére cipher hide frequency?
There are multiple ciphertext letters for each plaintext letter (depending on what character of the key is used each time).
Describe the one-time-pad
Uses a random key that is as long as the message
The key is only used to encrypt and decrypt a single message
Discarded after that
Each new message requires a new key of the same length as the message
Unbreakable - produces random output with no frequency preservation
What are the problem with the one-time-pad?
- Practical problem of making a large quantities of random keys
- Key distribution and protection
