Botan  1.10.9
rw.cpp
Go to the documentation of this file.
1 /*
2 * Rabin-Williams
3 * (C) 1999-2008 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/rw.h>
9 #include <botan/numthry.h>
10 #include <botan/keypair.h>
11 #include <botan/parsing.h>
12 #include <algorithm>
13 
14 namespace Botan {
15 
16 /*
17 * Create a Rabin-Williams private key
18 */
20  size_t bits, size_t exp)
21  {
22  if(bits < 512)
23  throw Invalid_Argument(algo_name() + ": Can't make a key that is only " +
24  to_string(bits) + " bits long");
25  if(exp < 2 || exp % 2 == 1)
26  throw Invalid_Argument(algo_name() + ": Invalid encryption exponent");
27 
28  e = exp;
29 
30  do
31  {
32  p = random_prime(rng, (bits + 1) / 2, e / 2, 3, 4);
33  q = random_prime(rng, bits - p.bits(), e / 2, ((p % 8 == 3) ? 7 : 3), 8);
34  n = p * q;
35  } while(n.bits() != bits);
36 
37  d = inverse_mod(e, lcm(p - 1, q - 1) >> 1);
38  d1 = d % (p - 1);
39  d2 = d % (q - 1);
40  c = inverse_mod(q, p);
41 
42  gen_check(rng);
43  }
44 
45 /*
46 * Check Private Rabin-Williams Parameters
47 */
49  {
50  if(!IF_Scheme_PrivateKey::check_key(rng, strong))
51  return false;
52 
53  if(!strong)
54  return true;
55 
56  if((e * d) % (lcm(p - 1, q - 1) / 2) != 1)
57  return false;
58 
59  return KeyPair::signature_consistency_check(rng, *this, "EMSA2(SHA-1)");
60  }
61 
63  n(rw.get_n()),
64  e(rw.get_e()),
65  q(rw.get_q()),
66  c(rw.get_c()),
67  powermod_d1_p(rw.get_d1(), rw.get_p()),
68  powermod_d2_q(rw.get_d2(), rw.get_q()),
69  mod_p(rw.get_p())
70  {
71  }
72 
74 RW_Signature_Operation::sign(const byte msg[], size_t msg_len,
76  {
77  if(!blinder.initialized())
78  {
79  BigInt k(rng, n.bits() / 2);
80  blinder = Blinder(power_mod(k, e, n), inverse_mod(k, n), n);
81  }
82 
83  BigInt i(msg, msg_len);
84 
85  if(i >= n || i % 16 != 12)
86  throw Invalid_Argument("Rabin-Williams: invalid input");
87 
88  if(jacobi(i, n) != 1)
89  i >>= 1;
90 
91  i = blinder.blind(i);
92 
93  BigInt j1 = powermod_d1_p(i);
94  BigInt j2 = powermod_d2_q(i);
95  j1 = mod_p.reduce(sub_mul(j1, j2, c));
96 
97  BigInt r = blinder.unblind(mul_add(j1, q, j2));
98 
99  r = std::min(r, n - r);
100 
101  return BigInt::encode_1363(r, n.bytes());
102  }
103 
105 RW_Verification_Operation::verify_mr(const byte msg[], size_t msg_len)
106  {
107  BigInt m(msg, msg_len);
108 
109  if((m > (n >> 1)) || m.is_negative())
110  throw Invalid_Argument("RW signature verification: m > n / 2 || m < 0");
111 
112  BigInt r = powermod_e_n(m);
113  if(r % 16 == 12)
114  return BigInt::encode(r);
115  if(r % 8 == 6)
116  return BigInt::encode(2*r);
117 
118  r = n - r;
119  if(r % 16 == 12)
120  return BigInt::encode(r);
121  if(r % 8 == 6)
122  return BigInt::encode(2*r);
123 
124  throw Invalid_Argument("RW signature verification: Invalid signature");
125  }
126 
127 }
bool check_key(RandomNumberGenerator &rng, bool) const
Definition: rw.cpp:48
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &key, const std::string &padding)
Definition: keypair.cpp:47
BigInt n
Definition: numthry.cpp:26
RW_Signature_Operation(const RW_PrivateKey &rw)
Definition: rw.cpp:62
SecureVector< byte > sign(const byte msg[], size_t msg_len, RandomNumberGenerator &rng)
Definition: rw.cpp:74
bool is_negative() const
Definition: bigint.h:245
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
static SecureVector< byte > encode(const BigInt &n, Base base=Binary)
Definition: big_code.cpp:64
SecureVector< byte > verify_mr(const byte msg[], size_t msg_len)
Definition: rw.cpp:105
RW_PrivateKey(const AlgorithmIdentifier &alg_id, const MemoryRegion< byte > &key_bits, RandomNumberGenerator &rng)
Definition: rw.h:46
unsigned char byte
Definition: types.h:22
bool initialized() const
Definition: blinding.h:25
size_t bits() const
Definition: bigint.cpp:253
RandomNumberGenerator * rng
Definition: global_rng.cpp:165
GMP_MPZ exp
Definition: gmp_powm.cpp:29
BigInt unblind(const BigInt &x) const
Definition: blinding.cpp:42
s32bit jacobi(const BigInt &a, const BigInt &n)
Definition: jacobi.cpp:15
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:32
bool check_key(RandomNumberGenerator &rng, bool) const
Definition: if_algo.cpp:121
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:202
std::string algo_name() const
Definition: rw.h:24
BigInt blind(const BigInt &x) const
Definition: blinding.cpp:29
BigInt sub_mul(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:60
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:251
BigInt r
Definition: numthry.cpp:26
std::string to_string(u64bit n, size_t min_len)
Definition: parsing.cpp:42
void gen_check(RandomNumberGenerator &rng) const
Definition: pk_keys.cpp:49
static SecureVector< byte > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:78
BigInt lcm(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:194
BigInt mul_add(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:33
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17
size_t bytes() const
Definition: bigint.cpp:245