Classical encryption

Question 1

What is cryptography?

Answer 1

The study of designing crypto-systems

Question 2

What is cryptoanalysis?

Answer 2

The study of breaking cryptosystems

Question 3

What is secret writing?

Answer 3

Transformation of data using a secret called the key

Question 4

What can cryptography provide?

Answer 4

Confidentiality: A key is needed in order to read the message

Authentication/ (integrity): A key is needed in order to write the message

Question 5

What does a cryptosystem consist of?

Answer 5

Plaintext
Ciphertext
Keys
Encryption function
Decryption (inverse function)

Question 6

What is symmetric key cipher (private key cipher)?

Answer 6

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

Question 7

What is asymmetric key cipher (public key)?

Answer 7

Each participant has private and public key

Used for encryption of messages, and creation of digital signatures

P -> (public key) -> C -> (private key) -> P

Question 8

How does digital signatures work?

Answer 8

Message -> Hash

Sign w/private key

Verify with public key

Question 9

What is brute force attack (exhaustive key search)?

Answer 9

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

Question 10

What are the 4 types of attacks?

Answer 10

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.

Question 11

Which attacks should cryptosystems prevent, by the modern standard?

Answer 11

Chosen plaintext and chosen ciphertext

Question 12

What is Kerckhoffs principle?

Answer 12

An attacker has complete knowledge of how the cryptosystem works. The key is the only unknown thing.

Question 13

What is security through obscurity?

Answer 13

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.

Question 14

What is transposition?

Answer 14

The characters in the plaintext are mixed up with each other (permuted)

Question 15

What is substitution?

Answer 15

Each character (or set of characters) is replaced by a different character (or set of characters)

Question 16

How does transposition ciphers work?

Answer 16

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

Question 17

Do a cryptanalysis of transposition ciphers

Answer 17

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.

Question 18

Describe substitution ciphers

Answer 18

Each char is replaced by a char in the Y-alphabet, as defined by a substitution table

Simple ciphers are called monoalphabetic sub. ciphers

Question 19

What is the difference between transposition and substitution ciphers?

Answer 19

t permute plaintext chars, while s permute alphabet chars

Question 20

How does the Caesar cipher work?

Answer 20

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

Question 21

Do a cryptanalysis of the Caesar cipher

Answer 21

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

Question 22

What is the random simple substitution cipher?

Answer 22

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

Question 23

What is polyalphabetic substitution?

Answer 23

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

Question 24

How does random polyalphabetic substitution cipher work?

Answer 24

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.

Question 25

What is the vignere cipher?

Answer 25

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

Question 26

Do a cryptoanalysis of the Vignere cipher

Answer 26

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

Question 27

What is a method that can be used to find the period of the vignere cipher?

Answer 27

Autocorrelation
Kasiski method
Index of coincidence

Question 28

What do we need to consider in regards to an adversary who wishes to break a cryptosystem?

Answer 28

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)

Question 29

How can you identify the Vigenére period using autocorrelation?

Answer 29

1. For a ciphertext C, compute the correlation between C and its shift Ci for all plausible values i of the period
2. There is a better correlation between two texts with the same size shift than between two texts with different size shifts
3. We therefore expect to see peaks in the value of Ci when i is a multiple of the period
4. Plot result in histogram to identify the period

Question 30

How can cryptoanalysis be done on Vigenére.

Answer 30

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

Question 31

Describe the Kasiski method of finding the period of a Vigenére cipher

Answer 31

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

Question 32

What is the autokey cipher?

Answer 32

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

Question 33

What is the running key cipher?

Answer 33

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

Question 34

What are the two most used symmetric ciphers?

Answer 34

AES and DES

Question 35

What are the 2 requirements of conventional encryption?

Answer 35

Strong enc algorithm

Sender and receiver must obtain the secret key in a secure fashion, and the key must be kept secure

Question 36

What feature of symmetric encryption makes it feasible for widespread use?

Answer 36

Only the key must be kept secret, not the algorithm

Question 37

What is the principal security problem in symmetric encryption?

Answer 37

Keeping the key secret

Question 38

What are the 3 dimensions for which cryptographic systems are characterized along?

Answer 38

Type of algorithm (substitution, transformation)

Number of keys (symmetric, private/public)

Way of processing plaintext (block, stream)

Question 39

For what problem is cryptoanalysis most difficult?

Answer 39

Ciphertext only

Question 40

What is an encryption algorithm designed to withstand?

Answer 40

Know-plaintext

Question 41

When is an algorithm unconditionally secure?

Answer 41

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.

Question 42

What algorithm provides unconditional security?

Answer 42

One-time pad

Question 43

When is an algorithm said to be computationally secure?

Answer 43

Meets one of the requirements:

1. Cost of breaking exceeds the value of the information
2. Time it takes to break exceeds the useful lifetime of the information

Question 44

Why is the ceasar cipher easy to break?

Answer 44

Only 25 keys need to be tried

The plaintext is recognizable

enc and dec algorithms are known

Question 45

What can cause plaintext to not be easily recognizable?

Answer 45

If the input is abbreviated or compressed

Question 46

How many permutations are there of a set of n elements?

Answer 46

n!

Question 47

What is a monoalphabetic substitution cipher?

Answer 47

Uses a single cipher alphabet, meaning a single mapping from the plaintext alphabet to the ciphertext alphabet is used per message.

Question 48

What are digrams?

Answer 48

Two-letter combinations

Question 49

Why are monoalphabetic ciphers easy to break?

Answer 49

They reflect the frequency data of the original alphabet

Question 50

What is the strength of the Hill-cipher?

Answer 50

It hides single-letter frequencies

3x3 hides digrams

It is string against ciphertext only attacks

Question 51

What types of attack is the Hill cipher weak for?

Answer 51

known plaintext attack

Can use matrix equations to calculate the key

Question 52

What are polyalphabetic substitution ciphers?

Answer 52

Uses different monoalphabetic substitutions through the plaintext

Question 53

How does the Vigenére cipher hide frequency?

Answer 53

There are multiple ciphertext letters for each plaintext letter (depending on what character of the key is used each time).

Question 54

Describe the one-time-pad

Answer 54

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

Question 55

What are the problem with the one-time-pad?

Answer 55

1. Practical problem of making a large quantities of random keys
2. Key distribution and protection