Cryptography-Digest Digest #566, Volume #10 Sun, 14 Nov 99 17:13:02 EST
Contents:
Re: Need technique for about 24 bytes (wtshaw)
Re: Codebook examples on Web? (Quisquater)
Re: What's gpg? <PHILOSOPHY 101> (Tim Smith)
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Elliptic-curve cryptography (kingtim)
thanks for all (Henri)
Re: Public Key w/o RSA? ("Douglas A. Gwyn")
Re: Ultimate Crypto Protection? ("Douglas A. Gwyn")
Re: intelligent brute force? ("Douglas A. Gwyn")
Re:SCOTT16U SOLUTION ON THE WEB (Gondolin Remailer)
Patent on general public-key concept? (Charles Blair)
Re: Elliptic-curve cryptography (Tom St Denis)
Re: Quantum Cracking (Tom St Denis)
Re: Patent on general public-key concept? (DJohn37050)
Re: S/MIME plug-in for Eudora? Strong Encryption (Bruno Wolff III)
Re: Need technique for about 24 bytes (SCOTT19U.ZIP_GUY)
Re: Quantum Cracking ("Gary")
Re: Bracking RSA Encryption. Is it possible. (David A Molnar)
Re: Patent on general public-key concept? (Quisquater)
Re: The Code Book (Tim Tyler)
Re: Codebook examples on Web? (HJS)
Re: Ultimate Crypto Protection? (HJS)
Breaking Enigma using modern technology? (Nogami)
Re: Proposal: Inexpensive Method of "True Random Data" Generation (Coen Visser)
Re: Proposal: Inexpensive Method of "True Random Data" Generation (Coen Visser)
Re: Breaking Enigma using modern technology? (JPeschel)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Need technique for about 24 bytes
Date: Sun, 14 Nov 1999 00:59:31 -0600
In article <80jq8m$214i$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:
> You could use my "conditional one to one adaptive huffman compressor"
> that is at my site to compresss the string to a smaller size and then compress
> the resulting binaray file with scott16u ( or even scott4u if a 40 bit key is
> OK) then you can convert the resulting string back to a base 36 character set
> using the conditional uncompressor. This does what you want except that the
> strings would most likely be longer. After encryption it would best to use a
> smaller fixed tree to expand back into the character set you wish or the
> adaptive condition uncompress will make the string generallt longer than you
> started with.
>
So many options are available if the information content of ciphertext is
allowed to exceed that in the plaintext, whether it is an increase in set
size used, or greater length in characters, or both.
You have to pay for tangible security in some way. My complaint with
so-called fixed block ciphers is that they tend to be overcomplicated to
get mediocre results.
--
The circus elephant has lost its way.
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: Codebook examples on Web?
Date: Sun, 14 Nov 1999 10:02:54 +0100
See http://www.research.att.com/~reeds/codebooks.html
for a beginning.
------------------------------
From: [EMAIL PROTECTED] (Tim Smith)
Subject: Re: What's gpg? <PHILOSOPHY 101>
Date: 14 Nov 1999 08:44:39 GMT
Reply-To: Tim Smith <[EMAIL PROTECTED]>
On Wed, 10 Nov 1999 04:44:45 +0000, Dennis Ritchie <[EMAIL PROTECTED]> wrote:
>> Yes, this really happened; it's not an urban legend. That was Paul
>> Cohen, and his proof that the negation of the Axiom of Choice was
>> compatible with set theory, wasn't it?
>
>Well, the independence of AC and GCH, and the forcing method,
>are Cohen's most memorable contributions that I know of, but
>he neglected to mention the waking-up business in his 1966 monograph
>and in the 1965 course at Harvard in which he discussed
>the then-new (1963) result. I'd want to see some direct testimony
>before believing this particular story.
You're right to be skeptical, since the original poster and the one who
said it was Paul Cohen have both botched it. The Cohen theorist was
close, though--it was George Dantzig. (I say he was close because the
chapter on Paul Cohen is next to the chapter on George Dantzig in "More
Mathematical People" :-)). Here's the relevant section from the interview
with Dantzig:
MP: How did happen that you did your Ph.D. on a statistical topic when
you took so few courses in statistics?
Dantzig: It happened because during my first year at Berkeley I arrived
late one day to one of Neyman's classes. On the blackboard were two
problems which I assumed had been assigned for homework. I copied them
down. A few days later I apologized to Neyman for taking so long to do
the homework--the problems seemed to be a little harder to do than
usual. I asked him if he still wanted the work. He told me to throw it
on his desk. I did so reluctantly because his desk was covered with
such a heap of papers that I feared my homework would be lost there
forever. About six weeks later, one Sunday morning about eight o'clock,
Anne and I were awakened by someone banging on our front door. It was
Neyman. He rushed in with papers in hand, all excited: "I've just
written an introduction to one of your papers. Read it so I can send it
out right away for publication." For a minute I had no idea what he was
talking about. To make a long story short, the problems on the
blackboard which I had solved thinking they were homework were in fact
two famous unsolved problems in statistics. That was the first inkling
I had that there was anything special about them.
--Tim Smith
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 14 Nov 1999 06:00:35 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: kingtim <[EMAIL PROTECTED]>
Subject: Elliptic-curve cryptography
Date: Sun, 14 Nov 1999 17:32:29 +0800
Do anyone know the application ,the theory and the source code of
Elliptic-curve cryptography ?
thanks
------------------------------
From: Henri <[EMAIL PROTECTED]>
Subject: thanks for all
Date: Sun, 14 Nov 1999 10:41:32 +0100
Thanks a lot for your advices. I 'll follow them strictly.
Have you another experiences or uses which are a bit specific of the hash functions
?
You can reply at [EMAIL PROTECTED] if you don't want to post.
Thanks again.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Public Key w/o RSA?
Date: Sun, 14 Nov 1999 03:46:03 GMT
Roger Schlafly wrote:
> No, Diffie-Hellman is older and just as secure.
I thought about that when I wrote the previous message,
but I tend to think of D-H only in connection with key exchange,
not message encryption.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Ultimate Crypto Protection?
Date: Sun, 14 Nov 1999 03:41:37 GMT
[EMAIL PROTECTED] wrote:
> ... It is only because the Russians used some of the pads twice
> that we're today hearing about the intelligence coup of Venona.
Other OTP systems have been cracked even though the pads were not
reused.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: intelligent brute force?
Date: Sun, 14 Nov 1999 03:54:12 GMT
Keith A Monahan wrote:
> Has anyone written a paper or a chapter in a book describing methods of
> brute forcing intelligently, before resorting to a full-scale search?
That's a contradiction in terms. A "brute force" attack *means*
simply trying every possible decryption key and testing the result
to see if it has plaintext characteristics. How you test the
plaintext is relatively unimportant, since for most cryptosystems
and most plaintext sources, correct plaintext will have high
coherence by almost any sensible statistical test and incorrect
"plaintext" will have low coherence ditto.
A better question would be, what are some more clever means of
cryptanalysis than a brute-force attack?
------------------------------
Date: Sun, 14 Nov 1999 08:35:16 -0500
From: Gondolin Remailer <[EMAIL PROTECTED]>
Subject: Re:SCOTT16U SOLUTION ON THE WEB
Sorry, you still have not answered my question. Why do you think that 3
letter chaining schemes are inherently week?. Why dont you write a small
paper outlining your views and analysis and claims and stick it on your
web site or post it here? That would help us uderstand your case. Making
a vague statement without backup will not be taken seriously.
------------------------------
From: [EMAIL PROTECTED] (Charles Blair)
Subject: Patent on general public-key concept?
Date: 14 Nov 1999 13:40:27 GMT
At one time, I was hearing a lot about a patent (in some
cases attributed to ``Public Key Partners'') that claimed the
idea of a public-key system, regardless of the specific way
in which it was implemented.
Was there ever such a patent? Did it expire or was it
disqualified in some way?
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Elliptic-curve cryptography
Date: Sun, 14 Nov 1999 13:44:41 GMT
In article <[EMAIL PROTECTED]>,
kingtim <[EMAIL PROTECTED]> wrote:
> Do anyone know the application ,the theory and the source code of
> Elliptic-curve cryptography ?
The source code? Oh yeah, you want some buzzword compliant crypto to
throw in your application to meet a checklist you probably don't
understand.
Talk to certicom for their ECC libraries. If you want to understand
the theory talk to Mike Rosing [he hangs out here].
What problem are you trying to solve with ECC?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Quantum Cracking
Date: Sun, 14 Nov 1999 13:42:00 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (UBCHI2) wrote:
> Have there been any further developments in theoretical quantum
factoring or
> quantum list lookup functions?
>
Your question is quite moot. Quantum mechanics is a very deep subject
[which happily excludes me :)]. If you are not in the game now, you
won't properly understand any theoretical results that come out. I
suggest you try to find research facilities that actually do work on it
and ask them. And also take a MS in physics, and ...
Similarly applies to any advanced cryptoanaylsis such as integer
factoring and discrete logs.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Patent on general public-key concept?
Date: 14 Nov 1999 16:15:16 GMT
Issued and expired.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Bruno Wolff III)
Crossposted-To:
comp.security.misc,comp.security.pgp.tech,alt.security.pgp,comp.mail.eudora.ms-windows
Subject: Re: S/MIME plug-in for Eudora? Strong Encryption
Date: 14 Nov 1999 16:20:43 GMT
Reply-To: [EMAIL PROTECTED]
>From article <[EMAIL PROTECTED]>, by Adam Kippes
><[EMAIL PROTECTED]>:
> In <[EMAIL PROTECTED]>, amateur wrote:
>
> If you do find such an option, please post. I would like to be able to do
> that. Or a least get one off of the server; not exactly the same thing, I
> realize, but I'll be satisfied.
>
You might want to switch to gnupg. It uses the openpgp standard (rfc 2440).
This includes putting expiration dates on keys. Openpgp is free from patent
encumberance (though some implementations use patented algorithms to provide
backward compatibility). It works with mutt. See http://www.gnupg.org/ .
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Need technique for about 24 bytes
Date: Sun, 14 Nov 1999 17:41:01 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(wtshaw) wrote:
>In article <80jq8m$214i$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>(SCOTT19U.ZIP_GUY) wrote:
>
>> You could use my "conditional one to one adaptive huffman compressor"
>> that is at my site to compresss the string to a smaller size and then
> compress
>> the resulting binaray file with scott16u ( or even scott4u if a 40 bit key is
>
>> OK) then you can convert the resulting string back to a base 36 character set
>> using the conditional uncompressor. This does what you want except that the
>> strings would most likely be longer. After encryption it would best to use a
>> smaller fixed tree to expand back into the character set you wish or the
>> adaptive condition uncompress will make the string generallt longer than you
>> started with.
>>
>So many options are available if the information content of ciphertext is
>allowed to exceed that in the plaintext, whether it is an increase in set
>size used, or greater length in characters, or both.
I agree that is why I suggest compressing to a unique binary file for
encrypting. You notice if a wrong key is used by the attacker it will
produce a valid file in the character set that the user used.
>You have to pay for tangible security in some way. My complaint with
>so-called fixed block ciphers is that they tend to be overcomplicated to
>get mediocre results.
That is one reason why scott16u and scott19u can work on variable length
files without chainging the file size during encryption.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
------------------------------
From: "Gary" <[EMAIL PROTECTED]>
Subject: Re: Quantum Cracking
Date: Sun, 14 Nov 1999 17:05:00 -0000
Tom St Denis wrote in message <80me79$7kv$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (UBCHI2) wrote:
>Your question is quite moot. Quantum mechanics is a very deep subject
Don't be put off, many people find QM easier to grasp than classical
mechanics.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Bracking RSA Encryption. Is it possible.
Date: 14 Nov 1999 17:46:29 GMT
Allan G. Schrum/Theresa C. Schrum <[EMAIL PROTECTED]> wrote:
> I would be curious to know exactly how, given a good integer factoring method,
> RSA could be broken. What is the approach?
Take the public key <e, n> .
Feed n to your factoring algorithm. Extract factors p and q.
Compute (p - 1)(q - 1) from p and q.
Compute e^{-1} mod (p-1)(q-1).
This is the RSA private key.
You're done!
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: Patent on general public-key concept?
Date: Sun, 14 Nov 1999 19:21:27 +0100
See also at
http://www.rsasecurity.com/rsalabs/faq/6-3-5.html
(3d one)
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: The Code Book
Reply-To: [EMAIL PROTECTED]
Date: Sun, 14 Nov 1999 19:28:17 GMT
Jim Gillogly <[EMAIL PROTECTED]> wrote:
: "Dr. Harley Mackenzie" wrote:
:> I dont suppose anyone would like to post or put on an FTP site any of
:> the challenge's text? I can't believe that the author didnt put them on
:> the challenge website.
: He wants to sell books -- giving away free chances at a prize doesn't seem to
: increase shareholder value, or however the Cryptonomicon mantra went.
The solution may depend on dictionary-lookup systems using texts from
"The Code Book" itself as dictionaries. That would certainly be a
sure-fire way of preventing "free riders" from solving all the cyphers.
: I'm still missing solutions to all the Stages evenly divisible by 5.
<fx: giggles>
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Wee Tam and The Big Huge.
------------------------------
From: [EMAIL PROTECTED] (HJS)
Subject: Re: Codebook examples on Web?
Date: Sun, 14 Nov 1999 20:00:19 GMT
Reply-To: HJS
On 14 Nov 1999 04:54:52 GMT, [EMAIL PROTECTED] (UBCHI2) wrote:
>Are there any examples of famous codebooks on the net? I want to see how the
>Gray code and other historical diplomatic codebooks were constructed.
There's a little material on commercial/shipping/banking codes, but I've
been unable to turn up anything else.
Please post here if you find anything.
--
___________________
HJS +
------------------------------
From: [EMAIL PROTECTED] (HJS)
Subject: Re: Ultimate Crypto Protection?
Date: Sun, 14 Nov 1999 20:00:17 GMT
Reply-To: HJS
On Sun, 14 Nov 1999 03:41:37 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>> ... It is only because the Russians used some of the pads twice
>> that we're today hearing about the intelligence coup of Venona.
>
>Other OTP systems have been cracked even though the pads were not
>reused.
But only by 'practical cryptanalysis' i.e. theft, and not by
pure cryptanalysis.
--
___________________
HJS +
------------------------------
From: Nogami <[EMAIL PROTECTED]>
Subject: Breaking Enigma using modern technology?
Date: Sun, 14 Nov 1999 12:25:27 -0800
After watching a 2-hour PBS episode of Nova about breaking Enigma (it
was the best special I've seen on the subject), I got to wondering:
Given today's computing power, how long (on average) would it take to
break enigma using a standard PII desktop PC using the most advanced
cryptoanalysis tools currently available?
Any ideas?
I'm assuming because enigma didn't use a true random number generator,
and had some interesting quirks, such as that an encypted character
would apparently _never_ be the same as the plaintext character, etc
that it would be reasonably easy, at least when compared with modern
(which is to say, software-mathematical rather than mechanical)
encryption techniques.
N.
------------------------------
From: Coen Visser <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: Sun, 14 Nov 1999 20:28:31 +0000
"Trevor Jackson, III" wrote:
> Coen Visser wrote:
> > Ok, here is an excerpt from what I wrote earlier:
> > 1 It happened to be proved that a string that passes all statistical
> > 2 tests within the required confidence level is incompressible
> > 3 (and random because it passed the tests).
> > 4 So our definitions start to look dangerously equivalent.
> The above is a perfect example of the confusion created by your suggestion that
> incompressibility means randomness.Given your definition of random, #3 above can be
> transformed by the substituion of "incompressible" where "random" is used. Then it
>reads
> "(and incompressible because it passed the tests)", which is simply a restatement of
>1+2.
I wrote:
1 A string that passes all statistical tests for randomness
is incompressible.
2 A string that passes all statistical tests for randomness
is random.
3 So it looks like random and incompressible can be substituted here.
I don't see any confusing statement here. The fact that you don't
believe it is not confusing. Just say you don't believe it and I
will try to convince you. Or point to an error and convince me.
> > Now to prove that a random generator is random you need to
> > put its output through all effective statistical tests, so that
> > is the connection. I must admit that I was a bit too eager to
> > convince my oponents with 4.
> This is false. One cannot prove that a random generator is random by statistical
>analysis.
> One can only prove that a generator is in some degree _not_ random.
Indeed, I never claimed it was *possible* to prove. I believe
that I have mentioned in earlier posts that it is impossible
to prove that a string is random. So it seems likely that the
randomness of a generator is also impossible to prove.
> > Patrick Juola pointed this out:
> > 1 *HOWEVER*, the output of a random coin-flipper is not necessarily
> > 2 random in the Kolmogorov-Chaitin sense
> random == incompressible
> > 3 (it's random with probability one, but that's *NOT* equivalent,
> > thanks).
> > 4 Nor is it the case that a number random in the Kolmogorov-Chaitin
> > sense
> > 5 was generated by the output of an appropriately random process
> random == unpredictable
So an unpredictable sequence is incompressible. I have no
problems with that. I wouldn't know what the other way around
would mean (an incompressible sequence is unpredictable).
> By this analysis all strings, including infinite ones, are compressible. Since you
>are
> willing to wait "forever" for your UTM to generate Pi, you must be willing to wait
>the same
> period for my generator to produce any specific number you choose.
> My generator is a fair coin. If you specify an infinite sequence you believe is
> incompressible
> (just how are you going to do that?),
That is impossible: if I can give an effective description I can
compress it.
> my generator will produce it "eventually".
For an infinite random sequence the chance is zero, absolutely,
there are uncountably many sequences. I would say your fair coin
compresses
one specific infinite length random number of which we have no other
information than that it is produced by your coin.
But even in the finite case there is a major problem. You have
to decide where the output of your decompressor starts and where
it stops, else the output of the decompressor is ambiguous. If
your coin produces "0100101011..." would you say it decompressed to
"101" or "01" or "1001" or ...? Decompression should be unambiguous,
there has been no confusion about that.
Regards,
Coen Visser
------------------------------
From: Coen Visser <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.misc,sci.physics
Subject: Re: Proposal: Inexpensive Method of "True Random Data" Generation
Date: Sun, 14 Nov 1999 20:37:19 +0000
"Trevor Jackson, III" wrote:
> Coen Visser wrote:
> > I thought that the arbitrary large but constant factor O(1)
> > was understood. [...]
> Your constant (the degree of compression of strings containing repeated "01")
That is not what the constant *additional* term +O(1) means.
The words "constant factor" might falsely suggest that it is something
multiplicative; I've got to be more careful with what I write.
> [...] But until you deal with the single instances I've mentioned,
> I'm not going to tackle one of your universal claims.
Ok. I seem to be trapped by the desire to keep my postings
within a reasonable size and the need to explain the concept of
optimal compression as used in incompressibility and randomness of
strings. I'll try to be as brief as possible but I will show the
equivalent principles as used in "real compression".
So bear with me...
0 The bear necessities
Suppose we want to define optimal compression on strings of arbitrary
length[1]. We first need to choose a Universal Turing Machine as a basis
for (de)compression. This will influence the rate of compression of
individual strings. Fortunately the difference between compression rates
when different Universal Turing Machines are used will only differ a
constant additional term ( +/- O(1) )[2]. The UTM is used to execute
other
well defined Turing Machines. For all practical purposes look at the UTM
as a PC with windows or a Sun with Solaris with unbounded memory.
1 Compression
For each string S we want to compress we build a
the smallest TM[3] that when executed by the UTM will produce S. This
is just a self-extracting program running on your PC.
Now one could object by saying: I use only non-selfextracting compressed
files so I don't have the overhead you have. This is not quite true.
The overhead is just moved to another place. The file has to be
recognized
as being a zip-file instead of an MP3/Arj/Zoo/JPG/.../Wav-file. So some
kind of compression-type-id has to be added to the file. In "real life"
this is usually done using a file-extension and/or a file header. The
theoretical model can be modified to use the same principle: the
compression
functions are added to the UTM and the compressed strings get prefixed
with
an additional compression-type-id. The theoretical model can perform
*at least* as good as the applied compression models. It performs better
because it can use the most optimal compression model for each string.
That
demands however that most strings will be self-extracting else the UTM
has
an infinite size.
2 Incompressibility
Most strings can not be compressed (much) and the compressed
representation will consist of a small TM of size O(1)[4] that will
copy its argument (the string S itself) to the output. It is easy
to find parallels in the world of applied compression. Use a reasonable
PRNG to produce say 1000 strings of 2 million bits and try to apply the
zip algorithm on it. Most compressed strings will be larger than the
original string. The most optimal compressed string would probably
incorporate the (optimally compressed) PRNG with its parameters.
Time constraints prevent me from elaborating further (*thank god* I
hear you say). But I hope to have shown that optimal compression does
not differ from the applied compression that is in use today. It only
uses the optimal compression algorithm for each string.
Regards,
Coen Visser
[1] Algorithms used in GIF, Zip, MP3 et cetera are defined on strings
of arbitrary length too, so nothing strange here.
[2] A self-extracting zip-file of file F on a Sun workstation will
differ
in size from the self-extracting zip-file of F on a PC due to
differences in the machine architecture (RISC vs. CISC,
Unix vs Windows).
[3] The smallest TM representation of a string although it exists
can not be effectively found. First of all there are too many TM to
try and
second things get a bit fuzzy when dealing with the constant
additional
term.
[4] O(1) + O(1) = O(1).
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Breaking Enigma using modern technology?
Date: 14 Nov 1999 20:35:48 GMT
Nogami [EMAIL PROTECTED] writes, in part:
>After watching a 2-hour PBS episode of Nova about breaking Enigma (it
>was the best special I've seen on the subject), I got to wondering:
>
>Given today's computing power, how long (on average) would it take to
>break enigma using a standard PII desktop PC using the most advanced
>cryptoanalysis tools currently available?
>
>Any ideas?
Apparently, if you're using Jim's tools, it'll take no time at all!
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
** 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
******************************
