Cryptography-Digest Digest #295, Volume #10 Wed, 22 Sep 99 14:13:03 EDT
Contents:
Re: Modified CBC (DJohn37050)
Re: Homophones (Tim Tyler)
Re: msg for Dave Scott (JPeschel)
Re: msg for Dave Scott (Tim Tyler)
Re: Another bug RE: CryptAPI (Paul Koning)
Re: EAR Relaxed? Really? (Paul Koning)
Re: frequency of prime numbers? (Tim Tyler)
Re: msg for Dave Scott (jerome)
Re: Glossary of undefineable crypto terms (was Re: Ritter's paper) (Patrick Juola)
Re: Purdue's Large Number (Dave Rusin)
Re: frequency of prime numbers? (Patrick Juola)
Re: Glossary of undefineable crypto terms (was Re: Ritter's paper) (Patrick Juola)
Re: Schrodinger's Cat and *really* good compression (Patrick Juola)
GNU Privacy Guard ("Steven H. McCown")
Re: msg for Dave Scott (SCOTT19U.ZIP_GUY)
Re: Another bug RE: CryptAPI (Christopher Biow)
Re: Another bug RE: CryptAPI (wtshaw)
Re: Another bug RE: CryptAPI (Christopher Biow)
Re: msg for Dave Scott (Tom St Denis)
Re: arguement against randomness (Jerry Coffin)
Re: Comments on ECC (Jerry Coffin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Modified CBC
Date: 22 Sep 1999 14:27:13 GMT
The reason for the IV is to ensure a random-appearing input to the first
encryption. It is called "whitening". If you do not use it, then patterns can
be detected easier, if they exist in the plaintext.
Don Johnson
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Homophones
Reply-To: [EMAIL PROTECTED]
Date: Wed, 22 Sep 1999 14:14:16 GMT
John <[EMAIL PROTECTED]> wrote:
: Does anyone have any information/can point me in the direction of some
: good information, regarding the decryption of a monoalphabetic cipher
: with homophones?
There are some tips about how to do this in Simon Singh's "The Code Book",
chapter one.
One of his ten cyphers (the uncoding of which would win 10,000 UKP)
is a monoalphabetic cipher with homophones. That isn't what you
want the info for - is it? ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Nuns do it out of habit.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: msg for Dave Scott
Date: 22 Sep 1999 14:54:59 GMT
Tom St Denis <[EMAIL PROTECTED]> writes:
>Well you say you can break all encryption methods and systems.
When did he say that? I think he claimed he would try breaking IDEA
once a long time ago, but usually he says it's the NSA that can
break everything.
I've never seen Dave or Tom break any sort of cipher.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Reply-To: [EMAIL PROTECTED]
Date: Wed, 22 Sep 1999 14:24:46 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: Well you say you can break all encryption methods and systems. Prove it.
: beaqaaamL6MNs6}utuaaaaiaaaaW{dsG{jC4KzE3hoqb}tWYZ9qT2Fcaaaaaaaaaaaaa
: aaaaaaaaaaaaaaaaaaaaaaaaa
Anyone under the illuion that they can break all modern cryptography
given tiny message fragments might like to try the challenge in
Simon Singh's "The Code Book" - break ten ciphers and win 10,000 UKP.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
You can't take it with you.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Another bug RE: CryptAPI
Date: Wed, 22 Sep 1999 10:15:19 -0400
Eric Lee Green wrote:
>
> Paul Mikesell wrote:
> > I'd like to point out that a non-dll implementation only will only make
> > the system more secure through obfuscation, which does not really make it
> > more secure.
>
> Well, if you statically link it into your code, you can at least assume
> that you are running your own code, not somebody else's. Unless somebody
> has compromised your actual binary, of course, but (shrug) what can you
> do about that? At least this way somebody has to specifically target
> your binary, rather than being able to fire a shotgun and hit every app
> that uses crypto.
If you're going to be concerned about security, you really do have
to worry about whether random bystanders can scribble on your binaries.
There's just one solution. You have to understand the fact that
NO Microsoft product has any security. If you switch to an OS that
starts out with reasonable security designed in (e.g., Unix, Linux)
it's possible that you will get what you need. You still have to be
careful, of course. Start on a Microsoft platform and you're defeated
before you even get started.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: EAR Relaxed? Really?
Date: Wed, 22 Sep 1999 10:24:07 -0400
Greg wrote:
> ...
> I have also heard that there are non disclosure agreements between
> NSA and the vendor.
Not in my experience. I suspect the NSA won't tell others about
their conversations with a vendor, but that's normal for such
a reticent organization. On the other hand, the vendor is free
to say whatever they want, in the cases I've been involved with.
> This is fine, except it can prevent the vendor
> from telling all about the negotiations with NSA. For example, if
> the NSA says, "We need two back doors into your software to examine
> the plain text before it is encrypted," then we would never hear of
> it. The encryption is sound, as you point out. But the application
> software is buggy with holes for the NSA to drive through.
Yes, of course, that would be an issue if that happened. I haven't
run into stuff like that. It seems a risky thing to try.
How would you rate the chances that someone confronted with such
a request would go to the nearest newspaper or congressman, never
mind that NDA? It seems significant.
> The point of my post is that IF a license is required to do business,
> then the application software itself is compromised by the very
> definition of the secret association between vendor and NSA. To
> be more specific, you and I have no absolute assurance that there
> are no planted or discovered and non publicized back doors as a
> requirement for the license.
That's the argument for open source. With OR WITHOUT NSA involvement,
you don't have that assurance unless you can read the source code.
Unless you're willing to limit your crypto apps to only those that
are available in open source, at some point you have to go with
the assumption that the seller is either honest enough or worried
enough about disclosure to stay away from monkey business.
> This is also indicative by the new
> rule that law enforcement does not have to disclose how they got
> the plain text. (They can illegally obtain it and never be held
> accountable- have you thought that through yet? This is far more
> dangerous than it appears- and they thought we would be throwing
> a party right about now!)
I quite agree. Do you have any pointers to this? It's news to me.
> > The interesting question is whether the "technical review"
> > will be allowed to end with the product failing to be approved
> > (presumably because it is too secure, although that might not
> > be the officially stated reason).
>
> Again, with the NDA, you and I will never know...
Yes, but you're basing a lot on the assumption that there are
NDAs, which I believe is not a correct assumption.
paul
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 22 Sep 1999 14:19:57 GMT
Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
: Douglas A. Gwyn wrote:
:> Donald Welsh wrote:
:> > I'd like to correct this misconception, if I may. Godel's theorem
:> > does not say that "there are true statements that cannot be proved".
:> > It says that there are unprovable statements. These statements are
:> > neither true nor false.
:>
:> False unprovable statements are trivial. Goedel's result
:> pertains to statements that are true, yet unprovable within
:> the given axiomatic system.
: Really. Do you have a trivial solution to the (false) statement
: "Turing machine N halts?"
You've told him that the statement is false in your question.
How much more trivial can a solution get? ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Marriage? Sorry - I don't mate in captivity.
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: msg for Dave Scott
Date: 22 Sep 1999 15:39:47 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 22 Sep 1999 12:09:57 GMT, Tom St Denis wrote:
>
>beaqaaamL6MNs6}utuaaaaiaaaaW{dsG{jC4KzE3hoqb}tWYZ9qT2Fcaaaaaaaaaaaaa
>aaaaaaaaaaaaaaaaaaaaaaaaa
can you explain all these 'a' at the end and in the middle of the
cypher text ?
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Glossary of undefineable crypto terms (was Re: Ritter's paper)
Date: 22 Sep 1999 11:39:34 -0400
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>>
>
>> Actually, I think the "generally accepted criterion" has long
>> been established; some problems are "generally accepted" to
>> be hard -- factoring, discrete logarithm, and roll-your-own-NP-complete
>> among them. Techniques of problem reduction have been formalized
>> and accepted since at least (Cook, 1971). So it's generally accepted
>> that a problem "as hard as" a "hard" problem is proven "hard."
>>
>> Of course, there are always a few hard-liners and wing-nuts out there
>> who don't believe that a given problem is "hard" -- general acceptance
>> doesn't mean and never has meant universal acceptance without a
>> single exception or reservation. (It's "generally accepted" that
>> the Moon landings occurred, too, despite the existence of the Flat
>> Earth Society.)
>
>How 'hard' are these REALLY? A citation from A. Salomaa says that
>there are no provable lower bounds for the amount of work of
>a cryptoanalyst analysing a public-key cryptosystem.
Well, if you accept the "lucky guess" algorithm, then *any* system
can be cracked in O(1) time.
Frankly, I think that Dr. Salomaa is grossly overstating the issue.
There are certainly some provable lower bounds; I can't factor an
N-bit number in less time than O(N) -- that much time is required both
to read in the number and to write out the answer. With our
current state of the art, this isn't an especially useful lower bound,
but it certainly exists, and it's certainly provable, thus
invalidating Dr. Salomaa's statement.
Similarly, there's a big difference between "there are no provable X"
and "there are no PROVEN X"; there may indeed be a provable lower bound,
but we haven't found it.
And, again, to the hard-liners and wing-nuts.... why is *proof* so
important to you? Madame Shasta down the street will tell me what
your key is by inspection of the leaves at the bottom of her teacup,
and you can't *prove* that she won't. You have an opinion, supported
by a lot of empirical research, that suggests that she can't do
what she claims. You similarly have an opinion, again bolstered by
lots of research, that factoring is a hard problem. Why dismiss
Ron Rivest but believe the NYPD bunko squad? Frankly, I think Ron
is a lot smarter than your average NYPD cop....
-kitten
------------------------------
From: [EMAIL PROTECTED] (Dave Rusin)
Crossposted-To: sci.math
Subject: Re: Purdue's Large Number
Date: 22 Sep 1999 15:42:53 GMT
In article <7samo2$kv4$[EMAIL PROTECTED]>,
John M. Gamble <[EMAIL PROTECTED]> wrote:
>"The number Purdue needs to factor is
>163790195580536623921741301545704495839
>239656848327040249837817092396946863513
>212041565096492260805419718247075557971
>445689690738777729730388837174490306288
>87379284041.
Typo? Easily found factors of 3, 39341, 46591, 163245571
>Anyone know why this particular number?
No, but the crew at Purdue (Sam Wagstaff et al) have been factoring
big numbers for many years, in particular shepherding the Cunningham
Project, seeking factors of numbers of the form b^n +- 1 (b small).
There are also some other numbers used as cryptographic challenges
or benchmarks.
>Anyone know of its status as far as factoring goes?
You quoted a 1997 newspaper article. A 149-digit composite of particular
interest would have yielded to massive parallel factorization efforts
using MPQS (say) by now.
dave
Factorization: http://www.math-atlas.org/index/11Y05.html
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: frequency of prime numbers?
Date: 22 Sep 1999 11:42:43 -0400
In article <[EMAIL PROTECTED]>,
Donald Welsh <[EMAIL PROTECTED]> wrote:
>On Fri, 06 Aug 1999 17:27:45 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
>
>>No. What Goedel showed was that any sufficiently rich axiomatic
>>system is incomplete in the sense that there are true statements
>>which can not be proved. [as well as other stuff I won't discuss].
>>Peano arithmetic is "sufficiently rich", BTW.
>
>I'd like to correct this misconception, if I may. Godel's theorem
>does not say that "there are true statements that cannot be proved".
>It says that there are unprovable statements. These statements are
>neither true nor false.
But at least some of the statements *are* either true or false; in
particular, Godel's sentence is an equation which either does or
does not have a solution -- which is a property of the mathematics
and not of the representation. So the Godel "sentence" *is*
actually either true or false within a given model -- but we'll
never know which.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Glossary of undefineable crypto terms (was Re: Ritter's paper)
Date: 22 Sep 1999 11:44:01 -0400
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Joseph Ashwood wrote:
>>
>> [snip]
>> > How 'hard' are these REALLY? A citation from A. Salomaa says that
>> > there are no provable lower bounds for the amount of work of
>> > a cryptoanalyst analysing a public-key cryptosystem.
>> There can be no lower bounds or upper bounds placed on human cognition,
>> simply because we do not understand it. If you are talking about lower
>> bounds of the work necessary to break a public key, it is trivial to prove
>> that no common method could possibly drop below O(n), where n is the length
>> of the key, this is because you obviously must read the key before you can
>> break the key, outside of that I am not aware of any progress.
>>
>
>If I understood correctly, you are saying what Salomaa wrote was
>nonsense.
If he isn't, I am. More accurately, I claim that your presentation of
his statement is demonstrably false.
Hell, there's an easier counterexample. O(1) is a provable lower
bound to *everything.*
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Schrodinger's Cat and *really* good compression
Date: 22 Sep 1999 11:46:00 -0400
In article <[EMAIL PROTECTED]>, Erwin Bolwidt <[EMAIL PROTECTED]> wrote:
>"Douglas A. Gwyn" wrote:
>
>> [EMAIL PROTECTED] wrote:
>> > And here we come to Schrodinger's cat. One of the interpretations of
>> > quantum mechanics held that a superposed quantum state did not resolve
>> > itself into one state until it was exposed to the gaze of a *human
>> > observer*.
>>
>> The point of Schr�dinger's cat is that it points up the logical
>> problem with that interpretation (which seems to have fooled
>> Roger Penrose too) -- why can't the cat play the role of observer?
>
>Isn't that the problem; who observes the observer?
>If you checked on the cat and I haven't spoken with you, isn't the state of
>the cat still undefined to me? And (let's not make this personal) if the
>observer dies before having spoken to anyone, isn't the state of the cat
>completely undefined again?
No.
>I guess what I'm wondering is, does nature take into account the
>peculiarities of human consciousness;
No.
-kitten
------------------------------
From: "Steven H. McCown" <[EMAIL PROTECTED]>
Subject: GNU Privacy Guard
Date: Wed, 22 Sep 1999 10:00:55 -0600
Reply-To: "Steven H. McCown" <[EMAIL PROTECTED]>
Version 1.0.0 of GNU Privacy Guard was released a couple of weeks ago. Does
anyone have any comments on this PGP replacement or OpenPGP?
Thanks,
Steve
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: msg for Dave Scott
Date: Wed, 22 Sep 1999 18:16:14 GMT
In article <7sagud$4ad$[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]> wrote:
>Well you say you can break all encryption methods and systems. Prove it.
>
>beaqaaamL6MNs6}utuaaaaiaaaaW{dsG{jC4KzE3hoqb}tWYZ9qT2Fcaaaaaaaaaaaaa
>aaaaaaaaaaaaaaaaaaaaaaaaa
>
Tommy I doubt on my 486 33mHz system with less than 30 megs of free space
that I will even bother trying to break it. However give me half the budget of
the NSA and have there computers with half there staff and I will give you the
anwser next weak.
Tommy there is a difference from seeing with information theory something
is weak than there is breaking a system. The point is if you know it is weak
and you can design something less weak you should knowing nothing else
go for it. That is not to say that just becasue the test one runs on any
method does not show a method to be weak. That the NSA may or may not
be able to break either.
>That was a peekboo message using my private key and csybrandy's public key.
>It was encrypted with RC4. I want to see if you can read the message, get
>the private key or both. The source and executables are all up on
>
>http://www.cell2000.net/security/peekboo/index.html
>
>And if you can't break peekboo, then I think you shut up, cuz I am just a
>kid, and if I could make peekboo imagine what wonder Comp sci majors and
>crypto 'gods' could do....
I am not sure you are a kid. Maybe your just a phony alter name for one
of the other people who post here. Secondly what langae is it in. At this
point in time I am only using DGJPP GNU C.
>
>(btw if anyone else reads this thread and thinks I am a jerk now can you do
>something usefull and makesure that the dh generator is actually a proper
>one. I was told by some people in this group it's ok....)
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Share what you know. Learn what you don't.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: Christopher Biow <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Another bug RE: CryptAPI
Date: Wed, 22 Sep 1999 12:30:07 -0400
Paul Koning <[EMAIL PROTECTED]> wrote:
>There's just one solution. You have to understand the fact that
>NO Microsoft product has any security. If you switch to an OS that
>starts out with reasonable security designed in (e.g., Unix, Linux)
>it's possible that you will get what you need. You still have to be
>careful, of course. Start on a Microsoft platform and you're defeated
>before you even get started.
Judging from my experience in academia and in government labs, something
like 90% of all MS and *nix machines are, at any given time, open to any
number of script-kiddie remote root/admin exploits. During periods
immediately after the publication of such exploits, ~100% of such machines
are vulnerable to someone capable of writing a script.
In terms of periods and scope of vulnerability, it would actually be the
Win98 workstation whose user regularly uses Windows Update which is (much)
more secure from remote root-equivalent exploits. It would be the actively
maintained NT box which is (marginally) more secure from trojan attack.
E.G. see the relative frequency of discovered vulnerabilities in CIAC
advisories. While the NT code may or may not have more security-related
faults per square gallon of functionality, its closed-source "security
through obscurity" has effectively made it relatively less vulnerable, by
this particular measure. Perhaps, at some time, enough serious security
faults in *nix code will all have been discovered and fixed that their
discovery rate falls off and becomes lower than that of NT. That does not
yet seem to have happened. NT4's *first* remote buffer overflow exploit was
found only a couple of months ago vs. perhaps a dozen applicable to a
default install of a contemporary version of *nix.
To apply the term "secure" to either of these is doing violence to the
word. There is at best "unsecure" and "very unsecure". (FWIW, I markedly
prefer working on *nix, but that's not due to any doctrinal delusion about
"security.")
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: talk.politics.crypto
Subject: Re: Another bug RE: CryptAPI
Date: Wed, 22 Sep 1999 11:27:07 -0600
In article <[EMAIL PROTECTED]>, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>
> It's a stretch, but Microsoft(tm)'s authority to sign every CryptoAPI
> module can be construed as a form of endorsement. By that standard it is
> false (fradulent) because one might end up with modules that are not signed
> -- endorsed -- by Microsoft(tm) because of the loopholes <bold> that
> Microsoft(tm) put in their software. </bold>
The more complicated crypto sounds to some, the more impressed they tend to be.
Trying to put your security into someone elses hands is usually not too
good of a thing because you must question 3rd party motives, and it seems,
they are not apt to be pure.
Having a direct tie of bonded security to individuals is really the best
way, something more than just promises, and having the right to lie about
the offered services.
--
Mark my return, in a somewhat limited way.
As things get better, I will try to follow more threads.
------------------------------
From: Christopher Biow <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Another bug RE: CryptAPI
Date: Wed, 22 Sep 1999 12:29:42 -0400
Paul Mikesell <[EMAIL PROTECTED]> wrote:
>I'd like to point out that a non-dll implementation only will only make
>the system more secure through obfuscation, which does not really make it
>more secure.
By analogy, passwords are security through obfuscation, but their use has
non-trivial effects upon security.
It adds considerably to the cost of attack. The DLL implementation exposes
a small, high-level, critical, interface that is easily observed,
understood and attacked. A monolithic implementation may require extensive
disassembly of code to attack.
>Give me any alternative way of creating a crypto api and I can attack it
>by running code on the local machine.
Privileged code (i.e. administrator on NT, root on *nix, any code on Win98,
any code on anything that exploits security holes which exist on 90% of
desktop systems) can, at some cost, attack any software crypto system
hosted on that machine. This, I suspect, is virtually the entire reason
that NSA has been so hesitant to use software crypto. Other purported
reasons are minor compared to this.
>The only way that I can think of to truly prevent your system from a
>locally running virus attack (the "maybe I shouldn't be using this
>goofball activeX/java/html/ole mail reader on this FisherPrice OS" attack)
>is by running the memory image of the crypto section through a one-way
>hash and having it validate the itself. Otherwise, as a virus writer I
>can always insert assembly wherever I want.
You've only incrementally increased the cost of attack, as now the attacker
must also disable your self-validation code. In most cases, that will have
a cost on the order of one byte.
--
System crashes have the highest execution priority.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Wed, 22 Sep 1999 16:54:49 GMT
Excuse the bad grammar of the last post... btw deja news put a space in the
ciphertext there so if you want to try and decrypt it paste it in notepad and
remove the space (or wait till 1.5 cuz I fixed it anyways)
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: arguement against randomness
Date: Wed, 22 Sep 1999 11:30:32 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> So *where* is "the randomness of radioactive decay being used to drive the
> most accurate clocks we've invented..."?
Sorry -- I said the wrong thing there. It's not radioactive decay,
that's involved. In an atomic clock, you subject atoms of something
(typically Cesium-133) first to a laser beam to put them into a known
state, then to radiation around their resonant frequency (in the
microwave region). After the atom has passed through the microwave
field, you measure whether its gone through a state transition or not.
You adjust your microwave oscillator to cause the state transition;
when it does, it's running at exactly the resonant frequency of that
element. You can then use it (while running at the proper frequency)
to measure time. You re-calibrate it on a regular basis by testing it
with another atom of Cesium.
The resonance of the element is ultimately based on quantum effects,
not radioactive decay. Whether the quantum effects are based on
something truly random or not, I guess I'm not really certain: I tend
to associate quantum effects with randomness, but when you get down to
it, I don't know quantum mechanics well enough to say whether the
association is correct in this case or not.
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Comments on ECC
Date: Wed, 22 Sep 1999 11:30:41 -0600
In article <7saf3l$2qk$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> > Keep in mind that "NP" means "modernistic polynomial."
> ^^^^^^^^
> WHAT??????
As you've (hopefully) seen I already corrected that -- it was a result
of the spell checker thinking "non-deterministic" wasn't a word.
> > IOW, even
> > assuming that there really is such a thing as an NP-complete problem
> > (I.e. that P!=NP)
>
> Now you are sounding like a total crank who does not know what
> he is talking about. Of course NP-Complete problems exist
> and their existence does NOT imply P != NP.
Sorry -- poor wording on my part. Yes, it's clear and proven that NP
complete problems exist. If, however, somebody proves that P=NP, then
being NP-complete doesn't mean much anymore, since it's then proven
that all NP problems really have deterministic solutions in polynomial
time.
Perhaps I can summarize what I'd originally intended to say: talking
about lucky guesses giving fast answers with respect to NP doesn't
really provide new information; in fact, it's basically just
rephrasing what NP stands for. I.e. "Lucky guess" and "non-
deterministic" basically mean the same thing...
--
Later,
Jerry.
The Universe is a figment of its own imagination.
------------------------------
** 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
******************************
