Exercise

Let E denote the elliptic curve y2 ≡ x3 + x + 26 mod 127. It can be shown that #E = 131, which is a prime

number. There any non-identity element in E is a generator for (E, +). Suppose the ECDSA is

implemented in E, with A = (2,6) and m = 54.

(a) Compute the public key B = mA.

(b) Compute the signature on a message x if SHA-1 (x) = 10, when k = 75.

(c) Show the computations used to verify the signature constructed in part(b).

Note: See next page for the elliptic curve subgroup which is needed for the exercise.

Variants of the E/Gamal Signature Scheme 297

The signature (94, 97) on the message digest 22 is verified by the following computations:

J- 1 = 97-l mod 101 = 25

e1 = 22 x 25 mod 101 = 45

e2 = 94 x 25 mod 101 = 27

(17045456727 mod 7879) mod 101 = 2518 mod 101 = 94.

a

When the DSA was proposed in 1991, there were several criticisms put forward.

One complaint was that the selection process by NIST was not public. The

standard was developed by the National Security Agency (NSA) without the input

of U.S. industry. Regardless of the merits of the resulting scheme, many people

resented the “closed-door” approach.

Of the technical criticisms put forward, the most serious was that the size of the

modulus p was fixed initially at 512 bits. Many people suggested that the modulus

size not be fixed, so that larger modulus sizes could be used if desired. In reponse

to these comments, NIST altered the description of the standard so that a variety

of modulus sizes were allowed.

7.4.3 The Elliptic Curve DSA

In 2000, the EIJiptic Curve Digital Signature Algorithm (ECDSA) was approved

as FIPS 186-2. This signature scheme can be viewed as a modification of the

DSA to the setting of elliptic curves. We have two points A and B on an elliptic

curve defined over Z’..p for some prime p. 1 The discrete logarithm m = logA B

is the private key. (This is analogous to the relation (3 = aa mod p in the DSA,

where a is the private key.) The order of A is a large prime number q. Computing

a signature involves first choosing a random value k and computing kA (this is

analogous to the computation of akin the DSA).

Now here is the main difference between the DSA and the ECDSA. In the

DSA, the value ak mod p is reduced modulo q to yield a value I which is the

first component of the signature ( /, J). In the ECDSA, the analogous value is r,

which is the x-co-ordinate of the elliptic curve point kA, reduced modulo q. This

value r is the first component of the signature ( r, s).

Finally, in the ECDSA, the values is computed from r, m, k, and the message

x in exactly the same way as J is computed from I• a, k and the message x in the

DSA.

We now present the complete description of the ECDSA as Cryptosystem 7 .5.

1 We note that the ECDSA also permits the use of elliptic curves defined over finite fields lF 2 n , but

we will not describe this variation here.

298 Signature Schemes

Cryptosystem 7.5: Elliptic Curve Digital Signature Algorithm

Let p be a large prime and let Ebe an elliptic curve defined over IFp. Let A be

a point on E having prime order q, such that the Discrete Logarithm problem

in (A) is infeasible. Let ‘.P = {O, 1}*, A= 7l.q* x 7l.q*, and define

X = {(p,q,E,A,m,B): B = mA},

where 0 < m < q – 1. The values p, q, E, A and Bare the public key, and m

is the private key.

For J( = (p, q, E, A, m, B), and for a (secret) random number k, 1 < k <

q – 1, define

sigK(x, k) = (r, s),

where

kA = (u, v)

r = u mod q, and

s = k- 1(SHA-l(x) + mr) mod q.

(If either r = 0 or s = 0, a new random value of k should be chosen.)

For x E { 0, 1} * and r, s E 7l.q *, verification is done by performing the following

computations:

w = s -1 mo d q

i = wSHA-l(x) modq

j = wr mod q

(u,v)=iA+jB

verK(x, (r, s)) =true<=? u mod q = r.

We work through a tiny example to illustrate the computations in the ECDSA.

Example 7.5 We will base our example on the same elliptic curve that was used

in Section 6.5.2, namely, y2 = x 3 + x + 6, defined over 7l. 11. The parameters of

the signature scheme are p = 11, q = 13, A= (2, 7), m = 7 and B = (7, 2).

Suppose we have a message x with SHA-l(x) = 4, and Alice wants to sign

Provably Secure Signature Schemes

the message x using the random value k = 3. She will compute

(u,v) = 3 (2, 7) = (8,3)

r = u mod 13 = 8, and

s = 3- 1 (4 + 7 x 8) mod 13 = 7.

Therefore (8, 7) is the signature.

Bob verifies the signature by performing the following computations:

w = 7-l mod 13 = 2

i = 2 x 4 mod 13 = 8

j = 2 x 8 mod 13 = 3

(u, v) = 8A + 3B = (8, 3), and

u mod 13 = 8 = r.

Hence, the signature is verified.

7.5 Provably Secure Signature Schemes

299

a

We present some examples of provably secure signature schemes in this section.

First, we describe a construction for a one-time signature scheme based on an

arbitrary one-way (i.e., preimage resistant) function, say f. This scheme can be

proven secure against a key-only attack provided that f is a bijective function.

The second construction is for a signature scheme known as Full Domain Hash.

This signature scheme is provably secure in the random oracle model provided

that it is constructed from a trap-door one-way permutation.

7.5.1 One-time Signatures

In this section, we describe a conceptually simple way to construct a provably secure

one-time signature scheme from a one-way function. (A signature scheme is

a one-time signature scheme if it is secure when only one message is signed. The

signature can be verified an arbitrary number of times, of course.) The description

of the scheme, which is known as the Lamport Signature Scheme, is given in

Cryptosystem 7.6.

Informally, this is how the system works. A message to be signed is a binary ktuple.

Each bit of the message is signed individually. If the ith bit of the message

equals j (where j E {O, 1} ), then the ith element of the signature is the value

Yi,j, which is a preimage of the public key value z;,j. The verification consists

simply of checking that each element in the signature is a preimage of the public

*Place your order now for a similar paper and have exceptional work written by our team of experts to guarantee you A Results*

*Why Choose US*

*6+ years experience on custom writing*

* 80% Return Client*

* Urgent 2 Hrs Delivery*

* Your Privacy Guaranteed*

* Unlimited Free Revisions*

Basic features

- Free title page and bibliography
- Unlimited revisions
- Plagiarism-free guarantee
- Money-back guarantee
- 24/7 support

On-demand options

- Writer’s samples
- Part-by-part delivery
- Overnight delivery
- Copies of used sources
- Expert Proofreading

Paper format

- 275 words per page
- 12 pt Arial/Times New Roman
- Double line spacing
- Any citation style (APA, MLA, Chicago/Turabian, Harvard)

Delivering a high-quality product at a reasonable price is not enough anymore.

That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

Read moreEach paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

Read moreThanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Read moreYour email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

Read moreBy sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.

Read more
The price is based on these factors:

Academic level

Number of pages

Urgency