第2章――Design Wave設計コンテスト2008 Professional部門 優勝

回路規模最小を目指した
FPGA向けRSA暗号化器の設計
上原昭宏
Design Wave 設計コンテスト 2008 の Professional 部門た．さらにバッファを共有およびバッファが不要な信号フで優勝した設計を紹介する．改良モンゴメリ乗算アルゴリズム

ローをとって回路規模を最小にしました．

を用いたべき乗剰余演算アルゴリズムによるビット・シリアル

米国 Xilinx 社の Spartan-3（スピード・グレード 4）を演算回路で構成した RSA 暗号化器を元にしている．けた上げ

ターゲットに合成したRSA 暗号化器の回路規模と最大動作が上位けたに伝播しないビット・シリアル加算および乗算/2

周波数は，それぞれ 583 スライスおよび 78MHz（50 入力乗回路を FPGA に最適化した．ビット長をパラメータ宣言しXOR に対して回路規模 58 倍，遅延時間 1.1）でした．また，ているので，任意のビット長に対応できる．

べき乗演算回路および RSA 暗号化回路の規模は，平文 1（編集部）

ビット当たりそれぞれ 10 スライス，17 スライスで設計でDesign Wave 設計コンテスト 2008 課題の，ビット長 32きることが分かりました．の平文を RSA 暗号化する回路に，「原理的に最小規模でかつ高クロック動作の設計ができるか」を目標に取り組みま

1．設計目標を決めるした．このために，RSA 暗号化の核であるべき乗剰余演算に正面から取り組み，FPGA に実装した際の回路規模と速度の設計限界を原理的に見極めようとしました．

● RSA 暗号処理の中身成果を上げるには目標が何かを明確にしなければなりま

設計検討のために文献を調査しても内容が高度で理解でせん．設計目標を決めるには，処理内容を地に足がついたきず冷や汗をかいているところに，改良モンゴメリ乗算ア感覚でしっかりと把握することが必須です．そこで，まずルゴリズムを用いたべき乗剰余演算アルゴリズムによるRSA 暗号化と復号化を見直しました．

ビット・シリアル演算回路で構成したRSA 暗号化器（1）に出会いました．

平文，暗号文，暗号化鍵，復号鍵，法をそれぞれ Cp，Ce，E，D，M と表します．ここで法 M は十分大きな二つ回路規模が平文のビット長に比例する，そして処理ビッの素数 p および q の積，平文 Cp は法 M より小さい正整数，

ト長が長くなっても最大動作クロックが低下しないビッ

そして正整数 L を（p − 1）と（q − 1）の最小公倍数とするとト・シリアル演算回路は，回路規模と速度の見極めに適し式（1）が成り立ちます．ていると思い，これを採用しました．さらに，けた上げが上位けたに伝播しないビット・シリアル加算および乗算/2

C p L modM = 1……………………………………
（1）乗回路を FPGA に最適化して設計しました．これらを，式（1）の mod は剰余を求める演算子です．A mod B は Aビット長をパラメータ宣言して設計することで，任意のを B で割った余りを表します．つまり式（1）は法 M の剰余ビット長に対応した実用的な RSA 暗号化器を設計しまし系のべき乗には周期 L があることを示しています．

KeywordRSA 暗号化器，改良モンゴメリ乗算アルゴリズム，ビット・シリアル演算回路，Spartan-3，べき乗剰余演算

Design Wave Magazine 2008 June 111ここで，鍵 E および D をある整数 H に対して，

E ⋅ D =H ⋅ L + 1……………………………………
（2）を満たすようにとり，暗号化と復号化をそれぞれ，

Ce = C p E modM
C p = Ce D modM……………………………………
（3）……………………………………
（4）のべき乗剰余演算で与えます．こうすると，D

Ce D modM = (C p E modM ) modM = Cp E⋅D modM
（5）
=Cp ( H⋅L +1) modM =C p …………………

