-----------------------------------------------------------------------------
-- |
-- Module      :  Crypto.Fi
-- Copyright   :  (c) Marcel Fourné 20[14..]
-- License     :  BSD3
-- Maintainer  :  Marcel Fourné (haskell@marcelfourne.de)
-- Stability   :  beta
-- Portability :  Good
--
-- This is a thin wrapper around Integer to ease transition toward FPrime
-- WARNING! Re Timing-Attacks: This backend is not fully timing attack resistant.
-- 
-----------------------------------------------------------------------------

{-# OPTIONS_GHC -O2 -feager-blackholing #-}
{-# LANGUAGE Safe, BangPatterns, NoImplicitPrelude #-}

module Crypto.Fi ( FPrime
                 , eq
                 , add
                 , addr
                 , sub
                 , subr
                 , neg
                 , shift
                 , mul
                 , mulr
                 , redc
                 , square
                 , pow
                 , inv
                 , fromInteger
                 , toInteger
                 , condBit
                 )
       where

import safe Prelude ((==),Integer,Int,Bool(),($),(+),(-),(*),(^),mod,otherwise,(<))
import safe qualified Prelude as P (fromInteger,toInteger)
import safe qualified Data.Bits as B (Bits(..),shift,(.&.))
import safe Crypto.Common (log2len)

-- | a simple wrapper to ease transition
type FPrime = Integer

-- | most trivial (==) wrapper
eq :: FPrime -> FPrime -> Bool
eq :: FPrime -> FPrime -> Bool
eq !FPrime
a !FPrime
b = FPrime
a forall a. Eq a => a -> a -> Bool
== FPrime
b
{-# INLINABLE eq #-}

-- | (+) in the field
add :: FPrime -> FPrime -> FPrime
add :: FPrime -> FPrime -> FPrime
add !FPrime
a !FPrime
b = FPrime
a forall a. Num a => a -> a -> a
+ FPrime
b
{-# INLINABLE add #-}

-- | (+) in the field
addr :: FPrime -> FPrime -> FPrime -> FPrime
addr :: FPrime -> FPrime -> FPrime -> FPrime
addr !FPrime
p !FPrime
a !FPrime
b = FPrime -> FPrime -> FPrime
redc FPrime
p forall a b. (a -> b) -> a -> b
$ FPrime
a forall a. Num a => a -> a -> a
+ FPrime
b
{-# INLINABLE addr #-}

-- | (-) in the field
sub :: FPrime -> FPrime -> FPrime
sub :: FPrime -> FPrime -> FPrime
sub !FPrime
a !FPrime
b = FPrime
a forall a. Num a => a -> a -> a
- FPrime
b
{-# INLINABLE sub #-}

-- | (-) in the field
subr :: FPrime -> FPrime -> FPrime -> FPrime
subr :: FPrime -> FPrime -> FPrime -> FPrime
subr !FPrime
p !FPrime
a !FPrime
b = FPrime -> FPrime -> FPrime
redc FPrime
p (FPrime
a forall a. Num a => a -> a -> a
- FPrime
b)
{-# INLINABLE subr #-}

-- | negation in the field
neg :: FPrime -> FPrime -> FPrime
neg :: FPrime -> FPrime -> FPrime
neg !FPrime
p !FPrime
a = FPrime -> FPrime -> FPrime
redc FPrime
p (-FPrime
a)
{-# INLINABLE neg #-}

-- | bitshift wrapper
shift :: FPrime -> Int -> FPrime
shift :: FPrime -> Int -> FPrime
shift !FPrime
a !Int
b = forall a. Bits a => a -> Int -> a
B.shift FPrime
a Int
b

-- | modular reduction, a simple wrapper around mod
redc :: FPrime -> FPrime -> FPrime
redc :: FPrime -> FPrime -> FPrime
redc !FPrime
p !FPrime
a = FPrime
a forall a. Integral a => a -> a -> a
`mod` FPrime
p
{-# INLINABLE redc #-}

-- | field multiplication, a * b
mul :: FPrime -> FPrime -> FPrime
mul :: FPrime -> FPrime -> FPrime
mul !FPrime
a !FPrime
b = FPrime
a forall a. Num a => a -> a -> a
* FPrime
b
{-# INLINABLE mul #-}

-- | field multiplication, a * b `mod` p
mulr :: FPrime -> FPrime -> FPrime -> FPrime
mulr :: FPrime -> FPrime -> FPrime -> FPrime
mulr !FPrime
p !FPrime
a !FPrime
b = FPrime -> FPrime -> FPrime
redc FPrime
p forall a b. (a -> b) -> a -> b
$ FPrime
a forall a. Num a => a -> a -> a
* FPrime
b
{-# INLINABLE mulr #-}

-- | simple squaring in the field
square :: FPrime -> FPrime -> FPrime
square :: FPrime -> FPrime -> FPrime
square !FPrime
p !FPrime
a = FPrime -> FPrime -> FPrime
redc FPrime
p (FPrime
a forall a b. (Num a, Integral b) => a -> b -> a
^ (Int
2::Int))
{-# INLINABLE square #-}

-- | the power function in the field, for 1>= k < p
pow :: FPrime -> FPrime -> Integer -> FPrime
{-
pow !p !a !k = let binlog = log2len k
                   ex p1 p2 i
                     | i < 0 = p1
                     | not (B.testBit k i) = redc p $ ex (square p p1)  (mulr p p1 p2) (i - 1)
                     | otherwise           = redc p $ ex (mulr p p1 p2) (square p p2)  (i - 1)
               in redc p $ ex a (square p a) (binlog - 2)
-- -}
-- {-
pow :: FPrime -> FPrime -> FPrime -> FPrime
pow !FPrime
p !FPrime
a' !FPrime
k = let a :: FPrime
a = FPrime -> FPrime -> FPrime
redc FPrime
p FPrime
a'
                    binlog :: Int
binlog = FPrime -> Int
log2len FPrime
a
                    alleeins :: FPrime
alleeins = Int -> FPrime -> FPrime
fromInteger Int
binlog (FPrime
2forall a b. (Num a, Integral b) => a -> b -> a
^Int
binlog forall a. Num a => a -> a -> a
- FPrime
1)
                    eins :: FPrime
eins = Int -> FPrime -> FPrime
fromInteger Int
binlog FPrime
1
                    ex :: FPrime -> Int -> FPrime
ex FPrime
erg Int
i
                      | Int
i forall a. Ord a => a -> a -> Bool
< Int
0 = FPrime
erg
                      | Bool
otherwise =
                          let s :: FPrime
s = FPrime -> Int -> FPrime
condBit FPrime
k Int
i
                              pat :: FPrime
pat = FPrime -> FPrime -> FPrime
mul FPrime
alleeins FPrime
s
                              invpat :: FPrime
invpat = FPrime -> FPrime -> FPrime
mul FPrime
alleeins (FPrime -> FPrime -> FPrime
sub FPrime
eins FPrime
s)
                          in FPrime -> FPrime -> FPrime
redc FPrime
p forall a b. (a -> b) -> a -> b
$ FPrime -> Int -> FPrime
ex (FPrime -> FPrime -> FPrime -> FPrime
mulr FPrime
p (FPrime -> FPrime -> FPrime
square FPrime
p FPrime
erg) (FPrime -> FPrime -> FPrime -> FPrime
addr FPrime
p (FPrime
a forall a. Bits a => a -> a -> a
B..&. FPrime
pat) (FPrime
eins forall a. Bits a => a -> a -> a
B..&. FPrime
invpat))) (Int
i forall a. Num a => a -> a -> a
- Int
1)
                in FPrime -> FPrime -> FPrime
redc FPrime
p forall a b. (a -> b) -> a -> b
$ FPrime -> Int -> FPrime
ex FPrime
1 (FPrime -> Int
log2len FPrime
k forall a. Num a => a -> a -> a
- Int
1)
-- -}

-- | field inversion
inv :: FPrime -> FPrime -> FPrime
inv :: FPrime -> FPrime -> FPrime
inv !FPrime
p !FPrime
a = FPrime -> FPrime -> FPrime -> FPrime
pow FPrime
p FPrime
a (FPrime -> FPrime
toInteger FPrime
p forall a. Num a => a -> a -> a
- FPrime
2)

-- | conversion wrapper with a limit
fromInteger :: Int -> FPrime -> Integer
fromInteger :: Int -> FPrime -> FPrime
fromInteger !Int
l !FPrime
a = forall a. Num a => FPrime -> a
P.fromInteger (FPrime
a forall a. Integral a => a -> a -> a
`mod` (FPrime
2forall a b. (Num a, Integral b) => a -> b -> a
^Int
l))
{-# INLINABLE fromInteger #-}

-- | a most simple conversion wrapper
toInteger :: FPrime -> Integer
toInteger :: FPrime -> FPrime
toInteger !FPrime
a = forall a. Integral a => a -> FPrime
P.toInteger FPrime
a
{-# INLINABLE toInteger #-}

-- | like testBit, but give either 0 or 1
condBit :: FPrime -> Int -> FPrime
condBit :: FPrime -> Int -> FPrime
condBit !FPrime
a !Int
i = FPrime -> Int -> FPrime
shift (FPrime
a forall a. Bits a => a -> a -> a
B..&. Int -> FPrime -> FPrime
fromInteger (Int
iforall a. Num a => a -> a -> a
+Int
1) ((FPrime
2forall a b. (Num a, Integral b) => a -> b -> a
^(Int
iforall a. Num a => a -> a -> a
+Int
1)forall a. Num a => a -> a -> a
-FPrime
1)::Integer)) (-Int
i)
{-# INLINABLE condBit #-}