Crypto++  5.6.3
Free C++ class library of cryptographic schemes
rw.cpp
1 // rw.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 
5 #include "rw.h"
6 #include "asn.h"
7 #include "integer.h"
8 #include "nbtheory.h"
9 #include "modarith.h"
10 
11 #ifndef CRYPTOPP_IMPORTS
12 
13 NAMESPACE_BEGIN(CryptoPP)
14 
16 {
17  BERSequenceDecoder seq(bt);
18  m_n.BERDecode(seq);
19  seq.MessageEnd();
20 }
21 
22 void RWFunction::DEREncode(BufferedTransformation &bt) const
23 {
24  DERSequenceEncoder seq(bt);
25  m_n.DEREncode(seq);
26  seq.MessageEnd();
27 }
28 
30 {
32 
33  Integer out = in.Squared()%m_n;
34  const word r = 12;
35  // this code was written to handle both r = 6 and r = 12,
36  // but now only r = 12 is used in P1363
37  const word r2 = r/2;
38  const word r3a = (16 + 5 - r) % 16; // n%16 could be 5 or 13
39  const word r3b = (16 + 13 - r) % 16;
40  const word r4 = (8 + 5 - r/2) % 8; // n%8 == 5
41  switch (out % 16)
42  {
43  case r:
44  break;
45  case r2:
46  case r2+8:
47  out <<= 1;
48  break;
49  case r3a:
50  case r3b:
51  out.Negate();
52  out += m_n;
53  break;
54  case r4:
55  case r4+8:
56  out.Negate();
57  out += m_n;
58  out <<= 1;
59  break;
60  default:
61  out = Integer::Zero();
62  }
63  return out;
64 }
65 
66 bool RWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
67 {
68  CRYPTOPP_UNUSED(rng), CRYPTOPP_UNUSED(level);
69  bool pass = true;
70  pass = pass && m_n > Integer::One() && m_n%8 == 5;
71  return pass;
72 }
73 
74 bool RWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
75 {
76  return GetValueHelper(this, name, valueType, pValue).Assignable()
77  CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
78  ;
79 }
80 
82 {
83  AssignFromHelper(this, source)
84  CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
85  ;
86 }
87 
88 // *****************************************************************************
89 // private key operations:
90 
91 // generate a random private key
93 {
94  int modulusSize = 2048;
95  alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
96 
97  if (modulusSize < 16)
98  throw InvalidArgument("InvertibleRWFunction: specified modulus length is too small");
99 
100  AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize);
101  m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 3)("Mod", 8)));
102  m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 7)("Mod", 8)));
103 
104  m_n = m_p * m_q;
105  m_u = m_q.InverseMod(m_p);
106 }
107 
108 void InvertibleRWFunction::BERDecode(BufferedTransformation &bt)
109 {
110  BERSequenceDecoder seq(bt);
111  m_n.BERDecode(seq);
112  m_p.BERDecode(seq);
113  m_q.BERDecode(seq);
114  m_u.BERDecode(seq);
115  seq.MessageEnd();
116 }
117 
118 void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const
119 {
120  DERSequenceEncoder seq(bt);
121  m_n.DEREncode(seq);
122  m_p.DEREncode(seq);
123  m_q.DEREncode(seq);
124  m_u.DEREncode(seq);
125  seq.MessageEnd();
126 }
127 
128 Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
129 {
131  ModularArithmetic modn(m_n);
132  Integer r, rInv;
133  do {
134  // do this in a loop for people using small numbers for testing
135  r.Randomize(rng, Integer::One(), m_n - Integer::One());
136  // Fix for CVE-2015-2141. Thanks to Evgeny Sidorov for reporting.
137  // Squaring to satisfy Jacobi requirements suggested by Jean-Pierre M√ľnch.
138  r = modn.Square(r);
139  rInv = modn.MultiplicativeInverse(r);
140  } while (rInv.IsZero());
141  Integer re = modn.Square(r);
142  re = modn.Multiply(re, x); // blind
143 
144  Integer cp=re%m_p, cq=re%m_q;
145  if (Jacobi(cp, m_p) * Jacobi(cq, m_q) != 1)
146  {
147  cp = cp.IsOdd() ? (cp+m_p) >> 1 : cp >> 1;
148  cq = cq.IsOdd() ? (cq+m_q) >> 1 : cq >> 1;
149  }
150 
151  #pragma omp parallel
152  #pragma omp sections
153  {
154  #pragma omp section
155  cp = ModularSquareRoot(cp, m_p);
156  #pragma omp section
157  cq = ModularSquareRoot(cq, m_q);
158  }
159 
160  Integer y = CRT(cq, m_q, cp, m_p, m_u);
161  y = modn.Multiply(y, rInv); // unblind
162  y = STDMIN(y, m_n-y);
163  if (ApplyFunction(y) != x) // check
164  throw Exception(Exception::OTHER_ERROR, "InvertibleRWFunction: computational error during private key operation");
165  return y;
166 }
167 
168 bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
169 {
170  bool pass = RWFunction::Validate(rng, level);
171  pass = pass && m_p > Integer::One() && m_p%8 == 3 && m_p < m_n;
172  pass = pass && m_q > Integer::One() && m_q%8 == 7 && m_q < m_n;
173  pass = pass && m_u.IsPositive() && m_u < m_p;
174  if (level >= 1)
175  {
176  pass = pass && m_p * m_q == m_n;
177  pass = pass && m_u * m_q % m_p == 1;
178  }
179  if (level >= 2)
180  pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
181  return pass;
182 }
183 
184 bool InvertibleRWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
185 {
186  return GetValueHelper<RWFunction>(this, name, valueType, pValue).Assignable()
187  CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
188  CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
189  CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
190  ;
191 }
192 
194 {
195  AssignFromHelper<RWFunction>(this, source)
196  CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
197  CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
198  CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
199  ;
200 }
201 
202 NAMESPACE_END
203 
204 #endif
Base class for all exceptions thrown by the library.
Definition: cryptlib.h:139
const char * MultiplicativeInverseOfPrime2ModPrime1()
Integer.
Definition: argnames.h:46
An invalid argument was detected.
Definition: cryptlib.h:182
const char * Prime2()
Integer.
Definition: argnames.h:43
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: rw.cpp:184
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:333
Some other error occurred not belonging to other categories.
Definition: cryptlib.h:158
Ring of congruence classes modulo n.
Definition: modarith.h:27
Interface for random number generators.
Definition: cryptlib.h:1176
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: rw.cpp:66
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Definition: integer.cpp:3355
Combines two sets of NameValuePairs.
Definition: algparam.h:135
BER Sequence Decoder.
Definition: asn.h:197
Interface for buffered transformations.
Definition: cryptlib.h:1342
Integer MultiplicativeInverse() const
return inverse if 1 or -1, otherwise return 0
Definition: integer.cpp:4102
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:2944
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
Definition: rw.cpp:29
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:371
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: rw.cpp:92
const char * Prime1()
Integer.
Definition: argnames.h:42
Classes for Rabin-Williams signature schemes.
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:324
Integer Squared() const
Definition: integer.h:482
_
Definition: rw.h:18
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:554
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
Definition: nbtheory.cpp:249
void Negate()
Reverse the Sign of the Integer.
Definition: integer.cpp:4039
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: rw.cpp:81
Multiple precision integer with arithmetic operations.
Definition: integer.h:31
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: rw.cpp:168
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: rw.cpp:74
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:397
bool IsZero() const
Determines if the Integer is 0.
Definition: integer.h:312
Classes and functions for working with ANS.1 objects.
Classes and functions for number theoretic operations.
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3288
DER Sequence Encoder.
Definition: asn.h:207
An object that implements NameValuePairs.
Definition: algparam.h:489
const char * Modulus()
Integer.
Definition: argnames.h:32
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:4123
static const Integer & Zero()
Integer representing 0.
Definition: integer.cpp:2939
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: rw.cpp:193
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Definition: integer.cpp:3295
Class file for performing modular arithmetic.
Crypto++ library namespace.
Interface for retrieving values given their names.
Definition: cryptlib.h:277
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition: cryptlib.h:2126