公開鍵暗号、特にRSA は、電子商取引の処理でますます重要性を増してきている。多くのデジタル・コンシューマ機器（例、セットトップ・ボックス、スマートカード）は現在、RSA法で暗号化したメッセージを送受信することが予想される。このようなメッセージのデコーディングではRSA暗号化処理が集中的に行われており、それを効率的に実現できれば大きなメリットがもたらされる。本論文は、ミップス・テクノロジーズがいかにしてプロセッサのハードウェアを変更することなくRSAアルゴリズムで4倍の高速化を達成したかについて述べる。

RSAが高速な処理速度を必要とする理由
公開鍵暗号は、二人の離れた者同士が、盗聴者に情報のやり取りを垣間見せることなく情報を共有できる唯一の手段として知られている。結果として、公開鍵暗号は、電子商取引や仮想閉鎖網（VPN）の運営にとり必須のものとなった。

RSAアルゴリズム（このアルゴリズムを発明した二番目のチームで、最初にこれを発表し特許を取得したRivest、ShamirおよびAdlemanの名前から名付けられた）は、今日最も広く利用されている公開鍵暗号システムである。

公開鍵暗号が抱える一つの問題に、大量の処理パワーを必要とするという点がある。これは、ギガヘルツのデスクトップ・コンピュータでさえ問題である。はるかに遅いプロセッサを採用しているのが普通である組込みシステムでは、これは深刻な問題となる。消費者は、単純に、ウェブサイトと秘密情報をやりとりする間長時間停止するようなデジタルセットトップボックスは受け入れないだろう。ユーザも、アクセス特権を確認するちょっと長い時間、スマートアクセス装置による（スマートカードとそれに付随する読取り器）雨が降っているような画像をぼんやりと見つめることになるだろう。

結果として、RSAの暗号化・復号速度は、様々な組込み装置にとり重要性を増してきている。本論文では、MIPS-based™ プロセッサの持つ64ビット能力を使ってこの速度を4倍にする方法を述べる。

RSA：簡単な紹介
暗号化システムには二つの種類がある。すなわち、共通鍵と公開鍵である。

共通鍵（または秘密鍵）暗号の概念は単純だ。メッセージの内容を隠すために鍵を使用し、それから隠したメッセージを他の人に送るというものだ。メッセージを隠すために使用するアルゴリズムは、DESやAES等、よく知られた規格にすることもできるが、最初の鍵を持っている受取人しか元々のメッセージを回復することができない。

共通鍵暗号アルゴリズムの課題は、電子商取引の場合のようにお互い一度も会ったことのない当事者間で鍵を安全に送るところにある。鍵がメッセージと共に送られる場合、それも暗号化しなければならない。また、それには第二の鍵も安全に送ることが要求され、同じ問題に戻ることになる。

公開鍵暗号は、異なった解決方法を採ることによりこの問題を解決する。公開鍵システムは、メッセージの暗号化と復号に異なる鍵を使用するかなり数学的なアルゴリズムである。暗号化されたメッセージを受け取りたい人は、暗号化と復号の一対の鍵を生成し、暗号化の鍵を公開する責任を負う。送り手は、この「公開鍵」を使ってその人へのメッセージを暗号化し、その人は、その人が（その人だけが）復号鍵を知っているためにそれを復号することができる。明らかに、二つの鍵は何らかの方法で関連していなければならないが、それらは、一つの鍵をもう一方の鍵から導き出すことが誰にもできないようにする方法で生成される。

RSAの暗号化はC＝Me mod nに、復号はM＝Cd mod nに基づく。ここで、Mはプレインテキストのメッセージ、Cは暗号化されたメッセージである。モジュラー巾（べき）乗法として知られる同じ基礎計算が、暗号化と復号の両方に使用される点に注目しよう。

システムの安全性は、モジュラー巾乗法のパラメータを導き出す方法から生じる。公開の巾数（e）は、素数でなければならないが、ある程度任意に選ぶことができ、17がよく利用される。法（n）は、二つの素数（通常pおよびqと呼ばれる）の積でなければならない。非公開の巾数（d）は、p、qおよびeから導かれる。

