Digital Signatures

Prev: Integer Factorization and RSA Next: Combinatorics Probability and Information Theory

Exercises

Section 4.2. RSA Digital Signatures

4.1

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

(a) What is Samantha’s public modulus? What is her private signing key?

(b) Samantha signs the digital document $D=630579$. What is the signature?

4.2

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

$$D=119812,D^{\prime }=161153,D^{\prime \prime }=586036,$$

and that the associated signatures are

$$S=876453,S^{\prime }=870099,S^{\prime \prime }=602754.$$

Which of these are valid signatures?

4.3

Samantha uses the RSA signature scheme with public modulus and public verification exponent

$$N=27212325191\text{and}e=22824469379.$$

Use whatever method you want to factor $N$, and then forge Samantha’s signature on the document $D=12910258780$.

4.4

Suppose that Alice and Bob communicate using the RSA PKC. This means that Alice has a public modulus $N_A=p_A{q}_A$, a public encryption exponent $e_A$, and a private decryption exponent $d_A$, where $p_A$ and $q_A$ are primes and $e_A$ and $d_A$ satisfy

$$e_A{d}_A\equiv 1(\mathrm{mod}(p_A-1)(q_A-1)).$$

Similarly, Bob has a public modulus $N_B=p_B{q}_B$, a public encryption exponent $e_B$, and a private decryption exponent $d_B$.

In this situation, Alice can simultaneously encrypt and sign a message in the following way. Alice chooses her plaintext $m$ and computes the usual RSA ciphertext

$$c\equiv m^{e_B}(\mathrm{mod}{N}_B).$$

She next applies a hash function to her plaintext and uses her private decryption key to compute

$$s\equiv \mathrm{Hash}(m{)}^{d_A}(\mathrm{mod}{N}_A).$$

She sends the pair $(c,s)$ to Bob.

Bob first decrypts the ciphertext using his private decryption exponent $d_B$,

$$m\equiv c^{d_B}(\mathrm{mod}{N}_B).$$

He then uses Alice’s public encryption exponent $e_A$ to verify that

$$\mathrm{Hash}(m)\equiv s^{e_A}(\mathrm{mod}{N}_A).$$

Explain why verification works, and why it would be difficult for anyone other than Alice to send Bob a validly signed message.

Section 4.3. Discrete Logarithm Digital Signatures

4.5

Samantha uses the Elgamal signature scheme with prime $p=6961$ and primitive root $g=437$.

(a) Samantha’s private signing key is $a=6104$. What is her public verification key?

(b) Samantha signs the digital document $D=5584$ using the random element $k=4451$. What is the signature?

4.6

Samantha uses the Elgamal signature scheme with prime $p=6961$ and primitive root $g=437$. Her public verification key is $A=4250$. Adam claims that Samantha has signed each of the documents

$$D=1521,D^{\prime }=1837,D^{\prime \prime }=1614,$$

and that the associated signatures are

$$(S_1,S_2)=(4129,5575),(S_1^{\prime },S_2^{\prime })=(3145,1871),(S_1^{\prime \prime },S_2^{\prime \prime })=(2709,2994).$$

Which of these are valid signatures?

4.7

Let $p$ be a prime, let $i$ and $j$ be integers with $\gcd (j,p-1)=1$, and let $A$ be arbitrary. Set

$$S_1\equiv g^i{A}^j(\mathrm{mod}p),S_2\equiv -S_1{j}^{-1}(\mathrm{mod}p-1),D\equiv -S_{1}i{j}^{-1}(\mathrm{mod}p-1).$$

Prove that $(S_1,S_2)$ is a valid Elgamal signature on the document $D$ for the verification key $A$. Thus Eve can produce signatures on random documents.

4.8

Suppose that Samantha is using the Elgamal signature scheme and that she is careless and uses the same random element $k$ to sign two documents $D$ and $D^{\prime }$.

(a) Explain how Eve can tell at a glance whether Samantha has made this mistake.

(b) If the signature on $D$ is $(S_1,S_2)$ and the signature on $D^{\prime }$ is $(S_1^{\prime },S_2^{\prime })$, explain how Eve can recover $a$, Samantha’s private signing key.

(c) Apply your method from (b) to the following example and recover Samantha’s signing key $a$, where Samantha is using the prime $p=348149$, base $g=113459$, and verification key $A=185149$.

$$\begin{array}{rlrlrl}D& =153405,& S_1& =208913,& S_2& =209176,\\ D^{\prime }& =127561,& S_1^{\prime }& =208913,& S_2^{\prime }& =217800.\end{array}$$

4.9

Samantha uses DSA with public parameters $(p,q,g)=(22531,751,4488)$. She chooses the secret signing key $a=674$.

(a) What is Samantha’s public verification key?

(b) Samantha signs the document $D=244$ using the random element $k=574$. What is the signature?

4.10

Samantha uses DSA with public parameters $(p,q,g)=(22531,751,4488)$. Her public verification key is $A=22476$.

(a) Is $(S_1,S_2)=(183,260)$ a valid signature on the document $D=329$?

(b) Is $(S_1,S_2)=(211,97)$ a valid signature on the document $D=432$?

4.11

Samantha’s DSA public parameters are $(p,q,g)=(103687,1571,21947)$, and her public verification key is $A=31377$. Use whatever method you prefer (brute-force, collision, index calculus, …) to solve the DLP and find Samantha’s private signing key. Use her key to sign the document $D=510$ using the random element $k=1105$.