[148475] in cryptography@c2.net mail archive
[Cryptography] A new digital signature scheme based on the RSA
daemon@ATHENA.MIT.EDU (Sergio Lerner)
Mon Dec 16 14:19:20 2013
X-Original-To: cryptography@metzdowd.com
Date: Mon, 16 Dec 2013 16:13:25 -0300
From: Sergio Lerner <sergiolerner@pentatek.com>
To: cryptography@metzdowd.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
This is a multi-part message in MIME format.
--===============3724582681598464607==
Content-Type: multipart/alternative;
boundary="------------000607090509090501020004"
This is a multi-part message in MIME format.
--------------000607090509090501020004
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
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.
--------------000607090509090501020004
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
<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>
--------------000607090509090501020004--
--===============3724582681598464607==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============3724582681598464607==--
