-- |
-- Module      : Crypto.Math.F2m
-- License     : BSD-style
-- Maintainer  : Danny Navarro <j@dannynavarro.net>
-- Stability   : experimental
-- Portability : Good
--
-- This module provides basic arithmetic operations over F₂m. Performance is
-- not optimal and it doesn't provide protection against timing
-- attacks. The 'm' parameter is implicitly derived from the irreducible
-- polynomial where applicable.
module Crypto.Number.F2m (
    BinaryPolynomial,
    addF2m,
    mulF2m,
    squareF2m',
    squareF2m,
    powF2m,
    modF2m,
    sqrtF2m,
    invF2m,
    divF2m,
    quadraticF2m,
) where

import Crypto.Number.Basic
import Data.Bits (setBit, shift, testBit, unsafeShiftR, xor)
import Data.List (foldl')

-- | Binary Polynomial represented by an integer
type BinaryPolynomial = Integer

-- | Addition over F₂m. This is just a synonym of 'xor'.
addF2m
    :: Integer
    -> Integer
    -> Integer
addF2m :: Integer -> Integer -> Integer
addF2m = Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
xor
{-# INLINE addF2m #-}

-- | Reduction by modulo over F₂m.
--
-- This function is undefined for negative arguments, because their bit
-- representation is platform-dependent. Zero modulus is also prohibited.
modF2m
    :: BinaryPolynomial
    -- ^ Modulus
    -> Integer
    -> Integer
modF2m :: Integer -> Integer -> Integer
modF2m Integer
fx Integer
i
    | Integer
fx Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 Bool -> Bool -> Bool
|| Integer
i Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 =
        [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error [Char]
"modF2m: negative number represent no binary polynomial"
    | Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error [Char]
"modF2m: cannot divide by zero polynomial"
    | Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Integer
0
    | Bool
otherwise = Integer -> Integer
go Integer
i
  where
    lfx :: Int
lfx = Integer -> Int
log2 Integer
fx
    go :: Integer -> Integer
go Integer
n
        | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Integer
n Integer -> Integer -> Integer
`addF2m` Integer
fx
        | Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = Integer
n
        | Bool
otherwise = Integer -> Integer
go (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Integer
n Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
fx Int
s
      where
        s :: Int
s = Integer -> Int
log2 Integer
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
lfx
{-# INLINE modF2m #-}

-- | Multiplication over F₂m.
--
-- This function is undefined for negative arguments, because their bit
-- representation is platform-dependent. Zero modulus is also prohibited.
mulF2m
    :: BinaryPolynomial
    -- ^ Modulus
    -> Integer
    -> Integer
    -> Integer
mulF2m :: Integer -> Integer -> Integer -> Integer
mulF2m Integer
fx Integer
n1 Integer
n2
    | Integer
fx Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0
        Bool -> Bool -> Bool
|| Integer
n1 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0
        Bool -> Bool -> Bool
|| Integer
n2 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 =
        [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error [Char]
"mulF2m: negative number represent no binary polynomial"
    | Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error [Char]
"mulF2m: cannot multiply modulo zero polynomial"
    | Bool
otherwise = Integer -> Integer -> Integer
modF2m Integer
fx (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Integer -> Int -> Integer
go (if Integer
n2 Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
2 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then Integer
n1 else Integer
0) (Integer -> Int
log2 Integer
n2)
  where
    go :: Integer -> Int -> Integer
go Integer
n Int
s
        | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 = Integer
n
        | Bool
otherwise =
            if Integer -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Integer
n2 Int
s
                then Integer -> Int -> Integer
go (Integer
n Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
n1 Int
s) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
                else Integer -> Int -> Integer
go Integer
n (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
{-# INLINEABLE mulF2m #-}

-- | Squaring over F₂m.
--
-- This function is undefined for negative arguments, because their bit
-- representation is platform-dependent. Zero modulus is also prohibited.
squareF2m
    :: BinaryPolynomial
    -- ^ Modulus
    -> Integer
    -> Integer
squareF2m :: Integer -> Integer -> Integer
squareF2m Integer
fx = Integer -> Integer -> Integer
modF2m Integer
fx (Integer -> Integer) -> (Integer -> Integer) -> Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
squareF2m'
{-# INLINE squareF2m #-}

-- | Squaring over F₂m without reduction by modulo.
--
-- The implementation utilizes the fact that for binary polynomial S(x) we have
-- S(x)^2 = S(x^2). In other words, insert a zero bit between every bits of argument: 1101 -> 1010001.
--
-- This function is undefined for negative arguments, because their bit
-- representation is platform-dependent.
squareF2m'
    :: Integer
    -> Integer
squareF2m' :: Integer -> Integer
squareF2m' Integer
n
    | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error [Char]
"mulF2m: negative number represent no binary polynomial"
    | Bool
otherwise =
        (Integer -> Int -> Integer) -> Integer -> [Int] -> Integer
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'
            (\Integer
acc Int
s -> if Integer -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Integer
n Int
s then Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
setBit Integer
acc (Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
s) else Integer
acc)
            Integer
0
            [Int
0 .. Integer -> Int
log2 Integer
n]
{-# INLINE squareF2m' #-}

-- | Exponentiation in F₂m by computing @a^b mod fx@.
--
-- This implements an exponentiation by squaring based solution. It inherits the
-- same restrictions as 'squareF2m'. Negative exponents are disallowed.
powF2m
    :: BinaryPolynomial
    -- ^ Modulus
    -> Integer
    -- ^ a
    -> Integer
    -- ^ b
    -> Integer
powF2m :: Integer -> Integer -> Integer -> Integer
powF2m Integer
fx Integer
a Integer
b
    | Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error [Char]
"powF2m: negative exponents disallowed"
    | Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = if Integer
fx Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
1 then Integer
1 else Integer
0
    | Integer -> Bool
forall a. Integral a => a -> Bool
even Integer
b = Integer -> Integer -> Integer
squareF2m Integer
fx Integer
x
    | Bool
otherwise = Integer -> Integer -> Integer -> Integer
mulF2m Integer
fx Integer
a (Integer -> Integer
squareF2m' Integer
x)
  where
    x :: Integer
x = Integer -> Integer -> Integer -> Integer
powF2m Integer
fx Integer
a (Integer
b Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
2)

-- | Square rooot in F₂m.
--
-- We exploit the fact that @a^(2^m) = a@, or in particular, @a^(2^m - 1) = 1@
-- from a classical result by Lagrange. Thus the square root is simply @a^(2^(m
-- - 1))@.
sqrtF2m
    :: BinaryPolynomial
    -- ^ Modulus
    -> Integer
    -- ^ a
    -> Integer
sqrtF2m :: Integer -> Integer -> Integer
sqrtF2m Integer
fx Integer
a = Int -> Integer -> Integer
forall {t}. (Eq t, Num t) => t -> Integer -> Integer
go (Integer -> Int
log2 Integer
fx Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Integer
a
  where
    go :: t -> Integer -> Integer
go t
0 Integer
x = Integer
x
    go t
n Integer
x = t -> Integer -> Integer
go (t
n t -> t -> t
forall a. Num a => a -> a -> a
- t
1) (Integer -> Integer -> Integer
squareF2m Integer
fx Integer
x)

-- | Extended GCD algorithm for polynomials. For @a@ and @b@ returns @(g, u, v)@ such that @a * u + b * v == g@.
--
-- Reference: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B.C3.A9zout.27s_identity_and_extended_GCD_algorithm
gcdF2m
    :: Integer
    -> Integer
    -> (Integer, Integer, Integer)
gcdF2m :: Integer -> Integer -> (Integer, Integer, Integer)
gcdF2m Integer
a Integer
b = (Integer, Integer, Integer, Integer, Integer, Integer)
-> (Integer, Integer, Integer)
go (Integer
a, Integer
b, Integer
1, Integer
0, Integer
0, Integer
1)
  where
    go :: (Integer, Integer, Integer, Integer, Integer, Integer)
-> (Integer, Integer, Integer)
go (Integer
g, Integer
0, Integer
u, Integer
_, Integer
v, Integer
_) =
        (Integer
g, Integer
u, Integer
v)
    go (Integer
r0, Integer
r1, Integer
s0, Integer
s1, Integer
t0, Integer
t1) =
        (Integer, Integer, Integer, Integer, Integer, Integer)
-> (Integer, Integer, Integer)
go
            ( Integer
r1
            , Integer
r0 Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
r1 Int
j
            , Integer
s1
            , Integer
s0 Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
s1 Int
j
            , Integer
t1
            , Integer
t0 Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
t1 Int
j
            )
      where
        j :: Int
j = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Integer -> Int
log2 Integer
r0 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Integer -> Int
log2 Integer
r1)

-- | Modular inversion over F₂m.
-- If @n@ doesn't have an inverse, 'Nothing' is returned.
--
-- This function is undefined for negative arguments, because their bit
-- representation is platform-dependent. Zero modulus is also prohibited.
invF2m
    :: BinaryPolynomial
    -- ^ Modulus
    -> Integer
    -> Maybe Integer
invF2m :: Integer -> Integer -> Maybe Integer
invF2m Integer
fx Integer
n = if Integer
g Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Integer -> Integer -> Integer
modF2m Integer
fx Integer
u) else Maybe Integer
forall a. Maybe a
Nothing
  where
    (Integer
g, Integer
u, Integer
_) = Integer -> Integer -> (Integer, Integer, Integer)
gcdF2m Integer
n Integer
fx
{-# INLINEABLE invF2m #-}

-- | Division over F₂m. If the dividend doesn't have an inverse it returns
-- 'Nothing'.
--
-- This function is undefined for negative arguments, because their bit
-- representation is platform-dependent. Zero modulus is also prohibited.
divF2m
    :: BinaryPolynomial
    -- ^ Modulus
    -> Integer
    -- ^ Dividend
    -> Integer
    -- ^ Divisor
    -> Maybe Integer
    -- ^ Quotient
divF2m :: Integer -> Integer -> Integer -> Maybe Integer
divF2m Integer
fx Integer
n1 Integer
n2 = Integer -> Integer -> Integer -> Integer
mulF2m Integer
fx Integer
n1 (Integer -> Integer) -> Maybe Integer -> Maybe Integer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Integer -> Integer -> Maybe Integer
invF2m Integer
fx Integer
n2
{-# INLINE divF2m #-}

traceF2m :: BinaryPolynomial -> Integer -> Integer
traceF2m :: Integer -> Integer -> Integer
traceF2m Integer
fx = (Integer -> Integer -> Integer) -> Integer -> [Integer] -> Integer
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Integer -> Integer -> Integer
addF2m Integer
0 ([Integer] -> Integer)
-> (Integer -> [Integer]) -> Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [Integer] -> [Integer]
forall a. Int -> [a] -> [a]
take (Integer -> Int
log2 Integer
fx) ([Integer] -> [Integer])
-> (Integer -> [Integer]) -> Integer -> [Integer]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Integer -> Integer) -> Integer -> [Integer]
forall a. (a -> a) -> a -> [a]
iterate (Integer -> Integer -> Integer
squareF2m Integer
fx)
{-# INLINE traceF2m #-}

halfTraceF2m :: BinaryPolynomial -> Integer -> Integer
halfTraceF2m :: Integer -> Integer -> Integer
halfTraceF2m Integer
fx =
    (Integer -> Integer -> Integer) -> Integer -> [Integer] -> Integer
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Integer -> Integer -> Integer
addF2m Integer
0
        ([Integer] -> Integer)
-> (Integer -> [Integer]) -> Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [Integer] -> [Integer]
forall a. Int -> [a] -> [a]
take (Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Integer -> Int
log2 Integer
fx Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int
1)
        ([Integer] -> [Integer])
-> (Integer -> [Integer]) -> Integer -> [Integer]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Integer -> Integer) -> Integer -> [Integer]
forall a. (a -> a) -> a -> [a]
iterate (Integer -> Integer -> Integer
squareF2m Integer
fx (Integer -> Integer) -> (Integer -> Integer) -> Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer -> Integer
squareF2m Integer
fx)
{-# INLINE halfTraceF2m #-}

-- | Solve a quadratic equation of the form @x^2 + x = a@ in F₂m.
quadraticF2m :: BinaryPolynomial -> Integer -> Maybe Integer
quadraticF2m :: Integer -> Integer -> Maybe Integer
quadraticF2m Integer
fx Integer
a
    | Integer -> Integer -> Integer
traceF2m Integer
fx Integer
a Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Integer -> Maybe Integer) -> Integer -> Maybe Integer
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Integer
halfTraceF2m Integer
fx Integer
a
    | Bool
otherwise = Maybe Integer
forall a. Maybe a
Nothing
{-# INLINEABLE quadraticF2m #-}