HW3: Elliptic Curve Information Leakage

CS 463, Dr. Lawlor

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.
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;
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).

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).