Bitslog

Playing with RSA digital signatures I realized that the same system can be used a bit differently and achieve the same security level (as far as I see). I haven’t read about this method before and it’s near impossible to google for a math formula. So this may be a very old broken digital signature method, or it may be a brand new shinny candidate. If you find any previous reference, let me know.

The main idea is to use the hash of the message as the public exponent, and everything else derives naturally from that idea. I show to slightly different schemes. The schemes are probably provably secure in the random oracle model. I leave the security proofs as an exercise to the reader 🙂

The RSAL Digital signature Scheme

KeySetup → n , (p,q)

1. Choose two distinct prime numbers p and q at random, of similar bit-length.
2. Compute n = pq. n is used as the modulus used as the public key.
3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1), where φ is Euler’s totient function.

n is the public key and (p,q) is the private key.

Sign(M) → s

1. Let M be the message to sign.

2. Compute z :=Hash(M).

3. Compute m :=ConvertToInteger(z). m must satisfy 0 ≤ m < φ(n) and gcd(m, φ(n)) = 1. If p and q are safe primes, ConvertToInteger() can be implemented simply by shifting z one bit to the left and making the resulting number odd.

4. Compute v := Hash(z)

5. Compute g := m^-1 ( mod φ(n) ). g is the multiplicative inverse of z (modulo φ(n)).

6. Compute s := v^g (mod n)

7. The signature is s

Verify(M,s,n)

1. Compute z :=Hash(M).

2. Compute v := Hash(z)

3. Compute m :=Integer(z)

4. Compute y := s^m (mod n)

5. Accept the signature if y=v.

Correctness

If the signature is authentic then we have: y = s^m = v^g*m = v

This signature scheme security relies on the difficulty of factoring large integers and the RSA problem (as the RSA cryptosystem).

Suppose that the hash digest is 256 bits. Then for each signature, the “public exponent” size is generally 257 bits. The ConvertToInteger may add a 1-bit can prefix the hash to force the “public exponent” to be always 258 bits.

The “private exponent” will generally have the same size of n, so no small exponent attack is possible.

The cryptosystem has almost no advantage over RSA, only the public key is just a little shorter.

The disadvantages are that signing requires a modular inversion and an exponentiation, while RSA requires only an exponentiation. Also signature verification in RSAL is slower than in RSA signatures. The only advantage I can think of is that this scheme may be naturally better protected against side channel attacks during signature generation. This is because the only secret operation RSAL performs is modular inversion, and modular inversion (performed with the Extended Euclidean algorithm) may be harder to attack than modular exponentiation used in RSA.

Can you break RSAL ? Let me know!

Edit1: I wanted to improve RSAL with some precomputation, and I called that scheme RSALX, but then realized that the RSALX did’t work! So only RSAL is left.

Edit2: After asking in the forum cryptography@metzdowd.com, Prof. Jonathan Katz replied to me that the RSAL scheme seems secure, and in fact similar schemes have been published (such as the Gennaro, Halevi and Rabin scheme – GHR). But GHR relies on a division intractability property of the hash function used, while my scheme does not require this extra condition. So the scheme is in fact new (good) but there is no advantage of my scheme relative to RSA-FDH, except for (maybe) a higher resistance against side-channels.

PS: I’m glad I’ve created my own secure digital signature scheme. I never though I would.  That’s a happy way of beginning year 2014.