Cryptography-Digest Digest #464, Volume #12 Thu, 17 Aug 00 01:13:00 EDT
Contents:
Re: New Stream Cipher like SEAL (Paul Rubin)
Re: 215 Hz five-qubit quantum processor (SCOTT19U.ZIP_GUY)
Re: books (Ernest Dumenigo)
Re: New Stream Cipher like SEAL ([EMAIL PROTECTED])
Re: New Stream Cipher like SEAL ([EMAIL PROTECTED])
Re: Funny Observation (John Savard)
Re: books ("John A. Malley")
Re: Funny Observation ([EMAIL PROTECTED])
Re: New Stream Cipher like SEAL (Paul Rubin)
Re: Big Brother Is Reading Your E-Mail (Michael Brown)
Re: 215 Hz five-qubit quantum processor ("Hank Oredson")
Re: New Stream Cipher like SEAL ([EMAIL PROTECTED])
Re: New Stream Cipher like SEAL (Paul Rubin)
Re: New Stream Cipher like SEAL ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: New Stream Cipher like SEAL
Date: 17 Aug 2000 02:10:45 GMT
In article <8nffb0$9vp$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>> This is unimpressive for a 32-bit stream cipher. I think you can get
>> more speed than that with 8-bit RC4. Do you have an estimated speed
>> for an asm implementation?
>
>It actually outputs 16 bytes at a time, but you can obviously just
>ignore the bytes you don't use.
>
>And I would think 22mb/sec is rather quick enough for a stream cipher.
>My HD only works at 5mb/sec anyways!!!
I just timed the OpenSSL implementation of RC4 on a PII-400 and it's
about 2x that fast (45 MB/sec). So even adjusting for clock speed and
the weird OpenSSL semi-asm RC4 implementation, the speeds are
comparable at best. I think SEAL is supposed to inherently be over 2x
as fast as RC4. So to win the speed race you need to get to the 7
cycles/byte range. Your HD speed isn't really relevant. Suppose you
want to run a VPN gateway with gigabit ethernet connections coming out
each end, and encrypt all the traffic. It would be great to be able
to do that with cheap hardware. This isn't computer science, it's the
real world. So speed counts!!! ;-)
>This is faster then Blowfish, RC5, IDEA, etc...
I think Blowfish can run at around 18 cycles/byte, so 15 cycles/byte
isn't much of an improvement. I don't know (or care) much about RC5
and IDEA, which are patented.
>I dunno if in ASM it would be terribly faster. I haven't tried yet
>though, maybe it could be shaved down a few cycles.
I'd be interested to see what you can do.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 17 Aug 2000 02:19:58 GMT
[EMAIL PROTECTED] (Steve Newman) wrote in <snewman-
[EMAIL PROTECTED]>:
>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>(SCOTT19U.ZIP_GUY) wrote:
>
>> [EMAIL PROTECTED] (Steve Newman) wrote in <snewman-
>> [EMAIL PROTECTED]>:
>>
>> >...
>> >
>> >Oh, well. Then my brilliant idea for the ultimate compression
>> >algorithm is probably no good either. (Generate all possible
>> >bitstrings, select the ones that when executed on a virtuam machine
>> >interpreter generate the uncompressed file as output, and keep the
>> >shortest such bitstring.) This one is actually even worse than the
>> >theorem-proving algorithm because it requires interpreting (executing)
>> >each bitstring, not just running it through a proof checker.
>>
>> Any method of full finite file transforms that leave no gaps
>> are already perfect compressors. In the sense that they make
>> maximum use of the file space. MY huffman coders and Matt Arithmetic
>> coder are examples of perfect compression. One test of perfect
>> compression is that for any file A = uncompress ( compress ( A ))
>> and A = compress ( uncompress ( A))
>
>This is true in an information-theoretic sense. However, it's not
>all that meaningful in a practical sense. For example, gzip yields
>smaller compressed files than a simple Huffman encoder in almost all
>typical usage. (Otherwise gzip would have been written to do simple
>Huffman coding.)
>
>What this points out is that the "best compression algorithm" is
>undefinable in theory, but definable (to some extent) in practice --
>the quality of a compression algorithm depends on what sort of files
>you're likely to throw at it.
I think ther are 2 measures of quality in a compressor
1) Is how small it compresses commonly used files.
2) Is how completely it uses that compressed file space.
By number 2 I mean what percent of files below a certain
length could be thought as compressed files. With gzip there
are very few files that are really compressed files so it
can't be to good.
With either my adaptive huffmna compressor or Matts Arithmetic
compressor any file can be thought of as a compressed file
so in some sense of the word they are perfect compressors
and if would be impossible for a quantum computer to use
information added to a file that was compressed and encrypted.
With a gzip compression it could find the file having ZERO
information about the file other than what it was compressed
with.
>
>-- Steve Newman
>
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction
of the truth."
------------------------------
From: [EMAIL PROTECTED] (Ernest Dumenigo)
Subject: Re: books
Date: 17 Aug 2000 02:39:10 GMT
James Pate Williams, Jr. ([EMAIL PROTECTED]) wrote:
: On 16 Aug 2000 21:30:45 GMT, [EMAIL PROTECTED] (Ernest Dumenigo)
: wrote:
: >I have just finished "The codebreakers", and wanted to know what everyone
: >felt should be the next books I should get to learn more.
: >Thanks
: >--
: >-----
: >Ernest
: Are you interested in the theory of cryptography and cryptanalysis or
: its history?
Both! I have gotten quit interested while reading codebreakers, and by luck
there was a special on PBS about Bletchley park!! I do have a copy of the
refrences in the faq, so any suggestions on which books I should start
off with would be much appriciated.
--
=====
Ernest
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 02:54:54 GMT
In article <8nfhj5$k3s$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Rubin) wrote:
> In article <8nffb0$9vp$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >> This is unimpressive for a 32-bit stream cipher. I think you can
get
> >> more speed than that with 8-bit RC4. Do you have an estimated
speed
> >> for an asm implementation?
> >
> >It actually outputs 16 bytes at a time, but you can obviously just
> >ignore the bytes you don't use.
> >
> >And I would think 22mb/sec is rather quick enough for a stream
cipher.
> >My HD only works at 5mb/sec anyways!!!
>
> I just timed the OpenSSL implementation of RC4 on a PII-400 and it's
> about 2x that fast (45 MB/sec). So even adjusting for clock speed and
> the weird OpenSSL semi-asm RC4 implementation, the speeds are
> comparable at best. I think SEAL is supposed to inherently be over 2x
> as fast as RC4. So to win the speed race you need to get to the 7
> cycles/byte range. Your HD speed isn't really relevant. Suppose you
> want to run a VPN gateway with gigabit ethernet connections coming out
> each end, and encrypt all the traffic. It would be great to be able
> to do that with cheap hardware. This isn't computer science, it's the
> real world. So speed counts!!! ;-)
>
> >This is faster then Blowfish, RC5, IDEA, etc...
>
> I think Blowfish can run at around 18 cycles/byte, so 15 cycles/byte
> isn't much of an improvement. I don't know (or care) much about RC5
> and IDEA, which are patented.
>
> >I dunno if in ASM it would be terribly faster. I haven't tried yet
> >though, maybe it could be shaved down a few cycles.
>
> I'd be interested to see what you can do.
I would be interested in security related comments before investing too
much time doing a asm coded version.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 03:04:13 GMT
... I forgot to mention ...
In article <8nfhj5$k3s$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Rubin) wrote:
> In article <8nffb0$9vp$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >> This is unimpressive for a 32-bit stream cipher. I think you can
get
> >> more speed than that with 8-bit RC4. Do you have an estimated
speed
> >> for an asm implementation?
> >
> >It actually outputs 16 bytes at a time, but you can obviously just
> >ignore the bytes you don't use.
> >
> >And I would think 22mb/sec is rather quick enough for a stream
cipher.
> >My HD only works at 5mb/sec anyways!!!
>
> I just timed the OpenSSL implementation of RC4 on a PII-400 and it's
> about 2x that fast (45 MB/sec). So even adjusting for clock speed and
> the weird OpenSSL semi-asm RC4 implementation, the speeds are
> comparable at best. I think SEAL is supposed to inherently be over 2x
> as fast as RC4. So to win the speed race you need to get to the 7
> cycles/byte range. Your HD speed isn't really relevant. Suppose you
> want to run a VPN gateway with gigabit ethernet connections coming out
> each end, and encrypt all the traffic. It would be great to be able
> to do that with cheap hardware. This isn't computer science, it's the
> real world. So speed counts!!! ;-)
Yea I would actually like to see that SEAL code that runs at 4
cycles/byte. That seems amazing at best to me.
> >This is faster then Blowfish, RC5, IDEA, etc...
>
> I think Blowfish can run at around 18 cycles/byte, so 15 cycles/byte
> isn't much of an improvement. I don't know (or care) much about RC5
> and IDEA, which are patented.
Yes, but my code in C runs faster then Blowfish in hand optimized asm.
I have not done too much super optimizations (only the RC5 code on my
site). Also SC1 involves quite a bit of shifts and rotates so I doubt
ASM code would get much better... perhaps in the 7 cycle range.
I would encourage anyone with a talent for ASM code to try it out, I
would seriously appreciate any tips on writing it,etc..
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Funny Observation
Date: Thu, 17 Aug 2000 03:27:43 GMT
On Wed, 16 Aug 2000 20:02:06 GMT, [EMAIL PROTECTED] wrote, in part:
>Anyone ever notice that Dave Scott calls himself the 'Zip Guy' but
>known of his software involves the deflate algorithm.
Ah, but what he calls (called?) himself the "Scott19u_zip" guy, and
his encryption package, no doubt, _is_ distributed in a file
compressed in the .ZIP format.
That, for encryption, he prefers adaptive arithmetic compression to
Lempel-Ziv is one thing I _don't_ fault him for, I think his judgement
is correct on that.
My own tastes run towards having a compressor with canned starting
information for various types of file. For text files, I would use a
multi-state Huffman, with one state containing symbols for word
lengths - and a _word_ dictionary maintained on Lempel-Ziv principles.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: books
Date: Wed, 16 Aug 2000 20:54:15 -0700
Might I suggest
"Cryptography, Theory and Practice" by Douglas R. Stinson,
"Decrypted Secrets, Methods and Maxims of Cryptology" by F.L. Bauer,
"Cryptanalysis, A Study of Ciphers and Their Solution" by Helen Fouche
Gaines,
"Applied Cryptography, Protocols Algorithms and Source Code in C" by
Bruce Schneier,
and either "Military Cryptanalysis Parts I, II, III and IV" by William
F. Friedman
or
"Military Cryptanalytics, Part I, Vol. 1 and 2, and Part II, Vol. 1 and
2 " by
William F. Friedman and L.D. Callimahos
as a good start.
(IMHO everything on cryptology from Aegean Park Press is worth reading,
not just those last two entries in the list.)
Any of these books are available from Barnes and Noble (bn.com) or
Amazon.com.
Aegean Park Press has its own web site at http://www.aegeanparkpress.com
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Funny Observation
Date: Thu, 17 Aug 2000 04:00:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> On Wed, 16 Aug 2000 20:02:06 GMT, [EMAIL PROTECTED] wrote, in part:
>
> >Anyone ever notice that Dave Scott calls himself the 'Zip Guy' but
> >known of his software involves the deflate algorithm.
>
> Ah, but what he calls (called?) himself the "Scott19u_zip" guy, and
> his encryption package, no doubt, _is_ distributed in a file
> compressed in the .ZIP format.
>
> That, for encryption, he prefers adaptive arithmetic compression to
> Lempel-Ziv is one thing I _don't_ fault him for, I think his judgement
> is correct on that.
>
> My own tastes run towards having a compressor with canned starting
> information for various types of file. For text files, I would use a
> multi-state Huffman, with one state containing symbols for word
> lengths - and a _word_ dictionary maintained on Lempel-Ziv principles.
it's really hard to say huffman is better then zip (deflate) since
deflate includes huffman as part of the codec.
I can't fathom why he believes huffman or arith alone is better then
deflate. I really would like to see him find typical files that
compress better with his methods then deflate.
Also time and time again I repeat that smaller files means less WASTED
SPACE. Which means the entropy per bit is higher (closer to one) then
with the other methods. Doesn't that make sense?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: New Stream Cipher like SEAL
Date: 17 Aug 2000 04:09:24 GMT
In article <8nfk5n$f5o$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>I would be interested in security related comments before investing too
>much time doing a asm coded version.
There's kind of a chicken and egg problem here. Those who might be
interested in using the cipher, want to know that there's some reason
to use it (i.e. that it outperforms existing ciphers) assuming that
it's secure, before wanting to invest time studying its security.
Reasonable compromise: instead of actually coding, debugging, and
measuring an asm implementation, can you make a semi-careful estimate
based on the algorithm, of the number of cycles needed?
------------------------------
From: Michael Brown <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.security.pgp
Subject: Re: Big Brother Is Reading Your E-Mail
Date: Thu, 17 Aug 2000 16:30:42 +1200
> Well, you are trying to reverse the Wallace-tree adder scheme. Are you
> willing to give only a describtion of this process in your future document,
> or will you also suply us with some analysis from mathematical point of
> view - the estimated complexity as a function of the bitlength and
> properties of factors? Otherwise your method will forever stay only in the
> position of nice logic-based game.
>
> good luck (you will need it, because it could be expected you will run into
> the trubble, soon)
> Tom
Unfortunatly, I just don't have any idea where to start with making a
complexity function. The complexity, as far as I can tell, is based
directly (and only) on the nuber of identical bits in the two source
prime numbers. After the first digit that is not identical for both the
input primes has been found, the rest is relatively easy. There would
be, of course, more boxes to fill in (and there is a formula for this),
but the algebra for finding the "different" bit will probably take up a
majority of the time for any factorisation (and I don't have a formula
for the amount of algebra required). Also, I don't know whether it grows
exponentially or in a linear fashon.
The only thing the document I'm writing at the moment does is get around
the problem when the primes are identical at bit 1, but I'll look at
trying to get a bit more info on the complexity.
As for the problems, each one I discover has been harder than the last.
Hopefully there are not too many more ...
Michael
PS: Do you have a Excel to PDF distiller? The other Tom can't read XL
files, and Excel is <hopeless> at exporting to HTML!
------------------------------
From: "Hank Oredson" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: Thu, 17 Aug 2000 04:27:54 GMT
What a mess. Coffee all over everything.
Please Andy, some WARNING ... like "Place coffee firmly on
desk before reading this post." Maybe a new mail header?
--
... Hank
http://horedson.home.att.net
"Andy Newman" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Jamie wrote:
> >Isn't MS Windows a simulation of a quantum machine?
> >You can never tell which application the "operating system" is going to
> >crash until you try to use it.
>
> They well may be using such techniques. Do not under estimate
> the capabilities of this giant among giants (ahem).
>
> For years we've maligned Bill Gates and Co (capital intended) for
> poor s/w but we all mis-understood Microsoft's grand plan. It all
> suddenly became clear the other day - in the bathroom or somewhere
> like that, the place such grand plans always become clear...
>
> Microsoft's software has been all about proving there is an efficient
> solution to the halting problem!
<snippage>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 04:43:34 GMT
In article <8nfohk$hpu$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Rubin) wrote:
> In article <8nfk5n$f5o$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >I would be interested in security related comments before investing
too
> >much time doing a asm coded version.
>
> There's kind of a chicken and egg problem here. Those who might be
> interested in using the cipher, want to know that there's some reason
> to use it (i.e. that it outperforms existing ciphers) assuming that
> it's secure, before wanting to invest time studying its security.
>
> Reasonable compromise: instead of actually coding, debugging, and
> measuring an asm implementation, can you make a semi-careful estimate
> based on the algorithm, of the number of cycles needed?
Well the inner loop has four data dependant rotations, four xor's, four
additions, four and's and four lookups. There are four iterations per
output so we know there are
16 x XOR, 16 x ADD, 16 x AND, 16 x LUT, 16 x ROL
Which for the first three are at best 1 cycle each, for 48 cycles to
begin with. Then 16 Luts will take 1-2 cycles each for about 24 cycles
(say avg), and finally the rotates are 2 cycles I believe each.
So in theory the best this could be done in is about 48+24+32=104
cycles per 16 bytes or 6.5 cycles per byte. I have no clue at this
moment how todo this, sorry. Assuming there will be some stalls I bet
around 10 cycles per byte (160 cycles total) will be the best
possible. Which in all accounts is still pretty fast.
Oh yeah forgot the adds in the end to create the output... so add in
four ADDS to the count...
Advantages over SEAL:
1. Free.
2. Easier to understand.
3. Uses less memory
Disadvantages:
1. Slightly Slower
2. Not as analyzed.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: New Stream Cipher like SEAL
Date: 17 Aug 2000 04:49:52 GMT
In article <8nfkn5$fq3$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Yea I would actually like to see that SEAL code that runs at 4
>cycles/byte. That seems amazing at best to me.
Since SEAL operates on 32-bit words, to get 4 cycles/byte it has to
generate an output word in 16 cycles. RC4 generates an output byte in
about 8 cycles (Pentium II) so SEAL has enough cycles to do about
twice as many instructions per iteration as RC4. This doesn't seem
all that amazing. It then gets 4 bytes at a time out instead of one.
>Yes, but my code in C runs faster then Blowfish in hand optimized asm.
Good point...
>I have not done too much super optimizations (only the RC5 code on my
>site). Also SC1 involves quite a bit of shifts and rotates so I doubt
>ASM code would get much better... perhaps in the 7 cycle range.
Yes, looking at the algorithm I can believe that.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Stream Cipher like SEAL
Date: Thu, 17 Aug 2000 04:51:43 GMT
Actually there are
16 xors, 16 ands, 24 adds, 16 luts, 16 shrs and 16 rols
Giving the best theoretical as
shr, and, add, xor = 1 cycle
luts = 2 cycles
rols = 2 cycles
For a total of (56x1) + (16)(2) + (16)(2) = 120 cycles minimum. Plus
pointer management we are talking about 160 or more cycles.
Personally I think DJGPP did an awesome job optimizating the code.
DJGPP got about 240 cycles per block which is about double the
theoretical max. I doubt any ASM version will be substantially faster
though.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
