Cryptography-Digest Digest #152, Volume #9 Sat, 27 Feb 99 12:13:03 EST
Contents:
Re: Quantum Computation and Cryptography (R. Knauer)
Re: Quantum Cryptography (R. Knauer)
Question on Pentium III unique ID ("Robert C. Paulsen, Jr.")
Re: True Randomness (R. Knauer)
Re: True Randomness (R. Knauer)
Re: Any idea what this might be??? (Marc Hoeppner)
Re: True Randomness (R. Knauer)
Re: Testing Algorithms [moving off-topic] (R. Knauer)
Re: Legal procedures for using third party crypto? (fungus)
Re: Testing Algorithms (R. Knauer)
Re: Question on Pentium III unique ID (Myself)
Quantum Randomness (R. Knauer)
Skipjack anyone? (Federico Ulivi)
16Bit RC4 (iLLusIOn)
Re: Testing Algorithms (fungus)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Quantum Computation and Cryptography
Date: Sat, 27 Feb 1999 12:29:48 GMT
Reply-To: [EMAIL PROTECTED]
On 26 Feb 1999 13:24:37 GMT, [EMAIL PROTECTED] (Coen Visser)
wrote:
>Quantum computers can factorize faster than conventional computers. However
>in general[*] they reduce the time complexity of a problem with just a square
>factor. So if today a 128 bit key would be sufficiently secure, a 256 bit key
>could be secure even when quantum computers are available.
Shor's quantum factoring algorithm is exponentially faster. I believe
you are referring to Glover's database algorithm.
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: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Quantum Cryptography
Date: Sat, 27 Feb 1999 12:39:26 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 27 Feb 1999 02:51:23 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>> "Moreover, the United States govternment is quietly funding research
>> in code-breaking, using quantum computers".
>So? It would be criminally negligent to ignore potentially relevant
>technology.
Hey, I am all for it. Better our govt than someone else.
The govt is the only entity that can afford to develop such
contraptions - what with an inexhaustable supply of other people's
money.
>Actually, quantum computing is a fairly hot research topic in the
>public sector. The basic notion is to obtain massive parallelism
>by encoding quantum states.
That's David Deutsch's original notion, and has been replaced by true
quantum computing, which not only takes advantage of massively
parallel superpositions (Deutsch's original notion) but also quantum
interference. It is quantum interference that makes the quantum
computer remarkable.
>I think there was a Sci.Am. article on
>this not too long ago, or I'm sure a Web search would turn up info.
As I have mentioned several times on sci.crypt, I recommend the book
entitled "Explorations In Quantum Computing" by Colin Williams and
Scott Clearwater. There are others, as you will discover if you visit
amazon.com.
But this book has a CD which has programs to run simulations. You can
actually see it factor (small) numbers on a probabilistic basis
running Shor's algorithm in simulation.
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: "Robert C. Paulsen, Jr." <[EMAIL PROTECTED]>
Subject: Question on Pentium III unique ID
Date: Sat, 27 Feb 1999 06:43:21 -0600
Perhaps I am missing something.
Many (most?) sustems today already have a unique ID that is software
accessible -- the MAC address of the network card.
In what way does the Pentium III add any additional privacy concern?
--
Robert Paulsen http://paulsen.home.texas.net
If my return address contains "ZAP." please remove it. Sorry for the
inconvenience but the unsolicited email is getting out of control.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Sat, 27 Feb 1999 13:03:18 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 27 Feb 1999 03:26:53 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Maximum likelihood is a standard goal (there are others) for
>estimation of model parameters: determine the parameters that
>maximize the likelihood of the observed training data.
I believe that is covered in Li & Vitanyi's book on Kolmogorov
Complexity. Maximum likelihood is the thing that drives pac-learning,
by making the "best" result be the simplest computationally.
>> Would you recommend a book that is accessible to the Informed Layman?
>I don't know what an Informed Layman is,
An Informed Layman (tm) is someone who is reasonably well versed in a
subject but is not a practitioner. He is like the dilettante student,
not pursuing a subject for any reason other than personal enjoyment.
IOW, a Professional Amateur (tm).
>but if you have a good
>foundation in mathematics,
Would a Ph.D. in Physics suffice - in your humble estimation?
>try Frederick Jelinek's "Statistical
>Methods for Speech Recognition" (MIT Press, 1997).
The amazon.com listing shows January 1999 as the publication date, yet
there is no mention of a 2nd edition. Whatever - I shall order it from
the library.
As they say down Texas way, "GrassyAss, Senyor".
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: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Sat, 27 Feb 1999 13:07:04 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 27 Feb 1999 03:33:16 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>> Hidden Markov models are far too recent to be in Feller's book.
>> And even later probability textbooks might not have this.
>The first open-literature publication of HMMs (known then as
>"probabilistic functions on Markov chains") was around 1967.
>The first edition of Feller's book was, if I recall correctly,
>published well before that, and I don't know how extensive
>the revisions were for later editions. It may well be that
>many textbook authors didn't appreciate their significance.
A trip to amazon.com will inform you that the 3rd edition of Feller's
book involved major revisions:
+++++
The publisher, John Wiley & Sons:
Major changes in this edition include the substitution of
probabilistic arguments for combinatorial artifices, and the addition
of new sections on branching processes, Markov chains, and the De
Moivre-Laplace theorem.
+++++
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: [EMAIL PROTECTED] (Marc Hoeppner)
Subject: Re: Any idea what this might be???
Date: Sat, 27 Feb 1999 12:26:02 GMT
Reply-To: [EMAIL PROTECTED]
>What leads you to believe it's simple? I don't see any obvious patterns
>in the output. The top three output bytes by frequency are all printable,
>but that's well within chance expectations, and none of the frequencies
>seems out of line with expectations from random.
>
>So far I don't see anything that would contradict an assumption of a
>normal block cipher or hash: no interesting repeats, reasonable
>distribution with the high bit, and so on.
>
>More info?
You are right, it seems to be cipher like DES. A friend of mine sent
the program to me for a challenge and I falsely believed that it would
be a simple alphabet exchange, so I got stuck when I tried the test
data that I included. Do agree that it could be DES? - And do you know
of any freeware C/C++ source code that I could use to try to find the
key? - Many thanks in advance.
Marc
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness
Date: Sat, 27 Feb 1999 13:21:24 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 27 Feb 1999 06:29:54 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
>I think an understanding of Markov processes is absolutely
>fundamental to any discussion of "randomness,"
I am beginning to think that *everything* in science and mathematics
is fundamental to a discussion of randomness.
>and an understanding of
>hidden Markov models is crucial to any discussion of whether one can
>determine if a given bitstream is "random."
I'm sold, at least for now. I thought I might find the Truth about
randomness in Kolmogorov Complexity, but alas, that's not it.
>Similarly, I think that
>likelihood is (or ought to be) central to any estimation process, and
>any inference about a bitstream that you would derive from it.
That I agree with. The induction schemes I read about with regard to
complexity theory rely on the likelihood of the simplest description
to produce the most probabily approximately correct result.
>But you will find that the books written about hidden Markov models
>are almost all about speech processing, and the books about likelihood
>are all about parameter estimation. They won't be directly applicable,
>but the ideas contained in them will. You might try:
>Elliott, Aggoun, and Moore, Hidden Markov Models : Estimation and
>Control (Applications of Mathematics, Vol 29); Springer Verlag; ISBN:
>0387943641
>MacDonald and Zucchini, Hidden Markov and Other Models for
>Discrete-Valued Time Series (Monographs on Statistics and Applied
>Probability, 70) Chapman & Hall; ISBN: 0412558505
Those two authors need to open a vegetarian hamburger stand, eh.
>Sinclair, Algorithms for Random Generation and Counting : A Markov Chain
>Approach (Progress in Theoretical Computer Science) Birkhauser; ISBN:
>0817636587
>Edwards, Likelihood; Johns Hopkins Univ Pr; ISBN: 0801844436
>(this one is good in that it explains pretty well the philosophical
>foundations of likelihood and the difference between likelihood and
>probability).
>Parametric Statistical Models and Likelihood; Springer Verlag; ISBN:
>3540969284
>Eliason, Maximum Likelihood Estimation : Logic and Practice (A Sage
>University Papers Series : Quantitative Applications in the Social
>Sciences, No 96) Sage Pubns; ISBN: 0803941072
That ought to keep the interlibrary loan department busy for a few
months.
Thanks for the references.
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: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Testing Algorithms [moving off-topic]
Date: Sat, 27 Feb 1999 13:29:06 GMT
Reply-To: [EMAIL PROTECTED]
On 26 Feb 1999 15:32:19 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>The force can be arbitrarily small (at least under the classical physics
>approximation appropriate to this oversimplification).
>
>Dragging out freshman physics :
>
>Force * time = mass * velocity change
>
>Applying any non-zero force *will* result in a velocity change, which
>is sufficient to cause the brick to move (absent friction).
>
>The limiting case of a sufficiently small non-zero number is zero.
>
>Q.e.d.
The force field must be conservative or the process is not reversible.
If the process is not reversible, then energy is consumed.
>Oh, you mean you think that lubrication technology will never improve
>over 1999 levels?
I thought superfluid liquid helium was not viscous.
Why not just build this contraption with photons and be done with it.
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: Legal procedures for using third party crypto?
Date: Sat, 27 Feb 1999 06:30:40 -0100
[EMAIL PROTECTED] wrote:
> My question is do we have to apply for
> export license with the commerce department (even if it is within
> the legal 56bit length)?
Yes.
This is why Java doesn't come with any "default" crypto module. You
have to plug it in and then do all the paperwork yourself.
> If so, I read that we have to submit code to them for review.
Yes.
> How does this work if we really haven't written the crypto stuff (we
> just access the well-known java "wrappers")? Isn't plugable crypto
> against the law to export (e.g. someone in another country can just
> remove the 56bit stuff and put in 128bit)?
>
They'll mainly be looking to make sure that your crypto is the
strength you claim. If you claim 56 bits than you have to show
really is 56 bits and not a bit more...
Pluggable crypto is a very grey area. You'll have to ask the US
Gov. for written advice on this (and make sure all paperwork is
signed by a high up person, not the guy in reception).
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Testing Algorithms
Date: Sat, 27 Feb 1999 13:49:32 GMT
Reply-To: [EMAIL PROTECTED]
On 26 Feb 1999 15:25:40 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>there's no bound in basic physics, even
>allowing for quantum effects, on the length of time that a pendulum can
>swing.
I would imagine as the Universe expands, it might affect the pendulum
in some irreversible way.
<idle speculation>In the limit of zero gravitation, the pendulum
becomes a rigid rotator. If gravity returns for some reason, then it
no longer behaves as a classic pendulum. I suspect it behaves as a
chaotic system, shifting between the two modes. But that would require
that gravity be nonconservative.</idle speculation>
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: [EMAIL PROTECTED] (Myself)
Subject: Re: Question on Pentium III unique ID
Date: Sat, 27 Feb 1999 13:52:19 GMT
On Sat, 27 Feb 1999 06:43:21 -0600, thermal and electromagnetic action
caused "Robert C. Paulsen, Jr." <[EMAIL PROTECTED]>'s brain to
produce the following pseudorandom thought:
>Many (most?) sustems today already have a unique ID that is software
>accessible -- the MAC address of the network card.
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.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Quantum Randomness
Date: Sat, 27 Feb 1999 16:11:31 GMT
Reply-To: [EMAIL PROTECTED]
We believe that the strongest kind of randomness is that which is
generated in Quantum Mechanical processes before the collapse of the
statevector. Therefore, if you were able to generate random sequences
with a Quantum Computer, they would be certifiably random in the sense
that the OTP ciphers you constructed with them would be proveably
secure - not approximately secure, but completely secure.
I am getting this straight out of a book I am not reading called
"Explorations In Quantum Computing" by Colin Williams and Scott
Clearwater". It is a book that is accessible to the Informed Layman
(tm).
Chapter 7 is entitled "True Randomness" and the quote on my sig line
below comes from the chapter heading. Here are some interesting
comments about randomness from the point of view of quantum physics.
The '*' asterisk indicates enphasis supplied by the authors, not me.
+++++
"Today our best description of Nature is in terms of quantum physics.
Quantum physics, as we currently understand it, relies heavily on the
concept of randomness."
[...]
"... a classical computer can only *pretend* to generate a random
number whereas a quantum computer can *actually* generate a random
number."
[...]
"... there is no such thing as *a* random number. It only makes sense
to talk about processes for generating sequences of random numbers."
[...]
"... we are faced with the question of whether a particular sequence
of numbers has the *appearance* of being random. Fortunately, there
are statistical tests that can answer this question."
[...]
"The art in creating computer programs that simulate the generation of
true random numbers is to devise algorithmic methods that generate
sequences of numbers that pass both the distribution test and
correlation checks. As we show, even when random number generators
pass such statistical tests, the sequence of numbers it generates may
still not be random enough to serve as an approximation to a true
random process."
+++++
There you have it - things that we have been saying all along are now
available in print from Practicing Physicists.
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
------------------------------
Date: Sat, 27 Feb 1999 17:43:00 +0100
From: Federico Ulivi <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Skipjack anyone?
Does anyone know of a publicly available description
of Skipjack algorithm? I'm evaluating various block algorithms
for a program of mine..
Any help appreciated.
Thanx in advance.
Federico Ulivi
Milan - Italy
------------------------------
Date: 27 Feb 1999 16:39:45 -0000
From: iLLusIOn <[EMAIL PROTECTED]>
Subject: 16Bit RC4
=====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.
Does this increase of keysize somehow weaken the original RC4 algorithm?
TIA for any comments and suggestions.
~~~
This PGP signature only certifies the sender and date of the message.
It implies no approval from the administrators of nym.alias.net.
Date: Sat Feb 27 16:39:43 1999 GMT
From: [EMAIL PROTECTED]
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQEVAwUBNtgf0E5NDhYLYPHNAQG5Swf/S3PvlmwBtZRyq03e+Gt0dbZ6QiOcg5qu
FxhFxarUuVNkigVhEqoT83HLyqP6Wrd2tzfbQXXmts3b0YZZmMnRwtGfsiwT+Rg7
d/deTNFQCWLG0344P6WspDtwx5MF3vosgPMzEcPAxCBWZ0u20hIKkVco11fIDKkS
BJUbWf+KsF1ikQMFAhMiKvVSPCP0eSvWqr5ng6MkIS9JL7fHhne/BswE8XXSMpPL
2vx6KNRfiMjRPIoOzibbmIWjh8ADWSmgrKA9X7pnyQu8d4483DMkfCxcGUPHDzHg
8VVwTQcy5MAAAKDkli515H334cT8X8y0GOE3ne7hZUdrUS+QUq8kdw==
=ijNW
=====END PGP SIGNATURE=====
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms
Date: Sun, 28 Feb 1999 03:14:19 +0100
"R. Knauer" wrote:
>
> On Fri, 26 Feb 1999 19:30:24 GMT, Doggmatic <[EMAIL PROTECTED]>
> wrote:
>
> >Any state change in this universe causes entropy to increase and
> >takes a GREATER THAN ZERO amount of energy.
>
Correct - TANSTAAFL.
> Not for reversible processes.
>
Is it time to ask Bob for his peculiar definition of "reversible
process"...
--
<\___/>
/ 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
******************************
