Botan  1.11.15
src/lib/pubkey/rw/rw.cpp
Go to the documentation of this file.
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 }