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);
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
Element & Accumulate(Element &a, const Element &b) const
Definition: algebra.h:410
const Element & Add(const Element &a, const Element &b) const
Definition: algebra.h:407
An invalid argument was detected.
Definition: cryptlib.h:202
static const PolynomialMod2 &CRYPTOPP_API Zero()
The Zero polinomial.
Definition: gf2n.cpp:165
Randomness Pool based on AES-256.
Definition: randpool.h:41
void CopyWords(word *r, const word *a, size_t n)
Copy word array.
Definition: words.h:48
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
Definition: misc.h:663
Utility functions for the Crypto++ library.
PolynomialMod2()
Construct the zero polynomial.
Definition: gf2n.cpp:60
Restricts the instantiation of a class to one static object without locks.
Definition: misc.h:304
void CleanNew(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:980
Class file for Randomness Pool.
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
Definition: asn.h:643
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: cryptlib.cpp:312
bool IsUnit() const
only 1 is a unit
Definition: gf2n.h:228
GF(2^n) with Trinomial Basis.
Definition: gf2n.h:332
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
Definition: misc.h:911
void MessageEnd()
Signals the end of messages to the object.
Definition: asn.cpp:538
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
Definition: misc.h:772
void CleanGrow(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:1013
Secure memory block with allocator and cleanup.
Definition: secblock.h:688
Abstract base classes that provide a uniform interface to this library.
static const PolynomialMod2 &CRYPTOPP_API One()
The One polinomial.
Definition: gf2n.cpp:177
void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag=INTEGER, T minValue=0, T maxValue=T(0xffffffff))
BER Decode unsigned value.
Definition: asn.h:679
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
Definition: gf2n.cpp:195
ASN.1 object identifiers for algorthms and schemes.
Classes for automatic resource management.
Library configuration file.
Interface for random number generators.
Definition: cryptlib.h:1412
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
Definition: misc.h:901
const Element & Square(const Element &a) const
Square an element in the group.
Definition: gf2n.h:343
static PolynomialMod2 CRYPTOPP_API Monomial(size_t i)
Provides x^i.
Definition: gf2n.cpp:129
const Element & Square(const Element &a) const
Definition: algebra.h:434
SecBlock<byte> typedef.
Definition: secblock.h:1058
BER Sequence Decoder.
Definition: asn.h:403
Classes for performing mathematics over different fields.
Interface for buffered transformations.
Definition: cryptlib.h:1627
bool IsIrreducible() const
check for irreducibility
Definition: gf2n.cpp:586
Support functions for word operations.
Quotient ring.
Definition: algebra.h:386
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
Definition: gf2n.cpp:239
Polynomial with Coefficients in GF(2)
Definition: gf2n.h:26
unsigned int BitCount() const
number of significant bits = Degree() + 1
Definition: gf2n.cpp:253
Excpetion thrown when divide by zero is encountered.
Definition: gf2n.h:32
static PolynomialMod2 CRYPTOPP_API Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
Definition: gf2n.cpp:575
Copy input to a memory buffer.
Definition: filters.h:1137
void ShiftWordsLeftByWords(word *r, size_t n, size_t shiftWords)
Left shift word array.
Definition: words.h:194
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1649
const Element & Multiply(const Element &a, const Element &b) const
Definition: algebra.h:431
bool IsDefiniteLength() const
Determine length encoding.
Definition: asn.h:283
bool HasCLMUL()
Determines Carryless Multiply availability.
Definition: cpu.h:177
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
Definition: misc.h:879
void Assign(const T *ptr, size_type len)
Set contents and size from an array.
Definition: secblock.h:841
Precompiled header file.
void SetWords(word *r, word a, size_t n)
Set the value of words.
Definition: words.h:35
Classes and functions for schemes over GF(2^n)
void ShiftWordsRightByWords(word *r, size_t n, size_t shiftWords)
Right shift word array.
Definition: words.h:212
unsigned int Parity(T value)
Returns the parity of a value.
Definition: misc.h:760
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:608
String-based implementation of Store interface.
Definition: filters.h:1196
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:69
void SetByte(size_t n, byte value)
set the n-th byte to value
Definition: gf2n.cpp:122
void BERDecodeError()
Raises a BERDecodeErr.
Definition: asn.h:69
Functions for CPU features and intrinsics.
virtual const Element & Gcd(const Element &a, const Element &b) const
Calculates the greatest common denominator in the ring.
Definition: algebra.cpp:56
Classes and functions for working with ANS.1 objects.
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:772
Implementation of BufferedTransformation's attachment interface.
void MessageEnd()
Signals the end of messages to the object.
Definition: asn.cpp:467
GF(2^n) with Pentanomial Basis.
Definition: gf2n.h:372
static PolynomialMod2 CRYPTOPP_API AllOnes(size_t n)
Provides x^(n-1) + ...
Definition: gf2n.cpp:91
void XorWords(word *r, const word *a, const word *b, size_t n)
XOR word arrays.
Definition: words.h:66
DER Sequence Encoder.
Definition: asn.h:435
virtual lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: cryptlib.cpp:506
GF(2^n) with Polynomial Basis.
Definition: gf2n.h:296
DER General Encoder.
Definition: asn.h:369
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
Definition: gf2n.cpp:580
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
Definition: gf2n.cpp:223
static void CRYPTOPP_API 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
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
Definition: gf2n.cpp:244
word ShiftWordsRightByBits(word *r, size_t n, unsigned int shiftBits)
Right shift word array.
Definition: words.h:172
byte GetByte(size_t n) const
return the n-th byte
Definition: gf2n.cpp:114
signed int Degree() const
the zero polynomial will return a degree of -1
Definition: gf2n.h:128
void Grow(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:995
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
Definition: gf2n.cpp:230
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition: cryptlib.cpp:529
Crypto++ library namespace.
const Element & MultiplicativeInverse(const Element &a) const
Calculate the multiplicative inverse of an element in the group.
Definition: algebra.cpp:70
static PolynomialMod2 CRYPTOPP_API Trinomial(size_t t0, size_t t1, size_t t2)
Provides x^t0 + x^t1 + x^t2.
Definition: gf2n.cpp:136
BER General Decoder.
Definition: asn.h:258
unsigned int Parity() const
sum modulo 2 of all coefficients
Definition: gf2n.cpp:262
size_t CountWords(const word *x, size_t n)
Count the number of words.
Definition: words.h:21
word ShiftWordsLeftByBits(word *r, size_t n, unsigned int shiftBits)
Left shift word array.
Definition: words.h:149
static PolynomialMod2 CRYPTOPP_API 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
Object Identifier.
Definition: asn.h:166
SecBlock<word> typedef.
Definition: secblock.h:1060
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:795
const T & Ref(...) const
Return a reference to the inner Singleton object.
Definition: misc.h:325
size_type size() const
Provides the count of elements in the SecBlock.
Definition: secblock.h:797
lword RemainingLength() const
Determine remaining length.
Definition: asn.h:291
bool HasPMULL()
Determine if an ARM processor provides Polynomial Multiplication.
Definition: cpu.h:408
void AndWords(word *r, const word *a, const word *b, size_t n)
AND word arrays.
Definition: words.h:93