The timing attack on Diffie-Hellman depends on assumptions about what multiplications are being made, and in what order. But you don't need to do them in order. The standard approach to calculating Y**x mod m is to calculate Y[1] = Y, Y[2] = Y**2, Y[3] = Y**4, .... Y[logx] = Y**(logx), and while you're doing this keep a running total r[i], where r[i] = (bit[x,i]) ? (r[i-1]*Y[i]) : r[i-1] all arithmetic modulo m (and all indices possibly off by one :-) This may be a bit memory-intensive for a smartcard, but there's no need to calculate these partial products in order; precompute the Y[i], pick a random permutation of 1..(logx), and compute the partial products in that order. This still leaks the number of 0 and 1 bits in x, but it doesn't say what they are. You probably still should multiply r[i-1]*Y[i] whether you're going to need it or not; I don't think the method hides enough information otherwise, but that needs more analysis. Cost - mostly administrative, plus the memory, since keeping track of permutations of small integers is cheap relative to bignum multiplication and modulo calculations. You also need a random number generator of some sort; LFSRs seem to be an easy way to do permutations on the fly, so seed them with something decent. How effective is it? I'm not sure - I'd need to do a lot more analysis than I've done so far, and the long version of Paul's paper would help :-) But at first glance it looks like it makes it much harder; no two calculations are in the same order, so feeding the system related Y = g**y mod m each time doesn't tell you much. As a further annoyance to the listener, split the permutation at random into two or three pieces, compute their products separately, and then multiply those partial products together. (Don't try this at home without analyzing whether it may leak more information than it conceals...) At very minimum, take two numbers you've got lying around and multiply them every once in a while :-) #-- # Thanks; Bill # Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com # Phone +1-510-247-0663 Pager/Voicemail 1-408-787-1281