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