Week 2 Part 1

Question 1

Explain what perfect secrecy is? and what’s another name for it?

Answer 1

Information-Theoretic Secrecy

• No matter how powerful the attacker can be, secrecy holds!
• Perfect Secrecy is achievable but very expensive and not practical
• The ciphertext does not reveal any new information about the message

Question 2

What is one of the simplest ciphers that gives you perfect secrecy?

Answer 2

One-Time Pad (Vernam) Cipher.

Question 3

What are the pros and cons of the one-time pad (vernam) cipher?

Answer 3

Pros:
- ciphertext reveals no information about the plaintext (perfect secrecy)
Cons:
-key has to be as long as the plaintext and truly random
- Insecure against two-time pad (if same key used twice)

Question 4

How can you prove that the one time pad (vernam) cipher is secure?

Answer 4

Bayess theorem

Question 5

Encryption and Decryption of onetime pad vernam cipher?

Answer 5

• Encryption: Enck(m) = m ⊕ k
• Decryption: m = Deck(c) = c ⊕ k
  (you just XOR)

Question 6

What are the limitations of perfect secrecy?

Answer 6

• The key has to be truly random
• We must have |K| ≥ |M|
• Each key can only be used once

Question 7

What is computational secrecy?

Answer 7

• allow a very small (negligible) probability of security failure
• protect against “efficient” adversaries (not unrestrictedly powerful)

Question 8

What do modern ciphers use to overcome a two-time pad attack?

Answer 8

Nonce (- A non-repeating value for a given key)

Question 9

What is a pseudo-random generator?

Answer 9

PRG is an efficient deterministic algorithm that expands random n-bit strings into random-looking (pseudo-random) p(n)-bit strings

Question 10

What is one way to obtain a Pseudo-random generator?

Answer 10

Linear Feedback Shift Register (LFSR)

Question 11

How does a Linear Feedback Shift Register (LFSR) work?

Answer 11

• xoring different bits and the last bit looks random without the other bits

Question 12

For an l - bit LFSR, what is the maximal period we can hope for?

Answer 12

2^l -1 (2 to the power of l minus 1)

Question 13

Assuming we start from the state 0100, what is the state after 3 ticks?

Answer 13

0010

Question 14

After some ticks, an LFSR’s previous state will re-occur ⇒ the same bit stream (output) will repeat, when does 0010 start repeating?

Answer 14

After the 5th tick

Question 15

What are the limitations for LFSR?

Answer 15

• If the coefficient of the LFSR are known, by knowing 1st n-bits of the output, one can recover the starting state
• if the coefficient of the LFSR are not known, by knowing 1st 2n bits of the output, one can recover the starting state and the coefficients using (Linear Algebra powerful against linear functions)

Question 16

How to make an LFSR secure?

Answer 16

A number of LFSRs are combined using a non-linear function

Question 17

A sender has encrypted the character“C”(ASCII code: 67) using a stream cipher. In transit, an attacker (who does not know the used key) has XORed the ciphertext with the integer number 2. What character will the recipient get when they perform decryption on this altered ciphertext?

Answer 17

A. because a stream cipher encrypts with the equation c = m ⊕ PRG(k), if we substitute 67 for m we get: c= 67 ⊕ PRG(k). The attacker XOR this message with 2 so he gets c= (67 ⊕ PRG(k)) ⊕ 2. The equation to decrypt is m = c ⊕ PRG(k) . If we substitute the equation we got for c we get m = ((67 ⊕ PRG(k)) ⊕ 2)⊕ PRG(k). By using the commutative and associative property, we can simplify this expression to get m= 67 ⊕ 2, m= 65. The corresponding letter for that ASCII code is A

Question 18

Assume that in the one-time pad (Vernam) cipher we have replaced the XOR operation with the Boolean OR operation. If the probability of the plaintext bit being 0 is 0.3, i.e. Pr[M=0]=0.3, what is the probability of the ciphertext bit being 1, i.e. Pr[C=1]?

Answer 18

According to the boolean OR, the ciphertext is 1 if there is 1 in the plaintext or the key or both. so Pr[C=1] = Pr[M=1] + Pr[K=1] - Pr[M=1]*Pr[K=1] .

if we substitute in the values: Pr[C=1] = 0.7 + 0.5 - 0.7*0.5 =0.85. How I got the values: Pr[M=0] = 0.3 then Pr[M=1] = 0.7 as per the rule Pr[M=0] + Pr[M=1] = 1

Pr[K=1] = 0.5 because its equally likely to be any

Question 19

A 4-bit LFSR has the connection polynomial X^4+ X^3+ 1, what is the period of this LFSR? And how do u calculate

Answer 19

15, either manually by hand see how long it takes to repeat or code:
P.<x> = GF(2)[ ]</x>

c = x^4 + x^3 + 1

for i in range (4,16):
if c.divides(x^i + 1):
print(“The period is: “, i)
break

Question 20

An LFSR has a connection polynomial which is irreducible and is of degree 6, which of the following cannot be the period of this LFSR? 5, 63 , 7

Answer 20

The period of an irreducible polynomial C(X) of degree n divides 2^n − 1. 2^6-1 is 63. 7 and 63 divide 63 but 5 does not. so the answer is 5.

Question 21

When is a polynomial irreducible

Answer 21

A polynomial is irreducible if it cannot be factored

Question 22

C(X) = X4 + X2 + 1 is this polynomial irreducible and/or primitive (why or why not)?

Answer 22

C(X) here is reducible (hence cannot be primitive) since we can factor it since X4 + X2 + 1 = (X2 + X + 1)(X2 + X + 1)

Question 23

What are pros and cons of stream ciphers?

Answer 23

Pros;
- Efficient & can be easily implemented in hardware (Involve cheap operations, e.g. XORing, bit shifting)
- No need to buffer data before applying stream ciphers (e.g. useful when the plaintext length is not known beforehand)
- Low error propagation (An error in a ciphertext symbol affects one symbol of plaintext)
Cons:
- Does not offer integrity (Adversary can alter the underlying plaintext by altering ciphertext)
- Low Diffusion (One symbol in plaintext is mapped to one symbol in ciphertext)

Question 24

Can stream ciphers be used for cryptographic purposes?

Answer 24

NO, theyre not secure

Question 25

Whats the encryption and decyrption formula for a stream cipher

Answer 25

• Encryption: c = m ⊕ PRG(k)
• Decryption: m = c ⊕ PRG(k)

Question 26

(XOR 3 & 4th) for a bit LFSR.
If the starting state is 1000, what is the bit stream produced by the above LFSR after 6 clock ticks? You also need to show the state of the LFSR at each tick.

Answer 26

0100 0
0010 0
1001 0
1100 1
0110 0
1011 0
Output bit stream:
000100

Question 27

X^4 + X^3 + 1 What is the period (i.e. how many clock ticks before it cycles) of this LFSR?

Answer 27

The period of the LFSR is that of its connection polynomial. Since the degree of the polynomial in this case is irreducible and primitive, it will have a maximal period, i.e. 2^4 − 1 = 15