From: schirado@lab.cc.wmich.edu (Schirado)
Date: Wed, 27 Apr 94 22:55:09 PDT
To: cypherpunks@toad.com
Subject: PROGRAMMING: Assessment wanted.
Message-ID: <9404280555.AA15128@lab.cc.wmich.edu>
MIME-Version: 1.0
Content-Type: text



I'm not a programmer, so this is all over my head. I'm just
throwing this out as a public service. I will forward mail
to the original author.

***


If a subscriber has the time and interest, I can supply them with
sources to build a new public key cryptography system based on
unpatented and UNPATENTABLE (because they are already published)
cryptographic systems which have an entire level of better security
than that RSA rubbish. So far, it appears that keys in the
neighborhood of 100-200 bits are equivalent to the "600" bits for RSA
and the "military grade" claims of 1024 bits (PGP) should be easily
doable in around 300-400 bits.

Requirements: You need to either have a good grasp on finite
mathematics (fields, rings, and such..just a basic understanding is
all that is necessary) or willing to spend the time to learn it (about
a week if you are already math-inclined).

You need programming skill too (of course).

I would also recommend that you use a different compression system
from that LZ-based stuff that half the world is using in favor of
higher order Markov tree things (I will supply complete references for
this too).

I am doing this because I have the necessary information but lack the
time to develop this project further.

[...]


Okay, for a good overview paper of doing it in hardware (the software
solution is also possible..just that you can't do it quite the
same..online that is), see _An Implementation of Elliptic Curve
Cryptosystems Over F-2-155_ , IEEE Journal on Selected Areas in
Communications, Vol. 11, #5, June 1993 (page 804).


Essentially, nonsupersingular elliptic curves over the finite group of
characteristic 2 become reducible to the discrete logarithm problem.
Watch when you are looking for papers and doing the research for stuff
by Neal Koblitz..he really knows his stuff and wrote a very good
introductory book to finite arithmetic and cryptology, although the
elliptic curve system in the book was written before the hole in the
supersingular case was known.

Elliptic curve cryptosystems appear to be the strongest known public
key cryptosystem on a per-bit basis in existence. The algorithm is
still horrendously slow (just like RSA-based stuff) so don't expect to
be doing the encryption/decryption in real time unless you're building
it in hardware.

The paper mentioned above has all the references you'll need. Use a
good solid block cypher for actual encryption and just encrypt a seed
using the public key stuff. Do us all a favor and publish it in
library as well as full-blown software package form and allow for
plug-in encryption modules as well as key management systems so the
software doesn't have to be done all over again each time. Same with
any compression software you put in it.

As far as compression (lossless) goes, you'll have to search for the
papers on that because my copy appears to have been borrowed and not
returned. Look for "Prediction by Partial Matching" or "PPM". This is
a multiple-order Markov solution which does better than the LZ-based
things.