Cryptography-Digest Digest #913, Volume #8 Fri, 15 Jan 99 22:13:03 EST
Contents:
Re: Cayley-Purser algorithm? (David R Brooks)
Re: coNP=NP Made Easier? (Mike McCarty)
Re: coNP=NP Made Easier? (Mike McCarty)
Re: searching protocol ([EMAIL PROTECTED])
Re: Help: a logical difficulty (Mike McCarty)
Re: Help: a logical difficulty (Mike McCarty)
Re: On leaving the 56-bit key length limitation ([EMAIL PROTECTED])
Re: Cayley-Purser algorithm? ([EMAIL PROTECTED])
Re: hotmail passwords (Jessica Anderson)
Re: Help: a logical difficulty (Mike McCarty)
Re: Help: a logical difficulty (Mike McCarty)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David R Brooks)
Subject: Re: Cayley-Purser algorithm?
Date: Sat, 16 Jan 1999 00:19:02 GMT
[EMAIL PROTECTED] (Doug Stell) wrote:
:On Fri, 15 Jan 1999 15:16:45 GMT, [EMAIL PROTECTED] wrote:
:
:>Sorry. Once the method has been published, it CAN NOT be patented in
:>the US.
:
:Have the rules changed? Wasn't RSA patented in the U.S. after it was
:published, else publication would have been squashed? Isn't RSA's
:publication also the reason that it isn't patented outside the U.S.?
:At least this is what I thought Ron and Jim both told me.
:
Just so. Publication can be followed (in the US) by patent filing
within 12 months. However in many other countries (eg Australia)
publication disqualifies any future patent application outright.
This is what led to the ambiguous situation of the RSA patent. The
patent is void in most countries outside the US, for the above reason.
-- Dave Brooks <http://www.iinet.net.au/~daveb>
PGP public key via <http://www.iinet.net.au/~daveb/crypto.html>, or servers
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: 16 Jan 1999 00:51:16 GMT
In article <77ajne$4ve$[EMAIL PROTECTED]>,
Lasse Reichstein Nielsen <[EMAIL PROTECTED]> wrote:
[snip]
)Yes, we can make nondeterministic algoritms on traditional computers,
)but we cannot implement the acceptance criteria (accept if it is possible)
)in the timebound we give for nondeterminsitic time classes. That is:
)No computer we have build (non-quantum) can decide a NP hard problem in
)a polynomially bounded time unless P=NP (assuming our computers are
)polynomially related to DTMs, which I believe they all are).
Well, we agree then, on this. But that still does not mean that running
nondeterministic algorithms on deterministic computers is useless. Some
of them play chess. Some of them design airplanes. Some of them position
integrated circuits on circuit boards, and route the traces to them.
Some of them are used to design the internal logic connections of GALs.
)The problem here is that a NDTM is defined as a DTM with a bounded
)choice of transitions, but the languages/problems decided by NDTMs are
)defined by quantification over ALL possible executions of the NDTM. We
)can build NDTM's (if we have access to some random-source), but we
)cannot yet check for possibility of acceptance without exponential
)blowup, as we have to check ALL the exponentially many executions.
)Quantum computers might solve this for a subset of NP, but so far it
)doesn't look like it's all of it, and therefore specifically no NP hard
)problems.
Exponential blowup does not mean "unusable". It means "eventually
unusable", or "unusable if you want the absolute best answer, as opposed
to a good enough one".
[snip]
)My Dragon book is somewhere else right now, but I'm pretty sure they used
)(N)FAs for regular expressions and (nondeterminstic) push down automata for
)the context free parts (making it even simpler by using LALR(1) grammars only).
)They didn't have to use the power of NDTMs at all.
True. But they *do* give a reasonable feel for it for the rank beginner.
Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Crossposted-To: sci.math,comp.theory
Subject: Re: coNP=NP Made Easier?
Date: 16 Jan 1999 00:52:14 GMT
In article <[EMAIL PROTECTED]>,
Matt Brubeck <[EMAIL PROTECTED]> wrote:
)[EMAIL PROTECTED] (Lasse Reichstein Nielsen) wrote:
)
)>> Interesting. I have used virtual NDTMs for solving real life problems.
)>> In fact, I have written (and use) LEX and GREP type programs for
)>> pattern matching which implement NDTMs.
)
)> I think you might be confuzing some things here. Regular expressions
)> are usually recognized by Finite Automatons(FAs), and nondeterministic
)> FAs(NFAs) are no more powerfull than FAs, so you can translate NFAs to
)> FAs, that can be implemented "easily". Ofcourse TMs are MORE powerful
)> than FAs (as language acceptors), so you could implement LEX and GREP
)> with TM's, but why bother?
)
)This is correct. Regexp matching is usually implemented with an
)nondeterministic finite automaton (FA) model, not with NDTMs. And the
)implementation usually involves a "translation" from NFA to deterministic
)FA.
)
)I also wasn't going to bring up issues such as virtual NDTMs, since they
)confused my main point, which was that Turing Machines, either
)deterministic or nondeterministic, are theoretical constructs. The
)original poster seemed a bit confused about the terminology and concepts,
)so I wanted to make it as clear as possible.
)
)Mr. McCarty pointed out that we can implement NDTM-like behavior on real
)computing machines. However, my main point still holds that once an NDTM
)is made deterministic, we can't guarantee the same run-time bounds.
We agree on that. What we seem to disagree on is that NDTM-like behavior
is useless.
Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: searching protocol
Date: Sat, 16 Jan 1999 01:41:12 GMT
In article <[EMAIL PROTECTED]>,
Medical Electronics Lab <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> > i am searching for a protocol to be carried out by 2 parties with the
> > following properties:
> >
> > both A and B know some (short, approx 8 byte) private secret.
for get the short this is computer age.
> >
> > A and B want to verify that they both got the same secret - without
revealing
> > any information to the partner what the secret is when the protocol says
> > 'different'.
> >
> > there is no secure channel between A and B.
> >
> > an eavesdropper must not learn anything when listening to the messages
> > exchanged by A and B.
> >
> > the protocol must not depend on a third party.
> >
> > any suggestions ?
>
> Do a web search on "zero knowledge". You may want to add the words
> "proof" and "protocol" to that. The basic idea is that they trade
> random numbers and use the secret to generate some other random number.
> The random numbers can be transmitted in the clear, and unless there
> is a match, both sides don't know what the other side has.
>
> Patience, persistence, truth,
> Dr. mike
>
one easy approach is to just use PGP the common secret can be a common
pgp key set. Then just send a signed pgp message to the person if he
verifes your signature(the shared common key) Then your secret information
is the same. I hope this clear the two of you are signing with the
same key if you have the same common information. If you have different
keys then you are signing with different keys and you are as safe as
what pgp is for the time being.
David A. Scott
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: 16 Jan 1999 01:31:42 GMT
In article <[EMAIL PROTECTED]>,
Tony T. Warnock <[EMAIL PROTECTED]> wrote:
)Darren New wrote:
)
)> > I would side with Mike on this. Computer scientists should serve the
)> > wider community, not dictate to them. If this make their sorting
)> > algorithms a bit harder, so be it.
)>
)> Amusingly enough, it became obvious when the local Blockbuster video
)> store switched to computerizing their videos for sale (as well as the
)> rented ones), as movies like "The 4th Protocol" moved from the "F's" to
)> the beginning of the section (as in ASCII). Bleh.
)
)It's worse in Spanish, Coahuila comes before Chihuahua. It is the
I believe this is no longer true. As a native Spanish speaker (it is my
first language) I sorta keep tabs on these things. I heard recently
(though have not verified) that the Academia Real has decided to "split"
the "ch", "ll", and "rr". I personally find this to be a bad move,
making Spanish less phonetic.
)responsibility of the program to get it right, not the users. Violation of
)this principle contributes the distrust of computers.
)
)As an aside, I once wrote a program to sort English transliterations of
)Russian names according to the Russian collating sequence. There was an
)essential ambiguity in that the letter "TS" and the sequence of letters
)"T""S" both occur in Russian names.
How did you handle the hard and soft signs? Usually they are both
transliterated as apostrophe ("'").
Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: 16 Jan 1999 01:27:14 GMT
In article <[EMAIL PROTECTED]>, Dik T. Winter <[EMAIL PROTECTED]> wrote:
[snip nested quote]
)When computer scientists use a specific term with a specific technical
)meaning this does *not* imply that they dictate the wider community to
)use it in the same way.
)
)Alphabetic sorting is something different from the technical "dictionary
)order". And indeed it is difficult as the collating order used depends
)on language and location. There are three places you might wish to
)put the letter a with diaeresis [umlaut], depending on language. Also
)for instance in Sweden "w" is sorted as if it is "v". And in Maltese
)the letter "g plus h-crossbar" should be sorted between "p" and "q",
)while "h-crossbar" alone is sorted between "h" and "i". In Dutch there
)are *three* ways to sort the combination "ij". Dictionaries generally
)sort it as an "i" followed by a "j". Phonebooks sort it as equivalent
)to "y", and I know at least one encyclopedia that sorts it between
)"x" and "y".
I would posit that the examples you give are somewhat at cross purposes.
The fact that letters in different languages have similar or even
identical graphic representation does not make them the same letter.
They usually do not have the same name. To discuss the alphabetic order
of "w" in English, versus "w" in Sweedish is to talk about two distinct
letters, as much different as the english letter "c" and the russian
letter "c" (ess), or the Katakana ">".
)Sorting names is again a different matter. For instance in the Netherlands
)the prefixes to the proper surname are generally disregarded when sorting.
)So you would find "van der Waerden" under "W" in the Netherlands and under
)"V" in Belgium, although Dutch is spoken in both languages and the name
)occurs in both countries.
This is indeed interesting. Dunno what it has to do with sci.crypt and
sci.math, but I find it fascinating. Especially as it affects me. People
usually get my name misalphabetized, and I have to scan lists carefully
to make sure that I have neither been omitted, nor duplicated.
Ignoring "van", "von", "de", etc. in names makes perfect sense to me,
though it is not followed in English. It is interesting that the
Netherlands and Belgium have different conventions on alphabetization of
Dutch.
Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: On leaving the 56-bit key length limitation
Date: Sat, 16 Jan 1999 01:50:59 GMT
Ed Gerk wrote:
> I want to call your attention to the fact that if your understanding of the
> concept of "unicity" would be correct, then the "example" you cited for it two
> e-mails ago would not be absurd -- such as considering that the unicity
> condition would be lost *after* it was reached. To recall, your "example" was:
Hmmm, perhaps we have progress at last. I'm not sure about the
term "unicity condition". Does this refer only to uniqueness of
the prefix of the message represented by a given prefix of the
ciphertext? Note that Shannon does not define unicity distance
in terms of being able to solve for some string that is a prefix
of one or more plaintexts in the message space, which seems to be
what Ed is working toward.
> So, I considered that "example" impossible in regard to DES (which was being
> discussed)
Quite a few things were being discussed.
> but gave you the opportunity to present the cipher system for
> which it would apply -- in other words, how did you calculate percentages
> such as "0.599999" and "0.399999", and with so many digits of precision? How
> could unicity be lost after it was reached and then regained after it was
> lost, so that one could unambiguously initially read "Attack at dawn with
> 300" *before* unicity was lost between a "6" or a "0" and then recuperated
> afterwards to unambiguously read " men" at the end -- and all that well past
> the limit of 20 characters currently cited for DES (that is, if I would be
> wrong)?. To which you have not answered.
When I first presented the probabilities, I granted that this
is a contrived example, and later I wrote what I intended to be
an answer, though it's not in the form Ed requested:
| What's at issue here are
| "Secrecy Systems", also defined by Shannon. Obviously we could
| construct a secrecy system and ciphertext that induces the given
| probabilities.
In a secrecy system, we have a probability distribution of
messages and another of keys. Given a ciphertext, we can use
Bayes' theorem to compute the conditional probability of each
plaintext given the ciphertext. I did not carry out the
exercise of listing possible messages in the plaintext space
and key spaces and assigning probabilities.
> This lack of proper dialogue in your presentations has IMO confused issues
> even more. Perhaps this has to do with the impression that some of your
> phrases are simply ambiguous.
What phrases? Why not ask? I've used and said that I'm
using Shannon's terms and meanings. I've talked in terms of
probability distributions, equivocation, conditional
probabilities and information. All of these are precisely
defined.
> Funnywise, it is even possible that we are
> speaking about the same issues at least in some points -- i.e, not regarding
> your "example".
Here are issues I've been speaking about:
* Presenting an adversary with less ciphertext than the unicity
distance of the secrecy system does _not_ ensure that he can
obtain no useful information from the ciphertext.
* If ciphertext contains no information about the corresponding
plaintext, we have perfect secrecy. Perfect secrecy is a strictly
stronger condition than lack of unique solution.
* The unicity distance of ASCII-encoded English under DES is greater
than one DES block.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cayley-Purser algorithm?
Date: Sat, 16 Jan 1999 01:11:27 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bruce Schneier) wrote:
> On Wed, 13 Jan 1999 17:53:28 +0000, William Whyte
> <[EMAIL PROTECTED]> wrote:
> >> 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.
>
> This sounds like it will be broken a few days after the details become
> public, assuming some of the mathematicians working in this area are
> not otherwise busy at the time. (Sorry for the skepticism, but others
> have worked in this area as well.)
>
> Bruce
>
Bruce you say that because of your prejuiduces. I hope because
she has not been brain washed by some of the so called modern
books on crypto that she was able to strike out on her on
instead of following so called phony experts in the crypto
field. Of course this is only a hope and I fear it may be
wrong but I keep hoping anyway.
But the sad truth of the matter is if was good I think the
NSA would have been able to keep the lid on it. Of course
they still have time since the method has yet to see the light
of day on the net.
David A. Scott
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Jessica Anderson <[EMAIL PROTECTED]>
Subject: Re: hotmail passwords
Date: Fri, 15 Jan 1999 18:23:53 -0800
shouldnt be trying anyways...but thats just morality
JPeschel wrote:
> >[EMAIL PROTECTED] (Robert Taylor)writes:
>
> >Is there anyway to get someones hotmail password? Please E-mail me!
>
> Ask 'em for it!
>
> Joe
>
> __________________________________________
>
> Joe Peschel
> D.O.E. SysWorks
> http://members.aol.com/jpeschel/index.htm
> __________________________________________
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: 16 Jan 1999 01:20:33 GMT
In article <[EMAIL PROTECTED]>, Dik T. Winter <[EMAIL PROTECTED]> wrote:
)In article <776hmi$5gi$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Mike
McCarty) writes:
) > Dictionary order is a complex and interesting topic, though no much
) > related to mathematics. For example, consider my name, McCarty, and that
) > of a friend of mine, MacDougal. Which of them comes first in dictionary
) > (or, equivalently, alphabetical) order? MINE!
)
)Depends on the language I would say.
I can't argue with your own assertion of what you would say. But in re
the case that it depends on the language, I am unwilling to take a
stance. This question seems even more complex, because one begins to get
into transliteration issues, even between languages which ostensibly use
the "same" alphabet. For example, in Spanish (up until recently) the
letter "ch" was usually used to transliterate the letter pair "ch" from
English. But this changed the letter count, and certainly changed the
lexicographic order, since the letter "ch" comes after the letter pair
"cz" in Spanish. So if two men were named (hypothetically)
Bunch
Bunczowitz
the order in Spanish would be the reverse of what I wrote above. But
"Bunch" would have only 4 letters in it, even though "Bunch" is (as I
posit here) an English name with 5 letters in it, since transliteration
has taken place. So no real conclusion can be made since the alphabets
are *never* exactly the same, and transliteration is taking place in
every instance.
)In our phonebook you would follow
)your friend, sorry.
I wonder. Most native English speakers in the USA would say the same,
but be wrong. Talk to a librarian first, unless you have special
expertise. Do you have special expertise? I suspect that you may in
fact be wrong. The spelling of my name is a contraction of MacCarty,
used by the branch of my clan which moved to Ireland. Most people in
the USA are not aware of this, and would incorrectly alphabetize my
name. I wonder whether note is made of this in the Netherlands as it is
in England, Scotland, Ireland, and the USA. I do not know whether it is
used in this wise in Canada, Australia, New Zealand, etc, but I suppose
that it is in all the "British Colonies".
Another point to note is that telephone books are not authorities.
)But dictionary order is also a specific Computer
)Science term and means first ordering by first element, next by the
)second element. Even the collating sequence for the elements is
)unspecified.
Could you give me a few cites? If I came to you and specified that I
wanted "dictionary order" and you gave me a program which behaved the
way you specify, I would be disappointed. If I paid you money for one,
I would be *angry*, and a lawsuit would likely result. The order you
mention I have seen called "lexicographic order", which is different.
Nitpick: one orders by last element first, then by next to last, if by
"then" you mean chronological sequence of sorts, to get lexicographic
order.
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
From: [EMAIL PROTECTED] (Mike McCarty)
Crossposted-To: sci.math
Subject: Re: Help: a logical difficulty
Date: 16 Jan 1999 01:32:30 GMT
In article <[EMAIL PROTECTED]>,
Arthur N. Klassen <[EMAIL PROTECTED]> wrote:
)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)
Now -this- is interesting (to me!)
Mike
--
----
char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
This message made from 100% recycled bits.
I don't speak for Alcatel <- They make me say that.
------------------------------
** 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
******************************
