[Cryptography] A new digital signature scheme based on the RSA problem?

[Sergio Lerner]

Hi!
 This is my first message to the group, and I hope it doesn't bore you.

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.

*The RSAL Digital signature Scheme*

*KeySetup* ? /n/ , /(p,q)/

 1. Choose two distinct prime numbers
    <http://en.wikipedia.org/wiki/Prime_number> /p/ and /q /at random,
    of similar bit-length.
 2. Compute /n/ = /pq/. /n/ is used as the modulus
    <http://en.wikipedia.org/wiki/Modular_arithmetic> used as the public
    key.
 3. Compute ?(/n/) = ?(/p/)?(/q/) = (/p/ - 1)(/q/ - 1), where ? is
    Euler's totient function
    <http://en.wikipedia.org/wiki/Euler%27s_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
    <http://en.wikipedia.org/wiki/Greatest_common_divisor>(/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
    <http://en.wikipedia.org/wiki/Modular_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. Also the scheme may be provable secure in the R.O.M., while
RSA requires padding to be provable secure.

Is RSAL broken?

Best regards,
 Sergio Demian Lerner.

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131216/620e5c83/attachment.html>