Gary Morris trevion at gmail.com
Tue Jun 7 03:06:24 EDT 2005

```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
```