Cryptography-Digest Digest #506, Volume #11 Fri, 7 Apr 00 05:13:01 EDT
Contents:
Stream cipher from FSE 1 ([EMAIL PROTECTED])
RC4 statistics (Paul Rubin)
Re: RC4 statistics ("Scott Fluhrer")
Re: Public|Private key cryptography? (Jerry Coffin)
Re: RC4 statistics (Johnny Bravo)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (Alan Mackenzie)
Re: Encrypt the signature? ([EMAIL PROTECTED])
Re: enigma returned ("G. R. Bricker")
Nevermind. Questioned answered... ("G. R. Bricker")
Re: Q: Simulation of quantum computing (Bill Unruh)
Re: Q: Simulation of quantum computing (Mok-Kong Shen)
Re: Q: Entropy (Mok-Kong Shen)
Re: Factoring Composite Numbers (Bill Unruh)
Re: Q: Entropy (Mok-Kong Shen)
Re: Is this code crackable? ("1198")
Re: Q: Simulation of quantum computing (Mok-Kong Shen)
Is AES necessary? (Mok-Kong Shen)
Processing encrypted data ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Stream cipher from FSE 1
Date: Fri, 07 Apr 2000 05:00:49 GMT
IIRC, in FSE 1 Ross Anderson suggested a stream cipher
formed by using an LFSR to turn the wheels of a three-wheel
rotor system. Has there been any cryptanalysis of this?
Or any other kind of -analysis?
--
Cordially,
Dave Empey
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: RC4 statistics
Date: 7 Apr 2000 05:26:25 GMT
I vaguely recall reading of statistical biases in RC4 output.
Is that something detectable in practice? If I have a few
gigabytes of RC4 output, assuming starting with a good initial
state, can I tell with high confidence that the output isn't random?
Thanks.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: RC4 statistics
Date: Thu, 6 Apr 2000 23:04:56 -0700
Paul Rubin <[EMAIL PROTECTED]> wrote in message
news:8cjri1$flt$[EMAIL PROTECTED]...
> I vaguely recall reading of statistical biases in RC4 output.
> Is that something detectable in practice? If I have a few
> gigabytes of RC4 output, assuming starting with a good initial
> state, can I tell with high confidence that the output isn't random?
Quick answer: Yes
Full answer: See FSE2000 next week
--
poncho
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Public|Private key cryptography?
Date: Fri, 7 Apr 2000 00:42:02 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> Actually 56 bits was too small then too. It's not practical to search a
> 80 bit key space now, or 10 years from now.
"Practical" is obviously open to definition. Right now it appears to
me that it could be one for a price in the range of 10s of millions
of dollars. Ten years from now I expect that price will be
substantially lower. Whether that translates to being practical is
open to question: the big problem, of course, is that almost every
way of making money by breaking a cipher is illegal. OTOH, and
intelligence agency might have a different idea of practicality than
you do: you don't have to prevent too many terrorist acts (for
example) to have paid off even a few hundred million dollar machine.
> Currently RC5des has been
> going for what 3 years? Let's say they finish tommorow... an 80 bit key
> with a keyspace 65,536 times larger will take just a bit to solve.
You seem to constantly make the same mistake. You use the speed of a
collection of general-purpose computers as a comparison point. If
you're going to do such a thing on a regular basis, that's NOT the
approach you'd normally take at all. There's no question that a
machine to search a 64 bit address space could be built right now
that would do the job in a matter of weeks for a couple of million
dollars. That's a totally differnet prospect from three+ years, to
put it mildly.
> You are assuming computers [classical] will always
> get faster, which generally has yet to be proven, even lately, actual
> improvements in throughput [not just clock rate] are not exponential
> like we want to think, it's 10% here, 5% there.
Of course it's not proven. Very little about the future is provable.
Despite this, improvements in computation have been exponential for
an awful long time, and despite your assertions to the contrary, this
trend is NOT leveling off at the present time. Intel first announced
a 500 MHz CPU in March of 1999. The announced a 1GHz CPU in March of
this year -- a doubling of speed within a matter of days of exactly
one year. You can argue all you want, but that's as obvious an
example of exponential growth as you can ask for.
> Well the way Bob Silverman said it, factoring large keys [i.e 1024 bits]
> will take a whopping amount of ram, more then you can store in a 2^64
> space. I dunno but I doubt anytime soon computers will have 2^64+ bytes
> of memory. Assuming that the memory board was made of solely 10^-8 (mm
> square) transistors,
Depending on your definition of "soon", you're right -- in fact, 2^64
is almost certainly more than the current annual production of DRAM
of the entire world (by what looks like 2 to 3 orders of magnitude).
The same situation arises, however, with respect to CPU production
and the ability to tackle a 200-bit ECDL. Even if you could buy
every CPU Intel produced for the next year, it still wouldn't get the
job done in a reasonable period of time. Samsung has just announced
a 1.6 GHz Alpha processor, and if you could get them to produce those
at the same kind of rates that Intel produces Pentiums, and you could
buy up all that they produce and all that Intel produce, a 200-bit
ECDL problem is STILL well out of reach in any reasonable period of
time.
IOW, you're right that nobody's going to break RSA with a 2000-bit
key anytime soon, but if you think they're going to break 200-bit ECC
much sooner, I think you're badly mistaken.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: RC4 statistics
Date: Fri, 07 Apr 2000 03:01:59 -0400
On Thu, 6 Apr 2000 23:04:56 -0700, "Scott Fluhrer"
<[EMAIL PROTECTED]> wrote:
>
>Paul Rubin <[EMAIL PROTECTED]> wrote in message
>news:8cjri1$flt$[EMAIL PROTECTED]...
>> I vaguely recall reading of statistical biases in RC4 output.
>> Is that something detectable in practice? If I have a few
>> gigabytes of RC4 output, assuming starting with a good initial
>> state, can I tell with high confidence that the output isn't random?
>Quick answer: Yes
On average you would detect about 16 extra instances of successive
identical bytes per megabyte of output. The probability of a doubled
byte is nearly 2^-8 + 2^-24 rather than the 2^-8 expected from random
output. See http://www.hedonism.demon.co.uk/paul/rc4/
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
From: Alan Mackenzie<[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Thu, 6 Apr 2000 19:16:06 +0000
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
> Harvey Rook wrote:
>> "Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message > For
>> any who need a lesson: first a random digit triplet is formed
>> > directly from the random digit generator. If this number is greater
>> > than 767 it is discarded. Otherwise this number is divided by 3 and
>> > the remainder is truncated. This and all subsequent random numbers
>> > from 000 - 255 calculated in this manner are then stored in RandOut
>> > files usually having a length of 18144000 binary bytes each. These
>> > several RandOut files are further processed repeatedly using as many
>> > as ten different processes. All processes use true random user
>> > input as parameters. Finally, these RandOut files are combined
>> > randomly in the OTPs again using true random user input. This is it
>> > in a nutshell. Read the documentation available in the Help Files
>> > for more details at http://www.ciphile.com
>> Out of curiosity, Why are you generating biased numbers? 0 and 255
>> will show up much less often than 127 and 128. This operates on the
>> same principle as rolling 3 dice, summing them up and then dividing by
>> 3. The value of 1 and 6 will only show up about 0.5 % of the time, but
>> the value of 3 will show up 8.3% of the time.
Mr. Rook, I don't think Mr. Szopa understands comments like the above.
Your sarcasm has become irony!
By "formed" (as in "a random digit triplet is formed directly from the
random digit generator") he surely means that three random decimal digits
are textually concatenated to give a number in the range [0,999], as I am
sure you are well aware.
>> Harvey Rook
> Your point of contention / question indicates clearly that you do not
> have the software, have not thoroughly read the Help Files, have not
> run the examples, and have not taken the tutorials.
> You are unmotivated and do not deserve any of my time.
Mr. Szopa, why can you not be more polite and helpful to people who are
willing to spend time attacking your crypto? Or even to people who point
out vagueness in your textual descriptions? Such activities can only
improve your system, by pointing out weaknesses which you can then
rectify, or by increasing its credibility if no such weaknesses are
found.
If I were a potential customer seeing your attitude here, I would give
your product a very wide berth.
--
Alan Mackenzie (Munich, Germany)
Email: [EMAIL PROTECTED]; to decode, wherever there is a repeated letter
(like "aa"), remove one of them (leaving, say, "a").
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encrypt the signature?
Date: Fri, 07 Apr 2000 07:12:12 GMT
Thank you for your help,
Patrice Krakow
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > If I want to have a crypted signed document, have I to
> > encrypt the signature ???
>
> No, that's not necessary. You hash the message before encryption,
> then use that to make the signature. The signature is independent
> of the message in that sense, you can send the message encrypted
> along with the signature in the clear. To check the signature you
> need a hash of the message, so only the receipient can check it
> since only they can decrypt the message. The hash isn't sent.
>
> Patience, persistence, truth,
> Dr. mike
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "G. R. Bricker" <[EMAIL PROTECTED]>
Subject: Re: enigma returned
Date: Fri, 07 Apr 2000 07:58:11 GMT
Is the enigma particularly rare or valuable? I was under the impression
that thousands of the machines were captured by the Allies in WWII and then
sold to Third World countries (particularly ex-colonies) for sensitive
encryption. These client countries didn't know that the Brits and Yanks had
figured out how to crack the machine. I can't remember where I read this.
Maybe "The Code Book" by Singh. Anyway, I would think that there would be
hundreds of these machines gathering dust in warehouses around the world. A
collecter would probably be able to track these down and buy them for very
little. Or very little compared to the same machine found in the US or GB,
where the nostalgia value would raise the price.
-Opinions?
Derek Bell wrote:
> : I have just heard (21.30 04/04/00)that a 50 year old man from Bedford,
> : England, has been arrested for the theft of the enigma machine from
> : Bletchley Park. No further details known.
>
> He's been released, but he the machine hasn't been recovered.
>
> I hope it's recovered soon and in good condition.
>
> Derek
>
------------------------------
From: "G. R. Bricker" <[EMAIL PROTECTED]>
Subject: Nevermind. Questioned answered...
Date: Fri, 07 Apr 2000 08:06:19 GMT
G. R. Bricker <[EMAIL PROTECTED]> wrote in article
<01bfa067$03a0aac0$3006ebd0@default>...
> Is the enigma particularly rare or valuable?
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Q: Simulation of quantum computing
Date: 7 Apr 2000 08:15:04 GMT
In <[EMAIL PROTECTED]> Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>I seems to follow from these that QC is more powerful than TM.
>Is that right?
If what you want is to generate random bits, then a quantum computer is
more powerfull than a classical computer. However a for this purpose a
zener diode is just as powerful as a quantum computer and much much much
cheaper.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Simulation of quantum computing
Date: Fri, 07 Apr 2000 10:23:31 +0200
NFN NMI L. wrote:
>
> <<Can one simulate a quantum computer with a common digital computer?>>
>
> Of course. Anything a quantum computer can do, a classicial computer can do.
> Both are universal. I suppose the difference lies in different ways of
> interpreting "emulation".
Do you mean that, depending on interpretation, that 'emulation'
could be an exact one or an approximate one, like 3.14 for PI, or
what? Since QC, as far as I know, exploits the uncertainty inherent
in quantum mechanics, it should be able to generate truly random
bits, while a classical computer can only do deterministic things
and hence can't perform that task by definition.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Fri, 07 Apr 2000 10:26:26 +0200
David Hopwood wrote:
>
> # Formally, the amount of information in a message M is measured by
> # the entropy of a message, denoted by H(M).
>
> As the notation H(M) is used in information theory, M is a random
> variable, not a message or bit string. It's quite common, even among
> mathematicians when speaking informally, to fudge the difference
> between a random variable and an outcome of that random variable,
> and "Applied Cryptography" is not the right book in which to look for
> a more formal treatment than that.
The point that is misleading is that the quote says 'message M', so M
is a 'message', not the 'random variable' of yours. A symbol can't
in one and the same sentence denote two different things :-)
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Factoring Composite Numbers
Date: 7 Apr 2000 08:22:43 GMT
In <8cj7o8$7qe$[EMAIL PROTECTED]> "Nickolaus Benjamin Padgett"
<[EMAIL PROTECTED]> writes:
>1) How long would it take to factor 'n' using the latest in factorization.
for n=4 less than a second.
The number field sieve is supposed to assymptote to
exp(1.9 ln(n)^(1/3) ln(ln(n))^(2/3)) operations. For a 2000 bit number
this is about 10^35 operations, while your method would require at least
2^1000= 10^300 operations.
>2) The most basic of all factorization methods is to divide 'n' up to the
>sqrt('n'). If I were to further decrease this space by 99% so that the
>total space to search was 1% of sqrt('n') would this be a viable decrease or
>would this expectancy still be to great?
See above. 1% of 10^300 is not much of an improvement.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Fri, 07 Apr 2000 10:34:06 +0200
Bryan Olson wrote:
>
> Here's an example that may help explain what I've been
> writing about in the "entropy" threads:
>
> Suppose Alice will shuffle a deck of 52 cards, and choose
> one at random. She will not look at it, but will show it to
> Bob, who will then give her one of two (truthful) messages:
> either "the card is an ace" or "the card is not an ace."
>
> The equivocation of an unknown card is
>
> log_2(52) = 5.70 bits.
>
> The entropy of the message space, in bits is
>
> 48/52 * log_2(52/48)
> + 4/52 * log_2(52/4)
> = 0.391
>
> If Alice receives the "the card is an ace" message, then
> there are four equally probable possibilities, so the
> equivocation of the card has dropped to 2 bits. But the
> entropy of the message space was only 0.391 bits. How could
> the entropy have dropped from 5.7 bits to 2.0 bits if she
> only received 0.391 bits in the message?
Could you please explain a bit how you derived the formula for 0.391?
What would be the entropy of the alternative message 'the card is not
an ace'? Thanks.
M. K. Shen
------------------------------
From: "1198" <[EMAIL PROTECTED]>
Subject: Re: Is this code crackable?
Date: Fri, 7 Apr 2000 16:25:12 +0800
What If a virus on the pc capable of duplicating floppies and send whenever
it can to somewhere?
Actually security is not only concern of not been able to be broken but also
to ensure delivery to the correct party.. so if you keep PAD on floppy you
are compromising the reliability of the receiver to safe keep the very
important part of his resource..
>
>>If he were to follow my instructions, how would the code be breakable?
The
>>only email traffic would be the encrypted files. And if nothing but the
>>encrypted files are on his HD, nobody could snoop his HD when he is
on-line
>>to find the PAD or any decrypted files to figure the PAD out.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Simulation of quantum computing
Date: Fri, 07 Apr 2000 11:00:40 +0200
Bill Unruh wrote:
>
> If what you want is to generate random bits, then a quantum computer is
> more powerfull than a classical computer. However a for this purpose a
> zener diode is just as powerful as a quantum computer and much much much
> cheaper.
There are always many ways to do things that more or less well
satisfy one's (practical) need. The question was mainly about
a comparison of the (theoretical) power of TM and QC. If QC
turns out to be more powerful, that fact could have considerable
theoretical consequence, I suppose.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Is AES necessary?
Date: Fri, 07 Apr 2000 11:00:55 +0200
Now that we'll soon have an AES, I think it could be interesting
to take a minute to look back and reflect whether AES is really
necessary.
I'll start by arguing for one side of the issue:
3DES is currently yet strong enough. If that's too weak, we could
use 5DES etc.
We could employ some trivial variants of DES that enable expansion
of the effective key space (e.g. permutation of the subkeys or
the S-boxes).
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Processing encrypted data
Date: Fri, 07 Apr 2000 11:07:50 +0200
Reply-To: [EMAIL PROTECTED]
I know that is possible make calculus directly on encrypted data with
functions called "Privacy homomorphisms". These functions allow
arithmetic operations like addition, subtraction and multiplication.
What are the homomorphic encryption schemes that you know?
It's possible to make also LOGIC operations on encrypted data (like
AND,OR,NOT)?.
I am very intersted in this subject.
Thanks for your informations and comments in advance.
Claudio
------------------------------
** 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
******************************
