Cryptography-Digest Digest #949, Volume #9 Thu, 29 Jul 99 11:13:03 EDT
Contents:
Re: Is breaking RSA NP-Complete ? (Scott Fluhrer)
Re: Prime numbers wanted (John Savard)
Re: Can you use HASH functions for identification? (Michelle Davis)
Re: Pentium III & cripto ("arcmight")
Re: Can you use HASH functions for identification? (Erwin Bolwidt)
Re: another news article on Kryptos (Mok-Kong Shen)
CSS/DVD Scrambler ([EMAIL PROTECTED])
Best way to ensure integrity of this system? (Matt)
Knapsack Problem? TryIt! (Vladimir Zabrodsky)
Re: OTP export controlled? (Isaac)
CIA's KRYPTOS Decoding End ("collomb")
RSA keys 2^64x + c versus SNFS (Francois Grieu)
Re: Modified Vigenere cipher (Jim Gillogly)
Re: What the hell is XOR? (John M. Gamble)
Observations on the Encrypting File System .. (Markku-Juhani O. Saarinen)
Re: Rsa-512 (Bob Silverman)
Re: the defintion of Entropy (Anton Stiglic)
Re: Is breaking RSA NP-Complete ? (Anton Stiglic)
Re: Freeware version of PGP !!! (Jerry Coffin)
Re: Is breaking RSA NP-Complete ? (Bob Silverman)
Re: Q: Does ElGamal require that (p-1)/2 is also prime like DH? (Anton Stiglic)
Re: Q: Does ElGamal require that (p-1)/2 is also prime like DH? (Anton Stiglic)
----------------------------------------------------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Thu, 29 Jul 1999 06:11:14 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
>jd_bertron wrote:
>
>> Has someone found a reduction of another NP-Complete problem to
>> breaking RSA ?
>
>No, it is not NP-Complete. In fact, there is no crypto-system that is
>based on an NP-Complete problem. Factoring, for example, is a
>problem that is in a class a "little under" NP-Complete (I forgot the
>name, sorry), and above P of cours (there might be other ways to break
>RSA than factoring, but that would just make RSA an "easier" problem).
>There is an article, in a recent Crypto or Eurocrypt, improving on
>earlier results, that discusses this problem (there is something about
>the hierarchy collapsing if a cryptosystem problem would be NP-Complete).
I know it (either the RSA problem, or factoring) is not known to be
NP-Complete, and I know it has been proven that it is not NP-Complete if
NP != co-NP, but do we know anything beyond that?
For that matter, I didn't think we knew that factoring wasn't P, even if
P != NP.
>
>I'll try to get info on the exact references....
Please do. I don't keep up with the literature as much as I ought...
--
poncho
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Prime numbers wanted
Date: Wed, 28 Jul 1999 22:35:18 GMT
Roger Carbol <[EMAIL PROTECTED]> wrote, in part:
>Does looking up the number in a table of primes count as a method?
Not for finding a 200 digit long prime that nobody's thought of
before, for use in forming an RSA modulus, no.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Michelle Davis)
Subject: Re: Can you use HASH functions for identification?
Date: Thu, 29 Jul 1999 08:23:11 GMT
Hey! I'm sure this is against net etiquette and all (sorry, I'm new to
this), but I'd really, really apreciate it if someone could tell me
his opinion on my idea. Thing is, it might be the basis for a paper I
have coming up in applied math (I'm studying at TAU), and the deadline
is really, really soon.
Thanks a lot,
Michelle
------------------------------
From: "arcmight" <[EMAIL PROTECTED]>
Subject: Re: Pentium III & cripto
Date: Thu, 29 Jul 1999 03:02:49 -0700
Ah, go search on the patent server under Davis and intel. You'll find the
entire
hardware based certificate store ( which is their future marketing ) there
for your perusal..
This by the way, blows a bunch of hardware based ecommerce companies out of
the water for
patent infringement, and as my patent lawyer says, "...Intel is not known
for being accomodating.."
John Savard wrote in message <[EMAIL PROTECTED]>...
>[EMAIL PROTECTED] wrote, in part:
>
>>Does anyone knows how is going to affect the new Pentium III's SIMD
>>instructions in the computing of crypto algorithms?
>
>>There is going to be any speed up at all?
>
>The Pentium III's "Streaming SIMD Extensions" are an extension of MMX
>which includes, as its major feature, short vector (two elements!)
>floating-point arithmetic.
>
>This won't be terribly relevant to cryptography, which usually uses
>integer arithmetic. When floating-point arithmetic is used, for
>example in some Schonhage-Strassen routines, it is double-precision
>arithmetic which is used in any case. (SSE fits two 32-bit single
>precision reals in one 64-bit vector.)
>
>So there is very little relevance of this new feature to cryptography.
>
>However, a new support chip used with the Pentium III offers the very
>important feature of hardware random numbers, but that feature is not
>generally available (documentation of it is not released).
>
>The forthcoming (middle of next year) IA-64 architecture does promise
>some exciting improvements that may relate to cryptography. A
>population count instruction is included (maybe because PA-RISC had
>one?) and there is also a transposition instruction, MUX;
>unfortunately, though, it only transposes 16-bit segments in an
>arbitrary way, and 8-bit bytes in a handful of preprogrammed ways;
>there is no real bit transposition instruction.
>
>John Savard ( teneerf<- )
>http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Erwin Bolwidt <[EMAIL PROTECTED]>
Subject: Re: Can you use HASH functions for identification?
Date: Thu, 29 Jul 1999 12:14:41 +0200
Michelle Davis wrote:
> Anyone knows if this sort of thing is already around? Either way, does
> my authentication scenario make sense? I'd really like to hear some
> input.
Yes, it's already in use. There's an alternative HTTP authentication
scheme based on MD5 hashes (not supported by many browsers) .
An extension to the standard POP mail-retrieval protocol, APOP, also uses
MD5 hashes for authentication, somewhat but not exactly in the manner you
describe; see http://www.faqs.org/rfcs/rfc1725.html
(You "challenge text" would be the "shared secret" in the POP protocol,
and your "reference number" would be the POP "timestamp", and that
timestamp is generated by the recipient of the authentication instead of
the originator as in your proposal, which, together with the requirement
that the timestamp be unique, eliminates the risk of a replay attack.)
Best,
Erwin
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: another news article on Kryptos
Date: Thu, 22 Jul 1999 11:12:09 +0200
Doug Gwyn (ISTD/CNS) wrote:
>
> Certainly, the more complex you make the encryption system,
> *usually* more work (and input data) is needed to crack it.
>
> But "switching algorithms" under control of a key is itself
> a fixed algorithm, just more complex than its components.
Besides switching algorithms and employing parametrized algorithms
mentioned previously, I use to think that there is substantial
potential of variability obtainable when one uses superencipherment.
For chaining n algorithms can be done in n factorail different
ways. Even for n as low as 3 the impact on the analyst could be
huge. (It is assumed, of course, that the chaining of the specific
algorithms concerned does not introduce weakness.)
BTW, in a recent thread one learned that in the realm of classical
methods double transpositions result in an effective key length which
is the LCM of the key lengths of the components. Could it be that the
yet unsolved part of Kryptos is superenciphered?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: CSS/DVD Scrambler
Date: Thu, 22 Jul 1999 10:03:17 GMT
Is the CSS/DVD-style crypt algorithm available anywhere, or information
about it? I know to read keys of the disk but that alone is rather
useless.
Or is it another of those things that can't be exported etc etc?
Cheers for any reply,
Lund
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Matt <[EMAIL PROTECTED]>
Subject: Best way to ensure integrity of this system?
Date: Thu, 29 Jul 1999 18:39:13 +0800
Hi there.
I am currently contemplating creating some software which will stay
resident on a user's screen, and display adverts. Through revenue raised
from advertises, the user will be paid per hour or part thereof, at a
fixed rate.
I would like suggestions on the best way to ensure that this system will
be extremely difficult to 'hack' or rorted, possibly using encryption of
the data communicated. I realise that it would be quite difficult to
keep keys secret in the client-side software, so any suggestions would
be appreciated.
Thanks,
Matt.
(please also reply to [EMAIL PROTECTED])
------------------------------
From: Vladimir Zabrodsky <[EMAIL PROTECTED]>
Subject: Knapsack Problem? TryIt!
Date: Thu, 29 Jul 1999 10:40:09 GMT
Hello,
could you read my article "Does it make sense to solve the knapsack
problem? TryIt!", please? See:
http://www.geocities.com/SiliconValley/Garage/3323/knapsack.html
Abstract: There are many variations of the knapsack problem; we
consider only a simple one dealing with one-dimensional items: Given an
array of positive integers A[1], ..., A[N]and an positive integer C
find a subset of A[1], ..., A[N] that sums to C. An particular case of
the knapsack problem is the partition problem: Given N positive
integers, is there a way to partition the integers into 2 disjoint
subsets so that the sum of the integers in each of the two subsets is
equal?
We can read in literature:
The only known solution is brute force: test all possible subsets until
the sum is found or you run out of subsets. When you have partition
items from an office, i.e. for N (approximately) equals 100, it doesn't
make sense to solve by WORLD'S FASTEST COMPUTER.
I introduce a simple algorithm TryIt!; while an array A will contain
really values of items (about 500 values of items from office or garage
or hangar or dock) then the problem can be solved ALMOST ALWAYS only by
the Rexx INTERPRETER and an ORDINARY PC in a REASONABLE amount of time.
=====================
Thanks advance. I am looking forward your comment.
Vladimir Zabrodsky
CKD Blansko a.s., Gellhornova 1, Blansko 678 01, Czech Republic
[EMAIL PROTECTED]
http://www.geocities.com/SiliconValley/Garage/3323
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Isaac)
Crossposted-To: talk.politics.crypto
Subject: Re: OTP export controlled?
Date: 29 Jul 1999 11:22:43 GMT
On Thu, 29 Jul 1999 05:12:50 GMT, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Isaac wrote:
>> ... Software with crypto shaped holes in it, that is with "hooks"
>> for crypto is also not exportable.
>
>You seem to have missed something crucial, to wit, the code I
>posted is a complete cryptosystem *if you choose to use it as one*.
>(Sender and receiver need to agree upon a file to use as the "key".)
>Yet I doubt that you're claiming it is "not exportable".
>
I didn't miss anything. Your code is not a complete system.
The part about sender and receiver agreeing upon a key is simply
not a trivial exercise. A true OTP is known to be unbreakable.
The reason why other, possibly breakable systems, are thousands of
times more popular is because they address the problems with
generating, sharing, and managing keys. Those things aren't
frills, and with a OTP they mean the difference between security
and false security. You haven't addressed any of these things.
Now perhaps you can fall short of the system I describe and still
draw the ire of the Commerce Department, but I personally wouldn't
be concerned with the code you posted.
Isaac
------------------------------
From: "collomb" <[EMAIL PROTECTED]>
Subject: CIA's KRYPTOS Decoding End
Date: 29 Jul 1999 12:19:38 GMT
KRYPTOS Decoding End
The solution of the enigma hidden in CIA's KRYPTOS sculpture is explained
step by step on my web site�:
http://calvaweb.calvacom.fr/collomb/
Best Regards
------------------------------
From: [EMAIL PROTECTED] (Francois Grieu)
Subject: RSA keys 2^64x + c versus SNFS
Date: Thu, 29 Jul 1999 15:44:35 +0200
Some standards, including [1] and former versions of [2], consider RSA
keys where the public modulus has the special form 2^(64x) + c with
|c| "small".
Such special form have been criticized: [3] and [2] warn that "moduli
of this form are readily suceptible now to the special version of the
Number Field Sieve and are quite insecure".
Still [1] suggests to use public keys of form n = p.q = 2^(64x) + c
with |c| > 2^(48x-1)
Loosely speaking c is at least 75% the size of the public modulus.
Question: is that enough to guard against SNFS ?
Francois Grieu - Innovatron
----
[1] ISO/IEC FCD 9796-1, "Information technology - Security techniques
- Digital signature scheme giving message recovery � Part 1: Mechanisms
using redundancy" (revision of ISO/IEC 9796: 1991)
[2] ANSI X9.31-1998, "Digital Signatures Using Reversible Public Key
Cryptography For The Financial Services Industry (rDSA)"
[3] R.D. Silverman, �Fast Generation of Random, Strong RSA Primes�,
May 17, 1997; available from <ftp://ftp.rsa.com/pub/ps/generation.zip>
in a Postcript dialect viewable with Ghostscript.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Modified Vigenere cipher
Date: Thu, 29 Jul 1999 07:04:32 -0700
Alexander Demin wrote:
> Has anybody solved the problem from Charles Wetherell's book 'Etudes
> for programmers' (chapter 24)?
> The problem is a modified vigenere cipher.
> But Wetherell used the non-plain alphabet and the table looks like
> this:
>
> abcdefghijklmnopqrstuvwxyz
> -------------------------------------
> a| qwertyuiopasdfghjklzxcvbnm <-- this is a random mixed alphabet
> b| wertyuiopasdfghjklzxcvbnmq
> c| ertyuiopasdfghjklzxcvbnmqw
> d| rtyuiopasdfghjklzxcvbnmqwe
> ...
> z| mqwertyuiopasdfghjklzxcvbn
>
> So, now the problem (when using non-plain alphabet) has two keys: the
> keyword and the alphabet.
>
> So, has anybody solved this modification of the vigenere cipher?
The first two pieces of the Kryptos sculpture used the next harder
variation, which has the plaintext alphabet on top mixed the same
way as the internal ciphertext alphabet. This method is also used
in the CipherClerk home page challenge at
http://members.magnet.at/wilhelm.m.plotz/ without a crib, but
with word divisions and capitalization retained.
The version you show is called "Quagmire II" by the American
Cryptogram Association, and is considered relatively simple
given some known plaintext. It's more challenging without
a crib, but still not too hard given sufficient depth.
Interestingly, Vigenere originally proposed mixed alphabets,
but only the simpler kind is now associated with his name.
> P.S. I can't post the crypted text here because I've got only russian
> translation of the original text.
Is the problem translated into a corresponding Russian version?
--
Jim Gillogly
6 Wedmath S.R. 1999, 13:50
12.19.6.7.4, 9 Kan 12 Xul, Ninth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (John M. Gamble)
Subject: Re: What the hell is XOR?
Date: 29 Jul 1999 13:46:18 GMT
In article <[EMAIL PROTECTED]>,
fungus <[EMAIL PROTECTED]> wrote:
>
>
>"Douglas A. Gwyn" wrote:
>>
>> "SCOTT19U.ZIP_GUY" wrote:
>> > XOR R1,R2 which is make r2 = r1 XOR r2
>> > XOR R2,R1 which is make r1 = r1 XOR r2
>> > XOR R1,R2 which is make r1 = r1 XOR r2
>>
>> This is a well-known hack.
>
>Yes, very well known....
>
>> Unless there
>> is a bottleneck at that point, swapping via a temporary
>> would be clearer and thus preferable (from a code
>> maintenance point of view).
If my maintainers didn't know this trick, or even worse,
didn't ask anyone about it if they didn't know it, i have
them off in a different department very, very, quickly.
>
>And don't forget that doing this via pointers is
>dangerous, eg. (in C)
>
>void swap(int *a, int *b)
>{
> *a ^= *b;
> *b ^= *a;
> *a ^= *b;
>}
>
>Will fail if a and b both point to the same int. Watch out
>for hard-to-find bugs if you ever do anything like this.
>
But good heavens, why would you do it like that?
/*
** Swap via the three-xor method, contained in a single line.
*/
#define swap(a, b) (a ^= (b ^= (a ^= b)))
And you'll note that i commented my code, which no one else
seems to have bothered. Frankly, if a programmer didn't know
the exchange by XOR method (hell, i knew it before i became a
programmer), and didn't bother to comment his/her code (but
it's obviouse, right? - no, nothing is obvious, espacially at
2AM), then i'd have serious doubts about hiring this person.
-john
February 28 1997: Last day libraries could order catalogue cards
from the Library of Congress.
--
Pursuant to US Code, Title 47, Chapter 5, Subchapter II, '227,
any and all unsolicited commercial E-mail sent to this address
is subject to a download and archival fee in the amount of $500
US. E-mailing denotes acceptance of these terms.
------------------------------
From: Markku-Juhani O. Saarinen <[EMAIL PROTECTED]>
Subject: Observations on the Encrypting File System ..
Date: 29 Jul 1999 13:02:29 GMT
The Encrypting File System (EFS) executive summary & tech. overview from
Microsoft [1] claims that the EFS in North American versions of Windows
2000 uses 128-bit DESX. The exportable version comes with 40-bit DESX
("40-bit keys (..) are expanded to the required 128 bits for DESX").
Both versions use key recovery. No other bulk data encryption methods
besides DESX are mentioned.
The paper also states that
"Currently, Microsoft is working with the United States government to
get export approval for EFS with 128-bit DES [sic] as the file
encryption algorithm along with its built-in recovery infrastructure."
The claim for 128-bit security is obviously wrong: Rogaway shows in [2]
that DESX has a 118-lg(m) security upper bound against brute force search,
where m is the number of DESX-encrypted message blocks the adversary can
obtain.
The microsoft paper [1] states very clearly that EFS uses DESX with
128-bit keys. Recall that DESX uses 184 bits of keying material. *IF* 56
bits of either one of the whitening keys are zero, it is easy to see that
the security of the "128-bit" DESX would be around 2^64 (the attack
requires only two known plaintext blocks). Can anyone confirm or disprove
this ?
[1] Microsoft, "Encrypting File System for Windows 2000"
http://www.microsoft.com/windows/server/Technical/security/encrypt.asp
[2] Phillip Rogaway, "The Security of DESX"
CryptoBytes 2 / 1996
- mj
Markku-Juhani Saarinen <[EMAIL PROTECTED]> University of Jyv�skyl�, Finland
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Rsa-512
Date: Thu, 29 Jul 1999 14:02:48 GMT
In article <[EMAIL PROTECTED]>,
"Adam Pridmore" <[EMAIL PROTECTED]> wrote:
> I know that RSA-512 is looking a little insecure, but I was curious
as to
> how insecure.
>
> Can anyone give me a guestimates of the time to break it by;
> (i.e. the maximum lifetime of any data encrypted with it)
>
> 1) the individual
>
> 2) the corperation
>
> 3) the government
Yes. I can give such estimates.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: the defintion of Entropy
Date: Thu, 29 Jul 1999 10:05:10 -0400
Keith A Monahan wrote:
> If that was an intuitive approach, I'd hate to see a non-intuitive approach.
>
> Keith
>
The non-intuitive approach is realy more non-intuitive :)
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Thu, 29 Jul 1999 10:08:51 -0400
Here is one of the first articles on the subject:
Brassard
A Note on the Complexity of Cryptography
IEEETIT: IEEE Transactions on Information Theory, Vol. 25, 1979.
Enjoy!
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Freeware version of PGP !!!
Date: Thu, 29 Jul 1999 08:33:28 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> That`s cool. What is twofish ? I mean... I know that it`s one of the AES
> candidates. But other than than I have no idea what it is. How does it
> compare it terms of speed and security to des, triple-des and idea.
In terms of speed, it's substantially faster than DES, (and therefore,
about three times that much faster than 3DES). Generally speaking,
IDEA and DES are _roughly_ the same speed, though this can vary
substantially, depending on the hardware you're using -- on low-end
hardware, IDEA doesn't (usually) slow down as much as DES. DES also
does a great deal better on hardware dedicated to the task rather than
on a general-purpose computer.
Even though that comparison of speed may seem a bit wishy-washy,
making definite statements about security is much more difficult --
some algorithms that looked like they should be extremely secure have
been found to be exactly the opposite.
Twofish has a larger key than DES, 3DES or IDEA, so if there's no
attack substantially better than brute-force, it's more secure than
any of them. IIRC, a few _minor_ shortcomings have been found in
Twofish that could, under limited circumstances, make an attack a
_little_ easier than brute-force, but most of these are pretty easy to
avoid. It has been designed specifically to resist most known styles
of attacks, such as differential and linear cryptanalysis.
OTOH, there's no method of proving the security of most encryption
algorithms. It's theoretically possible that somebody could find a
_really_ easy attack against any of these tomorrow. About all you can
point to in the opposite direction is the amount of time and effort
people have put into attacking an algorithm without being particularly
successful. In this area, DES is the obvious winner: it's been being
studied and attacked since long before any of the AES candidates even
existed. OTOH, DES is also known to be fairly easy to break by brute-
force. Twofish has the advantage of being similar enough to DES that
it benefits from the years of study on DES, but that's no guarantee
that in making it more difficult to attack in some (I.e. most known)
ways that it couldn't have been made easier (perhaps far easier) to
attack in others.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Thu, 29 Jul 1999 14:00:51 GMT
In article <7norar$[EMAIL PROTECTED]>,
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> Anton Stiglic <[EMAIL PROTECTED]> wrote:
>
> >jd_bertron wrote:
> >
> >> Has someone found a reduction of another NP-Complete problem to
> >> breaking RSA ?
> >
> >No, it is not NP-Complete. In fact, there is no crypto-system that
is
> >based on an NP-Complete problem.
Ah yes. More pearls of wisdom from someone who clearly does not
know the subject.
In fact there are several well known crypto systems (e.g. Chor-Rivest,
Ajtai-Dwork, and other knapsack related problems) that are known to be
NP-Complete.
Do us all a favor. Go study this subject for a few years before making
any more pronouncements.
Factoring, for example, is a
> >problem that is in a class a "little under" NP-Complete (I forgot the
> >name, sorry), and above P of cours (there might be other ways to
break
More ignorant prattle. The complexity of factoring is not known.
And I doubt that you even know what you mean when you say "a little
under NP-Complete and above P".
> >RSA than factoring, but that would just make RSA an "easier"
problem).
> >There is an article, in a recent Crypto or Eurocrypt, improving on
> >earlier results, that discusses this problem (there is something
about
> >the hierarchy collapsing if a cryptosystem problem would be NP-
Complete).
And the nonsense continues...
> Please do. I don't keep up with the literature as much as I ought...
Forget the literature. You don't even know the basics of the subject.
Stop posting nonsense.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Q: Does ElGamal require that (p-1)/2 is also prime like DH?
Date: Thu, 29 Jul 1999 10:22:25 -0400
David A Molnar wrote:
> Anton Stiglic <[EMAIL PROTECTED]> wrote:
> > anyways it is what is used). You then just test if p is in fact prime or
> > not,
> > this does not take much time (example, Miller Rabin prob. test algorithme
> > 4.24 in the Big Green book (Menezes, Oorschot, Vanstone)).
> > It is efficient, the probability of error reduces exponentialy with the
> > number
> > of rounds you execute the algo.
>
> This reminds me -- what do you think of the " construction of provable
> primes" algorithm due to Maurer in that book?
>
> Thanks,
> -David Molnar
I haven't looked into the specifis of the algo, but in general, I prefer
probable
primes over provable primes The error probability with Miller-Rabin is
(1/4)^t, for a sufficient t I would be very confident confident with it. You
can
get t such that the probability of error of the algo is smaller than the
probability
of the world exploding, I think thats good enaugh :) There is also always some
probability that your computer will not compute correctly, so there is always
some probability of error.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Q: Does ElGamal require that (p-1)/2 is also prime like DH?
Date: Thu, 29 Jul 1999 10:29:51 -0400
> I have to disagree. The following procedure
> constructs p = 2q + 1 where p and q are prime
> much faster.
>
> First, choose the range to search for p and q.
> Sieve out small prime factors from both the p
> range and q range. This way we only do further
> tests when we know that neither p nor q will
> have a small factor.
>
Of cours you can always test small numbers to make sure they
don't divide p, this just adds to the algo naturaly, it only
reduces it's complexity by a constant.
>
> To test a candidate that passes the sieve, do one
> iteration of a Fermat test on q with a base of 2.
> If it passes, do a base-2 Fermat test on p.
>
> Finally, do the iterated Miller-Rabin tests on q
> and p.
Again, you are adding a side-test. If you start spitting
out algos with to much details, you loose people. I feel
it's better to give the general idea, BEEING ABLE TO EXPLAIN IT,
then give references and leave the reader do the rest.
Anton
------------------------------
** 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
******************************
