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