大きな数の素因数を導き出すことは、うまく行ったとしても困難であり、数字が大きくなるほど処置しにくくなる。このため、pとqが十分に大きな数であれば、最も速いコンピュータでさえ合理的な時間内にnを分解し非公開鍵を得ることは不可能である。現在、nは、512ビット、768ビット、または1,024ビットの数となるよう選ばれるのが普通である。このような大きな数では、pおよびqから公開鍵を導き出すためには、数十万台の高速コンピュータを用いた場合でも何年もかかる。

RSAの速度の押し上げ：Montgomeryアルゴリズム
モジュラー巾乗法を実行する従来の方法は、除法の反復に依っていた。除法は本質的に遅いプロセスであり、特に除数と被除数が大きい場合は、RSAの暗号化および復号は以前から非常に遅いプロセスであった。

1985年、Peter Montgomeryという研究者が、除法ではなく乗法と桁移動に依る便利なアルゴリズムを発明した。この革新は、速度を大きく押し上げる結果をもたらし、今日ではRSAの復号を行うための広く受け入れられた方法となった。

Montgomeryアルゴリズムの背後にある数学を説明することは本論文の目的を外れるが、それを実行するためのコードは、下記の疑似コードに要約される。Montgomeryのアルゴリズムは、参考文献1で説明されている。

通常、RSAアプリケーションでは、扱われる値は512ビットか1,024ビットの数字である（すなわち、k＝512またはk＝1,024）。モジュラー巾乗法の計算（ModExp）は、最初のいくつかの予備計算と、その後のMontgomery積関数（MonPro）と呼ばれるループの512回または1,024回繰り返しで構成される。

MonProで実行される最も重要なタスクは、大きな数字の3回の乗算である。rは2の巾乗と定義されるので、mod rの演算は自明であり、rで割る演算は単純な右送りである。最後の比較演算と除算演算は、大きな数字の計算を必要とするが、これらは乗算よりも簡単である。

Montgomery積計算
実際には、大きな数字のMonPro乗算および桁送りは、1セットのソフトウェアループによって実行することができる。下記の疑似コードは、最適化後のMontgomery積アルゴリズムの主要部分を示すものである（参考文献2より引用）。

この疑似コードでは、mの計算はかなり複雑なように見える。しかし、この場合は、見かけにだまされている。n'[0]の値は、単純にモジュラー巾乗法の始めにnから導かれる一つの単語である。Wはプロセッサの処理ワード幅に上手くはまる最大値であり、従って、mod Wの値の計算には全く努力は要らない。mの計算は単純な乗算演算である。

二つの内ループは、プロセッサが最も時間を使う部分である。どちらのループも同類であり、従って、この考察の目的に関し、私達は、第一のループのみの実施に集中することにする。

Montgomery積のMIPS32® -Based実装
CのMontgomery計算の第一の内ループを実施するために上記の疑似コードを使用すると、以下のコードが得られる。

このコードの中で、Mult32×32は、a[j]とb[i]の乗算のフル64ビットの結果をxとyに入れる関数（またはマクロ）である。この関数は、本論文において後にポータブルCで拡張される。ここでは、第一の内ループをどのようにMIPS32コードに実装できるかを考察する。

このループの命令の多くは、オーバーフローをチェックし、キャリービットを処理するものである。これらのオペレーションのいくつかは、下記に示す通り、積和命令を使い64ビットの乗算の結果に32ビットの値を足せば排除することができる。

最新のMIPSプロセッサ（MIPS32® 4KEm™ コアやMIPS64® 5Kc® コア等）では、乗算器のハードウェアは、1クロック・サイクルで積和演算を実行する十分な速さがあり、従って、この実装は、ループのパフォーマンスを改良するものとなる。乗算器のハードウェアがボトルネックになる場合、この最適化はパフォーマンスを実際に減らすこともあり得る。明らかに、この方法は、MIPS32 4Kp® コア等、乗算器の遅いプロセッサでは薦められない。

