[148491] in cryptography@c2.net mail archive
Re: [Cryptography] A new digital signature scheme based on the RSA
daemon@ATHENA.MIT.EDU (Sergio Lerner)
Tue Dec 17 13:50:41 2013
X-Original-To: cryptography@metzdowd.com
Date: Tue, 17 Dec 2013 13:31:26 -0300
From: Sergio Lerner <sergiolerner@pentatek.com>
To: Jonathan Katz <jkatz@cs.umd.edu>
In-Reply-To: <Pine.LNX.4.64.1312161521550.26882@fireball.cs.umd.edu>
Cc: cryptography@metzdowd.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
I think the Gennaro,Halevi,Rabin scheme is completely broken. I cannot
see how they prevent that an attacker forge a signature for H(y).
Suppose H(x)=3Dk*H(y), k can generally be computed in Zn by inverting H(y)
using the Extented Ecleudian algorithm in Zn and computing
k=3DH(x)*h(y)^-1 (mod n). It's unimportant if H(x) divides H(y) in Z or
not. Inverting H(y) will not be possible if it has no inverse, but it
must be the case that gcd(h(y),n)=3D1, if not then H(y) could be used to
factor n, so we can assume h(y) is invertible.
Suppose w is the signature for x, then w^H(x) =3D s
We can forge a signature z for H(y) as z =3D (w^k).
This is because z^H(y) =3D w^k^H(y) =3D w^(k*H(y)) =3D w^H(x) =3D s
What's the scheme security? It seems to me that none.
What did I do wrong?
=
Best regards, Sergio.
=
16/12/2013 05:26 p.m., Jonathan Katz escribi=F3:
> On Mon, 16 Dec 2013, Sergio Lerner wrote:
>
>> 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*
>
> <snip>
>
> Your scheme is similar to several schemes in the literature based on
> the so-called *strong RSA* assumption (as compared to the [regular]
> RSA assumption). See, for example:
> http://www.research.ibm.com/people/s/shaih/pubs/ghr99.ps.gz
> http://www.shoup.net/papers/sig.ps
> (But make sure to also check google scholar for the followup work.)
>
> Note further that there is no real reason to make your base 'v' depend
> on the message; you may as well have the signer fix it as part of
> their public key once and for all.
> _______________________________________________
> The cryptography mailing list
> cryptography@metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
>
>
>
> -----
> Se certifico que el correo no contiene virus.
> Comprobada por AVG - www.avg.es
> Version: 2014.0.4259 / Base de datos de virus: 3658/6923 - Fecha de la
> version: 15/12/2013
>
>
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
