sara matheu / Mbed 2 deprecated cifrado_ecc

cifrado con ecc

Dependencies:   mbed

FiniteFieldElement.hpp@0:71704ec698ca, 2015-02-20 (annotated)

Committer:
saranieves92
Date:
Fri Feb 20 18:18:19 2015 +0000
Revision:
0:71704ec698ca
cifrado que va en linux

Who changed what in which revision?

UserRevisionLine numberNew contents of line
saranieves92 0:71704ec698ca 1
saranieves92 0:71704ec698ca 2
saranieves92 0:71704ec698ca 3 namespace Cryptography
saranieves92 0:71704ec698ca 4 {
saranieves92 0:71704ec698ca 5 // helper functions
saranieves92 0:71704ec698ca 6 namespace detail
saranieves92 0:71704ec698ca 7 {
saranieves92 0:71704ec698ca 8 //From Knuth; Extended GCD gives g = a*u + b*v
saranieves92 0:71704ec698ca 9 int EGCD(int a, int b, int& u, int &v)
saranieves92 0:71704ec698ca 10 {
saranieves92 0:71704ec698ca 11 u = 1;
saranieves92 0:71704ec698ca 12 v = 0;
saranieves92 0:71704ec698ca 13 int g = a;
saranieves92 0:71704ec698ca 14 int u1 = 0;
saranieves92 0:71704ec698ca 15 int v1 = 1;
saranieves92 0:71704ec698ca 16 int g1 = b;
saranieves92 0:71704ec698ca 17 while (g1 != 0)
saranieves92 0:71704ec698ca 18 {
saranieves92 0:71704ec698ca 19 int q = g/g1; // Integer divide
saranieves92 0:71704ec698ca 20 int t1 = u - q*u1;
saranieves92 0:71704ec698ca 21 int t2 = v - q*v1;
saranieves92 0:71704ec698ca 22 int t3 = g - q*g1;
saranieves92 0:71704ec698ca 23 u = u1; v = v1; g = g1;
saranieves92 0:71704ec698ca 24 u1 = t1; v1 = t2; g1 = t3;
saranieves92 0:71704ec698ca 25 }
saranieves92 0:71704ec698ca 26
saranieves92 0:71704ec698ca 27 return g;
saranieves92 0:71704ec698ca 28 }
saranieves92 0:71704ec698ca 29
saranieves92 0:71704ec698ca 30 int InvMod(int x, int n) // Solve linear congruence equation x * z == 1 (mod n) for z
saranieves92 0:71704ec698ca 31 {
saranieves92 0:71704ec698ca 32 //n = Abs(n);
saranieves92 0:71704ec698ca 33 x = x % n; // % is the remainder function, 0 <= x % n < |n|
saranieves92 0:71704ec698ca 34 int u,v,g,z;
saranieves92 0:71704ec698ca 35 g = EGCD(x, n, u,v);
saranieves92 0:71704ec698ca 36 if (g != 1)
saranieves92 0:71704ec698ca 37 {
saranieves92 0:71704ec698ca 38 // x and n have to be relative prime for there to exist an x^-1 mod n
saranieves92 0:71704ec698ca 39 z = 0;
saranieves92 0:71704ec698ca 40 }
saranieves92 0:71704ec698ca 41 else
saranieves92 0:71704ec698ca 42 {
saranieves92 0:71704ec698ca 43 z = u % n;
saranieves92 0:71704ec698ca 44 }
saranieves92 0:71704ec698ca 45 return z;
saranieves92 0:71704ec698ca 46 }
saranieves92 0:71704ec698ca 47 }
saranieves92 0:71704ec698ca 48
saranieves92 0:71704ec698ca 49 /*
saranieves92 0:71704ec698ca 50 An element in a Galois field FP
saranieves92 0:71704ec698ca 51 Adapted for the specific behaviour of the "mod" function where (-n) mod m returns a negative number
saranieves92 0:71704ec698ca 52 Allows basic arithmetic operations between elements:
saranieves92 0:71704ec698ca 53 +,-,/,scalar multiply
saranieves92 0:71704ec698ca 54
saranieves92 0:71704ec698ca 55 The template argument P is the order of the field
saranieves92 0:71704ec698ca 56 */
saranieves92 0:71704ec698ca 57 template<int P>
saranieves92 0:71704ec698ca 58 class FiniteFieldElement
saranieves92 0:71704ec698ca 59 {
saranieves92 0:71704ec698ca 60 int i_;
saranieves92 0:71704ec698ca 61
saranieves92 0:71704ec698ca 62 void assign(int i)
saranieves92 0:71704ec698ca 63 {
saranieves92 0:71704ec698ca 64 i_ = i;
saranieves92 0:71704ec698ca 65 if ( i<0 )
saranieves92 0:71704ec698ca 66 {
saranieves92 0:71704ec698ca 67 // ensure (-i) mod p correct behaviour
saranieves92 0:71704ec698ca 68 // the (i%P) term is to ensure that i is in the correct range before normalizing
saranieves92 0:71704ec698ca 69 i_ = (i%P) + 2*P;
saranieves92 0:71704ec698ca 70 }
saranieves92 0:71704ec698ca 71
saranieves92 0:71704ec698ca 72 i_ %= P;
saranieves92 0:71704ec698ca 73 }
saranieves92 0:71704ec698ca 74
saranieves92 0:71704ec698ca 75 public:
saranieves92 0:71704ec698ca 76 // ctor
saranieves92 0:71704ec698ca 77 FiniteFieldElement()
saranieves92 0:71704ec698ca 78 : i_(0)
saranieves92 0:71704ec698ca 79 {}
saranieves92 0:71704ec698ca 80 // ctor
saranieves92 0:71704ec698ca 81 explicit FiniteFieldElement(int i)
saranieves92 0:71704ec698ca 82 {
saranieves92 0:71704ec698ca 83 assign(i);
saranieves92 0:71704ec698ca 84 }
saranieves92 0:71704ec698ca 85 // copy ctor
saranieves92 0:71704ec698ca 86 FiniteFieldElement(const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 87 : i_(rhs.i_)
saranieves92 0:71704ec698ca 88 {
saranieves92 0:71704ec698ca 89 }
saranieves92 0:71704ec698ca 90
saranieves92 0:71704ec698ca 91 // access "raw" integer
saranieves92 0:71704ec698ca 92 int i() const { return i_; }
saranieves92 0:71704ec698ca 93 // negate
saranieves92 0:71704ec698ca 94 FiniteFieldElement operator-() const
saranieves92 0:71704ec698ca 95 {
saranieves92 0:71704ec698ca 96 return FiniteFieldElement(-i_);
saranieves92 0:71704ec698ca 97 }
saranieves92 0:71704ec698ca 98 // assign from integer
saranieves92 0:71704ec698ca 99 FiniteFieldElement& operator=(int i)
saranieves92 0:71704ec698ca 100 {
saranieves92 0:71704ec698ca 101 assign(i);
saranieves92 0:71704ec698ca 102 return *this;
saranieves92 0:71704ec698ca 103 }
saranieves92 0:71704ec698ca 104 // assign from field element
saranieves92 0:71704ec698ca 105 FiniteFieldElement<P>& operator=(const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 106 {
saranieves92 0:71704ec698ca 107 i_ = rhs.i_;
saranieves92 0:71704ec698ca 108 return *this;
saranieves92 0:71704ec698ca 109 }
saranieves92 0:71704ec698ca 110 // *=
saranieves92 0:71704ec698ca 111 FiniteFieldElement<P>& operator*=(const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 112 {
saranieves92 0:71704ec698ca 113 i_ = (i_*rhs.i_) % P;
saranieves92 0:71704ec698ca 114 return *this;
saranieves92 0:71704ec698ca 115 }
saranieves92 0:71704ec698ca 116 // ==
saranieves92 0:71704ec698ca 117 friend bool operator==(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 118 {
saranieves92 0:71704ec698ca 119 return (lhs.i_ == rhs.i_);
saranieves92 0:71704ec698ca 120 }
saranieves92 0:71704ec698ca 121 // == int
saranieves92 0:71704ec698ca 122 friend bool operator==(const FiniteFieldElement<P>& lhs, int rhs)
saranieves92 0:71704ec698ca 123 {
saranieves92 0:71704ec698ca 124 return (lhs.i_ == rhs);
saranieves92 0:71704ec698ca 125 }
saranieves92 0:71704ec698ca 126 // !=
saranieves92 0:71704ec698ca 127 friend bool operator!=(const FiniteFieldElement<P>& lhs, int rhs)
saranieves92 0:71704ec698ca 128 {
saranieves92 0:71704ec698ca 129 return (lhs.i_ != rhs);
saranieves92 0:71704ec698ca 130 }
saranieves92 0:71704ec698ca 131 // a / b
saranieves92 0:71704ec698ca 132 friend FiniteFieldElement<P> operator/(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 133 {
saranieves92 0:71704ec698ca 134 return FiniteFieldElement<P>( lhs.i_ * detail::InvMod(rhs.i_,P));
saranieves92 0:71704ec698ca 135 }
saranieves92 0:71704ec698ca 136 // a + b
saranieves92 0:71704ec698ca 137 friend FiniteFieldElement<P> operator+(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 138 {
saranieves92 0:71704ec698ca 139 return FiniteFieldElement<P>( lhs.i_ + rhs.i_);
saranieves92 0:71704ec698ca 140 }
saranieves92 0:71704ec698ca 141 // a - b
saranieves92 0:71704ec698ca 142 friend FiniteFieldElement<P> operator-(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 143 {
saranieves92 0:71704ec698ca 144 return FiniteFieldElement<P>( lhs.i_ - rhs.i_);
saranieves92 0:71704ec698ca 145 }
saranieves92 0:71704ec698ca 146 // a + int
saranieves92 0:71704ec698ca 147 friend FiniteFieldElement<P> operator+(const FiniteFieldElement<P>& lhs, int i)
saranieves92 0:71704ec698ca 148 {
saranieves92 0:71704ec698ca 149 return FiniteFieldElement<P>( lhs.i_+i);
saranieves92 0:71704ec698ca 150 }
saranieves92 0:71704ec698ca 151 // int + a
saranieves92 0:71704ec698ca 152 friend FiniteFieldElement<P> operator+(int i, const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 153 {
saranieves92 0:71704ec698ca 154 return FiniteFieldElement<P>( rhs.i_+i);
saranieves92 0:71704ec698ca 155 }
saranieves92 0:71704ec698ca 156 // int * a
saranieves92 0:71704ec698ca 157 friend FiniteFieldElement<P> operator*(int n, const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 158 {
saranieves92 0:71704ec698ca 159 return FiniteFieldElement<P>( n*rhs.i_);
saranieves92 0:71704ec698ca 160 }
saranieves92 0:71704ec698ca 161 // a * b
saranieves92 0:71704ec698ca 162 friend FiniteFieldElement<P> operator*(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
saranieves92 0:71704ec698ca 163 {
saranieves92 0:71704ec698ca 164 return FiniteFieldElement<P>( lhs.i_ * rhs.i_);
saranieves92 0:71704ec698ca 165 }
saranieves92 0:71704ec698ca 166 // ostream handler
saranieves92 0:71704ec698ca 167 template<int T>
saranieves92 0:71704ec698ca 168 friend ostream& operator<<(ostream& os, const FiniteFieldElement<T>& g)
saranieves92 0:71704ec698ca 169 {
saranieves92 0:71704ec698ca 170 return os << g.i_;
saranieves92 0:71704ec698ca 171 }
saranieves92 0:71704ec698ca 172 };
saranieves92 0:71704ec698ca 173 }
saranieves92 0:71704ec698ca 174
saranieves92 0:71704ec698ca 175