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