-- |
-- 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
    , modF2m
    , 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 = 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 fx :: Integer
fx i :: Integer
i
    | Integer
fx Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0 Bool -> Bool -> Bool
|| Integer
i Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "modF2m: negative number represent no binary polynomial"
    | Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 0         = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "modF2m: cannot divide by zero polynomial"
    | Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 1         = 0
    | Bool
otherwise       = Integer -> Integer
go Integer
i
      where
        lfx :: Int
lfx = Integer -> Int
log2 Integer
fx
        go :: Integer -> Integer
go n :: Integer
n | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0    = Integer
n Integer -> Integer -> Integer
`addF2m` Integer
fx
             | Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< 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 fx :: Integer
fx n1 :: Integer
n1 n2 :: Integer
n2
    |    Integer
fx Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0
      Bool -> Bool -> Bool
|| Integer
n1 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0
      Bool -> Bool -> Bool
|| Integer
n2 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "mulF2m: negative number represent no binary binary polynomial"
    | Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 0   = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "modF2m: 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` 2 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 1 then Integer
n1 else 0) (Integer -> Int
log2 Integer
n2)
      where
        go :: Integer -> Int -> Integer
go n :: Integer
n s :: Int
s | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 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
- 1)
                                else Integer -> Int -> Integer
go Integer
n (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- 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 fx :: 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' n :: Integer
n
    | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0     = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "mulF2m: negative number represent no binary binary polynomial"
    | Bool
otherwise = (Integer -> Int -> Integer) -> Integer -> [Int] -> Integer
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\acc :: Integer
acc s :: 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 (2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
s) else Integer
acc) 0 [0 .. Integer -> Int
log2 Integer
n]
{-# INLINE squareF2m' #-}

-- | 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 a :: Integer
a b :: Integer
b = (Integer, Integer, Integer, Integer, Integer, Integer)
-> (Integer, Integer, Integer)
go (Integer
a, Integer
b, 1, 0, 0, 1)
  where
    go :: (Integer, Integer, Integer, Integer, Integer, Integer)
-> (Integer, Integer, Integer)
go (g :: Integer
g, 0, u :: Integer
u, _, v :: Integer
v, _)
        = (Integer
g, Integer
u, Integer
v)
    go (r0 :: Integer
r0, r1 :: Integer
r1, s0 :: Integer
s0, s1 :: Integer
s1, t0 :: Integer
t0, t1 :: 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 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 fx :: Integer
fx n :: Integer
n = if Integer
g Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 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
    (g :: Integer
g, u :: Integer
u, _) = 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 fx :: Integer
fx n1 :: Integer
n1 n2 :: 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 #-}