1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
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.
|
