密码算法与协议2密钥交换协议案例分析.ppt

* * Passive Attacks For example, an eavesdropper might be able to determine the parity of K, viewing K as an integer, which would mean that the eavesdropper learns one bit of information. To exclude such possibilities we need the DDH assumption. We will now make this more precise. First we argue why we need to require that n is prime. Suppose n is not prime, say n = 2p’, where p’ is prime. For any element y ? G, we have ord(y) ? {1, 2, p’, 2p’} and ord(y) is easily computed. We have the following table, where each case occurs approximately with probability 1/4: * * Passive Attacks Hence, the order of the key K is biased, as Pr[ord(K) = p’] ? 3/4 and Pr[ord(K) = 2p’] ? 1/4. If K would be generated uniformly at random in G, then we would have Pr[ord(K) = p’] ? Pr[ord(K) = 2p’] ? 1/2. Such a slight deviation in the distribution of K seems innocent. However, suppose key K is used to encrypt a 1-bit message, say m ?R {1, g}, using c = mK as ciphertext (like the one-time pad construction). In that case, an eavesdropper would compute ord(c). If ord(c) = p then most likely m = 1, and if ord(c) = 2p then most likely m = g. * * Passive Attacks Exercise: Argue that the DDH assumption is false when n contains a small prime factor. * * Passive Attacks So, assume that n is prime. BTW, if an eavesdropper would be able to determine any partial information on key K, then we would get a contradiction with the DDH assumption. * * A Practical Variant We now consider the Diffie-Hellman protocol as above, except that the key K is defined as follows: K = H(gxAxB), where H is a cryptographic hash function. Clearly, both parties are still able to compute K by first computing gxy and then applying H. A practical choice for H is the standardized SHA-1 hash function. * * A Practical Variant The reason for using a hash function H is that even though gxAxB will have a sufficient amount of entropy, it cannot be simply used as an AES key, for example. The value