Botan
1.11.15
|
00001 /* 00002 * DSA 00003 * (C) 1999-2010,2014 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/internal/pk_utils.h> 00009 #include <botan/dsa.h> 00010 #include <botan/keypair.h> 00011 #include <botan/pow_mod.h> 00012 #include <botan/reducer.h> 00013 #include <botan/rfc6979.h> 00014 #include <future> 00015 00016 namespace Botan { 00017 00018 /* 00019 * DSA_PublicKey Constructor 00020 */ 00021 DSA_PublicKey::DSA_PublicKey(const DL_Group& grp, const BigInt& y1) 00022 { 00023 group = grp; 00024 y = y1; 00025 } 00026 00027 /* 00028 * Create a DSA private key 00029 */ 00030 DSA_PrivateKey::DSA_PrivateKey(RandomNumberGenerator& rng, 00031 const DL_Group& grp, 00032 const BigInt& x_arg) 00033 { 00034 group = grp; 00035 x = x_arg; 00036 00037 if(x == 0) 00038 x = BigInt::random_integer(rng, 2, group_q() - 1); 00039 00040 y = power_mod(group_g(), x, group_p()); 00041 00042 if(x_arg == 0) 00043 gen_check(rng); 00044 else 00045 load_check(rng); 00046 } 00047 00048 DSA_PrivateKey::DSA_PrivateKey(const AlgorithmIdentifier& alg_id, 00049 const secure_vector<byte>& key_bits, 00050 RandomNumberGenerator& rng) : 00051 DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_57) 00052 { 00053 y = power_mod(group_g(), x, group_p()); 00054 00055 load_check(rng); 00056 } 00057 00058 /* 00059 * Check Private DSA Parameters 00060 */ 00061 bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const 00062 { 00063 if(!DL_Scheme_PrivateKey::check_key(rng, strong) || x >= group_q()) 00064 return false; 00065 00066 if(!strong) 00067 return true; 00068 00069 return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-1)"); 00070 } 00071 00072 namespace { 00073 00074 /** 00075 * Object that can create a DSA signature 00076 */ 00077 class DSA_Signature_Operation : public PK_Ops::Signature 00078 { 00079 public: 00080 typedef DSA_PrivateKey Key_Type; 00081 DSA_Signature_Operation(const DSA_PrivateKey& dsa, const std::string& emsa) : 00082 q(dsa.group_q()), 00083 x(dsa.get_x()), 00084 powermod_g_p(dsa.group_g(), dsa.group_p()), 00085 mod_q(dsa.group_q()), 00086 m_hash(hash_for_deterministic_signature(emsa)) 00087 { 00088 } 00089 00090 size_t message_parts() const override { return 2; } 00091 size_t message_part_size() const override { return q.bytes(); } 00092 size_t max_input_bits() const override { return q.bits(); } 00093 00094 secure_vector<byte> sign(const byte msg[], size_t msg_len, 00095 RandomNumberGenerator& rng) override; 00096 private: 00097 const BigInt& q; 00098 const BigInt& x; 00099 Fixed_Base_Power_Mod powermod_g_p; 00100 Modular_Reducer mod_q; 00101 std::string m_hash; 00102 }; 00103 00104 secure_vector<byte> 00105 DSA_Signature_Operation::sign(const byte msg[], size_t msg_len, 00106 RandomNumberGenerator&) 00107 { 00108 BigInt i(msg, msg_len); 00109 00110 while(i >= q) 00111 i -= q; 00112 00113 const BigInt k = generate_rfc6979_nonce(x, q, i, m_hash); 00114 00115 auto future_r = std::async(std::launch::async, 00116 [&]() { return mod_q.reduce(powermod_g_p(k)); }); 00117 00118 BigInt s = inverse_mod(k, q); 00119 const BigInt r = future_r.get(); 00120 s = mod_q.multiply(s, mul_add(x, r, i)); 00121 00122 // With overwhelming probability, a bug rather than actual zero r/s 00123 BOTAN_ASSERT(s != 0, "invalid s"); 00124 BOTAN_ASSERT(r != 0, "invalid r"); 00125 00126 secure_vector<byte> output(2*q.bytes()); 00127 r.binary_encode(&output[output.size() / 2 - r.bytes()]); 00128 s.binary_encode(&output[output.size() - s.bytes()]); 00129 return output; 00130 } 00131 00132 /** 00133 * Object that can verify a DSA signature 00134 */ 00135 class DSA_Verification_Operation : public PK_Ops::Verification 00136 { 00137 public: 00138 typedef DSA_PublicKey Key_Type; 00139 DSA_Verification_Operation(const DSA_PublicKey& dsa, 00140 const std::string&) : 00141 q(dsa.group_q()), y(dsa.get_y()) 00142 { 00143 powermod_g_p = Fixed_Base_Power_Mod(dsa.group_g(), dsa.group_p()); 00144 powermod_y_p = Fixed_Base_Power_Mod(y, dsa.group_p()); 00145 mod_p = Modular_Reducer(dsa.group_p()); 00146 mod_q = Modular_Reducer(dsa.group_q()); 00147 } 00148 00149 size_t message_parts() const { return 2; } 00150 size_t message_part_size() const { return q.bytes(); } 00151 size_t max_input_bits() const { return q.bits(); } 00152 00153 bool with_recovery() const override { return false; } 00154 00155 bool verify(const byte msg[], size_t msg_len, 00156 const byte sig[], size_t sig_len) override; 00157 private: 00158 const BigInt& q; 00159 const BigInt& y; 00160 00161 Fixed_Base_Power_Mod powermod_g_p, powermod_y_p; 00162 Modular_Reducer mod_p, mod_q; 00163 }; 00164 00165 bool DSA_Verification_Operation::verify(const byte msg[], size_t msg_len, 00166 const byte sig[], size_t sig_len) 00167 { 00168 if(sig_len != 2*q.bytes() || msg_len > q.bytes()) 00169 return false; 00170 00171 BigInt r(sig, q.bytes()); 00172 BigInt s(sig + q.bytes(), q.bytes()); 00173 BigInt i(msg, msg_len); 00174 00175 if(r <= 0 || r >= q || s <= 0 || s >= q) 00176 return false; 00177 00178 s = inverse_mod(s, q); 00179 00180 auto future_s_i = std::async(std::launch::async, 00181 [&]() { return powermod_g_p(mod_q.multiply(s, i)); }); 00182 00183 BigInt s_r = powermod_y_p(mod_q.multiply(s, r)); 00184 BigInt s_i = future_s_i.get(); 00185 00186 s = mod_p.multiply(s_i, s_r); 00187 00188 return (mod_q.reduce(s) == r); 00189 } 00190 00191 BOTAN_REGISTER_PK_SIGNATURE_OP("DSA", DSA_Signature_Operation); 00192 BOTAN_REGISTER_PK_VERIFY_OP("DSA", DSA_Verification_Operation); 00193 00194 } 00195 00196 }