Botan  2.4.0
Crypto and TLS for C++11
gost_3410.cpp
Go to the documentation of this file.
1 /*
2 * GOST 34.10-2001 implemenation
3 * (C) 2007 Falko Strenzke, FlexSecure GmbH
4 * Manuel Hartl, FlexSecure GmbH
5 * (C) 2008-2010,2015 Jack Lloyd
6 *
7 * Botan is released under the Simplified BSD License (see license.txt)
8 */
9 
10 #include <botan/gost_3410.h>
11 #include <botan/internal/pk_ops_impl.h>
12 #include <botan/reducer.h>
13 #include <botan/der_enc.h>
14 #include <botan/ber_dec.h>
15 
16 namespace Botan {
17 
18 std::vector<uint8_t> GOST_3410_PublicKey::public_key_bits() const
19  {
20  const BigInt x = public_point().get_affine_x();
21  const BigInt y = public_point().get_affine_y();
22 
23  size_t part_size = std::max(x.bytes(), y.bytes());
24 
25  std::vector<uint8_t> bits(2*part_size);
26 
27  x.binary_encode(&bits[part_size - x.bytes()]);
28  y.binary_encode(&bits[2*part_size - y.bytes()]);
29 
30  // Keys are stored in little endian format (WTF)
31  for(size_t i = 0; i != part_size / 2; ++i)
32  {
33  std::swap(bits[i], bits[part_size-1-i]);
34  std::swap(bits[part_size+i], bits[2*part_size-1-i]);
35  }
36 
38  }
39 
41  {
42  std::vector<uint8_t> params =
44  .encode(OID(domain().get_oid()))
45  .end_cons()
47 
48  return AlgorithmIdentifier(get_oid(), params);
49  }
50 
52  const std::vector<uint8_t>& key_bits)
53  {
54  OID ecc_param_id;
55 
56  // The parameters also includes hash and cipher OIDs
57  BER_Decoder(alg_id.get_parameters()).start_cons(SEQUENCE).decode(ecc_param_id);
58 
59  m_domain_params = EC_Group(ecc_param_id);
60 
62  BER_Decoder(key_bits).decode(bits, OCTET_STRING);
63 
64  const size_t part_size = bits.size() / 2;
65 
66  // Keys are stored in little endian format (WTF)
67  for(size_t i = 0; i != part_size / 2; ++i)
68  {
69  std::swap(bits[i], bits[part_size-1-i]);
70  std::swap(bits[part_size+i], bits[2*part_size-1-i]);
71  }
72 
73  BigInt x(bits.data(), part_size);
74  BigInt y(&bits[part_size], part_size);
75 
76  m_public_key = PointGFp(domain().get_curve(), x, y);
77 
79  "Loaded GOST 34.10 public key is on the curve");
80  }
81 
82 namespace {
83 
84 BigInt decode_le(const uint8_t msg[], size_t msg_len)
85  {
86  secure_vector<uint8_t> msg_le(msg, msg + msg_len);
87 
88  for(size_t i = 0; i != msg_le.size() / 2; ++i)
89  std::swap(msg_le[i], msg_le[msg_le.size()-1-i]);
90 
91  return BigInt(msg_le.data(), msg_le.size());
92  }
93 
94 /**
95 * GOST-34.10 signature operation
96 */
97 class GOST_3410_Signature_Operation final : public PK_Ops::Signature_with_EMSA
98  {
99  public:
100  GOST_3410_Signature_Operation(const GOST_3410_PrivateKey& gost_3410,
101  const std::string& emsa) :
103  m_order(gost_3410.domain().get_order()),
104  m_mod_order(m_order),
105  m_base_point(gost_3410.domain().get_base_point(), m_order),
106  m_x(gost_3410.private_value()) {}
107 
108  size_t max_input_bits() const override { return m_order.bits(); }
109 
110  secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
111  RandomNumberGenerator& rng) override;
112 
113  private:
114  const BigInt& m_order;
115  Modular_Reducer m_mod_order;
116  Blinded_Point_Multiply m_base_point;
117  const BigInt& m_x;
118  };
119 
121 GOST_3410_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
123  {
124  BigInt k;
125  do
126  k.randomize(rng, m_order.bits()-1);
127  while(k >= m_order);
128 
129  BigInt e = decode_le(msg, msg_len);
130 
131  e = m_mod_order.reduce(e);
132  if(e == 0)
133  e = 1;
134 
135  const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
136  BOTAN_ASSERT(k_times_P.on_the_curve(), "GOST 34.10 k*g is on the curve");
137 
138  const BigInt r = m_mod_order.reduce(k_times_P.get_affine_x());
139  const BigInt s = m_mod_order.reduce(r*m_x + k*e);
140 
141  if(r == 0 || s == 0)
142  throw Invalid_State("GOST 34.10: r == 0 || s == 0");
143 
144  secure_vector<uint8_t> output(2*m_order.bytes());
145  s.binary_encode(&output[output.size() / 2 - s.bytes()]);
146  r.binary_encode(&output[output.size() - r.bytes()]);
147  return output;
148  }
149 
150 /**
151 * GOST-34.10 verification operation
152 */
153 class GOST_3410_Verification_Operation final : public PK_Ops::Verification_with_EMSA
154  {
155  public:
156 
157  GOST_3410_Verification_Operation(const GOST_3410_PublicKey& gost,
158  const std::string& emsa) :
160  m_base_point(gost.domain().get_base_point()),
161  m_public_point(gost.public_point()),
162  m_order(gost.domain().get_order()) {}
163 
164  size_t max_input_bits() const override { return m_order.bits(); }
165 
166  bool with_recovery() const override { return false; }
167 
168  bool verify(const uint8_t msg[], size_t msg_len,
169  const uint8_t sig[], size_t sig_len) override;
170  private:
171  const PointGFp& m_base_point;
172  const PointGFp& m_public_point;
173  const BigInt& m_order;
174  };
175 
176 bool GOST_3410_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
177  const uint8_t sig[], size_t sig_len)
178  {
179  if(sig_len != m_order.bytes()*2)
180  return false;
181 
182  BigInt e = decode_le(msg, msg_len);
183 
184  BigInt s(sig, sig_len / 2);
185  BigInt r(sig + sig_len / 2, sig_len / 2);
186 
187  if(r <= 0 || r >= m_order || s <= 0 || s >= m_order)
188  return false;
189 
190  e %= m_order;
191  if(e == 0)
192  e = 1;
193 
194  BigInt v = inverse_mod(e, m_order);
195 
196  BigInt z1 = (s*v) % m_order;
197  BigInt z2 = (-r*v) % m_order;
198 
199  PointGFp R = multi_exponentiate(m_base_point, z1,
200  m_public_point, z2);
201 
202  if(R.is_zero())
203  return false;
204 
205  return (R.get_affine_x() == r);
206  }
207 
208 }
209 
210 std::unique_ptr<PK_Ops::Verification>
212  const std::string& provider) const
213  {
214  if(provider == "base" || provider.empty())
215  return std::unique_ptr<PK_Ops::Verification>(new GOST_3410_Verification_Operation(*this, params));
216  throw Provider_Not_Found(algo_name(), provider);
217  }
218 
219 std::unique_ptr<PK_Ops::Signature>
221  const std::string& params,
222  const std::string& provider) const
223  {
224  if(provider == "base" || provider.empty())
225  return std::unique_ptr<PK_Ops::Signature>(new GOST_3410_Signature_Operation(*this, params));
226  throw Provider_Not_Found(algo_name(), provider);
227  }
228 
229 }
const BigInt & private_value() const
Definition: ecc_key.cpp:112
const PointGFp & get_base_point() const
Definition: ec_group.h:96
std::vector< uint8_t > get_contents_unlocked()
Definition: der_enc.h:27
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
const PointGFp & public_point() const
Definition: ecc_key.h:57
PointGFp m_public_key
Definition: ecc_key.h:102
BER_Decoder & decode(bool &v)
Definition: ber_dec.cpp:355
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:269
DER_Encoder & end_cons()
Definition: der_enc.cpp:146
BigInt get_affine_x() const
Definition: point_gfp.cpp:389
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: gost_3410.cpp:220
BigInt get_affine_y() const
Definition: point_gfp.cpp:401
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:29
std::vector< uint8_t > public_key_bits() const override
Definition: gost_3410.cpp:18
DER_Encoder & encode(bool b)
Definition: der_enc.cpp:202
virtual OID get_oid() const
Definition: pk_keys.cpp:51
const EC_Group & domain() const
Definition: ecc_key.h:72
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:277
Definition: alg_id.cpp:13
size_t bytes() const
Definition: bigint.cpp:175
const BigInt & get_order() const
Definition: ec_group.h:102
const std::vector< uint8_t > & get_parameters() const
Definition: alg_id.h:38
bool on_the_curve() const
Definition: point_gfp.cpp:413
std::string algo_name() const override
Definition: gost_3410.h:45
AlgorithmIdentifier algorithm_identifier() const override
Definition: gost_3410.cpp:40
DER_Encoder & start_cons(ASN1_Tag type_tag, ASN1_Tag class_tag=UNIVERSAL)
Definition: der_enc.cpp:136
bool is_zero() const
Definition: point_gfp.h:179
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string &params, const std::string &provider) const override
Definition: gost_3410.cpp:211
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
EC_Group m_domain_params
Definition: ecc_key.h:101
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_gfp.cpp:247