Crypto++
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 "nbtheory.h"
6 #include "asn.h"
7 #include "sha.h"
8 #include "modarith.h"
9 
10 NAMESPACE_BEGIN(CryptoPP)
11 
12 void RabinFunction::BERDecode(BufferedTransformation &bt)
13 {
14  BERSequenceDecoder seq(bt);
15  m_n.BERDecode(seq);
16  m_r.BERDecode(seq);
17  m_s.BERDecode(seq);
18  seq.MessageEnd();
19 }
20 
21 void RabinFunction::DEREncode(BufferedTransformation &bt) const
22 {
23  DERSequenceEncoder seq(bt);
24  m_n.DEREncode(seq);
25  m_r.DEREncode(seq);
26  m_s.DEREncode(seq);
27  seq.MessageEnd();
28 }
29 
30 Integer RabinFunction::ApplyFunction(const Integer &in) const
31 {
32  DoQuickSanityCheck();
33 
34  Integer out = in.Squared()%m_n;
35  if (in.IsOdd())
36  out = out*m_r%m_n;
37  if (Jacobi(in, m_n)==-1)
38  out = out*m_s%m_n;
39  return out;
40 }
41 
42 bool RabinFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
43 {
44  bool pass = true;
45  pass = pass && m_n > Integer::One() && m_n%4 == 1;
46  pass = pass && m_r > Integer::One() && m_r < m_n;
47  pass = pass && m_s > Integer::One() && m_s < m_n;
48  if (level >= 1)
49  pass = pass && Jacobi(m_r, m_n) == -1 && Jacobi(m_s, m_n) == -1;
50  return pass;
51 }
52 
53 bool RabinFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
54 {
55  return GetValueHelper(this, name, valueType, pValue).Assignable()
56  CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
57  CRYPTOPP_GET_FUNCTION_ENTRY(QuadraticResidueModPrime1)
58  CRYPTOPP_GET_FUNCTION_ENTRY(QuadraticResidueModPrime2)
59  ;
60 }
61 
63 {
64  AssignFromHelper(this, source)
65  CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
66  CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime1)
67  CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime2)
68  ;
69 }
70 
71 // *****************************************************************************
72 // private key operations:
73 
74 // generate a random private key
76 {
77  int modulusSize = 2048;
78  alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
79 
80  if (modulusSize < 16)
81  throw InvalidArgument("InvertibleRabinFunction: specified modulus size is too small");
82 
83  // VC70 workaround: putting these after primeParam causes overlapped stack allocation
84  bool rFound=false, sFound=false;
85  Integer t=2;
86 
87  AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
88  ("EquivalentTo", 3)("Mod", 4);
89  m_p.GenerateRandom(rng, primeParam);
90  m_q.GenerateRandom(rng, primeParam);
91 
92  while (!(rFound && sFound))
93  {
94  int jp = Jacobi(t, m_p);
95  int jq = Jacobi(t, m_q);
96 
97  if (!rFound && jp==1 && jq==-1)
98  {
99  m_r = t;
100  rFound = true;
101  }
102 
103  if (!sFound && jp==-1 && jq==1)
104  {
105  m_s = t;
106  sFound = true;
107  }
108 
109  ++t;
110  }
111 
112  m_n = m_p * m_q;
113  m_u = m_q.InverseMod(m_p);
114 }
115 
116 void InvertibleRabinFunction::BERDecode(BufferedTransformation &bt)
117 {
118  BERSequenceDecoder seq(bt);
119  m_n.BERDecode(seq);
120  m_r.BERDecode(seq);
121  m_s.BERDecode(seq);
122  m_p.BERDecode(seq);
123  m_q.BERDecode(seq);
124  m_u.BERDecode(seq);
125  seq.MessageEnd();
126 }
127 
128 void InvertibleRabinFunction::DEREncode(BufferedTransformation &bt) const
129 {
130  DERSequenceEncoder seq(bt);
131  m_n.DEREncode(seq);
132  m_r.DEREncode(seq);
133  m_s.DEREncode(seq);
134  m_p.DEREncode(seq);
135  m_q.DEREncode(seq);
136  m_u.DEREncode(seq);
137  seq.MessageEnd();
138 }
139 
140 Integer InvertibleRabinFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &in) const
141 {
142  DoQuickSanityCheck();
143 
144  ModularArithmetic modn(m_n);
145  Integer r(rng, Integer::One(), m_n - Integer::One());
146  r = modn.Square(r);
147  Integer r2 = modn.Square(r);
148  Integer c = modn.Multiply(in, r2); // blind
149 
150  Integer cp=c%m_p, cq=c%m_q;
151 
152  int jp = Jacobi(cp, m_p);
153  int jq = Jacobi(cq, m_q);
154 
155  if (jq==-1)
156  {
157  cp = cp*EuclideanMultiplicativeInverse(m_r, m_p)%m_p;
158  cq = cq*EuclideanMultiplicativeInverse(m_r, m_q)%m_q;
159  }
160 
161  if (jp==-1)
162  {
163  cp = cp*EuclideanMultiplicativeInverse(m_s, m_p)%m_p;
164  cq = cq*EuclideanMultiplicativeInverse(m_s, m_q)%m_q;
165  }
166 
167  cp = ModularSquareRoot(cp, m_p);
168  cq = ModularSquareRoot(cq, m_q);
169 
170  if (jp==-1)
171  cp = m_p-cp;
172 
173  Integer out = CRT(cq, m_q, cp, m_p, m_u);
174 
175  out = modn.Divide(out, r); // unblind
176 
177  if ((jq==-1 && out.IsEven()) || (jq==1 && out.IsOdd()))
178  out = m_n-out;
179 
180  return out;
181 }
182 
183 bool InvertibleRabinFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
184 {
185  bool pass = RabinFunction::Validate(rng, level);
186  pass = pass && m_p > Integer::One() && m_p%4 == 3 && m_p < m_n;
187  pass = pass && m_q > Integer::One() && m_q%4 == 3 && m_q < m_n;
188  pass = pass && m_u.IsPositive() && m_u < m_p;
189  if (level >= 1)
190  {
191  pass = pass && m_p * m_q == m_n;
192  pass = pass && m_u * m_q % m_p == 1;
193  pass = pass && Jacobi(m_r, m_p) == 1;
194  pass = pass && Jacobi(m_r, m_q) == -1;
195  pass = pass && Jacobi(m_s, m_p) == -1;
196  pass = pass && Jacobi(m_s, m_q) == 1;
197  }
198  if (level >= 2)
199  pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
200  return pass;
201 }
202 
203 bool InvertibleRabinFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
204 {
205  return GetValueHelper<RabinFunction>(this, name, valueType, pValue).Assignable()
206  CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
207  CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
208  CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
209  ;
210 }
211 
213 {
214  AssignFromHelper<RabinFunction>(this, source)
215  CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
216  CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
217  CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
218  ;
219 }
220 
221 NAMESPACE_END
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
check this object for errors
Definition: rabin.cpp:42
exception thrown when an invalid argument is detected
Definition: cryptlib.h:145
ring of congruence classes modulo n
Definition: modarith.h:19
interface for random number generators
Definition: cryptlib.h:669
BER Sequence Decoder.
Definition: asn.h:177
interface for buffered transformations
Definition: cryptlib.h:771
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
multiple precision integer and basic arithmetics
Definition: integer.h:26
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: rabin.cpp:75
static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d)
calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
Definition: integer.cpp:3734
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: rabin.cpp:53
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
void AssignFrom(const NameValuePairs &source)
assign values from source to this object
Definition: rabin.cpp:212
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:3958
void AssignFrom(const NameValuePairs &source)
assign values from source to this object
Definition: rabin.cpp:62
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
check this object for errors
Definition: rabin.cpp:183
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: rabin.cpp:203
interface for retrieving values given their names
Definition: cryptlib.h:225