Homework Help is Here – Start Your Trial Now!
Math
Advanced Math
3. Suppose that Eve is able to solve the Diffie-Hellman problem; i.e., if Eve is given two powers gu and gº mod p, then she is able to compute guv mod p. Show that Eve can break the Elgamal public key cryptosystem.

3. Suppose that Eve is able to solve the Diffie-Hellman problem; i.e., if Eve is given two powers gu and gº mod p, then she is able to compute guv mod p. Show that Eve can break the Elgamal public key cryptosystem.

Advanced Engineering Mathematics
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
See similar textbooks
icon
Related questions
Question

[Algebraic Cryptography] How do you solve this? Second picture is for context

3. Suppose that Eve is able to solve the Diffie-Hellman problem; i.e., if Eve is given two powers g" and gº mod p, then she is able to compute guv mod p. Show that Eve can break the Elgamal public key cryptosystem.
Transcribed Image Text:3. Suppose that Eve is able to solve the Diffie-Hellman problem; i.e., if Eve is given two powers g" and gº mod p, then she is able to compute guv mod p. Show that Eve can break the Elgamal public key cryptosystem.
Proposition 2.10. Fix a prime p and base g to use for Elgamal encryption. Suppose that Eve has access to an oracle that decrypts arbitrary Elgamal ci- phertexts encrypted using arbitrary Elgamal public keys. Then she can use the oracle to solve the Diffie-Hellman problem described on page 69. Conversely, if Eve can solve the Diffie-Hellman problem, then she can break the Elgamal PKC. Proof. Rather than giving a compact formal proof, we will be more discursive and explain how one might approach the problem of using an Elgamal oracle to solve the Diffie-Hellman problem. Recall that in the Diffie-Hellman problem, Eve is given the two values A = gº (mod p) and B = gb (mod p), and she is required to compute the value of gab (mod p). Keep in mind that she knows both of the values of A and B, but she does not know either of the values a and b. Now suppose that Eve can consult an Elgamal oracle. This means that Eve can send the oracle a prime p, a base g, a purported public key A, and a purported cipher text (C₁, C₂). Referring to Table 2.3, the oracle returns to Eve the quantity (c₁)-¹. c₂ (mod p). If Eve wants to solve the Diffie-Hellman problem, what values of c₁ and c₂ should she choose? A little thought shows that c₁ = B = gb and c₂ = 1 are good choices, since with this input, the oracle returns (gab)-1 (mod p), and then Eve can take the inverse modulo p to obtain gab (mod p), thereby solving the Diffie-Hellman problem. But maybe the oracle is smart enough to know that it should never decrypt ciphertexts having c₂ = 1. Eve can still fool the oracle by sending it random- looking ciphertexts as follows. She chooses an arbitrary value for c₂ and tells the oracle that the public key is A and that the ciphertext is (B, c₂). The oracle returns to her the supposed plaintext m that satisfies m = (ci) ¹. c₂ = (Bª)-¹. c₂ = (gab)-¹. c₂ (mod p). C2 C2 After the oracle tells Eve the value of m, she simply computes - C₂ = gab (mod p) m-1 to find the value of gab (mod p). It is worth noting that although, with the oracle's help, Eve has computed gab (mod p), she has done so without knowl- edge of a or b, so she has solved only the Diffie-Hellman problem, not the discrete logarithm problem. We leave the proof of the converse, i.e., that a Diffie-Hellman oracle breaks the Elgamal PKC, as an exercise; see Exercise 2.9.
Transcribed Image Text:Proposition 2.10. Fix a prime p and base g to use for Elgamal encryption. Suppose that Eve has access to an oracle that decrypts arbitrary Elgamal ci- phertexts encrypted using arbitrary Elgamal public keys. Then she can use the oracle to solve the Diffie-Hellman problem described on page 69. Conversely, if Eve can solve the Diffie-Hellman problem, then she can break the Elgamal PKC. Proof. Rather than giving a compact formal proof, we will be more discursive and explain how one might approach the problem of using an Elgamal oracle to solve the Diffie-Hellman problem. Recall that in the Diffie-Hellman problem, Eve is given the two values A = gº (mod p) and B = gb (mod p), and she is required to compute the value of gab (mod p). Keep in mind that she knows both of the values of A and B, but she does not know either of the values a and b. Now suppose that Eve can consult an Elgamal oracle. This means that Eve can send the oracle a prime p, a base g, a purported public key A, and a purported cipher text (C₁, C₂). Referring to Table 2.3, the oracle returns to Eve the quantity (c₁)-¹. c₂ (mod p). If Eve wants to solve the Diffie-Hellman problem, what values of c₁ and c₂ should she choose? A little thought shows that c₁ = B = gb and c₂ = 1 are good choices, since with this input, the oracle returns (gab)-1 (mod p), and then Eve can take the inverse modulo p to obtain gab (mod p), thereby solving the Diffie-Hellman problem. But maybe the oracle is smart enough to know that it should never decrypt ciphertexts having c₂ = 1. Eve can still fool the oracle by sending it random- looking ciphertexts as follows. She chooses an arbitrary value for c₂ and tells the oracle that the public key is A and that the ciphertext is (B, c₂). The oracle returns to her the supposed plaintext m that satisfies m = (ci) ¹. c₂ = (Bª)-¹. c₂ = (gab)-¹. c₂ (mod p). C2 C2 After the oracle tells Eve the value of m, she simply computes - C₂ = gab (mod p) m-1 to find the value of gab (mod p). It is worth noting that although, with the oracle's help, Eve has computed gab (mod p), she has done so without knowl- edge of a or b, so she has solved only the Diffie-Hellman problem, not the discrete logarithm problem. We leave the proof of the converse, i.e., that a Diffie-Hellman oracle breaks the Elgamal PKC, as an exercise; see Exercise 2.9.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,
SEE MORE TEXTBOOKS