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.

Click here to place an order for this or any other related assignment

(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

error.

(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

071920303047987890593495298641119199992345149607002318096312625702281139.

I propose you use Python as Python natively handles very large numbers. You can use the pow function to do fast

modular exponentiation.

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

prime order.

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.

1

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,

use

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.

Click Here to Place your order and Get **100% original paper on any topic** done for Your

The point

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.