Cryptography-Digest Digest #153, Volume #9 Sat, 27 Feb 99 17:13:03 EST
Contents:
Re: 16Bit RC4 (fungus)
Re: I'm puzzled ("FunkyDunk")
Re: Quantum Computation and Cryptography (John Savard)
Re: Testing Algorithms (R. Knauer)
Re: Miller-Rabin prime test. Random bit size (Scott Fluhrer)
Re: Testing Algorithms ("Trevor Jackson, III")
Re: Question on Pentium III unique ID ("Roger Schlafly")
Re: Why Physical Randomness? (Herman Rubin)
Re: One-Time-Pad program for Win85/98 or DOS (Helmut Kreft)
Re: My Book "The Unknowable" (Neil Nelson)
Re: One-Time-Pad program for Win85/98 or DOS (Gretchen Anonymous Remailer)
Re: Testing Algorithms (R. Knauer)
Re: Testing Algorithms (fungus)
----------------------------------------------------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: 16Bit RC4
Date: Sun, 28 Feb 1999 05:03:58 +0100
iLLusIOn wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Just out of curiosity I wrote a RC4 routine which uses 16bits instead of
> 8bits, thus I get a maximum keysize of 512kbits.
(see the thread "Testing Algoritms" for reasons why any key over 128 bits
in size is probably a waste of time)
> Does this increase of keysize somehow weaken the original RC4 algorithm?
>
16 bit RC4 has been done many times by idle cryptographers....
There is no real reason to believe it increases strength (apart from
increasing setup time and RAM requirements), and some reasons to believe
that it increases the danger of weak keys (if you understand why some
RC4 keys are weak then you'll see why).
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: "FunkyDunk" <[EMAIL PROTECTED]>
Subject: Re: I'm puzzled
Date: Mon, 22 Feb 1999 07:54:53 -0000
John,
Thanks very much. I spent a couple of hours trying to figure out if it was
random or actual simple cipher encryption and I have to admit it was beyond
me! Maybe I should stick to what I know... Although I must say this is a
very cool newsgroup!
Cheers
FunkyDunk
[EMAIL PROTECTED] wrote in message <[EMAIL PROTECTED]>...
>FunkyDunk ([EMAIL PROTECTED]) wrote:
>: Just wondering if anybody has any idea of what the encryption is at the
>: bottom of the message below. Always a strange header, always a strange
>: description and always this weird encrypted text.
>
>There is this spammer for a Dutch porn site that pads his messages with
>random letters so that they can't be as easily killfiled.
>
>John Savard
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Quantum Computation and Cryptography
Date: Thu, 25 Feb 1999 22:35:11 GMT
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote, in part:
>Even a quatum computer has a finite switching time or time per instruction, etc.
>What is the expected order of magnitude increase in performance? 5? 10?
>100???
Well, the basic idea is that while a quantum computer might be slower
and smaller than a regular computer, a certain number of bits could be
both 0 and 1 at the same time - and independent of the other bits.
So you could build a quantum computer to carry out DES encryption, and
if you had 56 "qubits", then it just has to decrypt your input block
once - and 'collapse the wave function' for the particular key that
produces the output block you're searching for.
How many "qubits" are really possible, and how involved a computation
could really be carried out quantum mechanically, are still very much
open questions.
In rough terms, though, think of a quantum computer as a way not to
make one faster microprocessor, but as a way to have trillions - or
more - computers working in parallel for the price of one. (But you
only get to hear the answer from one of the computers, which has to be
smart enough to pick itself.)
John Savard (teenerf is spelled backwards)
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Testing Algorithms
Date: Sat, 27 Feb 1999 18:06:56 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 28 Feb 1999 03:14:19 +0100, fungus
<[EMAIL PROTECTED]> wrote:
>Is it time to ask Bob for his peculiar definition of "reversible
>process"...
The same one that physicists define as a Reversible Process - the one
where you go around a closed loop in phase space and end up with the
same energy as you started with.
Try the Carnot Cycle - two adiabatic processes and two isothermal
processes intermixed. I believe you will find that it is reversible,
(if I remember my Thermodynamics of many years ago).
Another example is a particle moving about in a conservative force
field. If you calculate the energy for a closed loop in a conservative
force field, it will not change from the original value when you
return to the start of the loop. That is, the closed line integral of
the force is zero.
The inverse square law field of Newton's gravitational field and
Coulomb's electric field are examples of conservative force fields,
whereas the full electromagnetic field of Maxwell, which includes the
magnetic field, is not conservative IIRC.
Any more physics questions?
Bob Knauer
"If you want to build a robust universe, one that will never go wrong, then
you dosn't want to build it like a clock, for the smallest bit of grit will
cause it to go awry. However, if things at the base are utterly random, nothing
can make them more disordered. Complete randomness at the heart of things is the
most stable situation imaginable - a divinely clever way to build a universe."
-- Heinz Pagels
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Miller-Rabin prime test. Random bit size
Date: Sat, 27 Feb 1999 19:24:58 GMT
In article <7b74jg$hf2$[EMAIL PROTECTED]>,
"Erwin Molendijk" <[EMAIL PROTECTED]> wrote:
>When performing the Miller-Rabin test for prime n,
>you have to choose a random number A, 2<= A <=n-2.
>
>Is it ok to choose a random A between 2 and the
>max machine integer?
Well, what you lose is the proof of the probability
of any composite number making it through N
iterations of the test. It can be proven that,
for any composite N, (3/4)*N of the numbers between
2 and N-2 are witnesses to its compositeness (that
is, if you chose them to start the M-R test, the
test will output 'Definitely Composite'). So, if
you select k random numbers between 2 and N-2, then
N has a probability of at most (1/4)**k of passing
all the tests if it is composite.
Now, this proof does not work if you select a
smaller range (or if you use a deterministic method
to choose the numbers). At most 1/4 of the numbers
are liars, but there is no proof that they might not
be concentrated in the relatively small range
(2 <= A <= 0xFFFFFFFF) [1].
On the other hand, this is mostly of interest to
mathematical pendants like me. Having all the liars
concentrated in a small range is possible, but we
have no evidence that it actually occurs.
[1] I believe that someone has proven that, if the
"Extended Riemann hypothesis" is true, then there
will always be a witness between 2 and 4*log2(N).
Even if the ERH is true, all this means is that
there is at least one small witness -- the
probability of a small number being a liar could
still be high.
------------------------------
Date: Sat, 27 Feb 1999 14:45:39 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
R. Knauer wrote:
> On Sun, 28 Feb 1999 03:15:18 +0100, fungus
> <[EMAIL PROTECTED]> wrote:
>
> >*something* has to trigger a change of state...
>
> Yes, but it does not have to consume energy. By returning to the
> original state, all the energy needed to trigger it was returned. The
> concept of reversibility involves a closed cycle.
I think not. There must be some non-zero energy expenditure or we're into perpetual
motion.
For example, an object passing a massive body on an open (hyperbolic) orbit
experiences gravity as a conservative force. But, inevitably, the energy available
on ext is going to be less than that available on entry.
Even in the hardest vacuum with no friction against an ambient medium, the tidal
effects will heat both objects a tiny amount as a side effect of the frictional
losses internal to the objects. That energy is lost.
>
>
> A dumbweight is a good example. Put identical weights on either end of
> a rope that is suspended from a frictionless pulley, like the
> counterweight system used in an elevator. Very slowly move the weights
> about. The total energy of the system does not change as you shift the
> weights, since the gravitational force field is conservative.
>
> IOW, the energy needed to cause the left weight to be up and the right
> weight to be down is the same as the energy for the opposite
> condition, or for any intermediate condition for that matter.
>
> Bob Knauer
>
> "If you want to build a robust universe, one that will never go wrong, then
> you dosn't want to build it like a clock, for the smallest bit of grit will
> cause it to go awry. However, if things at the base are utterly random, nothing
> can make them more disordered. Complete randomness at the heart of things is the
> most stable situation imaginable - a divinely clever way to build a universe."
> -- Heinz Pagels
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Question on Pentium III unique ID
Date: Sat, 27 Feb 1999 11:08:24 -0800
Myself wrote in message <[EMAIL PROTECTED]>...
>And plug-n-play cards also have unique serial numbers. There's nothing
>new about uniquely identifiable PCs. The only interesting thing about
>the P3 is the publicity and standardization that comes with Intel's
>massive influence.
And the fact that Intel announced that it intends to distribute software
that surreptitiously uses the ID to identify people on the internet.
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Why Physical Randomness?
Date: 27 Feb 1999 14:45:46 -0500
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
>>We cannot distinguish between PRNG and TRNG by general external tests.
>>But the whole point of the device is to produce unknowable numbers.
>>These are TRNG, and there is a difference. That difference is the
>>unknown algorithm which can*recover the internal PRNG state, and then
>>reproduce the sequence. The reason for having a physically-random
>>device is that we can assume that there can be no such algorithm.
>This says - as well as anything that anyone has said here - why a
>physical source of randomness is useful to have, and what the
>advantage is that it has over an algorithmic method of generating
>random numbers, however good.
It depends on the purpose. For simulations, where there will not
be a need to use the numbers again, and where independence is
important, PRNGs are always going to be questionable. On the
other hand, for cryptography, it is important that the person
on the other end can produce the same numbers, and this means
physically sending the numbers over a secure channel. In this
case, a PRNG which is hard enough to crack, but simple enough
to remember, has advantages.
--
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: Helmut Kreft <[EMAIL PROTECTED]>
Crossposted-To: alt.security,alt.privacy
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Date: Sat, 27 Feb 1999 21:24:49 +0100
Daniel Kinnaer wrote:
>
>
> I would like to know why you think a OneTimeKey is cryptographically
> weak. Or is it just this implementation?
>
I do not say OTPs are cryptographically weak in general. A correct
implementation is provably secure. In fact - it is guaranteed to be
unbreakable. But a strong implementation must meet at least the
following requirements:
1.) A hardware random number generator must be used for key generation.
2.) The key (pad) will have to be transmitted over a secure channel.
3.) The key (pad) may be used only one time.
V-OTP fails completely.
Helmut
------------------------------
From: Neil Nelson <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.physics,sci.logic
Subject: Re: My Book "The Unknowable"
Date: Sat, 27 Feb 1999 20:46:21 GMT
In article <7b4ua7$1kc$[EMAIL PROTECTED]>,
Many thanks to the well known mathematician G. J. Chaitin for
providing web links to his recent viewpoints.
G. J. Chaitin wrote
(http://www.umcs.maine.edu/~chaitin/unknowable/):
[ In a nutshell, G�del discovered incompleteness, Turing discovered
[ uncomputability, and I discovered randomness---that's the amazing
[ fact that some mathematical statements are true for no reason,
[ they're true by accident. There can be no ``theory of everything,''
[ at least not in mathematics. Maybe in physics!
If these statements were true for no reason, it is not likely we would
need G�del's, Turing's, and Chaitin's detailed reasons, as evidenced
in their papers, to convince us they were true. Chaitin's viewpoint
conforms to the common Platonism in mathematics by presuming that
proof is merely a confirmation of pre-existing truth, and that somehow
the mentioned theorems evidence the Platonistic distinction in
identifying truth without proof (true for no reason). However I
suggest, whatever we know, we know by some means, and it seems a
rather arbitrary distinction to say the means in one case was a proof
and in another was not. I.e., there can be no proof of the
Platonistic distinction by definition and hence it becomes a
metaphysical/philosophical assumption.
Karl M. wrote:
< After looking through your paper: The difference between MATTER
< being paramount and INFORMATION being paramount is the difference
< between
< RANDOM=CHAOS/COMPLEXITY and
< RANDOM=INFORMATION*COMPLEXITY.
And the reference from Chaitin
(http://www.umcs.maine.edu/~chaitin/unknowable/ch7.html)
apparently being:
[ The conventional view is that matter is primary, and that
[ information, if it exists, emerges from matter. But what if
[ information is primary, and matter is the secondary phenomenon!
[ After all, the same information can have many different material
[ representations in biology, in physics, and in psychology: DNA, RNA;
[ DVD's, videotapes; long-term memory, short-term memory, nerve
[ impulses, hormones. The material representation is irrelevant, what
[ counts is the information itself. The same software can run on many
[ machines.
Although the question of information vs. matter can be viewed in this
way, it will be somewhat difficult to communicate the question without
embedding the derived concept of matter in information for
communication. I.e., if we are already in an information bounded
context, it is ultimately self-defeating to speak of that which is not
information.
Although there is an assumed matter substrate to communication (that
which carries the symbols of communication), it is the operations of
forming and recognizing patterns in matter that is communication.
Also information is assumed representational, to be about something
other than the symbols, though perhaps this representational aspect
can be exchanged for another operation of meaning. Hence information
is at least twice removed, via pattern recognition as (1) symbol and
(2) meaning, from particular physical instances of the communication
substrate.
Neil Nelson
------------------------------
From: [EMAIL PROTECTED] (Gretchen Anonymous Remailer)
Date: 27 Feb 1999 21:08:23 -0000
Subject: Re: One-Time-Pad program for Win85/98 or DOS
Crossposted-To: alt.security,alt.privacy
On Sat, 27 Feb 1999 21:24:49 +0100 Helmut Kreft
<[EMAIL PROTECTED]> wrote:
>Daniel Kinnaer wrote:
>>
>>
>> I would like to know why you think a OneTimeKey is cryptographically
>> weak. Or is it just this implementation?
>>
>I do not say OTPs are cryptographically weak in general. A correct
>implementation is provably secure. In fact - it is guaranteed to be
>unbreakable. But a strong implementation must meet at least the
>following requirements:
>1.) A hardware random number generator must be used for key generation.
>2.) The key (pad) will have to be transmitted over a secure channel.
>3.) The key (pad) may be used only one time.
>V-OTP fails completely.
>
> Helmut
I tend to disagree:
item 2: That has nothing to do with V-OTP or any other one-time-pad.
The program does not dictact how the pad will be transmitted.
item 3: Again the program does not control how many times the pad gets
used.
item 1: If one does not know the source of the pad, then to him it is
random. Sometimes people tend to forget that ALL patterns will exist
in a truly random file, even ones that appear to be non-random. That's
what random means.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Testing Algorithms
Date: Sat, 27 Feb 1999 18:13:21 GMT
Reply-To: [EMAIL PROTECTED]
On Sun, 28 Feb 1999 03:15:18 +0100, fungus
<[EMAIL PROTECTED]> wrote:
>*something* has to trigger a change of state...
Yes, but it does not have to consume energy. By returning to the
original state, all the energy needed to trigger it was returned. The
concept of reversibility involves a closed cycle.
A dumbweight is a good example. Put identical weights on either end of
a rope that is suspended from a frictionless pulley, like the
counterweight system used in an elevator. Very slowly move the weights
about. The total energy of the system does not change as you shift the
weights, since the gravitational force field is conservative.
IOW, the energy needed to cause the left weight to be up and the right
weight to be down is the same as the energy for the opposite
condition, or for any intermediate condition for that matter.
Bob Knauer
"If you want to build a robust universe, one that will never go wrong, then
you dosn't want to build it like a clock, for the smallest bit of grit will
cause it to go awry. However, if things at the base are utterly random, nothing
can make them more disordered. Complete randomness at the heart of things is the
most stable situation imaginable - a divinely clever way to build a universe."
-- Heinz Pagels
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Sun, 28 Feb 1999 08:34:01 +0100
"R. Knauer" wrote:
>
> On Sun, 28 Feb 1999 03:14:19 +0100, fungus
> <[EMAIL PROTECTED]> wrote:
>
> >Is it time to ask Bob for his peculiar definition of "reversible
> >process"...
>
> The same one that physicists define as a Reversible Process - the one
> where you go around a closed loop in phase space and end up with the
> same energy as you started with.
>
<snip>
Well, yeeesss...
...but I don't see the relevance in this context. We're talking
about a computer CPU which needs to be controlled in some way.
You can't just let the electrons (or whatever) float around in
space. They have to be pushed back and forth at predefined
intervals or chaos will follow.
How do you push them without using energy?
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
** 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
******************************
