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