Cryptography-Digest Digest #495, Volume #12 Mon, 21 Aug 00 10:13:01 EDT
Contents:
Re: OTP using BBS generator? (Mark Wooding)
Re: CRC? ("Z")
Re: OTP using BBS generator? (Mark Wooding)
Re: How many bits of strength does the ZIP encryption have? ("Vladimir Katalov")
Re: DES: Say it or spell it? (Newbie question) (Alan Braggins)
Re: Lehmann Primality Test (Mark Wooding)
Re: Question on Decorelation Theory ([EMAIL PROTECTED])
Re: How many bits of strength does the ZIP encryption have? (JPeschel)
Re: pRNG, ECC and block modes (Mark Wooding)
Re: blowfish problem ("Trevor L. Jackson, III")
Random Number Generator ([EMAIL PROTECTED])
Re: Random Number Generator ([EMAIL PROTECTED])
Re: Lehmann Primality Test (Bob Silverman)
Re: Lehmann Primality Test (Bob Silverman)
Simple cipher based on SHA-1 (Janne Tuukkanen)
Re: Lehmann Primality Test (Mack)
Re: CRC? (Mack)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 21 Aug 2000 09:35:16 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Tim Tyler wrote:
> >
> > I for one don't see how the nature of the BBS modulus might help prevent
> > cycles in the low bits.
You missed the bit where I explained exactly how the nature of the BBS
modulus can prevent short cycles in the parity bit. Remember that the
cycle length of the parity bits must be a factor of the cycle length for
the residue sequence, which in turn we know to be a factor of \pimax =
\lambda(\lambda(n)). By choosing n appropriately, we can ensure that
\pimax is twice the product of some large primes (larger than some
chosen bound t). Then, by rejecting a seed which leads to a cycle of
length 2, we know that the parity cycle length must be at least t.
> BBS states only that the cycle length of LSB must divide the first
> mentioned cycle length
I don't recall that it actually mentions this. It is an obvious
consequence, though.
-- [mdw]
------------------------------
From: "Z" <[EMAIL PROTECTED]>
Crossposted-To: alt.msdos.programmer,comp.lang.c,comp.lang.c++,comp.os.msdos.programmer
Subject: Re: CRC?
Date: Mon, 21 Aug 2000 12:03:55 +0100
Once upon a while in a tremendously nice article <8npvk4$m4l$[EMAIL PROTECTED]>,
Mario Tonni <[EMAIL PROTECTED]> wrote:
>
>
> Hi there.
> Often I hear the term "CRC", which I know that means
> "cyclic redundancy check".
>
> What I wonder instead is if CRC's are error-recovering
> methods, or simply a more reliable way to calculate a
> checksum?
>
> If so, could anybody provide me a C code to calculate the
> 32 (or better 64) bits CRC?
>
> I know that checksums are simply a serie of ADD or XOR
> on all your data.. but CRC (in case it's not a more
> sophisticated error-recovering scheme, as the ones used
> e.g. on Compact Discs) seems more complicated to calculate
> than checksums, could anybody help, please?
>
> Thanks!
> Mario
A simple web search will hit you the document
_A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS_
which is a painless guide to crc error detection algorithms :-)
and explains the items arround it pretty good.
Z
--
LISP is worth learning for the profound enlightenment experience you
will have when you finally get it; that experience will make you a
better programmer for the rest of your days. Eric S. Raymond
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 21 Aug 2000 10:07:09 GMT
D. J. Bernstein <[EMAIL PROTECTED]> wrote:
> Consider, for example, the Alexi-Chor-Goldreich-Schnorr theorem, which
> tells you how to factor N using 10^54 (lg N)^3 applications of an
> algorithm that has a 1/1000 chance of seeing a pattern in a billion bits
> produced by a BBS generator mod N. The theorem doesn't say that
> predicting the generator is as hard as factoring N; it allows a ratio of
> speeds as large as 10^54 (lg N)^3.
Is this a hard upper bound on the potential silliness (degree, size of
coefficients) of the polynomial relationship between factoring time and
prediction difficulty? If not, I think I'll claim that the proofs
aren't actually very useful in practice anyway.
Oh, do you have a pointer to Alexi-Chor-Goldreich-Schnorr?
-- [mdw]
------------------------------
From: "Vladimir Katalov" <[EMAIL PROTECTED]>
Subject: Re: How many bits of strength does the ZIP encryption have?
Date: Mon, 21 Aug 2000 14:08:10 +0400
JPeschel wrote in message <[EMAIL PROTECTED]>...
>[EMAIL PROTECTED] writes:
>
>>If, for instance, the archive consisted of .jpg files could one use the
.jpg
>>header information as plaintext somehow?
>
>Yes, but, as Conrad (the Pkcrack author) notes, you need
>to know "a reasonably long header." If the plaintext is less
>than 100 bytes, Pkcrack, Conrad says, will probably take a
>lot longer than an hour to crack a file.
Sorry, but it is not true. First, you have to know 12 bytes of *compressed*
stream, or much longer text from the original file (so first 12 bytes in
compressed file will be the same). Just try to compare two .jpg files
and look at the resulting files -- they'll be completely different (if, of
course, the compression method is not "storing").
Second, I don't know what you mean by "a lot longer", but actually you
need only about 2 days in the worst case (when 12 bytes are known).
--
Sincerely yours,
Vladimir
Vladimir Katalov
Managing Director
Elcom Ltd.
Member of Association of Shareware Professionals (ASP)
Member of Russian Cryptology Association
mailto:[EMAIL PROTECTED]
http://www.elcomsoft.com/adc.html (Advanced Disk Catalog)
http://www.elcomsoft.com/ems.html (Email Management Software)
http://www.elcomsoft.com/prs.html (Password Recovery Software)
------------------------------
From: Alan Braggins <[EMAIL PROTECTED]>
Subject: Re: DES: Say it or spell it? (Newbie question)
Date: 21 Aug 2000 11:41:02 +0100
"Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
> abbrevation for EXclusive-OR. (DES on the other hand is
> a pure acronym and thus by conventional English rules
> is pronounced as the sequence of individual letters.)
The whole point of an acronym is that it can be pronounced
as a word (e.g. laser, scuba).
http://www.m-w.com/cgi-bin/dictionary?acronym
"a word (as NATO, radar, or snafu) formed from the initial letter or
letters of each of the successive parts or major parts of a compound
term."
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Lehmann Primality Test
Date: 21 Aug 2000 10:46:59 GMT
Mack <[EMAIL PROTECTED]> wrote:
> venture a guess. The theory says that RM is wrong no more than 1/4 of
> the time. Empirical evidence says that it is wrong only 1/10^22 of
> the time or less.
You're confused about your conditional probabilities. Compare and
contrast:
* the probability that, given a composite number, the Rabin-Miller
test will erroneously report it as being prime; and
* the probability that, given a random number which the Rabin-Miller
test reports as being prime, it's really composite.
The latter probability is much lower than the former.
> Of course if you are worried about carmicheal numbers don't use
> a probabilistic test.
There is no class of numbers which fool the Rabin-Miller test in the
same way as Carmichael numbers fool the Fermat test.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Question on Decorelation Theory
Date: Mon, 21 Aug 2000 10:44:18 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> [EMAIL PROTECTED] wrote:
> >
>
> > In the paper "Provably Security for Block Ciphers by Decorrelation"
by
> > Serge Vaudenay. Page 5, Section 2 "Basic Constructions" and I quote
>
> Could you also give the name of the journal? Thanks.
I don't know. But you could I dunno, possibly LOOK HIM UP ON THE WEB!
Goto the DFC page and you can find his stuff from their, or goto the
researches part on Counterpane and look up Serge Vaudenay.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: How many bits of strength does the ZIP encryption have?
Date: 21 Aug 2000 10:58:17 GMT
"Vladimir Katalov" [EMAIL PROTECTED] writes:
>JPeschel wrote in message <[EMAIL PROTECTED]>...
>>[EMAIL PROTECTED] writes:
>>
>>>If, for instance, the archive consisted of .jpg files could one use the
>.jpg
>>>header information as plaintext somehow?
>>
>>Yes, but, as Conrad (the Pkcrack author) notes, you need
>>to know "a reasonably long header." If the plaintext is less
>>than 100 bytes, Pkcrack, Conrad says, will probably take a
>>lot longer than an hour to crack a file.
>
>
>Sorry, but it is not true. First, you have to know 12 bytes of *compressed*
>stream, or much longer text from the original file (so first 12 bytes in
>compressed file will be the same). Just try to compare two .jpg files
>and look at the resulting files -- they'll be completely different (if, of
>course, the compression method is not "storing").
>
Of course.
I was quoting from Conrad's Pkcrack readme file. If Seeker
is going to use pkcrack, he needs to read the entire readme file.
>Second, I don't know what you mean by "a lot longer", but actually you
>need only about 2 days in the worst case (when 12 bytes are known).
>
>
Actually, you'll have to ask Peter what he means by "a lot longer," as I was
quoting
him, but, I'd say two days is a lot longer.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: pRNG, ECC and block modes
Date: 21 Aug 2000 11:10:38 GMT
Rich <[EMAIL PROTECTED]> wrote:
> Hello group, as a long-time lurker I've learned quite a lot and very
> much appreciate all the discussions. I now have a few questions, which
> I hope you folks can weigh in on. There are as follows:
>
> 1. Which pseudo-random-number-generator is the "Best"?: Yarrow; Blum-Blum-
> Shub; Micali-Schnorr or Wichmann-Hill?
Which is better, an apple, or a JCB digger?
BBS is a deterministic PRNG; Yarrow is an entropy-distilling generator
designed to be used to obtain `true' random data if fed enough
unpredictable input.
> 2. Which one-way hash is the "Best"?: Havel; SHA-2; DHA; Tiger;
> Ripemd-160; Blum-Blum-Shub; Meyer-Davis; or GOST 34.11-94?
BBS isn't a hash. SHA-2 isn't published. I've not come across DHA.
I'd rather not go near Davis-Meyer (the key schedule requirements on the
underlying block cipher are *amazingly* strict); I'm not impressed by
GOST. I like Tiger and RIPEMD-160 more than SHA-1.
> 3. Which Message Authentication Cert. is the "Best"?: H-MAC or D-MAC?
D-MAC isn't one I've seen. HMAC has a tight security reduction to a
well-defined and important security property of the underying hash
function. It's my choice.
> 4. Which Error-Correction Code is the "Best"?: Turbo Codes; binary
> Goppa or Viterbi?
Wrong place for this question.
> And, finally: 5. Which block-cipher mode is "Best"?: CBC w/CTS or Counter-
> based CTR?
Depends.
Try asking a sensible question next time.
-- [mdw]
------------------------------
Date: Mon, 21 Aug 2000 08:53:46 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.c
Subject: Re: blowfish problem
Richard Heathfield wrote:
> "Trevor L. Jackson, III" wrote:
> >
> > Gergo Barany wrote:
> >
> > > Daniel Leonard <[EMAIL PROTECTED]> wrote:
> > > > I do not want to be rude, but there are some "errors" in your code.
> > >
> > > I do not want to be rude, but your news software posts in some
> > > funky "Quoted-Printable" encoding. It makes your posts hard to read
> > > because it replaces many characters such as '=' with a code like
> > > "=<hex>", where <hex> is a character's ASCII code in hexadecimal.
> > > This stinks, please turn it off.
> > >
> > > > On 17 Aug 2000, John Hascall wrote:
> > > > > =09out =3D malloc(inLen * 2 + 1);
> > > >
> > > > shouldn't it be:
> > > > out =3D malloc((inLen * 2 + 1) * sizeof(char));
> > > > /* a char could be more than 1 byte */
> > >
> > > No, a char is always one byte in C.
> >
> > No it's not. A character is the minimum unit of addressability, which may be
> > other than a byte. Espcially on older machines, making this assumption is an
> > error.
> Not if you're writing in ISO C, which is the topic of comp.lang.c.
<pedantic>
I rarely read clc, but even in my infrequent visits I've noted a variety of
languages discussed. The forum description may limit the context to ISO C, but the
practice in clc indicates otherwise. Now if you want to advocate the creation of
comp.lang.iso-c I wouldn't object.
</pedantic>
>
>
> This is a cross-posting issue. The ISO C Standard defines the language
> as far as comp.lang.c is concerned, and that is whence Gergo's point of
> view springs.
Grok.
Problem is that the standard is supposed to define _the_ language, but any
individual user ends up with _a_ language. And there are multiple ISO C
standards. Is it your position that programs written in compliance with C89 are
not C?
>
>
> I suggest that, for the sake of peace, harmony, and love between
> sci.crypt and comp.lang.c, we agree to differ on this point.
Sure.
------------------------------
From: [EMAIL PROTECTED]
Subject: Random Number Generator
Date: Mon, 21 Aug 2000 13:06:02 GMT
New feature
Objective of this feature is to make bit permutation
table dependent on overflow bytes which are lost in
multiplication operations. Each two bytes perform
transposition over PermTab in a way , which makes it
to a new bit permutation table. This make bit permutation
table also one way unpredictable.
Updated Delphi/Java source code can be found at
www.alex-encryption.de
Regards.
Alex.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random Number Generator
Date: Mon, 21 Aug 2000 13:25:12 GMT
In article <8nr9fe$8hu$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> New feature
> Objective of this feature is to make bit permutation
> table dependent on overflow bytes which are lost in
> multiplication operations. Each two bytes perform
> transposition over PermTab in a way , which makes it
> to a new bit permutation table. This make bit permutation
> table also one way unpredictable.
We normally call "bit permutation table" an "sbox" and transposing
elements (a.k.a swapping) of a fixed finite permutation is nothing new.
The new permutation will be random iff the two multiplicands are
random. How are you making them?
BTW "unpredictable" does not apply since given the same multiplicands I
can recreate the sboxes.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Lehmann Primality Test
Date: Mon, 21 Aug 2000 13:30:33 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (ChenNelson) wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Does anyone know the actual average fraction of composites that will
> falsely indicate "prime" with the Lehmann primality test?
>
> Lehmann test: take a random a, compute a^((p-1)/2) mod p. If that
> value is 1 or p-1, then output "prime."
>
> I know the theoretical *upper* limit is 1/2,
This is the worst case.
> but a few trial runs on
> my computer seem to indicate an average value much lower than this.
<snip>
The average, in the sense you ask, does not exist. The asymptotic
average is 0, however. That is, let c(n) denote the number of
Lehmann false witnesses to an integer n. Then we have
lim n-->oo 1/n * sum(i = 1 to n of c(n)) = 0.
As the numbers n get larger, the probability that any given integer
is a false witness (assuming n is composite) goes to 0.
See, for example,
Kim & Pomerance
The probability that a random probable prime is composite
Math. COmp. Vol 53, 1989
--
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/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Lehmann Primality Test
Date: Mon, 21 Aug 2000 13:33:39 GMT
In article <8nq397$v4a$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> >
> > Does anyone know the actual average fraction of composites that will
> > falsely indicate "prime" with the Lehmann primality test?
> >
> > Lehmann test: take a random a, compute a^((p-1)/2) mod p. If that
> > value is 1 or p-1, then output "prime."
> >
> > I know the theoretical *upper* limit is 1/2, but a few trial runs on
> > my computer seem to indicate an average value much lower than this.
>
> if 'p' is prime then a^(p-1) mod p will be 1. This is a similar test
> (actually the same test). This is also a variation of Fermats theorem
> and not very reliable.
You know, Tom, one of these days you might stop posting misinformation.
But I tend to doubt it.
The test is *very* reliable for even moderately sized integers.
See the Kim & Pomerance paper that I already quoted.
--
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/
Before you buy.
------------------------------
From: Janne Tuukkanen <[EMAIL PROTECTED]>
Subject: Simple cipher based on SHA-1
Date: Mon, 21 Aug 2000 16:30:41 +0300
I'm newbie on the field, so be patient ;-)
Is this worth anything:
160 bit key is created from pass phrase using SHA-1.
First 64 (or what ever) bits of plaintext are XORed with
(say for instance least significant) 64 bits from the key.
The 64 bits used from the key are replaced by the
ciphered 64 bits.
New key is produced for the next block from the key using SHA-1.
And so on...
If the key is understood as 'state', there should always be
at least 96 secret bits in it, and recovery of those even
when there is known plaintext should be somewhat difficult.
Other hand the ciphered 8 bytes are used for the next hash, so
other documents ciphered with the same key could not be
opened when the first one's plaintext is known.
Ok, I believe this is somewhat weak (and I hope someone will
gently point me the principles of the weaknesses of the algorithm),
but _how_ weak? If we are living in the world of 1GHz PIII's, what
kind of time scale it would take to break this (msecs? secs? hours?
days? weeks? ...)
JanneT
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 21 Aug 2000 14:02:24 GMT
Subject: Re: Lehmann Primality Test
>Mack <[EMAIL PROTECTED]> wrote:
>
>> venture a guess. The theory says that RM is wrong no more than 1/4 of
>> the time. Empirical evidence says that it is wrong only 1/10^22 of
>> the time or less.
>
>You're confused about your conditional probabilities. Compare and
>contrast:
>
> * the probability that, given a composite number, the Rabin-Miller
> test will erroneously report it as being prime; and
>
> * the probability that, given a random number which the Rabin-Miller
> test reports as being prime, it's really composite.
The 1/4 probability is for a worst case number ie. the number of
witnesses that will test the number as composite.
The latter probability is the empirical evidence of the second case.
>
>The latter probability is much lower than the former.
>
>> Of course if you are worried about carmicheal numbers don't use
>> a probabilistic test.
>
>There is no class of numbers which fool the Rabin-Miller test in the
>same way as Carmichael numbers fool the Fermat test.
The RM test has a set of numbers which have bad behavior. I should
have said strong pseudoprimes. You are correct.
>
>-- [mdw]
>
>
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 21 Aug 2000 14:08:23 GMT
Subject: Re: CRC?
><<What I wonder instead is if CRC's are error-recovering
>methods, or simply a more reliable way to calculate a
>checksum?
>
>If so, could anybody provide me a C code to calculate the
>32 (or better 64) bits CRC?>>
>
>I much prefer the SHA-1 algorithm for error detection. It absolutely
>guarantees error detection if you use the full 160 bits, and even 64 bits of
>output is quite strong. And the best part is that it makes sense.
For full 160bit SHA-1 will beat out a 64 bit CRC for correction rate
but lose badly on speed. When only using 64 bits of SHA-1 it will
lose badly on both. It isn't designed for it. It is easy to find strings
that match for a CRC but none will differ in certain ways that
are representative of communication errors. ie. burst errors.
>
>-*---*-------
>S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
>My upgraded Book Reviews Page: * http://sciencebook.cjb.net *
>Optimized pngcrush executable now on my Download page!
>Long live pngcrush! :->
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
** 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
******************************
