What's a proper window size in RSA exponentiation?

Question

I want to use the window method for RSA modular exponentiation.

Because of Side Channel Attacks (SCA).

But I don`t know what a proper window size is.

Answer 1

Window Size (W) for many practical implementation of RSA Algorithm (like OpenSSL) is related to key length.for example in openSSL library for insecure 80 bits key, W is 4 or for insecure 320 bits key , W is 5 and for 1024 or 2048 bits key (length), W is 6.

note:Maximum of Window size in openSSL Library is "6"

Answer 2

A.Toumantsev had it right in his comment that 'it depends'; I'll try to expand on that.

First of all, there's no one 'window method', there are a bunch of different variations, and which $w$ works best for you would depend on the exact version you're using.

With the most basic window method, to compute $a^e \bmod p$, you:

• compute $a^0 \bmod p, a^1 \bmod p, a^2 \bmod p, ..., a^{2^w-1} \bmod p$ (using $2^w-2$ modular multiplications),
• express $e$ as a base-$2^w$ integer as $e = d_n 2^{nw} + d_{n-1}2^{(n-1)w} + ... + d_02^{0w}$
• starting with $d_n$, alternatively multiply in $a^{d_i} \bmod p$ (doing a lookup into the table you computed in step 1), and doing $w$ modular square operations, ending with the multiply of $a^{d_0}$

This very basic form uses, for an $k$-bit exponent $e$, $2^w-2$ multiplications, $k/w$ multiplications of the digits, and about $k$ squaring operations (careful programming can reduce those a small amount).

So, the 'best' value of $w$, assuming that your exponent is $k$ bits long, is the value that minimizes $2^w - 2 + k/w + k$, or (dropping the terms that don't involve $w$, $2^w + k/w$.

If you're doing 2048 bit RSA with CRT (and hence during the private key operation, $e$ will be a 1024 bit integer), then a simple computation shows that $w=6$ would be optional, and $w=5$ would be only slightly worse. If $e$ is a 2048 bit integer, then $w=6$ is obviously optimal.

Now, a few words of warning:

• This analysis assumed the very basic window method. However, if you're actually worried about side channel attacks, you're not likely to use the very basic method, as it can leak rather a lot if you're not careful. You're rather more likely to use some variant; how that variant works could modify the analysis.

• Actually, using a less than optimal $w$ isn't all that costly (unless you use a drastically too large $w$); the largest cost in this is the repeated squarings, and $w$ doesn't do much to prevent that. You might (say) decide to use a fixed $w=4$; that takes a bit longer, but it may simplify the computation of the digits $d_i$, and that simplification may outweight the small time cost.

Answer 3

Window size(w) depends on the NIST curve and the algorithm that you are going to use for point multiplication.

I suggest you to look to the paper from Brown et al. Software Implementation of the NIST Elliptic Curves Over Prime Fields. They provide the number of operations in algorithms w. r. t. changing window size for some point multiplication algorithms.

Fo example, in the paper, they use w = 5 for curves P_192, P_224, P_256 and w = 6 for the curves the P_384 and P_521 in some point multiplication algorithms such as Fixed-base windowing method algorithm and Window NAF method for point multiplication algorithm. On the other hand, for the Fixed-base comb method with two tables method they suggest w = 4 for curves P_192, P_224, P_256 and w = 5 for the P_384 and P_521.