Let be a cubic polynomial with roots Show that
Write Show that
with and (Remark: This shows that a simple change of variables allows us to consider the case where the coefficient of is 0.)
Let be the elliptic curve
List the points on (don’t forget ).
Evaluate the elliptic curve addition
List the points on the elliptic curve
Find the sum on
Find the sum on
Let be the elliptic curve
Evaluate
Evaluate
Evaluate
Find the sum of the points (1, 2) and (6,3) on the elliptic curve
Eve tries to find the sum of the points (1,2) and (6,3) on the elliptic curve What information does she obtain?
Show that if is a point on an elliptic curve, then
Find an elliptic curve mod 101 such that is a point on the curve.
The point lies on the elliptic curve defined over the rational numbers. use the addition law to find another point with positive rational coordinates that lies on this curve.
Show that on satisfies (Hint: Compute then use Exercise 6.)
Your computations in (a) probably have shown that and Use this to show that the points are distinct.
Factor by the elliptic curve method by using the elliptic curve and calculating 3 times the point
Factor by the elliptic curve method by using the elliptic curve and the point
Suppose you want to factor a composite integer by using the elliptic curve method. You start with the curve and the point Why will this not yield the factorization of ?
Devise an analog of the procedure in Exercise 11(a) in Chapter 10 that uses elliptic curves.
Let The elliptic curve has 999984 points. Suppose you are given points and on and are told that there is an integer such that
Describe a birthday attack that is expected to find
Describe how the Baby Step, Giant Step method (see Section 10.2) finds
Let and be points on an elliptic curve Peggy claims that she knows an integer such that and she wants to convince Victor that she knows without giving Victor any information about They perform a zero-knowledge protocol. The first step is the following:
Peggy chooses a random integer and lets She computes and and sends them to Victor.
Give the remaining steps. Victor wants to be at least sure that Peggy knows (Technical note: You may regard and as numbers mod where Without congruences, Victor obtains some information about the size of
Nontechnical note: The “Technical note” may be ignored when solving the problem.)
Find all values of mod 35 such that is a point on the curve
Suppose is a product of two large primes and let Bob wants to find some points on
Bob tries choosing a random computing and finding the square root of this number mod when the square root exists. Why will this strategy probably fail if Bob does not know and ?
Suppose Bob knows and Explain how Bob can use the method of part (a) successfully? (Hint: He needs to use the Chinese Remainder Theorem.)
Show that if are points on an elliptic curve, then
Eve is trying to find an elliptic curve discrete log: She has points and on an elliptic curve such that for some There are approximately points on so assume that She makes two lists and looks for a match. The first list is for randomly chosen values of The second is for randomly chosen values of How big should be so that there is a good chance of a match?
Give a classical (that is, not elliptic curve) version of the procedure in part (a).
Let be a point on the elliptic curve mod a prime
Show that there are only finitely many points on so has only finitely many distinct multiples.
Show that there are integers with such that Conclude that
The smallest positive integer such that is called the order of Let be an integer such that Show that divides (Hint: Imitate the proof of Exercise 53(c, d) in Chapter 3.)
(for those who know some group theory) Use Lagrange’s theorem from group theory to show that the number of points on is a multiple of the order of (Combined with Hasse’s theorem, this gives a way of finding the number of points on See Computer Problems 1 and 4.)
Let be a point on the elliptic curve Suppose you know a positive integer such that You want to prove (or disprove) that is the order of
Show that if for some prime factor of then is not the order of
Suppose and Show that for some prime divisor of
Suppose that for each prime factor of Use Exercise 11(c) to show that the order of is (Compare with Exercise 54 in Chapter 3. For an example, see Computer Problem 4.)
Let be an integer written in binary. Let be a point on the elliptic curve Perform the following procedure:
Start with and
If let If let
Let
If stop. If add 1 to and go to step 2.
Show that (Compare with Exercise 56(a) in Chapter 3.)
Let be a positive integer and let be a point on an elliptic curve. Show that the following procedure computes
Start with
If is even, let and let
If is odd, let and let
If go to step 2.
Output
(Compare with Exercise 56(b) in Chapter 3.)
Let be an elliptic curve mod (where is some integer) and let and be points on with The curve and the point are public and are known to everyone. The point is secret. Peggy wants to convince Victor that she knows They do the following procedure:
Peggy chooses a random point on and lets
Peggy computes and and sends to Victor.
Victor checks that
Victor makes a request and Peggy responds.
Victor now does something else.
They repeat steps 1 through 5 several times.
Describe what is done in steps 4 and 5.
Give a classical (non-elliptic curve) version of this protocol that yields a zero-knowledge proof that Peggy knows a solution to
Let be an elliptic curve mod a large prime, let be the number of points on and let and be points on Peggy claims to know an integer such that She wants to prove this to Victor by the following procedure. Victor knows and but he does not know and should receive no information about
Peggy chooses a random integer mod and lets (Don’t worry about why it’s mod It’s for technical reasons.)
Peggy computes and and sends and to Victor.
Victor checks something.
Victor randomly chooses or and asks Peggy for
Peggy sends to Victor.
Victor checks something.
Step (7).
What does Victor check in step (3)?
What does Victor check in step (6)?
What should step (7) be if Victor wants to be at least sure that Peggy knows ?
Here is an elliptic curve version of the Digital Signature Algorithm. Alice wants to sign a message which is an integer. She chooses a prime and an elliptic curve The number of points on is computed and a large prime factor of is found. A point is chosen such that (In fact, is not needed. Choose a point on and find an integer with There are ways of doing this, though it is not easy. Let be a large prime factor of if it exists, and let Then ) It is assumed that the message satisfies Alice chooses her secret integer and computes The public information is Alice does the following:
Chooses a random integer with and computes
Computes
Sends the signed message to Bob
Bob verifies the signature as follows:
Computes and
Computes
Declares the signature valid if
Show that the verification equation holds for a correctly signed message. Where is the fact that used (see the “subtle point” mentioned in the ElGamal scheme in Section 21.5)?
Why does exist?
If is large, why is there very little chance that does not exist mod ? How do we recognize the case when it doesn’t exist? (Of course, in this case, Alice should start over by choosing a new )
How many computations “(large integer)(point on )” are made in the verification process here? How many are made in the verification process for the elliptic ElGamal scheme described in the text? (Compare with the end of Section 13.5.)
Let and be points on an elliptic curve and suppose for some integer Suppose also that for some integer but
Show that if then Therefore, we may assume that
Let be an integer. Show that when is even and when is odd.
Write where each is 0 or 1 (binary expansion of ). Show that if and only if
Suppose that for some we know Let Show that if and only if This allows us to find Continuing in this way, we obtain and therefore we can compute This technique can be extended to the case where where is an integer with only small prime factors. This is the analog of the Pohlig-Hellman algorithm (see Section 10.2).