00001
#ifndef CRYPTOPP_GF2N_H
00002
#define CRYPTOPP_GF2N_H
00003
00004
00005
00006
#include "cryptlib.h"
00007
#include "secblock.h"
00008
#include "misc.h"
00009
#include "algebra.h"
00010
00011
#include <iosfwd>
00012
00013 NAMESPACE_BEGIN(CryptoPP)
00014
00015
00016
00017 class CRYPTOPP_DLL
PolynomialMod2
00018 {
00019
public:
00020
00021
00022
00023 class DivideByZero :
public Exception
00024 {
00025
public:
00026
DivideByZero() :
Exception(OTHER_ERROR,
"PolynomialMod2: division by zero") {}
00027 };
00028
00029
typedef unsigned int RandomizationParameter;
00030
00031
00032
00033
00034
00035 PolynomialMod2();
00036
00037 PolynomialMod2(
const PolynomialMod2& t);
00038
00039
00040
00041
00042
00043
00044 PolynomialMod2(word value,
unsigned int bitLength=WORD_BITS);
00045
00046
00047 PolynomialMod2(
const byte *encodedPoly,
unsigned int byteCount)
00048 {Decode(encodedPoly, byteCount);}
00049
00050
00051 PolynomialMod2(
BufferedTransformation &encodedPoly,
unsigned int byteCount)
00052 {Decode(encodedPoly, byteCount);}
00053
00054
00055 PolynomialMod2(
RandomNumberGenerator &rng,
unsigned int bitcount)
00056 {Randomize(rng, bitcount);}
00057
00058
00059
static PolynomialMod2 Monomial(
unsigned i);
00060
00061
static PolynomialMod2 Trinomial(
unsigned t0,
unsigned t1,
unsigned t2);
00062
00063
static PolynomialMod2 Pentanomial(
unsigned t0,
unsigned t1,
unsigned t2,
unsigned int t3,
unsigned int t4);
00064
00065
static PolynomialMod2 AllOnes(
unsigned n);
00066
00067
00068
static const PolynomialMod2 &Zero();
00069
00070
static const PolynomialMod2 &One();
00071
00072
00073
00074
00075
00076
00077 unsigned int MinEncodedSize()
const {
return STDMAX(1U, ByteCount());}
00078
00079
00080
00081
00082
00083
unsigned int Encode(byte *output,
unsigned int outputLen)
const;
00084
00085
unsigned int Encode(
BufferedTransformation &bt,
unsigned int outputLen)
const;
00086
00087
00088
void Decode(
const byte *input,
unsigned int inputLen);
00089
00090
00091
void Decode(
BufferedTransformation &bt,
unsigned int inputLen);
00092
00093
00094
void DEREncodeAsOctetString(
BufferedTransformation &bt,
unsigned int length)
const;
00095
00096
void BERDecodeAsOctetString(
BufferedTransformation &bt,
unsigned int length);
00097
00098
00099
00100
00101
00102
unsigned int BitCount() const;
00103
00104
unsigned int ByteCount() const;
00105
00106
unsigned int WordCount() const;
00107
00108
00109 bool GetBit(
unsigned int n)
const {
return GetCoefficient(n)!=0;}
00110
00111 byte GetByte(
unsigned int n)
const;
00112
00113
00114 signed int Degree()
const {
return BitCount()-1;}
00115
00116 unsigned int CoefficientCount()
const {
return BitCount();}
00117
00118 int GetCoefficient(
unsigned int i)
const
00119
{
return (i/WORD_BITS < reg.size()) ? int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
00120
00121 int operator[](
unsigned int i)
const {
return GetCoefficient(i);}
00122
00123
00124
bool IsZero()
const {
return !*
this;}
00125
00126
bool Equals(
const PolynomialMod2 &rhs)
const;
00127
00128
00129
00130
00131
00132 PolynomialMod2& operator=(
const PolynomialMod2& t);
00133
00134 PolynomialMod2& operator&=(
const PolynomialMod2& t);
00135
00136 PolynomialMod2& operator^=(
const PolynomialMod2& t);
00137
00138 PolynomialMod2& operator+=(
const PolynomialMod2& t) {
return *
this ^= t;}
00139
00140 PolynomialMod2& operator-=(
const PolynomialMod2& t) {
return *
this ^= t;}
00141
00142 PolynomialMod2& operator*=(
const PolynomialMod2& t);
00143
00144 PolynomialMod2& operator/=(
const PolynomialMod2& t);
00145
00146 PolynomialMod2& operator%=(
const PolynomialMod2& t);
00147
00148 PolynomialMod2& operator<<=(
unsigned int);
00149
00150 PolynomialMod2& operator>>=(
unsigned int);
00151
00152
00153
void Randomize(
RandomNumberGenerator &rng,
unsigned int bitcount);
00154
00155
00156
void SetBit(
unsigned int i,
int value = 1);
00157
00158
void SetByte(
unsigned int n, byte value);
00159
00160
00161
void SetCoefficient(
unsigned int i,
int value) {SetBit(i, value);}
00162
00163
00164
void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
00165
00166
00167
00168
00169
00170
bool operator!() const;
00171
00172 PolynomialMod2 operator+()
const {
return *
this;}
00173
00174 PolynomialMod2 operator-()
const {
return *
this;}
00175
00176
00177
00178
00179
00180 PolynomialMod2 And(
const PolynomialMod2 &b)
const;
00181
00182 PolynomialMod2 Xor(
const PolynomialMod2 &b)
const;
00183
00184 PolynomialMod2 Plus(
const PolynomialMod2 &b)
const {
return Xor(b);}
00185
00186 PolynomialMod2 Minus(
const PolynomialMod2 &b)
const {
return Xor(b);}
00187
00188 PolynomialMod2 Times(
const PolynomialMod2 &b)
const;
00189
00190 PolynomialMod2 DividedBy(
const PolynomialMod2 &b)
const;
00191
00192 PolynomialMod2 Modulo(
const PolynomialMod2 &b)
const;
00193
00194
00195 PolynomialMod2 operator>>(
unsigned int n)
const;
00196
00197 PolynomialMod2 operator<<(
unsigned int n)
const;
00198
00199
00200
00201
00202
00203
unsigned int Parity() const;
00204
00205
00206
bool IsIrreducible() const;
00207
00208
00209 PolynomialMod2 Doubled()
const {
return Zero();}
00210
00211 PolynomialMod2 Squared() const;
00212
00213
00214 bool IsUnit()
const {
return Equals(One());}
00215
00216 PolynomialMod2 MultiplicativeInverse()
const {
return IsUnit() ? One() : Zero();}
00217
00218
00219
static PolynomialMod2 Gcd(
const PolynomialMod2 &a,
const PolynomialMod2 &n);
00220
00221 PolynomialMod2 InverseMod(
const PolynomialMod2 &) const;
00222
00223
00224 static
void Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d);
00225
00226
00227
00228
00229
00230 friend std::ostream& operator<<(std::ostream& out, const PolynomialMod2 &a);
00231
00232
00233 private:
00234 friend class
GF2NT;
00235
00236
SecWordBlock reg;
00237 };
00238
00239
00240 inline
bool operator==(const CryptoPP::PolynomialMod2 &a, const CryptoPP::PolynomialMod2 &b)
00241 {
return a.Equals(b);}
00242
00243
inline bool operator!=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
00244 {
return !(a==b);}
00245
00246 inline bool operator> (
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
00247 {
return a.Degree() > b.Degree();}
00248
00249 inline bool operator>=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
00250 {
return a.Degree() >= b.Degree();}
00251
00252 inline bool operator< (
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
00253 {
return a.Degree() < b.Degree();}
00254
00255 inline bool operator<=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
00256 {
return a.Degree() <= b.Degree();}
00257
00258
inline CryptoPP::PolynomialMod2 operator&(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.And(b);}
00259
00260
inline CryptoPP::PolynomialMod2 operator^(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Xor(b);}
00261
00262
inline CryptoPP::PolynomialMod2 operator+(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Plus(b);}
00263
00264
inline CryptoPP::PolynomialMod2 operator-(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Minus(b);}
00265
00266
inline CryptoPP::PolynomialMod2 operator*(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Times(b);}
00267
00268
inline CryptoPP::PolynomialMod2 operator/(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.DividedBy(b);}
00269
00270
inline CryptoPP::PolynomialMod2 operator%(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Modulo(b);}
00271
00272
00273
00274 CRYPTOPP_DLL_TEMPLATE_CLASS
AbstractGroup<PolynomialMod2>;
00275 CRYPTOPP_DLL_TEMPLATE_CLASS
AbstractRing<PolynomialMod2>;
00276 CRYPTOPP_DLL_TEMPLATE_CLASS
AbstractEuclideanDomain<PolynomialMod2>;
00277 CRYPTOPP_DLL_TEMPLATE_CLASS
EuclideanDomainOf<PolynomialMod2>;
00278 CRYPTOPP_DLL_TEMPLATE_CLASS
QuotientRing<EuclideanDomainOf<PolynomialMod2> >;
00279
00280
00281 class CRYPTOPP_DLL GF2NP :
public QuotientRing<EuclideanDomainOf<PolynomialMod2> >
00282 {
00283
public:
00284 GF2NP(
const PolynomialMod2 &modulus);
00285
00286
virtual GF2NP * Clone()
const {
return new GF2NP(*
this);}
00287
virtual void DEREncode(
BufferedTransformation &bt)
const
00288
{assert(
false);}
00289
00290
void DEREncodeElement(
BufferedTransformation &out,
const Element &a)
const;
00291
void BERDecodeElement(
BufferedTransformation &in, Element &a)
const;
00292
00293
bool Equal(
const Element &a,
const Element &b)
const
00294
{assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree());
return a.Equals(b);}
00295
00296
bool IsUnit(
const Element &a)
const
00297
{assert(a.Degree() < m_modulus.Degree());
return !!a;}
00298
00299
unsigned int MaxElementBitLength()
const
00300
{
return m;}
00301
00302
unsigned int MaxElementByteLength()
const
00303
{
return BitsToBytes(MaxElementBitLength());}
00304
00305 Element SquareRoot(
const Element &a)
const;
00306
00307 Element HalfTrace(
const Element &a)
const;
00308
00309
00310 Element SolveQuadraticEquation(
const Element &a)
const;
00311
00312
protected:
00313
unsigned int m;
00314 };
00315
00316
00317 class CRYPTOPP_DLL GF2NT :
public GF2NP
00318 {
00319
public:
00320
00321 GF2NT(
unsigned int t0,
unsigned int t1,
unsigned int t2);
00322
00323 GF2NP * Clone()
const {
return new GF2NT(*
this);}
00324
void DEREncode(
BufferedTransformation &bt)
const;
00325
00326
const Element& Multiply(
const Element &a,
const Element &b)
const;
00327
00328
const Element&
Square(
const Element &a)
const
00329
{
return Reduced(a.Squared());}
00330
00331
const Element& MultiplicativeInverse(
const Element &a)
const;
00332
00333
private:
00334
const Element& Reduced(
const Element &a)
const;
00335
00336
unsigned int t0, t1;
00337
mutable PolynomialMod2 result;
00338 };
00339
00340
00341 class CRYPTOPP_DLL GF2NPP :
public GF2NP
00342 {
00343
public:
00344
00345 GF2NPP(
unsigned int t0,
unsigned int t1,
unsigned int t2,
unsigned int t3,
unsigned int t4)
00346 : GF2NP(PolynomialMod2::Pentanomial(t0, t1, t2, t3, t4)), t0(t0), t1(t1), t2(t2), t3(t3) {}
00347
00348 GF2NP * Clone()
const {
return new GF2NPP(*
this);}
00349
void DEREncode(
BufferedTransformation &bt)
const;
00350
00351
private:
00352
unsigned int t0, t1, t2, t3;
00353 };
00354
00355
00356 CRYPTOPP_DLL GF2NP * BERDecodeGF2NP(
BufferedTransformation &bt);
00357
00358 NAMESPACE_END
00359
00360 NAMESPACE_BEGIN(std)
00361 template<> inline
void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
00362 {
00363 a.swap(b);
00364 }
00365 NAMESPACE_END
00366
00367
#endif