Cryptography-Digest Digest #894, Volume #11 Tue, 30 May 00 10:13:01 EDT
Contents:
compact sboxes (tomstd)
Re: No-Key Encryption (Mok-Kong Shen)
Re: No-Key Encryption (Mok-Kong Shen)
Re: new public key? (Mok-Kong Shen)
Re: No-Key Encryption (John Savard)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Marc Living)
Re: RIP Bill 3rd Reading in Parliament TODAY 8th May (Marc Living)
email list for the contest (tomstd)
Re: No-Key Encryption (tomstd)
Re: No-Key Encryption ("Trevor L. Jackson, III")
Re: No-Key Encryption ("Trevor L. Jackson, III")
Re: new public key? ("G. Orme")
Re: No-Key Encryption ("DD")
----------------------------------------------------------------------------
Subject: compact sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 30 May 2000 05:23:22 -0700
At http://www.tomstdenis.com/psbox.c is some source that
provides 8/16/32/64 bit sboxes with inverses. They are very
compact (none too fast).
It's not my idea to use sboxes like this, I got the original 8
bit idea from Twofish, but decided to go a bit further :-)
Any comments?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Tue, 30 May 2000 14:40:34 +0200
Mok-Kong Shen wrote:
> Bryan Olson wrote:
>
> > I think it's a little subtler. We can build the scheme
> > from an invertible associative operation, call it *, as:
> >
> > ----- k1 * x ----->
> >
> > <-- k1 * x * k2 ----
> >
> > ----- x * k2 ------>
> >
> > But what we want is somewhat more general: the encryption
> > functions must commute. (Which is not the same as saying
> > each encryption function must be a commutative operation
> > on message and key.)
>
> Pardon, I don't yet see why you additionally require commutativity.
> When x*k2 gets to the receiver, he can just do the inversion to
> get x, can't he? Or do you mean that it is 'desirable' to have in
> addition commutativity? (But then why?) Thanks.
Sorry for my question which was a result of misunderstanding. Yes,
the fundamential issue is commutativity of a pair of encryption
algorithms. It seems likely that all such pairs when used in the scheme
in question result in low strength or no strength. One should probably
also take this as a warning not to use a pair of commutative algorithms
as successive members in a superencipherment.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Tue, 30 May 2000 14:40:24 +0200
Greg wrote:
> > Yes. (Private) key is a piece of secret, not assumed to be
> > available to the public. A codebook is also secret and
> > equivalent to 'key' (one chooses the mapping or even chooses
> > a codebook from several). Hence 'no-key encryption' excludes
> > all such stuffs. What remains is, as Boris Kazak pointed
> > out, language translations.
>
> That makes no sense, because the language becomes the key.
One can consider that the receiver can recognize the language so
that neither an indicator for switching nor a key to determine the
language being used is necessary. So there is no 'key'. Languages
are common knowledges. If the opponent is a mono-glot and can't
decipher, then he has himself to blame.
> Understand the language, or the tranformation with the language,
> and you understand the cipher traffic.
Yes, we exploit the fact that the opponent doesn't have the resource
to understand the language, same as we often exploit the lack of sufficient
computing power of the opponent to crack some algorithms. I pointed
out that Kahn told of the use of foreign languages in WWII combats.
> The concept of a no key cipher is puzzling. Can it actually
> exist and if so for what applications can it be useful?
Elsewhere in this thread it has been pointed out that one can do such
things with certain pair of commutative algorithms, but unfortunately
these seem to be less than satisfactory. The usefullness, if good
schemes exist, lies in my view in doing away with keys, i.e. no need to
look them up, etc. etc., which can certainly be an advantage.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: new public key?
Date: Tue, 30 May 2000 14:40:40 +0200
"G. Orme" schrieb:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >
> >
> > "G. Orme" wrote:
> >
> > > [snip]
> > > multiplied together makes a number xy often difficult to factor. Has
> anyone
> > > tried finding the xth root of y and the yth root of x? These would both
> give
> >
> > If you are acquainted with the difficulty of computing roots in numerical
> > computations, I am afriad you would hesitate a bit. Further what you
> > described later in the post seems not to be clear, unless you would
> > kindly provide a concrete numerical example.
> >
> > M. K. Shen
>
> G. As an example, say your public key was a number 100 digits long, and this
> was the first hundred digits of 59 e 1/43, or the 43rd root of 57, an
> irrational number. Seeing the public key, parties A and B know 43 and 57, so
> they reverse it and find the 57th root of 43, or 43 e 1/57, get the first
> 100 digits and use that as a key. From the public key someone would have to
> work out the numbers 59 and 43 to find the actual key being used. Of course
> instead of 43 and 57 one would use much larger numbers. Because the key in
> both cases is part of an irrational number there should be no clue as to the
> values of 43 and 57, except by trying all combinations.
Questions:
1. Do you happen to have a good piece of software to calculate the
100 digits of 43rd root of 57? There are special softwares. My point
is that the computing job can be very expensive for the proper
communication partners if the figures involved are large.
2. For a legitimate user of your system, how is he going to determine
the values x and y, given 100 digits that are known to be the x-th
root of y? (This is an entirely different task than computing the
100 digits of x-th root of y, given x and y.)
3. I don't understand 'Seeing the public key, parties A and B know 43 and
57'. First, whose public key is that? Who posts the 100 digits? Do you
mean that A posts the 100 digits and B will know that A will use 43
and he is to use 57? Second, is you 'public key' for a pair of specific
partners and not like the common public key where A's public key can
be used by anybody wishing to communicate with him? If anybody
is supposed to make use of the 100 digits to communicate with A,
then anybody will use 57. But then why two numbers instead of one
number of the common public key system?
4. Is there a 'private key' in your public key system? Which is that?
5. Could you please give a very simpified yet concrete example
showing the complete history of how B encrpyts his message to A
and A decrypt that?
Thanks.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: No-Key Encryption
Date: Tue, 30 May 2000 12:56:31 GMT
On 29 May 2000 06:24:01 GMT, [EMAIL PROTECTED] (Decklin Foster)
wrote, in part:
>Unless I'm missing something, this doesn't make sense. An eavesdropper
>would see M+A, M+B, and M+A+B, and thus would able to recover M, A,
>and B.
That's correct, and it is also true if multiplication replaced XOR.
However, if exponentiation is used, then the Shamir three-pass
protocol yields the Massey-Omura cryptosystem, which does work.
And I'm gratified to see that I correctly understood what he meant by
"no-key encryption", although I'm still disappointed no one else seems
to have done so.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: Marc Living <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Tue, 30 May 2000 14:00:58 +0100
On Mon, 29 May 2000 19:51:59 +0000, [EMAIL PROTECTED] (David
Boothroyd) wrote:
>> The idea that the data may not be encrypted, or the suspect
>> may not have the key and cannot prove this. After all, if plod
>> knew what it was then they would not need the key - they must have
>> only suspicions.
>People cannot be put in jail because they have lost their keys, as
>Ministers have made clear during debate on the bill.
And who bears the burden of proving this?
--
Marc Living (remove "BOUNCEBACK" to reply)
***********************************************
Nor shall we proceed against a freeman, nor
condemn him but by lawful judgment of his peers
or by the law of the land.
http://www.holbornchambers.co.uk
************************************************
------------------------------
From: Marc Living <[EMAIL PROTECTED]>
Crossposted-To:
uk.media.newspapers,uk.legal,alt.security.pgp,alt.privacy,uk.politics.parliament,uk.politics.crime,talk.politics.crypto,alt.ph.uk,alt.conspiracy.spy,alt.politics.uk,uk.telecom
Subject: Re: RIP Bill 3rd Reading in Parliament TODAY 8th May
Date: Tue, 30 May 2000 14:01:00 +0100
On Tue, 30 May 2000 00:24:27 +0000, [EMAIL PROTECTED] (David
Boothroyd) wrote:
>A section 19 certificate is a statement by the Minister responsible for
>the Bill which states whether or not it complies with the European
>Convention on Human Rights. This statement is made on the advice of the
>government's law officers. The terms of the European Convention are,
>of course, those as drafted in the early 1950s and agreed internationally.
A section 19 certificate has two functions one overt, and one which
arises by implication.
The overt function is to confirm that, in the relevant Minister's
opinion, the Bill is compatible with the HRA. This doesn't bind the
courts in any way - since the final decision on compatibility is
theirs.
The implied function though is to inform the courts that Parliament
*intended* the Act to be compatible with the HRA - so that if there is
any reasonable way of interpreting the Act so as to retain
compatibility with the HRA, then the courts should so interpret it.
--
Marc Living (remove "BOUNCEBACK" to reply)
***********************************************
Nor shall we proceed against a freeman, nor
condemn him but by lawful judgment of his peers
or by the law of the land.
http://www.holbornchambers.co.uk
************************************************
------------------------------
Subject: email list for the contest
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 30 May 2000 06:06:43 -0700
Here are the revelant email addys you need to know.
Addresses:
Post message: [EMAIL PROTECTED]
Subscribe: [EMAIL PROTECTED]
Unsubscribe: [EMAIL PROTECTED]
List owner: [EMAIL PROTECTED]
URL to this page: http://www.egroups.com/group/ciphercontest
This way we can specialize the discussion for the contest.
All are welcome to join the list.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: No-Key Encryption
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 30 May 2000 06:08:48 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
>On 29 May 2000 06:24:01 GMT, [EMAIL PROTECTED] (Decklin
Foster)
>wrote, in part:
>
>>Unless I'm missing something, this doesn't make sense. An
eavesdropper
>>would see M+A, M+B, and M+A+B, and thus would able to recover
M, A,
>>and B.
>
>That's correct, and it is also true if multiplication replaced
XOR.
>However, if exponentiation is used, then the Shamir three-pass
>protocol yields the Massey-Omura cryptosystem, which does work.
>
>And I'm gratified to see that I correctly understood what he
meant by
>"no-key encryption", although I'm still disappointed no one
else seems
>to have done so.
If I get the 3-pass protocal it is:
A wants to send B 'm'.
1. A sends m^e mod p
2. B sends m^e^d mod p
3. A sends m^e^d^-e nod p
B recovers 'm' via m^e^d^-d^-e mod p
Then 'e' and 'd' are your keys. This is hardly 'no-key'
encryption.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Date: Tue, 30 May 2000 09:22:40 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Bryan Olson wrote:
> Steve Roberts wrote:
>
> > Er, ROT-13 *does* have a key - it's the "13" in the name. Maybe it
> > could be called "Known-Key Encryption"
>
> I suppose that's arguable.
>
> What I'm going to argue is that ROT-13 is not even
> encryption as we use the term today. ROT-13 lacks the
> defining adversarial characteristic, since it is designed to
> keep plaintext from exactly those who do not want to see it.
Interesting observation.
The criteria excluding such courtesy transforms is that they impose the same
work factor on the intended and unintended readers. Transforms with unity
work factor ratios really aren't ciphers.
------------------------------
Date: Tue, 30 May 2000 09:34:01 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Bryan Olson wrote:
> Trevor L. Jackson wrote:
> >
> > Michael Pellaton wrote:
> >
> > > It seems to me that I used the wrong name of a method of encryption.
> > > Maybe it's an error that occurred during translation from and to
> > > German (I have seen the word "no-key encryption" in at least two
> > > German books).
> > >
> > > I'd like to explain what I mean with "No-Key-Encryption" in a
> > > small example:
> > >
> > > Assume Alice wants to send a message to Bob.
> > >
> > > The message is M = 10101100
> > > Alice has a private key A = 11011001
> > > Bob has a private key B = 00010111
> > >
> > > Now, Alice encrypts her message with her private key
> > > M XOR A = Ma = 01110101
> > >
> > > and sends Ma to Bob. Bob can't decrypt the message, but he can
> > > encrypt it again using his key
> > > Ma XOR B = Mab = 01100010
> > >
> > > Now Bob sends Mab back to Alice. She decrypts it with her key A
> > > Mab XOR A = Mb = 10111011
> > >
> > > and again sends it to Bob who is now able to decrypt the Message
> > > with his key
> > > M = Mb XOR B = 10101100
> > >
> [...]
> > The reason your system works is that the combining operation
> > is associative,
>
> I think it's a little subtler. We can build the scheme
> from an invertible associative operation, call it *, as:
>
> ----- k1 * x ----->
>
> <-- k1 * x * k2 ----
>
> ----- x * k2 ------>
>
> But what we want is somewhat more general: the encryption
> functions must commute. (Which is not the same as saying
> each encryption function must be a commutative operation
> on message and key.)
>
> Let D_k denote the inverse of E_k, then we need:
>
> D_k2(D_k1(E_k2(E_k1(x)))) = x
>
> Applying E_k2 to both sides:
>
> D_k1(E_k2(E_k1(x))) = E_k2(x)
>
> Applying E_k1 to both sides:
>
> E_k2(E_k1(x)) = E_k1(E_k2(x))
Yes. Functional notation makes the concept much clearer. I did not describe
the relationship with sufficient care.
>
> > which is also the reason it, and all system like it, are
> > trivially useless. Once an opponent has M+Ka and M+Kb
> > recovering M is not hard. Given M recovering the keys is
> > not hard.
>
> That's certainly true of the XOR scheme Michael Pellaton
> presented. It seems not to be true of other encryption
> functions, such as:
>
> E_k(x) = x^k mod p
> where p is prime and gcd(k, p-1) = 1
>
> Shamir proposed this one for his "Three-Pass Protocol".
> (There are a few other subtle points I'll omit.)
>
> Suppose we limit ourselves to the associative operation
> case. Does there exist an associative operation "*" such
> that the protocol illustrated above is secure? I don't
> know.
>
> --Bryan
> --
> email: bolson at certicom dot com
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "G. Orme" <[EMAIL PROTECTED]>
Subject: Re: new public key?
Date: Tue, 30 May 2000 14:05:55 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> "G. Orme" schrieb:
>
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > >
> > >
> > > "G. Orme" wrote:
> > >
> > > > [snip]
> > > > multiplied together makes a number xy often difficult to factor. Has
> > anyone
> > > > tried finding the xth root of y and the yth root of x? These would
both
> > give
> > >
> > > If you are acquainted with the difficulty of computing roots in
numerical
> > > computations, I am afriad you would hesitate a bit. Further what you
> > > described later in the post seems not to be clear, unless you would
> > > kindly provide a concrete numerical example.
> > >
> > > M. K. Shen
> >
> > G. As an example, say your public key was a number 100 digits long, and
this
> > was the first hundred digits of 59 e 1/43, or the 43rd root of 57, an
> > irrational number. Seeing the public key, parties A and B know 43 and
57, so
> > they reverse it and find the 57th root of 43, or 43 e 1/57, get the
first
> > 100 digits and use that as a key. From the public key someone would have
to
> > work out the numbers 59 and 43 to find the actual key being used. Of
course
> > instead of 43 and 57 one would use much larger numbers. Because the key
in
> > both cases is part of an irrational number there should be no clue as to
the
> > values of 43 and 57, except by trying all combinations.
>
> Questions:
>
> 1. Do you happen to have a good piece of software to calculate the
> 100 digits of 43rd root of 57? There are special softwares. My point
> is that the computing job can be very expensive for the proper
> communication partners if the figures involved are large.
G. I agree the job is difficult, but this is an advantage as it is equally
difficult for someone to
crack it by trying different numbers.
>
> 2. For a legitimate user of your system, how is he going to determine
> the values x and y, given 100 digits that are known to be the x-th
> root of y?
G. He never has to work this out. Only someone trying to crack the code has
to work it out, which is very difficult.
(This is an entirely different task than computing the
> 100 digits of x-th root of y, given x and y.)
G. Users would already have the public keys worked out. They would see a
public key advertised, and look it up and find the values of x and y. They
would then recalculate the key to use between them. Let's say for example A
sends a message to B that is encrypted, and with it he sends the 100 digit
key which A knows is the first 100 digits of the 43rd root of 57. He then
knows that the message is encrypted with the first 100 digits the 57th root
of 43. The initial 100 digit public key is then a way for A to tell B that
the key is the 57th root of 43. For an eavesdropper to work this out he must
calculate all possible roots until he finds 43 and 57, then calculate out
the new key 57th root of 43. If the numbers are large this would take a long
time.
>
> 3. I don't understand 'Seeing the public key, parties A and B know 43 and
> 57'. First, whose public key is that?
A and B prepare beforehand to send messages. There may be many thousands of
values of the xth root of y or the yth root of x already worked out for
different values of x and y.
Who posts the 100 digits? Do you
> mean that A posts the 100 digits and B will know that A will use 43
> and he is to use 57?
G. Each person uses both numbers 43 and 57. Posting the 100 digit number
signals to B that 43 and 57 are the numbers to use because he knows this
already. it is a signal to him to create a new 100 digit key with these
numbers switched. This is not the best way to do it, but just to illustrate
that the key is hard to crack.
If you are familiar with RSA, then you know that it works because it is
difficult to factorise large numbers. Say a large number xy is used someone
can crack the cipher by finding the factors x and y. Now one can use the xth
root of y in exactly the same operations as xy in RSA. Posting a 100 digits
of the xth root of y invites someone to try to crack this just as they might
crack xy. You can then use x and y in this system exactly as you would use
them in RSA. These kinds of codes work because it is hard to find the
factors of large numbers. This would also work because it is hard to find
the values x and y if the number posted is the xth root of y.
Second, is you 'public key' for a pair of specific
> partners and not like the common public key where A's public key can
> be used by anybody wishing to communicate with him? If anybody
> is supposed to make use of the 100 digits to communicate with A,
> then anybody will use 57. But then why two numbers instead of one
> number of the common public key system?
>
> 4. Is there a 'private key' in your public key system? Which is that?
>
> 5. Could you please give a very simpified yet concrete example
> showing the complete history of how B encrpyts his message to A
> and A decrypt that?
>
> Thanks.
>
> M. K. Shen
G. many code systems work with an algorithm that is easy to work out one way
difficult in reverse. Factoring a large number is one example, and the xth
root of y is another possibly new kind of system. X and y are used as they
normally are in these systems.
>
>
------------------------------
Reply-To: "DD" <[EMAIL PROTECTED]>
From: "DD" <[EMAIL PROTECTED]>
Subject: Re: No-Key Encryption
Date: Tue, 30 May 2000 15:07:55 +0100
tomstd <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (John Savard) wrote:
> >On 29 May 2000 06:24:01 GMT, [EMAIL PROTECTED] (Decklin
> Foster)
> >wrote, in part:
> >
> >>Unless I'm missing something, this doesn't make sense. An
> eavesdropper
> >>would see M+A, M+B, and M+A+B, and thus would able to recover
> M, A,
> >>and B.
> >
> >That's correct, and it is also true if multiplication replaced
> XOR.
> >However, if exponentiation is used, then the Shamir three-pass
> >protocol yields the Massey-Omura cryptosystem, which does work.
> >
> >And I'm gratified to see that I correctly understood what he
> meant by
> >"no-key encryption", although I'm still disappointed no one
> else seems
> >to have done so.
>
> If I get the 3-pass protocal it is:
>
> A wants to send B 'm'.
>
> 1. A sends m^e mod p
> 2. B sends m^e^d mod p
> 3. A sends m^e^d^-e nod p
>
> B recovers 'm' via m^e^d^-d^-e mod p
>
> Then 'e' and 'd' are your keys. This is hardly 'no-key'
> encryption.
>
It is no-key in thye sense that neither user has a key.
It's generated on the fly (e.g. a session key) and exchanged
like in Diffie-Hellman.
Dermot.
> Tom
>
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network
*
> The fastest and easiest way to search and participate in Usenet - Free!
>
------------------------------
** 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
******************************
