[Botan-devel] ECC for Botan [Re: a build result of Botan-1.7.5]

Jack Lloyd lloyd at randombit.net
Thu Apr 24 16:29:49 EDT 2008


On Thu, Apr 24, 2008 at 09:45:32PM +0200, Saber Mbarek wrote:
> PS: I want to implement/develop some algorithm (may be from (hyper)elliptic
> curves cryptography) into botan..
> Do you have any idea? Could you assist me?

[CC'ing botan-devel since this is of general interest]

Much of the public key code is more complex than it need be (I have
been considering exactly the problem of adding new PK algorithms in a
sane/easy manner, and what needs to change in that area). Much of this
complexity comes from: need for serialization (X.509 certificates),
and desire for supporting hardware. For an initial implementation,
both of these can be safely ignored.

Here is my general suggestion about how to approach this:

Step 0: Choose algorithm(s) to implement

Step 1: Write out basic operations (key gen plus sign/verify, or
whatever ops are appropriate to the algorithm). This could be a simple
standalone class (or two: one for public key / public ops and another
for private key / private ops) or even just some functions, that used
Botan's BigInt and other math code for low-level stuff.

Step 2 (after the basic algorithm works and has been tested) is
modifying it to fit into Botan's worldview. The required derivations
depend on which exact algorithm, but at least you would have to
implement the Public_Key and Private_Key interfaces from pk_keys.h

Step 3: X.509 serialization, set OIDs, etc (this part is not hard once
you have finished step 2, just a hassle and not that fun/interesting
IMO)

Step 4: Plug it in. In Botan/pk_algs.cpp, there is this nasty bit of work:

   if(alg_name == "RSA")      return new RSA_PublicKey;
   else if(alg_name == "DSA") return new DSA_PublicKey;
   else if(alg_name == "DH")  return new DH_PublicKey;
   else if(alg_name == "NR")  return new NR_PublicKey;
   else if(alg_name == "RW")  return new RW_PublicKey;
   else if(alg_name == "ELG") return new ElGamal_PublicKey;
   else
      return 0;

Lines such as:
   else if(alg_name == "ECDSA")  return new ECDSA_PublicKey;
can easily be added.

Step 5: Modify to handle backend hardware/software engines

These steps are, happily, more or less ordered by:
  - How interesting the work is (well, at least from my viewpoint)
  - Likelyhood that it will work in both 1.6 and 1.7/1.8 - the last
    steps touch code that is quite likely to change in 1.7, but
    hopefully in ways that eliminates/simplifies said boring or
    unpleasant steps.

Let me know if you have other questions. I would be particularly
interested in ECDH/ECDSA over GF(p), which are fairly mundane
algorithms to be sure, but have the advantages of being easy to
implement (Botan has little to no support for GF(2^n), for one thing),
widely useful, and avoiding the worst of the ECC patent minefield.

Steps 1+2 are by far the most useful - even without any support for
X.509 encodings and so forth, ECC would be a valuable addition.

-Jack



More information about the botan-devel mailing list