Cryptography-Digest Digest #908, Volume #11 Thu, 1 Jun 00 06:13:01 EDT
Contents:
Re: Use of wasted symmetric key bandwidth in key agreement protocols (Mark Currie)
Re: XTR (was: any public-key algorithm) (Mark Wooding)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Peter G. Strangman)
Re: PGP 5.0 auto-seeding insecure (Gisle Sælensminde)
Re: No-Key Encryption (Mok-Kong Shen)
Re: XTR (was: any public-key algorithm) ("Michael Scott")
Pollard's algorithm for computing discrete logs (Jesper Stocholm)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (George Edwards)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (George Edwards)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (George Edwards)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (George Edwards)
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
(George Edwards)
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
(George Edwards)
Re: XTR (was: any public-key algorithm) (Wei Dai)
Re: Help! [Large Prime] (Mark Wooding)
----------------------------------------------------------------------------
Subject: Re: Use of wasted symmetric key bandwidth in key agreement protocols
From: [EMAIL PROTECTED] (Mark Currie)
Date: 01 Jun 2000 08:55:34 GMT
Yes, you can get a lot of overhead using a PKI, but perhaps it was misleading
of me to use the term "bandwidth". What I was meant was the usable information
space within a key encryption payload i.e. if you encrypt a symmetric key using
1024 bit RSA, you have a potential to send a 1023 bits of keying information.
Mark
In article <ffiZ4.5701$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>Most of the bandwidth waste is in shipping certificates to and fro,
>especially when they average 5k+ from the commercial cert providers.
>ECC certs don't help much overall, either.
>
>Lyal
>
>Mark Currie wrote in message <39322a5c$0$[EMAIL PROTECTED]>...
>>Hi,
>>
>>In a communications security application involving an on-line key agreement
>>protocol, there often exists additional keying bandwidth which is not
>generaly
>>used. As an example, if the key exchange protocol involved the use of
>>Diffie-Hellman, the typical length of the resultant mutual secret value
>could
>>be in the order of 128 bytes. Only 16 - 32 bytes are typically required for
>use
>>as a secret key for data encryption. These bytes can either be directly
>>extracted from or be the result of hashing the 128 bytes. I have often
>wondered
>>how the wasted bytes could be put to good use. One idea is to use them to
>>modify the symmetric algorithm used to encrypt the data in some way.
>However,
>>if not applied correctly, it can in fact weaken the algorithm even if these
>>values are secret. Another idea could be to use it in the key expansion
>part of
>>an algorithm to effectively increase key entropy while not impacting on
>>performance.
>>
>>I would be interested in any other idea's for the use of these often wasted
>>bytes to increase data security without (ideally) impacting on the data
>>encryption performance.
>>
>
>
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: XTR (was: any public-key algorithm)
Date: 1 Jun 2000 09:19:25 GMT
Wei Dai <[EMAIL PROTECTED]> wrote:
> If it doesn't use Karatsuba for example then Table 1 overstates the
> relative advantage of XTR over RSA.
I thought that conventional wisdom was that Karatsuba wasn't a win for
the sizes of numbers used for RSA and similar systems today. This is
certainly bourne out by my experiments with conventional versus
Karatsuba multiplication and squaring in my own library. The threshold
at which Karatsuba starts becoming a win is also increased if you use
Montgomery reduction, I believe, because of the way you can combine
multiplication and reduction. (Or is there some clever way to do a
Karatsuba-Montgomery multiply?)
I also don't understand where the number of multiplications needed for
RSA encryption (1500) comes from in the table. Let's consider a
standard 1024-bit RSA modulus n, and the `standard' public exponent e =
F_4 = 65537. Computing M^e mod n requires 16 squarings and one
multiplication. Let's say, pessimistically, that squarings are as slow
as multiplications: so that's 17 multiplications. Now, these are
multiplications of 1024-bit numbers; the speed figures are expressed
(for some reason) as 170-bit multiplications. Without using Karatsuba's
method, a pair of 2k-bit numbers takes four times as long as a pair of
k-bit numbers. We need to do this log_2(1024/170) =~ 2.6 times, so we
end up with approximately 36 times as many 170-bit multiplications.
That gives me an approximate total of 617 170-bit multiplications.
There's almost a factor of 2.5 between my number and the one given in
table 1, *and* I didn't use any cleverness. I'm assuming that these are
modular multiplications -- throw in a factor of 2 (hopelessly
pessimistic) if you have to do Montgomery reduction and I'm still only
at 1234 multiplies
Let's say now, by contrast, that a squaring really only takes half the
time of a multiplication. Then we have only 9 multiplication-
equivalents, reducing the work to 9 * 36 = 324 170-bit multiplies to do.
I'm now suspicious of the decryption number. Let's do a similar
analysis. The decryption exponent will be about 1024 bits long.
However, since we know the factors of the modulus, we can use the
Chinese Remainder Theorem, so I only have two 512-bit modular
exponentiations to do. We'll continue assuming that multiplications are
about twice as expensive as squarings. We have 512 squarings, and
(assuming an expected Hamming weight of 256) 256 multiplies, so 512
multiplications, altogether. But these are only 512-bit multiplies, not
1024-bit ones, so there's only a bit less than 9.1 170-bit multiplies
per 512-bit one. That gives a total of about 9300 multiplies (I've
thrown in a few more and rounded up for the recombination bit of the
CRT, and the mucking about with division).
So where do the numbers in that table come from? It looks to me very
much to me as if they've no basis in reality.
-- [mdw]
------------------------------
From: Peter G. Strangman <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Thu, 01 Jun 2000 10:08:30 +0100
Reply-To: [EMAIL PROTECTED]
On Wed, 31 May 2000 19:14:40 +0100, Stuart Tyrrell
<[EMAIL PROTECTED]> wrote:
> I'm intrigued - are these passwords indeed random?
As random as a PRNG seeded from the system clock will
make them.
> I have visions of PGS with a machine connected to a bunch of diodes /
> Beta particle source / rain sensor (OK, the last one is anything but
> random around here!).
(But the noise it makes is)
Not necessary for that particular application. The only
reason I use the program is that it prevents me from
using any personal bias and 'inventing' passwords which
might have a high probability of being researchable.
> Stuart (who's not sure he trusts the "interrupt a fast running
> counter" trick that he's seen PGP implementations use)
That trick is quite O.K. as long as what interupts it
are random external events, e.g. keystrokes, movement
of the mouse etc.
--
Peter G. Strangman | Leser, wie gefall ich dir?
[EMAIL PROTECTED] | Leser, wie gefaellst du mir?
http://www.adelheid.demon.co.uk | (Friedrich von Logau)
XLIV-VII-DCCCII-CCXII-DCCCXXXI |
------------------------------
From: [EMAIL PROTECTED] (Gisle Sælensminde)
Subject: Re: PGP 5.0 auto-seeding insecure
Date: 1 Jun 2000 11:31:48 +0200
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn wrote:
>Funny how nobody has mentioned the recent CERT advisory about all
>versions of PGP 5.0, which apparently miuses the /dev/random facility
>found on some systems and as a result picks guessable keys.
Do you have a pointer to this ?
--
--
Gisle Sælensminde ( [EMAIL PROTECTED] )
ln -s /dev/null ~/.netscape/cookies
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Thu, 01 Jun 2000 11:45:13 +0200
David Hopwood wrote:
> Bryan Olson wrote:
>
> > Suppose we limit ourselves to the associative operation
> > case. Does there exist an associative operation "*" such
> > that the protocol illustrated above is secure?
>
> No. Proof:
[snip]
I am confused. Doesn't that mean the schemes of Sharmir and
Massey-Omura etc. are all broken?
M. K. Shen
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: XTR (was: any public-key algorithm)
Date: Thu, 1 Jun 2000 10:46:59 +0100
"Eric Verheul" <[EMAIL PROTECTED]> wrote in message
news:8h55fh$n08$[EMAIL PROTECTED]...
> - ECC's parameter generation (a curve) is a pain ....
Not really. A Schoof-Elkies-Atkin point-counting program
(http://indigo.ie/~mscott) will spit out several suitable 170-bit curves per
minute on a decent computer. For most protocols these domain parameters are
a one-off calculation, and private/public key pairs are henceforth generated
very quickly by a single point multiplication. For most applications this
latter operation is "key generation".
> On the other hand XTR is based on the DL problem in a finite field, whose
> security is considered ok
.. based on the "extension-field" DL problem... Its not quite the same
claim.
> Finally, who says that you don't have to pay license fees for using (smart
> implementations of) ECC? Be careful, there are lots of patents filed
there..
>
Ah now. Spreading Fear Uncertainty and Doubt is not good marketing. The
Elliptic curve set in GF(p) for a random p (which is probably the strongest
variant) is patent free, (and appears to be that with which you were making
timing comparisions - comparison with a "smart" Koblitz curve would maybe
not look so good?)
You will probably get an easier ride at Crypto 2000! XTR/LUC are good ideas
and IMHO there may be a small niche there between RSA and ECC. And the math
is fascinating.
Mike Scott
> Thanks.
>
> Eric
>
>
>
------------------------------
From: Jesper Stocholm <[EMAIL PROTECTED]>
Subject: Pollard's algorithm for computing discrete logs
Date: Thu, 01 Jun 2000 09:41:42 GMT
I'm trying to implement Pollard's algorithm for discrete logs - but I
have a little problem:
I have to partition the Group into 3 sections (S1, S2 and S3). However -
the book I use (Handbook of Applied Cryptography) just says,
that "some care must be exercised in selecting the partition" - which
doesn't help me much.
How do I choose the right partition of the Group ?
ys
Jesper Stocholm
--
http://stocholm.dk
MSN Messenger: [EMAIL PROTECTED]
- On Usenet I represent only myself
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Wed, 31 May 2000 21:27:21 +0100
In article <[EMAIL PROTECTED]>, Peter G.
Strangman <[EMAIL PROTECTED]> writes
>Actually I use a little program, which I wrote, which will
>generate a random password whenever I need a new one.
could not the use of such a mechanism be interpreted as conspiracy to
pervert the course of justice?
(the more they try to nail it down, the more difficult it will become)
--
George Edwards
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Wed, 31 May 2000 21:37:51 +0100
In article <[EMAIL PROTECTED]>, Scotty
<[EMAIL PROTECTED]> writes
>
>You don't even have to go that far. I think if enough people kept a few
>files, randomly encrypted, (so they deliberately don't remember the
>password) on their disks, the whole bill will collapse. Anyone presented
>with a decryption notice could just claim it was such a file and the burden
>of proof could be correctly restored. I'm doing my bit, I suggest those
>opposed to the bill do likewise.
look this is a stupid bill.
I have (just counted) some 20 passwords on my board. Don't know what
most of them refer to. Can go on giving out possible keys till the cows
come home. How the hell do they prove I "know" key if I don't use it
after they ask?
More stupid law from A. Blair and Co.
--
George Edwards
The net is bigger than you think
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Wed, 31 May 2000 21:45:22 +0100
In article <[EMAIL PROTECTED]>, Andy Dingley
<[EMAIL PROTECTED]> writes
>>The answer is simple: Don't break the law.
Drive at exactly 30, never accept a duty free fag, don't even look at a
spliff.
Just because the government passes a law on a wet thursday in
westminster, when all the MPs are asleep or drunk, doesn't mean that
people regard you as criminal because you "break" it.
The net is uncontrollable - all they can do is take away your PC - a
twenty minute job to replace it, unless they lock you up. Hello Beijing.
--
George Edwards
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Wed, 31 May 2000 21:47:22 +0100
In article <[EMAIL PROTECTED]>, Scotty
<[EMAIL PROTECTED]> writes
> [end of
>rant]
No do go on.........
--
George Edwards
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: Wed, 31 May 2000 21:50:19 +0100
In article <Ty4Z4.175$[EMAIL PROTECTED]>, Michael
Watson <[EMAIL PROTECTED]> writes
>I /think/ so. Catterick seems to be the area in the North-east where there is
>an Army-base. I wouldn't be surprised to find out
>that the MI5 was there - there are too many "government-like" actions in that
>area. Plus everybody keeps mentioning North Yorkshire
Should we put the bomb in McDonalds or Tesco then?
(oooops!)
--
George Edwards
------------------------------
From: George Edwards <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: Wed, 31 May 2000 21:54:58 +0100
In article <[EMAIL PROTECTED]>, U Sewell-
Detritus <[EMAIL PROTECTED]> writes
>
>
>If you have a US base near you, chances are it has a
>chunky telecoms trunk running right through the middle of it ;o
Hey ho! Menwith hill again.
yoo hoo, spooks!
( I understand that our US friends are much more wired than we are.
Perhaps one of them will respond?)
--
George Edwards
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: XTR (was: any public-key algorithm)
Date: Thu, 1 Jun 2000 02:43:17 -0700
In article <8h4t29$mgh$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> In article <[EMAIL PROTECTED]>,
> Wei Dai <[EMAIL PROTECTED]> wrote:
> > XTR's advantages do not appear to be exaggerated, but they do seem marginal
> > (with respect to ECC).
>
> I'm not sure I'd call them marginal. In purely technical terms, it
> is interesting to find a public-key cryptosystem that achieves many of
> the benefits of elliptic curves -- but without the elliptic curves! --
> for those who are a bit skeptical about the security of elliptic curves.
Elliptic curves are supposed to offer exponential security whereas XTR still
only offers subexponential security at best. This means to obtain 2^128
security you'll need EC over GF(p) with p around 2^256 versus XTR over GF(q)
with q around 2^413.
Is there any theoretical reason to think that extension fields are more likely
to be secure than elliptic curves over GF(p)?
--
cryptopp.com - a free C++ class library of cryptographic schemes
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Help! [Large Prime]
Date: 1 Jun 2000 10:09:47 GMT
Park Jiho <[EMAIL PROTECTED]> wrote:
> Today, I'd like to ask you how to generate a special form of large
> prime number such as a "secure prime" or a "safe prime".
I assume you already know how to test a number for primality, using
residues mod small primes and a probabilistic test such as Rabin-Miller.
To find an n-bit safe prime, i.e., a prime p such that (p - 1)/2 is
prime also, I start with an (n - 1)-bit random odd number q_0. For
0 <= i, I test q_0 + 2 i and 2 q_0 + 4 i + 1 against my small primes.
If I find an i which passes, then I test q_0 + 2i and 2q_0 + 4i + 1 in
turn using my probabilistic test, until either one of them fails or I've
done enough iterations to be confident that the numbers are prime.
To find an n-bit strong prime, i.e., a prime p such that p - 1 has a
large prime factor p^-, p + 1 has a large prime factor p^+, and p^- has
a large prime factor p^{--}, I use Gordon's algorithm.
Let v = 12 be a `Stradivarius constant'. Compute n' = n/2 - v. Find a
pair of n'-bit prime numbers s and t. Let r_0 = 2^v t + 1, and find an
integer i >= 0 such that r = r_0 + 2 i t is prime. Now compute
p_0 = 2 (s^{r - 2} mod r) s - 1
and find an integer j >= 2^v such that p = p_0 + 2 j r s is prime. The
prime p is `strong'.
It is obvious that p^+ = s is a factor of p + 1. We can show that p^- =
r is a factor of p - 1. Firstly, note that s s^{r - 2} = s^{r - 1} = 1
(mod r) by Fermat's Little Theorem. Then,
p = 2 (s^{r - 2} mod r) s + 2 j r s - 1
= 2 (s^{r - 2} mod r) s - 1
= 1 (mod r)
Finally, p^{--} = t is a factor of r - 1.
Now all you need to think about are the bit lengths of everything, and
why my Stradivarious constant v has the value it does.
-- [mdw]
------------------------------
** 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
******************************