64ビットを利用した大きな数の計算
RSAで使用されるような512ビットや1,024ビットの数の計算は、プロセッサのレジスタとALUの幅に合ったチャンクに分割しなければならない。多くのオペレーションでは、処理ワード幅を二倍にすると計算を実行するために必要なステップ数は半分になる。そのため、64ビット・プロセッサはRSAの計算速度を二倍にすることができるという仮定は合理的である。

しかし、64ビット・プロセッサはロング加算、減算および比較の演算速度を二倍にする一方で、多くの部分を占める乗算演算の効果がより大である。64ビットの乗算を構成するには、実際には4回の32ビットの乗算と、部分積を合計するための数回の加算が必要である。従って、Montgomery積のような乗算に支配されるアルゴリズムでは、64ビット・プロセッサから期待される理論的な速度向上は4倍に近いものとなる。

この効果を分かりやすく示すため、下記の例で、32×32ビット乗算の64ビットの結果を計算するために必要なCコードを示す。32ビット以上を処理するポータブルCの文法はなく、従って、計算は4つの16ビット乗算に分割しなければならない。

Montgomery積のMIPS64-Based実装
4倍の高速化を達成することは理論的に可能であるが、現在のMIPSプロセッサでは、上記のMIPS32コードをMIPS64相当に翻訳するだけでは、完全な4倍高速化は達成されない。

この方法で完全な4倍の高速化を得るには、32×32の乗算を実行するのにかかるのと同じ時間で64×64の乗算を実行する能力を持った乗算器が必要である。それには4倍の数のトランジスタが必要となり、多くの組込みアプリケーションでは無理であろう。MIPS64 5Kcコア等、現状の実装では、32ビットの乗算を2サイクルで実施するが、64ビットの乗算では8～10サイクルかかる。

しかし、全ての手段が失われたわけではない。最も単純なMIPSプロセッサでもパイプライン・テクニックを使用している。これは、乗算の最中に他の命令を実行でき、乗算が完了する前に積が必要な場合にのみパイプラインをストールするテクニックである。これならば、プログラマは、乗算と平行して他の有用な演算をスケジュールする事ができる。

Montgomery積の計算の場合、乗算器が動作している間データ移動、加算およびループ維持のオペレーションがマシンを占め続けるように、内ループをアレンジすることが可能である。これにより、最近の64ビットMIPSプロセッサのほぼ全てが、フル64×64ビットの乗算器のシリコンを使うことなく、理論上の64ビット性能のピークに近づくことができる。

下記の例は、効率的にスケジュールを組んだ、Montgomery積の計算の第一内ループの64ビット実装を示す。

この例は、MIPS32について以前に示したものと似ているが、ここでは、ループは、乗算の結果をループの次の繰り返しまで使わないようにするため、ソフトウェアによるパイプライン処理を行っている。乗算の開始とその結果の使用の間に実行される12の命令は、乗算器ハードウェアの呼び出し時間を完全に隠してしまう。

この方法で乗算器の呼び出し時間をカバーすることにより、倍長の加算を実施するために積和演算を使用する機会が排除され、そのため、加算は遠回りで実行されなければならない。加算は乗算よりも通常速く、また安価であるため、交換条件としては良い条件である。

性能利得を測定する
私達は、64ビットのデータパスおよび乗算器の幅をどのようにしてMontgomery積の内ループに対し有効に行使できるかを考えた。これらがモジュラー巾乗法の計算を支配する範囲において、速度向上は、32ビット・プロセッサの4倍に近づくはずである。

下記のグラフは、このソフトウェアがMIPS 5Kcおよび20Kc™ プロセッサコアで動いている時に実際に達成された性能を比較したものである。比較のため、グラフは、MIPS32に適合したRSA Data Security Inc.のRSArefパッケージのコードを使用し、Montgomeryモジュラー巾乗法以外の関数の実行時間も示している。ランタイムは、ミップス・テクノロジーズのMIPSsim™サイクルアキュレート・シミュレータを使って得られたものである。

