00001
00002
00003 #include "pch.h"
00004
00005 #ifndef CRYPTOPP_IMPORTS
00006
00007 #include "gf2n.h"
00008 #include "algebra.h"
00009 #include "words.h"
00010 #include "randpool.h"
00011 #include "asn.h"
00012 #include "oids.h"
00013
00014 #include <iostream>
00015
00016 NAMESPACE_BEGIN(CryptoPP)
00017
00018 PolynomialMod2::PolynomialMod2()
00019 {
00020 }
00021
00022 PolynomialMod2::PolynomialMod2(word value, size_t bitLength)
00023 : reg(BitsToWords(bitLength))
00024 {
00025 assert(value==0 || reg.size()>0);
00026
00027 if (reg.size() > 0)
00028 {
00029 reg[0] = value;
00030 SetWords(reg+1, 0, reg.size()-1);
00031 }
00032 }
00033
00034 PolynomialMod2::PolynomialMod2(const PolynomialMod2& t)
00035 : reg(t.reg.size())
00036 {
00037 CopyWords(reg, t.reg, reg.size());
00038 }
00039
00040 void PolynomialMod2::Randomize(RandomNumberGenerator &rng, size_t nbits)
00041 {
00042 const size_t nbytes = nbits/8 + 1;
00043 SecByteBlock buf(nbytes);
00044 rng.GenerateBlock(buf, nbytes);
00045 buf[0] = (byte)Crop(buf[0], nbits % 8);
00046 Decode(buf, nbytes);
00047 }
00048
00049 PolynomialMod2 PolynomialMod2::AllOnes(size_t bitLength)
00050 {
00051 PolynomialMod2 result((word)0, bitLength);
00052 SetWords(result.reg, ~(word)0, result.reg.size());
00053 if (bitLength%WORD_BITS)
00054 result.reg[result.reg.size()-1] = (word)Crop(result.reg[result.reg.size()-1], bitLength%WORD_BITS);
00055 return result;
00056 }
00057
00058 void PolynomialMod2::SetBit(size_t n, int value)
00059 {
00060 if (value)
00061 {
00062 reg.CleanGrow(n/WORD_BITS + 1);
00063 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
00064 }
00065 else
00066 {
00067 if (n/WORD_BITS < reg.size())
00068 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
00069 }
00070 }
00071
00072 byte PolynomialMod2::GetByte(size_t n) const
00073 {
00074 if (n/WORD_SIZE >= reg.size())
00075 return 0;
00076 else
00077 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
00078 }
00079
00080 void PolynomialMod2::SetByte(size_t n, byte value)
00081 {
00082 reg.CleanGrow(BytesToWords(n+1));
00083 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
00084 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
00085 }
00086
00087 PolynomialMod2 PolynomialMod2::Monomial(size_t i)
00088 {
00089 PolynomialMod2 r((word)0, i+1);
00090 r.SetBit(i);
00091 return r;
00092 }
00093
00094 PolynomialMod2 PolynomialMod2::Trinomial(size_t t0, size_t t1, size_t t2)
00095 {
00096 PolynomialMod2 r((word)0, t0+1);
00097 r.SetBit(t0);
00098 r.SetBit(t1);
00099 r.SetBit(t2);
00100 return r;
00101 }
00102
00103 PolynomialMod2 PolynomialMod2::Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4)
00104 {
00105 PolynomialMod2 r((word)0, t0+1);
00106 r.SetBit(t0);
00107 r.SetBit(t1);
00108 r.SetBit(t2);
00109 r.SetBit(t3);
00110 r.SetBit(t4);
00111 return r;
00112 }
00113
00114 template <word i>
00115 struct NewPolynomialMod2
00116 {
00117 PolynomialMod2 * operator()() const
00118 {
00119 return new PolynomialMod2(i);
00120 }
00121 };
00122
00123 const PolynomialMod2 &PolynomialMod2::Zero()
00124 {
00125 return Singleton<PolynomialMod2>().Ref();
00126 }
00127
00128 const PolynomialMod2 &PolynomialMod2::One()
00129 {
00130 return Singleton<PolynomialMod2, NewPolynomialMod2<1> >().Ref();
00131 }
00132
00133 void PolynomialMod2::Decode(const byte *input, size_t inputLen)
00134 {
00135 StringStore store(input, inputLen);
00136 Decode(store, inputLen);
00137 }
00138
00139 void PolynomialMod2::Encode(byte *output, size_t outputLen) const
00140 {
00141 ArraySink sink(output, outputLen);
00142 Encode(sink, outputLen);
00143 }
00144
00145 void PolynomialMod2::Decode(BufferedTransformation &bt, size_t inputLen)
00146 {
00147 reg.CleanNew(BytesToWords(inputLen));
00148
00149 for (size_t i=inputLen; i > 0; i--)
00150 {
00151 byte b;
00152 bt.Get(b);
00153 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
00154 }
00155 }
00156
00157 void PolynomialMod2::Encode(BufferedTransformation &bt, size_t outputLen) const
00158 {
00159 for (size_t i=outputLen; i > 0; i--)
00160 bt.Put(GetByte(i-1));
00161 }
00162
00163 void PolynomialMod2::DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
00164 {
00165 DERGeneralEncoder enc(bt, OCTET_STRING);
00166 Encode(enc, length);
00167 enc.MessageEnd();
00168 }
00169
00170 void PolynomialMod2::BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
00171 {
00172 BERGeneralDecoder dec(bt, OCTET_STRING);
00173 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
00174 BERDecodeError();
00175 Decode(dec, length);
00176 dec.MessageEnd();
00177 }
00178
00179 unsigned int PolynomialMod2::WordCount() const
00180 {
00181 return (unsigned int)CountWords(reg, reg.size());
00182 }
00183
00184 unsigned int PolynomialMod2::ByteCount() const
00185 {
00186 unsigned wordCount = WordCount();
00187 if (wordCount)
00188 return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]);
00189 else
00190 return 0;
00191 }
00192
00193 unsigned int PolynomialMod2::BitCount() const
00194 {
00195 unsigned wordCount = WordCount();
00196 if (wordCount)
00197 return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]);
00198 else
00199 return 0;
00200 }
00201
00202 unsigned int PolynomialMod2::Parity() const
00203 {
00204 unsigned i;
00205 word temp=0;
00206 for (i=0; i<reg.size(); i++)
00207 temp ^= reg[i];
00208 return CryptoPP::Parity(temp);
00209 }
00210
00211 PolynomialMod2& PolynomialMod2::operator=(const PolynomialMod2& t)
00212 {
00213 reg.Assign(t.reg);
00214 return *this;
00215 }
00216
00217 PolynomialMod2& PolynomialMod2::operator^=(const PolynomialMod2& t)
00218 {
00219 reg.CleanGrow(t.reg.size());
00220 XorWords(reg, t.reg, t.reg.size());
00221 return *this;
00222 }
00223
00224 PolynomialMod2 PolynomialMod2::Xor(const PolynomialMod2 &b) const
00225 {
00226 if (b.reg.size() >= reg.size())
00227 {
00228 PolynomialMod2 result((word)0, b.reg.size()*WORD_BITS);
00229 XorWords(result.reg, reg, b.reg, reg.size());
00230 CopyWords(result.reg+reg.size(), b.reg+reg.size(), b.reg.size()-reg.size());
00231 return result;
00232 }
00233 else
00234 {
00235 PolynomialMod2 result((word)0, reg.size()*WORD_BITS);
00236 XorWords(result.reg, reg, b.reg, b.reg.size());
00237 CopyWords(result.reg+b.reg.size(), reg+b.reg.size(), reg.size()-b.reg.size());
00238 return result;
00239 }
00240 }
00241
00242 PolynomialMod2 PolynomialMod2::And(const PolynomialMod2 &b) const
00243 {
00244 PolynomialMod2 result((word)0, WORD_BITS*STDMIN(reg.size(), b.reg.size()));
00245 AndWords(result.reg, reg, b.reg, result.reg.size());
00246 return result;
00247 }
00248
00249 PolynomialMod2 PolynomialMod2::Times(const PolynomialMod2 &b) const
00250 {
00251 PolynomialMod2 result((word)0, BitCount() + b.BitCount());
00252
00253 for (int i=b.Degree(); i>=0; i--)
00254 {
00255 result <<= 1;
00256 if (b[i])
00257 XorWords(result.reg, reg, reg.size());
00258 }
00259 return result;
00260 }
00261
00262 PolynomialMod2 PolynomialMod2::Squared() const
00263 {
00264 static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};
00265
00266 PolynomialMod2 result((word)0, 2*reg.size()*WORD_BITS);
00267
00268 for (unsigned i=0; i<reg.size(); i++)
00269 {
00270 unsigned j;
00271
00272 for (j=0; j<WORD_BITS; j+=8)
00273 result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
00274
00275 for (j=0; j<WORD_BITS; j+=8)
00276 result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j;
00277 }
00278
00279 return result;
00280 }
00281
00282 void PolynomialMod2::Divide(PolynomialMod2 &remainder, PolynomialMod2 "ient,
00283 const PolynomialMod2 ÷nd, const PolynomialMod2 &divisor)
00284 {
00285 if (!divisor)
00286 throw PolynomialMod2::DivideByZero();
00287
00288 int degree = divisor.Degree();
00289 remainder.reg.CleanNew(BitsToWords(degree+1));
00290 if (dividend.BitCount() >= divisor.BitCount())
00291 quotient.reg.CleanNew(BitsToWords(dividend.BitCount() - divisor.BitCount() + 1));
00292 else
00293 quotient.reg.CleanNew(0);
00294
00295 for (int i=dividend.Degree(); i>=0; i--)
00296 {
00297 remainder <<= 1;
00298 remainder.reg[0] |= dividend[i];
00299 if (remainder[degree])
00300 {
00301 remainder -= divisor;
00302 quotient.SetBit(i);
00303 }
00304 }
00305 }
00306
00307 PolynomialMod2 PolynomialMod2::DividedBy(const PolynomialMod2 &b) const
00308 {
00309 PolynomialMod2 remainder, quotient;
00310 PolynomialMod2::Divide(remainder, quotient, *this, b);
00311 return quotient;
00312 }
00313
00314 PolynomialMod2 PolynomialMod2::Modulo(const PolynomialMod2 &b) const
00315 {
00316 PolynomialMod2 remainder, quotient;
00317 PolynomialMod2::Divide(remainder, quotient, *this, b);
00318 return remainder;
00319 }
00320
00321 PolynomialMod2& PolynomialMod2::operator<<=(unsigned int n)
00322 {
00323 if (!reg.size())
00324 return *this;
00325
00326 int i;
00327 word u;
00328 word carry=0;
00329 word *r=reg;
00330
00331 if (n==1)
00332 {
00333 i = (int)reg.size();
00334 while (i--)
00335 {
00336 u = *r;
00337 *r = (u << 1) | carry;
00338 carry = u >> (WORD_BITS-1);
00339 r++;
00340 }
00341
00342 if (carry)
00343 {
00344 reg.Grow(reg.size()+1);
00345 reg[reg.size()-1] = carry;
00346 }
00347
00348 return *this;
00349 }
00350
00351 int shiftWords = n / WORD_BITS;
00352 int shiftBits = n % WORD_BITS;
00353
00354 if (shiftBits)
00355 {
00356 i = (int)reg.size();
00357 while (i--)
00358 {
00359 u = *r;
00360 *r = (u << shiftBits) | carry;
00361 carry = u >> (WORD_BITS-shiftBits);
00362 r++;
00363 }
00364 }
00365
00366 if (carry)
00367 {
00368 reg.Grow(reg.size()+shiftWords+1);
00369 reg[reg.size()-1] = carry;
00370 }
00371 else
00372 reg.Grow(reg.size()+shiftWords);
00373
00374 if (shiftWords)
00375 {
00376 for (i = (int)reg.size()-1; i>=shiftWords; i--)
00377 reg[i] = reg[i-shiftWords];
00378 for (; i>=0; i--)
00379 reg[i] = 0;
00380 }
00381
00382 return *this;
00383 }
00384
00385 PolynomialMod2& PolynomialMod2::operator>>=(unsigned int n)
00386 {
00387 if (!reg.size())
00388 return *this;
00389
00390 int shiftWords = n / WORD_BITS;
00391 int shiftBits = n % WORD_BITS;
00392
00393 size_t i;
00394 word u;
00395 word carry=0;
00396 word *r=reg+reg.size()-1;
00397
00398 if (shiftBits)
00399 {
00400 i = reg.size();
00401 while (i--)
00402 {
00403 u = *r;
00404 *r = (u >> shiftBits) | carry;
00405 carry = u << (WORD_BITS-shiftBits);
00406 r--;
00407 }
00408 }
00409
00410 if (shiftWords)
00411 {
00412 for (i=0; i<reg.size()-shiftWords; i++)
00413 reg[i] = reg[i+shiftWords];
00414 for (; i<reg.size(); i++)
00415 reg[i] = 0;
00416 }
00417
00418 return *this;
00419 }
00420
00421 PolynomialMod2 PolynomialMod2::operator<<(unsigned int n) const
00422 {
00423 PolynomialMod2 result(*this);
00424 return result<<=n;
00425 }
00426
00427 PolynomialMod2 PolynomialMod2::operator>>(unsigned int n) const
00428 {
00429 PolynomialMod2 result(*this);
00430 return result>>=n;
00431 }
00432
00433 bool PolynomialMod2::operator!() const
00434 {
00435 for (unsigned i=0; i<reg.size(); i++)
00436 if (reg[i]) return false;
00437 return true;
00438 }
00439
00440 bool PolynomialMod2::Equals(const PolynomialMod2 &rhs) const
00441 {
00442 size_t i, smallerSize = STDMIN(reg.size(), rhs.reg.size());
00443
00444 for (i=0; i<smallerSize; i++)
00445 if (reg[i] != rhs.reg[i]) return false;
00446
00447 for (i=smallerSize; i<reg.size(); i++)
00448 if (reg[i] != 0) return false;
00449
00450 for (i=smallerSize; i<rhs.reg.size(); i++)
00451 if (rhs.reg[i] != 0) return false;
00452
00453 return true;
00454 }
00455
00456 std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a)
00457 {
00458
00459 long f = out.flags() & std::ios::basefield;
00460 int bits, block;
00461 char suffix;
00462 switch(f)
00463 {
00464 case std::ios::oct :
00465 bits = 3;
00466 block = 4;
00467 suffix = 'o';
00468 break;
00469 case std::ios::hex :
00470 bits = 4;
00471 block = 2;
00472 suffix = 'h';
00473 break;
00474 default :
00475 bits = 1;
00476 block = 8;
00477 suffix = 'b';
00478 }
00479
00480 if (!a)
00481 return out << '0' << suffix;
00482
00483 SecBlock<char> s(a.BitCount()/bits+1);
00484 unsigned i;
00485
00486 static const char upper[]="0123456789ABCDEF";
00487 static const char lower[]="0123456789abcdef";
00488 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
00489
00490 for (i=0; i*bits < a.BitCount(); i++)
00491 {
00492 int digit=0;
00493 for (int j=0; j<bits; j++)
00494 digit |= a[i*bits+j] << j;
00495 s[i]=vec[digit];
00496 }
00497
00498 while (i--)
00499 {
00500 out << s[i];
00501 if (i && (i%block)==0)
00502 out << ',';
00503 }
00504
00505 return out << suffix;
00506 }
00507
00508 PolynomialMod2 PolynomialMod2::Gcd(const PolynomialMod2 &a, const PolynomialMod2 &b)
00509 {
00510 return EuclideanDomainOf<PolynomialMod2>().Gcd(a, b);
00511 }
00512
00513 PolynomialMod2 PolynomialMod2::InverseMod(const PolynomialMod2 &modulus) const
00514 {
00515 typedef EuclideanDomainOf<PolynomialMod2> Domain;
00516 return QuotientRing<Domain>(Domain(), modulus).MultiplicativeInverse(*this);
00517 }
00518
00519 bool PolynomialMod2::IsIrreducible() const
00520 {
00521 signed int d = Degree();
00522 if (d <= 0)
00523 return false;
00524
00525 PolynomialMod2 t(2), u(t);
00526 for (int i=1; i<=d/2; i++)
00527 {
00528 u = u.Squared()%(*this);
00529 if (!Gcd(u+t, *this).IsUnit())
00530 return false;
00531 }
00532 return true;
00533 }
00534
00535
00536
00537 GF2NP::GF2NP(const PolynomialMod2 &modulus)
00538 : QuotientRing<EuclideanDomainOf<PolynomialMod2> >(EuclideanDomainOf<PolynomialMod2>(), modulus), m(modulus.Degree())
00539 {
00540 }
00541
00542 GF2NP::Element GF2NP::SquareRoot(const Element &a) const
00543 {
00544 Element r = a;
00545 for (unsigned int i=1; i<m; i++)
00546 r = Square(r);
00547 return r;
00548 }
00549
00550 GF2NP::Element GF2NP::HalfTrace(const Element &a) const
00551 {
00552 assert(m%2 == 1);
00553 Element h = a;
00554 for (unsigned int i=1; i<=(m-1)/2; i++)
00555 h = Add(Square(Square(h)), a);
00556 return h;
00557 }
00558
00559 GF2NP::Element GF2NP::SolveQuadraticEquation(const Element &a) const
00560 {
00561 if (m%2 == 0)
00562 {
00563 Element z, w;
00564 RandomPool rng;
00565 do
00566 {
00567 Element p((RandomNumberGenerator &)rng, m);
00568 z = PolynomialMod2::Zero();
00569 w = p;
00570 for (unsigned int i=1; i<=m-1; i++)
00571 {
00572 w = Square(w);
00573 z = Square(z);
00574 Accumulate(z, Multiply(w, a));
00575 Accumulate(w, p);
00576 }
00577 } while (w.IsZero());
00578 return z;
00579 }
00580 else
00581 return HalfTrace(a);
00582 }
00583
00584
00585
00586 GF2NT::GF2NT(unsigned int t0, unsigned int t1, unsigned int t2)
00587 : GF2NP(PolynomialMod2::Trinomial(t0, t1, t2))
00588 , t0(t0), t1(t1)
00589 , result((word)0, m)
00590 {
00591 assert(t0 > t1 && t1 > t2 && t2==0);
00592 }
00593
00594 const GF2NT::Element& GF2NT::MultiplicativeInverse(const Element &a) const
00595 {
00596 if (t0-t1 < WORD_BITS)
00597 return GF2NP::MultiplicativeInverse(a);
00598
00599 SecWordBlock T(m_modulus.reg.size() * 4);
00600 word *b = T;
00601 word *c = T+m_modulus.reg.size();
00602 word *f = T+2*m_modulus.reg.size();
00603 word *g = T+3*m_modulus.reg.size();
00604 size_t bcLen=1, fgLen=m_modulus.reg.size();
00605 unsigned int k=0;
00606
00607 SetWords(T, 0, 3*m_modulus.reg.size());
00608 b[0]=1;
00609 assert(a.reg.size() <= m_modulus.reg.size());
00610 CopyWords(f, a.reg, a.reg.size());
00611 CopyWords(g, m_modulus.reg, m_modulus.reg.size());
00612
00613 while (1)
00614 {
00615 word t=f[0];
00616 while (!t)
00617 {
00618 ShiftWordsRightByWords(f, fgLen, 1);
00619 if (c[bcLen-1])
00620 bcLen++;
00621 assert(bcLen <= m_modulus.reg.size());
00622 ShiftWordsLeftByWords(c, bcLen, 1);
00623 k+=WORD_BITS;
00624 t=f[0];
00625 }
00626
00627 unsigned int i=0;
00628 while (t%2 == 0)
00629 {
00630 t>>=1;
00631 i++;
00632 }
00633 k+=i;
00634
00635 if (t==1 && CountWords(f, fgLen)==1)
00636 break;
00637
00638 if (i==1)
00639 {
00640 ShiftWordsRightByBits(f, fgLen, 1);
00641 t=ShiftWordsLeftByBits(c, bcLen, 1);
00642 }
00643 else
00644 {
00645 ShiftWordsRightByBits(f, fgLen, i);
00646 t=ShiftWordsLeftByBits(c, bcLen, i);
00647 }
00648 if (t)
00649 {
00650 c[bcLen] = t;
00651 bcLen++;
00652 assert(bcLen <= m_modulus.reg.size());
00653 }
00654
00655 if (f[fgLen-1]==0 && g[fgLen-1]==0)
00656 fgLen--;
00657
00658 if (f[fgLen-1] < g[fgLen-1])
00659 {
00660 std::swap(f, g);
00661 std::swap(b, c);
00662 }
00663
00664 XorWords(f, g, fgLen);
00665 XorWords(b, c, bcLen);
00666 }
00667
00668 while (k >= WORD_BITS)
00669 {
00670 word temp = b[0];
00671
00672 for (unsigned i=0; i+1<BitsToWords(m); i++)
00673 b[i] = b[i+1];
00674 b[BitsToWords(m)-1] = 0;
00675
00676 if (t1 < WORD_BITS)
00677 for (unsigned int j=0; j<WORD_BITS-t1; j++)
00678 temp ^= ((temp >> j) & 1) << (t1 + j);
00679 else
00680 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
00681
00682 if (t1 % WORD_BITS)
00683 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
00684
00685 if (t0%WORD_BITS)
00686 {
00687 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
00688 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
00689 }
00690 else
00691 b[t0/WORD_BITS-1] ^= temp;
00692
00693 k -= WORD_BITS;
00694 }
00695
00696 if (k)
00697 {
00698 word temp = b[0] << (WORD_BITS - k);
00699 ShiftWordsRightByBits(b, BitsToWords(m), k);
00700
00701 if (t1 < WORD_BITS)
00702 for (unsigned int j=0; j<WORD_BITS-t1; j++)
00703 temp ^= ((temp >> j) & 1) << (t1 + j);
00704 else
00705 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
00706
00707 if (t1 % WORD_BITS)
00708 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
00709
00710 if (t0%WORD_BITS)
00711 {
00712 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
00713 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
00714 }
00715 else
00716 b[t0/WORD_BITS-1] ^= temp;
00717 }
00718
00719 CopyWords(result.reg.begin(), b, result.reg.size());
00720 return result;
00721 }
00722
00723 const GF2NT::Element& GF2NT::Multiply(const Element &a, const Element &b) const
00724 {
00725 size_t aSize = STDMIN(a.reg.size(), result.reg.size());
00726 Element r((word)0, m);
00727
00728 for (int i=m-1; i>=0; i--)
00729 {
00730 if (r[m-1])
00731 {
00732 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
00733 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
00734 }
00735 else
00736 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
00737
00738 if (b[i])
00739 XorWords(r.reg.begin(), a.reg, aSize);
00740 }
00741
00742 if (m%WORD_BITS)
00743 r.reg.begin()[r.reg.size()-1] = (word)Crop(r.reg[r.reg.size()-1], m%WORD_BITS);
00744
00745 CopyWords(result.reg.begin(), r.reg.begin(), result.reg.size());
00746 return result;
00747 }
00748
00749 const GF2NT::Element& GF2NT::Reduced(const Element &a) const
00750 {
00751 if (t0-t1 < WORD_BITS)
00752 return m_domain.Mod(a, m_modulus);
00753
00754 SecWordBlock b(a.reg);
00755
00756 size_t i;
00757 for (i=b.size()-1; i>=BitsToWords(t0); i--)
00758 {
00759 word temp = b[i];
00760
00761 if (t0%WORD_BITS)
00762 {
00763 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
00764 b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
00765 }
00766 else
00767 b[i-t0/WORD_BITS] ^= temp;
00768
00769 if ((t0-t1)%WORD_BITS)
00770 {
00771 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
00772 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
00773 }
00774 else
00775 b[i-(t0-t1)/WORD_BITS] ^= temp;
00776 }
00777
00778 if (i==BitsToWords(t0)-1 && t0%WORD_BITS)
00779 {
00780 word mask = ((word)1<<(t0%WORD_BITS))-1;
00781 word temp = b[i] & ~mask;
00782 b[i] &= mask;
00783
00784 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
00785
00786 if ((t0-t1)%WORD_BITS)
00787 {
00788 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
00789 if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
00790 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
00791 else
00792 assert(temp << (WORD_BITS - (t0-t1)%WORD_BITS) == 0);
00793 }
00794 else
00795 b[i-(t0-t1)/WORD_BITS] ^= temp;
00796 }
00797
00798 SetWords(result.reg.begin(), 0, result.reg.size());
00799 CopyWords(result.reg.begin(), b, STDMIN(b.size(), result.reg.size()));
00800 return result;
00801 }
00802
00803 void GF2NP::DEREncodeElement(BufferedTransformation &out, const Element &a) const
00804 {
00805 a.DEREncodeAsOctetString(out, MaxElementByteLength());
00806 }
00807
00808 void GF2NP::BERDecodeElement(BufferedTransformation &in, Element &a) const
00809 {
00810 a.BERDecodeAsOctetString(in, MaxElementByteLength());
00811 }
00812
00813 void GF2NT::DEREncode(BufferedTransformation &bt) const
00814 {
00815 DERSequenceEncoder seq(bt);
00816 ASN1::characteristic_two_field().DEREncode(seq);
00817 DERSequenceEncoder parameters(seq);
00818 DEREncodeUnsigned(parameters, m);
00819 ASN1::tpBasis().DEREncode(parameters);
00820 DEREncodeUnsigned(parameters, t1);
00821 parameters.MessageEnd();
00822 seq.MessageEnd();
00823 }
00824
00825 void GF2NPP::DEREncode(BufferedTransformation &bt) const
00826 {
00827 DERSequenceEncoder seq(bt);
00828 ASN1::characteristic_two_field().DEREncode(seq);
00829 DERSequenceEncoder parameters(seq);
00830 DEREncodeUnsigned(parameters, m);
00831 ASN1::ppBasis().DEREncode(parameters);
00832 DERSequenceEncoder pentanomial(parameters);
00833 DEREncodeUnsigned(pentanomial, t3);
00834 DEREncodeUnsigned(pentanomial, t2);
00835 DEREncodeUnsigned(pentanomial, t1);
00836 pentanomial.MessageEnd();
00837 parameters.MessageEnd();
00838 seq.MessageEnd();
00839 }
00840
00841 GF2NP * BERDecodeGF2NP(BufferedTransformation &bt)
00842 {
00843
00844 member_ptr<GF2NP> result;
00845
00846 BERSequenceDecoder seq(bt);
00847 if (OID(seq) != ASN1::characteristic_two_field())
00848 BERDecodeError();
00849 BERSequenceDecoder parameters(seq);
00850 unsigned int m;
00851 BERDecodeUnsigned(parameters, m);
00852 OID oid(parameters);
00853 if (oid == ASN1::tpBasis())
00854 {
00855 unsigned int t1;
00856 BERDecodeUnsigned(parameters, t1);
00857 result.reset(new GF2NT(m, t1, 0));
00858 }
00859 else if (oid == ASN1::ppBasis())
00860 {
00861 unsigned int t1, t2, t3;
00862 BERSequenceDecoder pentanomial(parameters);
00863 BERDecodeUnsigned(pentanomial, t3);
00864 BERDecodeUnsigned(pentanomial, t2);
00865 BERDecodeUnsigned(pentanomial, t1);
00866 pentanomial.MessageEnd();
00867 result.reset(new GF2NPP(m, t3, t2, t1, 0));
00868 }
00869 else
00870 {
00871 BERDecodeError();
00872 return NULL;
00873 }
00874 parameters.MessageEnd();
00875 seq.MessageEnd();
00876
00877 return result.release();
00878 }
00879
00880 NAMESPACE_END
00881
00882 #endif