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