1-- |
2-- Module      : Crypto.Math.F2m
3-- License     : BSD-style
4-- Maintainer  : Danny Navarro <j@dannynavarro.net>
5-- Stability   : experimental
6-- Portability : Good
7--
8-- This module provides basic arithmetic operations over F₂m. Performance is
9-- not optimal and it doesn't provide protection against timing
10-- attacks. The 'm' parameter is implicitly derived from the irreducible
11-- polynomial where applicable.
12
13module Crypto.Number.F2m
14    ( BinaryPolynomial
15    , addF2m
16    , mulF2m
17    , squareF2m'
18    , squareF2m
19    , modF2m
20    , invF2m
21    , divF2m
22    ) where
23
24import Data.Bits (xor, shift, testBit, setBit)
25import Data.List
26import Crypto.Number.Basic
27
28-- | Binary Polynomial represented by an integer
29type BinaryPolynomial = Integer
30
31-- | Addition over F₂m. This is just a synonym of 'xor'.
32addF2m :: Integer
33       -> Integer
34       -> Integer
35addF2m = xor
36{-# INLINE addF2m #-}
37
38-- | Reduction by modulo over F₂m.
39--
40-- This function is undefined for negative arguments, because their bit
41-- representation is platform-dependent. Zero modulus is also prohibited.
42modF2m :: BinaryPolynomial -- ^ Modulus
43       -> Integer
44       -> Integer
45modF2m fx i
46    | fx < 0 || i < 0 = error "modF2m: negative number represent no binary polynomial"
47    | fx == 0         = error "modF2m: cannot divide by zero polynomial"
48    | fx == 1         = 0
49    | otherwise       = go i
50      where
51        lfx = log2 fx
52        go n | s == 0    = n `addF2m` fx
53             | s < 0     = n
54             | otherwise = go $ n `addF2m` shift fx s
55                where s = log2 n - lfx
56{-# INLINE modF2m #-}
57
58-- | Multiplication over F₂m.
59--
60-- This function is undefined for negative arguments, because their bit
61-- representation is platform-dependent. Zero modulus is also prohibited.
62mulF2m :: BinaryPolynomial -- ^ Modulus
63       -> Integer
64       -> Integer
65       -> Integer
66mulF2m fx n1 n2
67    |    fx < 0
68      || n1 < 0
69      || n2 < 0 = error "mulF2m: negative number represent no binary binary polynomial"
70    | fx == 0   = error "modF2m: cannot multiply modulo zero polynomial"
71    | otherwise = modF2m fx $ go (if n2 `mod` 2 == 1 then n1 else 0) (log2 n2)
72      where
73        go n s | s == 0  = n
74               | otherwise = if testBit n2 s
75                                then go (n `addF2m` shift n1 s) (s - 1)
76                                else go n (s - 1)
77{-# INLINABLE mulF2m #-}
78
79-- | Squaring over F₂m.
80--
81-- This function is undefined for negative arguments, because their bit
82-- representation is platform-dependent. Zero modulus is also prohibited.
83squareF2m :: BinaryPolynomial -- ^ Modulus
84          -> Integer
85          -> Integer
86squareF2m fx = modF2m fx . squareF2m'
87{-# INLINE squareF2m #-}
88
89-- | Squaring over F₂m without reduction by modulo.
90--
91-- The implementation utilizes the fact that for binary polynomial S(x) we have
92-- S(x)^2 = S(x^2). In other words, insert a zero bit between every bits of argument: 1101 -> 1010001.
93--
94-- This function is undefined for negative arguments, because their bit
95-- representation is platform-dependent.
96squareF2m' :: Integer
97           -> Integer
98squareF2m' n
99    | n < 0     = error "mulF2m: negative number represent no binary binary polynomial"
100    | otherwise = foldl' (\acc s -> if testBit n s then setBit acc (2 * s) else acc) 0 [0 .. log2 n]
101{-# INLINE squareF2m' #-}
102
103-- | Extended GCD algorithm for polynomials. For @a@ and @b@ returns @(g, u, v)@ such that @a * u + b * v == g@.
104--
105-- Reference: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B.C3.A9zout.27s_identity_and_extended_GCD_algorithm
106gcdF2m :: Integer
107       -> Integer
108       -> (Integer, Integer, Integer)
109gcdF2m a b = go (a, b, 1, 0, 0, 1)
110  where
111    go (g, 0, u, _, v, _)
112        = (g, u, v)
113    go (r0, r1, s0, s1, t0, t1)
114        = go (r1, r0 `addF2m` shift r1 j, s1, s0 `addF2m` shift s1 j, t1, t0 `addF2m` shift t1 j)
115            where j = max 0 (log2 r0 - log2 r1)
116
117-- | Modular inversion over F₂m.
118-- If @n@ doesn't have an inverse, 'Nothing' is returned.
119--
120-- This function is undefined for negative arguments, because their bit
121-- representation is platform-dependent. Zero modulus is also prohibited.
122invF2m :: BinaryPolynomial -- ^ Modulus
123       -> Integer
124       -> Maybe Integer
125invF2m fx n = if g == 1 then Just (modF2m fx u) else Nothing
126  where
127    (g, u, _) = gcdF2m n fx
128{-# INLINABLE invF2m #-}
129
130-- | Division over F₂m. If the dividend doesn't have an inverse it returns
131-- 'Nothing'.
132--
133-- This function is undefined for negative arguments, because their bit
134-- representation is platform-dependent. Zero modulus is also prohibited.
135divF2m :: BinaryPolynomial -- ^ Modulus
136       -> Integer          -- ^ Dividend
137       -> Integer          -- ^ Divisor
138       -> Maybe Integer    -- ^ Quotient
139divF2m fx n1 n2 = mulF2m fx n1 <$> invF2m fx n2
140{-# INLINE divF2m #-}
141