- Level: University Degree
- Subject: Mathematical and Computer Sciences
- Word count: 973
IT Security. In this practical we focus on digital signing based on RSA and ElGamal. We also look at the Digital Signature Standard and the use of hashing when signing.
Extracts from this document...
Introduction
SIT392 PUBLIC KEY CRYPTOGRAPHY 2011 TRIMESTER 1
PRACTICAL SESSION 4 SOLUTIONS
In this practical we focus on digital signing based on RSA and ElGamal. We also look at the Digital Signature Standard and the use of hashing when signing.
A. Using RSA to sign.
1. Alice uses an RSA scheme based on the modulus 1081357. She only signs messages with 6 digits (base 10) and odd numbers, but only Alice knows this. You receive a signed message claiming to be from her which is 725226. You look up her public key: 17. Is the message really from Alice?
Solution.
To retrieve the message, you compute 725226^17 mod (phi(n))= mod (1079260) and get
1029556. So the message is not from Alice and could not have been computed using her private key. You should check with Alice in any case.
B. Using El Gamal to sign.
1. Alice derives an El Gamal signature scheme using p = 5023, α = 5 and y = 5a = 3796. Her computations yield β = 5r ≡ 2294 and γ = (444 – 2294 a)r-1 ≡ 3740, where m = 444 is the message. Determine if Bob should accept the signed message as valid.
Solution.
Bob checks by computing 5444 (mod 5023) ≡ 4678
Middle
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.
Conclusion
= 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.
This student written piece of work is one of many that can be found in our University Degree Computer Science section.
Found what you're looking for?
- Start learning 29% faster today
- 150,000+ documents available
- Just £6.99 a month