Hill cipher, stream ciphers and the One Time Pad Flashcards
What is the hill cipher?
Polygram cipher (polygraphic cipher)
Perform a linear transformation on d number of plaintext characters, to get d ciphertext characters.
Enc:
Multiply a d x d matrix K by the block of plaintext P
C = KP
Dec:
Multiply the matrix K⁻1 by the block of the ciphertext C
P = K⁻1C
What is a weakness of the Hill cipher?
It is linear, known plaintext attacks are easy
Do a cryptanalysis of the Hill cipher
Known plaintext are possible given d number of plaintext ciphertext matching blocks.
We are given d blocks of matching P and C,
Then we are able to C = KP for K
And use K to get rest of plaintext:
P = K⁻1*C
What are stream filters?
Characterised by the generation of a keystream of any required length.
Each element of the keystream encrypts one or more ciphertext characters
Usually symmetric ciphers
Keystream must have good randomness properties
What is a synchronous stream cipher?
Keystream generated independently of the P
How does enc and dec in synchronous stream ciphers work?
Enc: c(t) = p(t) XOR s(t)
Dec: p(t) = c(t) XOR s(t)
What is the one time pad?
Key: truly random sequence of characters, independently generated
Each character in key is used one time only
non-periodic binary synchronous stream cipher
Provides perfect secrecy
Define perfect secrecy
Message set: {M1, M2, …, Mk}
Ciphertext set: {C1, C2, …, CK}
P(Mi|Cj): Probability of Mi was encrypted given that Cj was observed
Perfect secrecy:
P(Mi|Cj) = P(Mi)
How does enc and dec work in the one time pad?
Enc:
ci = (pi + ki) mod 26
Dec:
pi = (ci -ki) mod 26
mod 26 when using roman alphabeth
With P = HELLO
K = EZABD
What is C?
LDLMR
Given C, note that P can be any 5-letter message
How does enc and dec work in binary one time pad?
Enc:
ci = pi XOR ki
Dec:
pi = ci XOR ki
What are some properties of perfect secrecy, in regards to the number of keys?
Any cipher with perfect secrecy, myst have as many keys as there are messages.
This makes one-time pad the only unbreakable cipher.
What is the main problem with one time pad?
Key distribution and random keys
Dealing with keys are difficult when these are so large
What is visual cryptography?
Application of one time pad
Split image into two shares
Dec: Overlaying the twoshares
Each pixel is shared in a random way
Each share reveals no information about the image
How does encryption work in visual cryptography?
Generate a one time pad P (random string of bits) with length equals to number of pixels in the image
Generate an image share by replacing each bit using these sub-pixels patterns:
0 bit: black-white
1 bit: white-black
Generate the other share as follows:
- The same as the first share for all the white pixels of the image
- The opposite of the first share for all black pixels of the image
