From: Bill Stewart <stewarts@ix.netcom.com>
Date: Wed, 13 Dec 1995 16:29:47 +0800
To: cypherpunks@toad.com
Subject: Re: Potential defense against timing attack on Diffie-Hellman
Message-ID: <199512130743.XAA25025@ix7.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Follow-on defense for low-memory smartcards:  This is a bit ugly
and I'm not sure how much it protects your information, but it's some
help for systems that can't store 1024 partial products 1024 bits long,
which smartcards generally can't be expected to do :-)

Pick k random values K1, K2, .. Kk, where k is some medium-sized number; 
probably about 10 though maybe more would be better.
Calculate Y[i] = Y**2**i, i=1...log x, as before, but instead of calculating
        r[i] = r[i-1] or r[i-1]*Y[i], i=1...logx,
calculate separate subproducts for i={1...K1}, {K1+1...K2}, ... {Kk...logx},
and then multiply those subproducts together.  The easy way to do this is
keep second running product P, and whenever you reach Kj, set P = P*r[i],
and set r[i]=1 for the next round of (Kj)+1...K(j+1).  You still need to
calculate r[i-1]*Y[i] whether you're using it or not.

For added obnoxiousness, at the cost of about 50% more calculation, you could
calculate Yinv = Y**-1 mod m, and calculate r[i] and Y**i for i = 1...Kj, 
calculate through Y[logx] ignoring the r[]s, and then calculate r[i]
and Y[logx] * Yinv**[logx-i] for i=logx....Kj+1.
#--
#				Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0663 Pager/Voicemail 1-408-787-1281