Cryptography-Digest Digest #419, Volume #10 Sat, 16 Oct 99 08:13:03 EDT
Contents:
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Re: PHT (Tom St Denis)
Re: detecting backdoor in prime generator (Tom St Denis)
looking for elliptic curve primer (Max Kubierschky)
Is this the place... (heron stone)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column ("Roger
Schlafly")
Re: looking for elliptic curve primer (Anti-Spam)
Re: looking for elliptic curve primer ("Steven Alexander")
3DES/PGP ("nKrypt-IT Ltd.")
Re: Q: Optimal diffusion (Mok-Kong Shen)
Re: looking for elliptic curve primer (David A Molnar)
Re: Factoring public keys attack? (Peter L. Montgomery)
Re: RSA Algorithm (Peter L. Montgomery)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column ("Brian
Gladman")
Re: PHT (Mok-Kong Shen)
Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column (Mok-Kong
Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 16 Oct 99 01:56:56 GMT
Brian Gladman ([EMAIL PROTECTED]) wrote:
: The arguments for multiple AES winners cannot be dismissed so easily.
Come to think of it, there *is* an easy way to dismiss the idea of having
multiple AES winners.
The AES entrants only promised to allow free use of their ciphers if their
own cipher was _the_ winner of the AES process. Hence, changing the rules
now, and declaring multiple winners would be unfair to those entrants
which are retaining proprietary rights to their ciphers.
However, just because only one algorithm is *the* winner in no way
prevents the other algorithms from being used, with the permission of
their inventors. Since the NSA has even spoken, and proclaimed that none
of the five finalists is insecure, we _have_ a plurality of block ciphers
to use.
They just won't all be declared "winners".
John Savard
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: 16 Oct 99 02:00:47 GMT
Bruce Schneier ([EMAIL PROTECTED]) wrote:
: As to (1), why does it make sense to give people without the expertise
: to make a choice a choice? If we, as the world's non-military
: cryptographers, cannot choose an algorithm, why should we expect
: others to?
Well, I don't see a compelling reason to have more than one winner - and
I've noted a serious objection, in that it would change the rules under
which entrants agreed to allow free use of their algorithms if they became
_the_ winner.
However, I'm not sure I see this as an objection. Presumably, even with
multiple winners, a choice has been made - and the announced conclusion is
that it is safe for others to make the choice among the winners by
flipping a coin.
John Savard
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: PHT
Date: Sat, 16 Oct 1999 02:23:49 GMT
In article <[EMAIL PROTECTED]>,
Wojciech Laskowski <[EMAIL PROTECTED]> wrote:
> Who tell me something about Pseudo-Hadamard Transform? I need know basic
> of PHT. Maybe somebody knows any reference to this subject?
>
Beware that the pht (as pointed out by David Wagner) has the 'flaw' that any
n-tuple in the form (a, b, a, b) [ or (a, b, c, a, b, c) etc...] the output
will be of form (x, y, x, y). This means there is a sorta-fixed point
there...
BTW what is a real ht?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: detecting backdoor in prime generator
Date: Sat, 16 Oct 1999 03:01:47 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
>
> Does someone remember the ref to an article talking about
> detecting prime generators (or n = pq generators) that have
> a backdoor?
To the best of my knowledge PGP doesn't have backdoors in their primes/keys.
If you don't trust it, don't use PGP.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Max Kubierschky <[EMAIL PROTECTED]>
Subject: looking for elliptic curve primer
Date: 16 Oct 1999 07:45:12 +0200
I need an introduction to or book on elliptic curve
cryptosystems (and elliptic curves in general).
I've a medium level background in algebra.
Any suggestions?
--
Max Kubierschky <[EMAIL PROTECTED]>
(Delete all dashes from the email address)
------------------------------
From: [EMAIL PROTECTED] (heron stone)
Subject: Is this the place...
Date: Fri, 15 Oct 1999 22:37:21 -0700
- is this the place to post a challenge to
decypher a message i have encoded
+ you can find it at:
http://home.earthlink.net/~herons/crypto.html
+ if this isn't the place, can someone please point
me to one
thanks
heron
--
ecstatitc wonder is our natural birthright...
don't settle for anything less
[EMAIL PROTECTED] http://home.earthlink.net/~herons/
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Fri, 15 Oct 1999 22:35:54 -0700
<[EMAIL PROTECTED]> wrote in message news:7u7fn4$l5o$[EMAIL PROTECTED]...
> Much of this thread has been about cascading ciphers as a way to
> increase security. What I find interesting is that only a few months
> ago many in this newsgroup thought that this is a bad idea.
Many still think it is a bad idea. If a cipher has shortcomings,
it is better to fix the cipher than to pile other ciphers on top
of it.
------------------------------
From: Anti-Spam <[EMAIL PROTECTED]>
Subject: Re: looking for elliptic curve primer
Date: Sat, 16 Oct 1999 00:23:17 -0700
Max Kubierschky wrote:
>
> I need an introduction to or book on elliptic curve
> cryptosystems (and elliptic curves in general).
> I've a medium level background in algebra.
>
> Any suggestions?
RSA Security have a FAQ entry and introductory material on ECCs at
http://www.rsasecurity.com/rsalabs/ecc/elliptic_curve.html
and
http://www.rsasecurity.com/rsalabs/ecc/ecc_recommendations.html
and
http://www.rsasecurity.com/rsalabs/faq/2-3-10.html
It's a nice start.
A much more detailed tutorial (and probaly what you're looking for) is
at Certicom's web site -
http://www.certicom.ca/ecc/enter/index.htm
Hope it proves useful,
[EMAIL PROTECTED]
------------------------------
From: "Steven Alexander" <[EMAIL PROTECTED]>
Subject: Re: looking for elliptic curve primer
Date: Sat, 16 Oct 1999 00:22:32 -0700
A good place to start is www.certicom.com/ecc/
-steven
Max Kubierschky wrote in message ...
>
>I need an introduction to or book on elliptic curve
>cryptosystems (and elliptic curves in general).
>I've a medium level background in algebra.
>
>Any suggestions?
>
>--
>Max Kubierschky <[EMAIL PROTECTED]>
>(Delete all dashes from the email address)
------------------------------
From: "nKrypt-IT Ltd." <[EMAIL PROTECTED]>
Subject: 3DES/PGP
Date: Sat, 16 Oct 1999 08:36:58 +0100
Can someone tell me which is the stronger form of encryption - 128 bit PGP
or 168 bit 3 key Triple des ?
many thanks !
--
________________________________
Martin Anderson,
Senior Developer,
nKrypt-IT Ltd.
http://www.nKrypt-IT.co.uk
________________________________
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Optimal diffusion
Date: Sat, 16 Oct 1999 10:08:14 +0200
Tim Tyler wrote:
> : Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> : : Is there a mapping of n bits to n bits that gives the best diffusion?
>
> [snip]
>
> : There are 2^256 different ways of mapping from an 8 bit input to an 8
> : bit output - whereas the above matrix can only represent 2^64 of these.
>
> Bad math alert! I /meant/ to say 256^256 ways. However of these only
> 256! are reversible (and thus qualify as information *diffusers* rather
> than information *destroyers*).
>
> This is /still/ much larger than the 2^64 figure (which also needs
> reducing for the same reasons: not all of those matrices will have
> inverses).
If I don't err, the common concept of diffusion considers the
influence of one single input bit on one single output bit under
the (implicit) assumption that this is independent of how the other
input bits influence the output bits. With that, the matrix is an
explicit specification of which input bits influence which output
bits (causing flipping or not). The invertibility of the matrix is
indeed needed for the matrix to be used in encryption/decryption.
M. K. Shen
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: looking for elliptic curve primer
Date: 16 Oct 1999 08:23:05 GMT
Neal Koblitz' book _A Course in Number Theory and Cryptography_ has
a chapter on elliptic curves. It's well written and starts out by giving
definitions and background, then demonstrating some sample systems. Worth
a look.
-David
Max Kubierschky <[EMAIL PROTECTED]> wrote:
> I need an introduction to or book on elliptic curve
> cryptosystems (and elliptic curves in general).
> I've a medium level background in algebra.
> Any suggestions?
> --
> Max Kubierschky <[EMAIL PROTECTED]>
> (Delete all dashes from the email address)
------------------------------
From: [EMAIL PROTECTED] (Peter L. Montgomery)
Subject: Re: Factoring public keys attack?
Date: Sat, 16 Oct 1999 08:27:33 GMT
In article <7u4to9$p51$[EMAIL PROTECTED]> Bob Silverman <[EMAIL PROTECTED]> writes:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Jerry Coffin) wrote:
>> In article <19991013151854.334$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>> says...
>> [ ... ]
>> > At most, wouldn't that only double the number of primes to examine?
>> > So 10^74 would become 2*10^74 or 10^74.3? And the combinations would
>> > be 10^148.6?
>> If you add one more bit in each direction, that should (unless I'm
>> missing something) roughly double the number of possible factors.
>You need to be careful with language here. You add one bit to one
>prime, but substract one bit from the other.
>If the modulus length is fixed at (say) 1024 bits, then
>the number of moduli which are the product of 512-bit primes is
>about [(sqrt(2) * 2^511)/log( sqrt(2) * 2^511)]^2 ~ 7.1e302
There are only 2^511 512-bit integers. I think you want
sqrt(0.5) rather than sqrt(2).
>The number which are the product of a 511 and 513 bit prime is about
>(sqrt(2)*2^510) * (sqrt(2) * 2^512)/log(...)log(...) ~ 5.1e302
Check your arithmetic. You missed a sqrt(2) multiply.
>You don't quite double the keyspace by allowing 511*513 in addition
>to 512*512
I claim we approximately _triple_ the key space (i.e., the number of
distinct products) by allowing 511*513 in addition to 512*512.
The number of k-bit primes is approximately (2^k - 2^(k-1))/ln(2^k)
= 2^(k-1) / ln(2^k). If one uses lengths k1 and k2, then there are
2^(k1-1) 2^(k2-1) 2^(k1+k2-2)
-------- * -------- = -------------------
ln(2^k1) ln(2^k2) ln(2^k1) * ln(2^k2)
pairs of primes available.
For real numbers chosen uniformly in intervals [a, 2a] and [b, 2b],
their product will exceed 2ab with probability 2 - ln(4) ~= 0.614.
For large k the k-bit primes are distributed approximately uniformly
in the interval [2^(k-1), 2^k]. We therefore estimate the number of ways
to select a k1-bit prime and a k2-bit prime whose product has (k1+k2) bits as
(2 - ln(4)) * 2^(k1+k2-2) / (k1 * k2 * ln(2)^2)
= c * 2^(k1+k2) / (k1*k2)
where c = (2 - ln(4))/(4 * ln(2)^2) ~= 0.319.
For 511*513 products, we can use this formula directly, and estimate
c*2^1024/(511*513) = c*2^1024 / 262143 ~= 2.19E302 pairs of primes.
This is the same as the number of 511*513 products of primes,
For 512*512 we estimate c*2^1024/(512*512) = c*2^1024/262144 pairs
of primes, almost the same as for 511*513. However the number of distinct
_products_ is only half this number, because we have counted both p*q and q*p.
There are about 1.09E302 products, only half as many as for 511*513.
To demonstrate this difference without all the equations,
consider 12-bit products. The 6-bit primes are 37, 41, 43, 47, 53, 59, 61.
The 12-bit products of two 6-bit primes are
37*(59, 61)
41*(53, 59, 61)
43*(53, 59, 61)
47*(53, 59, 61)
53*(59, 61)
59*61
plus 47^2, 53^2, 59^2, 61^2 if we allow squares of primes.
The count is either 14 or 18 12-bit products.
The 5-bit and 7-bit primes are
17, 19, 23, 29, 31
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127
The 12-bit products from these lines are
17*127 (1 product)
19*(109 to 127) (3 products)
23*(97 to 127) (7 products)
29*(71 to 127) (12 products)
31*(67 to 127) (13 products)
Using 5*7 allows 36 different 12-bit products, twice as many as 6*6.
As for the constant 0.614, we estimate that 21*0.614 = 12.894
of the (7 choose 2) 21 products of distinct 6-bit primes
will have 12 bits; the actual count is 14.
We estimate 65*0.614 = 39.91 of the 5*13 = 65 products
of 5-bit and 7-bit primes will have 12 bits; the actual count is 36.
--
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: [EMAIL PROTECTED] (Peter L. Montgomery)
Subject: Re: RSA Algorithm
Date: Sat, 16 Oct 1999 08:38:02 GMT
In article <7u7cl5$ipo$[EMAIL PROTECTED]> Bob Silverman <[EMAIL PROTECTED]> writes:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Francois Grieu) wrote:
>> [EMAIL PROTECTED] wrote :
>> > Published tables exist with (2^n)-1 up to 1000 bit numbers
>> > factorized, using old computers people would nowdays laugh at.
>This is a gross distortion of the facts. Most of the harder numbers
>were broken using very fast PC's and workstations (hundreds) running
>in parallel.
The tables exist, but are complete only to about 600 bits.
See http://www.cs.purdue.edu/homes/ssw/cun/index.html .
The versions published in 1988 stopped at about 300 bits.
>> > How large is the largest number (2^n)-1 factored today ?
>
>n = 2*1185 has been done. This is the largest that I know.
Both 2^4096 - 1 and 2^4620 - 1 have been completely factored.
The only larger n I know are prime n, such as where
2^n - 1 is a Mersenne prime.
--
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Sat, 16 Oct 1999 09:59:05 +0100
Roger Schlafly <[EMAIL PROTECTED]> wrote in message
news:7u7vp0$[EMAIL PROTECTED]...
> Brian Gladman <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > > There are probably also people who will not trust AES as is, and use
> > > triple-AES. If NIST sanctioned triple-AES, they'd use
triple-triple-AES.
> > > That's fine, but it is pretty useless for NIST to try to accommodate
> them
> >
> > No-one is asking for this AFAIK. I have a high level of trust in the
AES
> > process but since I have a lot at stake I want a fall back position in
> case
> > things go wrong.
>
> No, you are asking for a triple-AES solution because you don't
> trust AES. Perhaps your special needs justify it. That's fine, but
> I don't know why you'd want to burden everyone else with an
> overly complex AES when you are not going to trust it anyway.
For you trust may be as simple as 'yes' or 'no' but for me its not, I trust
things to varying degrees. I have a high degree of trust in my Bank in
looking after my money but I don't trust them absolutely and I hence check
what they do. For me trust is not a binary variable but a continuous one
from, say, 0 (no trust) to 1 (absolute trust).
I have a high level of trust in the AES process and I am very confident that
the probability that a single winner will later be found to have a serious
flaw is very, very small. But I don't have absolute trust in the winner
because this probability cannot be shown to be zero. And the consequences
are dire if the cipher does fail since a large proportion of the world's
secure data may well end up being protected by it.
In 'hand waving' terms we might loosely say that the risk we are taking is
the product of 'a very small probability of failure' with 'a huge
consequence if this failure occurs'. And the problem we face is that we
simply don't have any idea whether the resulting product is so small that we
can afford to ignore it or so large that we must do something about it.
Optimists will hope it is small and carry the risk - in other words they are
gambling. Pessimists will also hope it is small but they will assume it is
not and will hence develop a contingency plan to cope if the worst happens.
I don't object to you gambing provided it does not cause me harm but in AES
we are gambling for the world as a whole and not just for ourselves. And
that's why the debate is so important.
And there is nothing necessarily burdensome about an AES process in which
the result gives a formal status to more than one algorithm. For example, I
have no objection to a 'multiple winners' result which indicates that where
only a single algorithm is necessary it should be algorithm X. Nor have I
ruled out other possibilities which allow most of the requirements of
'multiple winner' advocates to be met without major compromises on the part
of those who want just one winner.
And why do you consider that my need to have a contingency plan to guard
against unlikely but possible future events is so special? Other
contributions to the debate here show very clearly that I am not alone.
Many disasters have been made much worse because people have failed to
anticipate and plan for them.
Brian Gladman
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: PHT
Date: Sat, 16 Oct 1999 12:19:43 +0200
Tom St Denis wrote:
>
> Beware that the pht (as pointed out by David Wagner) has the 'flaw' that any
> n-tuple in the form (a, b, a, b) [ or (a, b, c, a, b, c) etc...] the output
> will be of form (x, y, x, y). This means there is a sorta-fixed point
> there...
>
> BTW what is a real ht?
Depending on the nature of the applications, the existence of a
fixpoint of an operator may or may not be critical, I suppose.
The Hadamard transform is defined by the matrix
| H_j H_j |
H_(2j) = | |
| H_j -H_j |
with H_1 = (1).
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: "Risks of Relying on Cryptography," Oct 99 CACM "Inside Risks" column
Date: Sat, 16 Oct 1999 12:34:06 +0200
Brian Gladman wrote:
>
> Many disasters have been made much worse because people have failed to
> anticipate and plan for them.
Well said. In other contexts I read that there is a sort of natural
bias of the public (lay people) to have overconfidence, that they
neglect the potential of surprises (like the sudden discovery of
power analysis as mentioned by Mr. Schneier) and that further there
is a so-called bandwagon effect in decision making.
M. K. Shen
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
