Crypto++ 8.5 Free C++ class library of cryptographic schemes

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