Crypto++  5.6.5 Free C++ class library of cryptographic schemes
rabin.cpp
1 // rabin.cpp - written and placed in the public domain by Wei Dai
2
3 #include "pch.h"
4 #include "rabin.h"
5 #include "integer.h"
6 #include "nbtheory.h"
7 #include "modarith.h"
8 #include "asn.h"
9 #include "sha.h"
10
11 NAMESPACE_BEGIN(CryptoPP)
12
13 void RabinFunction::BERDecode(BufferedTransformation &bt)
14 {
15  BERSequenceDecoder seq(bt);
16  m_n.BERDecode(seq);
17  m_r.BERDecode(seq);
18  m_s.BERDecode(seq);
19  seq.MessageEnd();
20 }
21
22 void RabinFunction::DEREncode(BufferedTransformation &bt) const
23 {
24  DERSequenceEncoder seq(bt);
25  m_n.DEREncode(seq);
26  m_r.DEREncode(seq);
27  m_s.DEREncode(seq);
28  seq.MessageEnd();
29 }
30
32 {
34
35  Integer out = in.Squared()%m_n;
36  if (in.IsOdd())
37  out = out*m_r%m_n;
38  if (Jacobi(in, m_n)==-1)
39  out = out*m_s%m_n;
40  return out;
41 }
42
43 bool RabinFunction::Validate(RandomNumberGenerator& /*rng*/, unsigned int level) const
44 {
45  bool pass = true;
46  pass = pass && m_n > Integer::One() && m_n%4 == 1;
47  pass = pass && m_r > Integer::One() && m_r < m_n;
48  pass = pass && m_s > Integer::One() && m_s < m_n;
49  if (level >= 1)
50  pass = pass && Jacobi(m_r, m_n) == -1 && Jacobi(m_s, m_n) == -1;
51  return pass;
52 }
53
54 bool RabinFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
55 {
56  return GetValueHelper(this, name, valueType, pValue).Assignable()
57  CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
58  CRYPTOPP_GET_FUNCTION_ENTRY(QuadraticResidueModPrime1)
59  CRYPTOPP_GET_FUNCTION_ENTRY(QuadraticResidueModPrime2)
60  ;
61 }
62
64 {
65  AssignFromHelper(this, source)
66  CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
67  CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime1)
68  CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime2)
69  ;
70 }
71
72 // *****************************************************************************
73 // private key operations:
74
75 // generate a random private key
77 {
78  int modulusSize = 2048;
79  alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
80
81  if (modulusSize < 16)
82  throw InvalidArgument("InvertibleRabinFunction: specified modulus size is too small");
83
84  // VC70 workaround: putting these after primeParam causes overlapped stack allocation
85  bool rFound=false, sFound=false;
86  Integer t=2;
87
88  AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
89  ("EquivalentTo", 3)("Mod", 4);
90  m_p.GenerateRandom(rng, primeParam);
91  m_q.GenerateRandom(rng, primeParam);
92
93  while (!(rFound && sFound))
94  {
95  int jp = Jacobi(t, m_p);
96  int jq = Jacobi(t, m_q);
97
98  if (!rFound && jp==1 && jq==-1)
99  {
100  m_r = t;
101  rFound = true;
102  }
103
104  if (!sFound && jp==-1 && jq==1)
105  {
106  m_s = t;
107  sFound = true;
108  }
109
110  ++t;
111  }
112
113  m_n = m_p * m_q;
114  m_u = m_q.InverseMod(m_p);
115 }
116
117 void InvertibleRabinFunction::BERDecode(BufferedTransformation &bt)
118 {
119  BERSequenceDecoder seq(bt);
120  m_n.BERDecode(seq);
121  m_r.BERDecode(seq);
122  m_s.BERDecode(seq);
123  m_p.BERDecode(seq);
124  m_q.BERDecode(seq);
125  m_u.BERDecode(seq);
126  seq.MessageEnd();
127 }
128
129 void InvertibleRabinFunction::DEREncode(BufferedTransformation &bt) const
130 {
131  DERSequenceEncoder seq(bt);
132  m_n.DEREncode(seq);
133  m_r.DEREncode(seq);
134  m_s.DEREncode(seq);
135  m_p.DEREncode(seq);
136  m_q.DEREncode(seq);
137  m_u.DEREncode(seq);
138  seq.MessageEnd();
139 }
140
142 {
144
145  ModularArithmetic modn(m_n);
146  Integer r(rng, Integer::One(), m_n - Integer::One());
147  r = modn.Square(r);
148  Integer r2 = modn.Square(r);
149  Integer c = modn.Multiply(in, r2); // blind
150
151  Integer cp=c%m_p, cq=c%m_q;
152
153  int jp = Jacobi(cp, m_p);
154  int jq = Jacobi(cq, m_q);
155
156  if (jq==-1)
157  {
158  cp = cp*EuclideanMultiplicativeInverse(m_r, m_p)%m_p;
159  cq = cq*EuclideanMultiplicativeInverse(m_r, m_q)%m_q;
160  }
161
162  if (jp==-1)
163  {
164  cp = cp*EuclideanMultiplicativeInverse(m_s, m_p)%m_p;
165  cq = cq*EuclideanMultiplicativeInverse(m_s, m_q)%m_q;
166  }
167
168  cp = ModularSquareRoot(cp, m_p);
169  cq = ModularSquareRoot(cq, m_q);
170
171  if (jp==-1)
172  cp = m_p-cp;
173
174  Integer out = CRT(cq, m_q, cp, m_p, m_u);
175
176  out = modn.Divide(out, r); // unblind
177
178  if ((jq==-1 && out.IsEven()) || (jq==1 && out.IsOdd()))
179  out = m_n-out;
180
181  return out;
182 }
183
184 bool InvertibleRabinFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
185 {
186  bool pass = RabinFunction::Validate(rng, level);
187  pass = pass && m_p > Integer::One() && m_p%4 == 3 && m_p < m_n;
188  pass = pass && m_q > Integer::One() && m_q%4 == 3 && m_q < m_n;
189  pass = pass && m_u.IsPositive() && m_u < m_p;
190  if (level >= 1)
191  {
192  pass = pass && m_p * m_q == m_n;
193  pass = pass && m_u * m_q % m_p == 1;
194  pass = pass && Jacobi(m_r, m_p) == 1;
195  pass = pass && Jacobi(m_r, m_q) == -1;
196  pass = pass && Jacobi(m_s, m_p) == -1;
197  pass = pass && Jacobi(m_s, m_q) == 1;
198  }
199  if (level >= 2)
200  pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
201  return pass;
202 }
203
204 bool InvertibleRabinFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
205 {
206  return GetValueHelper<RabinFunction>(this, name, valueType, pValue).Assignable()
207  CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
208  CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
209  CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
210  ;
211 }
212
214 {
215  AssignFromHelper<RabinFunction>(this, source)
216  CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
217  CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
218  CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
219  ;
220 }
221
222 NAMESPACE_END
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: rabin.cpp:43
const char * MultiplicativeInverseOfPrime2ModPrime1()
Integer.
Definition: argnames.h:46
An invalid argument was detected.
Definition: cryptlib.h:187
Classes for Rabin encryption and signature schemes.
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
Definition: rabin.cpp:31
const char * Prime2()
Integer.
Definition: argnames.h:43
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:347
Integer CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
Calculates the inverse of an element.
Definition: rabin.cpp:141
const char * QuadraticResidueModPrime1()
Integer.
Definition: argnames.h:47
bool IsEven() const
Determines if the Integer is even parity.
Definition: integer.h:344
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition: modarith.h:179
Ring of congruence classes modulo n.
Definition: modarith.h:34
Interface for random number generators.
Definition: cryptlib.h:1201
BER Sequence Decoder.
Definition: asn.h:294
Interface for buffered transformations.
Definition: cryptlib.h:1367
static const Integer & One()
Integer representing 1.
Definition: integer.cpp:3040
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:376
const char * Prime1()
Integer.
Definition: argnames.h:42
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition: modarith.h:172
const char * QuadraticResidueModPrime2()
Integer.
Definition: argnames.h:48
bool IsPositive() const
Determines if the Integer is positive.
Definition: integer.h:338
Integer Squared() const
Definition: integer.h:496
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
Definition: nbtheory.cpp:249
Multiple precision integer with arithmetic operations.
Definition: integer.h:45
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: rabin.cpp:76
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: rabin.cpp:54
const Integer & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
Definition: modarith.h:200
Classes and functions for working with ANS.1 objects.
Classes for SHA-1 and SHA-2 family of message digests.
Classes and functions for number theoretic operations.
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
Definition: integer.cpp:3396
DER Sequence Encoder.
Definition: asn.h:304
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: rabin.cpp:213
An object that implements NameValuePairs.
Definition: algparam.h:498
const char * Modulus()
Integer.
Definition: argnames.h:32
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:4239
Multiple precision integer with arithmetic operations.
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: rabin.cpp:63
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
Definition: integer.cpp:3403
Class file for performing modular arithmetic.
Crypto++ library namespace.
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: rabin.cpp:184
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: rabin.cpp:204
Interface for retrieving values given their names.
Definition: cryptlib.h:282
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition: cryptlib.h:2164