-- |
-- 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
    ) where

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

-- | 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 = 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 forall a. Ord a => a -> a -> Bool
< Integer
0 Bool -> Bool -> Bool
|| Integer
i forall a. Ord a => a -> a -> Bool
< Integer
0 = forall a. HasCallStack => [Char] -> a
error [Char]
"modF2m: negative number represent no binary polynomial"
    | Integer
fx forall a. Eq a => a -> a -> Bool
== Integer
0         = forall a. HasCallStack => [Char] -> a
error [Char]
"modF2m: cannot divide by zero polynomial"
    | Integer
fx 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 forall a. Eq a => a -> a -> Bool
== Int
0    = Integer
n Integer -> Integer -> Integer
`addF2m` Integer
fx
             | Int
s forall a. Ord a => a -> a -> Bool
< Int
0     = Integer
n
             | Bool
otherwise = Integer -> Integer
go forall a b. (a -> b) -> a -> b
$ Integer
n Integer -> Integer -> Integer
`addF2m` forall a. Bits a => a -> Int -> a
shift Integer
fx Int
s
                where s :: Int
s = Integer -> Int
log2 Integer
n 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 forall a. Ord a => a -> a -> Bool
< Integer
0
      Bool -> Bool -> Bool
|| Integer
n1 forall a. Ord a => a -> a -> Bool
< Integer
0
      Bool -> Bool -> Bool
|| Integer
n2 forall a. Ord a => a -> a -> Bool
< Integer
0 = forall a. HasCallStack => [Char] -> a
error [Char]
"mulF2m: negative number represent no binary polynomial"
    | Integer
fx forall a. Eq a => a -> a -> Bool
== Integer
0   = forall a. HasCallStack => [Char] -> a
error [Char]
"mulF2m: cannot multiply modulo zero polynomial"
    | Bool
otherwise = Integer -> Integer -> Integer
modF2m Integer
fx forall a b. (a -> b) -> a -> b
$ Integer -> Int -> Integer
go (if Integer
n2 forall a. Integral a => a -> a -> a
`mod` Integer
2 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 forall a. Eq a => a -> a -> Bool
== Int
0  = Integer
n
               | Bool
otherwise = if forall a. Bits a => a -> Int -> Bool
testBit Integer
n2 Int
s
                                then Integer -> Int -> Integer
go (Integer
n Integer -> Integer -> Integer
`addF2m` forall a. Bits a => a -> Int -> a
shift Integer
n1 Int
s) (Int
s forall a. Num a => a -> a -> a
- Int
1)
                                else Integer -> Int -> Integer
go Integer
n (Int
s forall a. Num a => a -> a -> a
- Int
1)
{-# INLINABLE 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 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 forall a. Ord a => a -> a -> Bool
< Integer
0     = forall a. HasCallStack => [Char] -> a
error [Char]
"mulF2m: negative number represent no binary polynomial"
    | Bool
otherwise = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Integer
acc Int
s -> if forall a. Bits a => a -> Int -> Bool
testBit Integer
n Int
s then forall a. Bits a => a -> Int -> a
setBit Integer
acc (Int
2 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 forall a. Ord a => a -> a -> Bool
< Integer
0     = forall a. HasCallStack => [Char] -> a
error [Char]
"powF2m: negative exponents disallowed"
  | Integer
b forall a. Eq a => a -> a -> Bool
== Integer
0    = if Integer
fx forall a. Ord a => a -> a -> Bool
> Integer
1 then Integer
1 else Integer
0
  | 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 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 = forall {t}. (Eq t, Num t) => t -> Integer -> Integer
go (Integer -> Int
log2 Integer
fx 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 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` forall a. Bits a => a -> Int -> a
shift Integer
r1 Int
j, Integer
s1, Integer
s0 Integer -> Integer -> Integer
`addF2m` forall a. Bits a => a -> Int -> a
shift Integer
s1 Int
j, Integer
t1, Integer
t0 Integer -> Integer -> Integer
`addF2m` forall a. Bits a => a -> Int -> a
shift Integer
t1 Int
j)
            where j :: Int
j = forall a. Ord a => a -> a -> a
max Int
0 (Integer -> Int
log2 Integer
r0 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 forall a. Eq a => a -> a -> Bool
== Integer
1 then forall a. a -> Maybe a
Just (Integer -> Integer -> Integer
modF2m Integer
fx Integer
u) else forall a. Maybe a
Nothing
  where
    (Integer
g, Integer
u, Integer
_) = Integer -> Integer -> (Integer, Integer, Integer)
gcdF2m Integer
n Integer
fx
{-# INLINABLE 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 forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Integer -> Integer -> Maybe Integer
invF2m Integer
fx Integer
n2
{-# INLINE divF2m #-}