512ビットのモジュラー巾乗法を計算するためのサイクル数

1024ビットのモジュラー巾乗法を計算するためのサイクル数

これらの結果は、Montgomeryアルゴリズムが、モジュラー巾乗法の従来のアルゴリズムに対し大きな改善をもたらすことを示している。計算速度を約二倍にするのである。

MIPS32の結果は、最大の性能を引き出すためにソフトウェアのアルゴリズムを微調整する際にプロセッサの特性を考慮に入れることの重要性を証明している。5Kcプロセッサでは、倍長の加算に積和命令を使用すると、性能が約20％改善される。スーパースカラの20Kcプロセッサでは、積和演算はボトルネックになり、この最適化は実際には性能を減じる。この場合は別のテクニックが要求される。

MIPS64の結果は、64ビット・プロセッサでMontgomeryアルゴリズムを使用することの理論的な利益を確認するものである。MIPS 5Kcコアでは、MIPS32実装とMIPS64実装の間には3.5倍の性能差がある。MIPS 20Kcコアでは、向上は4倍である（20Kcコアに対し最適性が劣るMIPS32実装を使用すると5倍）。これらの結果を使えば、これらのプロセッサで動くフルRSA復号エンジンのスループットを見積もることができる。その見積りを下記のグラフに示す。

1024ビットのRSA復号（毎秒）

これらの見積りは、5Kcおよび20Kcプロセッサがそれぞれ366MHzおよび533MHzで演算処理を行っていること、およびRSA復号パッケージが"Chinese Remainder"を利用していることを仮定している。この定理は、結果を結合するためいくつかの簡単な算術を使い、1,024ビットのRSA復号処理を2つの512ビット・モジュラー巾乗に分割することを可能とする。

結論：Montgomeryおよび64ビットは大きな利得を生む
20年前にMontgomeryのアルゴリズムが紹介された時、旧来のアプローチに対し約2倍の高速化がもたらされた。それは、RSA暗号化・復号を実行する方法を完全に変えるものであった。それ以降、RSA問題に対する大きな改良はなかった。

今日、この問題に対し単に64ビット・プロセッサを応用することにより、わずかなソフトウェア面での努力でさらに4倍の高速化をもたらすことができる。暗号作成に関する専門知識は不要である。トランジスタ原価の急減によって32ビットと64ビット・プロセッサのシリコン原価の差はほぼ無くなったことを考えると、64ビット・プロセッサを選ぶことは、32ビット・プロセッサで効率的に動く新しいアルゴリズムを作り出すために大勢の数学者を雇うことに代わる経済的に賢明な代替法である。当然ながら、これらの数学者が考案するあらゆるアルゴリズムも、32ビット・マシンよりも64ビット・マシンでより高速に動くと思われる。

参考文献

C.K. Koc, "High-Speed RSA Implementation," RSA Laboratories, 1994
ftp://ftp.rsasecurity.com/pub/pdfs/tr201/pdf
C.K.Koc, T. Acar & B.S. Kaliski, "Analyzing and Comparing Montgomery Multiplication Algorithms," IEEE Micro, June 1996
http://www.security.ece.orst.edu/papers/j37acmon.pdf

Copyright©1998-2002, MIPS Technologies, Inc. All Rights Reserved. 「MIPS」は米国およびその他の国でMIPS Technologies, Inc.の登録商標、「MIPS-based」「MIPS32」「MIPS64」「4KEm」「4Kp」「5Kc」「20Kc」および「MIPSsim」は商標です。本文書で言及されているその他の商標は全て各所有者の財産です。

ご不明点・ご質問に関しましては、こちらまでお問い合わせください。

ホワイト・ペーパ
64-Bit Architecture Speeds RSA By 4x (.pdf) [U.S]