Botan
1.11.15
|
00001 /* 00002 * Rabin-Williams 00003 * (C) 1999-2008 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/rw.h> 00010 #include <botan/keypair.h> 00011 #include <botan/parsing.h> 00012 #include <botan/reducer.h> 00013 #include <botan/blinding.h> 00014 #include <algorithm> 00015 #include <future> 00016 00017 namespace Botan { 00018 00019 /* 00020 * Create a Rabin-Williams private key 00021 */ 00022 RW_PrivateKey::RW_PrivateKey(RandomNumberGenerator& rng, 00023 size_t bits, size_t exp) 00024 { 00025 if(bits < 1024) 00026 throw Invalid_Argument(algo_name() + ": Can't make a key that is only " + 00027 std::to_string(bits) + " bits long"); 00028 if(exp < 2 || exp % 2 == 1) 00029 throw Invalid_Argument(algo_name() + ": Invalid encryption exponent"); 00030 00031 e = exp; 00032 00033 do 00034 { 00035 p = random_prime(rng, (bits + 1) / 2, e / 2, 3, 4); 00036 q = random_prime(rng, bits - p.bits(), e / 2, ((p % 8 == 3) ? 7 : 3), 8); 00037 n = p * q; 00038 } while(n.bits() != bits); 00039 00040 d = inverse_mod(e, lcm(p - 1, q - 1) >> 1); 00041 d1 = d % (p - 1); 00042 d2 = d % (q - 1); 00043 c = inverse_mod(q, p); 00044 00045 gen_check(rng); 00046 } 00047 00048 /* 00049 * Check Private Rabin-Williams Parameters 00050 */ 00051 bool RW_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const 00052 { 00053 if(!IF_Scheme_PrivateKey::check_key(rng, strong)) 00054 return false; 00055 00056 if(!strong) 00057 return true; 00058 00059 if((e * d) % (lcm(p - 1, q - 1) / 2) != 1) 00060 return false; 00061 00062 return KeyPair::signature_consistency_check(rng, *this, "EMSA2(SHA-1)"); 00063 } 00064 00065 namespace { 00066 00067 /** 00068 * Rabin-Williams Signature Operation 00069 */ 00070 class RW_Signature_Operation : public PK_Ops::Signature 00071 { 00072 public: 00073 typedef RW_PrivateKey Key_Type; 00074 00075 RW_Signature_Operation(const RW_PrivateKey& rw, 00076 const std::string&) : 00077 n(rw.get_n()), 00078 e(rw.get_e()), 00079 q(rw.get_q()), 00080 c(rw.get_c()), 00081 powermod_d1_p(rw.get_d1(), rw.get_p()), 00082 powermod_d2_q(rw.get_d2(), rw.get_q()), 00083 mod_p(rw.get_p()), 00084 blinder(n, 00085 [this](const BigInt& k) { return power_mod(k, e, n); }, 00086 [this](const BigInt& k) { return inverse_mod(k, n); }) 00087 { 00088 } 00089 00090 size_t max_input_bits() const { return (n.bits() - 1); } 00091 00092 secure_vector<byte> sign(const byte msg[], size_t msg_len, 00093 RandomNumberGenerator& rng); 00094 private: 00095 const BigInt& n; 00096 const BigInt& e; 00097 const BigInt& q; 00098 const BigInt& c; 00099 00100 Fixed_Exponent_Power_Mod powermod_d1_p, powermod_d2_q; 00101 Modular_Reducer mod_p; 00102 Blinder blinder; 00103 }; 00104 00105 secure_vector<byte> 00106 RW_Signature_Operation::sign(const byte msg[], size_t msg_len, 00107 RandomNumberGenerator&) 00108 { 00109 BigInt i(msg, msg_len); 00110 00111 if(i >= n || i % 16 != 12) 00112 throw Invalid_Argument("Rabin-Williams: invalid input"); 00113 00114 if(jacobi(i, n) != 1) 00115 i >>= 1; 00116 00117 i = blinder.blind(i); 00118 00119 auto future_j1 = std::async(std::launch::async, powermod_d1_p, i); 00120 const BigInt j2 = powermod_d2_q(i); 00121 BigInt j1 = future_j1.get(); 00122 00123 j1 = mod_p.reduce(sub_mul(j1, j2, c)); 00124 00125 const BigInt r = blinder.unblind(mul_add(j1, q, j2)); 00126 00127 return BigInt::encode_1363(std::min(r, n - r), n.bytes()); 00128 } 00129 00130 /** 00131 * Rabin-Williams Verification Operation 00132 */ 00133 class RW_Verification_Operation : public PK_Ops::Verification 00134 { 00135 public: 00136 typedef RW_PublicKey Key_Type; 00137 00138 RW_Verification_Operation(const RW_PublicKey& rw, const std::string&) : 00139 n(rw.get_n()), powermod_e_n(rw.get_e(), rw.get_n()) 00140 {} 00141 00142 size_t max_input_bits() const { return (n.bits() - 1); } 00143 bool with_recovery() const { return true; } 00144 00145 secure_vector<byte> verify_mr(const byte msg[], size_t msg_len); 00146 00147 private: 00148 const BigInt& n; 00149 Fixed_Exponent_Power_Mod powermod_e_n; 00150 }; 00151 00152 secure_vector<byte> 00153 RW_Verification_Operation::verify_mr(const byte msg[], size_t msg_len) 00154 { 00155 BigInt m(msg, msg_len); 00156 00157 if((m > (n >> 1)) || m.is_negative()) 00158 throw Invalid_Argument("RW signature verification: m > n / 2 || m < 0"); 00159 00160 BigInt r = powermod_e_n(m); 00161 if(r % 16 == 12) 00162 return BigInt::encode_locked(r); 00163 if(r % 8 == 6) 00164 return BigInt::encode_locked(2*r); 00165 00166 r = n - r; 00167 if(r % 16 == 12) 00168 return BigInt::encode_locked(r); 00169 if(r % 8 == 6) 00170 return BigInt::encode_locked(2*r); 00171 00172 throw Invalid_Argument("RW signature verification: Invalid signature"); 00173 } 00174 00175 BOTAN_REGISTER_PK_SIGNATURE_OP("RW", RW_Signature_Operation); 00176 BOTAN_REGISTER_PK_VERIFY_OP("RW", RW_Verification_Operation); 00177 00178 } 00179 00180 }