<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hi!<br>
This is my first message to the group, and I hope it doesn't bore
you.<br>
<p>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. <br>
</p>
<p lang="en-US"><strong><span style="text-decoration:underline;">The
RSAL Digital signature Scheme</span></strong></p>
<p lang="en-US"><b>KeySetup</b> → <i>n</i> , <i>(p,q)</i></p>
<ol>
<li>Choose two distinct <a
href="http://en.wikipedia.org/wiki/Prime_number">prime numbers</a>
<i>p</i> and <i>q </i>at random, of similar bit-length.</li>
<li>Compute <i>n</i> = <i>pq</i>. <i>n</i> is used as the <a
href="http://en.wikipedia.org/wiki/Modular_arithmetic">modulus</a>
used as the public key.</li>
<li>Compute φ(<i>n</i>) = φ(<i>p</i>)φ(<i>q</i>) = (<i>p</i> − 1)(<i>q</i>
− 1), where φ is <a
href="http://en.wikipedia.org/wiki/Euler%27s_totient_function">Euler’s
totient function</a>.</li>
</ol>
<p lang="en-US"><i>n</i> is the public key and <i>(p,q)</i> is the
private key.</p>
<p lang="en-US"><b>Sign</b>(<i>M</i>) → s</p>
<ol>
<li>
<p lang="en-US">Let <i>M</i> be the message to sign.</p>
</li>
<li>
<p lang="en-US">Compute <i>z</i> :=Hash(<i>M</i>).</p>
</li>
<li>Compute <i>m</i> :=ConvertToInteger(<i>z</i>). <i>m</i> must
satisfy 0 ≤ <i>m</i> < φ(<i>n</i>)<i> </i>and <a
href="http://en.wikipedia.org/wiki/Greatest_common_divisor">gcd</a>(<i>m</i>,
φ(<i>n</i>)) = 1. If <i>p</i> and <i>q</i> are safe primes,
ConvertToInteger() can be implemented simply by shifting <i>z</i>
one bit to the left and making the resulting number odd.</li>
<li>
<p lang="en-US">Compute <i>v</i> := Hash(<i>z</i>)</p>
</li>
<li>Compute <i>g</i> := <i>m</i><sup><i>-1</i></sup> ( mod φ(<i>n</i>)
). <i>g</i> is the <a
href="http://en.wikipedia.org/wiki/Modular_multiplicative_inverse">multiplicative
inverse</a> of z (modulo φ(<i>n</i>)).</li>
<li>
<p lang="en-US">Compute <i>s</i> := <i>v</i><sup><i>g </i></sup>(mod
<i>n</i>)</p>
</li>
<li>
<p lang="en-US">The signature is <i>s</i></p>
</li>
</ol>
<p lang="en-US"><b>Verify</b>(<i>M</i>,<i>s</i>,<i>n</i>)</p>
<ol>
<li>
<p lang="en-US">Compute <i>z</i> :=Hash(<i>M</i>).</p>
</li>
<li>
<p lang="en-US">Compute <i>v</i> := Hash(<i>z</i>)</p>
</li>
<li>
<p lang="en-US">Compute <i>m</i> :=Integer(<i>z</i>)</p>
</li>
<li>
<p lang="en-US">Compute y := <i>s</i><sup><i>m </i></sup>(mod
<i>n</i>)</p>
</li>
<li>
<p lang="en-US">Accept the signature if y=v.</p>
</li>
</ol>
<p lang="en-US"><b>Correctness</b></p>
<p lang="en-US">If the signature is authentic then we have: y = <i>s</i><sup><i>m
</i></sup>= <i>v</i><sup><i>g*m </i></sup><i>= v</i></p>
<p align="JUSTIFY" lang="en-US">This signature scheme security
relies on the difficulty of factoring large integers and the RSA
problem (as the RSA cryptosystem).</p>
<p lang="en-US">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.</p>
<p lang="en-US">The “private exponent” will generally have the same
size of <i>n</i>, so no small exponent attack is possible.</p>
<p lang="en-US">The cryptosystem has almost no advantage over RSA,
only the public key is just a little shorter.</p>
<p lang="en-US">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.<br>
</p>
<p lang="en-US">Is RSAL broken? <br>
</p>
<p lang="en-US">Best regards,<br>
Sergio Demian Lerner.<br>
</p>
<p> </p>
</body>
</html>