1 files changed, 162 insertions, 0 deletions

diff --git a/ss2017/cryptography/Notes13.txt b/ss2017/cryptography/Notes13.txt
new file mode 100644
index 0000000..b8e5f0a
--- /dev/null
+++ b/ss2017/cryptography/Notes13.txt
@@ -0,0 +1,162 @@
+
+
+13 Diffie-Hellman key exchange and RSA
+--------------------------------------
+
+
+Diffie Hellman
+- - - - - - - -
+
+As already mentioned, the Diffie-Hellman key exchange system allows
+two people, say Alice and Bob, who do not share any secret information
+to obtain a shared secret key (which can then for example be used for
+subsequent private key cryptography). It thus avoids the need for the
+sharing of secret keys which is difficult in practice and involves
+trusted third parties or similar (see KL9.1-3 for a discussion).
+
+We now formalize what should be expected from such a key exchange protocol: 
+
+The key exchange experiment KE^eav_{A,Pi}(n):
+
+1. Two parties both holding n execute the protocol Pi. This results in
+   a transcript trans containing all messages exchanged and a string
+   ("key") k:{0,1}^n that is output by both parties. Thus, both
+   parties must output the same key.
+
+2. b<-{0,1}. if b then k':=k else k'<-{0,1}^n
+3. Adversary A is given trans and k' and outputs a bit b'.
+4. Output = 1 iff b'=b
+
+The protocol Pi is deemed secure if the success probability for any
+prob.polytime adversary A is bounded by 1/2+negl(n).
+
+
+The Diffie-Hellmann protocol Pi for some cyclic group (generating
+algorithm) G() now works as follows:
+
+1. Alice runs (G,q,g) := G(n) and sends (G,q,g) to Bob. 
+2. Alice chooses x<-Z_q and computes h1:=g^x
+3. Alice sends (G,q,g,h1) to Bob
+4. Bob chooses y<-Z_q and sends h2:=g^y to Alice. Bob then outputs k_B:=h1^x
+5. Alice outputs k_A:=h2^x /* Note that k_A=k_B=g^{xy} */
+
+We will now show that the Diffie-Hellman protocol is secure under the
+assumption that DDH is hard for the group in question and the further
+assumption that the random key k' chosen in the KE^eav experiment is a
+random element of G rather than an arbitrary random string. Let us
+call KE'^eav the thus modified experiment. We note that a random group
+element can be taken of the form g^z for z<-Z_q. 
+
+We now have
+
+Pr(KE'^eav_{A,Pi}(n)=1) = 1/2*Pr(KE'^eav(n)=1 | b=1) + 1/2*Pr(KE'^eav(n)=1 | b=0) =
+1/2*(Pr(A(G,g,q,g^x,g^y,g^{xy})=1)+ Pr(A(G,g,q,g^x,g^y,g^z)=0))  =
+1/2+1/2*(Pr(A(G,g,q,g^x,g^y,g^{xy})=1)- Pr(A(G,g,q,g^x,g^y,g^z)=1))  <=
+1/2+1/2*|Pr(A(G,g,q,g^x,g^y,g^{xy})=1)- Pr(A(G,g,q,g^x,g^y,g^z)=1)|  <=
+1/2 + 1/2*negl(n) /* assuming hardness of DDH for G() */
+
+We remark that while (under assumptions) Diffie-Hellman is secure
+against passive eavesdroppers it is vulnerable against more active
+adversaries that may also send, modify, and swallow messages during
+the run of the protocol. Achieving security against those requires
+some means of authenticating messages sent between the parties; a
+precise formulation of the additional assumptions needed for this is
+beyond the scope of this book.
+
+
+
+Public key cryptosystems
+- - - - - - - - - - - - - 
+
+We give a formal definition of a public key cryptosystem and its
+security.
+
+
+Definition: a public key cryptosystem Pi comprises
+
+-) a (probabilistic) key generation algorithm Gen() which given
+ security parameter n outputs a pair of keys (pk,sk) /* public, secret
+ */
+
+-) a (probabilistic) encryption algorithm which given plaintext m from
+some message space and the public key pk produces a ciphertext c:
+c<-nc_pk(m)
+
+-) a deterministic decryption algorithm which given ciphertext c and
+the secret key sk produces a plaintext m<-Dec_sk(c) in such a way that
+if c<-Enc_pk(m) then Dec_pk(End_sk(m)) = m.
+
+
+Definition: A public key scheme Pi is semantically secure in the
+presence of an eavesdropper if the for all (prob. polytime)
+adversaries A the success probability in the following experiment is
+bounded by 1/2+negl(n). 
+
+Experiment PubK^eav_{A,Pi}(n):
+
+1. (pk,sk)<-Gen(n)
+2. Adversary A is given pk and outputs messages m0 m1
+3. b <- {0,1}; c <- Enc_pk(m_b); c is given to A
+4. A outputs a bit b'
+5. Outcome is 1 if b=b' and 0 otherwise    End of definition
+
+
+We notice that this is just like semantic security in the private key
+setting except that the adversary has access to the public key which
+after all is supposed to be public. This means that, since by
+Kerckhoff's principle, the encryption algorithm is also public, the
+adversary has access to an encryption oracle and thus---in the public
+key setting---semantic security in the presence of an eavesdropper
+(the one above) is as powerful as cpa security.
+
+This has the consequence that no public key cryptosystem in which
+Enc_pk() is deterministic can be semantically secure. Indeed, all the
+adversary has to do in this case is to precompute the encryptions of
+its chosen messages m0 and m1. 
+
+We remark that a semantically secure public key cryptosystem can be
+combined with any cps-secure private key system by first using the
+public key to transmit a secret key. This is known as *hybrid
+encryption*. One can show (Theorem 10.13 of KL) that hybrid encryption
+yields semantically secure public-key encryption schemes.
+
+
+
+RSA cryptosystem
+- - - - - - - - -
+
+For this reason, the "textbook RSA" cryptosystem, as indicated in the
+last chapter, is actually insecure. In order to make it work, it must
+be enhanced with randomization for example as follows.
+
+Fix a length function l(n).
+
+Gen(): On input n run GenRSA(n) to obtain (N,e,d). Output
+       pk=(N,e) and sk=(N,d)
+Enc(): On input m:{0,1}^l(n) and pk=(N,e) choose
+       r<-{0,1}^{||N||-l(n)-1} and output c=(r||m)^e mod N
+       /* the -1 is there to make sure that r||m is in Z_N^* */
+Dec(): On input c and sk=(N,d) compute m'=c^d mod N and output the l(n)
+       low-order, i.e. rightmost, bits of m'
+
+Now, if the "padding" r is too short, then this does not help because
+an adversary could try out all possible values for r. It is believed
+that when r has a length comparable to |m|, then the above scheme is
+secure (relative to the RSA assumption), but unfortunately, no proof
+has been found. According to KL (Theorem 10.19) one can show that the
+scheme is secure when l(n)=O(log(n)), again under the RSA
+assumption. Note that this means that in order to increase the message
+size by just one bit one has to double the security parameter and
+hence the length of the modulus N and the ciphertexts. 
+
+In practice, one does not want to waste so much bandwidth on the
+padding and uses heuristic schemes like e.g. RSA-PKCS#1v1.5 which uses
+a random padding string of length at least 64bit.
+
+Another, more modern, method is RSA-OAEP which mixes the padding with
+the actual plaintext by way of a Feistel network of cryptographic hash
+functions. Intuitively, this makes the input to the actual RSA
+encryption look like a random string which then makes the RSA
+assumption applicable. Viewed more practically, it prevents attacks
+which only recover parts of the plaintext. In the random oracle model
+(Lecture 16) RSA-OAEP can be proved semantically secure.