Cryptography-Digest Digest #373, Volume #10 Thu, 7 Oct 99 19:13:02 EDT
Contents:
Re: There could be *some* truth to it (Anton Stiglic)
Re: Exclusive Or (XOR) Knapsacks (Guenther Brunthaler)
Re: Perfect Shuffle Algorithm? (Herman Rubin)
Re: Research paper... ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: frequency of prime numbers? ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: classifying algorithms ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: Very well.. here's the article itself (was Re: Second "_NSAKey") ("Doug Gwyn
(ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: Perfect Shuffle Algorithm? ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: Breaking iterated knapsacks ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: There could be *some* EIAC ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: Block encryption with variable keys ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: Exclusive Or (XOR) Knapsacks ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: There could be *some* truth to it ("Doug Gwyn (ISTD/CNS) " <[EMAIL PROTECTED]>)
Re: True Random numbers (Tim Tyler)
Re: Very well.. here's the article itself (was Re: Second "_NSAKey") (David Wagner)
Re: radioactive random number generator (Scott Nelson)
Re: RSA-512: Weizmann Institute: London Times (Bill Unruh)
Re: Perfect Shuffle Algorithm? (Dan Day)
----------------------------------------------------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: There could be *some* truth to it
Date: Thu, 07 Oct 1999 15:31:45 -0400
==============3D342A4349CE6FE90DE5DEB2
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Patrick Juola wrote:
> In article <[EMAIL PROTECTED]>, Anton Stiglic <[EMAIL PROTECTED]> wrote:
> >Marco Lange wrote:
> >>
> >> Hi John!
> >>
> >> > Just _possibly_, there could be a professor at the Weizmann Institute who
> >> > has made a *theoretical* breakthrough in quantum computing, and is about
> >> > to publish a paper saying that in perhaps ten or twenty years, using this
> >> > technique, a quantum computer might be made that would fit in a cube 5cm
> >> > on a side that could factor a 512-bit number in 12 microseconds...
> >>
> >> Shouldn't we be able to use much longer numbers for encryption with
> >> quantum computers, then?
> >
> >If quantum computers existed, you would use quantum cryptography.
>
> You're confusing two different technological developments and branches;
> quantum cryptography doesn't require quantum computers and vice versa.
> In fact, it doesn't even require similar machines -- or that similar
> machines be buildable. In like fashion, you're also confusing two
> separate problem domains.
>
No, I'm not confusing anything. I said that if quantum computers existed, you
would
be better off using quantum cryptography. It's a simple sentence. It does not
imply
that quantum cryptography uses quantum computers. I have already explained this
quit a while ago, I don't feel like repeating again.
You better read articles about this subject, if you want to talk about it, see
for example
my lab at McGill:
http://crypto.cs.mcgill.ca
my director has interesting papers, and links that introduce quantum info stuff.
Anton.
==============3D342A4349CE6FE90DE5DEB2
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Patrick Juola wrote:
<blockquote TYPE=CITE>In article <[EMAIL PROTECTED]>, Anton
Stiglic <[EMAIL PROTECTED]> wrote:
<br>>Marco Lange wrote:
<br>>>
<br>>> Hi John!
<br>>>
<br>>> > Just _possibly_, there could be a professor at the Weizmann Institute
who
<br>>> > has made a *theoretical* breakthrough in quantum computing, and
is about
<br>>> > to publish a paper saying that in perhaps ten or twenty years,
using this
<br>>> > technique, a quantum computer might be made that would fit in
a cube 5cm
<br>>> > on a side that could factor a 512-bit number in 12 microseconds...
<br>>>
<br>>> Shouldn't we be able to use much longer numbers for encryption with
<br>>> quantum computers, then?
<br>>
<br>>If quantum computers existed, you would use quantum cryptography.
<p>You're confusing two different technological developments and branches;
<br>quantum cryptography doesn't require quantum computers and vice versa.
<br>In fact, it doesn't even require similar machines -- or that similar
<br>machines be buildable. In like fashion, you're also confusing
two
<br>separate problem domains.
<br> </blockquote>
No, I'm not confusing anything. I said that if quantum computers
existed, you would
<br>be better off using quantum cryptography. It's a simple sentence.
It does not imply
<br>that quantum cryptography uses quantum computers. I have
already explained this
<br>quit a while ago, I don't feel like repeating again.
<br>You better read articles about this subject, if you want to talk about
it, see for example
<br>my lab at McGill:
<br> <a href="http://crypto.cs.mcgill.ca/">http://crypto.cs.mcgill.ca</a>
<br>my director has interesting papers, and links that introduce quantum
info stuff.
<p>Anton.</html>
==============3D342A4349CE6FE90DE5DEB2==
------------------------------
From: [EMAIL PROTECTED] (Guenther Brunthaler)
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Thu, 07 Oct 1999 18:21:53 GMT
On Wed, 06 Oct 1999 19:35:41 GMT, [EMAIL PROTECTED] wrote:
>> Also, is it coincidence that in your example there are B1..B4 and also
>> 4 bits in X?
>
>Not a coincidence. The question was:
>| Problem:
>| Given an n bit number X and a set {B1,B2,...,Bn}
>| of n bit numbers;is there a subset whose elements
Yes, seems I need stronger glasses ;-)
>Again, a linear algebra text will explain. If
Nevertheless, XOR is a nonlinear operator.
>any subset of the vectors xors to zero, then that
>subset can be xored into any solution to produce
>another solution, and all solutions may be
>produced this way.
Ok, sounds reasonable. Although I still cannot see the equation setup.
>> Perhaps you could outine your example for the following (1-bit) setup:
>>
>> X=1, B1 = 0, B2 = 0, B3 = 0, B4 = 1, B5 = 1, B6 = 1
>>
>> and the size of the requested subset shall be 3.
>
>This fails to be an example of the stated problem.
Admittedly, yes. But it's easy to convert it into a 6-Bit Problem:
Instead of writing
X = 1
B1 = 0
B2 = 0
B3 = 0
B4 = 1
B5 = 1
B6 = 1
let's assume:
X = 100000
B1 = 000000
B2 = 000000
B3 = 000000
B4 = 100000
B5 = 100000
B6 = 100000
there are the same 10 solutions as in my previous posting, and I still
cannot see how to setup a system of linear equations (using the
non-linear XOR-operator).
Greetings,
Guenther
--
Note: the 'From'-address shown in the header is an Anti-Spam
fake-address. Please remove 'nospam.' from the address in order
to get my real email address.
In order to get my public RSA PGP-key, send mail with blank body
to: [EMAIL PROTECTED]
Subject: get 0x2D2F0683
Key ID: 2D2F0683, 1024 bit, created 1993/02/05
Fingerprint: 11 71 47 2F AF 2F CD F4 E6 78 D5 E5 3E DD 07 B5
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: 7 Oct 1999 14:28:39 -0500
In article <[EMAIL PROTECTED]>,
Lynn Killingbeck <[EMAIL PROTECTED]> wrote:
>Sundial Services wrote:
>> Jean-Jacques Quisquater wrote:
>> > Again see
>> > "Magic tricks, card shuffling and dynamic computer memories"
>> > by S. Brent Morris (NSA)
>> > MAA, 1998.
>> > see http://www.maa.org/pubs/books/cards.html
>> The classic card-shuffling algorithm that I've seen and used does not
>> replicate the human technique at all, but it produces a throughly
>> scrambled deck instantly. In Pascal:
>> for n := 52 downto 2 do SwapCards(n, Random(1,n));
>> where "SwapCards" exchanges the position of two specified cards, and
>> "Random(1,n)" produces a random number in the inclusive range [1..n].
>I don't know your definition(s) of 'thoroughly' and 'instantly', but you
>might find the comments in volume 2 of Knuth, starting with the
>paragraph at the bottom of page 145 of the 3rd edition, of interest.
>Partial quote "...cannot possibly generate more than..." Even with just
>13 cards, the common random number generators based on 2^32 values can
>not generate all shuffles.
If you do it right, it can. And if the bits can be assumed to
be a good random bit stream, with the expected number of bits
less than log_2(n!) + 2(n-1) with a simple algorithm. The
algorithm below gives an optimal (in terms of bits used) method
of generating an equidistributed random integer from 0 to n-1.
BIT() gets a new random bit at any stage. The basis for the
algorithm is that at any time k is uniform in {0, ..., m-1}.
{int n,m,k;
m=1; k=0;
loop: m = m*2;
k = k*2 + BIT();
if(m < n) goto loop;
if(k < n) {return k; exit}
m = m - n;
k = k - n;
goto loop;}
--
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
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: Research paper...
Date: Thu, 7 Oct 1999 18:22:39 GMT
David Kahn, "The Codebreakers" (Macmillan)
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Thu, 7 Oct 1999 18:28:20 GMT
Donald Welsh wrote:
> These same believers also misuse statements like "there are true but
> unprovable statements".
> ...
> What's bothersome is not this definition (although it might be better
> to term this property of a statement "unfalsifiable" rather than
> "true"); that's understood. It's that for at least some FASs, there
> is a statement P such that P and its negation ~P are both true.
What do you *mean* "are both true"? If you mean, (finitely)
*derivable*, well of course. Take any system that embeds Boolean
logic and add the axiom T = F. In that extended FAS, there are
lots of derivable statements P such that ~P is also derivable.
So what?
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: classifying algorithms
Date: Thu, 7 Oct 1999 18:33:34 GMT
Doug Stell wrote:
> No. The hallmarks of a stream cipher are the existence of a key
> stream generator, continuously changing state of the generator and
> use of the XOR function.
That's only for one kind of "key generator" stream cipher.
Other stream ciphers don't necessarily XOR anything (although
XOR is a pretty common component somewhere within many stream
ciphers, due to its information-preserving property).
------------------------------
Crossposted-To: talk.politics.crypto
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: Very well.. here's the article itself (was Re: Second "_NSAKey")
Date: Thu, 7 Oct 1999 18:16:54 GMT
Sundial Services wrote:
> http://jya.com/cryptoa2.htm
Yeah, that's what I thought was being referred to. Those
news-media reports are at best speculative and in many
instances confused. For example, what is in one place said
about being able to conduct a ciphertext-only attack is in
another place interpreted as embedding the "key" within the
cipher stream, which has quite different connotations.
>From defector statements, it is public knowledge that the US
has had some degree of success in reading encrypted traffic of
several third-world countries. Largely they were using
Hagelin (M-209-like) systems. Note that even when the M-209
was placed into field military service for the US, it was
already known to be susceptible to cryptanalysis, so no
conspiracy is needed to explain US success at reading traffic
enciphered with further variations of the same basic design.
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: Perfect Shuffle Algorithm?
Date: Thu, 7 Oct 1999 19:30:39 GMT
Randy Poe wrote:
> And I stand by my earlier statement that the "cheats"
> magicians use to do their tricks are quite often feats
> of astonishing skill. (I'd mention Houdini here, but
> maybe I've fallen for more hype in that case as well.)
There are some illusions that require actual dexterity;
for example, palming takes a lot of practice. Some of
Houdini's exploits were, however, based on the usual
kinds of misdirection and specially prepared apparatus.
I won't swear that *none* of them required unique
abilities; I think some were indeed physically demanding,
such as being able to hold his breath a long time.
This seems to have gotten completely off topic.
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: Breaking iterated knapsacks
Date: Thu, 7 Oct 1999 18:41:55 GMT
> perhaps you have some links for me,
> where i can find info about breaking knapsack.
http://www.research.att.com/~amo/doc/arch/knapsack.survey.pdf
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: There could be *some* EIAC
Date: Thu, 7 Oct 1999 18:44:30 GMT
[EMAIL PROTECTED] wrote:
> EIQC spells bad news for the validity of the article:
> http://www.eiqc.org/
How?
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: Block encryption with variable keys
Date: Thu, 7 Oct 1999 18:46:55 GMT
Mok-Kong Shen wrote:
> Why does DES (and similar block ciphers) keep the key constant
> and not varying from block to block?
Why are there 12 items in a dozen? It just is what it is.
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Thu, 7 Oct 1999 19:00:44 GMT
Guenther Brunthaler wrote:
> Nevertheless, XOR is a nonlinear operator.
Not under Brian's generalized interpretation of "linear".
Consider that XOR is just (parallel) addition modulo-2.
------------------------------
From: "Doug Gwyn (ISTD/CNS) <gwyn>" <[EMAIL PROTECTED]>
Subject: Re: There could be *some* truth to it
Date: Thu, 7 Oct 1999 18:57:54 GMT
[EMAIL PROTECTED] wrote:
> Why wait ten to twenty years when you can have a quantum computer today.
> To learn more read the Core processor article at
> http://homepages.msn.com/LaGrangeLn/ronaldblue/
I found nothing except a background at the CORE processor link.
Further, one gets an annoying MSN popup window for each page.
If you have information for us, why not post it here.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: True Random numbers
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Oct 1999 20:26:52 GMT
fungus <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Thus their OTPs are probably as secure as their PRNG.
: Thus their "OTP" isn't a OTP at all, it's a stream cipher.
: Would you trust somebody who can't even get their terminology
: right after several years of being reminded of it.
: Would you trust somebody who uses the phrase "one time pad"
: as a cheap marketing ploy (it's basically a bare-faced
: lie...) to be a good cryptographer?
I observe that "the crypto link farm" places Ciphile Software's product
in their "Snake Oil: Proprietary guaranteed unbrekable crypto we invented
this morning in the shower" section:
http://www.cs.auckland.ac.nz/~pgut001/links.html
...the "Snake Oil" section itself is pretty mind-boggling...
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Excuse me while I change into something more formidable.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: talk.politics.crypto
Subject: Re: Very well.. here's the article itself (was Re: Second "_NSAKey")
Date: 7 Oct 1999 13:26:51 -0700
In article <[EMAIL PROTECTED]>, Doug Gwyn (ISTD/CNS) <gwyn> wrote:
> Yeah, that's what I thought was being referred to. Those
> news-media reports are at best speculative and in many
> instances confused. For example, what is in one place said
> about being able to conduct a ciphertext-only attack is in
> another place interpreted as embedding the "key" within the
> cipher stream, which has quite different connotations.
Hmm. If the key appears in the ciphertext stream (perhaps as a LEAF-like entity),
doesn't that imply there is a trivial ciphertext-only attack? Namely: extract the
key from the ciphertext stream, and use it to decrypt.
Are you saying the word "attack" carries the connotation of "exploiting a
non-trivial property of the cryptosystem"? I always thought the definition of
"attack" was "anything that works" -- even out-and-out cheating is allowed... --
but I haven't been in this field for very long.
Anyway, given that there's no hope in getting media reporters to use scientific
terms precisely, isn't the most plausible explanation that by "ciphertext-only
attack" the reporter meant "one could read encrypted traffic simply by reading
the key off from the ciphertext"?
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Crossposted-To: sci.electronics.design,sci.electronics.equipment
Subject: Re: radioactive random number generator
Reply-To: [EMAIL PROTECTED]
Date: Thu, 07 Oct 1999 22:33:28 GMT
On Wed, 06 Oct 1999 19:37:37 +0000, CT Franklin
<[EMAIL PROTECTED]> wrote:
>"John E. Kuslich" wrote:
>
>> Go ahead, buy an op-amp, a zener, a couple of resistors and make yourself a
>> random source. Sample the output with your PC and run the Die-Hard test suite on
>> your data.
>>
>> The very first thing you will discover is that there are more ones than zeros
>> (or the reverse) because of offset in your sampler or amplifier. Then you will
>> find that there is bitwise correlation between portions of the output stream
>> because of power supply ripple, pick-up, etc. After you discover fixes for these
>> problems, you will find that other more difficult to diagnose biases appear in
>> the output stream (like failure to pass the parking lot test).
>
>This is interesting, but I find that I am a little confused. Aren't there easy
>ways to extract some randomness from the data at the expense of generating random
>numbers at a lower rate? Consider the issue of bias (more ones than zeros).
>Take the output two bits at a time. If the bits are 00 or 11, discard them, if the
>bits are 01, output 1, of the bits are 10, output 0. This gives you an average
>rate of one bit out for 4 bits in (unless the bias is really bad). But, assuming
>no serial correlation, it wipes out any bias.
>
This is known as Von Neumann's method. It works in theory, although
it pretty hard to prove there's no correlation between the bits.
In particular the previous poster mentioned bitwise correlation
_specifically_ as a typical problem.
It also has the annoying property that it doesn't produce bits at
a constant rate. Oft times one is more interested in worst case,
than typical, and the worst case for Von Neuman's method is 0 bits
per second.
>Similarly, I suppose I want to reduce or eliminate easily detected correlations in
>the data. Take 110 bits of data, divide into 56 and 64 bits. Encode the 64 bit
>block using DES with the 56 bit block as the key.
>
Better, but this technique doesn't scale well. If the data
is extremely biased, it might take more than 120 bits to generate
64 unbiased bits.
>Another technique is to consider the data as coming in two streams, say strings of
>bytes x1, x2, x3 ... and y1, y2, y3. We could use one stream to index characters
>out of the other stream. (I've seen this technique called the Tausworth product of
>random number generators.) (see "Improving a Poor Random Number Generator," by C.
>Bays and S. D. Durham, ACM Transactions on Mathematical Software , Volume 2, Number
>1, March 1976)
>
I've seen other things given the name Tausworthe generators.
The construct above would be better than the raw data,
but not much better.
There are many other techniques for removing bias, see
http://www.helsbreth.org/random/removing_bias.html
to name just a few.
It's also worth looking at Terry Ritter's extensive collections
of usenet postings on the topic:
http://www.io.com/~ritter/REALRAND/REALRAND.HTM
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA-512: Weizmann Institute: London Times
Date: 7 Oct 1999 21:25:43 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] () writes:
>The title "No Safety in Numbers" was used for a web page at the
>http://www.eiqc.org/
Yikes! what a site! And teh Sunday Times was just an advert for this.
This site claims Dr Brian Oakley, EIQC Life President-- what legitimate
organisation has a life president-- and it had no members.
And it then has links to legitimate organisations, making it seem they
support this one.
I would have thought by now that reporters knew that anyone can set up a
web site!
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: Thu, 07 Oct 1999 21:26:09 GMT
On Thu, 07 Oct 1999 14:56:38 -0400, Randy Poe <[EMAIL PROTECTED]> wrote:
>And I stand by my earlier statement that the "cheats"
>magicians use to do their tricks are quite often feats
>of astonishing skill.
Very true. What's funny, though, is that feats of astonishing
skill often make for less "successful" tricks than ones performed
via the most cheesy "cheat" imaginable, because the audience is
usually unable to tell one from the other. (And ideally, they
*shouldn't* be able to tell the difference, since the mechanics
of the trick are *not* supposed to be apparent.)
I've lost count of the essays I've read in various magicians'
forums which make the point that while a technically "difficult"
trick may impress one's fellow magicians, the audiences don't care,
because it's all "magic" to them -- what matters is the *performance
effect*, not the degree of difficulty to the magician himself.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
** 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
******************************
