c61.py

"""

// ------------------------------------------------------------

61. Duplicate-Signature Key Selection in ECDSA (and RSA)

Suppose you have a message-signature pair. If I give you a public key
that verifies the signature, can you trust that I'm the author?

You shouldn't. It turns out to be pretty easy to solve this problem
across a variety of digital signature schemes. If you have a little
flexibility in choosing your public key, that is.

Let's consider the case of ECDSA.

First, implement ECDSA. If you still have your old DSA implementation
lying around, this should be straightforward. All the same, here's a
refresher if you need it:

    function sign(m, d):
        k := random_scalar(1, n)
        r := (k * G).x
        s := (H(m) + d*r) * k^-1
        return (r, s)

    function verify(m, (r, s), Q):
        u1 := H(m) * s^-1
        u2 := r * s^-1
        R := u1*G + u2*Q
        return r = R.x

Remember that all the scalar operations are mod n, the order of the
base point G. (d, Q) is the signer's key pair. H(m) is a hash of the
message.

Note that the verification function requires arbitrary point
addition. This means your Montgomery ladder (which only performs
scalar multiplication) won't work here. This is no big deal; just fall
back to your old Weierstrass imlpementation.

Once you've got this implemented, generate a key pair for Alice and
use it to sign some message m.

It would be tough for Eve to find a Q' to verify this signature if all
the domain parameters are fixed. But the domain parameters might not
be fixed - some protocols let the user specify them as part of their
public key.

Let's rearrange some terms. Consider this equality:

    R = u1*G + u2*Q

Let's do some regrouping:

    R = u1*G + u2*(d*G)
    R = (u1 + u2*d)*G

Consider R, u1, and u2 to be fixed. That leaves Alice's secret d and
the base point G. Since we don't know d, we'll need to choose a new
pair of values for which the equality holds. We can do it by starting
from the secret and working backwards.

1. Choose a random d' mod n.

2. Calculate t := u1 + u2*d'.

3. Calculate G' := t^-1 * R.

4. Calculate Q' := d' * G'.

5. Eve's public key is Q' with domain parameters (E(GF(p)), n, G').
   E(GF(p)) is the elliptic curve Alice originally chose.

Note that Eve's public key is totally valid: both the base point and
her public point are members of the subgroup of prime order n. Since
E(GF(p)) and n are unchanged from Alice's public key, they should pass
the same validation rules.

Assuming the role of Eve, derive a public key and domain parameters to
verify Alice's signature over the message.

Let's do the same thing with RSA. Same setup: we have some message and
a signature over it. How do we craft a public key to verify the
signature?

Well, first let's refresh ourselves on RSA. Signature verification
looks like this:

    s^e = pad(m) mod N

Where (m, s) is the message-signature pair and (e, N) is Alice's
public key.

So what we're really looking for is the pair (e', N') to make that
equality hold up. If this is starting to look a little familiar, it
should: what we're doing here is looking for the discrete logarithm of
pad(m) with base s.

We know discrete logarithms are easy to solve with Pohlig-Hellman in
groups with many small subgroups. And the choice of group is up to us,
so we can't fail!

But we should exercise some care. If we choose our primes incorrectly,
the discrete logarithm won't exist.

Okay, check the method:

1. Pick a prime p. Here are some conditions for p:

   a. p-1 should be smooth. How smooth is up to you, but you will need
      to find discrete logarithms in each of these subgroups. You can
      use something like Shanks or Pollard's rho to compute these in
      square-root time.

   b. s shouldn't be in any subgroup that pad(m) is not in. If it is,
      the discrete logarithm won't exist. The simplest thing to do is
      make sure they're both primitive roots. To check if an element g
      is a primitive root mod p, check that:

          g^((p-1)/q) != 1 mod p

      For every factor q of p-1.

2. Now pick a prime q. Ensure the same conditions as before, but add these:

   a. Don't reuse any factors of p-1 other than 2. It's possible to
      make this work with repeated factors, but it's a huge
      headache. Better just to avoid it.

   b. Make sure p*q is greater than Alice's modulus N. This is just to
      make sure the signature and padded message will fit under your
      new modulus.

3. Use Pohlig-Hellman to derive ep = e' mod p and eq = e' mod q.

4. Use the Chinese Remainder Theorem to put ep and eq together:

       e' = crt([ep, eq], [p-1, q-1])

5. Your public modulus is N' = p * q.

6. You can derive d' in the normal fashion.

Easy as pie. e' will be a lot larger than the typical public exponent,
but that's still legal.

Since RSA signing and decryption are equivalent operations, you can
use this same technique for other surprising results. Try generating a
random (or chosen) ciphertext and creating a key to decrypt it to a
plaintext of your choice!
"""