aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--aes.cpp2
-rw-r--r--gf28.cpp143
-rw-r--r--gf28.h37
3 files changed, 47 insertions, 135 deletions
diff --git a/aes.cpp b/aes.cpp
index f36a69f..6d9163d 100644
--- a/aes.cpp
+++ b/aes.cpp
@@ -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)^
diff --git a/gf28.cpp b/gf28.cpp
index 9513818..fbf7daa 100644
--- a/gf28.cpp
+++ b/gf28.cpp
@@ -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;
+
}
diff --git a/gf28.h b/gf28.h
index 194cd57..2f3401b 100644
--- a/gf28.h
+++ b/gf28.h
@@ -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);
+}