Solution.
Bob checks by computing 5444 (mod 5023) ≡ 4678
and also yββγ (mod p) ≡3796229422943740 ≡ 728.
So no, Bob should not accept the message as being validly signed by Alice.
C. The questions in this section deal with attacking the El Gamal scheme.
1. In this case, Oscar, the attacker, uses Alice’s scheme set-up parameters p = 5023, α = 5 and y = 5a = 3796. Oscar picks random , r1 = 205 and r2 = 1021.
He computes β1 = 5205 37961021 (mod p) = 1287 and
γ1 = -β1r2-1 = -1287 * 4417(mod p-1) = 225.
Oscar then sends (β1, γ1) with message m1 = γ1 r1 = 927 (mod p – 1) to Bob. Show why Bob thinks this message has been signed by Alice.
Solution.
Bob will do the same verification he did in part B above:
Bob checks by computing 5927 (mod 5023) ≡ 600.
and also yββγ (mod p) ≡379612871287225 ≡ 600 .
Since the two computations match, bob will assume that Alice signed this message.
2. Oscar has captured the message m = 487 along with the signed pair β = 1723 and γ = 7045 in Alice’s scheme with p = 7481, α = 6 and y = 5979. He checks that m-1 exists mod (p-1) and since it does, proceeds to choose his own message m1= 2222.
(a) Show how Oscar can now fraudulently attach Alice’s signature to this message.
Solution.
-
m-1 = 983 (mod7480). He computes t = m1 m-1 (mod p – 1) = 66 and
γ1 = tγ (mod p – 1) = 1210.
Oscar now uses the CRT to compute a solution β1 to the system
x ≡βt (mod p – 1) = 1518
x ≡β (mod p) = 1723.
We can use Maple to do this for us:
with(numtheory);
> chrem([1518,1723],[7480,7481]);
Oscar now sends (54425998, 1210) and 2222 to Bob.
(b) Why might Bob suspect that Oscar has used this attack?
Solution (b) Bob will notice that one of the values he receives is larger than the prime p used.
C. This section looks at the DSS.
1. Go to and describe NIST from this website.
Solution. Founded in 1901, NIST is a non-regulatory federal agency within the . NIST's mission is to promote U.S. innovation and industrial competitiveness by advancing measurement science, standards, and technology in ways that enhance economic security and improve our quality of life.
2. Locate NIST’s cryptographic algorithm testing page.
Solution. http://csrc.nist.gov/groups/STM/cavp/index.html
3. Locate the DSS document written by NIST in 2000.
Solution. This is FIPS PUB 186-2 at
4. Which hash function is recommended? Give the page number where this is written.
Solution. SHA-1. Page 8.
5. Appendix 1 of this standard states and proves the Lemma (Proposition):
LEMMA. Let p and q be primes so that q divides p - 1, h a positive integer less than p, and g = h(p-1)/q mod p. Then gq mod p = 1, and if m mod q = n mod q, then gm mod p = gn mod p.
Read through the proof and understand it.
Solution. Proof: We have gq mod p = (h(p-1)/q mod p)q mod p = h(p-1) mod p = 1
by Fermat's Little Theorem. Now let m mod q = n mod q, i.e., m = n + kq for some integer k. Then gm mod p = gn+kq mod p = (gn gkq) mod p = ((gn mod p) (gq mod p)k) mod p
= gn mod p since gq mod p = 1. ■
6. The above lemma is followed by a proof that the DSS verification actually works.
THEOREM. If M′ = M, r′ = r, and s′ = s in the signature verification, then v = r′.
Read this through and understand the steps.
Solution. Proof: We have w = (s′)-1 (mod q) = s-1 (mod q) and u1 = ((SHA-1(M′))w) (mod q) = ((SHA-1(M))w) (mod q) and u2 = ((r′)w) (mod q) = (rw) mod q.
Now y = gx (mod p), so that by the lemma, v = ((gu1 yu2) mod p) (mod q) = ((gSHA-1(M)w yrw) mod p) (mod q) = ((gSHA-1(M)w gxrw) mod p) (mod q) = ((g(SHA-1(M)+xr)w) mod p) (mod q).
Also s = (k-1(SHA-1(M) + xr)) (mod q).
Hence w = (k(SHA-1(M) + xr)-1) (mod q) so (SHA-1(M) + xr)w mod q = k (mod q).
Thus by the lemma, v = (gk mod p) mod q = r= r′. ■
7. Appendix 5 of the same document gives an example where p is 512 bits. Look through the example and see what kinds of computations are needed to work with this size of prime modulus.
