{-# LANGUAGE CPP #-}
#ifndef MIN_VERSION_integer_gmp
#define MIN_VERSION_integer_gmp(a,b,c) 0
#endif
-- |
-- Module      : Crypto.Number.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
    ( addF2m
    , mulF2m
    , squareF2m
    , modF2m
    , invF2m
    , divF2m
    ) where

import Control.Applicative ((<$>))
import Data.Bits ((.&.),(.|.),xor,shift,testBit)
import Crypto.Number.Basic

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 #-}

-- | Binary polynomial reduction modulo using long division algorithm.
modF2m :: Integer  -- ^ Irreducible binary polynomial
       -> Integer -> Integer
modF2m :: Integer -> Integer -> Integer
modF2m fx :: Integer
fx = Integer -> Integer
go
  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
forall a. Bits a => a -> a -> a
`xor` 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
forall a. Bits a => a -> a -> a
`xor` 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.
--
--     n1 * n2 (in F(2^m))
mulF2m :: BinaryPolynomial  -- ^ Irreducible binary polynomial
       -> Integer -> Integer -> Integer
mulF2m :: Integer -> Integer -> Integer -> Integer
mulF2m fx :: Integer
fx n1 :: Integer
n1 n2 :: Integer
n2 = 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
forall a. Bits a => a -> a -> a
`xor` 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.
-- TODO: This is still slower than @mulF2m@.

-- Multiplication table? C?
squareF2m :: BinaryPolynomial  -- ^ Irreducible binary polynomial
          -> 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
square
{-# INLINE squareF2m #-}

square :: Integer -> Integer
square :: Integer -> Integer
square n1 :: Integer
n1 = Integer -> Int -> Integer
forall t. (Num t, Bits t) => t -> Int -> t
go Integer
n1 Int
ln1
  where
    ln1 :: Int
ln1 = Integer -> Int
log2 Integer
n1
    go :: t -> Int -> t
go n :: t
n s :: Int
s | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = t
n
           | Bool
otherwise = t -> Int -> t
go (t
x t -> t -> t
forall a. Bits a => a -> a -> a
.|. t
y) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1)
      where
        x :: t
x = t -> Int -> t
forall a. Bits a => a -> Int -> a
shift (t -> Int -> t
forall a. Bits a => a -> Int -> a
shift t
n (2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
ln1) Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1)) (2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int
ln1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
s) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 2)
        y :: t
y = t
n t -> t -> t
forall a. Bits a => a -> a -> a
.&. (t -> Int -> t
forall a. Bits a => a -> Int -> a
shift 1 (2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int
ln1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
s) Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1) t -> t -> t
forall a. Num a => a -> a -> a
- 1)
{-# INLINE square #-}

-- | Inversion of @n over F₂m using extended Euclidean algorithm.
--
-- If @n doesn't have an inverse, Nothing is returned.
invF2m :: BinaryPolynomial -- ^ Irreducible binary polynomial
       -> Integer -> Maybe Integer
invF2m :: Integer -> Integer -> Maybe Integer
invF2m _  0 = Maybe Integer
forall a. Maybe a
Nothing
invF2m fx :: Integer
fx n :: Integer
n
    | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
fx   = Maybe Integer
forall a. Maybe a
Nothing
    | Bool
otherwise = Integer -> Integer -> Integer -> Integer -> Maybe Integer
go Integer
n Integer
fx 1 0
    where
      go :: Integer -> Integer -> Integer -> Integer -> Maybe Integer
go u :: Integer
u v :: Integer
v g1 :: Integer
g1 g2 :: Integer
g2
          | Integer
u Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 1    = 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
modF2m Integer
fx Integer
g1
          | Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< 0     = Integer -> Integer -> Integer -> Integer -> Maybe Integer
go Integer
u  (Integer
v  Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
`xor` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift  Integer
u (-Int
j)) Integer
g1 (Integer
g2 Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
`xor` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
g1 (-Int
j))
          | Bool
otherwise = Integer -> Integer -> Integer -> Integer -> Maybe Integer
go (Integer
u  Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
`xor` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
v  Int
j) Integer
v (Integer
g1 Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
`xor` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
g2 Int
j) Integer
g2
        where
          j :: Int
j = Integer -> Int
log2 Integer
u Int -> Int -> Int
forall a. Num a => a -> a -> a
- Integer -> Int
log2 Integer
v
{-# INLINABLE invF2m #-}

-- | Division over F₂m. If the dividend doesn't have an inverse it returns
-- 'Nothing'.
--
-- Compute n1 / n2
divF2m :: BinaryPolynomial  -- ^ Irreducible binary polynomial
       -> Integer  -- ^ Dividend
       -> Integer  -- ^ Quotient
       -> Maybe Integer
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 #-}