Cryptography-Digest Digest #899, Volume #8 Wed, 13 Jan 99 14:13:02 EST
Contents:
(fwd) Press release - The Crypto Controversy : no problem (Mok-Kong Shen)
Re: Help: a logical difficulty ("Arthur N. Klassen")
Re: Practical True Random Number Generator ("hapticz")
Re: On the Generation of Pseudo-OTP (Patrick Juola)
Re: Metaphysics Of Randomness (Patrick Juola)
Re: Practical True Random Number Generator (Mok-Kong Shen)
Re: Metaphysics Of Randomness (R. Knauer)
Re: Metaphysics Of Randomness (John Savard)
Re: What is better : Blowfish, Des, Tripple-Des (Doug Stell)
Cayley-Purser algorithm? ([EMAIL PROTECTED])
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: Metaphysics Of Randomness (Mok-Kong Shen)
Re: Cayley-Purser algorithm? (William Whyte)
Re: On the Generation of Pseudo-OTP ("Trevor Jackson, III")
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: Practical True Random Number Generator (R. Knauer)
Re: HIGH ENTROPY ENCRYPTION IS A MUST!! (Volker Hetzer)
Re: On the Generation of Pseudo-OTP (John Briggs)
Faster RSA by 16 years old girl ? (Emmanuel Mogenet)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: (fwd) Press release - The Crypto Controversy : no problem
Date: Wed, 13 Jan 1999 17:26:24 +0100
Press release - please spread widely
===========================
The Crypto Controversy: no problem
===========================
Tilburg, the Netherlands, 13 January 1999
The Dutch government should do nothing about the problem that
cryptography poses to law enforcement. All available options have more
negative than positive consequences. This is the conclusion of
Bert-Jaap Koops in his recently published Ph.D. thesis "The Crypto
Controversy". Although encoding programs potentially leave
law-enforcement powerless to wiretap communications and to conduct
computer searches, there is not a real solution to retrieve the keys
to decipher encoded data.
Koops, author of the Crypto Law Survey website, conducted a four-year
research at Tilburg University and Eindhoven University of
Technology. He analyzed the conflict of interests that cryptography
poses to society. On the one hand, encryption is crucial for
information security and for protecting privacy, but on the other
hand, it enables criminals to escape the scrutiny of law enforcement.
Governments are trying hard to address this conflict of interests,
but their proposals for regulation have been controversial. The
policy debate is polarized, with privacy activists and
law-enforcement agencies fiercely opposing each other's point of
view.
To address this crypto controversy, Koops discusses four possible
solutions: building-in Law-Enforcement Access to Keys (LEAK systems),
demanding suspects to decrypt, using alternative investigation
measures, and doing nothing. The first option is flawed, because
secure LEAK systems are not yet available, and criminals will anyway
not use crypto which they know to contain a backdoor for the police.
The second option, demanding suspects to decrypt, yields only very
limited opportunities, because of the privilege against
self-incrimination. Alternative investigation measures, such as using
directional microphones and intercepting radiation from computer
screens, can provide some leeway for the police if wiretaps lose
their efficacy, but they are serious infringements of people's
privacy.
Koops concludes that, for the time being, the "zero option"
is preferable: governments should decide upon a policy to do nothing
about the crypto problem. To meet developments in crime and
cryptography, this policy should be reviewed periodically. "Perhaps
the government will slowly have to adapt to the idea that wiretapping
is not a panacea for the information need of the police."
As Koops suggests: "if there is no solution, there is no problem
either." Rather than continue to worry over the crypto controversy,
the government should concentrate its energy and resources on other
pressing social issues which it can address.
==========================
Publication details
==========================
Bert-Jaap Koops, The Crypto Controversy. A Key Conflict in the
Information Society. The Hague / London / Boston, Kluwer Law
International, 1999, 301 pages, ISBN 90 411 1143 3.
A summary and ordering information are available at
http://cwis.kub.nl/~frw/people/koops/thesis/thesis.htm
=========================
Curriculum vitae
=========================
Bert-Jaap Koops (1967) studied mathematics and
literature at Groningen University. After working for Amnesty
International for two years, he started a Ph.D. research at Tilburg
University and Eindhoven University of Technology at the faculties of
law, mathematics and technology management. Since October 1998, he is
a senior research fellow at the Centre for Law, Public Administration
and Informatization of Tilburg University.
Koops is editor of the Dutch reference book Recht &
informatietechnologie. Hij co-edited a book on Emerging Electronic
Highways and has published widely on crypto regulation, computer
crime, and Trusted Third Parties. He maintains an extensive worldwide
survey of crypto laws on the Internet.
=============================
Bert-Jaap Koops <[EMAIL PROTECTED]>
Tilburg University
13 January 1999
------------------------------
From: "Arthur N. Klassen" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: Wed, 13 Jan 1999 16:27:51 GMT
Gurripato (x=nospam) wrote:
>
> On Tue, 12 Jan 1999 08:23:11 -0700, "Tony T. Warnock"
> <[EMAIL PROTECTED]> wrote:
> >
> >It's worse in Spanish, Coahuila comes before Chihuahua. It is the
> >responsibility of the program to get it right, not the users. Violation of
> >this principle contributes the distrust of computers.
>
> It is not a software problem. In Spanish, "ch" represents a
> sound, and is not considered as c+h, but as a single entity. Get a
> Spanish dictionary, and the words will be arranged as a,b,c,ch,d,e...
Actually it -is- a software problem, an internationalization of software problem, as
both Ken and Mike have so aptly pointed out -- which incidentally, doesn't have
anything to do with cryptography, does it?
(Incidentally, to this day, Canadian telephone directories put Mc/Mac in a section of
their own between L and M -- we're not all Scots and Irish, but we've got enough of
'em over here that this was a necessity)
cheers...ank
--
[EMAIL PROTECTED] <*> Who are you? What do you want? Do you
have anything worth living for? ... Answer these, if only to yourself!
PGP: **** 2047/DCDF9341:E273 AD0E F99A 8869 050B 5E92 0E47 C151 **** two
finger- *** 30DF 376C 43D0 DA74 F33F 752C 192E 3711 5E52 02BF *** prints
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Date: Wed, 13 Jan 1999 11:26:18 -0500
reminds me of particle decay tubes we used to optically observe in high
school classes to learn abt radioactivity.
--
best regards
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: On the Generation of Pseudo-OTP
Date: 13 Jan 1999 10:14:57 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 13 Jan 1999 13:29:28 GMT, [EMAIL PROTECTED] (John Briggs)
>wrote:
>
>>If you pick the number first, then the compression algorithm then
>>you can compress down to arbitrarily small sizes.
>
>Not if you must use that algorithm to reproduce the number, as is
>required in Chaitin's algorithmic complexity theory. Reduction is one
>criterion and reproducibliity is another.
Not if the size of the *algorithm* isn't included in the size of
the ``compression.''
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 13 Jan 1999 10:27:51 -0500
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>R. Knauer wrote:
>>
>> Consider this statement from Greg Chaitin's book "The Limits Of
>> Mathematics":
>>
>> "Most people believe that anything that is true is true for a reason.
>> These theorems show that some things are true for no reason at all,
>> i.e., accidentally, or at random."
>
>> Consider a TRNG (True Random Number Generator) based on the decay of a
>> radioisotope. The output of that TRNG depends on when a particular
>> nucleus decays, which as we know from Quantum Mechanics is completely
>> random in time. That is, the probability that a nucleus will decay in
>> the interval t -> t + dt is a constant independent of the time t - a
>> nucleus can decay *anytime* with equal probability related to the
>> reciprocal of the half-life.
>>
>> Therefore one cannot give an algorithmic reason for why it does decay
>> at any one particular time, because there is no calculable reason why
>> it decayed then. Put another way, there is no algorithm that
>> significantly lowers the complexity of the number that represents the
>> time of decay. It just "accidentally" decays at any time for no
>> algorithmic reason whatsoever.
>
>How about the time series of temperature at a particular location
>and the time series of the price of a certain stock at New York.
>Are there 'algorithmic reasons' for these? Are they therefore
>truly random and hence useful for secure encryption?
Well, temperature at a particular location is *certainly* predictable
to some extent -- it will be colder at 3am than at 3pm, colder in
January than in June (assuming Northern Hemisphere) and if you want
to use a more sophisticated model, talk to the backroom boys at
the National Center for Atmospheric Research. You could certainly
get *some* randomness out of the temperature, but not necessarily enough.
Ditto the stock market. There are lots of folks that claim to have
a system to predict the market based on some sort of algorithmic
principles. I don't know whether they really *do* -- but I do know
that I drive a ten year old Dodge and they drive new Lexuses....
-kitten
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Date: Wed, 13 Jan 1999 16:46:34 +0100
KloroX wrote:
>
> The point mentioned in the original post is that the half-life is
> finite, and therefore the interval t1 between decay 1 and 2 is
> slightly shorter (statistically) than the interval t2 between decay 2
> and 3. Thus, the result is slightly biased toward 0 if one generates a
> 0 whenever t1 < t2. Reversing the rule in 50% of the measurements
> removes this bias.
>
> As already mentioned, the bias in the original procedure is very small
> if t1 and t2 are short (milliseconds) and the half-time long (hundreds
> of years or more). The above fix is only of theoretical interest in
> such a case.
Thank you for clarifying a point that I have been arguing with
Knauer. (I read this post of yours too late.)
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Wed, 13 Jan 1999 15:49:45 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 13 Jan 1999 16:13:22 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>How about the time series of temperature at a particular location
>and the time series of the price of a certain stock at New York.
>Are there 'algorithmic reasons' for these? Are they therefore
>truly random and hence useful for secure encryption?
The temperature is not completely random nor is the stock market
because they cannot be just any possible value. The current value is
correlated to the previous value, unless either a nuclear device has
been just detonated - in which case there is a random change in the
local temperature - or the market crashes precipitously - in which
case there is a random change in the market value of stocks.
But your question is a good one in general - do you have any answers?
Most physicists believe that Quantum Mechanics describes indeterminate
random events in the subatomic world. But there are a few noteworthy
physicists who believe otherwise - Einstein among them ("God does not
play dice.")
Mathematical Indeterminancy, like the theory of Greg Chaitin, is on
the leading edge, so it is anyone's guess what lies in store. In fact
it could be said that the answer to your question in general is itself
a random output. If you really want to know the best answer possible
at this time, flip a coin.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Metaphysics Of Randomness
Date: Wed, 13 Jan 1999 17:09:00 GMT
[EMAIL PROTECTED] (R. Knauer) wrote, in part:
>That means that almost all of classical cryptography (the OTP being
>the sole exception) is not about security but is about obscurity,
>because if the cryptanalyst were able find the "reason" behind your a
>given encyption scheme, either formally or experimentally, he could
>break the cipher.
I wouldn't dismiss the value of "work factor" so quickly.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (Doug Stell)
Subject: Re: What is better : Blowfish, Des, Tripple-Des
Date: Wed, 13 Jan 1999 16:15:30 GMT
On Wed, 13 Jan 1999 06:46:50 GMT, [EMAIL PROTECTED] wrote:
> Actually the AES candidateS that are replaCements for the NSA clipper
>are just trojan horse routines that the NSA is trying to force
>on the public.
This inflamatory statement attacks the reputations of many of the best
professional cryptographers in business today.
The AES candidates are all submissions FROM the open community TO
NIST. NSA isn't forcing anything on the public via the candidates. NSA
does, of course, provide support and expertise to NIST in the
evaluation of the candidates. Whether or not they exercise any unfair
influence over NIST remains to be seen, but would be pretty hard to
hide, given the very public nature of the selection process.
BTW, clipper is not an algorithm. Clipper's tamper-proof concepts and
key recovery mechanism for some variants thereof could be and are used
with many other algorithms. The fact that the mechamism was associated
with a particular algorithm suite for a while does not reflect on
value of the algorithms in that suite. They remain trusted for use
where most commercial algorithms would not be trusted.
These points indicate that the author to whom I reply understands
neither the AES effort. the roles of the NSA nor cryptography in
general.
> The entropy in them is way to small to guarantee
>safe secure encrypted message exchanges over the internet and
>should not be trusted.
Nonsense. The security is in the key, given a decent algorithm. Most
or all of the AES candidates are very decent algorithms.
>Professional thorn in the side to fishy weak encryption methods!
One's professionalism or lack thereof is made known by one's behaviors
in the professional community. Insults, profanity, arrogance, wild
claims and other rantings is most unprofessional.
doug, with 20 years professional experience in cryptography
------------------------------
From: [EMAIL PROTECTED]
Subject: Cayley-Purser algorithm?
Date: Wed, 13 Jan 1999 16:13:24 GMT
There's an article on the BBC News website talking about some new encryption
algorithm invented by a schoolgirl. She calls it Cayley-Purser. No algorithm
details were given but all sorts of claims were made about how it's going to
revolutionize e-mail security.
They never bothered to mention if it's a public-key algorithm. They just said
it's thirty times faster than RSA (which isn't very impressive for private-key
algorithms).
Does anyone have any details on this, or am I right in guessing the
significance of the fact that this girl is from Blarney?
The page this was reported on was:
http://news.bbc.co.uk/hi/english/sci/tech/newsid_254000/254236.stm
Rick Miller
http://www.execpc.com/~rdmiller/
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Wed, 13 Jan 1999 12:27:14 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Mon, 11 Jan 1999 21:41:59 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >Now my sub-atomic physics was never great, but it appears that there will
> >always be a way to mess up "perfectly random" events.
>
> Proper design would take all that into account, byshielding for
> example.
Shielding? Against neutrinos? You cannot be serious! The 50% absorption
value for lead is 6 trillion miles or so.
Are we shielding with neutroniun? If so, that's the surface gravity of the
device we're protecting? A 1' sphere (no other shape is possible) runs arounf
1e7 m/s/s IIRC.
> >Now the key question:
> >Do we know for a fact, or can we prove, that no *natural* phenomena can
> >influence our TRNG in such a manner as to induce regularities.
>
> Nope. But stay tuned because I hear that hidden variable theories are
> making a comeback.
Good. I always liked Clue.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Wed, 13 Jan 1999 18:29:24 +0100
Patrick Juola wrote:
>
> Well, temperature at a particular location is *certainly* predictable
> to some extent -- it will be colder at 3am than at 3pm, colder in
> January than in June (assuming Northern Hemisphere) and if you want
> to use a more sophisticated model, talk to the backroom boys at
> the National Center for Atmospheric Research. You could certainly
> get *some* randomness out of the temperature, but not necessarily enough.
>
> Ditto the stock market. There are lots of folks that claim to have
> a system to predict the market based on some sort of algorithmic
> principles. I don't know whether they really *do* -- but I do know
> that I drive a ten year old Dodge and they drive new Lexuses....
That's why I guess the claim of Chaitin as described by Knauer
is questionable, at least to some extent.
M. K. Shen
------------------------------
From: William Whyte <[EMAIL PROTECTED]>
Subject: Re: Cayley-Purser algorithm?
Date: Wed, 13 Jan 1999 17:53:28 +0000
Hi,
I sent this message to ukcrypto and cryptography earlier today, so apologies to
those of you who are bored by it.
[EMAIL PROTECTED] wrote:
>
> There's an article on the BBC News website talking about some new encryption
> algorithm invented by a schoolgirl. She calls it Cayley-Purser. No algorithm
> details were given but all sorts of claims were made about how it's going to
> revolutionize e-mail security.
>
> They never bothered to mention if it's a public-key algorithm. They just said
> it's thirty times faster than RSA (which isn't very impressive for private-key
> algorithms).
>
> Does anyone have any details on this...
Yes, I do. it is a public key algorithm, and it's based on work that
Sarah did with us in Baltimore Technologies in Dublin when
she was here on a student work placement last March. We've been
looking at algorithms based on 2x2 matrices for a while and
gave her the idea to see what she could do with it.
The idea we were working on was to use 2x2 matrices with entries
modulo n, n the product of 2 primes (ie an RSA number). The
security is therefore exactly the same as the security of an RSA key with
the same modulus. However, the encryption and decryption processes
require only a small number of matrix multiplications rather than
modular exponentiation, so both public-key operations (16 multiplications
over the finite field) and private-key operations are as fast as a
normal RSA private-key operation (17 multiplications). The downside
is that both the key and the ciphertext are about eight times the
length of the modulus, rather than more-or-less the length of the
modulus as with RSA.
That was our idea, anyway. I haven't had time to look at Sarah's
project in great detail so I don't know how far (or even whether)
she's taken it beyond where we had it.
Sarah, by the way, is level-headed enough to know that new public-key
algorithms only made you millions if you invented them in the Seventies.
Her real problem is trying to stop the journalists talking up the
stupid parts of the story while still emphasising that there's a real
story in there.
Cheers,
William
=============================================================================
William Whyte, Senior Cryptographer, Baltimore-Zergo
Zergo & Baltimore Technologies merge in $55m deal !
The new company name will be "Baltimore"
See Baltimore at Stands 235 & 425
RSA Data Security Conference, 17-21 Jan '99
Baltimore Ltd, IFSC House, International Financial Services Centre,
Custom House Quay, Dublin 1, Ireland.
Tel. +353 1 605 4399 Fax. +353 1 605 4388
Email: [EMAIL PROTECTED]
Website http://www.baltimoreinc.com/
Baltimore - Global e-Security
------------------------------
Date: Wed, 13 Jan 1999 12:30:17 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
R. Knauer wrote:
> On Wed, 13 Jan 1999 14:59:01 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >> The statement you made above has been challenged many times before.
>
> >Please give a pointer to literature. I'll be interested to know more
> >of the issue.
>
> I already have, several times in fact.
>
> I would recommend you start with Hofstedter's "Godel, Escher, Bach",
> then read Roger Penrose's two recent book, then study Greg Chaitin's
> papers. Although that is certainly far from exhaustive, each is
> accessible to the layman.
Which of Penrose's books are you pointing to? The last I read, on AI, was
incredibly brilliant. But wrong.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 18:55:28 +0100
R. Knauer wrote:
>
> On Wed, 13 Jan 1999 14:59:01 +0100, Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
>
> >> The statement you made above has been challenged many times before.
>
> >Please give a pointer to literature. I'll be interested to know more
> >of the issue.
>
> I already have, several times in fact.
>
> I would recommend you start with Hofstedter's "Godel, Escher, Bach",
> then read Roger Penrose's two recent book, then study Greg Chaitin's
> papers. Although that is certainly far from exhaustive, each is
> accessible to the layman.
>
> There are several other books to read, but if you read those you will
> get the general idea. Another area tp keep in mind is Fuzzy Set Theory
> (see Bart Kosko, "Fuzzy Thinking" for a layman's book and G. J. Klir
> and B. Yuan, "Fuzzy Sets and Fuzzy Logic", for a hardcore treatment)
> which is just emerging on the scene.
This point (due to some misunderstanding of mine or yours) is
rendered unnecessary by what follows.
>
> > Absolute assertions are possible if they are deduced from axioms
> > by logical rules.
>
> What do you mean by an assertion being "possible" - do you mean that
> it is true?
I mean it is only through deduction in a logical system can one obtain
absolute assertions (in distinction to relative, fuzzy, assertions)
which have the value true in the particular logical system (with
the particular set of axioms) one has. There may be other absolute
assertions that are true but that are not deducible from the
logical system one has at hand and hence one will not be able to
know either of their existence or of their truth value. (These
are simply outside of one's capability, so to say.)
>
> >This means if you find a true absolute assertion then it must have
> >been deduced from axioms by logical rules.
>
> No! You still miss the point. There are assertions that are true which
> cannot be proven using logical rules.
See above. No disagreement.
>
> For example, a given computer program either halts or it does not
> halt, but you cannot prove which it does using logical rules. The only
> way you can know is to run it, and if it halts you know that it halts,
> and if it doesn't halt then you suspect it might never halt.
>
> You could analyze it with your mind, but even that is not infallible,
> as most of the code from MicroShaft demonstrates so convincingly.
>
> >This does NOT imply that
> >all true absolute assertions CAN be deduced from axioms by logical
> >rules.
>
> I am confused. You seem to be saying the same thing and its
> contradictory opposite.
Well, I suppose one of Goedel's theorem amounts to saying that there
are always matters that can't be proved by a given axiom system.
>
> What makes "a true absolute assertion" (statement one above) any
> different from "all true absolute assertions" (statement two above)?
If you have two axiom systems A and B, such that A is a subset
of B, then you will be able to deduce from B more numbers of
interesting assertions than you can do in A. Certainly if you stick
to A then you know only a smaller amount of things. One should
always be aware that one has only a limited view. One does not
know everything (like God). This is roughly what I wanted to express.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Wed, 13 Jan 1999 18:49:01 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 13 Jan 1999 16:46:34 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>> The point mentioned in the original post is that the half-life is
>> finite, and therefore the interval t1 between decay 1 and 2 is
>> slightly shorter (statistically) than the interval t2 between decay 2
>> and 3. Thus, the result is slightly biased toward 0 if one generates a
>> 0 whenever t1 < t2. Reversing the rule in 50% of the measurements
>> removes this bias.
>> As already mentioned, the bias in the original procedure is very small
>> if t1 and t2 are short (milliseconds) and the half-time long (hundreds
>> of years or more). The above fix is only of theoretical interest in
>> such a case.
>
>Thank you for clarifying a point that I have been arguing with
>Knauer. (I read this post of yours too late.)
I remind you to read my subsequent post where I comment that it is
good design practice to put in anti-bias provisions regardless of the
perceived necessity.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: HIGH ENTROPY ENCRYPTION IS A MUST!!
Date: Wed, 13 Jan 1999 19:09:34 +0100
Alan DeKok wrote:
> Is there a standard metric for measuring bias?
Depends on what you want to sell...
(sorry, couldn't resist)
Volker
------------------------------
From: [EMAIL PROTECTED] (John Briggs)
Subject: Re: On the Generation of Pseudo-OTP
Date: 13 Jan 1999 18:16:49 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (R. Knauer)
writes:
>On 12 Jan 1999 21:24:04 GMT, [EMAIL PROTECTED] (John Briggs)
>wrote:
>
>>All the infinite digits of pi can be easily compressed into just
>>two ASCII characters: "pi". They can even be compressed further
>>than that.
>
>But having done so, you cannot reproduce the actual number.
Sure I can. I can create a Turing maching that, on input "pi" produces
each digit of pi in turn. It can't create all the digits in finite time.
But it can produce any arbirarily large finite leading substring in finite
time.
Note that this is more than the problem statement requires. Nobody
said that either the compression or decompression had to be computable.
>If you had read Chaitin's papers you would know that was a
>requirement.
No. It is not a requirement. We're dealing with your problem
statement. Not Chaitin's.
Suppose hypothetically, the algorithmic complexity of pi is 12364.
That is, there is an algorithm whose size (when expressed in some
predefined programming language) is 12364. This algorithm produces pi
from null input. No other algorithm whose size (when expressed in
that same programming language) is less than 12364 can generate
pi from null input.
OK so far?
This does not mean that pi cannot be compressed to a representation
that is shorter than 12364. It means that pi cannot be compressed
to a program shorter than 12364 written in a specific programming
language.
Nothing keeps someone from representing pi as a much shorter program
written in an entirely different language or as a much shorter input
string using an entirely different decompression algorithm.
John Briggs [EMAIL PROTECTED]
------------------------------
From: Emmanuel Mogenet <[EMAIL PROTECTED]>
Subject: Faster RSA by 16 years old girl ?
Date: Wed, 13 Jan 1999 09:57:54 -0800
http://news.bbc.co.uk/hi/english/sci/tech/newsid_254000/254236.stm
Anyone's got more precise info ?
------------------------------
** 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
******************************
