Crypto++  8.6
Free C++ class library of cryptographic schemes
esign.cpp
1 // esign.cpp - originally written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 #include "config.h"
5 
6 // TODO: fix the C4589 warnings
7 #if CRYPTOPP_MSC_VERSION
8 # pragma warning(disable: 4589)
9 #endif
10 
11 #include "esign.h"
12 #include "modarith.h"
13 #include "integer.h"
14 #include "nbtheory.h"
15 #include "algparam.h"
16 #include "sha.h"
17 #include "asn.h"
18 
19 NAMESPACE_BEGIN(CryptoPP)
20 
21 #if defined(CRYPTOPP_DEBUG) && !defined(CRYPTOPP_DOXYGEN_PROCESSING)
22 void ESIGN_TestInstantiations()
23 {
24  ESIGN<SHA1>::Verifier x1(1, 1);
26  ESIGN<SHA1>::Verifier x3(x2);
27  ESIGN<SHA1>::Verifier x4(x2.GetKey());
28  ESIGN<SHA1>::Verifier x5(x3);
29  ESIGN<SHA1>::Signer x6 = x2;
30 
31  x6 = x2;
32  x3 = ESIGN<SHA1>::Verifier(x2);
33  x4 = x2.GetKey();
34 }
35 #endif
36 
38 {
39  BERSequenceDecoder seq(bt);
40  m_n.BERDecode(seq);
41  m_e.BERDecode(seq);
42  seq.MessageEnd();
43 }
44 
46 {
47  DERSequenceEncoder seq(bt);
48  m_n.DEREncode(seq);
49  m_e.DEREncode(seq);
50  seq.MessageEnd();
51 }
52 
54 {
56  return STDMIN(a_exp_b_mod_c(x, m_e, m_n) >> (2*GetK()+2), MaxImage());
57 }
58 
59 bool ESIGNFunction::Validate(RandomNumberGenerator& rng, unsigned int level) const
60 {
61  CRYPTOPP_UNUSED(rng), CRYPTOPP_UNUSED(level);
62  bool pass = true;
63  pass = pass && m_n > Integer::One() && m_n.IsOdd();
64  CRYPTOPP_ASSERT(pass);
65  pass = pass && m_e >= 8 && m_e < m_n;
66  CRYPTOPP_ASSERT(pass);
67  return pass;
68 }
69 
70 bool ESIGNFunction::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  CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent)
75  ;
76 }
77 
79 {
80  AssignFromHelper(this, source)
81  CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
82  CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
83  ;
84 }
85 
86 // *****************************************************************************
87 
89 {
90  int modulusSize = 1023*2;
91  param.GetIntValue("ModulusSize", modulusSize) || param.GetIntValue("KeySize", modulusSize);
92 
93  if (modulusSize < 24)
94  throw InvalidArgument("InvertibleESIGNFunction: specified modulus size is too small");
95 
96  if (modulusSize % 3 != 0)
97  throw InvalidArgument("InvertibleESIGNFunction: modulus size must be divisible by 3");
98 
99  m_e = param.GetValueWithDefault("PublicExponent", Integer(32));
100 
101  if (m_e < 8)
102  throw InvalidArgument("InvertibleESIGNFunction: public exponents less than 8 may not be secure");
103 
104  // VC70 workaround: putting these after primeParam causes overlapped stack allocation
105  ConstByteArrayParameter seedParam;
106  SecByteBlock seed;
107 
108  const Integer minP = Integer(204) << (modulusSize/3-8);
109  const Integer maxP = Integer::Power2(modulusSize/3)-1;
110  AlgorithmParameters primeParam = MakeParameters("Min", minP)("Max", maxP)("RandomNumberType", Integer::PRIME);
111 
112  if (param.GetValue("Seed", seedParam))
113  {
114  seed.resize(seedParam.size() + 4);
115  memcpy(seed + 4, seedParam.begin(), seedParam.size());
116 
117  PutWord(false, BIG_ENDIAN_ORDER, seed, (word32)0);
118  m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("Seed", ConstByteArrayParameter(seed))));
119  PutWord(false, BIG_ENDIAN_ORDER, seed, (word32)1);
120  m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("Seed", ConstByteArrayParameter(seed))));
121  }
122  else
123  {
124  m_p.GenerateRandom(rng, primeParam);
125  m_q.GenerateRandom(rng, primeParam);
126  }
127 
128  m_n = m_p * m_p * m_q;
129 
130  CRYPTOPP_ASSERT(m_n.BitCount() == (unsigned int)modulusSize);
131 }
132 
134 {
135  BERSequenceDecoder privateKey(bt);
136  m_n.BERDecode(privateKey);
137  m_e.BERDecode(privateKey);
138  m_p.BERDecode(privateKey);
139  m_q.BERDecode(privateKey);
140  privateKey.MessageEnd();
141 }
142 
144 {
145  DERSequenceEncoder privateKey(bt);
146  m_n.DEREncode(privateKey);
147  m_e.DEREncode(privateKey);
148  m_p.DEREncode(privateKey);
149  m_q.DEREncode(privateKey);
150  privateKey.MessageEnd();
151 }
152 
154 {
156 
157  Integer pq = m_p * m_q;
158  Integer p2 = m_p * m_p;
159  Integer r, z, re, a, w0, w1;
160 
161  do
162  {
163  r.Randomize(rng, Integer::Zero(), pq);
164  z = x << (2*GetK()+2);
165  re = a_exp_b_mod_c(r, m_e, m_n);
166  a = (z - re) % m_n;
167  Integer::Divide(w1, w0, a, pq);
168  if (w1.NotZero())
169  {
170  ++w0;
171  w1 = pq - w1;
172  }
173  }
174  while ((w1 >> (2*GetK()+1)).IsPositive());
175 
176  ModularArithmetic modp(m_p);
177  Integer t = modp.Divide(w0 * r % m_p, m_e * re % m_p);
178  Integer s = r + t*pq;
179  CRYPTOPP_ASSERT(s < m_n);
180 #if 0
181  using namespace std;
182  cout << "f = " << x << endl;
183  cout << "r = " << r << endl;
184  cout << "z = " << z << endl;
185  cout << "a = " << a << endl;
186  cout << "w0 = " << w0 << endl;
187  cout << "w1 = " << w1 << endl;
188  cout << "t = " << t << endl;
189  cout << "s = " << s << endl;
190 #endif
191  return s;
192 }
193 
194 bool InvertibleESIGNFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
195 {
196  bool pass = ESIGNFunction::Validate(rng, level);
197  CRYPTOPP_ASSERT(pass);
198  pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
199  CRYPTOPP_ASSERT(pass);
200  pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
201  CRYPTOPP_ASSERT(pass);
202  pass = pass && m_p.BitCount() == m_q.BitCount();
203  CRYPTOPP_ASSERT(pass);
204  if (level >= 1)
205  {
206  pass = pass && m_p * m_p * m_q == m_n;
207  CRYPTOPP_ASSERT(pass);
208  }
209  if (level >= 2)
210  {
211  pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
212  CRYPTOPP_ASSERT(pass);
213  }
214  return pass;
215 }
216 
217 bool InvertibleESIGNFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
218 {
219  return GetValueHelper<ESIGNFunction>(this, name, valueType, pValue).Assignable()
220  CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
221  CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
222  ;
223 }
224 
226 {
227  AssignFromHelper<ESIGNFunction>(this, source)
228  CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
229  CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
230  ;
231 }
232 
233 NAMESPACE_END
Used to pass byte array input as part of a NameValuePairs object.
Definition: algparam.h:24
An invalid argument was detected.
Definition: cryptlib.h:202
bool NotZero() const
Determines if the Integer is non-0.
Definition: integer.h:336
Classes for working with NameValuePairs.
const Integer & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
Definition: modarith.h:218
a number which is probabilistically prime
Definition: integer.h:95
static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d)
Extended Division.
static const Integer & One()
Integer representing 1.
const char * Prime2()
Integer.
Definition: argnames.h:44
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:392
void DEREncode(BufferedTransformation &bt) const
Encode in DER format.
size_t size() const
Length of the memory block.
Definition: algparam.h:88
PK_FinalTemplate< TF_VerifierImpl< SchemeOptions > > Verifier
implements PK_Verifier interface
Definition: pubkey.h:2328
void DEREncode(BufferedTransformation &bt) const
Encode this object into a BufferedTransformation.
Definition: esign.cpp:143
void resize(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:1198
void MessageEnd()
Signals the end of messages to the object.
void PutWord(bool assumeAligned, ByteOrder order, byte *block, T value, const byte *xorBlock=NULL)
Access a block of memory.
Definition: misc.h:2502
unsigned int word32
32-bit unsigned datatype
Definition: config_int.h:62
Integer CalculateRandomizedInverse(RandomNumberGenerator &rng, const Integer &x) const
Applies the inverse of the trapdoor function, using random data if required.
Definition: esign.cpp:153
Library configuration file.
Ring of congruence classes modulo n.
Definition: modarith.h:43
STL namespace.
Interface for random number generators.
Definition: cryptlib.h:1434
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Combines two sets of NameValuePairs.
Definition: algparam.h:128
SecBlock<byte> typedef.
Definition: secblock.h:1226
BER Sequence Decoder.
Definition: asn.h:524
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params=g_nullNameValuePairs)
Generate a random number.
Definition: integer.h:506
Interface for buffered transformations.
Definition: cryptlib.h:1651
Classes providing ESIGN signature schemes as defined in IEEE P1363a.
CRYPTOPP_DLL bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: esign.cpp:59
const char * Prime1()
Integer.
Definition: argnames.h:43
void DoQuickSanityCheck() const
Perform a quick sanity check.
Definition: cryptlib.h:2493
void BERDecode(BufferedTransformation &bt)
Decode this object from a BufferedTransformation.
Definition: esign.cpp:133
CRYPTOPP_DLL RandomNumberGenerator & NullRNG()
Random Number Generator that does not produce random numbers.
const byte * begin() const
Pointer to the first byte in the memory block.
Definition: algparam.h:84
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:508
const char * PublicExponent()
Integer.
Definition: argnames.h:34
Integer ApplyFunction(const Integer &x) const
Applies the trapdoor.
Definition: esign.cpp:53
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: esign.cpp:225
virtual Integer MaxImage() const
Returns the maximum size of a message after the trapdoor function is applied bound to a public key...
Definition: pubkey.h:92
Multiple precision integer with arithmetic operations.
Definition: integer.h:49
Precompiled header file.
void BERDecode(BufferedTransformation &bt)
Decode this object from a BufferedTransformation.
Definition: esign.cpp:37
static Integer Power2(size_t e)
Exponentiates to a power of 2.
byte order is big-endian
Definition: cryptlib.h:147
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:655
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68
void DEREncode(BufferedTransformation &bt) const
Encode this object into a BufferedTransformation.
Definition: esign.cpp:45
Classes and functions for working with ANS.1 objects.
Classes for SHA-1 and SHA-2 family of message digests.
CRYPTOPP_DLL bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:415
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
void MessageEnd()
Signals the end of messages to the object.
Classes and functions for number theoretic operations.
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: esign.cpp:70
DER Sequence Encoder.
Definition: asn.h:556
An object that implements NameValuePairs.
Definition: algparam.h:425
const char * Modulus()
Integer.
Definition: argnames.h:33
Multiple precision integer with arithmetic operations.
static const Integer & Zero()
Integer representing 0.
void BERDecode(const byte *input, size_t inputLen)
Decode from BER format.
void AssignFrom(const NameValuePairs &source)
Assign values to this object.
Definition: esign.cpp:78
Class file for performing modular arithmetic.
Crypto++ library namespace.
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:379
bool GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
Get a named value.
Definition: esign.cpp:217
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: esign.cpp:88
bool IsOdd() const
Determines if the Integer is odd parity.
Definition: integer.h:354
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check this object for errors.
Definition: esign.cpp:194
Interface for retrieving values given their names.
Definition: cryptlib.h:321
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2197