SASIMI 2018 Proceedings

R2-13

High-Level Synthesis of Side Channel Attack Resistant RSA Decryption Circuit
Naoki OSAKO Sayuri OTA Suguru YURA†

Nagisa ISHIURA

School of Science and Technology, Kwansei Gakuin University
2-1 Gakuen, Sanda, Hyogo, 669–1337, Japan

Abstract—This paper presents a side channel attack resistantdesign of an RSA decryption circuit using high-level synthesis.
An RSA encoder/decoder can be designed by high-level synthesis utilizing the GNU GMP library. With this methodology, anRSA decryption circuit is synthesized based on the Fournaris’salgorithm which was designed against power analysis attacks andfault injection attacks. In order to reduce computation time andhardware size, Montgomery modular multiplication and parallelization of CRT-based modular exponentiation are applied. Results of synthesis targeting Xilinx Kintex-7 FPGA shows that theattack resistance has been implemented with the 1.94 times LUT
count and 5.17 times execution cycles.

I. Introduction
The “Internet of Things (IoT)” is becoming an integral partof our daily life and explosively increasing number of devices
are being connected to the Internet. To safeguard information
across those devices, encryption technologies eﬃcient both inhardware cost and power consumption are becoming important.
Eﬃciency of common key block cryptosystems such as AES(Advance Encryption Standard) may be drastically improvedby manually designing dedicated hardware with streamlined
architecture. On the other hand, public key cryptosystems such
the RSA (RivestShamirAdleman) and ECC (Elliptic-Curve
Cryptography) involve very long precision arithmetic which
tend to end up with memory centric architecture. In this case,specialized hardware does not always exhibit overwhelming
eﬃciency over processor implementation. In spite of this low
return-of-investment, hardware implementation is still wanted
to reduce hardware cost and power consumption of the IoT devices as much as possible. High-level synthesis is an attractive
option to implement such complex computation into memory
centric hardware.
Moreover, in the design of cryptosystem modules, extra
care must be paid against side channel attacks [2]. Depending on desired security levels, sophisticated algorithms must
be employed which hide power consumption changes associated with secret keys and do not emit significant information on
fault injection. This further increases required design eﬀorts.
To address this issue, in this paper, a side channel attack
resistant RSA decryption circuit is designed by high-level synthesis. A side channel attack resistant algorithm proposed byFournaris [1] is coded in the C language utilizing the GNU
multiple precision arithmetic library (GMP), and RTL design
is obtained using a high-level synthesizer ACAP [4]. In order to make the implementation further eﬃcient, Montgomery
reduction and parallelization on CRT-based modular exponen† Currently with Ministry of Defense, Kanagawa, Japan.

- 159 -tiation are applied. Synthesis targeting Xilinx Kintex-7 FPGA
shows that attack resistance can be implemented at the cost of
1.94 times LUT count and 5.17 times execution cycles.
II. Protection against side channel attacks on RSA
cryptosystem
In the RSA cryptosystem, the ciphertext c of message m iscomputed with public keys N and e according to:c = me mod N(1)
where N = pq and p and q are prime numbers. Message m isrecovered from c using private key d by computing:m = cd mod N(2)The high computation cost of modular exponentiation in (2) isoften lessened utilizing the Chinese reminder theorem (CRT):
m p = cd p mod p, mq = cdq mod q(3)−1−1
m = mq (q mod p)q + m p (p mod q)p(4)A standard way to compute (3) is to iterate modular multiplications over the bits of d p and dq , which leads to diﬀerent power
consumption for diﬀerent bit values. Moreover, changes on
the outputs caused by intentionally injected faults on particular signal lines may be exploited to infer the secret keys.
Fournaris’s algorithm [1] was designed to protect RSA decryption against those side channel attacks. It had resistanceagainst the power analysis attacks as well as the fault injection
attacks known at the point of publication, including Bellcore
attack, KQ attack, and YLMH attack.
An outline of the algorithm is shown in Figure 1. The mainfunction DECRYPT receives c, N, p, q, secret keys (d p , dq , iq ),and a random mask b and its inverse b−1 , to compute cd mod N.
Modular multiplication in equation (3) is computed by calling
FSCAME (lines 4–5), and the output is computed according tothe CRT (lines 6–9). Here, 4-tuple values instead of a single
values are computed, which are used to detect fault injection;
if fault injection is detected, error is returned not to leak theinformation. Function FSCAME computes modular exponentiation in encoded 4-tuple values. It is designed so that theamount of computation is independent of the bit values in thesecret key d (lines 9–16). It also detects fault injection.
III.

High-level synthesis of attack resistant RSA
decryption circuit
A. Overview
In this paper, the algorithm in Figure 1 is coded in the C
language to generate RTL design by high-level synthesis.
The GNU GMP library is used for multiple precision arithmetic. It is rewritten for the use of high-level synthesis [3].
Dynamic allocation is eliminated and statically allocated ar-TABLE I
Synthesis Results.

1: Function DECRYPT
2: Input: c, N, p, q, d p , dq , iq , b, b−1
3: Output: cd mod Ndesign
RSA (MIPS)RSA
SRR (MIPS)
SRR
SRR+M
SRR+M+P

4: (s0 , s1 , s2 , s4 ) = FSCAME(c, b, b−1 , d p , p);q q q q5: (s0 , s1 , s2 , s4 ) = FSCAME(c, b, b−1 , dq , q);
pppqppq

6: S 0 = s0 + q · ((s0 − s0 ) · iq mod p);
qqp
7: S 1 = s1 + q · ((s1 − s1 ) · iq mod p);
qqp
8: S 2 = s2 + q · ((s2 − s2 ) · iq mod p);
qqp
9: S 4 = s4 + q · ((s4 − s4 ) · iq mod p);

