Cryptography-Digest Digest #691, Volume #11 Wed, 3 May 00 00:13:01 EDT
Contents:
Re: Deciphering Playfair (William Rowden)
Re: Any good attorneys? (Tom St Denis)
Re: Any good attorneys? (Tom St Denis)
Re: Any good attorneys? (Tom St Denis)
Re: Any good attorneys? (Tom St Denis)
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net" (Dan
Day)
Re: Any good attorneys? ("Trevor L. Jackson, III")
Progress (Tom St Denis)
Re: Any good attorneys? ("Trevor L. Jackson, III")
Re: Any good attorneys? (Paul Rubin)
Re: Any good attorneys? (jungle)
Re: factor large composite (Diet NSA)
Re: Any good attorneys? (Terry Ritter)
----------------------------------------------------------------------------
From: William Rowden <[EMAIL PROTECTED]>
Subject: Re: Deciphering Playfair
Date: Wed, 03 May 2000 02:12:50 GMT
In article <[EMAIL PROTECTED]>,
Jim Gillogly <[EMAIL PROTECTED]> wrote:
> Automated Playfair attacks without a crib are quite feasible
> using hillclimbing techniques.
I'm not familiar with all of the terminology of hillclimbing techniques,
so I may not phrase the following precisely. However, it's not
immediately obvious to me how one would define "adjacent" solutions
so that there aren't numerous local minima for any given (probably
statistical) measure of "closeness" to the solutions.
One could, for example, define the closeness of a given Playfair square
for a given ciphertext as the deviation from typical frequencies shown
by the "plaintext" produced by deciphering the ciphertext with that
square. One could also produce alternative solutions from a given
Playfair square by swapping any two letters at random. This initial
approach is probably unsophisticated, but nevertheless my question is
this: Is there something about the Playfair cipher that makes it
obvious that such an approach won't result in climbing many false hills?
How do you know such an approach will be significantly better than
brute force?
--
-William
SPAM filtered; damages claimed for UCE according to RCW19.86
PGP key: http://www.eskimo.com/~rowdenw/pgp/rowdenw.asc until 2000-08-01
Fingerprint: FB4B E2CD 25AF 95E5 ADBB DA28 379D 47DB 599E 0B1A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 02:33:57 GMT
Paul Rubin wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >> I'd say bag RC5 for sure. There's not much reason to care about it.
> >> However, the RSA public key algorithm is important and your product
> >> suffers if you don't include it. Even though you're in Canada and
> >> it's unpatented there, you might want to avoid hassles by leaving it
> >> out for now. But on September 20 when the US patent expires, please
> >> put it back.
> >
> >Hmm well I already deleted the source (I could restore it from backup)
> >but I seriously want to avoid RSA completely. I don't like getting
> >emails like that.
>
> I don't understand the logic of this. You don't like being bullied
> by RSA, so you're going to get back at the bully by doing exactly what
> he tells you?
It's called I am an 18 year old kid. Why would I throw my life away
just to have RSA patented technology?
I can get by with Cryptobag and PB3 by using other algorithms.
> >At anyrate ElGamal will fill the spot where RSA was quite nicely.
> >
> >I just need a DH pro to talk to (i.e how to minimize the ciphertext size
> >but remain relatively secure).
>
> El Gamal is much slower and makes larger signatures unless you do it
> (for example) over elliptic curves.
I still have some reading todo (I know basic EG right now) but I am
pretty sure you can get by with smaller ciphertext by using
sub-groups...
I would appreciate any info possible wrt to this. As I want to get CB
back out there.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 02:39:47 GMT
Eric Lee Green wrote:
>
> Tom St Denis wrote:
> > I just need a DH pro to talk to (i.e how to minimize the ciphertext size
> > but remain relatively secure).
>
> Huh? Diffie-Hellman is a key exchange mechanism, not an encryption algorithm,
> right? Or are we talking about a different thing?
>
> Here is what I think of when I'm thinking Diffie-Hellman, and what I want from
> a crypto API that implements it:
>
> The size of your modulus detirmines the size of the key exchanged via
> Diffie-Hellman. You can then feed the resulting key to MD5 or some other
> algorithm to get a nice-sized symmetric key for the actual data transfer. So
> basically all that a cryptographic toolkit needs in it for adequate support of
> Diffie-Hellman is: (the below in Python, which uses the "." to seperate class
> or module name from class or module member):
>
> (public,private)=dh.generate(generator,modulus)
>
> Which is implemented as (assuming 1024-bit modulus, and a module 'bigint' that
> is basically the GNU 'mpz' library):
>
> xxtemp=cryptrand.rand(128) # 1024 bit private key.
> private=bigint.bigint(xxtemp) # create a bigint instance with it.
> public=bigint.powm(generator,private,modulus) # create public key
>
> You then transmit your public key to the recipient (or not, if your recipient
> already has it), and the recipient sends you their public key. Then the crypto
> toolkit needs
>
> shared=dh.makeshared(theirpub,ourpriv,modulus)
>
> which is implemented as:
>
> sharedbignum=bigint.powm(theirpub,ourpriv,modulus)
> shared=sharedbignum.binval() # convert a 'bigint' value to a 1024-bit block of
> data
>
> Note that implementation of the bigint class is left as an exercise to the
> reader, as is choice of appropriate modulus and generator :-).
>
> You can then feed the resulting shared key to md5 and use the resulting
> 128-bit value as a key for one of the AES algorithms for doing your actual
> data transfer. Or, assuming that you've selected your generator and modulus
> appropriately, your result should be evenly distributed over the field, so
> since your input was a 1024 bit truly random number, you should have 1023 bits
> of randomness (at least) in the result, so theoretically you could just take
> 128 or 256 bits anywhere from the result and they'll be a random shared key.
> That depends upon not making a stupid mistake with your modulus and/or
> generator.
Sorry I wasn't clear I was planning on doing ElGamal not DH. However I
don't think adding DH to CB is a bad idea either.
What about this modification to DH encryption...
You have a private key x, and public key y=g^x
if I want to send a message I make up a 'j', (and send y^j) and use the
hash of y^j as the symmetric key. This means the ciphertext will be the
same size as the modulus. Which is a bonus.
Any ideas to speedup size-reduce signatures? I don't want to reduce the
size of the group though (i.e DSS).
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 02:40:21 GMT
jungle wrote:
>
> you are in UK [ tom ], the RSA patent is in USA, what is the problem ?
> is it [ RC5 ] patented in UK ? if not ask RSA to patent RC5 in UK & contact
> you after it will be issued / completed ...
Actually I am in Canada. I am choosing to avoid the company all
together.
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 02:42:50 GMT
Tom St Denis wrote:
>
> Eric Lee Green wrote:
> >
> > Tom St Denis wrote:
> > > I just need a DH pro to talk to (i.e how to minimize the ciphertext size
> > > but remain relatively secure).
> >
> > Huh? Diffie-Hellman is a key exchange mechanism, not an encryption algorithm,
> > right? Or are we talking about a different thing?
> >
> > Here is what I think of when I'm thinking Diffie-Hellman, and what I want from
> > a crypto API that implements it:
> >
> > The size of your modulus detirmines the size of the key exchanged via
> > Diffie-Hellman. You can then feed the resulting key to MD5 or some other
> > algorithm to get a nice-sized symmetric key for the actual data transfer. So
> > basically all that a cryptographic toolkit needs in it for adequate support of
> > Diffie-Hellman is: (the below in Python, which uses the "." to seperate class
> > or module name from class or module member):
> >
> > (public,private)=dh.generate(generator,modulus)
> >
> > Which is implemented as (assuming 1024-bit modulus, and a module 'bigint' that
> > is basically the GNU 'mpz' library):
> >
> > xxtemp=cryptrand.rand(128) # 1024 bit private key.
> > private=bigint.bigint(xxtemp) # create a bigint instance with it.
> > public=bigint.powm(generator,private,modulus) # create public key
> >
> > You then transmit your public key to the recipient (or not, if your recipient
> > already has it), and the recipient sends you their public key. Then the crypto
> > toolkit needs
> >
> > shared=dh.makeshared(theirpub,ourpriv,modulus)
> >
> > which is implemented as:
> >
> > sharedbignum=bigint.powm(theirpub,ourpriv,modulus)
> > shared=sharedbignum.binval() # convert a 'bigint' value to a 1024-bit block of
> > data
> >
> > Note that implementation of the bigint class is left as an exercise to the
> > reader, as is choice of appropriate modulus and generator :-).
> >
> > You can then feed the resulting shared key to md5 and use the resulting
> > 128-bit value as a key for one of the AES algorithms for doing your actual
> > data transfer. Or, assuming that you've selected your generator and modulus
> > appropriately, your result should be evenly distributed over the field, so
> > since your input was a 1024 bit truly random number, you should have 1023 bits
> > of randomness (at least) in the result, so theoretically you could just take
> > 128 or 256 bits anywhere from the result and they'll be a random shared key.
> > That depends upon not making a stupid mistake with your modulus and/or
> > generator.
>
> Sorry I wasn't clear I was planning on doing ElGamal not DH. However I
> don't think adding DH to CB is a bad idea either.
>
> What about this modification to DH encryption...
>
> You have a private key x, and public key y=g^x
>
> if I want to send a message I make up a 'j', (and send y^j) and use the
> hash of y^j as the symmetric key. This means the ciphertext will be the
> same size as the modulus. Which is a bonus.
Err.. that should read
Send "g^j" as the encryption parameter... the user can now use g^j^x as
the private key, whereas the sender can use y^j.
Tom
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
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
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: Wed, 03 May 2000 03:03:47 GMT
On Tue, 02 May 2000 15:16:50 GMT, [EMAIL PROTECTED] (JimD) wrote:
>>
>>This crap is getting out of hand.
>
>Yes. But they won't have the staff, technical or financial
>resources to do it.
Once they have the means, they'll make sure they solve the
resource problem...
------------------------------
Date: Tue, 02 May 2000 23:21:20 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Terry Ritter wrote:
> On Wed, 03 May 2000 00:00:07 +0200, in
> <[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
> <[EMAIL PROTECTED]> wrote:
> >[...]
> >But, for example, there are other algorithms that use S-boxes. Can one
> >say that, because the S-boxes of DES have currently no more patent
> >impacts (BTW was DES ever patented?), the S-boxes of a patented
> >algorithms can be imitated without problems?
>
> Again, I am not a patent lawyer. This is not legal advice.
>
> I doubt there was a patent on the "S-boxes" per se, since Simple
> Substitution is classical. There was a patent on the Feistel type of
> cipher, which *used* "S-boxes," but that would not protect the use of
> "S-boxes" in other ciphers. In the usual case, what is protected is a
> particular set of previously-known things, arranged in a new way.
>
> But to understand patent coverage, we simply *must* actually read the
> claims and see if they "read on" the other system. If all claim
> elements are present in the other system, that system infringes, even
> if it also has a lot of other stuff.
Actually, it takes even more than this because claims that are too wide (cover
prior art or another patent) are invalid. To infringe on has to use something
covered by a valid claim. This interconnected set of issues is why patent
suits are one of the most expensive kinds of suit there is.
>
>
> Interpreting patent claims is not necessarily simple, but there *are*
> no simple answers: Every court case has lawyers on both sides, and
> oftentimes *both* are convinced they are right. We can sit back and
> say, "Oh, no, that sounds too hard for me," but in reality it may not
> be quite as hard as one might imagine.
>
> ---
> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Progress
Date: Wed, 03 May 2000 03:22:58 GMT
In the wake of that little upset I am still working on CB. I have just
finished three routines for the ElGamal handling. I still have about
five more todo, then I have to fix up the rest of the library and make a
couple good test programs.
If anyone wants to help out please let me know. I sincerely want to get
this package back on the road again.
One thing I have been thinking about, to show off CB would anyone be
interested in a command line pgp style application? Would certainly be
a good way to test CB on multiple platforms while being productive. If
you want to help with this please let me know.
Thanks,
Tom
--
Want your academic website listed on a free websearch engine? Then
please check out http://tomstdenis.n3.net/search.html, it's entirely
free
and there are no advertisements.
------------------------------
Date: Tue, 02 May 2000 23:32:58 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Tom St Denis wrote:
> Paul Rubin wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> > >I think it's funny too, but I will just avoid all RSA (tm) products
> > >(hehehe) from CB in the future.
> > >
> > >I already have other block ciphers (Blowfish, Twofish, Serpent,
> > >CAST-128, Skip-jack, XTEA, GOST), and am adding DH to it now.
> >
> > I'd say bag RC5 for sure. There's not much reason to care about it.
> > However, the RSA public key algorithm is important and your product
> > suffers if you don't include it. Even though you're in Canada and
> > it's unpatented there, you might want to avoid hassles by leaving it
> > out for now. But on September 20 when the US patent expires, please
> > put it back.
>
> Hmm well I already deleted the source (I could restore it from backup)
> but I seriously want to avoid RSA completely. I don't like getting
> emails like that.
I suggest you reconsider. If RSA is not patented in Canada there is
absolutely nothing the owners of the US patent can do to you except send nasty
messages. If you react to their messages the way they want, by withdrawing
your product from the "market", you have handed them a victory they do not
deserve. If you decide that RSA's techniques are inferior to the
alternatives, then you should banish them from your software. However, you
may want to offer some backward compatibility so there may be some trivial
residual value in leaving it in.
Note that you are free to do as you choose because their letter carries no
weight. If you fail to exercise your freedom, you have lost it. I suggest
that an appropriate response to such a silly message is to send _them_ a
message forbidding them from using any of your software for any purpose (by
publishing it you created a copyrighted interest in it). You should copy not
only the lawyer but the officers of the company, and publish the message so
they get the publicity they deserve.
>
>
> At anyrate ElGamal will fill the spot where RSA was quite nicely.
So have your documentation recommend the superior technique, but keep the
deprecated RSA techniques around for their backwardness.
>
>
> I just need a DH pro to talk to (i.e how to minimize the ciphertext size
> but remain relatively secure).
>
> Tom
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Any good attorneys?
Date: 3 May 2000 03:28:32 GMT
In article <[EMAIL PROTECTED]>,
>> Tom St Denis <[EMAIL PROTECTED]> wrote:
>> >> I'd say bag RC5 for sure. There's not much reason to care about it.
>> >> However, the RSA public key algorithm is important and your product
>> >> suffers if you don't include it. Even though you're in Canada and
>> >> it's unpatented there, you might want to avoid hassles by leaving it
>> >> out for now. But on September 20 when the US patent expires, please
>> >> put it back.
>> >
>> >Hmm well I already deleted the source (I could restore it from backup)
>> >but I seriously want to avoid RSA completely. I don't like getting
>> >emails like that.
>>
>> I don't understand the logic of this. You don't like being bullied
>> by RSA, so you're going to get back at the bully by doing exactly what
>> he tells you?
>
>It's called I am an 18 year old kid. Why would I throw my life away
>just to have RSA patented technology?
It is only RSA patented technology until September 20. After that, it
is unpatented. The September 20 expiration date is published on RSA's
own web page. In 12184428 seconds (141 days, 00:34:48), RSA will join
the steam engine and aspirin as inventions whose patents have expired
and which will be in the public domain.
(RSA Patent Clock: http://www.kfu.com/~nsayer/encryption/rsaclock.html)
>> El Gamal is much slower and makes larger signatures unless you do it
>> (for example) over elliptic curves.
>
>I still have some reading todo (I know basic EG right now) but I am
>pretty sure you can get by with smaller ciphertext by using
>sub-groups...
It sounds like you are talking about DSA. If you don't have a DSA
implementation, you should add one. There is also a trick for
compressing the key exchange messages in DH by turning them into a
pair of DSA signatures. I think the paper is by Young and Yung in
Crypto 97.
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Tue, 02 May 2000 23:39:08 -0400
when you are in CANADA [ tom ], the RSA patent is in USA, what is the problem
?
is it [ RC5 ] patented in CANADA ? if not ask RSA to patent RC5 in CANADA &
contact
you after it will be issued / completed ...
above is the first step for your defense options ...
what is the problem ?
you removed your product from web site ?
Tom St Denis wrote:
>
> jungle wrote:
> >
> > you are in UK [ tom ], the RSA patent is in USA, what is the problem ?
> > is it [ RC5 ] patented in UK ? if not ask RSA to patent RC5 in UK & contact
> > you after it will be issued / completed ...
>
> Actually I am in Canada. I am choosing to avoid the company all
> together.
>
> Tom
------------------------------
Subject: Re: factor large composite
From: Diet NSA <[EMAIL PROTECTED]>
Date: Tue, 02 May 2000 20:41:00 -0700
In article <Y3JP4.1643$PY3.2104@client>,
"Dann Corbit" <[EMAIL PROTECTED]>
wrote:
>QC is currently absurdly infeasible for factoring of large
numbers and there
>are no valid projections as to when it will become feasible, or
if it ever
>will, for that matter. Have another slice of pie.
Thanks, I will have my pie and eat it too.
Your postings have reminded me of earlier
"pie-in-the-sky" ideas such as going to
the moon, nuclear energy, and PCs.
"640K of memory ought to be enough for anybody" - Bill Gates (1981)
=================================================================
* 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: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 03:48:55 GMT
On Tue, 02 May 2000 23:21:20 -0400, in <[EMAIL PROTECTED]>,
in sci.crypt "Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>
>> On Wed, 03 May 2000 00:00:07 +0200, in
>> <[EMAIL PROTECTED]>, in sci.crypt Mok-Kong Shen
>> <[EMAIL PROTECTED]> wrote:
>> >[...]
>> >But, for example, there are other algorithms that use S-boxes. Can one
>> >say that, because the S-boxes of DES have currently no more patent
>> >impacts (BTW was DES ever patented?), the S-boxes of a patented
>> >algorithms can be imitated without problems?
>>
>> Again, I am not a patent lawyer. This is not legal advice.
>>
>> I doubt there was a patent on the "S-boxes" per se, since Simple
>> Substitution is classical. There was a patent on the Feistel type of
>> cipher, which *used* "S-boxes," but that would not protect the use of
>> "S-boxes" in other ciphers. In the usual case, what is protected is a
>> particular set of previously-known things, arranged in a new way.
>>
>> But to understand patent coverage, we simply *must* actually read the
>> claims and see if they "read on" the other system. If all claim
>> elements are present in the other system, that system infringes, even
>> if it also has a lot of other stuff.
>
>Actually, it takes even more than this because claims that are too wide (cover
>prior art or another patent) are invalid. To infringe on has to use something
>covered by a valid claim.
Most patents are constructed with a few independent broad claims, and
a multitude of narrower dependent claims which further restrict one of
the independent claims. The hope is that even if new prior art is
found for the broad claim, one of the narrow claims will survive.
All this is good to know, but everything starts with actually reading
claims instead of imagining what they must be.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.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
******************************
