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