Hello everyone, I've been playing with implementing the Kocher attacks on RSA in Haskell. For the simplest version, I decided to implement the exponentiation in the same module. However, my initial tests suggest that the times don't have any correlation with the operations being performed. I'm wondering, however, if this is because some of the computation is being delayed until later in the program (when I'm not timing) - if that makes any sense. My code is: {- For a given n, base, val, expt and i, this function computes val ^ 2 and then, if the ith bit of expt is 1, multiplies by base, and returns the result. (All these computations are done mod n.) -}
exptmod' :: Integer -> Integer -> Integer -> Int -> Integer -> Integer exptmod' n base expt i val | testBit expt i = (val ^ 2) * base `mod` n | otherwise = val ^ 2 `mod` n
{- This function uses exptmod' to compute base ^ expt mod n. Because it folds from the right, it checks bits from keySize down to 0, even though the list comprehension goes the other direction. -}
exptmod :: Integer -> Integer -> Integer -> Int -> Integer exptmod base expt n keySize = foldr (exptmod' n base expt) 1 [0..keySize]
to compute the exponentiation and mods. Later, I time it using:
time :: IO a -> IO (a, Integer) time act = do time1 <- accuticks res <- act time2 <- accuticks return (res, time2 - time1)
check :: Integer -> IO Integer check m = do (_,t) <- time (ioexptmod m privkey modulus keySize) return t
ioexptmod :: Integer -> Integer -> Integer -> Int -> IO Integer ioexptmod base expt n keySize = return $! exptmod base expt n keySize
where accuticks is an interface to the rdtsc op on Windows and to clock_gettime(CLOCK_REALTIME,...) on Linux. My hope was that the use of $! would force it to compute the exponentiation while I was timing -- and the average times are around 30K clock cycles, suggesting that it's doing the work, but I was wondering if it was possible that I was missing something. Thanks, /g -- I'll see you down in Arizona Bay