Finite Field Arithmetic
for Cryptography

module gf2_8_mult (
  input  logic [7:0] a, b,
  output logic [7:0] p
);
  // AES irreducible polynomial: x^8 + x^4 + x^3 + x + 1
  localparam [8:0] POLY = 9'h11B;
  logic [7:0] partial [8];

  // Bit-serial "Russian peasant" multiply
  always_comb begin
    partial[0] = a;
    for (int i = 0; i < 8; i++) begin
      if (i == 0)
        p = b[0] ? a : 8'h00;
      else
        p = p ^ (b[i] ? partial[i] : 8'h00);

      // xtime: shift left, reduce if MSB was set
      if (i < 7)
        partial[i+1] = {partial[i][6:0], 1'b0}
                      ^ (partial[i][7] ? POLY[7:0] : 8'h00);
    end
  end
endmodule

module mod_add #(parameter WIDTH = 256)(
  input  logic [WIDTH-1:0] a, b, p,
  output logic [WIDTH-1:0] sum
);
  logic [WIDTH:0] temp;  // 1 extra bit for overflow
  always_comb begin
    temp = a + b;
    sum  = (temp >= {1'b0, p}) ? temp - p
                               : temp[WIDTH-1:0];
  end
endmodule

module mod_sub #(parameter WIDTH = 256)(
  input  logic [WIDTH-1:0] a, b, p,
  output logic [WIDTH-1:0] diff
);
  always_comb begin
    if (a >= b)
      diff = a - b;
    else
      diff = p - (b - a);  // wrap around via p
  end
endmodule

class GF2_8:
    """Galois Field GF(2^8) with AES polynomial."""
    POLY = 0x11B  # x^8 + x^4 + x^3 + x + 1

    def __init__(self, val):
        self.val = val & 0xFF

    def __add__(self, other):        # Addition = XOR
        return GF2_8(self.val ^ other.val)

    def __mul__(self, other):        # Russian peasant multiply
        a, b, p = self.val, other.val, 0
        for _ in range(8):
            if b & 1:  p ^= a
            hi = a & 0x80
            a = (a << 1) & 0xFF
            if hi:     a ^= self.POLY & 0xFF
            b >>= 1
        return GF2_8(p)

    def inverse(self):               # Fermat: a^(2^8 - 2) = a^254
        r = GF2_8(1)
        base = GF2_8(self.val)
        for bit in bin(254)[2:]:
            r = r * r
            if bit == '1':  r = r * base
        return r

# ── Usage ──
a, b = GF2_8(0x57), GF2_8(0x83)
print(f"0x57 * 0x83 = 0x{(a * b).val:02X}")       # 0xC1
print(f"inv(0x57)   = 0x{a.inverse().val:02X}")     # 0xFE
print(f"0x57 * inv  = 0x{(a * a.inverse()).val:02X}") # 0x01 ✓

class GFp:
    """Prime field GF(p) arithmetic."""
    def __init__(self, val, p):
        self.val = val % p
        self.p = p

    def __add__(self, o):  return GFp(self.val + o.val, self.p)
    def __sub__(self, o):  return GFp(self.val - o.val, self.p)
    def __mul__(self, o):  return GFp(self.val * o.val, self.p)
    def __truediv__(self, o): return self * o.inverse()
    def __eq__(self, o):   return self.val == o.val
    def __repr__(self):    return f"GFp({self.val})"

    def inverse(self):     # Fermat's little theorem
        return GFp(pow(self.val, self.p - 2, self.p), self.p)

# ── Curve25519 prime field ──
p25519 = 2**255 - 19
a = GFp(42, p25519)
b = GFp(17, p25519)
assert a * b / a == b          # field division works ✓
assert a * a.inverse() == GFp(1, p25519)  # inverse ✓

# ── P-256 prime field ──
p256 = 2**256 - 2**224 + 2**192 + 2**96 - 1
x = GFp(123456789, p256)
assert x * x.inverse() == GFp(1, p256)    # ✓