cycles432,256
68,261
3,557,349
627,615680,284
353,489#LUT
3,180
11,721
3,180
16,801
11,464
22,590

freq. [MHz]
121.7
107.8
121.7
77.5
105.5
105.6

ule for computation of line 4 before calling (its own) FSCAME
in line 5, and collect the return values before proceeding to line
6. Since most computation time is spent in the FSCAME, substantial speed-up is expected by this parallelization.

10: if (S 0 · S 1 mod N = S 2 and p, q not modified)
11: { return S 0 · S 4 mod N; } else { return error; }(a) RSA decryption.
1: Function FSCAME
2: Input: c, M, d = (1, dt−2 , ...d0 ), b, b−1
3: Output: (s0 , s1 , s2 , s4 )4:/ / s0 = be · ce mod M, s1 = bē+1 · cē+1 mod Mtt
5:/ / s2 = b2 · c2 mod M, s4 = b−e mod M

IV. Synthesis Results
The C code was synthesized into a Verilog HDL code by
high-level synthesizer ACAP [4] and then mapped into FPGA
(kintex-7 xc7k70) by Xilinx Vivado (2016.4). High-level synthesizer other than ACAP might also be used, but ACAP would
need less modification on the C code because it can synthesize
any C codes as long as their binaries can be executed on a baremetal MIPS.
The synthesis results are summarized in TABLE I. The C
code and the resulting circuits are independent of the number of bits for RSA decription, except for the size of arrays
to store intermediate results. In this experiment, the parameters were set so that up to 2048-bit RSA decription can beexecuted. “Cycles” in the table indicate the number of cycles
for RSA decryption of 128-bit data.

6: R = 2n+2 ; T = R2 mod M; T R = T · c · R−1 mod M;
7: bR = b · R mod M; bR−1 = b−1 · R mod M;
8: s0 = s1 = bR ; s2 = bR · T R · R−1 mod M; s3 = s4 = s5 = bR−1 ;9: for (i = 0 to t − 1) {10:
if (di = 1) {11:
s0 = s0 · s2 · R−1 mod M; s4 = s4 · s3 · R−1 mod M;
12:} else {13:
s1 = s1 · s2 · R−1 mod M; = s5 = s5 · s3 · R−1 mod M;
14:}15:
s2 = s22 · R−1 mod M; s3 = s23 · R−1 mod M;
16: }17: s0 = s0 · b−1 · R−1 mod M;
18: s1 = s1 · c · R−1 mod M;
19: s2 = s2 · 1 · R−1 mod M;
20: s4 = s4 · b · R−1 mod M;
21: if (i and d are not modified and22:s0 · s1 · R−1 mod M = s2 · 1 · R−1 mod M)
23: { return (s0 , s1 , s2 , s4 ); } else { return error; }(b) Attack resistant Montgomery modular exponentiationFig. 1. Fournaris’s Algorithm [1].

rays are used. Once the maximum bit length of N is declared,
the C code can compute decryption for N smaller than that.
B. Montgomery modular multiplication
Montgomery modular multiplication is a technique to eliminate division from modular multiplication. Let R be an integer
where R and N are mutually prime and R−1 be an integer satisfying RR−1 = 1 mod N. Montgomery reduction is definedas M(t) = tR−1 mod N. Let R2 = R2 mod N. Then, modular
multiplication z = xy mod N is replaced by:
X = M(xR2 ), Y = M(yR2 ),Z = MR(XY)z = MR(Z)If we choose R to be an exponential of 2, all these computationis performed only with multiplication, shift, and bit-wise andoperations. We apply this transformation to all the modular
multiplication in the algorithm to eliminate division.
C. Parallelization
There is no dependency between two modular exponentiation, so the calls to FSCAME in lines 4–5 in Figure 1 (a) can becomputed in parallel. For this purpose, we synthesize anotherhardware module that compute only FSCAME. Then, function
DECRYPT is modified so that it activates the FSCAME mod-- 160 -V. Conclusion
This paper has described high-level synthesis of a side channel attack resistant design of an RSA decryption circuit. Evaluation of the attack resistance is the future work. Even if thealgorithm is resistant, high-level synthesizer might bring unexpected variation exploited as side channels [5]. We consider
this an important topic to be investigated in details.
Acknowledgements—Authors would like to express their appreciation
to Dr. H. Kanbara (ASTEM/RI), Prof. H. Tomiyama (RitsumeikanUniv.), and Mr. T. Nakatani (formerly with Ritsumeikan Univ.) fortheir valuable comments. We would also like to thank to the membersof Ishiura Lab. of Kwansei Gakuin Univ. for their cooperation. Thiswork was partly supported by JSPS KAKENHI Grant #16K00088.

References[1] P. Fournaris, et al.: “Protecting CRT RSA against fault andpower side channel attacks,” in Proc. VLSI 2012, pp. 159–164 (Aug. 2012).
[2] Vlastı́mil Klı́ma and Tomáš Rosa: “Further results andconsiderations on side channel attacks on RSA,” in Proc.
CHES 2002, pp. 244–259 (Aug. 2002).
[3] N. Ito, et al.: “High Level synthesis from binary code
linked with multiple precision arithmetic library to RSA
encrypt/decrypt circuit,” (in Japanese) in Proc. Conventionof IPSJ Kansai Section, A-04 (Sept. 2015).
[4] N. Ishiura, H. Kanbara, and H. Tomiyama: “ACAP: Binary
synthesizer based on MIPS object codes,” in Proc. ITCCSCC 2014, pp. 725–728 (July 2014).
[5] S. Peter and T. Givargis: “Towards a timing attack aware
high-level synthesis of integrated circuits,” in Proc. ICCD,
pp. 452–455 (Nov. 2016).