Add an implementation of GOST 34.10-2001 as described in

draft-dolmatov-cryptocom-gost34102001-06

Known problem: GOST's X.509 (and PKCS #8?) formats are different from
ECDSA. ECDSA uses compressed points, GOST uses a completely raw pair
of points (with, OF COURSE, no leading uncompressed pair identifier,
because using something that already exists would just be too much).

6 files changed, 461 insertions, 0 deletions

diff --git a/src/libstate/policy.cpp b/src/libstate/policy.cpp
index dfc1dfc7a..45c99e674 100644
--- a/src/libstate/policy.cpp
+++ b/src/libstate/policy.cpp
@@ -38,6 +38,7 @@ void set_default_oids(Library_State& config)
    add_oid(config, "1.3.6.1.4.1.25258.1.1", "RW");
    add_oid(config, "1.3.6.1.4.1.25258.1.2", "NR");
    add_oid(config, "1.2.840.10045.2.1", "ECDSA"); // X9.62
+   add_oid(config, "1.2.643.2.2.19", "GOST-34.10"); // RFC 4491
 
    /* Ciphers */
    add_oid(config, "1.3.14.3.2.7", "DES/CBC");
@@ -94,6 +95,8 @@ void set_default_oids(Library_State& config)
    add_oid(config, "1.2.840.10045.4.3.3", "ECDSA/EMSA1(SHA-384)");
    add_oid(config, "1.2.840.10045.4.3.4", "ECDSA/EMSA1(SHA-512)");
 
+   add_oid(config, "1.2.643.2.2.3", "GOST-34.10/EMSA1(GOST-R-34.11-94)");
+
    add_oid(config, "1.3.6.1.4.1.25258.2.1.1.1", "RW/EMSA2(RIPEMD-160)");
    add_oid(config, "1.3.6.1.4.1.25258.2.1.1.2", "RW/EMSA2(SHA-160)");
    add_oid(config, "1.3.6.1.4.1.25258.2.1.1.3", "RW/EMSA2(SHA-224)");
diff --git a/src/pubkey/ec_dompar/ec_dompar.cpp b/src/pubkey/ec_dompar/ec_dompar.cpp
index 0b5a6e681..a23e31cf1 100644
--- a/src/pubkey/ec_dompar/ec_dompar.cpp
+++ b/src/pubkey/ec_dompar/ec_dompar.cpp
@@ -409,6 +409,18 @@ std::vector<std::string> get_standard_domain_parameter(const std::string& oid)
       return dom_par;
       }
 
+   if(oid == "1.2.643.2.2.35.1") // GostR3410-2001-CryptoPro-A-ParamSet
+      {
+      std::vector<std::string> dom_par;
+      dom_par.push_back("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97");
+      dom_par.push_back("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94");
+      dom_par.push_back("166");
+      dom_par.push_back("0400000000000000000000000000000000000000000000000000000000000000018D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14");
+      dom_par.push_back("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893");
+      dom_par.push_back("1");
+      return dom_par;
+      }
+
    throw Invalid_Argument("No such ECC curve " + oid);
    }
 
