Digital Signatures

Question 1

Characteristics of digital signatures

Answer 1

1. Goal: integrity – Message came from sender & is unmodified
2. Public verifiability: Everybody with access to pk can verify a
   signature.
3. Transferability: One can convince others of the signature’s
   validity.
4. Non-repudiation: Alice cannot repudiate that she has signed
   the message.
5. Key authenticity: Publish pk by distributing it with integrity

Question 2

Digital Signatures vs MACs

Answer 2

Signatures
1. No pre-shared secret
2. Private key independent of
verifiers
3. Only a single private key to
keep secret
4. Anyone who wants to verify
the signature can do so
5. Non-repudiation

MACs
1. Need key exchange
2. Secret key for each pair of
parties
3. Only the dedicated partner
can verify.
4. Large number of keys needed
5. Deniable
6. 2-3 orders of magnitude
faster than signature schemes

Question 3

Existential Unforgeability

Answer 3

Game:

An adversary has access to Oracle that can sign any message. The adversary signs an arbitrary number of messages ‘m’ in ‘Q’ Adversary then outputs a message signature pair that was not in Q and if this message and signature verifies then the adversary is successful.

Definition:

A signature scheme is considered existentially unforgeable when under an adaptive chosen message attack the success probability of an adversary in polynomial time is negligible.

Question 4

RSA Signature Key Generation

Answer 4

RSA Key Generation
GenRSA(1 n)
Input: key length n
Generate two large n-bit distinct primes p and q
Compute N = p · q and φ(N) = (p-1) · (q-1)
Choose a random integer e, gcd(e, φ(N)) = 1
Compute e’s inverse d: d · e = 1 (mod φ(N))
Output: pk = (N, e), sk = (N, d)

Question 5

Textbook RSA Key Signatures

Answer 5

Textbook RSA Signatures
KeyGen: pk=(N, e), sk=(N, d) ß GenRSA(1 n )
Sign: Given sk=(N, d) and message m:
σ = m d (mod N)
Verify: Given pk=(e, N) and signature σ:
m = σ e (mod N)

Question 6

How secure are textbook RSA signatures?

Answer 6

Textbook RSA signatures are not secure at all, even if the
RSA assumption holds.

Question 7

No Message Attack

Answer 7

No-message Attack on RSA:

• Situation: An attacker has the public key ( pk = (N, e) ) but no message.
• Method: The attacker picks a random number (sigma) from the group ( ({Z}_N)^* ).
• Attack: They compute ( m = \sigma^e \mod N ), which appears as a valid message-signature pair.
• Result: The attacker presents ( (m, \sigma) ) as the message and its signature without knowing the original message.

This demonstrates an RSA forgery where the attacker creates a signature first and then derives a corresponding message.

Question 8

Selected Message Attack

Answer 8

Selected-Message Attack on RSA:

• Access: Attacker has the public key ( (N, e) ).
• Goal: Forge a signature for a chosen message ( m ).
• Method:
  
  1. Choose a random message ( m_1 ) from ( (mathbb{Z}_N)^* ).
  2. Calculate ( m_2 = m/m_1 ) (mod ( N )).
  3. Obtain legitimate signatures ( sigma_1 ) and (sigma_2 ) for ( m_1 ) and ( m_2 ).
  4. Compute the signature for ( m ) by multiplying ( sigma_1 cdot \sigma_2 ) (mod ( N )).

The attacker can now present ( m ) and ( sigma ) as a valid message-signature pair without the signer’s direct endorsement of ( m ).