1 Problem 1 (30 points)
Alice and Bob are using software to create digital signatures. They have selected the DSA standard (represented as
Cryptosystem 8.4 on page 323 of the text). However the software has two implementation problems and in addition,
a very rare circumstance has occurred. Please refer to the module added to Canvas for final project that shows the
values of p, q, α, etc. for this problem. Alice and Bob share the same p, q, and α, but have different values of a
and thus different values of β.
(a) Verify that the signatures are valid.
(b) The first problem is that the Digital Signature algorithm was modified so that the value to be signed is not
hashed. Please produce one existential forgery for Alice and and one for Bob based on the public key.
(c) An unrelated software problem has made it likely that Alice and Bob have secret keys that are close to each
other. And this bug has in fact occurred in this situation. By close, I mean that the two secret keys aAlice = a1 and
aBob = a2 are different by less than 25,000. As if this was not bad enough, Alice and Bob have produced digital
signatures where their software chose the same value for k. Describe how to calculate d = a1 −a2 by trial and error,
then describe how to compute k, a1, and a2. Note it is only necessary to solve one instance of the the discrete log
problem, in order to compute d. Further, since d is small in absolute value, it is feasible to do this by trial and
(d) Implement the attack you have described in (c) and calculate k, a1 and a2.
(e) Now assume that during the instance where Alice and Bob accidentally had the same value of k, they were
engaging in the Public-Key Mutual Authentication protocol 10.5 (page 395). Would you, the hacker, now be able
to impersonate Alice and Bob to other parties in the future? Explain.
2 Problem 2 (20 points)
Be resourceful and factor the following number: 12799278244855761977683089682787008973539117867733922884954
I propose you use Python as Python natively handles very large numbers. You can use the pow function to do fast
3 Problem 3 (50 points)
When we select an elliptic curve for practical use, we would like the order of the base point to be a prime number.
Curve 25519 does this. In curves like 25519, the total number of points #E is not prime but the base point has
I had stated in class that it was a good idea for the number of points #E on the an Elliptic curve modulo a prime
p to be a prime number. That way, any point you choose (except the infinity point) is a generator of the group.
However, I forgot to mention a pathological case, which occurs when the number of points on the curve #E is the
same as the modulus p. So if you are selecting a curve, you need to check for this case.
Your task is to solve the discrete log problem for the following elliptic curve: For a curve y
2 = x
3 + ax + b mod p,
m = 257743850762632419871495
p = 11 ∗ m ∗ (m + 1) + 3
a = 425706413842211054102700238164133538302169176474
b = 203362936548826936673264444982866339953265530166.
Please perform the following tasks:
(a) Generate a curve with small prime pmini < 1000 that has the same number of points as pmini. Then create a
discrete log problem for this small curve. You will be using this curve to double check your code.
(b) Check if p is prime. OK to use software tools.
(c) What is the number of points on E? (OK to use software tools).
(d) Now use the resources uploaded on the final project module to solve the following discrete logarithm problem.
A = (24, 310224165475973298147806088269428225647703826034)
B = (50, 66275076336461442314332875274548217082100991151),
where mA = B, and the goal is to find m. Hint: First work the sample problems in the two reference papers by
hand. Then download SageMath and use it. It will greatly speed up your work. You may need to modify existing
Sage code to solve the problem. If you use a source, please cite it. The method for breaking the DL problem in this
case is elegant.