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