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