2017 年電子情報通信学会基礎・ 境界ソ サイ エ テ ィ /NOLTA ソ サイ エ テ ィ 大会

A-7-1

モンゴメリ法及び並列化を適用した
耐サイドチャネル攻撃 RSA 復号回路の高位合成
High-Level Synthesis of Side Channel Attack Resistant RSA Decryption Circuitwith Montgomery Modular Multiplication and Parallelization
大窄 直樹
Naoki Osako
関西学院大学 理工学部

石浦 菜岐佐Nagisa Ishiura

School of Science and Technology, Kwansei Gakuin University

はじめにIoT (Internet of Things) 向け組込み機器の増加に伴い, 暗号回路のサイドチャネル攻撃への対策が重要な課題となっている. 文献 [1] では, Fournaris のアルゴリズ
ム [2] に基づき, サイドチャネル攻撃に耐性を持つ RSAの復号回路を高位合成により設計する手法を提案しているが, 攻撃に耐性を持たせるために, 復号回路の規模, 実
行時間が大幅に増加している. 本稿では, モンゴメリ法及び並列化により, サイドチャネル攻撃に耐性を持つ RSA復号回路の高速化と回路規模の削減を試みる.

11 耐攻撃 Montgomery 冪剰余算
⃝Function: FSCAME
Input: c, b, b−1 , d = (1, dt−2 , ...d0 ), M
Output: (s0 , s1 , s2 , s4 )R = 2n+2 ; T = R2 mod M ;bR = b · R mod M ;bR−1 = b−1 · R mod M ;s0 = s1 = bR ;TR = T · c · R−1 mod M ;s2 = bR · TR · R−1 mod M ;s3 = s4 = s5 = bR−1 ;for (i = 0 to t − 1) {if (di = 1) {s0 = s0 · s2 · R−1 mod M ; s4 = s4 · s3 · R−1 mod M ;} else {s1 = s1 · s2 · R−1 mod M ; s5 = s5 · s3 · R−1 mod M ;}s2 = s22 · R−1 mod M ;s3 = s23 · R−1 mod M ;}s0 = s0 · b−1 · R−1 mod M ; s1 = s1 · c · R−1 mod M ;s2 = s2 · 1 · R−1 mod M ; s4 = s4 · b · R−1 mod M ;if (i and d are not modified ands0 · s1 · R−1 mod M = s2 · 1 · R−1 mod M ){ return (s0 , s1 , s2 , s4 ); } else { return error; }耐サイドチャネル攻撃 RSA 復号回路の高位合成
Fournaris のアルゴリズム (図 1) [2] は, RSA 復号処理のサイドチャネル攻撃に対する脆弱性の解決を図ったものであり, 一般的な単純電力解析攻撃や差分電力解析攻撃の他, Bellcore 攻撃, KQ 攻撃, YLMH 攻撃等の故障利用攻撃への耐性を持つ. [1] は, 多倍長整数演算ライブ
ラリ GMP を用いて Fournaris のアルゴリズムを C 言語で記述し, これを高位合成システム ACAP [3] で合成することにより耐サイドチャネル攻撃 RSA 復号回路を設計している.

22 RSA 復号⃝Input: c, b, b−1 , p, q, dp , dq , iq = q −1 mod p, N
Output: cd mod Nppp−1(sp, dp , p);
0 , s1 , s2 , s4 ) = FSCAME(c, b, b(sq0 , sq1 , sq2 , sq4 ) = FSCAME(c, b, b−1 , dq , q);q) · iq mod p);
S0 = sq0 + q · ((sp0 − s0S1 = sq1 + q · ((sp− sq1 ) · iq mod p);
1q
S2 = sq2 + q · ((sp−s) · iq mod p);
22q
S4 = sq4 + q · ((sp4 − s4 ) · iq mod p);

モンゴメリ法適用及び並列化
本稿では, モンゴメリ法の適用と並列化により [1] のRSA 復号回路を効率化する. 図 1 中の乗算剰余演算(x · y mod M ) を全てモンゴメリ法での計算に変更するとともに, モンゴメリ法で使用する R, p, q 等を事前に2 に 2 箇所ある計算して定数として与える. 図 1 の ⃝FSCAME にはデータ依存がないので並列に計算する.
これは, FSCAME を計算する回路モジュールを作成し,一方の FSCAME の計算開始と同時にこれを起動することにより実現する.

3if (S0 · S1 mod N = S2 and p, q not modified){ return (S0 · S4 mod N ); } else { return error; }図1codeRSA
SRR [1]
SRR+M
SRR+M+P

Fournaris のアルゴリズム [2].
表 1 合成結果.
#LUT 動作周波数 [MHz] cycles
11,721
107.8 68,261
16,80177.5 627,615
11,464105.5 680,284
22,727105.6 353,489

むすび
本稿では, モンゴメリ法及び並列化により耐サイドチャネル攻撃 RSA 復号回路の効率化をした. 耐攻撃性の評
価及び回路の更なる効率化が今後の課題である. 本研究は一部 JSPS 科研費 16K00088 の助成による.

5合成結果
本稿の手法により記述した C プログラムを ACAP で高位合成し, Xilinx Vivado (2016.4) で FPGA (kintex-7xc7k70) をターゲットとして論理合成した. 結果を表 1に示す. RSA は攻撃に耐性のないの回路, SRR は [1]の回路, SRR+M は SRR にモンゴメリ法を適用した回路, SRR+M+P は SRR+M に並列化を適用した回路である. cycles は 128 ビット復号処理に要したサイクル数である. モンゴメリ法の適用により回路規模を約 68%に削減できた. 並列化により回路規模は SRR の 1.35 倍になったが, サイクル数は 56%に削減できた. 結果, RSAの約 5.17 倍の実行時間, 約 1.94 倍の回路規模でサイドチャネル攻撃耐性を持たせることができた.

4

参考文献[1] 太田, 由良, 石浦: “電力解析攻撃/故障利用攻撃耐性 RSA
復号回路の高位合成,” 信学ソ大, A-6-6 (Sept. 2016).

[2] P. Fournaris, et al.: “Protecting CRT RSA against fault
and power side channel attacks,” in Proc. VLSI 2012,pp. 159–164 (Aug. 2012).
[3] N. Ishiura, H. Kanbara, and H. Tomiyama: “ACAP: Binary synthesizer based on MIPS object codes,” in Proc.
ITC-CSCC 2014, pp. 725–728 (July 2014).

56
2017/9/12 〜 15

東京

（ 基礎・ 境界 /NOLTA 講演論文集）

Copyright © 2017 IEICE