Cryptography-Digest Digest #573, Volume #12 Wed, 30 Aug 00 13:13:01 EDT
Contents:
Re: Idea for creating primes (Mark Wooding)
Re: PGP ADK Bug: What we expect from N.A.I. (Mark Wooding)
Re: 4096 BIT RSA Key (Mark Wooding)
Re: "Warn when encrypting to keys with an ADK" (Tom McCune)
Re: A little technical note about intepreters (Jeffrey Williams)
Re: Destruction of CDs (Jeffrey Williams)
Re: Idea for creating primes (Robert Harley)
Where is everyone? (Rich Griffin)
Re: I need ADK tampered key that PGP will not detect ADK, on it ... (jungle)
Re: Idea for creating primes (Zulfikar Ramzan)
Re: 4096 BIT RSA Key (DJohn37050)
Re: Idea for creating primes ("Scott Fluhrer")
Re: Idea for creating primes ([EMAIL PROTECTED])
RSA public exponent ("John Matzen")
Re: RSA public exponent ([EMAIL PROTECTED])
Re: RSA public exponent (Thomas Pornin)
Re: RSA public exponent (David A Molnar)
Re: Primitive polynomial generator (Mike Rosing)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Idea for creating primes
Date: 30 Aug 2000 09:50:08 GMT
Big Boy Barry <[EMAIL PROTECTED]> wrote:
> did you patent this?
I wouldn't have thought he'd get very far trying: it's far too obvious.
I thought of exactly the same thing a few weeks ago and didn't consider
it worth mentioning even in passing. A better approach to generation of
provable primes is probably to use Maurer's algorithm (HAC 4.4.4).
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: PGP ADK Bug: What we expect from N.A.I.
Date: 30 Aug 2000 09:56:54 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
> You probably meant "sensitive". "Sensible" it definitely isn't!
I disagree that it's a totally daft feature.
There is a definite requirement for an employer to want to recover
messages sent to an employee in the course of his or her job if the
employee is unable to decrypt messages for some reason (e.g., run over
by a bus, disgruntled and left, or whatever).
Perhaps a key-recovery mechanism is a better way of doing this -- you
could store a key-recovery blob for the user's decryption key protected
by some high-security key shared among appropriate important people.
However, key recovery was a bit of a dirty word back when this was being
implemented.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: 4096 BIT RSA Key
Date: 30 Aug 2000 10:03:50 GMT
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> The real issue with huge RSA keys in pgp is the tendancy to make them
> so much stronger than the underlying block cipher. Once you've passed
> the point where guessing the session key is less work than factoring
> the RSA key, you may as well stop making that bigger. ;)
The cut-off point where RSA stops being the weak link for encryption is
quite high -- somewhere around 1600 bits (or possibly higher, depending
on who you listen to). There can be good reasons for wanting to use key
lengths which are a power of two, so 2048 bits isn't *completely* daft.
> On a personal note, though, I admit I tend to "oversize" keys which
> can be used for signatures a bit, if not that much.
That's sillier. PGP doesn't have a hashing algorithm which offers more
than 80 bits of security against collision-finding attacks. A 1024-bit
signature key is a reasonable choice.
-- [mdw]
------------------------------
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: "Warn when encrypting to keys with an ADK"
Date: Wed, 30 Aug 2000 10:35:06 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
In article <8ohtlr$l6$[EMAIL PROTECTED]>, Philip Stromer
<[EMAIL PROTECTED]> wrote:
>In article <8o5n05$kiv$[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] wrote:
>
>If I'm using PGP 6.5.3, and I have the box checked under Options,
>Advanced, Warn when encrypting to keys with an ADK, am I protected
>without applying the Hotfix? If not, why not, in lay language, please!
>
>I'm confused as all heck by this announcement. PGP seemed at first to
>say "yes, there is a serious bug," but now they seem to be saying "it's
>not such a big deal, after all."
>
>Thanks in advance.
I'm thinking that I might need to add some more information, but this
might help: http://www.McCune.cc/PGPpage2.htm#ADKSecurityFlaw
=====BEGIN PGP SIGNATURE=====
Version: PGP Personal Privacy 6.5.3
Comment: My PGP Page & FAQ: http://www.McCune.cc/PGP.htm
iQA/AwUBOazj/Q2jfaGYDC35EQKHZQCgy8lGaA5kASWjZYzadl5tPb+USEcAoNsn
kgvQZsVSidB5YmcvH/xL8tG3
=A1DN
=====END PGP SIGNATURE=====
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: A little technical note about intepreters
Date: Wed, 30 Aug 2000 07:03:28 -0500
My goodness. I hadn't intended to cause such a large quantity of OT
traffic. I only wanted to provide Tom with an example of how even those
who ought to be well-informed in our technical society are not
necessarily so.
Like many other aspects of computer science, commenting verges on the
religious, frequently with extremists adherents (I, myself, have fairly
extreme views on the matter, but will not expound them here as we are
severely OT).
LL&P
Jeff
"Douglas A. Gwyn" wrote:
> Andrew Carol wrote:
> > Comments are a good thing.
>
> Only when used appropriately.
> To be useful, a comment must be present, informative,
> and accurate.
> Kernighan & Plauger had something to say about this
> in "Elements of Programming Style".
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: Destruction of CDs
Date: Wed, 30 Aug 2000 07:06:18 -0500
Why erase it multiple times if you're going to physically destroy it? It
would almost certainly take less time to melt the disk in the fireplace (or
the oven) than to erase it multiple times.
Eric Smith wrote:
> Thomas W. Barr wrote:
> > I, for one, would use a CD-RW for my one-time-pads and then go through
> > an erase cycle, write 650mb of junk data (make sure you overwrite the
> > FAT), and erase that. This would remove ALL remnants of data that could
> > be left behind in the walls of the tracks.
>
> [EMAIL PROTECTED] (Guy Macon) writes:
> > It bwould be cheaper and more secure to use a CR-R and burn it
> > (I mean in a fire pit, not a drive!) afterwards.
>
> Better yet, use the CD-RW, erase it multiple times, then physically
> destroy it.
------------------------------
From: Robert Harley <[EMAIL PROTECTED]>
Subject: Re: Idea for creating primes
Date: 30 Aug 2000 15:01:16 +0200
[EMAIL PROTECTED] (Mark Wooding) writes:
> Big Boy Barry <[EMAIL PROTECTED]> wrote:
> > did you patent this?
>
> I wouldn't have thought he'd get very far trying: it's far too obvious.
Like that ever stopped anybody!
It seems that the majority of patents are obvious, never mind "to a
person skilled in the art" which is supposed to be one of the
criterions for invalidity.
Rob.
.-. .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' [EMAIL PROTECTED] `-'
------------------------------
Subject: Where is everyone?
From: [EMAIL PROTECTED] (Rich Griffin)
Date: Wed, 30 Aug 2000 13:19:33 GMT
Is is just my ISP, or have all the messages disappeared?
------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: I need ADK tampered key that PGP will not detect ADK, on it ...
Date: Wed, 30 Aug 2000 09:57:53 -0400
thanks for excellent response ...
I tested A4 key on the day the article become public ...
[ that's why I created my question ]
pgp v658 ? I don't have reason to upgrade from v262 ...
the adk problem [ realistically doesn't exist ], when you [ I ] know what I'm
doing ...
the first simple rule in encryption software business is :
- don't use when you don't know what is inside ...
when you know, you are the lucky one who works for nai company ...
I don't know because source code is not available ...
Rich Wales wrote:
>
> "jungle" wrote:
>
> > the question is open : could someone post public key
> > that is tampered & pgp will not detect added ADK to
> > it ? I need ADK tampered key that PGP will not detect
> > ADK, on it ...
>
> Have you tried Ralf Senderek's "A4" key with NAI's latest PGP (6.5.8)?
> (That is, the same key you've already tried, but with a different PGP?)
------------------------------
Date: Wed, 30 Aug 2000 10:32:16 -0400
From: Zulfikar Ramzan <[EMAIL PROTECTED]>
Subject: Re: Idea for creating primes
> Next question - can we work out a way to encrypt a proof of primality
> along with the number of which it proves the primality in such a way that
>
> a) we know that the encrypted number is prime (i.e. the proof still works)
>
> but
>
> b) we have no idea what the encrypted number is
>
> and potentially
>
> c) we can multiply together two encrypted numbers E(p), E(q) which have
> encrypted proofs of primality to obtain E(pq), then give a proof
> that D(E(pq)) = n, the product of two primes and an RSA modulus?
>
> It seems at the minimum we'd need an encryption scheme which is
> a multiplicative homomorphism. But there may be more to it than that;
> I haven't thought about it at length. For one thing, over what would it
> be a homomorphism, since you have many different groups involved? :\
>
A similar kind of question has been addressed in the literature, I believe. There
is a paper by Liskov and Silverman, as well as one by Camenisch and Michels -- I
don't have the papers or references offhand, so I may be off. The later paper
appeared, I believe, two Eurocrypts ago.
I don't remember the results too well, but here's a very weak attempt to
recapitulate:
The idea in the [CM] paper is to use Pedersen commitments and commit two prime
numbers, and give you a modulus, which is their product. Then you can do
non-interactive zero knowledge proofs that the commitment of both values are
primes, and that their product is the modulus n.
The above papers actually go several steps further and show that the resulting RSA
key is balanced -- that is the primes p and q are roughly the same size.
This question is slightly different from the one you are asking since we deal with
commitments here, and not specifically with encryption. Though I suspect this
approach suffices for what you want.
> -David
--
--Zully
=======
Zulfikar Ramzan (AKA Zully)
Laboratory for Computer Science, MIT
NE43-311, (617) 253-2345
http://theory.lcs.mit.edu/~zulfikar/homepage.html
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 30 Aug 2000 14:46:38 GMT
Subject: Re: 4096 BIT RSA Key
Recall SHA-2 will be out shortly with 256, 392 and 512 bit output. So this
will offer up to 256 symmetric key security, as in AES. NIST has said that
2048 DSA keys are appropriate for 112 bit (Triple DES) keys and 3072 DSA keys
are appropriate for 128 bit AES keys. And DSA is considered slightly stronger
than RSA for same key length.
Don Johnson
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Idea for creating primes
Date: Wed, 30 Aug 2000 07:40:09 -0700
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> [EMAIL PROTECTED] wrote:
> >
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >
> > >
> > > [EMAIL PROTECTED] wrote:
> > > >
> > > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > > > > [EMAIL PROTECTED] wrote:
> > > > > >
> > > > > [snip]
> > > > > > You can test to see if a number is a genrerator by performing g^
> > > > (p/q) !
> > > > > > = 1 for various 'q's that divide your testing prime 'p'.
> > > > > [snip]
> > > > >
> > > > > I suspect there is a printing error here. If one knows that
> > > > > there is a q that divides p, then p is certainly not a prime,
> > > > > isn't it? Or how should one properly interpret that phrase
> > > > > above? Thanks.
> > > >
> > > > Simple typo.
> > > >
> > > > You have your list of smaller primes N1, N2, N3 ...
> > > >
> > > > then you have the value p' = 2*N1*N2*N3*N4*...
> > > >
> > > > Then you have the value p = p' + 1
> > > >
> > > > Sorry for the confusion. You are looking for a value q that divides
> > > > the value p'
> > >
> > > Questions:
> > >
> > > (1) Your g is such that (g,p)=1 and g^p' = 1 and g^s != 1
> > > for all s equal to p' divided by one of its factors?
> > > Is that right?
> >
> > Yea, you want to make sure that g doesn't belong to a sub-group.
>
> O.k. This shows that the order of g is p-1 and hence p is
> prime. But in a book of mine where this is proved it is
> said that finding primes this way for large p is too slow
> compared to modern methods.
Actually, it's about as fast as a few passes with the Miller-Rabin test. In
both cases, you pick a g, determine g^k mod p, where k is about as large as
p, and then run quick tests on the results. With Tom's test, you run it
once for every prime dividing p-1 (plus a few times to find an appropriate
g). With Miller-Rabin's test, you run it until you get error probability
"small enough". And, in both cases, when p is not prime, then almost all
the time, you'll find it out the very first time you compute g^k mod p.
And, of course, with both methods, you do some quick composite checks (eg.
checking for small factors) first.
What I suspect your book says that it's a slow way to prove a number p prime
assuming you don't know a priori the factorization of p-1, because factoring
p-1 is a bear. With Tom's approach, that isn't a problem.
--
poncho
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Idea for creating primes
Date: Wed, 30 Aug 2000 15:59:35 GMT
In article <8oj7hd$mqg$[EMAIL PROTECTED]>,
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
> Actually, it's about as fast as a few passes with the Miller-Rabin
test. In
> both cases, you pick a g, determine g^k mod p, where k is about as
large as
> p, and then run quick tests on the results. With Tom's test, you run
it
> once for every prime dividing p-1 (plus a few times to find an
appropriate
> g). With Miller-Rabin's test, you run it until you get error
probability
> "small enough". And, in both cases, when p is not prime, then almost
all
> the time, you'll find it out the very first time you compute g^k mod
p.
> And, of course, with both methods, you do some quick composite checks
(eg.
> checking for small factors) first.
That's slightly right. My problem works the other way in that as soon
as you find a primitive generator you know it's prime. However when
you start with g=2 "g^k mod p" will not tell you right away that it's
prime or not, unlike MR which will almost always immediately
say "composite" if it is composite. With my method however you can
discard values of g once you find a subgroup they belong to, so at most
you will have to try a few times per base 'g'.
> What I suspect your book says that it's a slow way to prove a number
p prime
> assuming you don't know a priori the factorization of p-1, because
factoring
> p-1 is a bear. With Tom's approach, that isn't a problem.
Well that's why the factors of (p - 1) are small, it makes proving they
are prime is easier. And of course you can recurse this to use 64-bit
primes to make the 128-bit primes, etc...
It's just an idea.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "John Matzen" <jmatzen(at)origin(d0t)ea(d0t)com>
Subject: RSA public exponent
Date: Wed, 30 Aug 2000 11:13:01 -0500
I've read that good values for the RSA public exponent are 3 or 65537. Then
I read that you should use an exponent such that the GCD of (q-1)(p-1) and
the private exponent (e) is 1. So, my question is which is better and what
accounts for the disparity.
- John
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA public exponent
Date: Wed, 30 Aug 2000 16:44:33 GMT
In article <[EMAIL PROTECTED]>,
"John Matzen" <jmatzen(at)origin(d0t)ea(d0t)com> wrote:
> I've read that good values for the RSA public exponent are 3 or
65537. Then
> I read that you should use an exponent such that the GCD of (q-1)(p-
1) and
> the private exponent (e) is 1. So, my question is which is better
and what
> accounts for the disparity.
Um you obviously don't understand. You "fix" the value of 'e' to
3,17,65537 (I would choose the latter myself) and find a 'd' that
works. You don't do both.
For any lcm(q-1,p-1) that is not a multiple of 'e' you can find a 'd'
that will allow de = 1 (mod lcm(p-1,q-1)).
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: RSA public exponent
Date: 30 Aug 2000 16:53:45 GMT
According to John Matzen <jmatzen(at)origin(d0t)ea(d0t)com>:
> I've read that good values for the RSA public exponent are 3 or 65537.
> Then I read that you should use an exponent such that the GCD of
> (q-1)(p-1) and the private exponent (e) is 1. So, my question is which
> is better and what accounts for the disparity.
e must be prime to (p-1)(q-1), so, when you choose your key, by
randomly selecting p and q, you are more likely to have this property
if e is prime. Your odds are about 44% with e = 3, and almost 100%
with e = 65537, that the two first primes you choose are good in
that respect.
When enciphering with the public exponent, you perform a modular
exponentiation, using usually the famous "square and multiply"
algorithm. The complexity of this algorithm can be expressed in modular
multiplications, and depends upon the binary representation of the
exponent: each bit (except the first one) in the exponent means one
squaring, and one extra multiplication if that bit is set to 1. 65537
has the binary representation 10000000000000001, which means that there
will be only one multiplication, and 16 modular squarings.
e = 3 is the original exponent proposed in the paper from Rivest, Shamir
and Adleman. However, there is a (real slight) security concern: if
you encipher the same message three times with three different public
keys and public exponent 3, an attacker will be able to retrieve the
plaintext from the three ciphertext: if you have m^3 modulo N1, N2 and
N3, you can easily get m^3 modulo N1*N2*N3 by Chinese Reminder Theorem.
However, N1*N2*N3 is larger than m^3 (without the modulo) so you have
m^3 with no modular reduction, and a simple integer cubic root will
give you m.
With e = 65537, this problem does not appear unless you encrypt the
very same message 65537 times with 65537 different public keys. Quite
unlikely.
Note that the vulnerability does not affect PGP, since PGP encrypts en
random session key with RSA, and this random key is never twice the
same, even if the underlying message has not changed.
To sum up, e = 3 is faster for encryption, and e = 65537 is faster
for key generation.
--Thomas Pornin
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: 30 Aug 2000 16:39:33 GMT
John Matzen <jmatzen(at)origin(d0t)ea(d0t)com> wrote:
> I've read that good values for the RSA public exponent are 3 or 65537. Then
These are chosen because they have few 1s in them and so require
relatively little computation time. This is just a recommendation.
> I read that you should use an exponent such that the GCD of (q-1)(p-1) and
> the private exponent (e) is 1.
If this condition is not satisfied, then e will not have an inverse modulo
(q-1)(p(-1), and so no decryption key will exist. This is necessary and
must be satisfied by all choices of e.
It's just that 3 and 65537 are particularly popular choices of e which
satisfy this criterion always and almost always respectively.
> So, my question is which is better and what
> accounts for the disparity.
There isn't a disparity, really. Consider that q-1 and p-1 are both even,
thus their product is even. So gcd( (p-1)*(q-1), 3) = 1 always.
If the gcd of 65537 with p-1q-1 is not 1, then calculating the decryption
key d will fail, and you'll notice that, but for randomly chosen p and q
you wouldn't expect this to happen very often.
-David
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Primitive polynomial generator
Date: Wed, 30 Aug 2000 12:00:32 -0500
Benjamin Goldberg wrote:
>
> This might not be the best place to put this request, but ...
>
> Where can I find a C program that, for any N, will generate a random
> order N primitive polynomial (for use as a modulo for GF(2^N))?
>
> I'll probably be using it with N = 32, 64, 128 or 256, not other values.
>
> Having two versions, one written for clarity, one for speed/efficiency
> would be MUCH appreciated.
You can find a subroutine called "irreducible()" in the file polymain.c
on my web site: http://www.terracom.net/~eresrch. Just feed it random
values until you get a prime, then check it's order. Checking the order
is easy, you just take x to powers of the factors of N-1 modulo the polynomial
and see if you get 1. If not, it's primitive.
You might also look at Maple, Mathematica and other high level math programs.
I'm sure it's built in.
Patience, persistence, truth,
Dr. mike
------------------------------
** 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
******************************
