Crypto++
rw.cpp
1 // rw.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 #include "rw.h"
5 #include "nbtheory.h"
6 #include "asn.h"
7 
8 #ifndef CRYPTOPP_IMPORTS
9 
10 NAMESPACE_BEGIN(CryptoPP)
11 
13 {
14  BERSequenceDecoder seq(bt);
15  m_n.BERDecode(seq);
16  seq.MessageEnd();
17 }
18 
19 void RWFunction::DEREncode(BufferedTransformation &bt) const
20 {
21  DERSequenceEncoder seq(bt);
22  m_n.DEREncode(seq);
23  seq.MessageEnd();
24 }
25 
26 Integer RWFunction::ApplyFunction(const Integer &in) const
27 {
28  DoQuickSanityCheck();
29 
30  Integer out = in.Squared()%m_n;
31  const word r = 12;
32  // this code was written to handle both r = 6 and r = 12,
33  // but now only r = 12 is used in P1363
34  const word r2 = r/2;
35  const word r3a = (16 + 5 - r) % 16; // n%16 could be 5 or 13
36  const word r3b = (16 + 13 - r) % 16;
37  const word r4 = (8 + 5 - r/2) % 8; // n%8 == 5
38  switch (out % 16)
39  {
40  case r:
41  break;
42  case r2:
43  case r2+8:
44  out <<= 1;
45  break;
46  case r3a:
47  case r3b:
48  out.Negate();
49  out += m_n;
50  break;
51  case r4:
52  case r4+8:
53  out.Negate();
54  out += m_n;
55  out <<= 1;
56  break;
57  default:
58  out = Integer::Zero();
59  }
60  return out;
61 }
62 
63 bool RWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
64 {
65  bool pass = true;
66  pass = pass && m_n > Integer::One() && m_n%8 == 5;
67  return pass;
68 }
69 
70 bool RWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
71 {
72  return GetValueHelper(this, name, valueType, pValue).Assignable()
73  CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
74  ;
75 }
76 
78 {
79  AssignFromHelper(this, source)
80  CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
81  ;
82 }
83 
84 // *****************************************************************************
85 // private key operations:
86 
87 // generate a random private key
89 {
90  int modulusSize = 2048;
91  alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
92 
93  if (modulusSize < 16)
94  throw InvalidArgument("InvertibleRWFunction: specified modulus length is too small");
95 
96  AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize);
97  m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 3)("Mod", 8)));
98  m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 7)("Mod", 8)));
99 
100  m_n = m_p * m_q;
101  m_u = m_q.InverseMod(m_p);
102 }
103 
104 void InvertibleRWFunction::BERDecode(BufferedTransformation &bt)
105 {
106  BERSequenceDecoder seq(bt);
107  m_n.BERDecode(seq);
108  m_p.BERDecode(seq);
109  m_q.BERDecode(seq);
110  m_u.BERDecode(seq);
111  seq.MessageEnd();
112 }
113 
114 void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const
115 {
116  DERSequenceEncoder seq(bt);
117  m_n.DEREncode(seq);
118  m_p.DEREncode(seq);
119  m_q.DEREncode(seq);
120  m_u.DEREncode(seq);
121  seq.MessageEnd();
122 }
123 
124 Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
125 {
126  DoQuickSanityCheck();
127  ModularArithmetic modn(m_n);
128  Integer r, rInv;
129 
130  // do this in a loop for people using small numbers for testing
131  do {
132  r.Randomize(rng, Integer::One(), m_n - Integer::One());
133  // Fix for CVE-2015-2141. Thanks to Evgeny Sidorov for reporting.
134  // Squaring to satisfy Jacobi requirements suggested by JPM.
135  r = modn.Square(r);
136  rInv = modn.MultiplicativeInverse(r);
137  } while (rInv.IsZero());
138 
139  Integer re = modn.Square(r);
140  re = modn.Multiply(re, x); // blind
141 
142  Integer cp=re%m_p, cq=re%m_q;
143  if (Jacobi(cp, m_p) * Jacobi(cq, m_q) != 1)
144  {
145  cp = cp.IsOdd() ? (cp+m_p) >> 1 : cp >> 1;
146  cq = cq.IsOdd() ? (cq+m_q) >> 1 : cq >> 1;
147  }
148 
149  #pragma omp parallel
150  #pragma omp sections
151  {
152  #pragma omp section
153  cp = ModularSquareRoot(cp, m_p);
154  #pragma omp section
155  cq = ModularSquareRoot(cq, m_q);
156  }
157 
158  Integer y = CRT(cq, m_q, cp, m_p, m_u);
159  y = modn.Multiply(y, rInv); // unblind
160  y = STDMIN(y, m_n-y);
161  if (ApplyFunction(y) != x) // check
162  throw Exception(Exception::OTHER_ERROR, "InvertibleRWFunction: computational error during private key operation");
163  return y;
164 }
165 
166 bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
167 {
168  bool pass = RWFunction::Validate(rng, level);
169  pass = pass && m_p > Integer::One() && m_p%8 == 3 && m_p < m_n;
170  pass = pass && m_q > Integer::One() && m_q%8 == 7 && m_q < m_n;
171  pass = pass && m_u.IsPositive() && m_u < m_p;
172  if (level >= 1)
173  {
174  pass = pass && m_p * m_q == m_n;
175  pass = pass && m_u * m_q % m_p == 1;
176  }
177  if (level >= 2)
178  pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
179  return pass;
180 }
181 
182 bool InvertibleRWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
183 {
184  return GetValueHelper<RWFunction>(this, name, valueType, pValue).Assignable()
185  CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
186  CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
187  CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
188  ;
189 }
190 
192 {
193  AssignFromHelper<RWFunction>(this, source)
194  CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
195  CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
196  CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
197  ;
198 }
199 
200 NAMESPACE_END
201 
202 #endif
base class for all exceptions thrown by Crypto++
Definition: cryptlib.h:110
exception thrown when an invalid argument is detected
Definition: cryptlib.h:145
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
to be implemented by derived classes, users should use one of the above functions instead ...
Definition: rw.cpp:182
some error not belong to any of the above categories
Definition: cryptlib.h:128
ring of congruence classes modulo n
Definition: modarith.h:19
interface for random number generators
Definition: cryptlib.h:669
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
check this object for errors
Definition: rw.cpp:63
BER Sequence Decoder.
Definition: asn.h:177
interface for buffered transformations
Definition: cryptlib.h:771
Integer MultiplicativeInverse() const
return inverse if 1 or -1, otherwise return 0
Definition: integer.cpp:3937
static const Integer & One()
avoid calling constructors for these frequently used integers
Definition: integer.cpp:2867
bool GetIntValue(const char *name, int &value) const
get a named value with type int
Definition: cryptlib.h:282
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: rw.cpp:88
This file contains classes that implement the Rabin-Williams signature schemes as defined in IEEE P13...
_
Definition: rw.h:14
void AssignFrom(const NameValuePairs &source)
assign values from source to this object
Definition: rw.cpp:77
multiple precision integer and basic arithmetics
Definition: integer.h:26
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
check this object for errors
Definition: rw.cpp:166
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
to be implemented by derived classes, users should use one of the above functions instead ...
Definition: rw.cpp:70
void DEREncode(BufferedTransformation &bt) const
encode using Distinguished Encoding Rules, put result into a BufferedTransformation object ...
Definition: integer.cpp:3133
DER Sequence Encoder.
Definition: asn.h:187
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:3958
static const Integer & Zero()
avoid calling constructors for these frequently used integers
Definition: integer.cpp:2862
void AssignFrom(const NameValuePairs &source)
assign values from source to this object
Definition: rw.cpp:191
interface for retrieving values given their names
Definition: cryptlib.h:225