Cryptography-Digest Digest #49, Volume #11 Fri, 4 Feb 00 04:13:01 EST
Contents:
Re: How to choose public-key e on RSA? (Ed Pugh)
Re: KEA gains something with RSA instead of D-H (David Hopwood)
KEA, and XDH (David Hopwood)
Re: Terms need explain (Sandy Harris)
Merkle hash tree patent expired (Paul Rubin)
Re: password encryption/decryption (Palmpalmpalm)
Re: 26-Dimensional cipher - is it secure (or even possible)?
([EMAIL PROTECTED])
Re: Challenge: Who can discover the encryption used here? (NFN NMI L.)
Re: ascii to binary (NFN NMI L.)
Re: Does the NSA have ALL Possible PGP keys? (NFN NMI L.)
Re: is key escrow still current topic? (NFN NMI L.)
Re: How to Annoy the NSA ("Mark T. VandeWettering")
Re: ascii to binary (Paul Schlyter)
Re: Does the NSA have ALL Possible PGP keys? (Paul Schlyter)
Re: Does the NSA have ALL Possible PGP keys? (Guy Macon)
Re: Does the NSA have ALL Possible PGP keys? (Guy Macon)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Ed Pugh)
Subject: Re: How to choose public-key e on RSA?
Date: 4 Feb 2000 04:24:23 GMT
Reply-To: [EMAIL PROTECTED] (Ed Pugh)
"Miryadi" ([EMAIL PROTECTED]) writes:
> Peter L. Montgomery wrote in message ...
>>In article <t3nm4.3968$15.28174@news> "Miryadi" <[EMAIL PROTECTED]>
> writes:
>>>
>> Usually e is fixed, for all users. e = 2^16 + 1 = 65537
>>is common. e = 3 has weaknesses.
>>
> Is this e=3 or e=65537 always relatively prime to any (p-1)*(q-1)?
> What If it doesn't?
> So, I guess I've to run my procedure (starting with e=3) anyway.
Actually, the modulus used to find e and d should NOT be (p-1)*(q-1)
but, instead, should be LCM((p-1),(q-1)). So, we need to use an
e that is co-prime to LCM((p-1),(q-1)), and then find d such that
e*d = 1 (mod LCM((p-1),(q-1)))
[ LCM(x,y) is the Least Common Multiple of x and y, and is calculated
as LCM(x,y) = (x*y)/gcd(x,y) ]
Classic descriptions of RSA always use phi(n) = (p-1)*(q-1) when
n = p*q (for p,q prime). Then, for any number a, a^phi(n) = 1 (mod n).
(This is the Euler-Fermat theorem - or rather Euler's extension to
Fermat's Little Theorem).
However, it turns out that phi(n) is NOT the smallest number with
this property; rather LCM((p-1),(q-1)) is. So that, for any a,
then a^LCM((p-1),(q-1)) = 1 (mod n).
However, I have only read this; I do NOT know the proof that it
works with the LCM. I *do* know that PGP 2.6.3ia uses this fact
and calculates e and d with the LCM((p-1),(q-1)), NOT with phi(n).
Also, contrary to popular belief, a does NOT have to be relatively
prime to n for RSA to work. I once developed a proof for this, but
do not remember it now. Therefore, it is NOT necessary in RSA to
ensure that a is r.p. to n in order for the calculations to work.
(However, using a plaintext or ciphertext that is not r.p. to n
probably seriously compromises RSA.)
Regards,
--
Ed Pugh, <[EMAIL PROTECTED]>
Richmond, ON, Canada (near Ottawa)
"Bum gall unwaith-hynny oedd, llefain pan ym ganed."
(I was wise once, when I was born I cried - Welsh proverb)
------------------------------
Date: Fri, 04 Feb 2000 03:08:35 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: KEA gains something with RSA instead of D-H
=====BEGIN PGP SIGNED MESSAGE=====
John Savard wrote:
>
> On Wed, 02 Feb 2000 01:19:25 +0000, David Hopwood
> <[EMAIL PROTECTED]> wrote, in part:
> >How were you intending to adapt KEA to use RSA?
>
> I was simply thinking that A sends session key 1 to B using B's public
> key, B sends session key 2 to A using A's public key, and then the XOR
> of the two session keys is actually used for the message.
Just as an interesting historical note, I believe this was first proposed
in 1984 (with a report of an implementation using an 8085 chip):
S. C. Serpell, C. B. Brookson, B. L. Clark
(British Telecom Research Laboratories),
"A Prototype Encryption System using Public Key,"
Proceedings of CRYPTO '84, pp 3-9.
It's on the Springer-Verlag CD-ROM for the CRYPTO and EUROCRYPT
conferences.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOJpCnzkCAxeYt5gVAQHM0Af/QAXZ1yxqeFcqYXTtKraU9Fk81o3SPKf7
wq8m0+UJyWzPAKSOnFxnCvzKjXMSY0wx5feU++er1qqsd5PT8kowKf81b9wxbDP9
CE3l4iZ7gkqyxhLKqIC2N2lInDz9AKJ9jymsTRUgDI/MvVFVQAfgkBMugDQRezJJ
kOdu7+hpujcKoqqEtrFqpjxE0H3GSIyN/63mDvo2uqHj9IiwJ/y5qR/zGsIey4YG
6Yq5ZWc7RiXvIwIH/E3QQVh0gzlt9/qCMcZHwSztw05BkyfJ01RbZspyqALqf+vd
y+g5oslKdDgpCJZpA+yIKn7JExQvEjjpUsqvkSHZr/Qxml3rcLYcCw==
=9dHM
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 04 Feb 2000 04:37:43 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: KEA, and XDH
=====BEGIN PGP SIGNED MESSAGE=====
Doug Stell wrote:
>
> On Wed, 02 Feb 2000 01:19:25 +0000, David Hopwood
> <[EMAIL PROTECTED]> wrote:
[...]
> > Alice and Bob agree on parameters g, p, and q
> > (q is the order of g in GF(p)).
>
> While the use of DSA-style parameters is suggested in the
> specification, it is not technically necessary. KEA works without
> having a q-parameter.
Provided that you still check that RA and RB are of large order, yes.
[...]
> Incidentally, the CA also checks that YA and YB are elements of the
> order-q subgroup, before it signs the certificate. This is not in the
> KEA specification, but is a part of the CA requirements. The KEA
> specification is simply focused on the two communicants, rather than
> the CA.
>
> The reason for this check can be found in a paper by Lim and Lee.
Do you have a reference for that paper?
> > Alice: tAB = YB^rA mod p
> > Bob: tBA = YA^rB mod p
> > Alice: uAB = RB^xA mod p
> > Bob: uBA = RA^xB mod p
> > Alice: w = (tAB + uAB) mod p
> > Bob: w = (tBA + uBA) mod p
>
> As pointed out in yesterday's post, XOR or a hash could be used to
> combine the two session key contributions. KEA just happens to use
> addition.
> > Alice & Bob check that w != 0, and derive a key from it (details
> > omitted)
Does anyone know the reason for the check that w != 0, BTW? It is not
possible for any of tAB, uAB, tBA or uBA to be zero (because of the
checks on RA, RB, YA and YB), and I can't see any other reason why
w would be zero except by chance.
> >This is quite similar to some of the MTI* protocols, for example
> >MTI/A0 [HAC Protocol 12.53] and MTI/C1. It's also similar to a protocol
> >I designed myself (unpublished, called SID-3-DH),
I've decided to rename it to "XDH" (extended Diffie-Hellman).
> >in which the agreed
> >value is g^((xA + rA)(xB + rB)), rather than g^(xB.rA) + g^(xA.rB).
> >
> >[This is more efficient than KEA, because
> >
> > g^((xA + rA)(xB + rB)) = (YB * RB)^(xA + rA)
> > = (YA * RA)^(xB + rB)
> >
> >can be calculated by each side using only one modexp, not two.
>
> This is faster than KEA by a factor of about 2.
Not quite, because each side also needs to compute RA or RB, but
these can be precomputed. (For example, a server would probably
maintain a pool of g^rB values for incoming connections; in that
case computing RB values wouldn't contribute to connection setup
latency, but would contribute to server load. These are only short-
exponent, fixed-base modexps, anyway.)
Note that Alice must check that YB * RB generates a group of
order q, and similarly for Bob. rA and rB must not be chosen such
that (xA + rA) mod q or (xB + rB) mod q are zero (although that
happens with negligable probability). Also, timing and other side
channel attacks against the modexp calculations must be prevented.
========
I said that the security of XDH could be proven (relative to DHP);
here is the proof:
Let G be a cyclic group or subgroup of known order q generated by
an element g, and call an integer that is chosen uniformly and
independently at random from the range [0, q-1], an "R-integer".
(Note that the oracles used in the proof can depend on G, g and q,
so these do not have to be passed to them as parameters.)
Define a problem XDHP[G, g, q] as follows:
Suppose that a, b, c and d are R-integers.
Given g^a, g^b, c, and d, find g^(a+c)(b+d).
Proof that XDHP[G, g, q] reduces to DHP[G, g, q]:
Suppose that we have an oracle O, which, when given g^a, g^b,
c, and d, such that a, b, c, d are R-integers, returns g^(a+c)(b+d)
with probability p0, in time t0, and using memory m0.
Then when given g^a and g^b, such that a, b are R-integers, we
can calculate g^ab with probability p0, in time t0 + t1 and using
memory m0 + m1, where t1 and m1 are the time and memory needed to
calculate 3 modexps, 3 multiplications, and 1 inverse in G (and
an integer multiplication), as follows:
1. Choose two R-integers c and d.
2. Let x = O(g^a, g^b, c, d).
3. Return x * (g^(cd) * (g^a)^d * (g^b)^c)^-1
(G is a cyclic group or subgroup, so all elements have an inverse).
This works because:
g^(a+c)(b+d) = g^ab * g^cd * g^ad * g^bc, therefore
g^ab = g^(a+c)(b+d) * (g^cd * (g^a)^d * (g^b)^c)^-1
Note that the result also holds if the R-integers are chosen with
a non-uniform distribution, e.g. using an imperfect PRNG, in both
the XDHP and DHP problems.
[Conversely, XDHP can be solved using an oracle for DHP, since
g^(a+c)(b+d) = g^ab * g^cd * g^ad * g^bd (actually, this also solves
the potentially more difficult problem when only g^c and g^d are
given, instead of c and d).]
An important point is that by symmetry, we could have chosen the
private value inputs to XDHP as either (a and b), (a and d),
(c and b), or (c and d).
The security of the XDH protocol can now be expressed in terms
of XDHP.
There are 5 cases:
1. The attacker knows xA, xB, RA and RB (known-key passive attack).
2. The attacker knows YA, xB, rA and RB (attempted
impersonation of Alice, possibly given Bob's private data).
3. The attacker knows xA, YB, RA and rB (attempted
impersonation of Bob, possibly given Alice's private data).
4. The attacker knows YA, YB, rA and rB (failure of both Alice
and Bob's RNGs).
5. For a man-in-the-middle attack, the attacker is assumed not
to know *both* Alice and Bob's private keys, and therefore this
is as difficult as either case 2 or case 3.
In all of these cases, finding g^(xA + rA)(xB + rB) is equivalent
to an instance of XDHP, and therefore is as difficult as solving DHP
in the same group or subgroup.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOJpXhjkCAxeYt5gVAQEyzAgAmUnnq1x4Mp2ixwBAVf7xxuOIBM59mMDb
0+Um5ONsx8KG9IFEQmLMR0Lj/kjmpXb4V8URQ53a+RE9iSXduLCL3A0/mxcnudqT
LJ0TxaKwLo3R36G4yRczTCIAOoF6wZzqQk61DujwcbULSW+dAMPStKwIrhDjsO3g
8r4JRhYWm8/VY0pwTlHhSGCCKDee2p5O73hvf/mOrP6TOk5aaF4xCqjXDqrWbH1y
yBKID0i0N7qoDtuSanzv0FVEEf+eyIINXigGR4BVnluk3lMlSYg/OcrysCTdA2J1
b5igg5ypP84fXZ3iKiOCiy8+82EQfehWVcGpDUUePE0oSEPUNB2eMQ==
=dK6F
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Sandy Harris)
Subject: Re: Terms need explain
Date: 4 Feb 2000 05:09:00 GMT
[EMAIL PROTECTED] (Angus Lee) spake thus:
>What're the meanings of:
>1. digital signature;
>2. key-exchange certificate; and
>3. signature certificate
>in the above context?
http://www.freeswan.org/freeswan_trees/freeswan-1.2/doc/glossary.html
A crypto glossary with links to several others.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Merkle hash tree patent expired
Date: 4 Feb 2000 05:53:00 GMT
Hey, nobody seems to have mentioned it here, but apparently US patent
4,309,569 expired on September 5, 1999. This gives a somewhat clunky
way of doing digital signatures using only conventional hash functions,
no modular exponentiations or elliptic curves or other fancy math.
------------------------------
From: [EMAIL PROTECTED] (Palmpalmpalm)
Subject: Re: password encryption/decryption
Date: 04 Feb 2000 06:07:07 GMT
If you wanna encrypt and "decrypt" the password, why don't you use a
cryptographic protocol using password-verifier.
Password scheme is the simplest one but if you want to encrypt it, must be
careful. There must be several cryptographic schemes for you.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 26-Dimensional cipher - is it secure (or even possible)?
Date: Fri, 04 Feb 2000 06:29:33 GMT
In article <jgfunj-0302001405320001@dial-
243-006.itexas.net>,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (James Barlow) wrote:
>
> > In article <86nuja$39r$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] says...
> >
> >
> Let me remind those skeptics that anyone can have a shot at
> multidimmensional algorithms if you are willing to leave the comforts that
> wandering about in three, and doing algorithms in one or two gives you.
> --
The only multi-dimensional algorithm I am
personally aware of is a Monte Carlo
algorithm. What kinds of algorithms do you
mean? Also, is it possible to base
cryptography on higher dimensional automata?
> A big-endian and a little-endian have been spotted sitting at a
> campfire nibling on bytes and pointing at each other as they
> argued about who got hit with the most errors.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: Challenge: Who can discover the encryption used here?
Date: 04 Feb 2000 06:43:08 GMT
<<I deal with trainers>>
Cheat programs.
S.T.L.
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: ascii to binary
Date: 04 Feb 2000 06:47:47 GMT
Gaaaach. Look at all the cruddy C code.
In any case, ASCII is stored as binary. Maybe you C (scoff) people think of
ASCII as 0-255, but I've always though of it as 8-bit binary codes since
reading _Understanding Computers_ (these really cool silvery books that, if I
recall correctly, Timelife published).
S.T.L.
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: 04 Feb 2000 06:49:52 GMT
<<They purport that the NSA has ALL POSSIBLE keys for PGP>>
Yes. Now, the question is, where is the NSA hiding their hard drive? It'll make
exabyte storage capacities look like bits of fluff.
Freaking moron.
S.T.L.
------------------------------
From: [EMAIL PROTECTED] (NFN NMI L.)
Subject: Re: is key escrow still current topic?
Date: 04 Feb 2000 06:50:21 GMT
Clipper's dead. Hallelujah.
S.T.L.
------------------------------
From: "Mark T. VandeWettering" <[EMAIL PROTECTED]>
Subject: Re: How to Annoy the NSA
Date: Fri, 04 Feb 2000 06:53:56 GMT
[EMAIL PROTECTED] wrote:
> This error was supposedly due to a
> grammatical misreading (see msg 16).
> Ignoring the difficulty of factoring RSA, aren't
> PGP systems vulnerable in other ways?
> Couldn't someone modify the publicly
> available code to PGP, compile it, and sneak it
> into a target system via a network without
> having to access any physical machine?
Such a "Trojan horse" is of course possible. Security
isn't guaranteed by using cryptography or cryptographic
protocols. Someone could easily make a trojan that would
snarf your keyphrase that protects your private key too.
The PGP documentation has a rather good section about the
practicalities of using PGP, it bears careful reading.
Of course, this has nothing to do with the absurdity of the
original topic.
Mark
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: ascii to binary
Date: 4 Feb 2000 08:58:03 +0100
In article <[EMAIL PROTECTED]>,
NFN NMI L. <[EMAIL PROTECTED]> wrote:
>Gaaaach. Look at all the cruddy C code.
>
>In any case, ASCII is stored as binary. Maybe you C (scoff) people think of
>ASCII as 0-255, but I've always though of it as 8-bit binary codes
Even on systems where one bye isn't 8 bits, but instead 6, 7, 9 or 12 bits?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: 4 Feb 2000 08:59:21 +0100
In article <[EMAIL PROTECTED]>,
NFN NMI L. <[EMAIL PROTECTED]> wrote:
><<They purport that the NSA has ALL POSSIBLE keys for PGP>>
>
>Yes. Now, the question is, where is the NSA hiding their hard drive? It'll
>make exabyte storage capacities look like bits of fluff.
It indeed would: even if the NSA had the entire universe at their
disposal, and was able to store one bit in each and every atom,
that wouldn't be enough.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: 04 Feb 2000 03:27:27 EST
In article <87bt0s$7ck$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tom St Denis) wrote:
>Anyone who thinks you can make a list [and store it] of 512 bit primes
>[even 128 bit primes....] is just insane.
I just did, and posted it. Here it is again: "10". Two characters.
(this being a *humor* post, there are practical difficulties, but data
storage isn't on of them.)
Method used:
Consider the following set of keys (rules selected to keep list short)
11
12
13
21
22
23
31
32
33
This is a coplete list of all keys that are two characters long
and contain only the characters "1" "2" and "3".
I can represent this list as follows:
111213212223313233
Which can be considered a a single number.
Clearly the list of all possible PGP keys can also be turned
(after a base conversion) into one (REALLY BIG) number.
Now, the number above would seem to require 18 digits, but
that's only if you represent it in base 10.. In base 16,
it would be C8E69551, which has 8 digits. (In base 2, it
would be 11001000111001101001010101010001 - 32 digits).
Thus I can extend the above scheme to represent
111213212223313233 as 10 in base 111213212223313233.
Clearly I can do the same with the number that I make
out of the sum of all PGP keys. Let's call it "PBN"
(Pretty Big Number). The universe is too small to
write down PBN in binary, decimal, or hex, but you
can write down PBN in base PBN with ease. it's "10".
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Does the NSA have ALL Possible PGP keys?
Date: 04 Feb 2000 03:32:47 EST
In article <87acst$kqf$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Xcott Craver)
wrote:
>
>Guy Macon <[EMAIL PROTECTED]> wrote:
>>
> [...]
>>
>>Thus I can extend the above scheme to represent
>>111213212223313233 as 10 in base 111213212223313233.
>
> How would you represent 111213212223313233-1?
I am glad that you asked that question.
That was a fine question - on of the best that I have seen.
You are to be commended for your insight.
I hope that this answered your question.
Are there any further questions?
(If anybody has missed the fact that I am doing a parody of
certain posters, please email me for an explaination)
------------------------------
** 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
******************************
