1 files changed, 214 insertions, 0 deletions

diff --git a/ss2017/cryptography/Notes02.txt b/ss2017/cryptography/Notes02.txt
new file mode 100644
index 0000000..59da143
--- /dev/null
+++ b/ss2017/cryptography/Notes02.txt
@@ -0,0 +1,214 @@
+2 Principles of  cryptography (KL1.1, KL1.2, KL1.4, KL2)
+--------------------------------------------------------
+
+These considerations and similar ones applying to other historical
+ciphers have led to the principles for the design of cryptosystems.
+
+Before stating these we describe somewhat more formally what a
+(private-key) cryptosystem is. 
+
+A cryptosystem comprises three algorithms:
+
+- A key generation algorithm Gen which outputs a key according to some
+  format an probability distribution.
+
+- An encryption algorithm Enc which given plaintext m and key k
+  produces a ciphertext Enc_k(m)
+
+- A decryption algorithm Dec which given ciphertext c and key k
+  produces a plaintext Dec_k(m).
+
+The set of all keys possibly put out by the key generator Gen is
+called keyspace (K).  For every key k produced by Gen it must hold
+that Dec_k(Enc_k(m)) = m. There is also a finite set of possible
+messages M and ciphertexts C. Clearly, Gen must be randomized,
+otherwise it would always return the same key. Sometimes Enc is also
+randomized, i.e. ciphertexts may contain some random information and
+do not depend functionally on plaintext and key.
+
+One of the most important design principles is Kerckhoff's rule (19th
+century): Security of the cryptosystem should rely on secrecy of the
+key not on secrecy of the method. In other words, the cryptosystem
+should remain secure if everything about the three algorithms involved
+is publicly known. "No security through obscurity".
+
+In addition to this, the cryptosystem should withstand some or all of
+the following kinds of attack:
+
+Ciphertext only attack: an eavesdropper observes ciphertext and aims
+at determining the underlying plaintexts.
+
+Known plaintext attack (KPA): This is when the eavesdropper knows some
+ciphertext-plaintext pairs for one and the same key and tries to use
+this information to then decrypt additional ciphertexts (again
+w.r.t. the same key).
+
+Chosen plaintext attack (CPA): Here the adversary may prepare
+plaintexts of its choice and request the corresponding ciphertexts.
+
+Chosen ciphertext attack (CCA): Here the adversary can even request
+the decryption of ciphertexts of its choice.
+
+Modern cryptography, say since WW2, holds the following additional
+principles:
+
+
+Principle 1: Formulation of exact definitions
+
+Which notion of security is one aiming at?
+
+No adversary should be able to know the key ... But what if they can
+decrypt ciphertexts without knowing the key?
+
+No adversary should be able to decrypt any ciphertext unless they know
+the key. But what if they can find out some bits of the ciphertext,
+e.g. every second letter, or a block of letters somewhere in the
+middle?
+
+
+Principle 2: Reliance on precise assumptions
+
+Typically, security of a cryptosystem can be guaranteed only by making
+assumptions on the computational power of an adversary (with unlimited
+resources they could always try out all plaintexts) and also on the
+computational difficulty of solving certain algorithmic
+problems. Desirable as it would be to have unconditional security; if
+one has to work with assumptions one should at least state them
+precisely. Sometimes, security can only be proven for idealized
+versions of cryptosystems that use components not known to exist but
+which are believed to be "approximated" by existing components. Again,
+it is then important to clearly state what these idealized components
+or versions are.
+
+
+Principle 3: Rigorous proofs of security 
+
+Once the desired notion of security and the assumptions are clearly
+defined one should then establish a rigorous mathematical proof of
+conditional security.
+
+"Given that Assumption X is true, Construction Y is secure according
+to the given definition."
+
+As an example, we now look at perfect security in the sense of Shannon
+and see how Vernam's cipher (patented in 1919) implements it.
+
+
+In order to get around the fact that an adversary can always try out
+all possible plaintexts but that this kind of attack "doesn't count"
+Claude Shannon suggested to use probabilities: if one out of two
+messages is selected at random and the adversary gets to see the
+ciphertexts only it has a chance of no more than 50% of determining
+the plaintext correctly from the ciphertext. For cryptosystem Pi and
+adversary A we thus define the following
+
+Eavesdropping indistinguishability experiment PrivK^eav_{A,Pi}:
+
+  1. The adversary produces two messages m0, m1 from the message space M.
+  2. Gen is used to generate a (random) key k and a bit b <- {0,1} is
+     chosen uniformly at random (50/50). The (or rather a) ciphertext
+     c = Enc_k(m_b) is then given to A. 
+  3. A answers by outputting a bit b'.
+  4. The output of the experiment is defined 1 if b=b' and 0 otherwise.
+
+Definition (perfect secrecy): The encryption scheme Pi=(Gen,Enc,Dec)
+is perfectly secret if for all adversaries A it holds that
+
+                Pr[PrivK^eav_{A,Pi} = 1] = 0.5
+
+The following cryptosystems are not perfectly secure:
+
+A book cipher which uses a secret code book containing for each *word*
+another word to replace it. E,g. "bomb" gets enciphered as "cake" and
+"dollars" gets enciphered as "grams". Here the adversary could select
+m0="bomb bomb" and m1="dollar bomb". If the received ciphertext has
+the form c = x x then it will output b'=0 and if c = x y with x =/= y
+it goes for 1.
+
+The Vigenere cipher with key length uniformly chosen at random from
+{1,2} (and once the length is fixed keys also chosen at random).  The
+adversary can choose m0 = aa and m1=ab. If the ciphertext has the form
+xx it goes for b'=0. Otherwise it returns b'=1.
+
+Now, if b=0 then there is a 1/2+1/2*1/26 chance that the ciphertext
+has the form xx (key length 1 or key length 2 with equal letters) and thus
+the adversary is right with probability 1/2+1/52
+
+If b=1 then the adversary is right with probability 1-1/52 (the only
+way to be wrong is key length two and two key letters of distance 1).
+
+Thus, the total probability for A to be right is 1/2*(1/2+1/52) +
+1/2*(1-1/52) = 3/4.
+
+
+Proposition: Fix a cryptosystem Pi and suppose that plaintexts and
+keys are drawn according to some, not necessarily uniform
+distribution. The sytem Pi is perfectly secret if and only if
+
+               Pr[M=m | C=c] = Pr[M=m]
+
+for every fixed plaintext m and ciphertext c such that Pr[C=c] !=
+0.
+
+Proof (sketch): Suppose that Pr[M=m | C=c] != Pr[M=m] for some c and
+m. Since sum_m Pr[M=m | C=c] = sum_m Pr[M=m] = 1 (both are probability
+measures) there must exist m_0,m_1 (one of them m) such that Pr[M=m0 |
+C=c] < Pr[M=m0] and Pr[M=m1 | C=c] > Pr[M=m1].  By Bayes' theorem it
+follows that Pr[C=c|M=m0]<Pr[C=c] and Pr[C=c|M=m1]>Pr[C=c], thus in
+particular, Pr[C=c|M=m0] < Pr[C=c|M=m1].
+
+Now, consider the adversary who presents these messages m_0, m_1 and
+if the ciphertext returned is c
+then outputs b'=1, i.e. assume that the plaintext was not
+m0 and outputs b'=0 otherwise. Its success probability is 
+
+1/2*(1-Pr[C=c|M=m0]) + 1/2*Pr[C=c|M=m1] =
+1/2 + 1/2(Pr[C=c|M=m1] - Pr[C=c|M=m0])
+
+which is strictly above 1/2.
+
+For the converse, one uses the fact that all the adversary knows is
+the ciphertext, but according to the assumed equality Pr[M=m | C=c] =
+Pr[M=m] this does not help.                                  Q.E.D.
+
+Now, such perfectly secret cryptosystems exist indeed: for fixed n:N
+put M=C=K={0,1}^n and let Gen return k:K uniformly at random. The
+encryption function is Enc_k(m) = m+k and Dec_k(m) = m+k as well,
+where + denotes pointwise addition modulo 2 (XOR). For example, if n=5
+and k=11010 and m=11100 then Enc_k(m)=00110.
+
+This system is known as Vernam's cipher or "one time pad" the point
+being that its secrecy relies on the key being chosen afresh at random
+every time one wants to use the scheme. It can also be seen as a
+special case of the Vigenere cipher with the key being as long as the
+entire text to be enciphered.
+
+Proposition: The Vernam cipher is perfectly secret.
+
+Proof: This is because for a given plaintext m the ciphertexts are
+uniformly distributed, i.e., their distributions are identical and
+independent for m0 and m1. As a result, the adversary cannot have an
+advantage. Q.E.D.
+
+The obvious disadvantage of the one-time pad is the key length,
+nevertheless it is sometimes used, e.g. purportedly during the Cold
+War for secure communication between the White House and the Kremlin. 
+
+Unfortunately, this key length is the price of perfect secrecy:
+
+Theorem: If Pi is a perfectly secret cryptosystem with key space K and
+message space M then |K|>=|M|, i.e. there have to be at least as many
+possible keys as there are possible messages ("the key must be as long
+as the message").
+
+Proof: Suppose for a contradiction that |K|<|M| and that ciphertext
+c:C occurs with nonzero probability. Let M(c) = {m | Dec_k(c)=m for
+some k:K}.  We must have |M(c)|<=|K| since for each m:M(c) there is at
+least one k:K such that m=Dec_k(c) and the keys thus corresponding to
+distinct messages are distinct. If now |K|<|M| there must exist some
+m' not in M(c). But then Pr[M=m'|C=c] = 0 =/= Pr[M=m'], so the scheme
+is not perfectly secret.
+
+This result is due to Claude Shannon who gives in fact a more precise
+characterisation of perfect secrecy, see (KL2.4).
+