There's a serious problem with this function from my Elliptic Curve Crypto Library (see "ecc_lib.cpp" in bigint_OSL.zip/tar-gzip)

// Multiply us by this scalar, under the action of this curve.This function runs much faster when multiplying by a small scalar than when multiplying by a big scalar. On my machine, multiplying by 0 takes 80 nanoseconds; while multiplying by 0xffffff (a 24-bit value) takes 27 million nanoseconds! Because each bit costs about a millisecond, and millisecond-level timing information is pretty easy to observe over a local network, an attacker might be able to recover a 512-bit key using as few as 512 message exchanges (these could be generated as, for example, innocent-looking attempts to create an ECDSA signature).

ECpoint ECpoint::multiply(BigInteger scalar,const ECcurve &curve) const

{

ECpoint sum=ECpoint::infinity;

ECpoint A=*this;

for (int bit=0;scalar!=0;bit++) {

if ( bi_is_odd(scalar.get()) ) // this bit is set--include value in sum

sum=sum.add(A,curve); // do sum+=A;

scalar = scalar/2; // shift right by 1 bit

if (scalar!=0) // more data is available

A=A.add(A,curve); // shift A up to next bit (A+=A)

// possible optimization: save the table of A values...

}

return sum;

}

For this assignment, simply modify the bigint_OSL/ecc_lib.cpp multiply function so its timing varies by no more than a few milliseconds (on your computer), for any scalar up to 32 bits in size. Turn in your modified source code, and a very short README.txt file listing your general approach and the new timing information. Due date is Monday, April 29 (postponed due to NCCDC and SpringFest).