Cryptography-Digest Digest #690, Volume #11 Tue, 2 May 00 22:13:01 EDT
Contents:
Re: Any good attorneys? (Paul Rubin)
Re: about search and seisure of computers again-reality check (jungle)
Re: Any good attorneys? (Eric Lee Green)
Re: Deciphering Playfair (long) (Jim Gillogly)
Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
("Garry Anderson")
Re: Any good attorneys? (jungle)
Questions about imaginary quadratic orders (David Hopwood)
Re: Any good attorneys? (Terry Ritter)
Re: Silly way of generating randm numbers? (David A. Wagner)
Re: Any good attorneys? (Scott Contini)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Any good attorneys?
Date: 2 May 2000 23:26:23 GMT
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?
>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.
------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy.anon-server,alt.privacy,alt.2600
Subject: Re: about search and seisure of computers again-reality check
Date: Tue, 02 May 2000 19:31:10 -0400
one of the best ...
create scramdisk container for delete purposes, move to it
instead delete files ...
when container is full, delete scramdisk container ...
one better solution than above one ...
never delete anything, use wipe from PGP with 3 passes every time ...
AlienZen wrote:
> Well, again, the best defence is a good encryption...
> If you want to delete something, delete the whole encrypted folder.
> Move everything you want to keep into a new folder, and delete the old.
> Let 'em try to recover that!!!
> Hail Scramdisk!!
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Tue, 02 May 2000 23:48:32 GMT
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.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Deciphering Playfair (long)
Date: Wed, 03 May 2000 00:06:36 +0000
William Rowden wrote:
> I'm not certain how to interpret this; do you have probable plaintext,
> or not? The "experts" think that solving Playfair by hand requires a
> crib.
That's not required, actually. Private Alf Monge solved a very short
Playfair without a crib, based on some inspired guesses about the
nature and placement of the keyword, in the pencil-and-paper era.
Many others have solved the longer ciphertext-only Playfair challenge
cipher in Simon Singh's "The Code Book".
Automated Playfair attacks without a crib are quite feasible
using hillclimbing techniques. Even simpler, if you have an
idea of the keying strategy, is a dictionary attack.
--
Jim Gillogly
Sterday, 13 Thrimidge S.R. 2000, 00:02
12.19.7.3.3, 2 Akbal 6 Uo, Ninth Lord of Night
------------------------------
From: "Garry Anderson" <[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
Subject: Re: Sunday Times 30/4/2000: "MI5 builds new centre to read e-mails on the net"
Date: Wed, 3 May 2000 01:41:24 +0100
JimD <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Mon, 01 May 2000 20:06:12 GMT, [EMAIL PROTECTED] (Dan Day) wrote:
>
> >On Sun, 30 Apr 2000 10:24:47 +0100, "NoSpam" <[EMAIL PROTECTED]>
wrote:
> >>The government already has powers to tap phone lines linking computers,
> >>but the growth of the internet has made it impossible to read all
> >>material. By requiring service providers to install cables that will
> >>download material to MI5, the government will have the technical
> >>capability to read everything that passes over the internet.
> >
> >This crap is getting out of hand.
>
> Yes. But they won't have the staff, technical or financial
> resources to do it.
Then why did they ask for all this equipment to be put in?
They will not need to read it all information that passes, programs will
look for keywords.
As all your work and social communication comes to be done on the Internet,
the greater your lack of privacy.
You will have a permanent phone tap, for them to do with as they will.
The dangerous criminals and terrorists will get round this - so who do you
think they are going to be looking at?
Visit the number 1 UK organization - www.1UK.org
------------------------------
From: jungle <[EMAIL PROTECTED]>
Subject: Re: Any good attorneys?
Date: Tue, 02 May 2000 21:03:01 -0400
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 ...
> Tom St Denis wrote:
> > I just got a notice from RSA stating...
> >
> > >Please contact RSA Security Inc. immediately regarding your use of the RC5
> > >encryption method (US Patent# 5,724,428) within your PeekBoo PB2, and PB3
> > >toolkit.
> > >This toolkit and its distribution without a license from RSA Security Inc.,
> > >violates US Patent and copyright law.
> > >Please call me at 650-295-7625
> > >
> > Anyone want to help me out?
> > Tom
------------------------------
Date: Wed, 03 May 2000 02:14:57 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Questions about imaginary quadratic orders
=====BEGIN PGP SIGNED MESSAGE=====
I'm attempting to create a public key cryptosystem based on the class group
of an imaginary quadratic order (for those in sci.math, see the post with
title "Forward secrecy and imaginary quadratic orders" in sci.crypt), and
I have some questions about the maths involved:
Let Delta be a negative integer such that abs(Delta) is prime, and
Delta is congruent to 1 (mod 4),
q be a prime integer,
Delta_q = Delta.q^2,
Cl(Delta) be the class group of the maximal imaginary quadratic order
with discriminant Delta,
Cl(Delta_q) be the class group of the non-maximal imaginary quadratic
order with discriminant Delta_q.
Assume that elements of Cl(Delta_q), i.e. equivalence classes of ideals in
the quadratic order with discriminant Delta_q, are represented according
to the "standard representation" described in [HJPT98] (and [BDW89], which
only covers the case of maximal orders), as pairs of integers (a, b),
where (Z + ((b + sqrt(Delta_q))/2.a)Z) is the unique reduced ideal in
the equivalence class.
1. Am I correct in thinking that the class number, h(Delta), is just the
order of the class group, |Cl(Delta)| (and similarly for h(Delta_q))?
2. What is the expected size or range of |Cl(Delta)|, and does its
factorisation "look like" the factorisation of a random integer of
about the same size?
3. What is the standard representation of the identity element?
4. [HJPT98] gives the following algorithm for choosing an element of
Cl(Delta_q), that it claims to be suitable as a base for a Diffie-
Hellman-based cryptosystem:
choose a prime a_g such that the Kronecker symbol (Delta_q / a_g) = 1.
compute b_g as the square root of Delta_q mod 4a_g, using
"Shanks' probabilistic algorithm RESSOL", from [Due91, page 43ff].
g = (a_g, b_g) is the standard representation of a prime ideal
corresponding to the base.
Presumably this doesn't ensure that g has any particular order in
the class group? I.e. the order of g could be any factor of
|Cl(Delta_q)|? If g is to be distributed as uniformly as possible
on Cl(Delta_q), what range should a_g be chosen from?
I don't have a copy of [Due91]; if anyone does, I'd very much
appreciate it if they could post the RESSOL algorithm and the
algorithm for computing a Kronecker symbol, or point me to another
description of these algorithms.
4. In [BW88] (which I haven't read yet), it is apparently proven that
an oracle for computing discrete logarithms in Cl(Delta_q) can be used
to factor Delta_q. How many calls to the oracle are typically needed,
and do the logarithms need to be of specific, as opposed to random
group elements?
If several elements and the corresponding logarithms are needed in
order to make the cryptosystem work, then
a) is it necessary,
b) is it sufficient,
to hide the base to which the logarithms were taken, in order to
prevent factoring Delta_q?
5. In Cl(D) and in Z*_n (the group of units modulo a composite integer
n), taking discrete logarithms requires factoring a parameter that
describes the group (D or n), then calculating discrete logarithms
in a smaller group or groups dependent on the factorisation.
Are there any other finite groups that share this property? (Ideally,
the discrete logarithm problem would be "easy" in the smaller group
for factors of about 300 bits or so.)
[BW88] J. A. Buchmann, H. C. Williams,
"A key exchange system based on imaginary quadratic fields,"
Journal of Cryptology, 1:107-118, 1988.
[BDW89] J. A. Buchmann, S. Duellmann, H. C. Williams,
"On the complexity and efficiency of a new key exchange system,"
Advances in Cryptology - EuroCrypt '89.
[Due91] S. Duellmann,
Ein Algorithmus zur Bestimmung der Klassengruppe positiv definiter
binaerer quadratischer Formen,
PhD thesis, Universitaet des Saarlandes, Saarbrueken, Germany,
1991.
[HJPT98] Detlef Huenlein, Michael J. Jacobson Jr., Sachar Paulus,
Tsuyoshi Takagi,
"A cryptosystem based on non-maximal imaginary quadratic orders
with fast decryption,"
Advances in Cryptology - EuroCrypt '98,
Volume 1403 of Lecture Notes in Computer Science, pp. 294-307,
1998.
http://www.cacr.math.uwaterloo.ca/~mjjacobs/
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOQ99gDkCAxeYt5gVAQH0nggAlWi3+5o6nVcfif2+ksUeu69KKNlUCz9B
FjFXUiKOrL7SZOhBkhFkDK5pJ/6b9TGmOSR3dvPuZO51HngdOd135wG6rGMDejuF
N/nBPfBrj9vDy1GSFTkGbTlb0ih34oULFCtzuc3hobOyR1x3vyXHtS2pl7klbBjK
NfooHNtfog8tJ7dSmJP9eoFLlTFWC/w29xX4ivP8KJwt3354iq2hqXToH5fQnfOa
U38aQ9DUwJr5AK18X0UgHLNZwGCMkTyKLAg8XVEpLf1iexstHnJPL3H8VZPMGzSx
WFY0WxjzGeqg1y0r1TEr8/6z1xIAp5GihxNfndvkqwLUNSwQV4OSYQ==
=7/JK
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Any good attorneys?
Date: Wed, 03 May 2000 01:38:28 GMT
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.
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: [EMAIL PROTECTED] (David A. Wagner)
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: 2 May 2000 18:03:12 -0700
There have been proposals in the past to use transcendental numbers
for generating hopefully-cryptographically-secure pseudorandom
bitstreams, but it seems to be difficult to avoid lattice attacks.
I have attached below excerpts from an informative post that appeared
on sci.crypt several years ago.
> Newsgroups: sci.crypt
> From: Dipankar Gupta <[EMAIL PROTECTED]>
> Subject: Re: Irrational numbers as pseudo-random number streams?
> Message-ID: <[EMAIL PROTECTED]>
> Date: Sat, 27 Sep 1997 18:50:55 GMT
>
> ...
>
> A generic technique for solving such problems is lattice reduction.
> For algebraic numbers, the question is essentially to find a small
> irreducible polynomial p(x) whose root corresponds to the digit
> sequence. If you look at the extension field by adjoining the root,
> then the problem can be rephrased in terms of finding a small basis
> for this extension.
>
> The precise result for algebraic numbers is: if a complex number a is
> the root of an irreducible polynomial p(x) of degree d with integer
> coefficients each of magnitude at most H, then we can find p(x) in
> polytime given O(d^2 + d * log H) bits of the binary expansion of a.
>
> This also works for certain kinds of transcendental numbers;
> e.g. numbers like arccos(a) or log(a) where a is algebraic. The idea
> here is to use a truncated Taylor series for the function cos() or
> log() to build a basis, and then use lattice reduction to find a.
>
> The technique is described in:
>
> R. Kannan, A. K. Lenstra and L. Lovasz, Polynomial factorization and
> non-randomness of bits of algebraic and some transcendental numbers,
> Proc. ACM STOC 84, pp 191-200 (1984).
>
> where they discuss kinds of transcendental numbers that the technique
> can deal with.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Any good attorneys?
Date: 3 May 2000 01:54:25 GMT
In article <[EMAIL PROTECTED]>,
Eric Lee Green <[EMAIL PROTECTED]> 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.
>
It sounds to me like Tom is trying to minimize the number of bits
you have to communicate while still using Diffie-Hellman securely. One
way of doing this is using the recently invented XTR cryptosystem:
http://www.ecstr.com/
I am still learning this cryptosystem, but I believe it provides the
same security (proveably) as the traditional Diffie-Hellman while
communicating less bits. It is also supposed to be faster than
traditional Diffie-Hellman.
Scott
------------------------------
** 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
******************************
