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