17crypto_L10
Diffe Helman Key Exchange
Elgamal Encryption
Crypto & SecDev 2017 © Ron Poet: Lecture 10 1
Diffie-Hellman Key Exchange
� The Diffie-Hellman key exchange uses an exponential
encryption system to generate a single key that is shared by
two people.
� Both parties contribute to the key by sharing information
over an insecure communication channel.
Crypto & SecDev 2017 © Ron Poet: Lecture 10 2
over an insecure communication channel.
� Each party keeps some information secret. This secret
information is vital to be able to construct the key.
� The key cannot be generated from this public information.
� This algorithm forms the basis for session key construction
in many internet applications.
Diffe-Hellman Algorithm
� Both Alice and Bob agree on two numbers, p a large prime
number, and g which is less than p. These two numbers
are public.
� Alice selects a random number XA as her secret key and
transmits Y = gX % p as her public key.
Crypto & SecDev 2017 © Ron Poet: Lecture 10 3
A
transmits YA = g
XA % p as her public key.
�Bob does the same.
� Alice computes YB
XA % p, and Bob computes YA
XB % p.
�They are both the same, K = gXAXB % p.
�This is the session key.
Diffe-Hellman Algorithm (2)
� Eve only knows p, g, YA and YB, and so cannot compute
K.
� For best result, (p-1) / 2 should also be a prime and g
should be a primitive root of p.
Crypto & SecDev 2017 © Ron Poet: Lecture 10 4
should be a primitive root of p.
�This means that gx mod p, 1 < x < p takes all the values between 1 and p. �Thus all possible values are used. � This scheme is vulnerable to a man-in-the-middle attack. �Just like other public key systems. Primitive Roots When p = 7 � Let us calculate gz % 7when �g is 2, 3, 4, 5, 6 and �z = 1, 2, 3, 4, 5, 6 g z=1, 2, 3, 4, 5, 6, period Crypto & SecDev 2017 © Ron Poet: Lecture 10 5 2 2 4 1 2 4 1 3 3 3 2 6 4 5 1 6 4 4 2 1 4 2 1 3 5 5 4 6 2 3 1 6 6 6 1 6 1 6 1 2 � Primitive roots are 3 and 5 Security of Diffe-Hellman � The Diffe-Hellman algorithm relies on the hardness of the discrete logarithm problem for its security. � The discrete logarithm problem states that if we know p, g and Y = gX % p, then it is computationally infeasible to calculate X. Crypto & SecDev 2017 © Ron Poet: Lecture 10 6 calculate X. � It can be shown that this problem is equivalent to the factoring problem. �If a fast algorithm for factoring is discovered then there exists an equivalent fast algorithm for solving the discrete logarithm problem, and vice versa. Diffe-Hellman with Multiple Parties � The D-H algorithm can be extended so that three or more parties can share a session key. Here is how it would work with 3 parties. � Alice, Bob and Carol each choose a secret random number Crypto & SecDev 2017 © Ron Poet: Lecture 10 7 � Alice, Bob and Carol each choose a secret random number XA, XB, XC. � They each calculate Y = gX % p. � Alice sends her value of Y to Bob, Bob his to Carol, and Carol hers to Alice. � Alice has YC, Bob has YA, Carol has YB. Three Person D-H (2) � They each calculate Z = YX % p, from the Y they have just received and their secret key. � Alice sends her value of Z to Bob, Bob his to Carol, and Carol hers to Alice. Crypto & SecDev 2017 © Ron Poet: Lecture 10 8 � Alice has ZC = YBXC % p = g XBXC % p, etc. � They each compute K = ZX % p from the Z they have just received and their secret key. � Alice computes K = ZCXA % p = g XAXCXB % p. � These values are identical Elgamal Public Key Systems � This system is based on Diffie-Hellman key exchange. � It is just as secure as RSA. � It is not quite as convenient as RSA. � But it can be used without as license.� But it can be used without as license. � Martin Hellman was Elgamal’s PhD advisor at Stanford. 9Crypto & SecDev 2017 © Ron Poet: Lecture 10 Elgamal Encryption � Assume Alice and Bob have agreed on p, g, calculated XA and XB and exchanged YA and YB. �They can thus both calculate the shared secret key K. � Alice wants to send the secret message M to Bob.� Alice wants to send the secret message M to Bob. � Alice calculates C = (M * K) % n and sends it to Bob. � Bob calculates (C * K-1) % n, which equals M. � The inverse K-1 satisfies the usual inverse criteria: �K * K-1 = 1 % p. 10Crypto & SecDev 2017 © Ron Poet: Lecture 10 Elgamal Signature � Let M be a plaintext block that we want Bob to sign. � It is a large integer. � Bob chooses a random number Z (kept secret) such that �1 < Z < p-1 �gcd(Z, p-1) = 1, since p-1 is even and we want Z to have an inverse in the integers mod p-1 system. �Z must be different for each document signed. � Compute r = gZ % p-1 � Compute s = (M – XB * r) * Z -1 % p-1, where �Z * Z-1 = 1 % p-1 � (r, s) is the signature. 11Crypto & SecDev 2017 © Ron Poet: Lecture 10 Elgamal Signature (2) � Verify the signature by checking that gM = YB r * rs % p � s = (M – XB * r) * Z -1 % p-1 � So s * Z = M – XB * r % p-1 � i.e. M = s * Z + X * r % p-1� i.e. M = s * Z + XB * r % p-1 � i.e. M = s * Z + XB * r + λ * (p-1) �We don’t need to know the value of the integer λ. � So gM % p = U * V % p where � U = g(s * Z + XB * r ) % p and � V = g(λ * (p-1)) % p = (g(p-1) % p)λ % p = 1 by Fermat’s thm. 12Crypto & SecDev 2017 © Ron Poet: Lecture 10 Elgamal Signature (2) � So gM % p = gXBr * gsZ % p � i.e. = (gXB)r * (gZ)s % p � i.e. = YB r * rs % p 13Crypto & SecDev 2017 © Ron Poet: Lecture 10