diff options
Diffstat (limited to 'ss2017/cryptography/Notes13.txt')
-rw-r--r-- | ss2017/cryptography/Notes13.txt | 162 |
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 @@ | |||
1 | |||
2 | |||
3 | 13 Diffie-Hellman key exchange and RSA | ||
4 | -------------------------------------- | ||
5 | |||
6 | |||
7 | Diffie Hellman | ||
8 | - - - - - - - - | ||
9 | |||
10 | As already mentioned, the Diffie-Hellman key exchange system allows | ||
11 | two people, say Alice and Bob, who do not share any secret information | ||
12 | to obtain a shared secret key (which can then for example be used for | ||
13 | subsequent private key cryptography). It thus avoids the need for the | ||
14 | sharing of secret keys which is difficult in practice and involves | ||
15 | trusted third parties or similar (see KL9.1-3 for a discussion). | ||
16 | |||
17 | We now formalize what should be expected from such a key exchange protocol: | ||
18 | |||
19 | The key exchange experiment KE^eav_{A,Pi}(n): | ||
20 | |||
21 | 1. Two parties both holding n execute the protocol Pi. This results in | ||
22 | a transcript trans containing all messages exchanged and a string | ||
23 | ("key") k:{0,1}^n that is output by both parties. Thus, both | ||
24 | parties must output the same key. | ||
25 | |||
26 | 2. b<-{0,1}. if b then k':=k else k'<-{0,1}^n | ||
27 | 3. Adversary A is given trans and k' and outputs a bit b'. | ||
28 | 4. Output = 1 iff b'=b | ||
29 | |||
30 | The protocol Pi is deemed secure if the success probability for any | ||
31 | prob.polytime adversary A is bounded by 1/2+negl(n). | ||
32 | |||
33 | |||
34 | The Diffie-Hellmann protocol Pi for some cyclic group (generating | ||
35 | algorithm) G() now works as follows: | ||
36 | |||
37 | 1. Alice runs (G,q,g) := G(n) and sends (G,q,g) to Bob. | ||
38 | 2. Alice chooses x<-Z_q and computes h1:=g^x | ||
39 | 3. Alice sends (G,q,g,h1) to Bob | ||
40 | 4. Bob chooses y<-Z_q and sends h2:=g^y to Alice. Bob then outputs k_B:=h1^x | ||
41 | 5. Alice outputs k_A:=h2^x /* Note that k_A=k_B=g^{xy} */ | ||
42 | |||
43 | We will now show that the Diffie-Hellman protocol is secure under the | ||
44 | assumption that DDH is hard for the group in question and the further | ||
45 | assumption that the random key k' chosen in the KE^eav experiment is a | ||
46 | random element of G rather than an arbitrary random string. Let us | ||
47 | call KE'^eav the thus modified experiment. We note that a random group | ||
48 | element can be taken of the form g^z for z<-Z_q. | ||
49 | |||
50 | We now have | ||
51 | |||
52 | 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) = | ||
53 | 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)) = | ||
54 | 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)) <= | ||
55 | 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)| <= | ||
56 | 1/2 + 1/2*negl(n) /* assuming hardness of DDH for G() */ | ||
57 | |||
58 | We remark that while (under assumptions) Diffie-Hellman is secure | ||
59 | against passive eavesdroppers it is vulnerable against more active | ||
60 | adversaries that may also send, modify, and swallow messages during | ||
61 | the run of the protocol. Achieving security against those requires | ||
62 | some means of authenticating messages sent between the parties; a | ||
63 | precise formulation of the additional assumptions needed for this is | ||
64 | beyond the scope of this book. | ||
65 | |||
66 | |||
67 | |||
68 | Public key cryptosystems | ||
69 | - - - - - - - - - - - - - | ||
70 | |||
71 | We give a formal definition of a public key cryptosystem and its | ||
72 | security. | ||
73 | |||
74 | |||
75 | Definition: a public key cryptosystem Pi comprises | ||
76 | |||
77 | -) a (probabilistic) key generation algorithm Gen() which given | ||
78 | security parameter n outputs a pair of keys (pk,sk) /* public, secret | ||
79 | */ | ||
80 | |||
81 | -) a (probabilistic) encryption algorithm which given plaintext m from | ||
82 | some message space and the public key pk produces a ciphertext c: | ||
83 | c<-nc_pk(m) | ||
84 | |||
85 | -) a deterministic decryption algorithm which given ciphertext c and | ||
86 | the secret key sk produces a plaintext m<-Dec_sk(c) in such a way that | ||
87 | if c<-Enc_pk(m) then Dec_pk(End_sk(m)) = m. | ||
88 | |||
89 | |||
90 | Definition: A public key scheme Pi is semantically secure in the | ||
91 | presence of an eavesdropper if the for all (prob. polytime) | ||
92 | adversaries A the success probability in the following experiment is | ||
93 | bounded by 1/2+negl(n). | ||
94 | |||
95 | Experiment PubK^eav_{A,Pi}(n): | ||
96 | |||
97 | 1. (pk,sk)<-Gen(n) | ||
98 | 2. Adversary A is given pk and outputs messages m0 m1 | ||
99 | 3. b <- {0,1}; c <- Enc_pk(m_b); c is given to A | ||
100 | 4. A outputs a bit b' | ||
101 | 5. Outcome is 1 if b=b' and 0 otherwise End of definition | ||
102 | |||
103 | |||
104 | We notice that this is just like semantic security in the private key | ||
105 | setting except that the adversary has access to the public key which | ||
106 | after all is supposed to be public. This means that, since by | ||
107 | Kerckhoff's principle, the encryption algorithm is also public, the | ||
108 | adversary has access to an encryption oracle and thus---in the public | ||
109 | key setting---semantic security in the presence of an eavesdropper | ||
110 | (the one above) is as powerful as cpa security. | ||
111 | |||
112 | This has the consequence that no public key cryptosystem in which | ||
113 | Enc_pk() is deterministic can be semantically secure. Indeed, all the | ||
114 | adversary has to do in this case is to precompute the encryptions of | ||
115 | its chosen messages m0 and m1. | ||
116 | |||
117 | We remark that a semantically secure public key cryptosystem can be | ||
118 | combined with any cps-secure private key system by first using the | ||
119 | public key to transmit a secret key. This is known as *hybrid | ||
120 | encryption*. One can show (Theorem 10.13 of KL) that hybrid encryption | ||
121 | yields semantically secure public-key encryption schemes. | ||
122 | |||
123 | |||
124 | |||
125 | RSA cryptosystem | ||
126 | - - - - - - - - - | ||
127 | |||
128 | For this reason, the "textbook RSA" cryptosystem, as indicated in the | ||
129 | last chapter, is actually insecure. In order to make it work, it must | ||
130 | be enhanced with randomization for example as follows. | ||
131 | |||
132 | Fix a length function l(n). | ||
133 | |||
134 | Gen(): On input n run GenRSA(n) to obtain (N,e,d). Output | ||
135 | pk=(N,e) and sk=(N,d) | ||
136 | Enc(): On input m:{0,1}^l(n) and pk=(N,e) choose | ||
137 | r<-{0,1}^{||N||-l(n)-1} and output c=(r||m)^e mod N | ||
138 | /* the -1 is there to make sure that r||m is in Z_N^* */ | ||
139 | Dec(): On input c and sk=(N,d) compute m'=c^d mod N and output the l(n) | ||
140 | low-order, i.e. rightmost, bits of m' | ||
141 | |||
142 | Now, if the "padding" r is too short, then this does not help because | ||
143 | an adversary could try out all possible values for r. It is believed | ||
144 | that when r has a length comparable to |m|, then the above scheme is | ||
145 | secure (relative to the RSA assumption), but unfortunately, no proof | ||
146 | has been found. According to KL (Theorem 10.19) one can show that the | ||
147 | scheme is secure when l(n)=O(log(n)), again under the RSA | ||
148 | assumption. Note that this means that in order to increase the message | ||
149 | size by just one bit one has to double the security parameter and | ||
150 | hence the length of the modulus N and the ciphertexts. | ||
151 | |||
152 | In practice, one does not want to waste so much bandwidth on the | ||
153 | padding and uses heuristic schemes like e.g. RSA-PKCS#1v1.5 which uses | ||
154 | a random padding string of length at least 64bit. | ||
155 | |||
156 | Another, more modern, method is RSA-OAEP which mixes the padding with | ||
157 | the actual plaintext by way of a Feistel network of cryptographic hash | ||
158 | functions. Intuitively, this makes the input to the actual RSA | ||
159 | encryption look like a random string which then makes the RSA | ||
160 | assumption applicable. Viewed more practically, it prevents attacks | ||
161 | which only recover parts of the plaintext. In the random oracle model | ||
162 | (Lecture 16) RSA-OAEP can be proved semantically secure. | ||