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