[45313] in Cypherpunks
Re: Potential defense against timing attack on Diffie-Hellman
daemon@ATHENA.MIT.EDU (Bill Stewart)
Wed Dec 13 03:07:05 1995
Date: Tue, 12 Dec 1995 23:43:55 -0800
To: cypherpunks@toad.com
From: Bill Stewart <stewarts@ix.netcom.com>
Cc: mab@research.att.com, smb@ulysses.att.com, pck@cryptography.com
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
