0
$\begingroup$

I want to Use Window method for RSA modular Exponentiation.

because of SCA.

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

$\endgroup$
  • $\begingroup$ Window methods are not a good way for preventing side-channel attacks. See the Big Mac attack by Walter (2001), DOI:10.1007/3-540-44709-1_24 $\endgroup$ – user94293 May 19 '16 at 2:00
  • $\begingroup$ Thanks. I will Use Window method and Other method at same time. So I need proper Window size. but Now I think Window method is Not good way Since i saw Bic Mac attack... $\endgroup$ – pftpmlp May 20 '16 at 5:59
  • $\begingroup$ @pftpmlp Your question is too broad, you'd better give people some background on what are you going to use "window method" for, what is your key size, or the range of key sizes, what are you trying to achieve, etc. The way you asked the question, my answer is - there is no such thing as "proper window size". It all depends... $\endgroup$ – tum_ May 27 '16 at 14:57
  • 1
    $\begingroup$ Your question seems to be about RSA, but has the [elliptic-curve] tag. Which is it? $\endgroup$ – Mike Ounsworth May 27 '16 at 15:28
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ hmm..I want to know window size (in window method) with modular Exponentiation. Not point multiplication. $\endgroup$ – pftpmlp May 17 '16 at 7:32
  • 1
    $\begingroup$ My bad, in the question you are asking is it right to use w = 4 for NIST curves, i was answering that question. $\endgroup$ – Makif May 17 '16 at 8:22
  • 1
    $\begingroup$ I`m sorry. I thought window method in Point multiplication and Modular Exponentiation is Too similar that name and algorithms. $\endgroup$ – pftpmlp May 17 '16 at 8:43
0
$\begingroup$

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"

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.