# Random ladder for public-key encryption

{-
This module performs a public-key encryption operation, such as modulo
exponentiation or elliptic curve scalar multiplication, in a way that makes it
difficult for an attacker to determine the exponent or multiplier by listening
to a side channel. Rather than performing the operation in a constant time
regardless of the bits, as is done in imperative languages such as C and Rust,
it randomizes the sequence of operations, dividing the number by 2 or 3 at random,
so that the same number can result in different sequences of operations and
the same sequence of operations can result from different numbers.
-}
) where
import qualified Data.Sequence as Seq
import Data.Sequence ((><), (<|), (|>), Seq((:<|)), Seq((:|>)))

ladderBitsNeeded :: Int -- ^ The number of bits in the exponent/multiplier.
-> Int -- ^ The number of bits in range for randomLadder.
ladderBitsNeeded n = round ((fromIntegral n) * 0.78788506 + 9.331)
-- 0.78788506 is (log (644/373))/(log 2),
-- which is pretty close to (log (644/271))/(log 3).
-- 9.331 is (log 644)/(log 2),
-- which allows the last bit to be split close to 373|271.

makeLadder :: Integer -> Integer -> Integer -> Seq.Seq Int
-- makeLadder n random range -> sequence-of-instructions
-- range should be at least n**0.78788506
-- random should be in [0..range)
-- n should be nonnegative
makeLadder (-1) _ _ = error "negative multiplier/exponent"
makeLadder 0 _ _ = Seq.empty
makeLadder 1 _ _ = Seq.singleton 21
makeLadder 2 _ _ = Seq.singleton 32
let crit = (range * 373 + 322) div 644
(quo2,rem2) = n divMod 2
(quo3,rem3) = n divMod 3
in if random >= crit
then let third = makeLadder quo3 (random - crit) (range - crit)
in
if rem3 == 0
then 30 <| third
else
if rem3 == 1
then 31 <| third
else 32 <| third
else let half = makeLadder quo2 random crit
in
if rem2 == 0
then 20 <| half
else 21 <| half

climbLadder :: Seq.Seq Int -> a -> a -> (a -> a -> a) -> a -> a
climbLadder Seq.Empty _ _ _ acc = acc
climbLadder (is :|> 20) gen gen2 (<+>) acc =
climbLadder is gen gen2 (<+>) (acc <+> acc)
climbLadder (is :|> 21) gen gen2 (<+>) acc =
climbLadder is gen gen2 (<+>) ((acc <+> acc) <+> gen)
climbLadder (is :|> 30) gen gen2 (<+>) acc =
climbLadder is gen gen2 (<+>) (acc <+> acc <+> acc)
climbLadder (is :|> 31) gen gen2 (<+>) acc =
climbLadder is gen gen2 (<+>) ((acc <+> acc <+> acc) <+> gen)
climbLadder (is :|> 32) gen gen2 (<+>) acc =
climbLadder is gen gen2 (<+>) ((acc <+> acc <+> acc) <+> gen2)

-- | For example, (randomLadder 3 (*) 1 17 8388608 16777216) = 129140163.
-- The number 8388608 determines the sequence of squaring and cubing, but
-- the final result, which is 3^17, does not depend on it.
randomLadder :: a -- ^ The generator of the group, the point being multiplied or the base of exponentiation.
-> (a -> a -> a) -- ^ The group operation.
-> a -- ^ The identity element.
-> Integer -- ^ The exponent or multiplier (must be nonnegative).
-> Integer -- ^ A random number in [0..range).
-> Integer -- ^ The range of the random number.
-> a -- ^ The result of exponentiation or scalar multiplication.
randomLadder gen (<+>) zero n random range =


I've run this code with (+) and (*) as the operation, and it works correctly. I haven't tried big-number modulo exponentiation or elliptic curve point multiplication.

I'm new to Haddock and couldn't figure out how to comment the whole module. I'd like to know how clear the code and comments are and also if it would actually foil side-channel attacks.

My code assumes that (<+>) works correctly in expressions like g<+>g, g<+>(-g), and g<+>0, as well as g<+>h where g and h are unrelated. Is this true of actual elliptic-curve implementations?

Code is available on GitHub.

I'm new to Haddock and couldn't figure out how to comment the whole module.

I think the problem is that the module description needs to have some internal structure. See here

I'd like to know how clear the code and comments

The code seems kinda dense. Maybe it's just that I don't understand it and have context, so my eyes inevitably bounce off, I'm not sure. Trying to articulate how I'd make it easier to read, I'd say you're not using newlines and indentation in a way that forefronts the code's structure. For example, the then and else clauses should always be indented more than the controlling if. I also suspect you could improve clarity by using where clauses for a lot of stuff.

• More consistency would be good. climbLadder has no comments, and makeLadder has a comment but it's not a Haddock comment. Maybe that's on purpose; which would be fine.
• The first things to document about a function are what it's for and how it's used. (How it works may also be commented, but doesn't usually belong in Haddock documentation). randomLadder appears to be the meat of the module, so its documentation should say those two things succinctly upfront. Including an example is often good, but again, try putting it in the format of "in order to do X, write Y".
• The reason the module comment didn't show up turned out to be that | needs to go on the same line as {-. Aug 4, 2022 at 14:51