SCIENCE CHINA Information Sciences, Volume 62 , Issue 3 : 039105(2019) https://doi.org/10.1007/s11432-018-9488-2

Side channel attack of multiplication in $~\bf{GF}\boldsymbol{(q)}$ – application to secure RSA-CRT

More info
  • ReceivedFeb 4, 2018
  • AcceptedJun 15, 2018
  • PublishedOct 18, 2018


There is no abstract available for this article.


This work was supported by National Natural Science Foundation of China (Grant Nos. U1536103, 61402286, 61472249, 61602239, 6157- 2192, 61472250), and Minhang District Cooperation Plan (Grant No. 2016MH310).


[1] Kocher P C, Jaffe J, Jun B. Differential power analysis. In: Proceedings of Annual International Cryptology Conference, Santa Barbara, 1999. 15--19. Google Scholar

[2] Brier E, Clavier C, Olivier F. Correlation power analysis with a leakage model. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems, Cambridge, 2004. 16--29. Google Scholar

[3] Boscher A, Naciri R, Prouff E. CRT RSA algorithm protected against fault attack. In: Proceedings of International Conference on Information Security Theory and Practices, Heraklion, 2007. 229--243. Google Scholar

[4] Boscher A, Handschuh H, Trichina E. Blinded fault resistant exponentiation revisited. In: Proceedings of Fault Diagnosis and Tolerance in Cryptography, Lausanne, 2010. Google Scholar

[5] Clavier C, Reynaud L. Improved blind side-channel analysis by exploitation of joint distributions of leakages. In: proceedings of International Conference on Cryptographic Hardware and Embedded Systems, Taipei, 2017. 24--44. Google Scholar

[6] Xu S, Lu X J, Zhang K Y. Similar operation template attack on RSA-CRT as a case study. Sci China Inf Sci, 2018, 61: 032111 CrossRef Google Scholar

[7] Giraud C. An RSA implementation resistant to fault attacks and to simple power analysis. IEEE Trans Comput, 2006, 55: 1116-1120 CrossRef Google Scholar

[8] Kiss Á, Krämer J, Rauzy P. Algorithmic countermeasures against fault attacks and power analysis for RSA-CRT. In: Proceedings of Constructive Side-Channel Analysis and Secure Design, Graz, 2016. 111--129. Google Scholar

[9] Kim S K, Kim T H, Han D G. An efficient CRT-RSA algorithm secure against power and fault attacks. J Syst Softw, 2011, 84: 1660-1669 CrossRef Google Scholar

  • Figure 1

    (Color online) (a) Evaluation and (b) practical results of bit-flipping countermeasure with various noisy inputs.


    Algorithm 1 Prime byte recovery algorithm

    Require:$x^t=\{x_{n-1}^t,x_{n-2}^t,\ldots,x_{i}^t~\}$, where $x_{i}^t\in~\mathcal{I}^t_0$ and $x_{i-1}^t\in~\mathcal{I}^t_1$, $p=\{p_{n-1},p_{n-2},\ldots,p_{i+1}\}$,$~~~~~~~~~{\rm~previous~prime~byte~set}~S_{\rm~pre}$ where $p_{i+1}\in~S_{\rm~pre}$, result $r^t=\{r_{2n-1}^t,\ldots,r_{n}^t\}$;


    for $t=0$ to $n$

    for all $p_{i+1}\in~S_{\rm~pre}$

    for ${\rm~prime}~=~0$ to 255

    ${\rm~Index}\Leftarrow~1$; $\vartriangleright$ flag


    for all $x_{i}^t\in~\mathcal{I}^t_0$

    for all $x_{i-1}^t\in~\mathcal{I}^t_1$

    $x^t=\{x_{n-1}^t,x_{n-2}^t,\ldots,x_{i}^t~\}$; $\vartriangleright$ obtain previous input bytes

    $\{{\rm~PreviousByte,CurrentByte}\}=x^t\times~p$; $\vartriangleright$ obtain current and previous product result values

    if ${\rm~CurrentByte}\leq~r^{t}_{2n-i}-1$ ${\rm~PreviousByte}\equiv~r^{t}_{2n-i+1}$ Index then

    $A[p_{i+1}][{\rm~prime}]+=1$; $\vartriangleright$ compare intermediate value and $r^t$, count all possible prime bytes


    end if

    end for

    end for

    end for

    end for

    end for

    $S_{p_{i+1},p_{i}}\Leftarrow~{\rm~max}(A_{p_{i+1}}~^{\rm~prime})$. $\vartriangleright$ obtain prime byte results