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