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    , powF2m
20    , modF2m
21    , sqrtF2m
22    , invF2m
23    , divF2m
24    ) where
25
26import Data.Bits (xor, shift, testBit, setBit)
27import Data.List
28import Crypto.Number.Basic
29
30-- | Binary Polynomial represented by an integer
31type BinaryPolynomial = Integer
32
33-- | Addition over F₂m. This is just a synonym of 'xor'.
34addF2m :: Integer
35       -> Integer
36       -> Integer
37addF2m = xor
38{-# INLINE addF2m #-}
39
40-- | Reduction by modulo over F₂m.
41--
42-- This function is undefined for negative arguments, because their bit
43-- representation is platform-dependent. Zero modulus is also prohibited.
44modF2m :: BinaryPolynomial -- ^ Modulus
45       -> Integer
46       -> Integer
47modF2m fx i
48    | fx < 0 || i < 0 = error "modF2m: negative number represent no binary polynomial"
49    | fx == 0         = error "modF2m: cannot divide by zero polynomial"
50    | fx == 1         = 0
51    | otherwise       = go i
52      where
53        lfx = log2 fx
54        go n | s == 0    = n `addF2m` fx
55             | s < 0     = n
56             | otherwise = go $ n `addF2m` shift fx s
57                where s = log2 n - lfx
58{-# INLINE modF2m #-}
59
60-- | Multiplication over F₂m.
61--
62-- This function is undefined for negative arguments, because their bit
63-- representation is platform-dependent. Zero modulus is also prohibited.
64mulF2m :: BinaryPolynomial -- ^ Modulus
65       -> Integer
66       -> Integer
67       -> Integer
68mulF2m fx n1 n2
69    |    fx < 0
70      || n1 < 0
71      || n2 < 0 = error "mulF2m: negative number represent no binary polynomial"
72    | fx == 0   = error "mulF2m: cannot multiply modulo zero polynomial"
73    | otherwise = modF2m fx $ go (if n2 `mod` 2 == 1 then n1 else 0) (log2 n2)
74      where
75        go n s | s == 0  = n
76               | otherwise = if testBit n2 s
77                                then go (n `addF2m` shift n1 s) (s - 1)
78                                else go n (s - 1)
79{-# INLINABLE mulF2m #-}
80
81-- | Squaring over F₂m.
82--
83-- This function is undefined for negative arguments, because their bit
84-- representation is platform-dependent. Zero modulus is also prohibited.
85squareF2m :: BinaryPolynomial -- ^ Modulus
86          -> Integer
87          -> Integer
88squareF2m fx = modF2m fx . squareF2m'
89{-# INLINE squareF2m #-}
90
91-- | Squaring over F₂m without reduction by modulo.
92--
93-- The implementation utilizes the fact that for binary polynomial S(x) we have
94-- S(x)^2 = S(x^2). In other words, insert a zero bit between every bits of argument: 1101 -> 1010001.
95--
96-- This function is undefined for negative arguments, because their bit
97-- representation is platform-dependent.
98squareF2m' :: Integer
99           -> Integer
100squareF2m' n
101    | n < 0     = error "mulF2m: negative number represent no binary polynomial"
102    | otherwise = foldl' (\acc s -> if testBit n s then setBit acc (2 * s) else acc) 0 [0 .. log2 n]
103{-# INLINE squareF2m' #-}
104
105-- | Exponentiation in F₂m by computing @a^b mod fx@.
106--
107-- This implements an exponentiation by squaring based solution. It inherits the
108-- same restrictions as 'squareF2m'. Negative exponents are disallowed.
109powF2m :: BinaryPolynomial -- ^Modulus
110       -> Integer          -- ^a
111       -> Integer          -- ^b
112       -> Integer
113powF2m fx a b
114  | b < 0     = error "powF2m: negative exponents disallowed"
115  | b == 0    = if fx > 1 then 1 else 0
116  | even b    = squareF2m fx x
117  | otherwise = mulF2m fx a (squareF2m' x)
118  where x = powF2m fx a (b `div` 2)
119
120-- | Square rooot in F₂m.
121--
122-- We exploit the fact that @a^(2^m) = a@, or in particular, @a^(2^m - 1) = 1@
123-- from a classical result by Lagrange. Thus the square root is simply @a^(2^(m
124-- - 1))@.
125sqrtF2m :: BinaryPolynomial -- ^Modulus
126        -> Integer          -- ^a
127        -> Integer
128sqrtF2m fx a = go (log2 fx - 1) a
129  where go 0 x = x
130        go n x = go (n - 1) (squareF2m fx x)
131
132-- | Extended GCD algorithm for polynomials. For @a@ and @b@ returns @(g, u, v)@ such that @a * u + b * v == g@.
133--
134-- Reference: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B.C3.A9zout.27s_identity_and_extended_GCD_algorithm
135gcdF2m :: Integer
136       -> Integer
137       -> (Integer, Integer, Integer)
138gcdF2m a b = go (a, b, 1, 0, 0, 1)
139  where
140    go (g, 0, u, _, v, _)
141        = (g, u, v)
142    go (r0, r1, s0, s1, t0, t1)
143        = go (r1, r0 `addF2m` shift r1 j, s1, s0 `addF2m` shift s1 j, t1, t0 `addF2m` shift t1 j)
144            where j = max 0 (log2 r0 - log2 r1)
145
146-- | Modular inversion over F₂m.
147-- If @n@ doesn't have an inverse, 'Nothing' is returned.
148--
149-- This function is undefined for negative arguments, because their bit
150-- representation is platform-dependent. Zero modulus is also prohibited.
151invF2m :: BinaryPolynomial -- ^ Modulus
152       -> Integer
153       -> Maybe Integer
154invF2m fx n = if g == 1 then Just (modF2m fx u) else Nothing
155  where
156    (g, u, _) = gcdF2m n fx
157{-# INLINABLE invF2m #-}
158
159-- | Division over F₂m. If the dividend doesn't have an inverse it returns
160-- 'Nothing'.
161--
162-- This function is undefined for negative arguments, because their bit
163-- representation is platform-dependent. Zero modulus is also prohibited.
164divF2m :: BinaryPolynomial -- ^ Modulus
165       -> Integer          -- ^ Dividend
166       -> Integer          -- ^ Divisor
167       -> Maybe Integer    -- ^ Quotient
168divF2m fx n1 n2 = mulF2m fx n1 <$> invF2m fx n2
169{-# INLINE divF2m #-}
170