intro-to-cryptography (week 5) Flashcards
vignere cipher
1586
the idea is to use a collection of substitution cyphers - if there are n different ciphers then the first letter of the plaintext is encoded with the first cipher, the second with the second cipher, the nth with the nth cipher, and the n+1st letter is again encoded with the first cipher
the key is usually a word or a phrase of n letters, and the ith substitution cipher is obtained by shifting each letter ki positions in the alphabet
this flattens the frequencies and makes it much harder to do frequency analysis
enigma cipher
mechanical cipher where each letter typed would get mapped into a different letter depending of the key and current state of the machine which had several rotors that rotated at different paces
an identically wired machine at the other end could be used to decrypt
encryption scheme
clearly we can encode every message as a string of bits, i.e., an element of {0,1}^l for some l. and we can encode the key as a string of bits as well, i.e., an element of {0,1}^n.
thus, we can think of an encryption scheme as composed of two functions.
the encryption function E maps a secret key k E {0,1}^n and a message (known as plaintext) E {0,1}^l.
the decryption function D does the reverse operation, mapping the secret key k and the cypertext c back into the plaintext message m, which we write as m = D_k(c).
What is Auguste Kerckhoffs principle?
A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.
How should we restate Kerckhoff’s principle?
There is no secrecy without randomness.
two statements about probability that will get you much of what you need for cryptography
- for every fixed string x E {0,1}^n, if you toss a coin n times, the probability that the heads/tails pattern will be exactly x is 2^-n
- a probaility of 2^-128 is really really small
what are the two steps in generating randomness in actual cryptographic systems?
- first, we need to get some data that is unpredictable from the point of view of an attacker on our system (thermal noise / nuclear decay, for e.g.)
- estimate the entropy in it: roughly X has k bits of entropy if the probability that an attacker can guess X is at most 2^-k. then use a hash function to map X into a string of length k which is hopefully distributed uniformly at random.
digital signatures
goal: sign a message but prevent forgeries (copy pasting of a signature onto a different message)
digital cash
goal: prevent double spending (so i can’t copy a coin and spend it twice)
homomorphic encryptions
goal: compute on encrypted data without revealing inputs or outputs (confidentiality)
verifiable computation
goal: outsource a computation and quickly verify that the result is correct (integrity)
secure multiparty computation
goal: compute some function on inputs provided by multiple parties, such that no party learns the other’s inputs, on the final output (confidentiality)
cryptograph requires
- formal definitions of the property / guarantee
- mathematically precise threat models
- construction of a cryptosystem
- math proof showing correctness and security of constructions
kasiki test
- look for repeated sequences of characters
- english has a large repetition of bigrams or trigrams and over a long enough string of text these are likely to match up the same two or three letters in the key every so often
- by examining the distance between two repeated sequences we can guess the length of the keyword
plaintext space
set of all valid messages
{a,…,z}*: set of all strings with characters in “a” through “z”
Z_7: set of integers modulo 7
ciphertext space: set of all valid ciphertexts
key space: set of all valid keys
affine cipher
alphabet of N elements
key space tuple of two integers in Z_n
k = (a,b) E_R (Z_n, Z_n)
