diff options
| -rw-r--r-- | aes.cpp | 2 | ||||
| -rw-r--r-- | gf28.cpp | 143 | ||||
| -rw-r--r-- | gf28.h | 37 |
3 files changed, 47 insertions, 135 deletions
@@ -31,7 +31,7 @@ namespace AES{ } for(int i=0;i<256;i++){ - uint8_t inv=(uint8_t)GF28(i).inverse(); + uint8_t inv=GF28::inverse(i); uint8_t res=0; for(int j=0;j<8;j++){ uint8_t bit=((inv>>j)&1)^ @@ -3,117 +3,52 @@ using namespace std; -int GF28::reduce(int v,int m){ - assert(m); - while(true){ - int sh=__builtin_clz(m)-__builtin_clz(v); - if(sh<0)break; - v^=m<<sh; - if(v==0)break; - } - return v; -} - -uint8_t GF28::multiply(uint8_t x,uint8_t y){ - if(x==0||y==0)return 0; - int res=0; - int addend=x; - while(y){ - if(y&1)res^=addend; - addend<<=1; - if(addend&0x100)addend^=modulus; - y>>=1; - } - return res; -} - -GF28::GF28() - :value(0){} - -GF28::GF28(int v) - :value(reduce(v,modulus)){} - -GF28::operator uint8_t() const { - return value; -} - -GF28& GF28::operator+=(GF28 o){ - value^=o.value; - return *this; -} - -GF28& GF28::operator-=(GF28 o){ - value^=o.value; - return *this; -} +namespace GF28 { -GF28& GF28::operator<<=(int n){ - assert(n>=0); - value<<=n; - if(value&0x100)value^=modulus; - return *this; -} - -GF28 GF28::operator+(GF28 o) const { - return GF28(value^o.value); -} + const int modulus=0x11b; -GF28 GF28::operator-(GF28 o) const { - return GF28(value^o.value); -} - -GF28 GF28::operator*(GF28 o) const { - if(value==0||o.value==0)return GF28(0); - GF28 res; - GF28 addend(*this); - while(o.value){ - if(o.value&1)res+=addend; - addend<<=1; - o.value>>=1; + uint8_t reduce(int v,int m){ + assert(v&&m); + while(true){ + int sh=__builtin_clz(m)-__builtin_clz(v); + if(sh<0)break; + v^=m<<sh; + if(v==0)break; + } + return (uint8_t)(unsigned int)v; } - return res; -} -GF28 GF28::operator<<(int n) const { - return GF28(*this)<<=n; -} - -bool GF28::operator==(GF28 o) const { - return value==o.value; -} -GF28 GF28::inverse() const { - if(value==0)return *this; - int x=1,y=0,x2=0,y2=1,r=modulus,r2=value; - while(r2!=0){ - assert(r!=0); - int ex=__builtin_clz(r2)-__builtin_clz(r); - if(ex<0){ - swap(x,x2); - swap(y,y2); - swap(r,r2); - } else { - int xn=x^(x2<<ex); x=x2; x2=xn; - int yn=y^(y2<<ex); y=y2; y2=yn; - int rn=r^(r2<<ex); r=r2; r2=rn; + uint8_t multiply(uint8_t x,uint8_t y){ + if(x==0||y==0)return 0; + int res=0; + int addend=x; + while(y){ + if(y&1)res^=addend; + addend<<=1; + if(addend&0x100)addend^=modulus; + y>>=1; } + return res; } - assert(r==1); - return GF28(y); -} -ostream& operator<<(ostream &os,GF28 p){ - if(os.flags()&ios_base::hex){ - return os<<p.value; - } - if(p.value==0)return os<<'0'; - bool first=true; - for(int m=1<<16,i=16;m!=0;m>>=1,i--){ - if(p.value&m){ - if(!first)os<<'+'; - first=false; - if(i==0)os<<'1'; - else os<<"x^"<<i; + uint8_t inverse(uint8_t value){ + if(value==0)return value; + int x=1,y=0,x2=0,y2=1,r=modulus,r2=value; + while(r2!=0){ + assert(r!=0); + int ex=__builtin_clz(r2)-__builtin_clz(r); + if(ex<0){ + swap(x,x2); + swap(y,y2); + swap(r,r2); + } else { + int xn=x^(x2<<ex); x=x2; x2=xn; + int yn=y^(y2<<ex); y=y2; y2=yn; + int rn=r^(r2<<ex); r=r2; r2=rn; + } } + assert(r==1); + return reduce(y,modulus); } - return os; + } @@ -4,36 +4,13 @@ #include <cstdint> //The GF(2^8) field used in AES +//Elements are represented by unsigned 8-bit ints, as is their nature. +//Since addition in GF(2^8) is more simply written as just '^', only +//multiplication and taking inverses is necessary to implement separately. -class GF28{ - int value; +namespace GF28 { - static int reduce(int v,int m); + uint8_t multiply(uint8_t x,uint8_t y); + uint8_t inverse(uint8_t value); -public: - static const int modulus=0x11b; - - static uint8_t multiply(uint8_t x,uint8_t y); //for when the class is overkill - - GF28(); - explicit GF28(int v); - - explicit operator uint8_t() const; - - GF28& operator+=(GF28 o); - GF28& operator-=(GF28 o); - GF28& operator<<=(int n); //multiplication by x^n - - GF28 operator+(GF28 o) const; - GF28 operator-(GF28 o) const; - GF28 operator*(GF28 o) const; - GF28 operator<<(int n) const; //multiplication by x^n - - bool operator==(GF28 o) const; - - GF28 inverse() const; - - friend std::ostream& operator<<(std::ostream&,GF28); -}; - -std::ostream& operator<<(std::ostream &os,GF28 p); +} |