Exam 2 Flashcards
how do you get p[4|O] in the dice problem?
Consider all odd cases, look for sums of 4 within those cases
how do you get p[a|1]?
Use bayes theorem:
p[a|1] = ( p[1|a] p[a] ) / p[1]
how do you get p[1|a]?
refer to the table, look for 1 under a, add up the probabilities of the keys with 1
formula for joint probability
p[x,y]=p[x|y]p[y]
OR
p[x, y]=p[y|x]p[x]
how to get l(f)
multiply the number of bits with the probability
(if only the frequency was provided, calculate the probability by dividing by the total)
find H[P|1]
-1/ln2(p[a|1]ln(p[a|1])+p[b|1]ln(p[b|1])+…)
information gain
( H(P)-H(P|C) ) / H(P)
what is |P| and |K| for a substitution cipher?
|P|=26, |K|=26!
what is |P| and |K| for a vigenere cipher?
|P|=26^m, |K|=26^m
what is |P| and |K| for a hill cipher?
|P|=26^m, |K|=26^m^2
what is |P| and |K| for a affine cipher?
|P|=26, |K|=312
R_L = ?
0.75
formula for unicity distance?
ln|K| / (R_L ln|P|)
formula for the number of spurious keys? s_n
|K|/ (|P|^nR_L) - 1
n = size of the cipher text
memory requirement for s-box?
l2^l
l = number of inputs
how would you get p[1] given a table?
multiply the probability of every key where 1 appears with the probability of the letter it corresponds to
H(P) of a table?
use probabilities of a,b,c in entropy formula
get H[P|C]
do p[1]H[P|1]+p[2]H[P|2]+…
division algorithm
- make columns for u1, v1, u2, v2, u3, v3, q
- The first row should be 1, 0, 0, 1, (larger input), (smaller input), 0
- For the next row, former v’s become u. Every u becomes u - (v *q). Q will be u3/v3 without the remainder
- Repeat 3 until v3 = 0. GCD = u3. Multiplicative inverse of the smaller number in the mod of the larger number is u2
how to write a decryption rule given an encryption rule
- encryption function is: e(x) = (ax+b) mod 26
- key is (a, b)
- decryption function: d_k(y)=a^{-1}(y-b)
- dont forget to mod out!!!
how to decrypt autokey cipher?
- Write the value equivalents of each letter
- Start by subtracting the key value from the first letter, subtract the resulting value from the next letter and onwards
find the inverse of a matrix in Z_26
K^{-1}=(detK)^{-1}\begin{pmatrix}
d & -b
-c & a
\end{pmatrix}
determinant is ad - bc
formula for period of key stream
2^m -1
m = degree
How to apply MixColumn
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
perfect secrecy
p[x|y] = p[x] for x in P and y in C
Compute N_D
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
Compute R_P
N_D / 2^m
m = number of bits
baby horst cipher
1) first half of plaintext is L0, other half is R0
2) L1 = R0
3) R1 = L0 + f(R0, K1)
SDES/DES: how to handle inputs for s-box
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
H(P|C)
H(P|C) = H(P, C) - H(C)
for modular equations, when is there more than one solution or no solution?
when gcd does not equal 1
formula for hash functions
B = a^x mod p
x = L_a(B)
random oracle model
E = 1 - (1 - 1/M)^Q
Q = number of tags
M = possible messages
