DHExp

Files CCore/inc/crypton/DHExp.h CCore/src/crypton/DHExp.cpp

This tool is designed to perform the Diffie-Hellman key exchange protocol.

The abstract Diffie-Hellman protocol uses some finite group G with efficient octet representation. "Efficient" means that group operations can be performed efficiently from the octet representation of elements. Some group element g with large order is chosen also. Two peers A and B generate secret data x and y, which are long integer numbers. Then A sends g^x to B and B sends g^y to A. Each side can calculate g^xy. This is a common secret. It cannot be figured out from intercepted data, if the task of calculation x from g^x is difficult.

The simplest example of G is a multiplicative group of invertible elements of the ring Z/(p), where p is a large prime number. Two particular such numbers are well known as Diffie-Hellman Group I and Diffie-Hellman Group II primes. In both cases g is the class of 2.

template <class DHMod,class Algo=DefaultDHAlgo>
class DHExp : NoCopy 
 {
  public: 
 
   static const ulen GLen = DHMod::GLen ;

   DHExp();
   
   ~DHExp();
   
   void pow(const uint8 a[GLen],const uint8 x[GLen],uint8 ax[GLen]);
   
   void pow(const uint8 x[GLen],uint8 gx[GLen]);
 };

This class implements required functionality to use the Diffie-Hellman protocol. The first template parameter gives the group related data. The second is an Algorithm Package with required long integer algorithms.

GLen is the length of group element octet representation.

pow(a,x,ax) calculates the power of the element a in x and returns the result in ax.

pow(x,gx) calculates the power of the g in x and returns the result in gx.

In both methods x represents the unsigned number in the lendian byte order.

struct DHModI
 {
  static const ulen GLen = 96 ;
  
  static const uint8 G[GLen];
  
  static const uint8 Mod[GLen];
  
  static const uint8 InvMod[GLen];
  
  static const uint8 Lift[GLen];
 };

struct DHModII
 {
  static const ulen GLen = 128 ;
  
  static const uint8 G[GLen];
  
  static const uint8 Mod[GLen];
  
  static const uint8 InvMod[GLen];
  
  static const uint8 Lift[GLen];
 };

These two types can be used as the template parameter DHMod and contains all required precalculated data for Diffie-Hellman Groups I and II.

GLen is the length of the octet reprsentation of group elements. A group element is represented by the long unsigned number, using the lendian representation.

Mod is a prime module. This number is normalized, i.e. the most significant bit equals 1. D below is the power of 2, D = 2^8*GLen.

G is a generator.

InvMod is an inversion of Mod by module D, i.e. InvMod*Mod = 1 (mod D).

Lift is ((D-Mod)*D)/Mod.

struct Algo
 {
  using Unit = ??? ;
  
  static const unsigned UnitBits = ??? ;
  
  template <ulen Len>
  class MulOp : NoCopy
   {
    public:
    
     MulOp();
     
     ~MulOp();
     
     void mul(const Unit A[Len],const Unit B[Len],Unit C[2*Len]); // no overlapp
     
     void mulHi(const Unit A[Len],const Unit B[Len],Unit C[Len]); // no overlapp
     
     void mulLo(const Unit A[Len],const Unit B[Len],Unit C[Len]); // no overlapp
     
     void mulLo1(const Unit A[Len],const Unit B[Len],Unit C[Len+1]); // no overlapp
     
     void sq(const Unit A[Len],Unit B[2*Len]); // no overlapp
   };

  template <ulen Len>
  class AddOp : NoCopy
   {
    public:
   
     AddOp();
     
     ~AddOp();
     
     bool /* borrow */ sub(const Unit A[Len],const Unit B[Len],Unit C[Len]); // no overlapp
     
     bool /* carry */ add(const Unit A[Len],Unit B[Len]); // no overlap
     
     bool /* borrow */ neg(Unit A[Len]);
   };
 };

Here is the pattern for the template parameter Algo.

Unit is the unsigned integral type, used as the long integer unit. Long integers are represented using the lendian unit order.

UnitBits is the number of bits in the Unit.

Two inner classes MulOp and AddOp are used to perform the required long integer operations. They are parametrized by the long integer length Len.

MulOp operations are:

mul() multiplies A and B and returns the result of the double length in C. No overlap C with A or B is assumed.

mulHi() multiplies A and B and returns the high part of the result in C. No overlap C with A or B is assumed.

mulLo() multiplies A and B and returns the lower part of the result in C. No overlap C with A or B is assumed.

mulLo1() multiplies A and B and returns the lower part of the result of the length Len+1 in C. No overlap C with A or B is assumed.

sq() squares A and returns the result of the double length in B. No overlap B with A is assumed.

AddOp operations are:

sub() subtracts B from A and returns the result in C. Borrow is returned. No overlap C with A or B is assumed.

add() adds A to B and returns the carry. No overlap B with A is assumed.

neg() negates A. Borrow is returned.

struct DefaultDHAlgo
 {
  using Algo = Math::IntegerFastAlgo;
  
  using Unit = Algo::Unit ;
  
  static const unsigned UnitBits = Algo::UnitBits ;
  
  template <ulen Len>
  class MulOp : NoCopy
   {
     Unit temp[2*Len];
     
    public:
    
     MulOp();
     
     ~MulOp();
     
     void mul(const Unit A[Len],const Unit B[Len],Unit C[2*Len]);
     
     void mulHi(const Unit A[Len],const Unit B[Len],Unit C[Len]);
     
     void mulLo(const Unit A[Len],const Unit B[Len],Unit C[Len]);
     
     void mulLo1(const Unit A[Len],const Unit B[Len],Unit C[Len+1]);
     
     void sq(const Unit A[Len],Unit B[2*Len]);
   };

  template <ulen Len>
  class AddOp : NoCopy
   {
    public:
   
     AddOp();
     
     ~AddOp();
     
     bool /* borrow */ sub(const Unit A[Len],const Unit B[Len],Unit C[Len]);
     
     bool /* carry */ add(const Unit A[Len],Unit B[Len]);
     
     bool /* borrow */ neg(Unit A[Len]);
   };
 };

This is the default implementation of the Algo, based on the Math::IntegerFastAlgo package.