Here is some cryptographic C++ software, mostly written by me, and all public domain i.e. free, you may do whatever you wish with it. However if you operate in the USA beware of patent restrictions. I would be pleased to hear if you find it interesting or useful, or if you have any questions, comments or suggestions.
If you can read zip files you can download all the sources by pressing here.
*** NEW *** PEGWIT ***
I have now written a complete usable program, which combines all the other stuff.
First of all a fast block cipher shark.cpp This is not subject to any patent or licensing restrictions. My source is derived from the reference implementation which you can get from here.
And here is shark's successor, square (also public domain). I can claim no part in this, I have just copied it from the reference implementation and tried it out, but it looks really neat (and very fast), so here it is anyway: square.h square.c and square.tab which is generated by sqgen.c
Correction: It seems square is a distinct new cipher, not shark's successor. However it is from the same stable (Vincent Rijmen). Apparently there is a also a shark2, which is shark with smaller tables, but I have not seen it. Square has a 128-bit block size, and a 128-bit key.
Secondly RSA public key encryption rsa.hpp and rsa.cpp which uses prime.hpp, prime.cpp, vlong.hpp and vlong.cpp. There is no test program for this, but the rsa class should be fairly self-explanatory.
Finally Elliptic curve public key cryptography is more complicated, but has the advantage that the public keys and certificates can be much smaller for the same amount of security.
[ My first effort which used ONB is here. ]
There is a test program nctest.cpp, and elliptic curves ncurve.hpp, ncurve.cpp, ncdata.hpp.
You also need prime.hpp , prime.cpp , vlong.hpp and vlong.cpp..
Also if you want to generate ncdata.hpp for yourself, you need ncurve0.cpp and ncgen.cpp. Note that curve generation takes quite a while (hence ncdata.hpp).
ncdatas.hpp is ncdata.hpp sorted by field size.
Here is the output from the test program. The times are in units of 1/100 second.
For the theory behind the table lookup field operations see this nice paper on representing GF(2^n) as polynomials with coefficients in GF(2^16)
My main source of information has been the IEEE P1363 working draft, which if you are lucky you can find here.
Other links:
Tatu Ylönen's international crypto pages
Change history for elliptic curves
Change(1) (9th Jan 97) (corrected date - my watch was set wrong!) MINP didn't make sense - it has been replaced by MAX_NTF which stands for Maxiumum Non-Trivial-Factor. I have recalculated the magic numbers. I also now reset the initialisation prng before generating curve::P
Change(2) (Also 9th Jan 97) I got rid of curve::a since I don't think it really achieves anything.
Change(3) (Also 9th Jan 97) Spotted nasty bug - in field::mul the declaration of lb is wrong - the length should be K+1 not K. Sorry if this caused you any trouble.
Change(4) (10th Jan 97) If SO is defined, don't bother to allocate qs ( saves storage ) Also re-organised macro definitions. Only use unsigned short (lunit) for large tables.
Change(5) (Also 10th Jan 97) Added two new curves which will work OK on 16-bit computer. CNUM=4 which uses GF(154) is now the default, and is my suggested standard. Fixed small problem with MAX_NTF.
Change(6) (also 10th Jan 97) Made curve selection dynamic i.e. different curves can be selected at run-time. There is now a program ncgen.cpp to generate a table of curve parameters, which is included in the program. Thus if you increase MAXL or MAXK you should execute ncgen.cpp redirecting output to ncdata.hpp. (This can take quite a long time). Fixed bug in initialisation of field::qs (taking log[0]) You need an update of prime.hpp and prime.cpp (is_probable_prime is now public).
Change(7) (12th Jan 97) When looking for curves, for each L, the program now computes a vector indexed by b which is the order of the curve over GF(2^L) for each b (see field::small_order). This is then used to find K,B such that the order over GF(2^(L*K)) divided by the order over GF(2^L) is prime.
The pre-computation is O(2^(2*L)), so for L=16 just the pre-computation takes quite a while (2^32 operations), about an hour on my P75. Then the hard work really begins - I could do with faster primality testing software.
I have now computed ncdata.hpp for L up to 16 and K up to 100. I may have a go at L=18. In practice I think that GF(2^154) should satisfy most people, but it is fun to see how large one can go.
Change(8) (12th Jan 97) In field::field assertion code was not randomising a,b,c - not exactly a bug, but a bit silly. Also if L is invalid the tests should not be attempted.
Change(9) (12th Jan 97) I have seperated out the curve generation code into ncurve0.cpp. This need not be compiled if you use ncdata.hpp, as the test program does, but is required when linking ncgen. In this case prime.cpp is also not required, unless assertions are enabled in ncurve.cpp. I have also generally tidied up the class structure, put in proper access controls etc.
To summarise the link situation, the commands I use on my pentium are:
cl /Ox /G5 nctest.cpp ncurve.cpp vlong.cpp
and
cl /Ox /G5 ncgen.cpp ncurve.cpp ncurve0.cpp vlong.cpp prime.cpp
Change(10) (13th Jan 97) The restriction that L be even is lifted. This roughly doubles the choice of curves, which is nice. I have also re-instated non-trivial factors, although it is unusual for them to be useful. In the range L*K=50..400,L=8..14, with a trial division bound of 1000, there is only 1 instance viz. GF(2^230) (see ncdata.hpp). The non-trivial factor means that the prime order is only 213 bits, so one would probably prefer to use GF(2^221) which gives nearly as big a prime order (209 bits), and is faster.
Change (11) (Jan 14th 97) Added a wrapper class ec_crypt, and adjusted test program accordingly. Also I have now computed ncdata.hpp for L=8..16, L*K up to 2000. [ The trial division bound is 1000, and the bound for maximum non-trivial-factor is 0xffff ]. Made some further tidying-up changes.
Change (12) (Jan 14th 97) Normalised the curve parameters to make them small (root and so).
Change (13) (Jan 15th 97) In curve::unpack, the conversion from vlong was slow. Changed to using shift operations rather than general division. Also changed pack, and set_random to use shifts, although I don't think these were a problem.
Change (14) (Jan 16th 97) Added parameters to allow prime order and point to be supplied as parameters. There are also new member functions to access these values.
Change (15) (Jan 16th 97) Speeded up computation of nzt (element with non-zero trace). This is only needed when M is even. I made 2 changes - firstly I now use an element in the small field, since evaluating trace values there is much cheaper, and if the trace is non-zero in the small field, it is non-zero in the extension (quite easy to see, I think). Secondly I have found a method that finds an element with trace 1 in at most 2 attempts for L up to 16. First I try BASE/2 + BASE/4, where BASE=2^L. If that does not work, then I use BASE/8. I do not know if this works for general L, so beware! (It is quite easy to extend the algorithm to one that must work in general - just keep incrementing the value, where the *top* bit is regarded as the least significant. Since half the field elements have non-zero trace, we will find one sooner or later (hopefully sooner!) It seems that in the representation used, there are long runs of elements with trace 0 (with the usual bit ordering), so searching using conventional arithmetic can work badly.
Next day I checked, and the first counter-example is L=44. Since a table size of 2**44 would be excessive, the code I had would be ok in practice, but it leaves me slightly dissatisfied.
So what is going on? Eventually it dawned on me that in GF(2^m) if
a^2 + a = A and
b^2 + b = B then
(a+b)^2 + (a+b) = A+B
Thus trace(A+B) = trace(A)+trace(B), and we can always find a trace element with just 1 bit set in its binary representation. Also, treating the field elements as bit strings, if we compute a bit-string TM whose ith bit is the trace of the field element with just the ith bit set, then the trace of an arbitrary field element B is the parity of TM & B. This is a very fast operation (see the source for field::trace). TM can also be used to derive nzt, the arbitrary element with non-zero trace by just selecting any non-zero bit. Calculating TM is relatively slow (a few seconds) so TM should be cached (it is a constant associated with curve_parameter ).
I think it would also be possible to implement quad_solve as a matrix operation on the argument, but since the matrix would be quite bulky, (M poly's) and the speed of quad_solve is not that important, I don't think this is probably worthwhile.
Change (16) (Jan 18th) I realised that when multiplying by nzt in quad_solve, it is beneficial to make it the 1st parameter, since it is mostly zero.
Change (17) (Jan 18th) Reworked curve_parameter to incorporate extra parameters ( prime order, point and TM ). The way it works now is that if the extra parameters are not set up, they are calculated, so that subsequent constructor calls using the same curve parameter structure will be fast. Also moved calculation of small field reduction poly to ncurve0 (this simplifies small_field::small_field).
Change (18) (Jan 18th) Optimised field::inverse to remove copying due to the swap calls.
I am fairly happy with the code now, so I do not intend making any more changes for a while, unless any bugs come to light.
Send mail to George at
george.barwood@dial.pipex.com