diff --git a/src/pubkey/gost_3410/gost_3410.cpp b/src/pubkey/gost_3410/gost_3410.cpp
new file mode 100644
index 000000000..e4eb88307
--- /dev/null
+++ b/src/pubkey/gost_3410/gost_3410.cpp
@@ -0,0 +1,269 @@
+/*
+* GOST 34.10 implemenation
+* (C) 2007 Falko Strenzke, FlexSecure GmbH
+*          Manuel Hartl, FlexSecure GmbH
+* (C) 2008-2009 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#include <botan/gost_3410.h>
+#include <botan/numthry.h>
+#include <botan/der_enc.h>
+#include <botan/ber_dec.h>
+#include <botan/secmem.h>
+#include <botan/point_gfp.h>
+
+#include <iostream>
+
+namespace Botan {
+
+GOST_3410_PrivateKey::GOST_3410_PrivateKey(RandomNumberGenerator& rng,
+                                           const EC_Domain_Params& dom_pars)
+   {
+   mp_dom_pars = std::auto_ptr<EC_Domain_Params>(new EC_Domain_Params(dom_pars));
+   generate_private_key(rng);
+
+   try
+      {
+      mp_public_point->check_invariants();
+      }
+   catch(Illegal_Point& e)
+      {
+      throw Invalid_State("GOST_3410 key generation failed");
+      }
+   }
+
+GOST_3410_PrivateKey::GOST_3410_PrivateKey(const EC_Domain_Params& domain,
+                                           const BigInt& x)
+   {
+   mp_dom_pars = std::auto_ptr<EC_Domain_Params>(new EC_Domain_Params(domain));
+
+   m_private_value = x;
+   mp_public_point = std::auto_ptr<PointGFp>(new PointGFp (mp_dom_pars->get_base_point()));
+   mp_public_point->mult_this_secure(m_private_value,
+                                     mp_dom_pars->get_order(),
+                                     mp_dom_pars->get_order()-1);
+
+   try
+      {
+      mp_public_point->check_invariants();
+      }
+   catch(Illegal_Point)
+      {
+      throw Invalid_State("GOST_3410 key generation failed");
+      }
+   }
+
+/*
+* GOST_3410_PublicKey
+*/
+void GOST_3410_PublicKey::affirm_init() const // virtual
+   {
+   EC_PublicKey::affirm_init();
+   }
+
+void GOST_3410_PublicKey::set_domain_parameters(const EC_Domain_Params& dom_pars)
+   {
+   if(mp_dom_pars.get())
+      {
+      // they are already set, we must ensure that they are equal to the arg
+      if(dom_pars != *mp_dom_pars.get())
+         throw Invalid_Argument("EC_PublicKey::set_domain_parameters - cannot reset to a new value");
+
+      return;
+      }
+
+   if(m_enc_public_point.size() == 0)
+      throw Invalid_State("EC_PublicKey::set_domain_parameters(): encoded public point isn't set");
+
+   // now try to decode the public key ...
+   PointGFp tmp_pp(OS2ECP(m_enc_public_point, dom_pars.get_curve()));
+   try
+      {
+      tmp_pp.check_invariants();
+      }
+   catch(Illegal_Point e)
+      {
+      throw Invalid_State("EC_PublicKey::set_domain_parameters(): point does not lie on provided curve");
+      }
+
+   std::auto_ptr<EC_Domain_Params> p_tmp_pars(new EC_Domain_Params(dom_pars));
+   mp_public_point.reset(new PointGFp(tmp_pp));
+   mp_dom_pars = p_tmp_pars;
+   }
+
+void GOST_3410_PublicKey::set_all_values(const GOST_3410_PublicKey& other)
+   {
+   m_param_enc = other.m_param_enc;
+   m_enc_public_point = other.m_enc_public_point;
+   if(other.mp_dom_pars.get())
+      mp_dom_pars.reset(new EC_Domain_Params(other.domain_parameters()));
+
+   if(other.mp_public_point.get())
+      mp_public_point.reset(new PointGFp(other.public_point()));
+   }
+
+GOST_3410_PublicKey::GOST_3410_PublicKey(const GOST_3410_PublicKey& other)
+   : Public_Key(),
+     EC_PublicKey(),
+     PK_Verifying_wo_MR_Key()
+   {
+   set_all_values(other);
+   }
+
+const GOST_3410_PublicKey& GOST_3410_PublicKey::operator=(const GOST_3410_PublicKey& rhs)
+   {
+   set_all_values(rhs);
+   return *this;
+   }
+
+bool GOST_3410_PublicKey::verify(const byte msg[], u32bit msg_len,
+                                 const byte sig[], u32bit sig_len) const
+   {
+   affirm_init();
+
+   const BigInt& n = mp_dom_pars->get_order();
+
+   if(sig_len != n.bytes()*2)
+      return false;
+
+   // NOTE: it is not checked whether the public point is set
+   if(mp_dom_pars->get_curve().get_p() == 0)
+      throw Internal_Error("domain parameters not set");
+
+   BigInt e(msg, msg_len);
+
+   BigInt r(sig, sig_len / 2);
+   BigInt s(sig + sig_len / 2, sig_len / 2);
+
+   if(r < 0 || r >= n || s < 0 || s >= n)
+      return false;
+
+   e %= n;
+   if(e == 0)
+      e = 1;
+
+   BigInt v = inverse_mod(e, n);
+
+   BigInt z1 = (s*v) % n;
+   BigInt z2 = (-r*v) % n;
+
+   PointGFp R = (z1 * mp_dom_pars->get_base_point() + z2 * *mp_public_point);
+
+   return (R.get_affine_x().get_value() == r);
+   }
+
+GOST_3410_PublicKey::GOST_3410_PublicKey(const EC_Domain_Params& dom_par,
+                                 const PointGFp& public_point)
+   {
+   mp_dom_pars = std::auto_ptr<EC_Domain_Params>(new EC_Domain_Params(dom_par));
+   mp_public_point = std::auto_ptr<PointGFp>(new PointGFp(public_point));
+   m_param_enc = ENC_EXPLICIT;
+   }
+
+void GOST_3410_PublicKey::X509_load_hook()
+   {
+   EC_PublicKey::X509_load_hook();
+   EC_PublicKey::affirm_init();
+   }
+
+u32bit GOST_3410_PublicKey::max_input_bits() const
+   {
+   if(!mp_dom_pars.get())
+      {
+      throw Invalid_State("GOST_3410_PublicKey::max_input_bits(): domain parameters not set");
+      }
+   return mp_dom_pars->get_order().bits();
+   }
+
+/*************************
+* GOST_3410_PrivateKey
+*************************/
+void GOST_3410_PrivateKey::affirm_init() const // virtual
+   {
+   EC_PrivateKey::affirm_init();
+   }
+
+void GOST_3410_PrivateKey::PKCS8_load_hook(bool generated)
+   {
+   EC_PrivateKey::PKCS8_load_hook(generated);
+   EC_PrivateKey::affirm_init();
+   }
+
+void GOST_3410_PrivateKey::set_all_values(const GOST_3410_PrivateKey& other)
+   {
+   m_private_value = other.m_private_value;
+   m_param_enc = other.m_param_enc;
+   m_enc_public_point = other.m_enc_public_point;
+
+   if(other.mp_dom_pars.get())
+      mp_dom_pars.reset(new EC_Domain_Params(other.domain_parameters()));
+
+   if(other.mp_public_point.get())
+      mp_public_point.reset(new PointGFp(other.public_point()));
+   }
+
+GOST_3410_PrivateKey::GOST_3410_PrivateKey(GOST_3410_PrivateKey const& other)
+   : Public_Key(),
+     EC_PublicKey(),
+     Private_Key(),
+     GOST_3410_PublicKey(),
+     EC_PrivateKey(),
+     PK_Signing_Key()
+   {
+   set_all_values(other);
+   }
+
+const GOST_3410_PrivateKey& GOST_3410_PrivateKey::operator=(const GOST_3410_PrivateKey& rhs)
+   {
+   set_all_values(rhs);
+   return *this;
+   }
+
+SecureVector<byte>
+GOST_3410_PrivateKey::sign(const byte msg[],
+                           u32bit msg_len,
+                           RandomNumberGenerator& rng) const
+   {
+   affirm_init();
+
+   const BigInt& n = mp_dom_pars->get_order();
+
+   BigInt k;
+   do
+      k.randomize(rng, n.bits()-1);
+   while(k >= n);
+
+   if(m_private_value == 0)
+      throw Internal_Error("GOST_3410::sign(): no private key");
+
+   if(n == 0)
+      throw Internal_Error("GOST_3410::sign(): domain parameters not set");
+
+   BigInt e(msg, msg_len);
+
+   e %= n;
+   if(e == 0)
+      e = 1;
+
+   PointGFp k_times_P(mp_dom_pars->get_base_point());
+   k_times_P.mult_this_secure(k, n, n-1);
+   k_times_P.check_invariants();
+   BigInt r = k_times_P.get_affine_x().get_value() % n;
+
+   if(r == 0)
+      throw Internal_Error("GOST_3410::sign: r was zero");
+
+   BigInt s = (r*m_private_value + k*e) % n;
+
+   std::cout << "r = " << r << '\n';
+   std::cout << "s = " << s << '\n';
+
+   SecureVector<byte> output(2*n.bytes());
+   r.binary_encode(output + (output.size() / 2 - r.bytes()));
+   s.binary_encode(output + (output.size() - s.bytes()));
+   return output;
+   }
+
+}
diff --git a/src/pubkey/gost_3410/gost_3410.h b/src/pubkey/gost_3410/gost_3410.h
new file mode 100644
index 000000000..f053091ca
--- /dev/null
+++ b/src/pubkey/gost_3410/gost_3410.h
@@ -0,0 +1,151 @@
+/*
+* GOST_3410
+* (C) 2007 Falko Strenzke, FlexSecure GmbH
+*          Manuel Hartl, FlexSecure GmbH
+* (C) 2008-2009 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_GOST_3410_KEY_H__
+#define BOTAN_GOST_3410_KEY_H__
+
+#include <botan/ecc_key.h>
+
+namespace Botan {
+
+/**
+* This class represents GOST_3410 Public Keys.
+*/
+class BOTAN_DLL GOST_3410_PublicKey : public virtual EC_PublicKey,
+                                      public PK_Verifying_wo_MR_Key
+   {
+   public:
+
+      /**
+      * Get this keys algorithm name.
+      * @result this keys algorithm name
+      */
+      std::string algo_name() const { return "GOST-34.10"; }
+
+      /**
+      * Get the maximum number of bits allowed to be fed to this key.
+      * This is the bitlength of the order of the base point.
+
+      * @result the maximum number of input bits
+      */
+      u32bit max_input_bits() const;
+
+      u32bit message_parts() const { return 2; }
+
+      u32bit message_part_size() const
+         { return mp_dom_pars->get_order().bytes(); }
+
+      /**
+      * Verify a message with this key.
+      * @param message the byte array containing the message
+      * @param mess_len the number of bytes in the message byte array
+      * @param signature the byte array containing the signature
+      * @param sig_len the number of bytes in the signature byte array
+      */
+      bool verify(const byte message[], u32bit mess_len,
+                  const byte signature[], u32bit sig_len) const;
+
+      /**
+      * Default constructor. Use this one if you want to later fill
+      * this object with data from an encoded key.
+      */
+      GOST_3410_PublicKey() {}
+
+      /**
+      * Construct a public key from a given public point.
+      * @param dom_par the domain parameters associated with this key
+      * @param public_point the public point defining this key
+      */
+      GOST_3410_PublicKey(const EC_Domain_Params& dom_par,
+                          const PointGFp& public_point); // sets core
+
+      GOST_3410_PublicKey const& operator=(const GOST_3410_PublicKey& rhs);
+
+      GOST_3410_PublicKey(const GOST_3410_PublicKey& other);
+
+      /**
+      * Set the domain parameters of this key. This function has to be
+      * used when a key encoded without domain parameters was decoded into
+      * this key. Otherwise it will not be able to verify a signature.
+      * @param dom_pars the domain_parameters associated with this key
+      * @throw Invalid_Argument if the point was found not to be satisfying the
+      * curve equation of the provided domain parameters
+      * or if this key already has domain parameters set
+      * and these are differing from those given as the parameter
+      */
+      void set_domain_parameters(const EC_Domain_Params& dom_pars);
+
+      /**
+      * Ensure that the public point and domain parameters of this key are set.
+      * @throw Invalid_State if either of the two data members is not set
+      */
+      virtual void affirm_init() const;
+
+   protected:
+      void X509_load_hook();
+      void set_all_values(const GOST_3410_PublicKey& other);
+   };
+
+/**
+* This class represents GOST_3410 Private Keys
+*/
+class BOTAN_DLL GOST_3410_PrivateKey : public GOST_3410_PublicKey,
+                                   public EC_PrivateKey,
+                                   public PK_Signing_Key
+   {
+   public:
+      /**
+      * Default constructor. Use this one if you want to later fill
+      * this object with data from an encoded key.
+      */
+      GOST_3410_PrivateKey() {}
+
+      /**
+      * Generate a new private key
+      * @param the domain parameters to used for this key
+      */
+      GOST_3410_PrivateKey(RandomNumberGenerator& rng,
+                       const EC_Domain_Params& domain);
+
+      /**
+      * Load a private key
+      * @param domain parameters
+      * @param x the private key
+      */
+      GOST_3410_PrivateKey(const EC_Domain_Params& domain, const BigInt& x);
+
+      GOST_3410_PrivateKey(const GOST_3410_PrivateKey& other);
+      GOST_3410_PrivateKey const& operator=(const GOST_3410_PrivateKey& rhs);
+
+      /**
+      * Sign a message with this key.
+      * @param message the byte array representing the message to be signed
+      * @param mess_len the length of the message byte array
+      * @result the signature
+      */
+
+      SecureVector<byte> sign(const byte message[], u32bit mess_len,
+                              RandomNumberGenerator& rng) const;
+
+      /**
+      * Make sure that the public key parts of this object are set
+      * (calls EC_PublicKey::affirm_init()) as well as the private key
+      * value.
+      * @throw Invalid_State if the above conditions are not satisfied
+      */
+      virtual void affirm_init() const;
+
+   private:
+      void set_all_values(const GOST_3410_PrivateKey& other);
+      void PKCS8_load_hook(bool = false);
+   };
+
+}
+
+#endif
diff --git a/src/pubkey/gost_3410/info.txt b/src/pubkey/gost_3410/info.txt
new file mode 100644
index 000000000..1d6c1ed17
--- /dev/null
+++ b/src/pubkey/gost_3410/info.txt
@@ -0,0 +1,14 @@
+define GOST_34_10_2001
+
+load_on auto
+
+<requires>
+alloc
+asn1
+ec_dompar
+ecc_key
+gfpmath
+libstate
+numbertheory
+rng
+</requires>
diff --git a/src/pubkey/pk_algs.cpp b/src/pubkey/pk_algs.cpp
index 99d7294f0..ab922217a 100644
--- a/src/pubkey/pk_algs.cpp
+++ b/src/pubkey/pk_algs.cpp
@@ -23,6 +23,10 @@
   #include <botan/ecdsa.h>
 #endif
 
+#if defined(BOTAN_HAS_GOST_34_10_2001)
+  #include <botan/gost_3410.h>
+#endif
+
 #if defined(BOTAN_HAS_NYBERG_RUEPPEL)
   #include <botan/nr.h>
 #endif
@@ -70,6 +74,10 @@ Public_Key* get_public_key(const std::string& alg_name)
    if(alg_name == "ECDSA") return new ECDSA_PublicKey;
 #endif
 
+#if defined(BOTAN_HAS_GOST_34_10_2001)
+   if(alg_name == "GOST-34.10") return new GOST_3410_PublicKey;
+#endif
+
    return 0;
    }
 
@@ -106,6 +114,10 @@ Private_Key* get_private_key(const std::string& alg_name)
    if(alg_name == "ECDSA") return new ECDSA_PrivateKey;
 #endif
 
+#if defined(BOTAN_HAS_GOST_34_10_2001)
+   if(alg_name == "GOST-34.10") return new GOST_3410_PrivateKey;
+#endif
+
    return 0;
    }