An Introduction to Mathematical Cryptography Jeffrey Hoffstein, Joseph H. Silverman, Jill Pipher

Proposed Solutions to the questions in the book An Introduction to Mathematical Cryptography Jeffrey Hoffstein, Joseph H. Silverman, Jill Pipher

Chapter 7 : Digital Signatures

Section 7.2. RSA digital signatures:

7.1. Samantha uses the RSA signature scheme with primes p = 541 and q = 1223 and public verification exponent v = 159853.

1. What is Samantha’s public modulus? What is her private signing key?
i)Public modulus , N = pq 541*1223=661643

N = 661643

ii)s = private signing key

f(N) = (p-1)*(q-1) = (541-1)*(1223-1)=659880

vs= 1(mod(p-1)(q-1)) => 159853.s = 1(mod(540)(1222)

= 159853.s =1(mod 659880)

7.2. Samantha uses the RSA signature scheme with public modulus N = 1562501 and public verification exponent v = 87953. Adam claims that Samantha has signed each of the documents

             D = 119812,     D' = 161153,     D'' = 586036,

and that the associated signatures are

             S = 876453,     S'= 870099,     S''= 602754.

Which of these are valid signatures?

a) D = 119812 and S = 876453

876453 ⁸⁷⁹⁵³MOD 1562501 = 772481

119812 ? 772481
b) D' = 161153 and S' = 870099

870099 ⁸⁷⁹⁵³ MOD 1562501 = 161153

161153 = 161153
c) D'' = 586036 and S'' = 602754

602754⁸⁷⁹⁵³ MOD 1562501 = 586036

586036 = 586036

S' and S'' are valid signatures