調査は過去の設計例との差異を押さえて自分のオリジナル点を主張するためにも重要です．
「べき乗剰余演算」や「RSA」などのキーワードを使い，Google Scholar，Google Patent，CiteSeer，IEEE Xploreなどで検索をかけて，引用数が多い論文を特に重点的に見ていきました．ところが内容がさっぱり理解できません．
英文は読めて意味も分かる（分かっているはず）のですが，RSA 暗号化器の一部分，べき乗もしくは乗算に論点が集中するので，RSA の全体回路を知らない私には全体像がピンときません．そのうえ，何年にも渡る研究を基にしているために，議論も高度で理解が追いつかずに途方にくれてしまいました．のように，鍵 E で暗号化した文を鍵 D で復号化できます．

何とかモンゴメリ・アルゴリズムが乗法演算に重要だとこのように式自体は短くて理解しやすいのですが，平文，分かり，原典（2）を参照したり初期の研究論文（3）を読んでみ鍵，法のそれぞれの項が，通常はビット長1024 以上とけたました．しかし，回路全体の姿が見通せずに苦しみました．

数が大きいことが計算を難しくします．ビット長 32 の場合

そんなときに内容が理解できて自分の設計方針にぴったりですら関数電卓を使っても計算は大変です．

くる Ching-Chao らの論文（1）に出会い，これを FPGA に最適化することにしました．

● 設計方針を決める
本設計の目的は優れた設計例を示すことであり，その評
価ポイントは回路規模と速度，ユニークさの 3 点です．こ2．アルゴリズムを FPGA にはめこんでいくの 3 点のどこに重きを置くかで結果の 8 割が決まると考えました．

● RSA 暗号化器の構成

RSA 暗号化回路は，数多くの設計例が既に報告されていChing-Chao らのべき乗アルゴリズム（1）を C 言語風に表ます．ユニークさを出すにも一朝一夕に新アイデアは出て記したものを図 1 に示します．これだけでは分かりにくいきません．そこで今回のコンテスト特有の条件「平文のビッので具体例で説明していきます．

ト長が最大 32」を活用できないかと考えました．

べき乗は 2 乗と前処理した平文 Cp との積を繰り返すもところがビット長が短くても，剰余系演算という本質ののです．前処理した平文 Cp については後で説明します．

困難さには違いがないために，手が浮かびませんでした．

例として指数が6 のときの処理ステップを図2 に示します．

そこで規模と速度の 2 点に，正面から取り組むことにしま

2 乗すれば指数を 2 倍（左に 1 ビット・シフト），Cp を掛けした．また，せっかく 1 から設計するのですから，FPGAれば指数に＋ 1 することになります．従って，2 進数表記

におけるRSA 暗号化器の回路規模と最大動作クロックの設した指数を最上位ビットから 1 ビットずつ見ていき，ビッ計限界はどこにあるのかを原理的に明らかにしたいと考え

ト・シフトと＋ 1 に対応した2 乗またはCp との積を繰り返ました．そしてコンテスト課題限定の設計では面白くないせばべき乗が求まります．

ので，ビット長がより長い平文も処理できる実用的な設計を目指しました．

このべき乗剰余演算のほとんどの処理時間を占めるのが乗算です．例えば n ビットの A と B の積を計算するには，まず（A × B）を求めてから法 M の剰余を求めなければなり● 文献調査で巨人の肩に乗るません．この剰余を求めるためのビット長 2n の除算回路はRSA 暗号化は広く一般に使われており回路設計例の報告

設計が厄介です．ところが，この乗算をビット・シフトとも数多くあります．そこで過去の成果を吸収すれば手早く加算だけで行うのがモンゴメリ・アルゴリズム（2）です．

巨人の肩に乗れるだろうと文献調査をしました．また文献

112 Design Wave Magazine 2008 June

これは（A × B × 2 − n）を求めるものです．まず（A × B）