Crypto++  8.2
Free C++ class library of cryptographic schemes
gf2n.cpp
1 // gf2n.cpp - originally written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 #include "config.h"
5 
6 #ifndef CRYPTOPP_IMPORTS
7 
8 #include "cryptlib.h"
9 #include "algebra.h"
10 #include "randpool.h"
11 #include "filters.h"
12 #include "smartptr.h"
13 #include "words.h"
14 #include "misc.h"
15 #include "gf2n.h"
16 #include "oids.h"
17 #include "asn.h"
18 #include "cpu.h"
19 
20 #include <iostream>
21 
22 ANONYMOUS_NAMESPACE_BEGIN
23 
24 using CryptoPP::PolynomialMod2;
25 
26 #if defined(HAVE_GCC_INIT_PRIORITY)
27  const PolynomialMod2 g_zero __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 60))) = PolynomialMod2();
28  const PolynomialMod2 g_one __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 61))) = PolynomialMod2(1);
29 #elif defined(HAVE_MSC_INIT_PRIORITY)
30  #pragma warning(disable: 4075)
31  #pragma init_seg(".CRT$XCU")
32  const PolynomialMod2 g_zero;
33  const PolynomialMod2 g_one(1);
34  #pragma warning(default: 4075)
35 #elif defined(HAVE_XLC_INIT_PRIORITY)
36  #pragma priority(290)
37  const PolynomialMod2 g_zero;
38  const PolynomialMod2 g_one(1);
39 #endif
40 
41 ANONYMOUS_NAMESPACE_END
42 
43 NAMESPACE_BEGIN(CryptoPP)
44 
45 #if (CRYPTOPP_CLMUL_AVAILABLE)
46 extern CRYPTOPP_DLL void GF2NT_233_Multiply_Reduce_CLMUL(const word* pA, const word* pB, word* pC);
47 extern CRYPTOPP_DLL void GF2NT_233_Square_Reduce_CLMUL(const word* pA, word* pC);
48 #endif
49 
50 #if (CRYPTOPP_ARM_PMULL_AVAILABLE)
51 extern void GF2NT_233_Multiply_Reduce_ARMv8(const word* pA, const word* pB, word* pC);
52 extern void GF2NT_233_Square_Reduce_ARMv8(const word* pA, word* pC);
53 #endif
54 
55 #if (CRYPTOPP_POWER8_VMULL_AVAILABLE)
56 extern void GF2NT_233_Multiply_Reduce_POWER8(const word* pA, const word* pB, word* pC);
57 extern void GF2NT_233_Square_Reduce_POWER8(const word* pA, word* pC);
58 #endif
59 
61 {
62 }
63 
64 PolynomialMod2::PolynomialMod2(word value, size_t bitLength)
65  : reg(BitsToWords(bitLength))
66 {
67  CRYPTOPP_ASSERT(value==0 || reg.size()>0);
68 
69  if (reg.size() > 0)
70  {
71  reg[0] = value;
72  SetWords(reg+1, 0, reg.size()-1);
73  }
74 }
75 
77  : reg(t.reg.size())
78 {
79  CopyWords(reg, t.reg, reg.size());
80 }
81 
82 void PolynomialMod2::Randomize(RandomNumberGenerator &rng, size_t nbits)
83 {
84  const size_t nbytes = nbits/8 + 1;
85  SecByteBlock buf(nbytes);
86  rng.GenerateBlock(buf, nbytes);
87  buf[0] = (byte)Crop(buf[0], nbits % 8);
88  Decode(buf, nbytes);
89 }
90 
92 {
93  PolynomialMod2 result((word)0, bitLength);
94  SetWords(result.reg, ~(word(0)), result.reg.size());
95  if (bitLength%WORD_BITS)
96  result.reg[result.reg.size()-1] = (word)Crop(result.reg[result.reg.size()-1], bitLength%WORD_BITS);
97  return result;
98 }
99 
100 void PolynomialMod2::SetBit(size_t n, int value)
101 {
102  if (value)
103  {
104  reg.CleanGrow(n/WORD_BITS + 1);
105  reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
106  }
107  else
108  {
109  if (n/WORD_BITS < reg.size())
110  reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
111  }
112 }
113 
114 byte PolynomialMod2::GetByte(size_t n) const
115 {
116  if (n/WORD_SIZE >= reg.size())
117  return 0;
118  else
119  return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
120 }
121 
122 void PolynomialMod2::SetByte(size_t n, byte value)
123 {
124  reg.CleanGrow(BytesToWords(n+1));
125  reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
126  reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
127 }
128 
130 {
131  PolynomialMod2 r((word)0, i+1);
132  r.SetBit(i);
133  return r;
134 }
135 
136 PolynomialMod2 PolynomialMod2::Trinomial(size_t t0, size_t t1, size_t t2)
137 {
138  PolynomialMod2 r((word)0, t0+1);
139  r.SetBit(t0);
140  r.SetBit(t1);
141  r.SetBit(t2);
142  return r;
143 }
144 
145 PolynomialMod2 PolynomialMod2::Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4)
146 {
147  PolynomialMod2 r((word)0, t0+1);
148  r.SetBit(t0);
149  r.SetBit(t1);
150  r.SetBit(t2);
151  r.SetBit(t3);
152  r.SetBit(t4);
153  return r;
154 }
155 
156 template <word i>
158 {
159  PolynomialMod2 * operator()() const
160  {
161  return new PolynomialMod2(i);
162  }
163 };
164 
166 {
167 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
168  return g_zero;
169 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
170  static const PolynomialMod2 g_zero;
171  return g_zero;
172 #else
173  return Singleton<PolynomialMod2>().Ref();
174 #endif
175 }
176 
178 {
179 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
180  return g_one;
181 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
182  static const PolynomialMod2 g_one(1);
183  return g_one;
184 #else
186 #endif
187 }
188 
189 void PolynomialMod2::Decode(const byte *input, size_t inputLen)
190 {
191  StringStore store(input, inputLen);
192  Decode(store, inputLen);
193 }
194 
195 void PolynomialMod2::Encode(byte *output, size_t outputLen) const
196 {
197  ArraySink sink(output, outputLen);
198  Encode(sink, outputLen);
199 }
200 
201 void PolynomialMod2::Decode(BufferedTransformation &bt, size_t inputLen)
202 {
203  CRYPTOPP_ASSERT(bt.MaxRetrievable() >= inputLen);
204  if (bt.MaxRetrievable() < inputLen)
205  throw InvalidArgument("PolynomialMod2: input length is too small");
206 
207  reg.CleanNew(BytesToWords(inputLen));
208 
209  for (size_t i=inputLen; i > 0; i--)
210  {
211  byte b;
212  (void)bt.Get(b);
213  reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
214  }
215 }
216 
217 void PolynomialMod2::Encode(BufferedTransformation &bt, size_t outputLen) const
218 {
219  for (size_t i=outputLen; i > 0; i--)
220  bt.Put(GetByte(i-1));
221 }
222 
224 {
225  DERGeneralEncoder enc(bt, OCTET_STRING);
226  Encode(enc, length);
227  enc.MessageEnd();
228 }
229 
231 {
232  BERGeneralDecoder dec(bt, OCTET_STRING);
233  if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
234  BERDecodeError();
235  Decode(dec, length);
236  dec.MessageEnd();
237 }
238 
239 unsigned int PolynomialMod2::WordCount() const
240 {
241  return (unsigned int)CountWords(reg, reg.size());
242 }
243 
244 unsigned int PolynomialMod2::ByteCount() const
245 {
246  unsigned wordCount = WordCount();
247  if (wordCount)
248  return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]);
249  else
250  return 0;
251 }
252 
253 unsigned int PolynomialMod2::BitCount() const
254 {
255  unsigned wordCount = WordCount();
256  if (wordCount)
257  return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]);
258  else
259  return 0;
260 }
261 
262 unsigned int PolynomialMod2::Parity() const
263 {
264  unsigned i;
265  word temp=0;
266  for (i=0; i<reg.size(); i++)
267  temp ^= reg[i];
268  return CryptoPP::Parity(temp);
269 }
270 
271 PolynomialMod2& PolynomialMod2::operator=(const PolynomialMod2& t)
272 {
273  reg.Assign(t.reg);
274  return *this;
275 }
276 
277 PolynomialMod2& PolynomialMod2::operator^=(const PolynomialMod2& t)
278 {
279  reg.CleanGrow(t.reg.size());
280  XorWords(reg, t.reg, t.reg.size());
281  return *this;
282 }
283 
284 PolynomialMod2 PolynomialMod2::Xor(const PolynomialMod2 &b) const
285 {
286  if (b.reg.size() >= reg.size())
287  {
288  PolynomialMod2 result((word)0, b.reg.size()*WORD_BITS);
289  XorWords(result.reg, reg, b.reg, reg.size());
290  CopyWords(result.reg+reg.size(), b.reg+reg.size(), b.reg.size()-reg.size());
291  return result;
292  }
293  else
294  {
295  PolynomialMod2 result((word)0, reg.size()*WORD_BITS);
296  XorWords(result.reg, reg, b.reg, b.reg.size());
297  CopyWords(result.reg+b.reg.size(), reg+b.reg.size(), reg.size()-b.reg.size());
298  return result;
299  }
300 }
301 
302 PolynomialMod2 PolynomialMod2::And(const PolynomialMod2 &b) const
303 {
304  PolynomialMod2 result((word)0, WORD_BITS*STDMIN(reg.size(), b.reg.size()));
305  AndWords(result.reg, reg, b.reg, result.reg.size());
306  return result;
307 }
308 
309 PolynomialMod2 PolynomialMod2::Times(const PolynomialMod2 &b) const
310 {
311  PolynomialMod2 result((word)0, BitCount() + b.BitCount());
312 
313  for (int i=b.Degree(); i>=0; i--)
314  {
315  result <<= 1;
316  if (b[i])
317  XorWords(result.reg, reg, reg.size());
318  }
319  return result;
320 }
321 
322 PolynomialMod2 PolynomialMod2::Squared() const
323 {
324  static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};
325 
326  PolynomialMod2 result((word)0, 2*reg.size()*WORD_BITS);
327 
328  for (unsigned i=0; i<reg.size(); i++)
329  {
330  unsigned j;
331 
332  for (j=0; j<WORD_BITS; j+=8)
333  result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
334 
335  for (j=0; j<WORD_BITS; j+=8)
336  result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j;
337  }
338 
339  return result;
340 }
341 
343  const PolynomialMod2 &dividend, const PolynomialMod2 &divisor)
344 {
345  if (!divisor)
347 
348  int degree = divisor.Degree();
349  remainder.reg.CleanNew(BitsToWords(degree+1));
350  if (dividend.BitCount() >= divisor.BitCount())
351  quotient.reg.CleanNew(BitsToWords(dividend.BitCount() - divisor.BitCount() + 1));
352  else
353  quotient.reg.CleanNew(0);
354 
355  for (int i=dividend.Degree(); i>=0; i--)
356  {
357  remainder <<= 1;
358  remainder.reg[0] |= dividend[i];
359  if (remainder[degree])
360  {
361  remainder -= divisor;
362  quotient.SetBit(i);
363  }
364  }
365 }
366 
367 PolynomialMod2 PolynomialMod2::DividedBy(const PolynomialMod2 &b) const
368 {
369  PolynomialMod2 remainder, quotient;
370  PolynomialMod2::Divide(remainder, quotient, *this, b);
371  return quotient;
372 }
373 
374 PolynomialMod2 PolynomialMod2::Modulo(const PolynomialMod2 &b) const
375 {
376  PolynomialMod2 remainder, quotient;
377  PolynomialMod2::Divide(remainder, quotient, *this, b);
378  return remainder;
379 }
380 
381 PolynomialMod2& PolynomialMod2::operator<<=(unsigned int n)
382 {
383 #if defined(CRYPTOPP_DEBUG)
384  int x=0; CRYPTOPP_UNUSED(x);
386 #endif
387 
388  if (!reg.size())
389  return *this;
390 
391  int i;
392  word u;
393  word carry=0;
394  word *r=reg;
395 
396  if (n==1) // special case code for most frequent case
397  {
398  i = (int)reg.size();
399  while (i--)
400  {
401  u = *r;
402  *r = (u << 1) | carry;
403  carry = u >> (WORD_BITS-1);
404  r++;
405  }
406 
407  if (carry)
408  {
409  reg.Grow(reg.size()+1);
410  reg[reg.size()-1] = carry;
411  }
412 
413  return *this;
414  }
415 
416  const int shiftWords = n / WORD_BITS;
417  const int shiftBits = n % WORD_BITS;
418 
419  if (shiftBits)
420  {
421  i = (int)reg.size();
422  while (i--)
423  {
424  u = *r;
425  *r = (u << shiftBits) | carry;
426  carry = u >> (WORD_BITS-shiftBits);
427  r++;
428  }
429  }
430 
431  if (carry)
432  {
433  // Thanks to Apatryda, http://github.com/weidai11/cryptopp/issues/64
434  const size_t carryIndex = reg.size();
435  reg.Grow(reg.size()+shiftWords+!!shiftBits);
436  reg[carryIndex] = carry;
437  }
438  else
439  reg.Grow(reg.size()+shiftWords);
440 
441  if (shiftWords)
442  {
443  for (i = (int)reg.size()-1; i>=shiftWords; i--)
444  reg[i] = reg[i-shiftWords];
445  for (; i>=0; i--)
446  reg[i] = 0;
447  }
448 
449  return *this;
450 }
451 
452 PolynomialMod2& PolynomialMod2::operator>>=(unsigned int n)
453 {
454  if (!reg.size())
455  return *this;
456 
457  int shiftWords = n / WORD_BITS;
458  int shiftBits = n % WORD_BITS;
459 
460  size_t i;
461  word u;
462  word carry=0;
463  word *r=reg+reg.size()-1;
464 
465  if (shiftBits)
466  {
467  i = reg.size();
468  while (i--)
469  {
470  u = *r;
471  *r = (u >> shiftBits) | carry;
472  carry = u << (WORD_BITS-shiftBits);
473  r--;
474  }
475  }
476 
477  if (shiftWords)
478  {
479  for (i=0; i<reg.size()-shiftWords; i++)
480  reg[i] = reg[i+shiftWords];
481  for (; i<reg.size(); i++)
482  reg[i] = 0;
483  }
484 
485  return *this;
486 }
487 
488 PolynomialMod2 PolynomialMod2::operator<<(unsigned int n) const
489 {
490  PolynomialMod2 result(*this);
491  return result<<=n;
492 }
493 
494 PolynomialMod2 PolynomialMod2::operator>>(unsigned int n) const
495 {
496  PolynomialMod2 result(*this);
497  return result>>=n;
498 }
499 
500 bool PolynomialMod2::operator!() const
501 {
502  for (unsigned i=0; i<reg.size(); i++)
503  if (reg[i]) return false;
504  return true;
505 }
506 
507 bool PolynomialMod2::Equals(const PolynomialMod2 &rhs) const
508 {
509  size_t i, smallerSize = STDMIN(reg.size(), rhs.reg.size());
510 
511  for (i=0; i<smallerSize; i++)
512  if (reg[i] != rhs.reg[i]) return false;
513 
514  for (i=smallerSize; i<reg.size(); i++)
515  if (reg[i] != 0) return false;
516 
517  for (i=smallerSize; i<rhs.reg.size(); i++)
518  if (rhs.reg[i] != 0) return false;
519 
520  return true;
521 }
522 
523 std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a)
524 {
525  // Get relevant conversion specifications from ostream.
526  long f = out.flags() & std::ios::basefield; // Get base digits.
527  int bits, block;
528  char suffix;
529  switch(f)
530  {
531  case std::ios::oct :
532  bits = 3;
533  block = 4;
534  suffix = 'o';
535  break;
536  case std::ios::hex :
537  bits = 4;
538  block = 2;
539  suffix = 'h';
540  break;
541  default :
542  bits = 1;
543  block = 8;
544  suffix = 'b';
545  }
546 
547  if (!a)
548  return out << '0' << suffix;
549 
550  SecBlock<char> s(a.BitCount()/bits+1);
551  unsigned i;
552 
553  static const char upper[]="0123456789ABCDEF";
554  static const char lower[]="0123456789abcdef";
555  const char* const vec = (out.flags() & std::ios::uppercase) ? upper : lower;
556 
557  for (i=0; i*bits < a.BitCount(); i++)
558  {
559  int digit=0;
560  for (int j=0; j<bits; j++)
561  digit |= a[i*bits+j] << j;
562  s[i]=vec[digit];
563  }
564 
565  while (i--)
566  {
567  out << s[i];
568  if (i && (i%block)==0)
569  out << ',';
570  }
571 
572  return out << suffix;
573 }
574 
576 {
577  return EuclideanDomainOf<PolynomialMod2>().Gcd(a, b);
578 }
579 
581 {
582  typedef EuclideanDomainOf<PolynomialMod2> Domain;
583  return QuotientRing<Domain>(Domain(), modulus).MultiplicativeInverse(*this);
584 }
585 
587 {
588  signed int d = Degree();
589  if (d <= 0)
590  return false;
591 
592  PolynomialMod2 t(2), u(t);
593  for (int i=1; i<=d/2; i++)
594  {
595  u = u.Squared()%(*this);
596  if (!Gcd(u+t, *this).IsUnit())
597  return false;
598  }
599  return true;
600 }
601 
602 // ********************************************************
603 
604 GF2NP::GF2NP(const PolynomialMod2 &modulus)
605  : QuotientRing<EuclideanDomainOf<PolynomialMod2> >(EuclideanDomainOf<PolynomialMod2>(), modulus), m(modulus.Degree())
606 {
607 }
608 
609 GF2NP::Element GF2NP::SquareRoot(const Element &a) const
610 {
611  Element r = a;
612  for (unsigned int i=1; i<m; i++)
613  r = Square(r);
614  return r;
615 }
616 
617 GF2NP::Element GF2NP::HalfTrace(const Element &a) const
618 {
619  CRYPTOPP_ASSERT(m%2 == 1);
620  Element h = a;
621  for (unsigned int i=1; i<=(m-1)/2; i++)
622  h = Add(Square(Square(h)), a);
623  return h;
624 }
625 
626 GF2NP::Element GF2NP::SolveQuadraticEquation(const Element &a) const
627 {
628  if (m%2 == 0)
629  {
630  Element z, w;
631  RandomPool rng;
632  do
633  {
634  Element p((RandomNumberGenerator &)rng, m);
635  z = PolynomialMod2::Zero();
636  w = p;
637  for (unsigned int i=1; i<=m-1; i++)
638  {
639  w = Square(w);
640  z = Square(z);
641  Accumulate(z, Multiply(w, a));
642  Accumulate(w, p);
643  }
644  } while (w.IsZero());
645  return z;
646  }
647  else
648  return HalfTrace(a);
649 }
650 
651 // ********************************************************
652 
653 GF2NT::GF2NT(unsigned int c0, unsigned int c1, unsigned int c2)
654  : GF2NP(PolynomialMod2::Trinomial(c0, c1, c2))
655  , t0(c0), t1(c1)
656  , result((word)0, m)
657 {
658  CRYPTOPP_ASSERT(c0 > c1 && c1 > c2 && c2==0);
659 }
660 
661 const GF2NT::Element& GF2NT::MultiplicativeInverse(const Element &a) const
662 {
663  if (t0-t1 < WORD_BITS)
665 
666  SecWordBlock T(m_modulus.reg.size() * 4);
667  word *b = T;
668  word *c = T+m_modulus.reg.size();
669  word *f = T+2*m_modulus.reg.size();
670  word *g = T+3*m_modulus.reg.size();
671  size_t bcLen=1, fgLen=m_modulus.reg.size();
672  unsigned int k=0;
673 
674  SetWords(T, 0, 3*m_modulus.reg.size());
675  b[0]=1;
676  CRYPTOPP_ASSERT(a.reg.size() <= m_modulus.reg.size());
677  CopyWords(f, a.reg, a.reg.size());
678  CopyWords(g, m_modulus.reg, m_modulus.reg.size());
679 
680  while (1)
681  {
682  word t=f[0];
683  while (!t)
684  {
685  ShiftWordsRightByWords(f, fgLen, 1);
686  if (c[bcLen-1])
687  bcLen++;
688  CRYPTOPP_ASSERT(bcLen <= m_modulus.reg.size());
689  ShiftWordsLeftByWords(c, bcLen, 1);
690  k+=WORD_BITS;
691  t=f[0];
692  }
693 
694  unsigned int i=0;
695  while (t%2 == 0)
696  {
697  t>>=1;
698  i++;
699  }
700  k+=i;
701 
702  if (t==1 && CountWords(f, fgLen)==1)
703  break;
704 
705  if (i==1)
706  {
707  ShiftWordsRightByBits(f, fgLen, 1);
708  t=ShiftWordsLeftByBits(c, bcLen, 1);
709  }
710  else
711  {
712  ShiftWordsRightByBits(f, fgLen, i);
713  t=ShiftWordsLeftByBits(c, bcLen, i);
714  }
715  if (t)
716  {
717  c[bcLen] = t;
718  bcLen++;
719  CRYPTOPP_ASSERT(bcLen <= m_modulus.reg.size());
720  }
721 
722  if (f[fgLen-1]==0 && g[fgLen-1]==0)
723  fgLen--;
724 
725  if (f[fgLen-1] < g[fgLen-1])
726  {
727  std::swap(f, g);
728  std::swap(b, c);
729  }
730 
731  XorWords(f, g, fgLen);
732  XorWords(b, c, bcLen);
733  }
734 
735  while (k >= WORD_BITS)
736  {
737  word temp = b[0];
738  // right shift b
739  for (unsigned i=0; i+1<BitsToWords(m); i++)
740  b[i] = b[i+1];
741  b[BitsToWords(m)-1] = 0;
742 
743  if (t1 < WORD_BITS)
744  for (unsigned int j=0; j<WORD_BITS-t1; j++)
745  {
746  // Coverity finding on shift amount of 'word x << (t1+j)'.
747  // temp ^= ((temp >> j) & 1) << (t1 + j);
748  const unsigned int shift = t1 + j;
749  CRYPTOPP_ASSERT(shift < WORD_BITS);
750  temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
751  }
752  else
753  b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
754 
755  if (t1 % WORD_BITS)
756  b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
757 
758  if (t0%WORD_BITS)
759  {
760  b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
761  b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
762  }
763  else
764  b[t0/WORD_BITS-1] ^= temp;
765 
766  k -= WORD_BITS;
767  }
768 
769  if (k)
770  {
771  word temp = b[0] << (WORD_BITS - k);
772  ShiftWordsRightByBits(b, BitsToWords(m), k);
773 
774  if (t1 < WORD_BITS)
775  {
776  for (unsigned int j=0; j<WORD_BITS-t1; j++)
777  {
778  // Coverity finding on shift amount of 'word x << (t1+j)'.
779  // temp ^= ((temp >> j) & 1) << (t1 + j);
780  const unsigned int shift = t1 + j;
781  CRYPTOPP_ASSERT(shift < WORD_BITS);
782  temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
783  }
784  }
785  else
786  {
787  b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
788  }
789 
790  if (t1 % WORD_BITS)
791  b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
792 
793  if (t0%WORD_BITS)
794  {
795  b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
796  b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
797  }
798  else
799  b[t0/WORD_BITS-1] ^= temp;
800  }
801 
802  CopyWords(result.reg.begin(), b, result.reg.size());
803  return result;
804 }
805 
806 const GF2NT::Element& GF2NT::Multiply(const Element &a, const Element &b) const
807 {
808  size_t aSize = STDMIN(a.reg.size(), result.reg.size());
809  Element r((word)0, m);
810 
811  for (int i=m-1; i>=0; i--)
812  {
813  if (r[m-1])
814  {
815  ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
816  XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
817  }
818  else
819  ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
820 
821  if (b[i])
822  XorWords(r.reg.begin(), a.reg, aSize);
823  }
824 
825  if (m%WORD_BITS)
826  r.reg.begin()[r.reg.size()-1] = (word)Crop(r.reg[r.reg.size()-1], m%WORD_BITS);
827 
828  CopyWords(result.reg.begin(), r.reg.begin(), result.reg.size());
829  return result;
830 }
831 
832 const GF2NT::Element& GF2NT::Reduced(const Element &a) const
833 {
834  if (t0-t1 < WORD_BITS)
835  return m_domain.Mod(a, m_modulus);
836 
837  SecWordBlock b(a.reg);
838 
839  size_t i;
840  for (i=b.size()-1; i>=BitsToWords(t0); i--)
841  {
842  word temp = b[i];
843 
844  if (t0%WORD_BITS)
845  {
846  b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
847  b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
848  }
849  else
850  b[i-t0/WORD_BITS] ^= temp;
851 
852  if ((t0-t1)%WORD_BITS)
853  {
854  b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
855  b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
856  }
857  else
858  b[i-(t0-t1)/WORD_BITS] ^= temp;
859  }
860 
861  if (i==BitsToWords(t0)-1 && t0%WORD_BITS)
862  {
863  word mask = ((word)1<<(t0%WORD_BITS))-1;
864  word temp = b[i] & ~mask;
865  b[i] &= mask;
866 
867  b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
868 
869  if ((t0-t1)%WORD_BITS)
870  {
871  b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
872  if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
873  b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
874  else
875  CRYPTOPP_ASSERT(temp << (WORD_BITS - (t0-t1)%WORD_BITS) == 0);
876  }
877  else
878  b[i-(t0-t1)/WORD_BITS] ^= temp;
879  }
880 
881  SetWords(result.reg.begin(), 0, result.reg.size());
882  CopyWords(result.reg.begin(), b, STDMIN(b.size(), result.reg.size()));
883  return result;
884 }
885 
886 void GF2NP::DEREncodeElement(BufferedTransformation &out, const Element &a) const
887 {
888  a.DEREncodeAsOctetString(out, MaxElementByteLength());
889 }
890 
891 void GF2NP::BERDecodeElement(BufferedTransformation &in, Element &a) const
892 {
893  a.BERDecodeAsOctetString(in, MaxElementByteLength());
894 }
895 
896 void GF2NT::DEREncode(BufferedTransformation &bt) const
897 {
898  DERSequenceEncoder seq(bt);
899  ASN1::characteristic_two_field().DEREncode(seq);
900  DERSequenceEncoder parameters(seq);
901  DEREncodeUnsigned(parameters, m);
902  ASN1::tpBasis().DEREncode(parameters);
903  DEREncodeUnsigned(parameters, t1);
904  parameters.MessageEnd();
905  seq.MessageEnd();
906 }
907 
908 void GF2NPP::DEREncode(BufferedTransformation &bt) const
909 {
910  DERSequenceEncoder seq(bt);
911  ASN1::characteristic_two_field().DEREncode(seq);
912  DERSequenceEncoder parameters(seq);
913  DEREncodeUnsigned(parameters, m);
914  ASN1::ppBasis().DEREncode(parameters);
915  DERSequenceEncoder pentanomial(parameters);
916  DEREncodeUnsigned(pentanomial, t3);
917  DEREncodeUnsigned(pentanomial, t2);
918  DEREncodeUnsigned(pentanomial, t1);
919  pentanomial.MessageEnd();
920  parameters.MessageEnd();
921  seq.MessageEnd();
922 }
923 
924 GF2NP * BERDecodeGF2NP(BufferedTransformation &bt)
925 {
926  member_ptr<GF2NP> result;
927 
928  BERSequenceDecoder seq(bt);
929  if (OID(seq) != ASN1::characteristic_two_field())
930  BERDecodeError();
931  BERSequenceDecoder parameters(seq);
932  unsigned int m;
933  BERDecodeUnsigned(parameters, m);
934  OID oid(parameters);
935  if (oid == ASN1::tpBasis())
936  {
937  unsigned int t1;
938  BERDecodeUnsigned(parameters, t1);
939  result.reset(new GF2NT(m, t1, 0));
940  }
941  else if (oid == ASN1::ppBasis())
942  {
943  unsigned int t1, t2, t3;
944  BERSequenceDecoder pentanomial(parameters);
945  BERDecodeUnsigned(pentanomial, t3);
946  BERDecodeUnsigned(pentanomial, t2);
947  BERDecodeUnsigned(pentanomial, t1);
948  pentanomial.MessageEnd();
949  result.reset(new GF2NPP(m, t3, t2, t1, 0));
950  }
951  else
952  {
953  BERDecodeError();
954  return NULLPTR;
955  }
956  parameters.MessageEnd();
957  seq.MessageEnd();
958 
959  return result.release();
960 }
961 
962 // ********************************************************
963 
964 GF2NT233::GF2NT233(unsigned int c0, unsigned int c1, unsigned int c2)
965  : GF2NT(c0, c1, c2)
966 {
967  CRYPTOPP_ASSERT(c0 > c1 && c1 > c2 && c2==0);
968 }
969 
970 const GF2NT::Element& GF2NT233::Multiply(const Element &a, const Element &b) const
971 {
972 #if (CRYPTOPP_CLMUL_AVAILABLE)
973  if (HasCLMUL())
974  {
975  CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
976  CRYPTOPP_ASSERT(b.reg.size()*WORD_BITS == 256);
977  CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
978 
979  const word* pA = a.reg.begin();
980  const word* pB = b.reg.begin();
981  word* pR = result.reg.begin();
982 
983  GF2NT_233_Multiply_Reduce_CLMUL(pA, pB, pR);
984  return result;
985  }
986  else
987 #elif (CRYPTOPP_ARM_PMULL_AVAILABLE)
988  if (HasPMULL())
989  {
990  CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
991  CRYPTOPP_ASSERT(b.reg.size()*WORD_BITS == 256);
992  CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
993 
994  const word* pA = a.reg.begin();
995  const word* pB = b.reg.begin();
996  word* pR = result.reg.begin();
997 
998  GF2NT_233_Multiply_Reduce_ARMv8(pA, pB, pR);
999  return result;
1000  }
1001  else
1002 #elif (CRYPTOPP_POWER8_VMULL_AVAILABLE)
1003  if (HasPMULL())
1004  {
1005  CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
1006  CRYPTOPP_ASSERT(b.reg.size()*WORD_BITS == 256);
1007  CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
1008 
1009  const word* pA = a.reg.begin();
1010  const word* pB = b.reg.begin();
1011  word* pR = result.reg.begin();
1012 
1013  GF2NT_233_Multiply_Reduce_POWER8(pA, pB, pR);
1014  return result;
1015  }
1016  else
1017 #endif
1018 
1019  return GF2NT::Multiply(a, b);
1020 }
1021 
1022 const GF2NT::Element& GF2NT233::Square(const Element &a) const
1023 {
1024 #if (CRYPTOPP_CLMUL_AVAILABLE)
1025  if (HasCLMUL())
1026  {
1027  CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
1028  CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
1029 
1030  const word* pA = a.reg.begin();
1031  word* pR = result.reg.begin();
1032 
1033  GF2NT_233_Square_Reduce_CLMUL(pA, pR);
1034  return result;
1035  }
1036  else
1037 #elif (CRYPTOPP_ARM_PMULL_AVAILABLE)
1038  if (HasPMULL())
1039  {
1040  CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
1041  CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
1042 
1043  const word* pA = a.reg.begin();
1044  word* pR = result.reg.begin();
1045 
1046  GF2NT_233_Square_Reduce_ARMv8(pA, pR);
1047  return result;
1048  }
1049  else
1050 #elif (CRYPTOPP_POWER8_VMULL_AVAILABLE)
1051  if (HasPMULL())
1052  {
1053  CRYPTOPP_ASSERT(a.reg.size()*WORD_BITS == 256);
1054  CRYPTOPP_ASSERT(result.reg.size()*WORD_BITS == 256);
1055 
1056  const word* pA = a.reg.begin();
1057  word* pR = result.reg.begin();
1058 
1059  GF2NT_233_Square_Reduce_POWER8(pA, pR);
1060  return result;
1061  }
1062  else
1063 #endif
1064 
1065  return GF2NT::Square(a);
1066 }
1067 
1068 NAMESPACE_END
1069 
1070 #endif
SecBlock::begin
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:772
Singleton::Ref
const T & Ref(...) const
Return a reference to the inner Singleton object.
Definition: misc.h:284
member_ptr< GF2NP >
SecWordBlock
SecBlock<word> typedef.
Definition: secblock.h:1060
PolynomialMod2::Divide
static void Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d)
calculate r and q such that (a == d*q + r) && (deg(r) < deg(d))
Definition: gf2n.cpp:342
QuotientRing
Quotient ring.
Definition: algebra.h:386
gf2n.h
Classes and functions for schemes over GF(2^n)
SecBlock::Grow
void Grow(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:995
PolynomialMod2::GetByte
byte GetByte(size_t n) const
return the n-th byte
Definition: gf2n.cpp:114
StringStore
String-based implementation of Store interface.
Definition: filters.h:1195
PolynomialMod2
Polynomial with Coefficients in GF(2)
Definition: gf2n.h:26
PolynomialMod2::InverseMod
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
Definition: gf2n.cpp:580
DERSequenceEncoder
DER Sequence Encoder.
Definition: asn.h:319
DERGeneralEncoder
DER General Encoder.
Definition: asn.h:291
PolynomialMod2::DEREncodeAsOctetString
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
Definition: gf2n.cpp:223
BufferedTransformation
Interface for buffered transformations.
Definition: cryptlib.h:1598
PolynomialMod2::Trinomial
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
Definition: gf2n.cpp:136
QuotientRing< EuclideanDomainOf< PolynomialMod2 > >::Accumulate
Element & Accumulate(Element &a, const Element &b) const
Definition: algebra.h:410
SecByteBlock
SecBlock<byte> typedef.
Definition: secblock.h:1058
PolynomialMod2::ByteCount
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
Definition: gf2n.cpp:244
QuotientRing::MultiplicativeInverse
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
Definition: algebra.cpp:70
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69
GF2NT233::Square
const Element & Square(const Element &a) const
Square an element in the group.
Definition: gf2n.cpp:1022
GF2NT233::Multiply
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
Definition: gf2n.cpp:970
smartptr.h
Classes for automatic resource management.
PolynomialMod2::SetByte
void SetByte(size_t n, byte value)
set the n-th byte to value
Definition: gf2n.cpp:122
PolynomialMod2::BERDecodeAsOctetString
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
Definition: gf2n.cpp:230
BufferedTransformation::Put
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1620
Singleton
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:263
SafeConvert
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
Definition: misc.h:622
pch.h
Precompiled header file.
PolynomialMod2::AllOnes
static PolynomialMod2 AllOnes(size_t n)
Provides x^(n-1) + ...
Definition: gf2n.cpp:91
RandomNumberGenerator::GenerateBlock
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: cryptlib.cpp:311
PolynomialMod2::Parity
unsigned int Parity() const
sum modulo 2 of all coefficients
Definition: gf2n.cpp:262
BERGeneralDecoder
BER General Decoder.
Definition: asn.h:258
OID
Object Identifier.
Definition: asn.h:166
filters.h
Implementation of BufferedTransformation's attachment interface.
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1383
NewPolynomialMod2
Definition: gf2n.cpp:157
BERDecodeError
void BERDecodeError()
Raises a BERDecodeErr.
Definition: asn.h:69
BitsToWords
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
Definition: misc.h:870
BytePrecision
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
Definition: misc.h:731
randpool.h
Class file for Randomness Pool.
DEREncodeUnsigned
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
Definition: asn.h:461
SecBlock::CleanGrow
void CleanGrow(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:1013
misc.h
Utility functions for the Crypto++ library.
PolynomialMod2::Degree
signed int Degree() const
the zero polynomial will return a degree of -1
Definition: gf2n.h:128
EuclideanDomainOf< PolynomialMod2 >
QuotientRing< EuclideanDomainOf< PolynomialMod2 > >::Square
const Element & Square(const Element &a) const
Definition: algebra.h:434
PolynomialMod2::Pentanomial
static PolynomialMod2 Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4)
Provides x^t0 + x^t1 + x^t2 + x^t3 + x^t4.
Definition: gf2n.cpp:145
SecBlock::CleanNew
void CleanNew(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:980
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:567
PolynomialMod2::Zero
static const PolynomialMod2 & Zero()
The Zero polinomial.
Definition: gf2n.cpp:165
ArraySink
Copy input to a memory buffer.
Definition: filters.h:1136
BufferedTransformation::MaxRetrievable
virtual lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: cryptlib.cpp:504
PolynomialMod2::PolynomialMod2
PolynomialMod2()
Construct the zero polynomial.
Definition: gf2n.cpp:60
GF2NT::Square
const Element & Square(const Element &a) const
Square an element in the group.
Definition: gf2n.h:343
GF2NP
GF(2^n) with Polynomial Basis.
Definition: gf2n.h:296
GF2NPP
GF(2^n) with Pentanomial Basis.
Definition: gf2n.h:372
cpu.h
Functions for CPU features and intrinsics.
asn.h
Classes and functions for working with ANS.1 objects.
oids.h
ASN.1 object identifiers for algorthms and schemes.
HasCLMUL
bool HasCLMUL()
Determines Carryless Multiply availability.
Definition: cpu.h:177
BitPrecision
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:754
PolynomialMod2::WordCount
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
Definition: gf2n.cpp:239
PolynomialMod2::IsUnit
bool IsUnit() const
only 1 is a unit
Definition: gf2n.h:228
SecBlock::size
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:797
PolynomialMod2::Monomial
static PolynomialMod2 Monomial(size_t i)
Provides x^i.
Definition: gf2n.cpp:129
InvalidArgument
An invalid argument was detected.
Definition: cryptlib.h:202
BufferedTransformation::Get
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: cryptlib.cpp:527
RandomPool
Randomness Pool based on AES-256.
Definition: randpool.h:41
SecBlock::Assign
void Assign(const T *ptr, size_type len)
Set contents and size from an array.
Definition: secblock.h:841
PolynomialMod2::Encode
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
Definition: gf2n.cpp:195
QuotientRing< EuclideanDomainOf< PolynomialMod2 > >::Multiply
const Element & Multiply(const Element &a, const Element &b) const
Definition: algebra.h:431
PolynomialMod2::DivideByZero
Excpetion thrown when divide by zero is encountered.
Definition: gf2n.h:32
algebra.h
Classes for performing mathematics over different fields.
Crop
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
Definition: misc.h:838
CryptoPP
Crypto++ library namespace.
GF2NT::MultiplicativeInverse
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
Definition: gf2n.cpp:661
PolynomialMod2::Gcd
static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
Definition: gf2n.cpp:575
config.h
Library configuration file.
HasPMULL
bool HasPMULL()
Determine if an ARM processor provides Polynomial Multiplication.
Definition: cpu.h:408
PolynomialMod2::One
static const PolynomialMod2 & One()
The One polinomial.
Definition: gf2n.cpp:177
PolynomialMod2::IsIrreducible
bool IsIrreducible() const
check for irreducibility
Definition: gf2n.cpp:586
BytesToWords
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
Definition: misc.h:860
SecBlock
Secure memory block with allocator and cleanup.
Definition: secblock.h:688
AbstractEuclideanDomain::Gcd
virtual const Element & Gcd(const Element &a, const Element &b) const
Calculates the greatest common denominator in the ring.
Definition: algebra.cpp:56
Parity
unsigned int Parity(T value)
Returns the parity of a value.
Definition: misc.h:719
BERDecodeUnsigned
void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag=INTEGER, T minValue=0, T maxValue=T(0xffffffff))
BER Decode unsigned value.
Definition: asn.h:497
QuotientRing< EuclideanDomainOf< PolynomialMod2 > >::Add
const Element & Add(const Element &a, const Element &b) const
Definition: algebra.h:407
cryptlib.h
Abstract base classes that provide a uniform interface to this library.
GF2NT
GF(2^n) with Trinomial Basis.
Definition: gf2n.h:332
BERSequenceDecoder
BER Sequence Decoder.
Definition: asn.h:309
GF2NT::Multiply
const Element & Multiply(const Element &a, const Element &b) const
Multiplies elements in the group.
Definition: gf2n.cpp:806
PolynomialMod2::BitCount
unsigned int BitCount() const
number of significant bits = Degree() + 1
Definition: gf2n.cpp:253