Problem Sheet Exercises 9
Jim Laird
April 24, 2018
1. Samantha uses the RSA signature scheme with public modulus and public
verification exponent N = 27212325191 and v = 22824469379. Use what-
ever method you want to factor N, and then forge Samantha’s signature
on the document D = 12910258780.
2. Suppose Bob is using the ElGamal Signature Scheme, and he signs two
messages x1 and x2 with signatures (γ, δ1) and (γ, δ2) respectively. (i.e.
the same value for γ occurs in both signatures because he uses the same
ephemeral key) Suppose also that gcd(δ1 − δ2, p− 1) = 1
• (a) Describe how the epehmeral key r can be computed efficiently
given this information.
• (b) Describe how the signature scheme can then be broken.
• (c) Suppose p = 31847, α = 5 and β = 25703. Given the signatures
(23972, 31396) for the message x = 8990 and (23972, 20481) for the
message x = 31415, compute r and the private key a.
Sony used the same ephemeral key to sign all software for the PS3, allowing
for it to be hacked.
3. A further method of forging El Gamal digital signatures uses existing
signatures:Suppose (γ, δ) is a valid signature for a message x. Then it is
possible for Oscar to sign various other messages.
Choose integers h, i, j such that 0 ≤ h, i, j ≤ p−2 and gcd(hγ−jδ, p−1) =
1 and let
λ = γhαiβj (mod(p))
µ = δλ(hγ − jδ)−1 mod(p− 1)
x′ = λ(hx+ iδ)(hδ − jδ)−1 mod(p− 1)
where (hδ − jδ)−1 is computed modulo (p− 1).
Show that (λ, µ) is a valid signature for x′.
1