Re: Signature length of DSA
From: Michael Brown (see_at_signature.below)
Date: 11/30/03
- Previous message: m_houllier: "Design (easy-ish) cipher C++ implentation,"
- In reply to: Gregory G Rose: "Re: Signature length of DSA"
- Next in thread: Paul Rubin: "Re: Signature length of DSA"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sun, 30 Nov 2003 14:32:04 +1300
Gregory G Rose wrote:
> In article <ifYxb.13354$VV6.293606@news.xtra.co.nz>,
> Michael Brown <see@signature.below> wrote:
>> Tom St Denis wrote:
>>> "Michael Brown" <see@signature.below> wrote in message
>>> news:PtAxb.12280$VV6.272318@news.xtra.co.nz...
>>>> Rereading though the DSA specification and some other literature,
>>>> and am wondering a bit about the impact of reducing the signature
>>>> length. Obviously, reducing the public key decreases the security
>>>> because it's easier to factor, and increases the speed. However, I
>>>> coudln't find any information about the effects of reducing the
>>>> signature length (ie: q) from 160 bits to, say, 128 bits (by
>>>> dropping the last 32 bits of SHA1). Obviously it makes birthday and
>>>> brute-force attacks easier (as in any hashing function), but is
>>>> there any other attcks that become viable by doing this?
>>>
>>> 160 wasn't really a random choice for DSA. At 160 bits you make the
>>> SQRT attacks take about the same amount of time as GNFS. At
>>> 128-bits you make them faster.
>>
>> Thanks for the info :) Just to make sure I'm thinking of the same
>> attack ... this is the attack requires two signatures with the same
>> r value?
>
> I don't think that's what Tom meant. With DSA,
> there are *two* discrete logarithm problems
> involved.
>
> You can break the system by solving discrete logs
> modulo P; this problem has a name something like
> "Modular integer discrete logarithm" (check out
> the Handbook of Applied Cryptography for the
> right name and details), and can be solved in
> superpolylogarithmic subexponential time (gotta
> love that name) (same basic formula as for
> factoring).
This is referring to attacking the
y = (g^x) mod p
part I presume.
> You can also solve the problem by solving for
> discrete logarithms in the subgroup of order Q,
> however for this subgroup you can't bring to bear
> the structure of the modular integers, so you
> have to solve it as a General Discrete Logarithm
> problem, for which all the known algorithms have
> complexity sqrt(Q) (Pollards methods,
> baby-step-giant-step, etc). (note 1: HAC
> again...) (note 2: sqrt(Q) is exponential in the
> *size* of Q. This often confuses people.)
Ah, this makes it very clear what I was missing :) I'm presuming this is
referring to the
r = ((g^k) mod p) mod q
part. Solving this (sqrt(q) work) gives you k, which then gives easily gives
you x through the second part of the signature
s = (k^(-1)*(SHA(M) + x*r)) mod q
Thanks for your help.
> So, the 160-bit subgroup size corresponds to 2^80
> complexity to solve it, and also determines the
> size of the signatures. Decreasing the subgroup
> size directly decreases the amount of work to
> break the system, irrespective of the size of the
> modulus.
-- Michael Brown www.emboss.co.nz : OOS/RSI software and more :) Add michael@ to emboss.co.nz - My inbox is always open
- Previous message: m_houllier: "Design (easy-ish) cipher C++ implentation,"
- In reply to: Gregory G Rose: "Re: Signature length of DSA"
- Next in thread: Paul Rubin: "Re: Signature length of DSA"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
|
