Exam 2

Question 1

how do you get p[4|O] in the dice problem?

Answer 1

Consider all odd cases, look for sums of 4 within those cases

Question 2

how do you get p[a|1]?

Answer 2

Use bayes theorem:
p[a|1] = ( p[1|a] p[a] ) / p[1]

Question 3

how do you get p[1|a]?

Answer 3

refer to the table, look for 1 under a, add up the probabilities of the keys with 1

Question 4

formula for joint probability

Answer 4

p[x,y]=p[x|y]p[y]
OR
p[x, y]=p[y|x]p[x]

Question 5

how to get l(f)

Answer 5

multiply the number of bits with the probability
(if only the frequency was provided, calculate the probability by dividing by the total)

Question 6

find H[P|1]

Answer 6

-1/ln2(p[a|1]ln(p[a|1])+p[b|1]ln(p[b|1])+…)

Question 7

information gain

Answer 7

( H(P)-H(P|C) ) / H(P)

Question 8

what is |P| and |K| for a substitution cipher?

Answer 8

|P|=26, |K|=26!

Question 9

what is |P| and |K| for a vigenere cipher?

Answer 9

|P|=26^m, |K|=26^m

Question 10

what is |P| and |K| for a hill cipher?

Answer 10

|P|=26^m, |K|=26^m^2

Question 11

what is |P| and |K| for a affine cipher?

Answer 11

|P|=26, |K|=312

Question 12

R_L = ?

Answer 12

0.75

Question 13

formula for unicity distance?

Answer 13

ln|K| / (R_L ln|P|)

Question 14

formula for the number of spurious keys? s_n

Answer 14

|K|/ (|P|^nR_L) - 1
n = size of the cipher text

Question 15

memory requirement for s-box?

Answer 15

l2^l
l = number of inputs

Question 16

how would you get p[1] given a table?

Answer 16

multiply the probability of every key where 1 appears with the probability of the letter it corresponds to

Question 17

H(P) of a table?

Answer 17

use probabilities of a,b,c in entropy formula

Question 18

get H[P|C]

Answer 18

do p[1]H[P|1]+p[2]H[P|2]+…

Question 19

division algorithm

Answer 19

1. make columns for u1, v1, u2, v2, u3, v3, q
2. The first row should be 1, 0, 0, 1, (larger input), (smaller input), 0
3. For the next row, former v’s become u. Every u becomes u - (v *q). Q will be u3/v3 without the remainder
4. Repeat 3 until v3 = 0. GCD = u3. Multiplicative inverse of the smaller number in the mod of the larger number is u2

Question 20

how to write a decryption rule given an encryption rule

Answer 20

1. encryption function is: e(x) = (ax+b) mod 26
2. key is (a, b)
3. decryption function: d_k(y)=a^{-1}(y-b)
4. dont forget to mod out!!!

Question 21

how to decrypt autokey cipher?

Answer 21

1. Write the value equivalents of each letter
2. Start by subtracting the key value from the first letter, subtract the resulting value from the next letter and onwards

Question 22

find the inverse of a matrix in Z_26

Answer 22

K^{-1}=(detK)^{-1}\begin{pmatrix}
d & -b
-c & a
\end{pmatrix}

determinant is ad - bc

Question 23

formula for period of key stream

Answer 23

2^m -1
m = degree

Question 24

How to apply MixColumn

Answer 24

1) convert matrix values to polynomials
2) multiply 2x2 matrix of [1 x^2 x^2 1] with the matrix
3) mod out, divide each polynomial by the field given

Question 25

perfect secrecy

Answer 25

p[x|y] = p[x] for x in P and y in C

Question 26

Compute N_D

Answer 26

1) for the x* column: add the bits of the input value for each input in the s-box
2) for the y* column: use the s-box and x* as the input
3) add y + y* to get y’
4) look for the number of values in y’ that equal the output value

Question 27

Compute R_P

Answer 27

N_D / 2^m
m = number of bits

Question 28

baby horst cipher

Answer 28

1) first half of plaintext is L0, other half is R0
2) L1 = R0
3) R1 = L0 + f(R0, K1)

Question 29

SDES/DES: how to handle inputs for s-box

Answer 29

DES:
1) 1st and last bit plus 1 represents the row
2) middle bits + 1 represent the column
SDES:
1) 1st bit + 1 represents the row
2) last 3 bits + 1 represent the column

Question 30

H(P|C)

Answer 30

H(P|C) = H(P, C) - H(C)

Question 31

for modular equations, when is there more than one solution or no solution?

Answer 31

when gcd does not equal 1

Question 32

formula for hash functions

Answer 32

B = a^x mod p
x = L_a(B)

Question 33

random oracle model

Answer 33

E = 1 - (1 - 1/M)^Q
Q = number of tags
M = possible messages