第1章――Design Wave設計コンテスト2008総評

RSA暗号化器設計のポイント
和田知久，林 輝彦
本誌 2008 年 5 月号において，Design Wave 設計コンテス

号の場合は，まったく同じ式で，P の部分と暗号 C の部分

ト 2008 の入賞者を発表した．ここでは，課題に対する回路が入れ替わり，別の鍵を用いる計算となります．

設計上のポイントを解説する．Professional 部門の入賞者を決定するに当たっては，技術的な評価のために，エンジニアのC = P E mod M………………………………………
（1）

方々にご協力いただいた．その審査委員である林 輝彦氏に，演算として一見単純に見えますが，指数の計算のために，Professional 部門の総評をお願いした．もう一方の Student

計算機では簡単に取り扱えない大きな数があり，計算には部門については，琉球大学にご協力いただき，同大学共催の特別な工夫が必要となります．

「LSI デザインコンテスト 2008」を同部門とさせていただいている．主催者でもある和田知久氏に，Student 部門の総評と入賞設計の概要の解説をお願いした．

2． Professional 部門総評

（編集部）

林 輝彦
Design Wave 設計コンテストでは，参加を希望される

1. コンテスト課題の概要
和田知久

方には例年，できるかぎり参加の登録をしていただいています（登録しなくてもコンテストへの参加は可能）．また希

今回の設計テーマは，電子メールや電子ファイルの暗号

望される方には，設計に使用する FPGA 評価ボードや化に用いられるRSA 暗号の暗号化・復号化回路の設計です

FPGA 開発ツールの貸し出しを行っています．今回も従来（図 1）．と同様にコンテストへの参加の登録，評価ボードや設計

RSA 暗号は，1977 年に発明されました．発明者であるツールの貸し出しの希望は活発でした．しかし，最終的にRon Rivest，Adi Shamir，Len Adleman の頭文字をつな

実際に設計を完了し，コンテストの応募レポートを作成でげてこのように呼ばれています．

きた参加者は限られたようでした．

RSA 暗号は，けた数が大きい整数の素因数分解が困難で最終的に審査に残った応募は例年に比べてかなり少なく，あることを利用して，安全性を保障している暗号です．

2 件の応募レポートを優勝候補としてコンテスト審査委員

従って，大きなけた数の整数演算が必要となります．

会で評価することになりました．いずれの応募も以前に設RSA の暗号化と復号化の計算は対称（同じ演算）です．暗計コンテストに複数回応募されている方からの応募で，完号鍵と復号鍵は異なるものですが，同一の指数演算と mod成度，実際のアプリケーションに使用できるだけの拡張性，（剰余）演算の組み合わせの演算となります．式（1）は平文柔軟性を備えた優れた設計に仕上がっていて，優劣を付け

P を暗号化鍵 E，M を用いて暗号 C を計算する式です．復

難く，コンテスト審査委員会は大変難しい選択を迫られる

KeywordRSA 暗号，モンゴメリ乗剰余演算，ビット・シリアル，シストリック・アレイ，CSA

102 Design Wave Magazine 2008 JuneRSA暗号化回路設計の特集2 トライ＆エラー
Input : N, 0< A <N, 0< B <N
PREP : V = - N-1 mod R
Output : S = A ・ B ・ R-1 mod N

発信者（Sender）

設計
ターゲット

設計
ターゲット

通信路（CommunicationChannel）
RSA暗号化器
RSA復号器（Encipher）（Decipher）

Q := (A ・ B) V mod R;
S := A ・ B + Q ・ N;
S := S / R;
If (N < S) then S := S - N;
Out(S)

受信者（Receiver）

図2

モンゴメリ法による乗剰余演算（N ＜ R ＝ 2r）

平文（Plaintext）
ASCII コード

平文（Plaintext）
ASCII コード
暗号文（Ciphertext）

P = C D mod MM）（E，（D，M）

暗号化鍵（Encription Key）
公開鍵（Public Key）

図1………………………………………
（3）

復号化鍵（Decryption Key）
秘密鍵（Private Key）

設計課題のシステム概要

これらの式から分かるように，暗号化器を設計することで同じ設計を復号化器に使うことができるわけです．

● モンゴメリ乗剰余演算法の採用
式（2）や式（3）は，数式としては単純です．しかし，累乗の計算を含んでいるため，実際にハードウェアに実装しことになりました．

ようとすると，そのまま計算したのでは計算量が大変多く● 審査結果なり，計算の途中のデータのけた数が膨大になってしまい「Design Wave 設計コンテスト 2008」の入賞者は以下のます．またmod の計算で必要になる除算は，計算の途中で方に決定しました．

何らかの判断を行う必要が出てくるので，乗算のようにストレートに効率良く処理することが難しいものです．

¡優勝 上原昭宏（冗長表現ビット・シリアル演算回路にそこで，上原氏，石井氏ともにモンゴメリ乗剰余演算法（Montgomery Multiplication ；以下モンゴメリ法）に着目

よる RSA 暗号回路の設計）¡準優勝 石井康雄（Scalable RSA Architecture）（敬称略）

し，設計に適用していました．
モンゴメリ法は二つの値を乗算し剰余を取る，乗剰余演算を行うアルゴリズムで，例えば図 2 のように表すことが賞品として，優勝の上原氏には，沖縄における発表会講できます．

演を兼ねた2 泊 3 日の沖縄旅行のほか，副賞のBlu-ray ビデ

少し調べてみると，乗剰余演算のアルゴリズムの研究はオ・レコーダ（パナソニック DMR-BW800-K）が，準優勝現在も盛んです．いかに小さな回路で高速に処理するかとの石井氏には 32V 型液晶テレビ（シャープ LC-32D10B）がいう観点から，今日でもいろいろな提案，報告が継続して贈られました．

行われています．また，実際に IP（Intellectual Property）コア製品として市場に出回っているRSA 暗号の暗号器，復● RSA 暗号の暗号化と複号化の手順
今年の Design Wave 設計コンテストの設計課題である号器でも，このモンゴメリ法を中心的なアルゴリズムとして利用しているものも多いようです．

RSA 暗号化器に実装する計算のアルゴリズムは，式で表現
すると大変簡素です．平文 P，暗号文 C，暗号化鍵 E，復号鍵 D，法 M のそれぞれが正の整数で表されているとき，以下の式で示される計算によって暗号化を行います．

C = P E mod M………………………………………
（2）

また，RSA 暗号を復号化する計算は以下になります．

● アーキテクチャの比較
最終的に審査に残った上原氏と石井氏の設計は，乗剰余演算にモンゴメリ法を採用した点では似通っていました．
両氏とも課題で与えられたビット長 32 にとどまらず，1024〜 4096 ビットの現実的なビット長にまで拡張可能な実用的な暗号器に仕上げています．そこで設計のアルゴリズムやDesign Wave Magazine 2008 June 10312