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