DSS Keys
Nicholas Cole
Hash: SHA1
1. Why are signing keys limited in length?
2. Why does this not make them easy to crack?
Thanks for any help,
Nick
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i
iQA/AwUBNtPWYb7aI4xWD24oEQLaBACg0EZcqyBjIFSAohTQSex2iw+jXBQAn02i
IwQ9aPsZnSiuUmmmHCCvbr5e
=pXTo
-----END PGP SIGNATURE-----
Sam Simpson
Hash: SHA1
Nicholas Cole wrote in message <7b0ks9$l2e$1...@news.ox.ac.uk>...
>
>1. Why are signing keys limited in length?
Because that's what's stipulated in FIPS186-1 & ANSI930-1 (the DSS
documents)
>2. Why does this not make them easy to crack?
DSS keys are not "easy to crack" by any stretch of the imagination,
though they could certainly be made "harder" by increasing the algorithm
parameters. But then the implementation would not conform to the
standard.....
Cheers,
- --
Sam Simpson
Comms Analyst
http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because he's
kill filed. See http://www.openpgp.net/FUD for why!
-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0.2
iQA/AwUBNtPeB+0ty8FDP9tPEQJyvQCg5Ue78B9JUVrWnBwj6dSx/gZQS1QAni5B
PdoPYzGFBz2Gri8GsXZuLYZl
=aME2
-----END PGP SIGNATURE-----
Nicholas Cole
Hash: SHA1
Sam Simpson wrote in message <36d3d...@nnrp1.news.uk.psi.net>...
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>Nicholas Cole wrote in message <7b0ks9$l2e$1...@news.ox.ac.uk>...
>>
>>1. Why are signing keys limited in length?
>
>
>Because that's what's stipulated in FIPS186-1 & ANSI930-1 (the DSS
>documents)
>
>>2. Why does this not make them easy to crack?
>
>
>DSS keys are not "easy to crack" by any stretch of the imagination,
>though they could certainly be made "harder" by increasing the
algorithm
>parameters. But then the implementation would not conform to the
>standard.....
>
I understand that that is what is stipulated, but if encryption keys
need to be (some say) at least 2Mb, what is different about signing
keys that means that they can be short.
Cheers,
Nick
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i
iQA/AwUBNtP8v77aI4xWD24oEQKjXwCgu10dSlgy77FoYJNQJ3bRQJKl49AAoJLr
Ncjj2BKJ9tnhoWidZ8T/adDB
=erK/
-----END PGP SIGNATURE-----
Anonymous
> I understand that that is what is stipulated, but if encryption keys
> need to be (some say) at least 2Mb, what is different about signing
> keys that means that they can be short.
>
> Cheers,
>
> Nick
Signing keys have a completely different function than encryption
keys. The purpose of a signing key is just to calculate a summary
(hash) of the signed material. It does not need to resist "cracking"
in the same way as an encryption key. All a signing key needs to do is
make it near impossible to create a message that is different from the
original and have the same hash.
Sam Simpson
Hash: SHA1
Nicholas Cole wrote in message <7b0uf7$p8l$1...@news.ox.ac.uk>...
>
>Sam Simpson wrote in message <36d3d...@nnrp1.news.uk.psi.net>...
<SNIP>
>I understand that that is what is stipulated, but if encryption keys
>need to be (some say) at least 2Mb, what is different about signing
>keys that means that they can be short.
<SNIP>
I have attempted to answer this question in the next version of the PGP
DH vs PGP RSA FAQ (unpublished ATM) which is published on my Web Site.
Please find below the new (yet to be proof read!) section:
"2.10. Why are DSS keys significantly smaller than DH keys?
Clearly, if DH keys can be up to 4,096 bits while DSS keys can only be
1,024-bits then there is a serious disparity between the strength
offered by these two types of keys.
An initial thought was; DSS keys are offered more security by combining
both ElGamal and Schnorr signature schemes. This is untrue however as
breaking ElGamal clearly breaks DSS.
A 1,024-bit DSS key appears far easier to break than a DH key of greater
length. This is indeed so; DH and DSS are based on the same underlying
mathematical theory - a key of 1,024-bits is inherently easier to break
than a 4,096-bit key.
So, why the contrast? Well, firstly, PGP simply implements the Digital
Signature Standard as per [FIPS186]. DSS is the de facto standard for
digital signatures, and PGP implements DSS to the maximum strength
possible within the bounds of the standard (e.g. with p up to
1024-bits). An implementation of "DSS" with p greater than 1024-bits
would no longer conform to the standard.
Secondly, let's look at the purpose of encryption & signature keys.
Encryption is used to hide data - a compromise of the key would clearly
make all messages readable and would thus make encryption entirely
useless. This is a real problem; it will one day certainly be possible
to read messages secured with 1,024-bit keys.
Signature keys are used to offer integrity, authentication and
non-repudiation. The ability to "break" a DSS key would allow an
adversary to forge digital signatures. DSS keys of 1,024-bits are secure
for several years, then what? Well, time stamping and document trail
mechanisms can be used to "prove" the genuineness of an old digital
signature (which could have been forged using what will be current
technology). This assumes that there are no totally unexpected
breakthroughs in computing discrete logs.
So, one can see that breaking an encryption key is catastrophic, while
breaking a signature key at some date in the future is nowhere near as
disastrous.
If you are interested in reading further on this point then I recommend
A.M.Odlyzko, "The Future of Integer Factorization" [Odl95] - which also
similarly covers key lengths for DH/ElGamal based systems."
Any feedback appreciated. Regards,
- --
Sam Simpson
Comms Analyst
http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because he's
kill filed. See http://www.openpgp.net/FUD for why!
-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0.2
iQA/AwUBNtQ92O0ty8FDP9tPEQKFDgCg+D3H5LgmesBz06hoo0gNqMidvacAoJUp
V9gE6yX5ZChWOx8m6wXumxB/
=E2fl
-----END PGP SIGNATURE-----
Sam Simpson
Hash: SHA1
I disagree. Signature keys need to be "uncrackable" in the same way
that encryption keys are.
If a signature key is "broken" then an adversary can forge signatures on
*any* documents.
- --
Sam Simpson
Comms Analyst
http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because he's
kill filed. See http://www.openpgp.net/FUD for why!
Anonymous wrote in message <1999022415...@replay.com>...
>Nicholas Cole wrote:
>> I understand that that is what is stipulated, but if encryption keys
>> need to be (some say) at least 2Mb, what is different about signing
>> keys that means that they can be short.
>>
>> Cheers,
>>
>> Nick
>
>Signing keys have a completely different function than encryption
>keys. The purpose of a signing key is just to calculate a summary
>(hash) of the signed material. It does not need to resist "cracking"
>in the same way as an encryption key. All a signing key needs to do is
>make it near impossible to create a message that is different from the
>original and have the same hash.
-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0.2
iQA/AwUBNtQ/3O0ty8FDP9tPEQI2CgCg31Or9CIT3JeFbNAeSFq7n38mH1gAoO5L
fL/q8DuqN+qF7I8wSML2FrWX
=5scv
-----END PGP SIGNATURE-----
Nicholas Cole
Hash: SHA1
[SNIP]
>
>Signature keys are used to offer integrity, authentication and
>non-repudiation. The ability to "break" a DSS key would allow an
>adversary to forge digital signatures. DSS keys of 1,024-bits are
secure
>for several years, then what? Well, time stamping and document trail
>mechanisms can be used to "prove" the genuineness of an old digital
>signature (which could have been forged using what will be current
>technology). This assumes that there are no totally unexpected
>breakthroughs in computing discrete logs.
So DSS keys of 1024 length can be expected to be broken at the same
time as encryption keys? Isn't this very much a real problem? People
currently expect to be able to use 2 or 3 MB keys for about 5 to ten
years. No one expects 1 Mb keys to last that long. In addition,
given the time it seems to take to get an "international" version of
PGP running, isn't it time to start thinking about longer signature
keys. Of course, I see the point that a sig should be short and
convenient, but surely if mid-term security is at stake? I for one
consider the value, for the kinds of things I do (ie. not FBI or MI5
work!), of PGP to be the ability to sign messages and know that
nothing I haven't signed can be forged.
Apologies for the cross posting. I thought others might find this
thread interesting ... it began in alt.security.pgp
Best wishes,
Nick
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.0.2i
iQA/AwUBNtRJIb7aI4xWD24oEQJNXQCfQXkwlWTze6h6cSrTPSsp45fpXksAn3Yp
jJiMIX5tb05otpq030Nq8AvN
=8wYf
-----END PGP SIGNATURE-----
Thomas J. Boschloo
> "2.10. Why are DSS keys significantly smaller than DH keys?
> Clearly, if DH keys can be up to 4,096 bits while DSS keys can only be
> 1,024-bits then there is a serious disparity between the strength
> offered by these two types of keys.
I believe to have read somewhere that a 1024 bit DSS key is about as
strong as a 2048 bit DH key. I could be completely of target however
since I am not experienced in these matters. Better ask in sci-crypt ;-)
Thomas
--
Seven of Nine: "You will be assimilated"
PGP key: http://x13.dejanews.com/getdoc.xp?AN=406702465
Post your keys to news:alt.security.keydist
Thomas J. Boschloo
> Apologies for the cross posting. I thought others might find this
> thread interesting ... it began in alt.security.pgp
c.s.p.d is Sternlight's newsgroup, nothing useful gets accomplished
there! It's just somebody says something interesting, Sternfud
disagrees, everybody replies to Sternfud, Sternfud replies to everybody.
You get the basic idea. That newsgroup is as good as dead!
Thomas <grin>
(P.S. You should try sci.crypt instead. Really excellent people in
there, they are CRYPTOGODS)
Brandon Blackmoor
Thomas J. Boschloo wrote in message
<36D459A5...@multiweb.nl>...
>
>c.s.p.d is Sternlight's newsgroup, nothing useful gets
accomplished
>there!
So killfile him. I haven't seen a Sternlight post on c.s.p.d. in
weeks, the list of posts I do see is much shorter, and I have
had most my questions there answered (which I greatly
appreciate). About the only puzzle I am still struggling with is
how to access the conventional encryption ability of PGP 6 from
a Visual Basic program, but I am sure that the answer to that
will come eventually (or I'll figure it out myself).
BBlackmoor
-----BEGIN PGP SIGNATURE-----
Version: 6.0.2ckt http://members.tripod.com/IRFaiad
iQCVAwUBNtR61SV2E2252X/xAQEzIwP8DgiTbrhAmNk8yTN9Euw8La2sVm9bgtfA
cCt1B1zGiJkdZCC2X9GF94yqLquY/3F2vTTX9YAKI6D9VEHBUpT8LmbLMu+moa4C
QmncplhxH5Ax3igXcJ26Kt5PcQL5Q8AUy0I6Wqf7Rdcw1eCuKQM48Qgusqv8NFQK
7n8DKjJTETc=
=MWzw
-----END PGP SIGNATURE-----
ESPO247
>(hash) of the signed material.
No. A signing key is used to sign hashed material.
>It does not need to resist "cracking"
>in the same way as an encryption key.
Of course not, if you wan't your messages forged.
>All a signing key needs to do is
>make it near impossible to create a message that is different from the
>original and have the same hash.
No. It is the responsibility of the hash to be collision (two messaegs with the
same hash) resistant.
-
Espo
Free Kevin! www.KevinMitnick.com
"Mary had a crypto key, she kept it in escrow, and everything that Mary said,
the Feds were sure to know." -- Sam Simpson
E-mail me for my PGP keys.
DH/DSS Key ID: 0x927BED1D
RSA Key ID: 0x76C6AB73
Brandon Blackmoor
Brandon Blackmoor wrote in message
<7b1tsh$e2m$1...@winter.news.rcn.net>...
>
>About the only puzzle I am still struggling with is how to
access
>the conventional encryption ability of PGP 6 from a Visual
Basic
>program, but I am sure that the answer to that will come
eventually
>(or I'll figure it out myself).
As luck would have it, I just found something that *might* be
the answer to my puzzle:
http://www.oz.net/~srheller/privacy/pgp/spgp/spgp.htm
BBlackmoor
-----BEGIN PGP SIGNATURE-----
Version: 6.0.2ckt http://members.tripod.com/IRFaiad
iQCVAwUBNtSKEiV2E2252X/xAQEuyAQAwn4BmSXX1DJ+4H/MWaWkrDBhcn22UJrz
JfsJZZFaU09AIci2QtCQnTxB+JscJRwpx/pYUoro3qEK0bB/yHkrZQL1gh1j56Lq
3sJPhm0JqIWr8N8b5rhWsU4lDsQp5rIwfboGEO/slKXhvK2T0ei+XgZJJjm089oC
XNKW+FF764s=
=Vvdg
-----END PGP SIGNATURE-----
Thomas J. Boschloo
> So killfile him. I haven't seen a Sternlight post on c.s.p.d. in
> weeks, the list of posts I do see is much shorter, and I have
> had most my questions there answered (which I greatly
> appreciate).
I would do that (if that is at all possible in Netscape 4.5, killfiles
seemed to only work on e-mail in Netscape 4.04), but then I will still
see the replies to him (with quotation of his famous posting style).
Best would be to killfill every subtread his is in, but I have just
given up on it. I like the informative posts of Ed Stone and others, but
I'll just stick with the less volumious alt.security.pgp for now.
Thanx 4 replying,
Thomas
Sam Simpson
Hash: SHA1
Sorry Thomas.....
If one can break an arbitrary 1,024-bit DH key in reasonable time, then
1,024-bit DSS is also toast.
- --
Sam Simpson
Comms Analyst
http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because he's
kill filed. See http://www.openpgp.net/FUD for why!
Thomas J. Boschloo wrote in message <36D45815...@multiweb.nl>...
>Sam Simpson wrote:
>
>> "2.10. Why are DSS keys significantly smaller than DH keys?
>> Clearly, if DH keys can be up to 4,096 bits while DSS keys can only
be
>> 1,024-bits then there is a serious disparity between the strength
>> offered by these two types of keys.
>
>I believe to have read somewhere that a 1024 bit DSS key is about as
>strong as a 2048 bit DH key. I could be completely of target however
>since I am not experienced in these matters. Better ask in sci-crypt
;-)
-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0.2
iQA/AwUBNtUKvu0ty8FDP9tPEQIRpQCg4mmwlMY2E4HA16w2H/Frv+aqMzQAnRcC
LRyKLN5ojs1JL8RpuPxWnAuS
=iWyC
-----END PGP SIGNATURE-----
Sam Simpson
Hash: SHA1
Yes there is a current discrepancy between signature strength and
encryption strength, yes it's a pain the arse.
But, the "accepted" hash functions, SHA-1, RIPEMD and MD5 all need
increasing in length if the overall strength of a signature scheme is to
be increased (it is thought that DSS can be broken in 2^80 operations -
but collisions in SHA-1 and RIPEMD can also be found in 2^80 via the
birthday attack, in MD5 collisions can be found in far fewer
operations).
If you need to worry about assuring the validity of signatures at a
future date then certain manual mechanisms can be applied. Of course,
this isn't pretty, but it's workable.
Role on DSS mark 2, huh?
- --
Sam Simpson
Comms Analyst
http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because he's
kill filed. See http://www.openpgp.net/FUD for why!
Nicholas Cole wrote in message <7b1hl4$408$1...@news.ox.ac.uk>...
<SNIP>
>So DSS keys of 1024 length can be expected to be broken at the same
>time as encryption keys? Isn't this very much a real problem? People
>currently expect to be able to use 2 or 3 MB keys for about 5 to ten
>years. No one expects 1 Mb keys to last that long. In addition,
>given the time it seems to take to get an "international" version of
>PGP running, isn't it time to start thinking about longer signature
>keys. Of course, I see the point that a sig should be short and
>convenient, but surely if mid-term security is at stake? I for one
>consider the value, for the kinds of things I do (ie. not FBI or MI5
>work!), of PGP to be the ability to sign messages and know that
>nothing I haven't signed can be forged.
>
>Apologies for the cross posting. I thought others might find this
>thread interesting ... it began in alt.security.pgp
>
>Best wishes,
>
>Nick
-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0.2
iQA/AwUBNtUdT+0ty8FDP9tPEQKRuQCfcct4QM+FAZXzMKp21QaRNAL810gAn162
Cx0S3gvGVxVfQ+BEsiGiRBs9
=sVpV
-----END PGP SIGNATURE-----
Thomas J. Boschloo
>
> Sorry Thomas.....
>
> If one can break an arbitrary 1,024-bit DH key in reasonable time, then
> 1,024-bit DSS is also toast.
I find this hard to believe (no offence), since a 1024 bit DH is only
about 56 bits symmetric strong. I have kept a post by Lutz Donnerhacke
which stated this. I haven't checked IEEE P1363 since you need to
register to their website or something and I don't like that :-(
<http://standards.ieee.org/>
Here is his post:
----------------------------------------------------------------------
> Subject: Re: RSA Vs DH/DSS?
> Date: 13 Nov 1998 12:49:48 GMT
> From: lu...@taranis.iks-jena.de (Lutz Donnerhacke)
> Organization: IKS GmbH Jena
> Newsgroups: comp.security.pgp.discuss,alt.security.pgp,comp.security.pgp.resources
> Followup-To: sci.crypt
>
> * |MrB| wrote:
> >Who encryption is the best or the hardest to crack between
> > RSA Vs DH/DSS?
>
> DH is easy to break, but your may refer to ElGamal.
>
> The question itself is: What is more difficult, discrete logarithms over
> a finite field (ElGamal, Diffie-Hellman, DSA) or discrete logarithms over
> a finite abelian ring which is not a domain (RSA)? And the answer is
> unknown.
> A theoretical result is, that discrete logarithms over a finite field are
> at most as difficult as the factorisation of the predecessor of the
> characteristic of the field which is always prime.
> OTOH discrete logarithms over a finite ring are at most as difficult as the
> factorisation of the ring characteristic itself which is composite is this
> case.
> Several algorithms are knows to solve the problems. But it's unknown what
> algorithms are known to the secret services. The public knownlegde is
> documented in the standard P1363 of the IEEE. Appedix A says:
>
> Ring Field
> -----+---- -----+----
> 512 | 63 |
> 786 | 76 |
> 1024 | 86 1024 | 56
> 2048 | 117 2048 | 112
> 3072 | 139 3072 | 128
> 4096 | 157 4096 | 168
>
> So a 512 bit RSA key is as secure as a 63 bit symmetric key (runtime
> complexity). A 1024 bit DSA key is as secure as a 56 bit symmetric key.
> It's easy to see, that 3100 bit are enough to fit every paranoic feelings.
> For longer keys RSAs security grows slower, but the initial security is
> better.
> 1024 bit are acceptable for RSA but not for DSA or ElGamal. Due to the
> fact, that RfC 2440 relates on the DSA signature even for an ElGamal key,
> the communication security is limited to the lowest of both.
>
> As you know, the whole topic is irrelevant as long keys are stored on
> insecure devices and operating systems, handled by incompetent users (click
> and pray), managed by insufficent software running inadequate trust models.
>
> Have fun in sci.crypt
----------------------------------------------------------------------
ssim...@hertreg.ac.uk
"Thomas J. Boschloo" <nospam...@multiweb.nl> wrote:
> Sam Simpson wrote:
> >
> > Sorry Thomas.....
> >
> > If one can break an arbitrary 1,024-bit DH key in reasonable time, then
> > 1,024-bit DSS is also toast.
>
> I find this hard to believe (no offence), since a 1024 bit DH is only
> about 56 bits symmetric strong. I have kept a post by Lutz Donnerhacke
> which stated this. I haven't checked IEEE P1363 since you need to
> register to their website or something and I don't like that :-(
> <http://standards.ieee.org/>
Who is Lutz Donnerhacke?
I totally disagree with the substance of his post (and so does Bruce Schneier,
RSA Labs, Roger Schafly et al).
Read the references in my PGP DH vs RSA FAQ (when it's back online!). I am
yet to find a single ref that supports this view.
Have you got a copy of HAC / AC2 / Koblitz text (Course in number theory) or
Sinsons Crypto Theory and Practice?
I think Lutz is on a wind-up! You should really check references and tables
rather than blindly follow words of another ;)
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
> Here is his post:
Where is this table from? 1024-bit DSA is thought to have an approx. strength
of a 2^80 symmetric cipher! Nowhere near 56 bits!
> >
> > So a 512 bit RSA key is as secure as a 63 bit symmetric key (runtime
> > complexity). A 1024 bit DSA key is as secure as a 56 bit symmetric key.
> > It's easy to see, that 3100 bit are enough to fit every paranoic feelings.
> > For longer keys RSAs security grows slower, but the initial security is
> > better.
Bollocks.
> > 1024 bit are acceptable for RSA but not for DSA or ElGamal. Due to the
> > fact, that RfC 2440 relates on the DSA signature even for an ElGamal key,
> > the communication security is limited to the lowest of both.
More bollocks. Read AC2.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Thomas J. Boschloo
>
> Who is Lutz Donnerhacke?
>
> I totally disagree with the substance of his post (and so does Bruce Schneier,
> RSA Labs, Roger Schafly et al).
>
> Read the references in my PGP DH vs RSA FAQ (when it's back online!). I am
> yet to find a single ref that supports this view.
>
> > Here is his post:
[snip]
> > > A theoretical result is, that discrete logarithms over a finite field are
> > > at most as difficult as the factorisation of the predecessor of the
> > > characteristic of the field which is always prime.
> > > OTOH discrete logarithms over a finite ring are at most as difficult as the
> > > factorisation of the ring characteristic itself which is composite is this
> > > case.
> > > Several algorithms are knows to solve the problems. But it's unknown what
> > > algorithms are known to the secret services. The public knownlegde is
> > > documented in the standard P1363 of the IEEE. Appedix A says:
> > >
> > > Ring Field
> > > -----+---- -----+----
> > > 512 | 63 |
> > > 786 | 76 |
> > > 1024 | 86 1024 | 56
> > > 2048 | 117 2048 | 112
> > > 3072 | 139 3072 | 128
> > > 4096 | 157 4096 | 168
>
> Where is this table from? 1024-bit DSA is thought to have an approx. strength
> of a 2^80 symmetric cipher! Nowhere near 56 bits!
_From IEEE P1363 Appendix A, I hope! I haven't gone throught the trouble
to subscribing to their mailing list at
http://grouper.ieee.org/groups/1363/draft.html. But Lutz seemed to know
what he was talking about. At least he knew of the existance of the
document?
Forgive me for crossposting, but I just wanted to be sure ;)
Ludwig Huegelschaefer
ssim...@hertreg.ac.uk wrote:
>
> Who is Lutz Donnerhacke?
http://www.iks-jena.de/mitarb/lutz/
mailto:L.Donn...@iks-jena.de
Sam Simpson
Hash: SHA1
Cheers for the pointer Ludwig,
I recommend that if anyone has any doubt about the relative strengths of
RSA & DH, they read
"The Future of Integer Factorization" by A.M.Odlyzko - it's available
on the net somewhere.
Also, try the RSA FAQ (v4) Question 4.1.2.1. What key size should be
used?
Seriously, I'm not going to spend any more time proving something that's
in virtually every modern crypto books.
- --
Sam Simpson
Comms Analyst
http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
If you're wondering why I don't reply to Sternlight, it's because he's
kill filed. See http://www.openpgp.net/FUD for why!
Ludwig Huegelschaefer wrote in message <36DA5E3C...@gmx.net>...
-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0.2
iQA/AwUBNtp94u0ty8FDP9tPEQI9eACfZ78PwfzLotzBViTvq9jruOLROK8AoLJ2
kVrKwAx73QARQOfyxFcj0bFH
=CS7R
-----END PGP SIGNATURE-----
Thomas J. Boschloo
Well, since Sam seemed to get a little fed up on the whole subject, I
decided to subscribe to their mailing list myself. I found the current
draft very interesting en surprisingly readable for someone like me.
This is what the draft (version 8) really said in Appendix A (note: DL
means Discrete Logarithm, like in DH/DSS):
***
A.3.10 Parameters for Common Key Sizes
When selecting domain parameters for DL-based cryptography over binary
fields, it is necessary to begin by choosing the following:
— The degree m of the field (so that the field has 2^m elements)
— The prime number r which is to serve as the order of the base point
These two numbers are related by the condition that r must be a
primitive divisor of 2^m – 1 (see Annex A.3.9). Moreover, it is a common
practice to choose the two numbers to provide comparable levels of
security. (See Annex D.4.1.4, Note 1.) Each parameter depends on the
size of the symmetric keys which the DL system is being used to protect.
The following table lists several common symmetric key lengths. For each
length is given a set of parameters of m and r which can be used in
conjunction with symmetric keys of that length.
Key Size m r
40 189 207617485544258392970753527
56 384 442499826945303593556473164314770689
64 506 2822551529460330847604262086149015242689
80 1024 7455602825647884208337395736200454918783366342657
112 2068 2845635541041154750961337415015805123165674305234451316-
1858038422883778013.
128 2880 1919487818858585561290806193694428146403929496534649176-
7953330250249208842371201
***
So Lutz Donnerhacke was indeed on a wind up :-) [Hope he reads this
post]
1024 DSS is about 80 bit symmetric (if I understand the text correctly).
Or maybe there was an error in an earlier draft...
For eliptic curve it had the following estimated strengths (Appendix D):
Size of generator Processing Time
(Bits) (MIPS-Years)
128 4.0x10^5
172 3x10^12
234 3x10^21
314 2x10^33
A minimum length of 161 is suggested by the draft for EC (1024 bits for
DL and 1024 bit for IF).
For IF (Integer Factorization, like RSA) it had the following
interesting table:
Modulus Processing Time Memory Requirements
(Bits) (MIPS-Years) Sieving process Linear Algebra
512 4.0x10^5 130 Kb 20 Mb
1024 3x10^12 300 Mb 100 Tb
2048 3x10^21 8000 Tb 3000 Tb
The sieving process can be done on multiple computers in parallel, the
linear deduction must be done on a single processor.
Hope this was informative (and I made no typo's).
Regards,
Sam Simpson
Hash: SHA1
(Removed sci.crypt from the TO list, coz I'm having a whinge...)
Thomas J. Boschloo wrote in message
<36DCFBFA...@multiweb.nl>...
>"Thomas J. Boschloo" wrote:
<SNIP>
>Well, since Sam seemed to get a little fed up on the whole
subject, I
>decided to subscribe to their mailing list myself. I found the
current
>draft very interesting en surprisingly readable for someone like
me.
>This is what the draft (version 8) really said in Appendix A
(note: DL
>means Discrete Logarithm, like in DH/DSS):
I just get fed up of having to repeat and justify myself - my FAQ
gives copious references to highly respected material. Why did I
even bother to produce the FAQ?
You can lead a horse to water, but you can't make it drink, huh
Thomas?
<SNIP>
>So Lutz Donnerhacke was indeed on a wind up :-) [Hope he reads
this
>post]
Thankyou! Didn't I make this very point a week ago? Didn't I
also include reference to same?
>1024 DSS is about 80 bit symmetric (if I understand the text
correctly).
>Or maybe there was an error in an earlier draft...
>Hope this was informative (and I made no typo's).
Not really. One only needed to read one of a hundred references
to get exactly the same information.
I think it's been a proper waste of my time (but that's probably
me just being in a grumpy mood).
- --
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive
encryption & Delphi Crypto Components. PGP Keys available at the
same site.
-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0.2
iQA/AwUBNt0SCe0ty8FDP9tPEQL3JgCg/12wa+E89IgtYXkVZtEDxAhigiIAoO69
NdvqbwabQKFTtclj6QRUFRKw
=+dL9
-----END PGP SIGNATURE-----