Crypto++
luc.cpp
1 // luc.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 #include "luc.h"
5 #include "asn.h"
6 #include "nbtheory.h"
7 #include "sha.h"
8 #include "algparam.h"
9 
10 NAMESPACE_BEGIN(CryptoPP)
11 
12 void LUC_TestInstantiations()
13 {
15  LUCFunction t2;
17 }
18 
19 void DL_Algorithm_LUC_HMP::Sign(const DL_GroupParameters<Integer> &params, const Integer &x, const Integer &k, const Integer &e, Integer &r, Integer &s) const
20 {
21  const Integer &q = params.GetSubgroupOrder();
22  r = params.ExponentiateBase(k);
23  s = (k + x*(r+e)) % q;
24 }
25 
26 bool DL_Algorithm_LUC_HMP::Verify(const DL_GroupParameters<Integer> &params, const DL_PublicKey<Integer> &publicKey, const Integer &e, const Integer &r, const Integer &s) const
27 {
28  Integer p = params.GetGroupOrder()-1;
29  const Integer &q = params.GetSubgroupOrder();
30 
31  Integer Vsg = params.ExponentiateBase(s);
32  Integer Vry = publicKey.ExponentiatePublicElement((r+e)%q);
33  return (Vsg*Vsg + Vry*Vry + r*r) % p == (Vsg * Vry * r + 4) % p;
34 }
35 
36 Integer DL_BasePrecomputation_LUC::Exponentiate(const DL_GroupPrecomputation<Element> &group, const Integer &exponent) const
37 {
38  return Lucas(exponent, m_g, static_cast<const DL_GroupPrecomputation_LUC &>(group).GetModulus());
39 }
40 
41 void DL_GroupParameters_LUC::SimultaneousExponentiate(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
42 {
43  for (unsigned int i=0; i<exponentsCount; i++)
44  results[i] = Lucas(exponents[i], base, GetModulus());
45 }
46 
47 void LUCFunction::BERDecode(BufferedTransformation &bt)
48 {
49  BERSequenceDecoder seq(bt);
50  m_n.BERDecode(seq);
51  m_e.BERDecode(seq);
52  seq.MessageEnd();
53 }
54 
55 void LUCFunction::DEREncode(BufferedTransformation &bt) const
56 {
57  DERSequenceEncoder seq(bt);
58  m_n.DEREncode(seq);
59  m_e.DEREncode(seq);
60  seq.MessageEnd();
61 }
62 
63 Integer LUCFunction::ApplyFunction(const Integer &x) const
64 {
65  DoQuickSanityCheck();
66  return Lucas(m_e, x, m_n);
67 }
68 
69 bool LUCFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
70 {
71  bool pass = true;
72  pass = pass && m_n > Integer::One() && m_n.IsOdd();
73  pass = pass && m_e > Integer::One() && m_e.IsOdd() && m_e < m_n;
74  return pass;
75 }
76 
77 bool LUCFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
78 {
79  return GetValueHelper(this, name, valueType, pValue).Assignable()
80  CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
81  CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent)
82  ;
83 }
84 
86 {
87  AssignFromHelper(this, source)
88  CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
89  CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
90  ;
91 }
92 
93 // *****************************************************************************
94 // private key operations:
95 
97 {
98 public:
99  LUCPrimeSelector(const Integer &e) : m_e(e) {}
100  bool IsAcceptable(const Integer &candidate) const
101  {
102  return RelativelyPrime(m_e, candidate+1) && RelativelyPrime(m_e, candidate-1);
103  }
104  Integer m_e;
105 };
106 
108 {
109  int modulusSize = 2048;
110  alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
111 
112  if (modulusSize < 16)
113  throw InvalidArgument("InvertibleLUCFunction: specified modulus size is too small");
114 
115  m_e = alg.GetValueWithDefault("PublicExponent", Integer(17));
116 
117  if (m_e < 5 || m_e.IsEven())
118  throw InvalidArgument("InvertibleLUCFunction: invalid public exponent");
119 
120  LUCPrimeSelector selector(m_e);
121  AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
122  ("PointerToPrimeSelector", selector.GetSelectorPointer());
123  m_p.GenerateRandom(rng, primeParam);
124  m_q.GenerateRandom(rng, primeParam);
125 
126  m_n = m_p * m_q;
127  m_u = m_q.InverseMod(m_p);
128 }
129 
130 void InvertibleLUCFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
131 {
132  GenerateRandom(rng, MakeParameters("ModulusSize", (int)keybits)("PublicExponent", e));
133 }
134 
135 void InvertibleLUCFunction::BERDecode(BufferedTransformation &bt)
136 {
137  BERSequenceDecoder seq(bt);
138 
139  Integer version(seq);
140  if (!!version) // make sure version is 0
141  BERDecodeError();
142 
143  m_n.BERDecode(seq);
144  m_e.BERDecode(seq);
145  m_p.BERDecode(seq);
146  m_q.BERDecode(seq);
147  m_u.BERDecode(seq);
148  seq.MessageEnd();
149 }
150 
151 void InvertibleLUCFunction::DEREncode(BufferedTransformation &bt) const
152 {
153  DERSequenceEncoder seq(bt);
154 
155  const byte version[] = {INTEGER, 1, 0};
156  seq.Put(version, sizeof(version));
157  m_n.DEREncode(seq);
158  m_e.DEREncode(seq);
159  m_p.DEREncode(seq);
160  m_q.DEREncode(seq);
161  m_u.DEREncode(seq);
162  seq.MessageEnd();
163 }
164 
165 Integer InvertibleLUCFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const
166 {
167  // not clear how to do blinding with LUC
168  DoQuickSanityCheck();
169  return InverseLucas(m_e, x, m_q, m_p, m_u);
170 }
171 
172 bool InvertibleLUCFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
173 {
174  bool pass = LUCFunction::Validate(rng, level);
175  pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
176  pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
177  pass = pass && m_u.IsPositive() && m_u < m_p;
178  if (level >= 1)
179  {
180  pass = pass && m_p * m_q == m_n;
181  pass = pass && RelativelyPrime(m_e, m_p+1);
182  pass = pass && RelativelyPrime(m_e, m_p-1);
183  pass = pass && RelativelyPrime(m_e, m_q+1);
184  pass = pass && RelativelyPrime(m_e, m_q-1);
185  pass = pass && m_u * m_q % m_p == 1;
186  }
187  if (level >= 2)
188  pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
189  return pass;
190 }
191 
192 bool InvertibleLUCFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
193 {
194  return GetValueHelper<LUCFunction>(this, name, valueType, pValue).Assignable()
195  CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
196  CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
197  CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
198  ;
199 }
200 
202 {
203  AssignFromHelper<LUCFunction>(this, source)
204  CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
205  CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
206  CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
207  ;
208 }
209 
210 NAMESPACE_END
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: luc.cpp:77
void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
Definition: luc.cpp:107
T GetValueWithDefault(const char *name, T defaultValue) const
get a named value, returns the default if the name doesn't exist
Definition: cryptlib.h:269
void AssignFrom(const NameValuePairs &source)
assign values from source to this object
Definition: luc.cpp:85
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
interface for DL public keys
Definition: pubkey.h:640
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: luc.cpp:192
multiple precision integer and basic arithmetics
Definition: integer.h:26
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: luc.cpp:201
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Definition: integer.cpp:3958
The LUC function.
Definition: luc.h:22
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
check this object for errors
Definition: luc.cpp:69
interface for retrieving values given their names
Definition: cryptlib.h:225
A template implementing constructors for public key algorithm classes.
Definition: pubkey.h:1488
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
check this object for errors
Definition: luc.cpp:172