Cryptography-Digest Digest #202, Volume #12 Tue, 11 Jul 00 11:13:01 EDT
Contents:
Re: Quantum Computing (Was: Newbie question about factoring) (ca314159)
Re: Proposal of some processor instructions for cryptographical applications ("Scott
Fluhrer")
Re: Elliptic Curves encryption (DJohn37050)
Re: Proposal of some processor instructions for cryptographical applications (John
Savard)
Re: Proposal of some processor instructions for cryptographical applications (John
Savard)
Re: Random Numbers ("Tony T. Warnock")
Re: Advanced Cryptography FAQ (Guy Macon)
Re: Proposal of some processor instructions for cryptographical (Terje Mathisen)
Re: IDEA CBC ("Sam Simpson")
Re: One plaintext, multiple keys (Guy Macon)
Re: RC4 question (Guy Macon)
Re: Who was that girl? (John Bailey)
Re: Random Numbers (Guy Macon)
Re: Random Numbers (Guy Macon)
Re: Random Numbers (Guy Macon)
Re: Random Numbers (Herman Rubin)
----------------------------------------------------------------------------
From: ca314159 <[EMAIL PROTECTED]>
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: Tue, 11 Jul 2000 13:01:10 GMT
In article <8kf0e7$7bd$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Nick Maclaren) wrote:
>
> In article <8kcqbk$p93$[EMAIL PROTECTED]>, Bob Silverman
<[EMAIL PROTECTED]> writes:
> |> In article <[EMAIL PROTECTED]>,
> |> [EMAIL PROTECTED] wrote:
> |> > Jeff Erickson wrote:
> |> >
> |> > > ca314159 <[EMAIL PROTECTED]> writes:
> |> > > | D. Mermin poses a useful problem for only one qubit:
> |> > > | to determin the millionth bit of the binary expansion
> |> > > | of sqrt(2+x). That would be big news.
> |> > >
> |> > > Hardly. Given the recent computation of the trillionth(!) bit
of pi
> |> > > using classical computers, why should anyone think computing
bits of
> |> > > sqrt(2+x) is hard?
> |> >
> |> > I'm going to guess that it's much harder to compute the bits of
an
> |> algebraic
> |> > number than the bits of Pi or or some other transcendentals.
> |>
> |> No. It is because an algorithm by Simon Plouffe allows computation
> |> of the k'th bit of Pi **without** having to compute the 1...k-1
> |> bits.
>
> Whereas effective ways to do similar things for sqrt(2+x) have been
> known for centuries ....
>
> One reason that nobody is very interested in calculating the digits
> of sqrt(2+x) is that it is so easy - the other is that the properties
> of sqrt(2) are well-understood compared with those of pi.
>
> Regards,
> Nick Maclaren,
> University of Cambridge Computing Service,
> New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
> Email: [EMAIL PROTECTED]
> Tel.: +44 1223 334761 Fax: +44 1223 334679
>
Has anyone done anything interesting with even a single qubit ?
It matters little whether this problem is easy or hard,
it just happened to be one which seemed a suitable
problem for a quantum computer.
The un-conscience (the "un-measurable") is a terrible thing to waste.
It can be your best singular friend if greeted, or your worst myraid
nightmares if repressed.
As a single serial real saviour in the form of a single coherent
state in heaven, or a parallel plurality of cacophonic imaginary
universes in the form of raining deamons from a decoherent hell.
The cocoon of mythos is a comforting blanket during the
metaphosis between complementary states.
Making up, and waking up is hard to do.
Mastering duality is more politics than science:
The crook and fan:
http://www2.cybercities.com/j/joenbevs/Graphics/tutcoffin.jpg
The arrows and sprig:
http://www.greatseal.com/GSeals.jpg
BTW, what's going on with LANL ?
Fire, flood,... what's next, pestilence ?
"Don't fool around with mother nature"
-olde saying
"Don't mess around with Jim" (unless you're prepared to take its place)
- Jim Croce
What happens when a watch starts playing with its own escapement ?
(and when all the escapements of many watches are entangled ?)
Parrondo's Paradox:
http://www.bestweb.net/~ca314159/parrondo.htm
Quantum Escapements:
http://www.phys.unsw.edu.au/STAFF/RESEARCH/linke.html#quantum
Tic Toc, Tic Toc...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Tue, 11 Jul 2000 06:28:57 -0700
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Scott Fluhrer wrote:
> > For example, in terms of private key encryption systems, we already
> > know how to do secure (at least, to the best of our knowledge)
> > encryption in 10-20 cycles per byte encrypted (eg. the AES finalists).
>
> Which were designed specifically with common existing architectures
> in mind. On any word-oriented architecture, there will be occasions
> when one can treat memory word access as the parallel bit-bus transfer
> that it really is, and of course parallelism speeds things up. But
> try using such tricks on a good stream cipher some time; they tend to
> use inherently serial algorithms, not parallelizable ones.
I'm not certain how this is supposed to invalidate my argument that a
cipher that deals with bits individually would be too slow to be
interesting. Yes, existing ciphers gain performance by treating groups of
bits at once, rather than individually -- any new cipher that tries to take
advantage of bit addressability to access individual bits would not be
taking advantage of this parallelism, and thus will be at a large
performance disadvantage against existing ciphers.
BTW: the fastest stream ciphers do use word-wide parallelism -- look at
Seal. Or, to a lesser extent, RC4, which does 8 bit parallelism.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Elliptic Curves encryption
Date: 11 Jul 2000 13:49:43 GMT
Look at IEEE P1363 website for P13634a draft for ECIES method of encryption.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Tue, 11 Jul 2000 13:52:48 GMT
On Tue, 11 Jul 2000 00:07:21 -0400, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Konrad Schwarz wrote:
>> From an abstract point of view, possibly. From a practical
>> point of view, I beleive not: the investment in byte addressable
>> hardware is just too large and the payoff of bit-addressing too small.
>Spoken like somebody who does not program communication protocols,
>error-correcting codes, etc.
>There is no fundamental obstacle. The main issue is that bit
>addresses require 3 more bits than octet addresses. Whoopdeedo.
I can remember the days when (one or) two more bits were saved from
addresses: people addressed words in the computer's memory, whether
12, 16, 18, 24, 32, 36, 48 or 64 bits long, and bytes, or 6-bit
characters, were only dealt with using special instructions.
I don't see why a compromise has never been used: a computer might use
addresses that refer to 16-bit words in its memory (say, if its
instructions are aligned on 16-bit boundaries) but for byte
manipulations, the index register might contain a byte displacement,
and bit manipulations would use an index register with a bit
displacement. (The quantities in the base register, of course, would
still be normal addresses, which in the system I am proposing would
refer to the number of a 16-bit word.) One could also address nybbles
(four bit hexadecimal digits).
Thus, arrays of bytes or bits would be aligned on halfword boundaries,
but they would be packed internally. This would gain a bit of
efficiency over byte addressing, yet still allow character
manipulation instructions.
John Savard (teneerf <-)
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Tue, 11 Jul 2000 13:56:25 GMT
On Tue, 11 Jul 2000 00:16:07 -0400, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Jayant Shukla wrote:
>> The AES candidates are not too _tiny_. In fact, the fully pipelined
>> version of the AES candidates could not be fitted on Xilinx XC4000
>> FPGA. The NSA paper shows that even the most efficient implementation
>> of these algorithms in hardware takes up > 23 mm^2 of silicon.
>> Don't even ask about the fully pipelined versions ( ~1000 mm^2).
>Sounds to me like somebody screwed up. The TMS320C6201 versions
>were something like 1KB each on average.
If, by "fully pipelined", one means an implementation where each round
has a separate hardware implementation, so that blocks can be
enciphered at a rate corresponding to the time required to do one
round in hardware, I suppose you would need a fair amount of silicon.
But the fact that *such* an implementation is not "tiny" is not, I
would agree, something that disqualifies the AES from that many uses.
John Savard (teneerf <-)
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Tue, 11 Jul 2000 08:04:20 -0600
Reply-To: [EMAIL PROTECTED]
Paul Koning wrote:
> John Savard wrote:
> > ...But the simplest rule for producing truly random bits
> > from biased bits is to use this table:
> >
> > 00 : discard
> > 01 : 0
> > 10 : 1
> > 11 : discard
>
> Shouldn't that be "less biased bits from biased bits"?
> If there is correlation over lengths greater than 2, this
> approach alone is not sufficient.
>
> If I remember right, this algorithm was first suggested
> by John von Neumann.
It was suggested by von Neumann. It completely removes bias if the
numbers are independent. This is why independence is so important.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Advanced Cryptography FAQ
Date: 11 Jul 2000 10:21:30 EDT
[EMAIL PROTECTED] wrote:
>
>Many people are now broken up into two groups...
>
>1) Those that want to have something (anything!!!) to do with it
> to steal credit or get some personal gain as base encryption
> revolutionizes the cryptography world.
>
>2) Those that are attacking it.
>
You missed the group that I am in. I have no particular interest in
attacking any idea. I just wish to learn and to avoid misinformation.
In every field there is a set of recognized experts, a few folks with
wild and radical ideas that, if true. will advance the state of the art
(and who the experts pay attention to), and a huge crowd of crackpots
who are either not understandable at all or who don't grasp the
fundamentals of the subject at hand. The latter group includes you.
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 12:35:27 +0200
Stephen Fuld wrote:
>
> "Terje Mathisen" <[EMAIL PROTECTED]> wrote in message
> > It does look like IA64, if not Merced, could be capable of doing this,
> > since it becomes feasible to keep even 2048-bit keys inside a range of
> > cpu registers.
>
> OK, but this brings up one of my questions about IA64. It appears that
> there is no carry flag and that the add instructions can't set a predicate
> bit if there is a carry (similarly for subtract / borrow). Wouldn't that
> help bignum addition and subtraction. I know you can get around it, but it
> seems a curious omission.
Even if you have carry flags, carry propagation will always become a
bottleneck for a sufficiently large (pipelined) bignum add.
This is why I stated that high performance IA64 code should use
carry-save number storage, this way each iteration of the
multiply-accumulate loop will have the two operands plus carry as
inputs, while generating the result and outgoing carry arrays.
Only at the very end do you need to merge the product(sum) and carry
arrays.
This approach makes it possible to utilize an arbitrary number of
execution units, up to the size of the bignum arrays, without the carry
propagation becoming a latency limiter.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: IDEA CBC
Date: Tue, 11 Jul 2000 15:29:47 +0100
Wasn't the use of the word "idea" a hint? ;)
--
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
Runu Knips <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Daouda Timera wrote:
> > I won to get information about the difference beetwen the
idea_cbc40 and
> > the idea_cbc56 and how can I implement it ( to generate the
necessary
> > 128 Bits Key vor encryption) vor WAP (WTLS -Layer)
>
> Sounds like DES with 40 or 56 bit keys, both in CBC mode.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: One plaintext, multiple keys
Date: 11 Jul 2000 10:33:29 EDT
Paul Pires wrote:
>
>What do you mean "Other algorithms can leak if you repeatedly send the same
>plaintext enciphered with different keys." ? All others or just some others?
>Any in the class of DES, AES finalist? Can you give an example of one and
>show the type of information leaked?
>
You are confusing "can" with "do". "Can leak" is the opposite of
"Can't leak" (leakage is impossible), which is a property of OTP
and not, say, DES. In fact, many commonly used ciphers are, in
theory, "easily" breakable by an exhaustive key search by a
sufficiently powerful computer. In many cases, the speed of light
is too slow for the speed required and the total number of atoms in
the universe is too small for the memory required, but the crack is
still conceptually simple. You can't crack OTP with a brute force
"try every key" approach even if your computer is infinitely fast
and infinitely powerful.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: RC4 question
Date: 11 Jul 2000 10:38:13 EDT
Bill Unruh wrote:
>
>
>In <8js32m$t7j$[EMAIL PROTECTED]> dexMilano <[EMAIL PROTECTED]> writes:
>
>]A silly question.
>
>]I've tried the implementation of RC4 you can find on the web.
>]Is it correct the felling that the same sequence of bits in the same
>]position, with the same key, is coded in the same way, indipendently
>]form the previos bit sequences.
>
>]I mean that, if yuo have to code gufy and pufy, the cript version shold
>]be something like 1234 and 9234.
>
>Yes, IF they are in the same postion in the stream with the same key.
>That is why you MUST NEVER use the same key to encrypt two different
>texts.
If you use the implementation found at http://www.ciphersaber.gurus.com
you will avoid reusing the same key.
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Who was that girl?
Date: Tue, 11 Jul 2000 14:38:39 GMT
On Mon, 10 Jul 2000 23:44:58 -0400, An Metet
<[EMAIL PROTECTED]> wrote:
>Please accept my apologies for this tyro question. I scanned the FAQ and
>didn't see any reference to this.
>
>About a year ago there was a news item in the popular press that a young
>girl (age 13-16) had created a rather sophisticated new cipher (I hope I
On Sun, 9 Jul 2000 22:55:15 +0100, "Theophilus Samuels"
<[EMAIL PROTECTED]> wrote:
Re: CP algorithm
on sci.crypt
>Check out http://www.cayley-purser.ie for an article entitled 'Cryptography:
>An Investigation of a New Algorithm vs. the RSA' - this was written by Sarah
>Flannery who won Ireland's Young Scientist of the Year award 1999. If this
>has already been discussed beforehand, then forgive my intrusion.
>
> T.L.S.
We need cross thread posting as well as news group cross posting., The
theophilus post was only about 8 messages earlier than anmetet's in
this newsgroup.
BTW, the Flannery paper is clear and informative. Quite a contrast
with some of the snakeoil being peddled elsewhere.
John
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Random Numbers
Date: 11 Jul 2000 10:43:02 EDT
John Savard wrote:
>
>
>On Mon, 10 Jul 2000 00:18:55 +0100, "David Hyde"
><[EMAIL PROTECTED]> wrote, in part:
>
>>Sorry I left out some detail about the random bit stream. The bit stream
>>has been generated from a white noise source I built from a zener diode, a
>>couple of op-amp stages and a comparator. Although the bits produced are
>>independent of each other, there is a bias that can't be removed by
>>adjusting the dc mean level of the noise. Therefore I was asking if there
>>is a way of processing the bit stream to produce 16-bit random numbers with
>>a uniform distribution?
>
>One important thing to note is the information content of these random
>bits, so you know how many of them are needed to produce a 16-bit
>random number. But the simplest rule for producing truly random bits
>from biased bits is to use this table:
>
>00 : discard
>01 : 0
>10 : 1
>11 : discard
At least one implementation (Intel's motherboard RNG) alternates the
above with
00 : discard
01 : 1
10 : 0
11 : discard
In an attempt to further reduce bias.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Random Numbers
Date: 11 Jul 2000 10:47:28 EDT
David Hyde wrote:
>
>
>
>"David Hyde" <[EMAIL PROTECTED]> wrote in message
>news:8kac12$nk2$[EMAIL PROTECTED]...
>> Does anyone know how to convert a random bit stream into random 16-bit
>> numbers with uniform distribution?
>>
>>
>
>Sorry I left out some detail about the random bit stream. The bit stream
>has been generated from a white noise source I built from a zener diode, a
>couple of op-amp stages and a comparator. Although the bits produced are
>independent of each other, there is a bias that can't be removed by
>adjusting the dc mean level of the noise. Therefore I was asking if there
>is a way of processing the bit stream to produce 16-bit random numbers with
>a uniform distribution?
>
>
Consider the case if you sample at. say 10 Gigasamples/second.
Would the bits produced be independent of each other?
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Random Numbers
Date: 11 Jul 2000 10:50:54 EDT
Paul Koning wrote:
>
>
>John Savard wrote:
>> ...But the simplest rule for producing truly random bits
>> from biased bits is to use this table:
>>
>> 00 : discard
>> 01 : 0
>> 10 : 1
>> 11 : discard
>
>Shouldn't that be "less biased bits from biased bits"?
>If there is correlation over lengths greater than 2, this
>approach alone is not sufficient.
Yes. Take the output of the above and feed it into another
identical stage and you reject correlation over lengths of 4
or smaller. Do it again and it's 8. You throw away more and
more bits, though.
>If I remember right, this algorithm was first suggested
>by John von Neumann.
Yes.
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Random Numbers
Date: 11 Jul 2000 09:59:10 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Herman Rubin wrote:
>> Diodes tend to have rather nasty types of dependence.
>> There are ways to remove this, and the bias. The easiest
>> to carry out, if enough are available, is to add the blocks
>> with or without carry, discarding the overflow. It would
>> be better to have the blocks widely separated in time; even
>> storing the numbers and doing this weeks later is not a bad
>> idea.
>I suppose an equivalent to your suggestion is to use several
>devices and combine them together. (I attempted to use
>combination of a number of pseudo-random streams to get
>better result in a combined PRNG.)
It would improve randomness for physical devices. For PRNGs,
it is likely to do so, but combining them in other ways can
produce worse results. This has been suggested for combining
generators of the type x[n] = x[n-j] OP x[n-k], 0 < j < k,
using several large values of k to remove the known problems
with single ones. Using the same k more than once is not
recommended here; the separate streams are combined.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
** 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
******************************
