共用メモリ配線を有する暗号化プロセッサ
【課題】さまざまな秘密鍵および公開鍵の暗号化アルゴリズムを処理するようプログラム可能な暗号化チップを提供する。
【解決手段】暗号化チップは、演算処理装置のパイプラインを含み、該演算処理装置の各々は、秘密鍵アルゴリズム内の1ラウンドを処理することが可能である。データは、該演算処理装置間で、デュアルポートメモリを介して転送される。中央処理装置は、単一サイクルのオペレーションで、グローバルメモリからの非常に幅の広いデータ語を処理することができる。加算器回路は、比較的小さい複数の加算器回路を使用することによって簡素化され、合計およびキャリが複数サイクルでループバックされる。乗算器回路は、非常に幅の広い中央処理乗算器となるよう連結することができるように、より小さい演算処理装置乗算器を適用することによって、複数の演算処理装置と中央処理装置との間で共用することができる。
【解決手段】暗号化チップは、演算処理装置のパイプラインを含み、該演算処理装置の各々は、秘密鍵アルゴリズム内の1ラウンドを処理することが可能である。データは、該演算処理装置間で、デュアルポートメモリを介して転送される。中央処理装置は、単一サイクルのオペレーションで、グローバルメモリからの非常に幅の広いデータ語を処理することができる。加算器回路は、比較的小さい複数の加算器回路を使用することによって簡素化され、合計およびキャリが複数サイクルでループバックされる。乗算器回路は、非常に幅の広い中央処理乗算器となるよう連結することができるように、より小さい演算処理装置乗算器を適用することによって、複数の演算処理装置と中央処理装置との間で共用することができる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は高性能ネットワーク暗号化デバイスに関し、より特定的には、ハードウェアおよびソフトウェアの双方を組み込む暗号化デバイスに関する。
【背景技術】
【0002】
インターネットの出現以前は、企業のデータネットワークは典型的に、公共の電話会社からリースした専用遠隔通信ラインで構成されていた。このようなデータネットワークのハードウェア実装は、媒体上で絶対的な独占権を有する規制された公益企業であるその電話会社の独占的所有物であったために、セキュリティは大した問題ではなかった。その単一のプロバイダは、契約により安全が義務づけられ、また、中継ネットワークへの外部からのアクセスが不可能であったために、外部からのハッキングやタンパリングに対してかなり耐性があった。
【0003】
今日、ますます多くの企業がインターネットに価値を見出している。インターネットは現時点において、単一のコンピュータネットワークとしては世界中で最も広く展開しているネットワークであり、したがって、国際的な企業ネットワークに容易に利用することが可能である。インターネットはまた、消費者レベルの製品であるので、インターネットアクセスは通常、専用電話会社のネットワークによって提供される同じサービスよりもはるかに低コストで提供され得る。また、インターネットのエンドユーザに対する可用性によって、個人が家庭や他の遠隔地から企業のネットワークに容易にアクセスすることが可能となっている。
【0004】
しかしながら、インターネットは複数の株式会社によって運営されており、オープンプロトコルを用い、自由に調査可能なインバンドルーティングおよび制御の下に置かれている。このような環境は、ハッカーを育てるには絶好の土壌である。企業の諜報活動は今日では利益の多いビジネスであって、インターネット上でビジネスを行なう企業にとって、予防を怠ることは重大な損失を被ることにつながる。
【0005】
今日、インターネット上では、プライバシーおよび強力な認証のためのいくつかの基準が存在する。プライバシーは暗号化/復号化、すなわち解読、によって達成される。典型的に、暗号化/解読はメッセージ内容のプライバシーを維持しながらも当事者間でオープンチャネルを介してデータを転送することを可能にするよう設計されたアルゴリズムに基づいて行なわれる。これは、送信者が暗号化鍵を使用してデータを暗号化し、受信者が解読鍵を使用してそれを解読することによって達成される(ときに、暗号化鍵と解読鍵とは同一のものである)。
【0006】
暗号化アルゴリズムの種類
暗号化アルゴリズムは、公開鍵アルゴリズムと秘密鍵アルゴリズムとに分類することができる。秘密鍵アルゴリズムにおいては両方の鍵が秘密であり、これに対し、公開鍵アルゴリズムでは鍵のうち一方が公開されている。ブロック型暗号は、今日使用されている秘密鍵暗号システムの代表である。通常、ブロック型暗号については、暗号化鍵と解読鍵とは同じものである。ブロック型暗号は、データのブロック、典型的には32〜128ビットを入力として受取り、同じ数のビットを出力として生成する。暗号化および解読は、長さが56ビットから128ビットの間である鍵を使用して行なわれる。この暗号化アルゴリズムは、鍵を知らなければメッセージの解読が非常に困難なものとなるように設計されている。
【0007】
インターネットのセキュリティプロトコルにより、ブロック型暗号に加えて、公開鍵アルゴリズムが多用されている。PogueおよびRivestに発行された米国特許番号第5,144,667号に記載の、Rivest, Shamir, Adelman(RSA)暗号システム等の公開鍵暗号システムは、2つの鍵を使用し、そのうち一方のみが公開されている。ある人物が鍵を公開すると、他の誰もがその鍵を使用して秘密のメッセージをその人物に対して送信することができるが、そのメッセージは秘密鍵を使用しなければ解読することができない。このような公開鍵暗号化の利点は、会話を行なう前にすべての相手に対して秘密鍵を配布する必要がないことである。これに対して、もし秘密鍵の暗号化のみが使用されるようであれば、メッセージを受信する予定の各相手先に対して1つずつ、合せて多数の秘密鍵を生成せねばならず、またそれらすべての秘密鍵を1つずつ個別に配布せねばならなくなる。秘密裡に秘密鍵を送信しようと試みる場合、秘密鍵暗号化のみを使用してメッセージそのものを送信する場合と同じ問題が生じることになる。このような問題を、鍵の配布問題(key distribution problem)と呼ぶ。
【0008】
鍵の交換は、公開鍵技術の別の応用例である。鍵交換プロトコルにおいて、当事者間の会話が第三者によって傍受された場合にも、当事者間は秘密鍵で対処することが可能である。米国特許番号第4,200,770号に記載されているDiffie-Hellman指数関数鍵交換は、そのようなプロトコルの一例である。
【0009】
RSAやDiffie-Hellman指数関数鍵交換等の、大半の公開鍵アルゴリズムは、モジュラ指数関数に基づいており、この関数は、αxmodPを計算するものである。この式は、「αをx乗し、その解をpで除して、剰余を得る」ことを意味する。このような計算を行なうには非常にコストがかかるが、それは以下の理由による。すなわち、この演算を行なうために、多数の乗算および除算を繰返す必要がある。ただし、1985年4月の、Mathematics of Computation, Vol. 44, No. 170の「試行除算を行なわないモジュラ乗算(“Modular Multiplication Without Trial Division”)」に記載のモンゴメリーの法(Montgomery's method)等の技術によれば、必要とされる除算の数を減じることができる。加えて、使用される数も非常に大きく(典型的に1024ビット以上)、したがって、一般のCPUに見られる乗除命令を直接使用することができず、代わりに、そのような大きな乗算および除算を、1つのCPUで行なうのに十分小さい演算へと分割する、特別なアルゴリズムを使用せねばならない。また、そのようなアルゴリズムの実行時間は通常、関連する機械語の数の二乗に比例する。これらの要因により、大きな数の乗算はその演算が非常に遅いものとなる。たとえば、Pentium(登録商標)は、1回の32×32ビット乗算を10クロックサイクルで行なうことができる。2048ビット数は64個の32ビット語で表わすことができる。2048×2048ビット乗算には、64×64回の別個の32×32ビット乗算が必要であり、この乗算のためにこのPentium(登録商標)上では40960クロックが必要となる。2048ビット指数を用いる指数関数は、通常の方法では最高で4096回の乗算を必要とし、これには約1億6700万クロックサイクルが必要となる。このPentium(登録商標)が166MHZで動作するとすると、この演算全体でおよそ1秒かかることになる。驚くべきことに、この例では除算にかかる時間は一切考慮されていないのである。明らかに、Pentium(登録商標)等の一般的なCPUで鍵の生成および交換を行なうことはほとんど期待することはできない。
【0010】
公開鍵アルゴリズムは、計算が非常に面倒なので、典型的にメッセージ全体を暗号化するのには使用されず、代わりに、プライベート鍵暗号システムがメッセージの転送に使用される。メッセージの暗号化に使用されるプライベート鍵はセッション鍵と呼ばれ、この鍵が無作為に選ばれて公開鍵を用いて暗号化される。暗号化されたセッション鍵は暗号化されたメッセージとともに相手先に送信される。相手先は、自身の秘密鍵を用いてセッション鍵を解読し、その時点で、そのセッション鍵を用いてメッセージを解読することができる。各通信には異なるセッション鍵が使用されるので、もし1つのセッション鍵が破壊されたとしても、読むことができるメッセージはそのセッション鍵を使用して暗号化された1つのメッセージのみである。この公開鍵/プライベート鍵の方法はまた、双方向端末セッション等の、通常動作時には決して終了することのない連続的な通信を保護するのにも使用することが可能である。この場合、セッション鍵は、公開鍵生成技術を繰返すことによって周期的に(たとえば1時間ごとに)変更される。やはり、セッション鍵を頻繁に変更することによって、暗号化が破られたとしても犠牲となるデータ量は制限される。
【0011】
先行技術
ソフトウェアをベースとした解決法を用いて企業のネットワークへのアクセスを可能にする、ネットワークレベルの暗号化デバイスが広く使用されている。Raptor Eagle Remote等の製品は、暗号化をすべてソフトウェアで行なっている。ソフトウェアは、暗号器のスループットを制限する。公開鍵技術を用いたセッション鍵の生成には数分かかることもある。この理由のために、セッション鍵の再生成はある人々が望むほどには頻繁には行なわれない。しかし、ソフトウェアは、その分野における開発に応じて、暗号化アルゴリズムを容易に変更することができるという利点を有する。
【0012】
他のデバイスは、ハードウェアとソフトウェアとの組合せを使用する。たとえば、Northern Telecom(現在のEntrust)のSentinel X.25暗号化製品は、AMDによって製造されたDESチップを使用して、DES秘密鍵の暗号化を行なう。DESはハードウェアで効率的に実装されるように設計されたものなので、ハードウェア実装の方がはるかに高速である。ソフトウェアにおいては多くのCPU命令を要する転換を、並列の専用ルックアップテーブルおよび配線を使用して行なうことが可能である。
【0013】
Sentinelはまた、Motorola DSP56000プロセッサを使用して、公開鍵演算を行なう。当時、DSPの単一サイクルの乗算能力のおかげで、この方法によって、一般的なCISCマイクロプロセッサで公開鍵アルゴリズムを実現するよりもはるかに高速で演算ができるようになった。
【先行技術文献】
【特許文献】
【0014】
【特許文献1】米国特許番号第5,144,667号
【特許文献2】米国特許番号第4,200,770号
【発明の概要】
【発明が解決しようとする課題】
【0015】
大半のハードウェア暗号化デバイスにおいては、それによって実現することのできるアルゴリズムの数が大幅に制限されている。たとえば、Sentinelにおいて使用されるAMDチップは、DESのみを実行する。Hi/Fnによるより最近のデバイスでは、DESおよびRC4を実行することができる。しかし、RC5またはIDEAを実現したい場合には、別の製品を用いねばならないであろう。
【課題を解決するための手段】
【0016】
発明の概要
好ましい高性能プログラマブルネットワーク暗号化デバイスは、単一チップ内に集積され、これは、その命令の組が共通の暗号化アルゴリズムに対して最適化された、並列パイプライン式のプロセッサシステムである。本発明は、ハードウェアおよびソフトウェアの両方の方法の利点を実現する。該プロセッサはプログラマブルプロセッサであるため、どのような暗号化アルゴリズムも実現することが可能であり、これは、1つのアルゴリズムのみを実行するよう設計されるハードウェア実装の暗号化プロセッサとは対照的である。しかし、このプロセッサのアーキテクチャは、暗号化に有益な特性である並列計算を可能にしているので、その性能は、専用ハードウェアデバイスの性能により近づく。
【0017】
本発明の好ましい実現例に従えば、電子暗号化デバイスは演算処理装置のアレイを含む。各演算処理装置は、暗号化アルゴリズムの1ラウンドを記憶するための命令メモリを含み、該ラウンドは、命令の1シーケンスを含む。該演算処理装置はまた、命令メモリからのラウンドを実現するためのプロセッサ、ならびに、暗号化データオペランドおよびラウンドを実現することによって得られる暗号化されたデータを記憶するためのデータ記憶装置を含む。該アレイの各演算処理装置は、複数のラウンドのうち1つを実現し、その結果を連続する演算処理装置へと転送し、それにより、該演算処理装置のアレイは演算処理装置のパイプラインにおいて暗号化アルゴリズムの連続的なラウンドを実現する。
【0018】
好ましい実施例においては、該データ記憶装置はその一部分が該線形アレイの隣接する演算処理装置間で共用されており、該線形アレイの隣接する演算処理装置間でデータを転送するのに使用される。該共用データ記憶装置は好ましくは、デュアルポートメモリで構成されるが、これはまた、共用レジスタを含んでもよい。
【0019】
好ましい演算処理装置は、制御ユニットおよびALUを含む。制御ユニット、ALU、命令メモリおよびデータ記憶装置は、ローカルデータメモリおよび共用データメモリも含めて、ローカル演算処理装置バスに接続される。このローカルバスはスイッチによって区分されて、命令メモリおよび制御ユニットを接続するローカル命令バス区分と、ALU、ローカルデータメモリおよび共用データメモリを接続するローカルデータバス区分とに分けられる。該スイッチは、該2つのローカルバス区分上で別個に同時に演算ができるようにするか、または、それら2つのバス区分の間で通信ができるようにする。各演算処理装置はさらに、その演算処理装置内で乗算演算を行なうための乗算器を含む。
【0020】
好ましい暗号化デバイスはさらに、グローバルランダムアクセスメモリおよびグローバルバスを含み、データは該グローバルランダムアクセスメモリと演算処理装置のデータ記憶装置との間で該グローバルバスを通じて転送される。中央処理装置は、このグローバルバスに結合されて、演算処理装置によって処理されるデータ語よりも幅の広いデータ語を処理する。複数の演算処理装置のそれぞれの乗算器は、中央処理装置によって使用されるより幅の広い乗算器の区分として連結できるようにされ得る。好ましくは、各乗算器は部分積加算器を含み、該加算器は、個別の乗算器として動作しているときには第1の入力の組を選択し、かつ、連結されているときには隣接する演算処理装置からの入力を含む第2の入力の組を選択するための、入力選択回路を有する。
【0021】
好ましくは、中央処理装置は新規な加算器を含む。該加算器において、複数加算器区分の各々はキャリ出力および合計出力を有し、それら加算器区分の各々は、2つあるオペランドの各オペランドの1区分を処理する。選択器は、加算器サイクル中にキャリが得られる限り、連続するクロックサイクル中、該キャリ出力を連続する加算器区分へのキャリ入力として選択する。選択器はまた、各合計出力を同じ加算器区分へのオペランド入力として選択する。したがって、加算器サイクル中にキャリが得られる限り、ある加算器の合計出力はその入力にフィードバックされ、また該加算器区分は先行するサイクルにおいて先行する区分からキャリ出力として生成されたキャリ入力を受取ることになる。
【0022】
好ましくは、各演算処理装置は、除算回路を用いずにMmodNを計算する、モジュラ調整演算を行なう。各演算処理装置はまた、A±BmodNを計算するモジュロ加算/減算演算を行なう。さらに、各演算処理装置は、A×BmodNを計算するモジュロ乗算演算を行なう。
【図面の簡単な説明】
【0023】
【図1A】本発明の可能な応用例のブロック図である。
【図1B】本発明の可能な応用例のブロック図である。
【図2】本発明を用いた暗号化チップのブロック図である。
【図3】図2の暗号化チップにおける演算処理装置のブロック図である。
【図4】図2および図3に示した回路の好ましいチップレイアウトを示す。
【図5】図4に示したレイアウトに対応するように書き直された図3の演算処理装置ならびに、PEローカルバスおよびグローバルバス接続を示す。
【図6】図2のPK ALUにおいて使用される加算器回路を示す。
【図7】PK ALUの乗算器において使用される全加算器の符号を示す。
【図8】全加算器を使用する4×4乗算器の第1段における処理を示す。
【図9】4×4乗算器の3つの段を示す。
【図10】4×4乗算器の加算器がその上に重ねられた、幅の広い乗算器の加算器を示す。
【図11】図10に示した広い語長の演算器において、同様の乗算器と連結されるように適合された、4×4乗算器のブロック図である。
【図12】全加算器を使用する8ビット加算器の従来技術による実現例を示す。
【図13】キャリ先見型加算器の従来技術による実現例である。
【図14】DES暗号化ラウンドをブロック図で表現したものである。
【図15A】本発明の実施例に従ったモジュラ加算演算を示す機能図である。
【図15B】本発明の実施例に従ったモジュラ減算演算を示す機能図である。
【図15C】本発明の実施例に従ったモジュラ調整演算を示す機能図である。
【図15D】本発明の実施例に従った3つすべてのモジュラ演算の組合せを示す機能図である。
【発明を実施するための形態】
【0024】
詳細な説明
本発明の上記および他の目的、特徴および利点は、添付の図面に示される本発明の好ましい実施例に関する以下のより詳細な説明から明らかとなるであろう。添付の図面においては、複数の図面を通じて、同じ部分には同様の参照符号が付される。図面は必ずしも一定の比で描かれているわけではなく、本発明の原理を説明するために強調されている部分を含む。
【0025】
本発明の暗号化チップは、任意のアプリケーションにおける1または複数のデータストリーム上で、共通のデータ暗号化および復号化、すなわち解読、のアルゴリズムを行なうようプログラムすることが可能である。この暗号化チップの主要な目的は、インターネット上でその使用が想定されるアルゴリズムを用いて、100〜2000Mbpsのデータレートで、高速データ暗号化を行なうことである。
【0026】
アプリケーションの例を図1Aおよび図1Bに示す。図1Aにおいて、ソース22からのデータが、暗号化チップ24で暗号化された後に公衆ネットワーク26に渡される。データはその後、暗号化チップ28内で解読されて、宛先30に送られる。一実施例においては、このソースおよび宛先自体が、ローカルエリアネットワーク等のネットワークである。そのような場合、これら暗号化チップが、ローカルエリアネットワークと公衆ネットワーク26との間に安全な経路を提供する。
【0027】
図1Bに示されるリンク暗号化アプリケーションにおいては、各リンク内でルータ間で転送されるデータが暗号化される。この場合、リンクとリンクの間にあるルータ32に入力された暗号化データは、暗号化チップ34でまず解読されねばならず、またそのデータは、暗号化チップ36において、次のリンクの暗号化アルゴリズムに従って再度暗号化される。
【0028】
今日、DES、RC5およびIDEAという3つの主要な秘密鍵ブロック型暗号化アルゴリズムが一般に使用されている。最初の2つのアルゴリズムは、標準的なインターネットプロトコルセキュリティ(Internet Protocol SECurity)の略である、IPSEC標準アルゴリズムである。IDEAは、広く利用されている電子メール暗号化プログラムであるPGPによって使用されるアルゴリズムである。
【0029】
典型的に、ブロック型アルゴリズムは、多数のラウンドで構成され、各ラウンドは、暗号化アルゴリズムにおける演算の1シーケンスである。暗号化アルゴリズムを完全に実現するには、8〜32ラウンドが必要とされる。各ラウンドによって行なわれる演算は、しばしば同じものであるが、同じものでなくてもよい。ソフトウェアにおいては、各ラウンドは少数の機械命令で実現される。ハードウェアにおいては、各ラウンドは専用回路で実現される。ハードウェアは典型的にパイプライン化されており、各ラウンドは自身に該当するパイプライン段において実現される。
【0030】
図2は、本発明の一実施例に従った、集積チップの解決法を図示する。これを今後、暗号化チップと呼ぶ。暗号化チップと呼ぶと、そのチップが暗号化を行なうことができることが示唆されるが、このチップが復号化、すなわち解読、およびメッセージダイジェスト機能もまた行なうことに留意されたい。
【0031】
データは、ネットワークデータを受取る入力段40を介して、典型的にはシリアルビットストリームとして暗号化チップに入力される。イーサネット(登録商標)、ATMまたは他のどのような直列化フォーマットも使用することができる。入力段はこのシリアルデータストリームを、暗号化/解読パイプラインへの入力として処理するのに好適な、ブロック整合されたデータへと変換する。入力ブロックのサイズはプログラム可能である。図2に示した好ましい実施例においては、パイプラインは線形アレイに配された複数の演算処理装置37からなり、各演算処理装置は、命令メモリ、レジスタファイル、ALU、ローカルおよび共用データメモリ、ならびに制御回路を含む。演算処理装置の各々は、32ビット幅のデータ語を処理するよう設計されている。暗号化されたデータは、該パイプラインの最後の演算処理装置から取出されて出力段42に渡され、出力段42がそのブロックデータをシリアルストリームフォーマットに戻して、そのデータをネットワークを介してまたは局所宛先へと送る。
【0032】
データは、グローバルデータバス38を介して、暗号化チップ内の隣接しない演算処理装置間および/または他の装置間で転送することができる。グローバルデータバス38にはまた、I/O通信ロジック54が接続されており、このロジック54が、ホストCPU(図示せず)との通信を可能にする。ホストCPUとの通信は、暗号化チップを使用前にプログラムするのに必要である。グローバルランダムアクセスメモリ(RAM)44もまたグローバルデータバス38に接続され、それにより、演算処理装置間でグローバルな通信が可能となっている。制御CPU52は、暗号化パイプラインプロセッサの動作を同期化する。このCPUは、MIPS、ARMまたはARC等の、利用可能ないずれの組込み型CPUコアを使用しても実現することができる。さらに、公開鍵暗号化アルゴリズムのように非常に幅の広いオペランドを利用するアルゴリズムを処理することができるように、公開鍵(PK)コアプロセッサ46が制御CPU52に接続されている。PKコアは、8個から16個の512ビット幅のレジスタからなるレジスタファイル48、およびPK ALU50を含む。PKコアプロセッサは、1システムクロックサイクルで、512ビットバスを介してグローバルRAM44との間でデータの送受信を行なうことができる。512ビットのオペランドは、典型的には2〜32クロックサイクルで、ALU50内で処理される。PKコアALU50は、制御CPU52によって制御されるコプロセッサであって、ローディングおよび記憶の他には、算術および論理演算のみを行なう。PKアルゴリズムを実現するのに必要な他の命令は、制御CPU52内で実行され得る。
【0033】
この暗号化チップは、秘密鍵アルゴリズムの各ラウンドのためのコードを、パイプラインの別個の演算処理装置内で実現する。計算が終わると、1つのPEからのデータは次のPEに転送され、そこで次のラウンドが実現される。第1のPEはその後、入来するデータの次のブロックのための暗号化ラウンドを処理することができるようになる。パイプライン処理は残りのPEにおいて続けられる。このアーキテクチャを用いて1つのブロックを暗号化するのに必要とされる時間は、したがって、1つのラウンドを暗号化するのに必要とされる時間に等しい。
【0034】
多くのブロックアルゴリズムは、データを暗号化するのにある演算の組を使用し、鍵を拡張するのに別の演算の組を使用する。鍵の拡張は、比較的小さい鍵(56〜128ビット)を、統計的に無作為の性質を有するより大きい数(512ビット以上)の鍵へと変換するプロセスである。こうして拡張された鍵は、より小さなサブ鍵に分配され、拡張された鍵の異なる部分が各々異なるラウンドのために使用される。拡張された鍵がデータによって変化しないことに注目することが重要である。したがって、これはクリティカルパス内にはないため、予め計算してメモリに記憶しておくことができる。後に説明するコードの例は、鍵情報が予め計算されて各PEのローカルデータメモリ内に記憶されているものと仮定している。
【0035】
ブロックアルゴリズムの基本的なアプリケーションは、平文(暗号化されていない情報)のブロックを同じサイズの暗号文(暗号化された情報)のブロックに変換したり、その逆を行なう。この動作モードは、電子コードブック(ECB)モードとして知られているが、これはセキュリティに関して多くの固有の弱点を有するので、基本的な出力のいくつかを入力に戻るよう巡回させることによって暗号化にフィードバックを導入する方法が一般に使用されている。この暗号化チップは、グローバルデータバス38を利用して暗号フィードバック(CFB)を行なう。ECBモードにおいては、データの新しいブロックを各パイプラインサイクルにつき1回暗号化することができる。これは10〜100個の命令であり得る。しかし、CFBモードにおいては、各データはパイプラインを多数回通過せねばならない。このモードは単一チャネル上のスループットを大幅に減じるが、パイプラインにおいてインターリーブされている多数のデータチャネルを暗号化することによって、ピーク性能を達成することができる。
【0036】
本発明の一実施例に従った1つの演算処理装置PEのブロック図を図3に示す。演算処理装置37は、8〜16個の32ビットレジスタで構成されたレジスタファイル58から得られる32ビット語の演算を行なう、ALU56を含む。レジスタファイル58およびALU56は、制御ユニット60によって制御される。制御ユニット60は、演算処理装置命令メモリ62からの命令をデコードする。各演算処理装置命令メモリは暗号化アルゴリズムの少なくとも1つのラウンドを記憶し、ここで1つのラウンドとは、暗号化アルゴリズムにおける命令の1シーケンスと定義される。各演算処理装置がアクセスすることのできるPEデータメモリスペースは、4つの領域に分割される。すなわち、ローカルPEメモリ64(図3においてはPEnローカルメモリ)、共用メモリ66(図3では、n番目の演算処理装置とn−1番目の演算処理装置との間で共用される、PEn,n-1共用メモリ)、第2の共用メモリ68(図3では、n+1番目の演算処理装置とn番目の演算処理装置との間で共用される、PEn+1,n共用メモリ)、および、図2を参照して説明した、すべてのPEがアクセス可能なグローバルメモリ44、の4つの領域である。これらのメモリはすべて、1つの演算処理装置、たとえばn番目の演算処理装置のアドレススペースにマップされる。どの種類のメモリにアクセスするのにも、特別な命令は必要ない。すべてのメモリはすべてのメモリアクセス命令によってアクセス可能である。
【0037】
1つの演算処理装置のメモリ66および68は、デュアルポートSRAMであって、これらはそれぞれ、先行する、すなわち前隣りのパイプ段および、次の、すなわち後ろ隣りのパイプ段と共用される。あるPEにとっての後ろ隣りのPEとの共用メモリは、次のPEにとっての前隣りのPEとの共用メモリと同じものであることを理解されたい。
【0038】
これらのデュアルポートのSRAMは、パイプライン段を通じてデータを伝搬するのに使用される。ある演算処理装置が、転送されるべきデータをそれに関連する後ろ隣りの装置との共用メモリに書込む。すると、その記憶されたデータを、該当する後ろ隣りの演算処理装置が、自身の前隣りの装置との共用メモリから読出す。ここで、前隣りの装置との共用メモリとは、上述のように、先行する演算処理装置にとっての後ろ隣りの装置との共用メモリと同一無二のメモリを指す。これらのメモリはデュアルポートメモリであるため、アクセスにはタイミングの制限がない。アクセスの同期化は、ソフトウェアの作者または編集者による機械命令の静的なスケジューリングを用いて行なわれる。さらに、隣接するPE間の通信にグローバルバスを使用しないので、PEはすべて同時に通信することが可能である。
【0039】
グローバルメモリ44はグローバル通信バスに接続される。任意の時間にグローバルメモリ44にアクセスが許可されるのは1つの演算処理装置のみである。このメモリは、たとえば、フィードバック暗号化アルゴリズム中に、隣接していない演算処理装置間でデータをやりとりするのに使用され、また、個々の演算処理装置のための補助記憶装置としての役割を果たす。
【0040】
PE命令メモリ62は、現代のRISCプロセッサの整数ユニットのそれに似た、命令の組を有する。この命令の組は、どのレジスタもどの命令に対するオペランドとしても使用することができるという点で、いくぶん直交性である。浮動小数点やメモリ管理サポートは、どちらも暗号化には有益ではないので、設ける必要はない。しかし、この命令の組は、以下の有益な追加機能を含む。すなわち、モジュラ加算/減算命令、モジュラ乗算命令およびモジュロ調整命令、である。
【0041】
モジュラ加算/減算命令は、A±BmodNを計算する(「MmodN」の数はMをNで除した際の剰余である)。図15Aから図15Dは、モジュラ加算、減算および調整を、1つのスリーインワン(3-in-1)モジュロ算術ユニットに組合せた例を示す。
【0042】
図15Aは、モジュラ加算演算を示す。加算すべき2つの数AおよびBが双方ともNよりも小さければ、加算器120からのそれらの合計を、Nを法として減じることができる。すなわち具体的には、減算器122においてNを減じ、その後、その差の符号に応じて、マルチプレクサ124を介して、減算器の出力または元々の数のいずれかを選択する。同様に、図15Bに示すモジュラ減算演算の場合には、2つの数AおよびBがNよりも小さい場合には、Nを法とするそれらの差を計算することが可能である。これは具体的には、減算器128からの差が負であれば加算器126においてNを加算し、その差が正であればマルチプレクサ130を介してその差を選択することによって、行なわれる。ここで、モジュロ加算およびモジュロ減算がいずれも除算を必要としないことに注目されたい。しかし、それらは、連続2回の加算を必要とする(そのうち1つは合計/差を計算するもの、もう1つはNを法として減算するものである)。このような2回続けての加算がクリティカルパスに打撃を与える場合には、Nを法とする減算は、別個の命令としてエンコードすることが可能であり、これを「モジュロ調整」命令と呼ぶ。
【0043】
図15Cに示すこのモジュロ調整命令は、AおよびBの両方が既にNを法として減じられていて、MがAとBとの合計または差のいずれかであるものとして、MmodNを計算する。Mが負である場合、ロジック132は、加算器/減算器134においてMにNを加えて、マルチプレクサ136を介して結果が生成されるようにする。Mが正である場合には、ロジック132は、Nの減算を行ない、その差が正であればその差を返し、その差が負であればMを返す。この命令は、合計および差の命令と関連づけて使用することが可能であり、それにより、モジュラ加算/減算命令が不要となる。
【0044】
図15Dにおいて、スリーインワンの算術ユニットは、モジュロ加算、モジュロ減算およびモジュロ調整を、各演算処理装置内で実現される単一のユニットに組合せる。1つの命令(モジュラ加算、減算または調整)および最上位ビット(MSB)の符号入力に応答するロジック144の制御下で、加算器/減算器138は装置120および128のいずれかの機能を行ない、加算器/減算器140は、装置122、126および134のうちいずれかの機能を行なう。マルチプレクサ142は装置124、130および136に対応する。モジュロ調整演算において、MがA入力に印加され、B入力はゼロにセットされる。この組合せユニットは、速度は落ちるが、面積効率は最も高い。この組合せユニットはまた、Mathematics of Computation, Vol. 44, No. 170, April 1985, pages 519-521の、ピーター・L・モンゴメリー(Peter L. Montgomery)による「試行除算を行なわないモジュラ乗算」に記された、試行除算を行なわないモジュラ乗算のためのモンゴメリーの法を実現するのに有益である。
【0045】
モジュラ加算および減算は、従来技術によるプロセッサにおいてわずか2〜3個の命令で実現することができるが、これらの命令を暗号化チップの命令の組の特別な関数として含むことで、特定的な暗号化アルゴリズムの場合においては、わずかながら高速化につながる。
【0046】
モジュラ乗算命令は、A*BmodNを計算する。この命令に使用される乗算器は、下により詳細に説明する。暗号化チップは、後に明らかとなるであろう理由によって、全体のモジュラ乗算命令を提供することができる。
【0047】
表1は、以下の例において使用される、PEの命令の組の代表的な例を示す。他の従来技術によるRISC命令もまた実現することが可能である。
【0048】
【表1】
【0049】
レイアウトの課題
暗号化チップの一般的なレイアウトを図4に示す。ここでは、16個の演算処理装置および、512ビット幅の公開鍵PKコアユニットを想定する。ここで512ビットのPKコア語幅を選択したのは、そのレイアウトが容易であるためである。たとえば1024ビット幅は、より広いシリコン面積を必要とするであろうが、性能は倍加するであろう。
【0050】
個々の素子は、図2および図3に示した素子に匹敵し得る。16個の演算処理装置が、レイアウトの大きな領域内で左下側に1列に線形に配されており、その1つが詳細に示されている。図中、共用乗算器素子70は、図示された演算処理装置に関連づけて示されている。前述のように、32×32乗算器区分70は、各演算処理装置と関連づけられて、それぞれの演算処理装置内で32ビット乗算を行なう。これに代えて、乗算器素子70は、公開鍵ALU50のための幅の広い512×32ビット乗算器として機能するように、連結することも可能である。公開鍵PK ALU50は、秘密鍵SK素子の右側に配置され、上述のような演算処理装置で構成されている。PK ALUの隣りに、PKレジスタファイル48が配される。PK ALU50およびPKレジスタファイル48は併せて、図2において46で示されたPK処理コアを形成する。PKコアの右側には、グローバルメモリ(RAM)44が配置される。チップの上辺に沿って、制御CPU52、通信ロジック54および入出力処理ブロック40、42が配置される。グローバルデータバス38は、SK素子、PKコア46、グローバルRAM44、通信ロジック54および制御CPU52を繋ぐ。
【0051】
ローカルバス接続を含む典型的な演算処理装置のレイアウトを図5に示す。1つの演算処理装置のすべての構成要素は、ローカル演算処理装置データバス72を介して通信することができる。このバス72は、メモリとレジスタとの間のすべての転送を扱う。ここで、次に隣接するPEとの共用PEメモリ68は、図示されている演算処理装置の他の素子と直列に(in-link)配されており、これに対し、先に隣接するPEとの共用PEメモリ66は、先に隣接する演算処理装置の素子と直列に配されていることに注目されたい。プログラミングおよびテストの目的のために、すべてのPEメモリはグローバルバス38からアクセス可能である。スイッチ74は通常、ローカルバス72をグローバルバス38から切離しているが、ローカルRAM64とグローバルRAM44との間でデータ転送を可能にするように選択的に閉じることが可能である。別のスイッチ76は、ローカルバス72を独立した2つの区分に区分けすることを可能にし、これにより、制御ユニット60は、バス72上のデータ転送と同時に、RAM62から命令を読出すことが可能となる。このように、演算処理装置内の動作は、ある命令がPE ALU56内で実行されている間に次の命令が制御ユニット内で処理されるというように、パイプライン化することが可能である。暗号化コードの実行中、スイッチ74および76は通常は開かれており、これにより、命令RAMからの命令フェッチを、データメモリおよびレジスタファイルからのデータフェッチと同時に進めることができる。
【0052】
多数のマルチプロセッサアーキテクチャが提案されているが、それらの大半は、汎用マルチプロセッシングのために設計されている。このため、演算処理装置間の通信は通常、あるPEから別のPEへとデータを切換えるよう動的に構成することが可能な、切換マトリックスを使用して行なわれる。これらのスイッチの設計は非常に複雑である。このようなスイッチは暗号化には不要であるため、本発明の実施例においては、切換回路が大幅に減じられた、より簡単なPEの線形配列を用いている。
【0053】
加えて、相互配線技術として、文献に記載されているようなI/Oポートを使用するのではなく共用メモリを使用していることにより、はるかに簡単かつはるかに強力なプログラミングモデルが生成される。ここで、2つのPE、AおよびBが単一の32ビットI/Oポートに接続されているものとする。AがBに対してデータの複数語を転送するためには、Aは各語をI/Oポートに書込んで、Bがそれを読出すのを待たねばならない。これに対し、AおよびBが、通信のすべての語を保持するのに十分な大きさの共用メモリによって接続されている場合には、AはBが読出すのを待つことなくそのデータを書出すことが可能である。さらに、PE Bはどのような順序でもそれらの語を読出すことができ、また、そのデータから、進行中のジョブに応じて適宜、必要なものをピックアップして選択することもできる。最後に、共用メモリのうちあるメモリが通信に不要である場合には、そのようなメモリはローカルメモリの延長として使用されて、付加的なローカルワークスペースを提供することができることに注目されたい。
【0054】
公開鍵サポート
効率的な公開鍵暗号化のためには、公開鍵コプロセッサによって提供される効率的なモジュラ指数関数が必要である。このユニットは、以下の項目を含む。すなわち:・16個の512ビット幅のレジスタで構成される、PKレジスタファイル48・連結されたSK乗算器素子からなる、PK512×32ビット乗算器70(このユニットは、わずか32クロックサイクルで1つの512×512乗算を行なうことができる)・PK512ビット加算器ALU50、これは、2〜16サイクルで、典型的には2サイクル以下で、加算を行なうことができる・単一クロックサイクルで512ビット語をロードおよび記憶するために、PKコプロセッサからの512ビット並列アクセスのために構成される、グローバルメモリ44。
【0055】
PKコアプロセッサは、モジュラ乗算を512ビット語を使用して行なうことによって加速する。本発明のPKユニットを用いる512×512乗算演算は、下に説明する16個の演算処理装置を連結した乗算器素子を用いて、16個の512×32乗算を行なうことによって実現されるであろう。各乗算につき2クロックサイクルが必要とされかつそのような乗算が16回必要とされると仮定すると、1回の512×512乗算に必要なのは32クロックサイクルであり、1回の2048×2048乗算はわずか512クロックサイクルで行なうことができることになる。4096回の乗算を必要とする全体のモジュラ指数演算は、合計200万クロックサイクルを要することになるが、これは、先に説明したPentium(登録商標)の例に比べて80倍の改良を意味する。PKアルゴリズムにおいても同様の性能の改良が期待される。これは、先行技術に比べて大幅な性能の向上を意味し、セッション鍵をより頻繁に変更することが可能になって、セキュリティが向上することを意味する。
【0056】
512ビット加算器
加算器は、公開鍵PKユニットと秘密鍵SKユニットとの間で共用されることはない。加算演算および論理演算がPKおよびSKの双方において共通であるので、各ユニットは自身の加算器を有し、したがって、演算を同時に進行することが可能である。
【0057】
公開鍵PK ALU50内において、512ビットの単一サイクルの加算器は非常に複雑であって、ALUのクリティカルパス時間を大幅に増やすことになるであろう。このため、ALU50内の512ビット加算器は、図6に示すように、16個の32ビット加算器から形成される。動作中、ANDゲート78およびマルチプレクサ80がまず、2つの32ビットオペランド区分を、32ビット加算器A0〜A15の各々に供給する。ここで、ANDゲート78は32ビット幅の動作を表わす。各32ビット加算器は、キャリ出力に加えて、32ビット合計を計算する。1つの加算器のキャリ出力は、Dフリップフロップ79を介して、次の加算器のキャリ入力に接続される。第1のサイクル中にキャリが生成されると、それはフリップフロップ内にクロック入力され、そのフリップフロップにおいてそのキャリは、次のクロックサイクルのためのキャリ入力として利用可能となる。各合計は、Dフリップフロップ81およびマルチプレクサ80を介して同じ加算器の一方入力に戻される。この加算器の他方入力は、連続するクロックサイクル中、ANDゲート78を用いてゼロに保持される。合計を各加算器へのキャリ入力として戻し加算するステップは、32ビット加算器のうちいずれかの出力にキャリが得られる限り繰返される。
【0058】
512ビット加算器の動作は、以下の例を参照してよりよく理解されるであろう。この例においては、実際の実装時の16個の32ビット語の代わりに、4つの4ビットの2進語を使用する。
【0059】
【数1】
【0060】
ここでは、さらなるキャリがもはや得られない最終合計に達するまでに必要とされる加算は2回であった。これは典型的な場合である。加算器が暗号化演算のために使用されるので、加算される回数はある程度ランダムにばらつくと仮定すると安全であろう。初回の加算の後にキャリ出力が得られる可能性は極めて高い。しかし、最下位ビットとして戻され加算されるキャリによって最上位ビットからの別のキャリが得られる可能性は極めて低い。このため、ほとんどの加算演算はわずか2クロックサイクルしか必要としないと予測されるのである。
【0061】
512ビット加算器を構築するという最初の課題に戻って、標準的なキャリ先見型またはキャリバイパス型加算器設計を使用する場合、その加算器を通じるクリティカルパスは極めて長くなるであろう。なぜなら、キャリが、512ビットの演算を行なう何らかの最適化された回路を通じて伝搬されねばならないためである。この加算器は極めて大きくかつ低速であろう。これに対して、本発明の一実施例においては、512ビット加算器は32ビット加算器から構成されている。32ビット加算器の設計は今日ではよく知られておりまた十分に最適化されている。個々の32ビット加算器の最大クロック速度は、512ビットキャリ先見型設計のクロック速度の2倍以上であると予測される。したがって、本発明に従った2以上のサイクルの加算器は、より大きな512ビット加算器よりも、チップ面積の消費量はより少ないのに対し、通常はより高速で動作することができるであろう。
【0062】
最悪の場合、下に説明するように、16個の32ビット加算器の実装において、キャリを有さない最終合計を完全に計算するのに、16サイクルが必要となることも考えられる。ここで再び4ビットの2進語の例を使用して説明すると、以下のようになる。
【0063】
【数2】
【0064】
以上のように、4回の加算が必要であった。一般に、n個の数のグループについては、最大でn回の加算が必要とされる。
【0065】
512×32乗算器
乗算器は占有面積が広い。各秘密鍵演算処理装置は、たとえば下により詳細に説明するIDEA等の、乗算を必要と秘密鍵アルゴリズムを実現するためには、自身の乗算器を含まねばならない。各PE乗算器によって占められる面積を合わせると相当な面積となり、そこで、この面積は、512×32ビット公開鍵乗算器を実現するのに使用される。面積の節約のために、このように大きな512×32乗算器は、各秘密鍵演算処理装置において16個の32×32乗算器を連結することによって実現される。換言すれば、秘密鍵ユニットおよび公開鍵ユニットは、図4のチップレイアウト内に示すように、複数の乗算器素子を共用することが可能である。したがって、乗算器素子の使用は、秘密鍵演算処理装置とPKコアプロセッサとの間で調整されねばならない。なぜなら、PKコアプロセッサは、複数の秘密鍵演算処理装置のうちどの1つが独立して乗算演算を行なっている場合にも、乗算演算を行なうことができないためである。
【0066】
乗算器の連結を説明するために、4×4/4×N乗算器の組合せの簡単な設計を下に示す。ただし、Boothの符号化および4:2コンプレッサ等の、より進歩した乗算器設計技術もまた利用可能である。以下に、簡単な実現例を提示する。
【0067】
【数3】
【0068】
1桁の乗算は、ANDゲートを用いることによって容易に実現することができる。2つの4ビットオペランドを使用した場合、その結果は、部分積の16ビットから構成される。これらの部分積は、効率的に加算されねばならない。部分積はたとえば、2つの4ビット全加算器および1つの6ビット全加算器を使用して加算することができるが、それらは部分積の加算を行なうのに相当な時間を要するであろう。なぜなら、キャリを複数の加算器を通じて伝搬させる必要があるためである。このような加算器実装の全体としての結果は、遅すぎるであろう。よりよい方法として、加算器のキャリが通らねばならない段の数がより少なくて済むような加算器が考えられる。
【0069】
好ましい乗算器の基本的な構成要素は、3つの入力をとってそれら入力の2ビットの合計を出力する、全加算器である。図7に全加算器を、符号を用いて示すが、ここでは、2進数の代わりに四角形を使用して、一般化および簡素化を図っている。上方の3つの四角は全加算器の3つの入力を示し、下方の2つの四角は合計出力およびキャリ出力を示す。キャリが左下側にあるのは、その桁の値が合計のそれの2倍であることを示すためである。
【0070】
4×4乗算器の加算の第1の段を図8に示す。合計線の上方にある16個の四角は、そのいくつかが黒で示され、その他は白い箱として示されているが、これらは、加算されねばならないある部分積のビットを表わしている。黒で示されるビットは、この第1の段において、4つの全加算器82を使用して加算されるものである。白い箱で示すビットは、第1段では加算されずに、図8に矢印で示すように、次の加算段に備えて単に下方に送られるビットである。第1の段における加算器の合計は、合計線の下に示されている。
【0071】
第2の段を図9に示す。矢印はやはり、この現時点の段においては演算されずに単に下に送られるビットを示し、黒い箱で示されるビットは、この現時点における(すなわち第2の)段において加算されるべきビットを示す。ここでもやはり、黒い箱で示したエレメントが4つの全加算器84を使用して加算される。全加算器84によって生成される第2の段の出力には2つの数があり、これらは今度は一般的な4ビットキャリ加算器86で加算されねばならない。
【0072】
さまざまな加算器および乗算器アーキテクチャの性能を比較することは、本発明に従った乗算器の利点を説明するのに役立つであろう。4ビット加算器の簡単な実現例は、図12に示すように、直列に並んだ4つの全加算器A0〜A3で構成される。この設計においては、最も右側の加算器のキャリ出力Coutが、その左側にあるすべての加算器段のそれぞれに影響を及ぼす可能性がある。この設計におけるクリティカルパスはしたがって、4加算器段である。典型的な全加算器が2以上の論理段から構成されるので、1つの4ビット加算器の合計ゲート遅延は8段を超える場合がある。
【0073】
改良された4ビット加算器は、キャリ先見型設計のものである。3ビットのキャリ先見型加算器を図13に示す。4ビット設計はこれよりもわずかに複雑である。ANDゲート102、ORゲート104および排他的ORゲート106の動作の詳細な説明は、周知の回路であるためここでは省略する。キャリ先見型加算器の利点は、キャリが最終合計ビットまでわずか4論理ゲートで伝搬することである。より大きな数に対するより複雑な設計は、より多くの論理段を有するが、それでもキャリ連鎖型設計よりは、やはり高速である。
【0074】
全4×4乗算器において、キャリ保存型設計は、2つの全加算器および最後のキャリ先見型加算器を通じてクリティカルパスを作る。全加算器のみを使用した実現例では、クリティカルパスがより長くなるであろう。なぜなら、連鎖型キャリを使用する簡単な加算器は、キャリ先見型加算器よりも低速だからである。最後に、部分積合計の最初の2つの段で全キャリ先見型加算器を使用した場合には、結果として得られる乗算器はやはり低速となるであろう。なぜなら、キャリ先見型加算器は個々の全加算器よりは低速なためである。なお、本発明に従った乗算器設計は、同じ部分積レベルでは、あるキャリをある加算器から別の加算器へと伝搬することはない。このようにして、乗算器を通じるクリティカルパスが、部分積合計の最初の2段において、2つを超える数の全加算器を含むことを確実に防止している。
【0075】
図10は、はるかに幅の広い4×N乗算器を示す。大きな黒い箱82、84、86は、図9において使用されていたのと同じ全加算器ハードウェアを示す。この場合、全加算器が必要であるが、これは、各状況において3つの入力が合わせて加算されるためである。図9においては、すべての状況において3つの入力の加算が必要とされたわけではなかったので、より簡単な回路を使用することができた。しかし、4×Nを処理することのできるシステムを作るためには、すべての段において好ましくは全加算器が使用され、加えて、2つ以下の入力の場合にどのように処理を行なうべきかを決定する何らかの付加的な回路が必要となる。したがって、デュアルモードの加算器が複数個作られ、そのいくつかは1つの乗算器を有し、この乗算器が自身の複数入力のうち1つを供給することで、先行する段の出力または単一ビットの部分積の、どちらかが選択されるようにする。
【0076】
図11は、図10に示す囲んだ領域82、84、86を実現するのに必要とされる全加算器Aを示し、合せてその左下方に、それぞれのキャリ出力を示す。好ましい実現例においては、各加算器Aは全加算器である。加算器のうちいくつかは、4×4の場合(すなわち秘密鍵の場合)2つの入力のみを有し、これに対し、他の加算器は、4×Nの場合(すなわち公開鍵の場合)3入力を有する。2入力の加算器は、その第3の入力がイネーブル信号でゲート制御されるようにされねばならない。いくつかの加算器はまた、複数入力のうち1つを提供して先の段の出力または単一ビットの部分積のいずれかを選択するようにする、乗算器を必要とする。下方に示されたキャリ先見型加算器86は、4×4の場合に積の最終ビットを生成するために、4つの位置毎に1つのキャリ出力を必要とする。
【0077】
図11において、4×4乗算器の部分積は、以下の部分積のシナリオに対応するように参照符号が付されている。
【0078】
【数4】
【0079】
4×N乗算器については、隣接する部分積もまた考慮に入れねばならない。それらは図11において、以下のシナリオに従って参照符号が付されている。
【0080】
【数5】
【0081】
ここで、D′は、隣接する(左側または右側の)Dの等価物である。8ビットの最終合計は、S7、S6、S5、S4、S3、S2、S1、S0で示され、左側に隣接する乗算器の合計の下方3ビットは、S2′、S1′、S0′で示される。2:1乗算器88は、選択信号Selを有する。一般に、Selが論理1である場合、左側の入力がマルチプレクサの出力に渡され、反対にSelが論理0の場合には、右側の入力がマルチプレクサの出力に渡される。Sel信号はまた、ANDゲート90をゲート制御するのにも使用される。Selが論理1である場合、ANDゲートへの他方入力が出力に渡され、反対に、Selが論理0である場合、ANDゲート90はディスエーブルされて、他方入力の値にかかわらず論理0を渡す。したがって、図11の実現例においては、Selが論理1である場合には4×N乗算器の区分が実現可能となり、積は出力S6〜S3に現われる。Selが論理0であれば、4×4乗算器が実現されて、8ビットの積が出力S7〜S0に現われる。このように、図11の実現例は秘密鍵乗算器素子を示し、これは、1つの乗算器素子としても利用することができ、または、他の同様の乗算器素子と連結されて、はるかに幅の広い公開鍵乗算器を実現するのにも使用することができる。
【0082】
実現例
先に説明した暗号化チップの好ましい実施例を参照して、一般的な暗号化アルゴリズムの実現例を以下に説明する。RC5はおそらくは、実現するのが最も簡単な暗号化アルゴリズムのうちの1つであろう。これは基本的に、3つの種類の演算を利用する。すなわち、XOR、加算および回転である。これらすべては、表1に示すように、上述の演算処理装置のうちのいずれかによってサポート可能である。RC5は可変長のブロックを有するが、最も一般的には、RC5アルゴリズムの各ラウンドは、Si1およびSi2に記憶される64ビットデータブロックおよび鍵値について演算を行なう。これらは、各演算処理装置内の定数であって、そのラウンドおよびその鍵のみに依存する。データを暗号化するために、64ビットの入力ブロックは2つの32ビット語に分割され、それらはその後、前隣りのメモリ内の場所AおよびBに記憶される。出力ブロックは、後ろ隣りのメモリにおけるA_nextおよびB_nextに書込まれることになる。RC5の暗号化アルゴリズムの1ラウンドの例を以下に示す。
【0083】
【数6】
【0084】
各ラウンドは11クロックサイクルを必要とする。暗号化チップが最高400MHZで動作し得る論理プロセスを用いるように設計されている場合には、1秒あたり3600万ブロックを暗号化することが可能である。これは、ECBモードにおいて288MB/sに相当する。12ラウンド(RC5における典型的な例)を想定すると、同じクロック速度で動作する従来技術によるCPUと比較して、本発明の一実施例に従った複数PEの同時実行によって、従来技術によるソフトウェア実装に対して12倍も性能が改良されることになる。
【0085】
IDEAは、利用可能なブロックアルゴリズムのうち最も安全なものの1つであり、その構造ははるかにより複雑である。IDEAは、64ビットの平文ブロックに対して演算を行ない、128ビットの鍵が使用される。同じアルゴリズムを暗号化および解読の両方に使用する。このアルゴリズムの主要な原理は、種々の代数グループの演算、すなわち、XOR、加算モジュロ216および乗算モジュロ216+1等の演算を組合せることである。これらの演算を使用して、16ビットブロックに対する演算を行なう。
【0086】
したがってIDEAは、モジュラ乗算およびモジュラ加算の両方を使用するが、それらはソフトウェアでは費用が高くつく演算である。乗算は、IDEAのゼロの扱いによって複雑化されている。すなわち、乗算において、ゼロは(−1)モジュロ65537と解釈されるのである。この値65537が演算処理装置のレジスタファイルのレジスタr8内にプリロードされていると仮定し、また、レジスタr0がゼロを含むものと仮定して、以下に乗算マクロの例を示す。
【0087】
【数7】
【0088】
IDEAの各ラウンドは、モジュラ乗算、モジュラ加算および排他的ORから構成される。128ビットの鍵がサブ鍵へと分割される。各演算処理装置のサブ鍵は、その鍵およびその演算処理装置のみに応じて変化するので、予め計算してPE内に記憶させておくことが可能である。IDEAに入力される平文は、先に説明したように、16ビットの4つのサブブロックX1〜X4から構成される。各ラウンドは、6つのサブ鍵K1〜K6を使用し、以下のようにコード化することができる。
【0089】
【数8】
【0090】
IDEAは8ラウンドを有するので、本発明の一実施例に従った暗号化チップハードウェア実装はその実行を8倍以上加速する。さらなる加速は、ほとんどのマイクロプロセッサにおいては利用されないモジュラ乗算命令によってもたらされる。上述のコードは、1ラウンドを実行するのにおよそ50クロックサイクルを要する。400MHZにおいて、この暗号化チップは、IDEAで64MB/sのレートで暗号化することができ、これは、チューリッヒのETH大学(ETH University, Zurich)において開発された25MHZハードウェア実装よりも約3倍高速である。
【0091】
データ暗号化標準、すなわちDESは、当初、ハードウェア実装のために設計されたものであり、したがって、ソフトウェアで実現するのが最も困難なアルゴリズムである。それでも、本発明の一実施例に従えば、これは暗号化チップにおいて容易にコード化することが可能である。
【0092】
先の2つのアルゴリズムと同様に、DESもまた、64ビットブロックでデータを暗号化するブロック型暗号である。平文の64ビットブロックが入力であり、64ビットの暗号文が出力となる。ここでもやはり、暗号化と解読の両方が同じアルゴリズムを使用し、DESを対称的なアルゴリズムとしている。DESは、この場合においては56ビットの単一の鍵から、サブ鍵を作成する。これらのサブ鍵は、該当のPEおよびその56ビットの鍵に応じて変化するものであり、したがって、それらは予め計算しておくことが可能である。
【0093】
図14に示すようなDESにおける基本的な概念は、鍵に基づいてテキスト上で代入を行ない引続き置換を行なうものである。以下の演算によってDESのコアが作られている。・拡張:64ビットブロックを2つの32ビット片108、110に分割する。一方の片は暗号化によって影響を受けることがない。(これらの片は1つおきのラウンドで演算される。)影響を受ける方の片が8つの4ビットのグループに分割される。各グループは、それに隣接する2つのビットをコピーすることによって拡張される。・拡張された各グループは、112においてサブ鍵でXOR処理される。・XORの6ビットの結果を使用して、Sボックス(S-box)と呼ばれる、64エントリ×4ビット先見テーブル114をインデックスする。8個のグループの各々が自身のSボックスを使用する。・Sボックスからの出力は116において置換され、それらのビットがスクランブルされる。8個の出力から32ビットが得られる。・その32ビットの出力が、118において、そのブロックの他方の32ビット片とXOR処理される。
【0094】
これらの演算は以下のようにコード化することが可能である。すなわち:拡張は、入力語をコピーしてから、ビットをマスキングすることによって、1つが偶数のSボックス入力を表わし他方が奇数のSボックスの入力を表わす2つの語が存在するようにすることによって行なわれる。これら2つの語を、鍵情報でXOR処理し、その結果を使用して、Sボックスルックアップテーブルをインデックスする。各Sボックスにおけるデータは予め置換され、したがって、Sボックスの出力は32ビットのデータとなる。最終値はすべての構成要素の論理ORである。コードの例を以下に示す。
【0095】
【数9】
【0096】
このサンプルコードは、1ラウンドを実行するのに44クロックサイクルを必要とする。400MHZにおいて、72MB/sのデータレートが達成され得る。このレートは、1〜35MB/sの範囲のレートで暗号化を行なう、1990年代半ばに利用可能となったDESのハードウェア実装に比べて遜色のないものである。VLSIテクノロジー(VLSI Technology)のVM007は、最高200MB/sで暗号化を行なうことが可能である。
【0097】
以上の例の各々において、その性能は、従来技術におけるCPU上のソフトウェア実装よりもはるかに高速であるが、専用ハードウェア実装よりも低速であることが示されている。本発明のハードウェア実装に対する利点は、暗号化チップがプログラマブルであり、したがって、今後想定され得るものも含むどのようなアルゴリズムも実装が可能であるということである。
【0098】
特定的な公開鍵アルゴリズムの例は何ら示さなかったが、既存の方法に対して同様の改良が、本発明の好ましい実施例において説明したのと同様の技術を用いて実現され得るものと理解されたい。
【0099】
均等物
本発明をその好ましい実施例を参照して特定的に図示しかつ説明したが、当業者においては、その形および詳細に、前掲の請求の範囲によって規定される本発明の精神および範囲から離れることなく、種々の変更が行なわれ得ることが理解されるであろう。当業者においては、日常的な作業の範囲を超えることなく、ここに特定的に示した本発明の具体的な実施例に対する多くの均等物が認識されるかまたは確認されるであろう。そのような均等物は、前述の請求の範囲に包含されるものと意図される。
【符号の説明】
【0100】
22 ソース、24,28,34,36 暗号化チップ、26 ネットワーク、30 宛先、32 ルータ。
【技術分野】
【0001】
本発明は高性能ネットワーク暗号化デバイスに関し、より特定的には、ハードウェアおよびソフトウェアの双方を組み込む暗号化デバイスに関する。
【背景技術】
【0002】
インターネットの出現以前は、企業のデータネットワークは典型的に、公共の電話会社からリースした専用遠隔通信ラインで構成されていた。このようなデータネットワークのハードウェア実装は、媒体上で絶対的な独占権を有する規制された公益企業であるその電話会社の独占的所有物であったために、セキュリティは大した問題ではなかった。その単一のプロバイダは、契約により安全が義務づけられ、また、中継ネットワークへの外部からのアクセスが不可能であったために、外部からのハッキングやタンパリングに対してかなり耐性があった。
【0003】
今日、ますます多くの企業がインターネットに価値を見出している。インターネットは現時点において、単一のコンピュータネットワークとしては世界中で最も広く展開しているネットワークであり、したがって、国際的な企業ネットワークに容易に利用することが可能である。インターネットはまた、消費者レベルの製品であるので、インターネットアクセスは通常、専用電話会社のネットワークによって提供される同じサービスよりもはるかに低コストで提供され得る。また、インターネットのエンドユーザに対する可用性によって、個人が家庭や他の遠隔地から企業のネットワークに容易にアクセスすることが可能となっている。
【0004】
しかしながら、インターネットは複数の株式会社によって運営されており、オープンプロトコルを用い、自由に調査可能なインバンドルーティングおよび制御の下に置かれている。このような環境は、ハッカーを育てるには絶好の土壌である。企業の諜報活動は今日では利益の多いビジネスであって、インターネット上でビジネスを行なう企業にとって、予防を怠ることは重大な損失を被ることにつながる。
【0005】
今日、インターネット上では、プライバシーおよび強力な認証のためのいくつかの基準が存在する。プライバシーは暗号化/復号化、すなわち解読、によって達成される。典型的に、暗号化/解読はメッセージ内容のプライバシーを維持しながらも当事者間でオープンチャネルを介してデータを転送することを可能にするよう設計されたアルゴリズムに基づいて行なわれる。これは、送信者が暗号化鍵を使用してデータを暗号化し、受信者が解読鍵を使用してそれを解読することによって達成される(ときに、暗号化鍵と解読鍵とは同一のものである)。
【0006】
暗号化アルゴリズムの種類
暗号化アルゴリズムは、公開鍵アルゴリズムと秘密鍵アルゴリズムとに分類することができる。秘密鍵アルゴリズムにおいては両方の鍵が秘密であり、これに対し、公開鍵アルゴリズムでは鍵のうち一方が公開されている。ブロック型暗号は、今日使用されている秘密鍵暗号システムの代表である。通常、ブロック型暗号については、暗号化鍵と解読鍵とは同じものである。ブロック型暗号は、データのブロック、典型的には32〜128ビットを入力として受取り、同じ数のビットを出力として生成する。暗号化および解読は、長さが56ビットから128ビットの間である鍵を使用して行なわれる。この暗号化アルゴリズムは、鍵を知らなければメッセージの解読が非常に困難なものとなるように設計されている。
【0007】
インターネットのセキュリティプロトコルにより、ブロック型暗号に加えて、公開鍵アルゴリズムが多用されている。PogueおよびRivestに発行された米国特許番号第5,144,667号に記載の、Rivest, Shamir, Adelman(RSA)暗号システム等の公開鍵暗号システムは、2つの鍵を使用し、そのうち一方のみが公開されている。ある人物が鍵を公開すると、他の誰もがその鍵を使用して秘密のメッセージをその人物に対して送信することができるが、そのメッセージは秘密鍵を使用しなければ解読することができない。このような公開鍵暗号化の利点は、会話を行なう前にすべての相手に対して秘密鍵を配布する必要がないことである。これに対して、もし秘密鍵の暗号化のみが使用されるようであれば、メッセージを受信する予定の各相手先に対して1つずつ、合せて多数の秘密鍵を生成せねばならず、またそれらすべての秘密鍵を1つずつ個別に配布せねばならなくなる。秘密裡に秘密鍵を送信しようと試みる場合、秘密鍵暗号化のみを使用してメッセージそのものを送信する場合と同じ問題が生じることになる。このような問題を、鍵の配布問題(key distribution problem)と呼ぶ。
【0008】
鍵の交換は、公開鍵技術の別の応用例である。鍵交換プロトコルにおいて、当事者間の会話が第三者によって傍受された場合にも、当事者間は秘密鍵で対処することが可能である。米国特許番号第4,200,770号に記載されているDiffie-Hellman指数関数鍵交換は、そのようなプロトコルの一例である。
【0009】
RSAやDiffie-Hellman指数関数鍵交換等の、大半の公開鍵アルゴリズムは、モジュラ指数関数に基づいており、この関数は、αxmodPを計算するものである。この式は、「αをx乗し、その解をpで除して、剰余を得る」ことを意味する。このような計算を行なうには非常にコストがかかるが、それは以下の理由による。すなわち、この演算を行なうために、多数の乗算および除算を繰返す必要がある。ただし、1985年4月の、Mathematics of Computation, Vol. 44, No. 170の「試行除算を行なわないモジュラ乗算(“Modular Multiplication Without Trial Division”)」に記載のモンゴメリーの法(Montgomery's method)等の技術によれば、必要とされる除算の数を減じることができる。加えて、使用される数も非常に大きく(典型的に1024ビット以上)、したがって、一般のCPUに見られる乗除命令を直接使用することができず、代わりに、そのような大きな乗算および除算を、1つのCPUで行なうのに十分小さい演算へと分割する、特別なアルゴリズムを使用せねばならない。また、そのようなアルゴリズムの実行時間は通常、関連する機械語の数の二乗に比例する。これらの要因により、大きな数の乗算はその演算が非常に遅いものとなる。たとえば、Pentium(登録商標)は、1回の32×32ビット乗算を10クロックサイクルで行なうことができる。2048ビット数は64個の32ビット語で表わすことができる。2048×2048ビット乗算には、64×64回の別個の32×32ビット乗算が必要であり、この乗算のためにこのPentium(登録商標)上では40960クロックが必要となる。2048ビット指数を用いる指数関数は、通常の方法では最高で4096回の乗算を必要とし、これには約1億6700万クロックサイクルが必要となる。このPentium(登録商標)が166MHZで動作するとすると、この演算全体でおよそ1秒かかることになる。驚くべきことに、この例では除算にかかる時間は一切考慮されていないのである。明らかに、Pentium(登録商標)等の一般的なCPUで鍵の生成および交換を行なうことはほとんど期待することはできない。
【0010】
公開鍵アルゴリズムは、計算が非常に面倒なので、典型的にメッセージ全体を暗号化するのには使用されず、代わりに、プライベート鍵暗号システムがメッセージの転送に使用される。メッセージの暗号化に使用されるプライベート鍵はセッション鍵と呼ばれ、この鍵が無作為に選ばれて公開鍵を用いて暗号化される。暗号化されたセッション鍵は暗号化されたメッセージとともに相手先に送信される。相手先は、自身の秘密鍵を用いてセッション鍵を解読し、その時点で、そのセッション鍵を用いてメッセージを解読することができる。各通信には異なるセッション鍵が使用されるので、もし1つのセッション鍵が破壊されたとしても、読むことができるメッセージはそのセッション鍵を使用して暗号化された1つのメッセージのみである。この公開鍵/プライベート鍵の方法はまた、双方向端末セッション等の、通常動作時には決して終了することのない連続的な通信を保護するのにも使用することが可能である。この場合、セッション鍵は、公開鍵生成技術を繰返すことによって周期的に(たとえば1時間ごとに)変更される。やはり、セッション鍵を頻繁に変更することによって、暗号化が破られたとしても犠牲となるデータ量は制限される。
【0011】
先行技術
ソフトウェアをベースとした解決法を用いて企業のネットワークへのアクセスを可能にする、ネットワークレベルの暗号化デバイスが広く使用されている。Raptor Eagle Remote等の製品は、暗号化をすべてソフトウェアで行なっている。ソフトウェアは、暗号器のスループットを制限する。公開鍵技術を用いたセッション鍵の生成には数分かかることもある。この理由のために、セッション鍵の再生成はある人々が望むほどには頻繁には行なわれない。しかし、ソフトウェアは、その分野における開発に応じて、暗号化アルゴリズムを容易に変更することができるという利点を有する。
【0012】
他のデバイスは、ハードウェアとソフトウェアとの組合せを使用する。たとえば、Northern Telecom(現在のEntrust)のSentinel X.25暗号化製品は、AMDによって製造されたDESチップを使用して、DES秘密鍵の暗号化を行なう。DESはハードウェアで効率的に実装されるように設計されたものなので、ハードウェア実装の方がはるかに高速である。ソフトウェアにおいては多くのCPU命令を要する転換を、並列の専用ルックアップテーブルおよび配線を使用して行なうことが可能である。
【0013】
Sentinelはまた、Motorola DSP56000プロセッサを使用して、公開鍵演算を行なう。当時、DSPの単一サイクルの乗算能力のおかげで、この方法によって、一般的なCISCマイクロプロセッサで公開鍵アルゴリズムを実現するよりもはるかに高速で演算ができるようになった。
【先行技術文献】
【特許文献】
【0014】
【特許文献1】米国特許番号第5,144,667号
【特許文献2】米国特許番号第4,200,770号
【発明の概要】
【発明が解決しようとする課題】
【0015】
大半のハードウェア暗号化デバイスにおいては、それによって実現することのできるアルゴリズムの数が大幅に制限されている。たとえば、Sentinelにおいて使用されるAMDチップは、DESのみを実行する。Hi/Fnによるより最近のデバイスでは、DESおよびRC4を実行することができる。しかし、RC5またはIDEAを実現したい場合には、別の製品を用いねばならないであろう。
【課題を解決するための手段】
【0016】
発明の概要
好ましい高性能プログラマブルネットワーク暗号化デバイスは、単一チップ内に集積され、これは、その命令の組が共通の暗号化アルゴリズムに対して最適化された、並列パイプライン式のプロセッサシステムである。本発明は、ハードウェアおよびソフトウェアの両方の方法の利点を実現する。該プロセッサはプログラマブルプロセッサであるため、どのような暗号化アルゴリズムも実現することが可能であり、これは、1つのアルゴリズムのみを実行するよう設計されるハードウェア実装の暗号化プロセッサとは対照的である。しかし、このプロセッサのアーキテクチャは、暗号化に有益な特性である並列計算を可能にしているので、その性能は、専用ハードウェアデバイスの性能により近づく。
【0017】
本発明の好ましい実現例に従えば、電子暗号化デバイスは演算処理装置のアレイを含む。各演算処理装置は、暗号化アルゴリズムの1ラウンドを記憶するための命令メモリを含み、該ラウンドは、命令の1シーケンスを含む。該演算処理装置はまた、命令メモリからのラウンドを実現するためのプロセッサ、ならびに、暗号化データオペランドおよびラウンドを実現することによって得られる暗号化されたデータを記憶するためのデータ記憶装置を含む。該アレイの各演算処理装置は、複数のラウンドのうち1つを実現し、その結果を連続する演算処理装置へと転送し、それにより、該演算処理装置のアレイは演算処理装置のパイプラインにおいて暗号化アルゴリズムの連続的なラウンドを実現する。
【0018】
好ましい実施例においては、該データ記憶装置はその一部分が該線形アレイの隣接する演算処理装置間で共用されており、該線形アレイの隣接する演算処理装置間でデータを転送するのに使用される。該共用データ記憶装置は好ましくは、デュアルポートメモリで構成されるが、これはまた、共用レジスタを含んでもよい。
【0019】
好ましい演算処理装置は、制御ユニットおよびALUを含む。制御ユニット、ALU、命令メモリおよびデータ記憶装置は、ローカルデータメモリおよび共用データメモリも含めて、ローカル演算処理装置バスに接続される。このローカルバスはスイッチによって区分されて、命令メモリおよび制御ユニットを接続するローカル命令バス区分と、ALU、ローカルデータメモリおよび共用データメモリを接続するローカルデータバス区分とに分けられる。該スイッチは、該2つのローカルバス区分上で別個に同時に演算ができるようにするか、または、それら2つのバス区分の間で通信ができるようにする。各演算処理装置はさらに、その演算処理装置内で乗算演算を行なうための乗算器を含む。
【0020】
好ましい暗号化デバイスはさらに、グローバルランダムアクセスメモリおよびグローバルバスを含み、データは該グローバルランダムアクセスメモリと演算処理装置のデータ記憶装置との間で該グローバルバスを通じて転送される。中央処理装置は、このグローバルバスに結合されて、演算処理装置によって処理されるデータ語よりも幅の広いデータ語を処理する。複数の演算処理装置のそれぞれの乗算器は、中央処理装置によって使用されるより幅の広い乗算器の区分として連結できるようにされ得る。好ましくは、各乗算器は部分積加算器を含み、該加算器は、個別の乗算器として動作しているときには第1の入力の組を選択し、かつ、連結されているときには隣接する演算処理装置からの入力を含む第2の入力の組を選択するための、入力選択回路を有する。
【0021】
好ましくは、中央処理装置は新規な加算器を含む。該加算器において、複数加算器区分の各々はキャリ出力および合計出力を有し、それら加算器区分の各々は、2つあるオペランドの各オペランドの1区分を処理する。選択器は、加算器サイクル中にキャリが得られる限り、連続するクロックサイクル中、該キャリ出力を連続する加算器区分へのキャリ入力として選択する。選択器はまた、各合計出力を同じ加算器区分へのオペランド入力として選択する。したがって、加算器サイクル中にキャリが得られる限り、ある加算器の合計出力はその入力にフィードバックされ、また該加算器区分は先行するサイクルにおいて先行する区分からキャリ出力として生成されたキャリ入力を受取ることになる。
【0022】
好ましくは、各演算処理装置は、除算回路を用いずにMmodNを計算する、モジュラ調整演算を行なう。各演算処理装置はまた、A±BmodNを計算するモジュロ加算/減算演算を行なう。さらに、各演算処理装置は、A×BmodNを計算するモジュロ乗算演算を行なう。
【図面の簡単な説明】
【0023】
【図1A】本発明の可能な応用例のブロック図である。
【図1B】本発明の可能な応用例のブロック図である。
【図2】本発明を用いた暗号化チップのブロック図である。
【図3】図2の暗号化チップにおける演算処理装置のブロック図である。
【図4】図2および図3に示した回路の好ましいチップレイアウトを示す。
【図5】図4に示したレイアウトに対応するように書き直された図3の演算処理装置ならびに、PEローカルバスおよびグローバルバス接続を示す。
【図6】図2のPK ALUにおいて使用される加算器回路を示す。
【図7】PK ALUの乗算器において使用される全加算器の符号を示す。
【図8】全加算器を使用する4×4乗算器の第1段における処理を示す。
【図9】4×4乗算器の3つの段を示す。
【図10】4×4乗算器の加算器がその上に重ねられた、幅の広い乗算器の加算器を示す。
【図11】図10に示した広い語長の演算器において、同様の乗算器と連結されるように適合された、4×4乗算器のブロック図である。
【図12】全加算器を使用する8ビット加算器の従来技術による実現例を示す。
【図13】キャリ先見型加算器の従来技術による実現例である。
【図14】DES暗号化ラウンドをブロック図で表現したものである。
【図15A】本発明の実施例に従ったモジュラ加算演算を示す機能図である。
【図15B】本発明の実施例に従ったモジュラ減算演算を示す機能図である。
【図15C】本発明の実施例に従ったモジュラ調整演算を示す機能図である。
【図15D】本発明の実施例に従った3つすべてのモジュラ演算の組合せを示す機能図である。
【発明を実施するための形態】
【0024】
詳細な説明
本発明の上記および他の目的、特徴および利点は、添付の図面に示される本発明の好ましい実施例に関する以下のより詳細な説明から明らかとなるであろう。添付の図面においては、複数の図面を通じて、同じ部分には同様の参照符号が付される。図面は必ずしも一定の比で描かれているわけではなく、本発明の原理を説明するために強調されている部分を含む。
【0025】
本発明の暗号化チップは、任意のアプリケーションにおける1または複数のデータストリーム上で、共通のデータ暗号化および復号化、すなわち解読、のアルゴリズムを行なうようプログラムすることが可能である。この暗号化チップの主要な目的は、インターネット上でその使用が想定されるアルゴリズムを用いて、100〜2000Mbpsのデータレートで、高速データ暗号化を行なうことである。
【0026】
アプリケーションの例を図1Aおよび図1Bに示す。図1Aにおいて、ソース22からのデータが、暗号化チップ24で暗号化された後に公衆ネットワーク26に渡される。データはその後、暗号化チップ28内で解読されて、宛先30に送られる。一実施例においては、このソースおよび宛先自体が、ローカルエリアネットワーク等のネットワークである。そのような場合、これら暗号化チップが、ローカルエリアネットワークと公衆ネットワーク26との間に安全な経路を提供する。
【0027】
図1Bに示されるリンク暗号化アプリケーションにおいては、各リンク内でルータ間で転送されるデータが暗号化される。この場合、リンクとリンクの間にあるルータ32に入力された暗号化データは、暗号化チップ34でまず解読されねばならず、またそのデータは、暗号化チップ36において、次のリンクの暗号化アルゴリズムに従って再度暗号化される。
【0028】
今日、DES、RC5およびIDEAという3つの主要な秘密鍵ブロック型暗号化アルゴリズムが一般に使用されている。最初の2つのアルゴリズムは、標準的なインターネットプロトコルセキュリティ(Internet Protocol SECurity)の略である、IPSEC標準アルゴリズムである。IDEAは、広く利用されている電子メール暗号化プログラムであるPGPによって使用されるアルゴリズムである。
【0029】
典型的に、ブロック型アルゴリズムは、多数のラウンドで構成され、各ラウンドは、暗号化アルゴリズムにおける演算の1シーケンスである。暗号化アルゴリズムを完全に実現するには、8〜32ラウンドが必要とされる。各ラウンドによって行なわれる演算は、しばしば同じものであるが、同じものでなくてもよい。ソフトウェアにおいては、各ラウンドは少数の機械命令で実現される。ハードウェアにおいては、各ラウンドは専用回路で実現される。ハードウェアは典型的にパイプライン化されており、各ラウンドは自身に該当するパイプライン段において実現される。
【0030】
図2は、本発明の一実施例に従った、集積チップの解決法を図示する。これを今後、暗号化チップと呼ぶ。暗号化チップと呼ぶと、そのチップが暗号化を行なうことができることが示唆されるが、このチップが復号化、すなわち解読、およびメッセージダイジェスト機能もまた行なうことに留意されたい。
【0031】
データは、ネットワークデータを受取る入力段40を介して、典型的にはシリアルビットストリームとして暗号化チップに入力される。イーサネット(登録商標)、ATMまたは他のどのような直列化フォーマットも使用することができる。入力段はこのシリアルデータストリームを、暗号化/解読パイプラインへの入力として処理するのに好適な、ブロック整合されたデータへと変換する。入力ブロックのサイズはプログラム可能である。図2に示した好ましい実施例においては、パイプラインは線形アレイに配された複数の演算処理装置37からなり、各演算処理装置は、命令メモリ、レジスタファイル、ALU、ローカルおよび共用データメモリ、ならびに制御回路を含む。演算処理装置の各々は、32ビット幅のデータ語を処理するよう設計されている。暗号化されたデータは、該パイプラインの最後の演算処理装置から取出されて出力段42に渡され、出力段42がそのブロックデータをシリアルストリームフォーマットに戻して、そのデータをネットワークを介してまたは局所宛先へと送る。
【0032】
データは、グローバルデータバス38を介して、暗号化チップ内の隣接しない演算処理装置間および/または他の装置間で転送することができる。グローバルデータバス38にはまた、I/O通信ロジック54が接続されており、このロジック54が、ホストCPU(図示せず)との通信を可能にする。ホストCPUとの通信は、暗号化チップを使用前にプログラムするのに必要である。グローバルランダムアクセスメモリ(RAM)44もまたグローバルデータバス38に接続され、それにより、演算処理装置間でグローバルな通信が可能となっている。制御CPU52は、暗号化パイプラインプロセッサの動作を同期化する。このCPUは、MIPS、ARMまたはARC等の、利用可能ないずれの組込み型CPUコアを使用しても実現することができる。さらに、公開鍵暗号化アルゴリズムのように非常に幅の広いオペランドを利用するアルゴリズムを処理することができるように、公開鍵(PK)コアプロセッサ46が制御CPU52に接続されている。PKコアは、8個から16個の512ビット幅のレジスタからなるレジスタファイル48、およびPK ALU50を含む。PKコアプロセッサは、1システムクロックサイクルで、512ビットバスを介してグローバルRAM44との間でデータの送受信を行なうことができる。512ビットのオペランドは、典型的には2〜32クロックサイクルで、ALU50内で処理される。PKコアALU50は、制御CPU52によって制御されるコプロセッサであって、ローディングおよび記憶の他には、算術および論理演算のみを行なう。PKアルゴリズムを実現するのに必要な他の命令は、制御CPU52内で実行され得る。
【0033】
この暗号化チップは、秘密鍵アルゴリズムの各ラウンドのためのコードを、パイプラインの別個の演算処理装置内で実現する。計算が終わると、1つのPEからのデータは次のPEに転送され、そこで次のラウンドが実現される。第1のPEはその後、入来するデータの次のブロックのための暗号化ラウンドを処理することができるようになる。パイプライン処理は残りのPEにおいて続けられる。このアーキテクチャを用いて1つのブロックを暗号化するのに必要とされる時間は、したがって、1つのラウンドを暗号化するのに必要とされる時間に等しい。
【0034】
多くのブロックアルゴリズムは、データを暗号化するのにある演算の組を使用し、鍵を拡張するのに別の演算の組を使用する。鍵の拡張は、比較的小さい鍵(56〜128ビット)を、統計的に無作為の性質を有するより大きい数(512ビット以上)の鍵へと変換するプロセスである。こうして拡張された鍵は、より小さなサブ鍵に分配され、拡張された鍵の異なる部分が各々異なるラウンドのために使用される。拡張された鍵がデータによって変化しないことに注目することが重要である。したがって、これはクリティカルパス内にはないため、予め計算してメモリに記憶しておくことができる。後に説明するコードの例は、鍵情報が予め計算されて各PEのローカルデータメモリ内に記憶されているものと仮定している。
【0035】
ブロックアルゴリズムの基本的なアプリケーションは、平文(暗号化されていない情報)のブロックを同じサイズの暗号文(暗号化された情報)のブロックに変換したり、その逆を行なう。この動作モードは、電子コードブック(ECB)モードとして知られているが、これはセキュリティに関して多くの固有の弱点を有するので、基本的な出力のいくつかを入力に戻るよう巡回させることによって暗号化にフィードバックを導入する方法が一般に使用されている。この暗号化チップは、グローバルデータバス38を利用して暗号フィードバック(CFB)を行なう。ECBモードにおいては、データの新しいブロックを各パイプラインサイクルにつき1回暗号化することができる。これは10〜100個の命令であり得る。しかし、CFBモードにおいては、各データはパイプラインを多数回通過せねばならない。このモードは単一チャネル上のスループットを大幅に減じるが、パイプラインにおいてインターリーブされている多数のデータチャネルを暗号化することによって、ピーク性能を達成することができる。
【0036】
本発明の一実施例に従った1つの演算処理装置PEのブロック図を図3に示す。演算処理装置37は、8〜16個の32ビットレジスタで構成されたレジスタファイル58から得られる32ビット語の演算を行なう、ALU56を含む。レジスタファイル58およびALU56は、制御ユニット60によって制御される。制御ユニット60は、演算処理装置命令メモリ62からの命令をデコードする。各演算処理装置命令メモリは暗号化アルゴリズムの少なくとも1つのラウンドを記憶し、ここで1つのラウンドとは、暗号化アルゴリズムにおける命令の1シーケンスと定義される。各演算処理装置がアクセスすることのできるPEデータメモリスペースは、4つの領域に分割される。すなわち、ローカルPEメモリ64(図3においてはPEnローカルメモリ)、共用メモリ66(図3では、n番目の演算処理装置とn−1番目の演算処理装置との間で共用される、PEn,n-1共用メモリ)、第2の共用メモリ68(図3では、n+1番目の演算処理装置とn番目の演算処理装置との間で共用される、PEn+1,n共用メモリ)、および、図2を参照して説明した、すべてのPEがアクセス可能なグローバルメモリ44、の4つの領域である。これらのメモリはすべて、1つの演算処理装置、たとえばn番目の演算処理装置のアドレススペースにマップされる。どの種類のメモリにアクセスするのにも、特別な命令は必要ない。すべてのメモリはすべてのメモリアクセス命令によってアクセス可能である。
【0037】
1つの演算処理装置のメモリ66および68は、デュアルポートSRAMであって、これらはそれぞれ、先行する、すなわち前隣りのパイプ段および、次の、すなわち後ろ隣りのパイプ段と共用される。あるPEにとっての後ろ隣りのPEとの共用メモリは、次のPEにとっての前隣りのPEとの共用メモリと同じものであることを理解されたい。
【0038】
これらのデュアルポートのSRAMは、パイプライン段を通じてデータを伝搬するのに使用される。ある演算処理装置が、転送されるべきデータをそれに関連する後ろ隣りの装置との共用メモリに書込む。すると、その記憶されたデータを、該当する後ろ隣りの演算処理装置が、自身の前隣りの装置との共用メモリから読出す。ここで、前隣りの装置との共用メモリとは、上述のように、先行する演算処理装置にとっての後ろ隣りの装置との共用メモリと同一無二のメモリを指す。これらのメモリはデュアルポートメモリであるため、アクセスにはタイミングの制限がない。アクセスの同期化は、ソフトウェアの作者または編集者による機械命令の静的なスケジューリングを用いて行なわれる。さらに、隣接するPE間の通信にグローバルバスを使用しないので、PEはすべて同時に通信することが可能である。
【0039】
グローバルメモリ44はグローバル通信バスに接続される。任意の時間にグローバルメモリ44にアクセスが許可されるのは1つの演算処理装置のみである。このメモリは、たとえば、フィードバック暗号化アルゴリズム中に、隣接していない演算処理装置間でデータをやりとりするのに使用され、また、個々の演算処理装置のための補助記憶装置としての役割を果たす。
【0040】
PE命令メモリ62は、現代のRISCプロセッサの整数ユニットのそれに似た、命令の組を有する。この命令の組は、どのレジスタもどの命令に対するオペランドとしても使用することができるという点で、いくぶん直交性である。浮動小数点やメモリ管理サポートは、どちらも暗号化には有益ではないので、設ける必要はない。しかし、この命令の組は、以下の有益な追加機能を含む。すなわち、モジュラ加算/減算命令、モジュラ乗算命令およびモジュロ調整命令、である。
【0041】
モジュラ加算/減算命令は、A±BmodNを計算する(「MmodN」の数はMをNで除した際の剰余である)。図15Aから図15Dは、モジュラ加算、減算および調整を、1つのスリーインワン(3-in-1)モジュロ算術ユニットに組合せた例を示す。
【0042】
図15Aは、モジュラ加算演算を示す。加算すべき2つの数AおよびBが双方ともNよりも小さければ、加算器120からのそれらの合計を、Nを法として減じることができる。すなわち具体的には、減算器122においてNを減じ、その後、その差の符号に応じて、マルチプレクサ124を介して、減算器の出力または元々の数のいずれかを選択する。同様に、図15Bに示すモジュラ減算演算の場合には、2つの数AおよびBがNよりも小さい場合には、Nを法とするそれらの差を計算することが可能である。これは具体的には、減算器128からの差が負であれば加算器126においてNを加算し、その差が正であればマルチプレクサ130を介してその差を選択することによって、行なわれる。ここで、モジュロ加算およびモジュロ減算がいずれも除算を必要としないことに注目されたい。しかし、それらは、連続2回の加算を必要とする(そのうち1つは合計/差を計算するもの、もう1つはNを法として減算するものである)。このような2回続けての加算がクリティカルパスに打撃を与える場合には、Nを法とする減算は、別個の命令としてエンコードすることが可能であり、これを「モジュロ調整」命令と呼ぶ。
【0043】
図15Cに示すこのモジュロ調整命令は、AおよびBの両方が既にNを法として減じられていて、MがAとBとの合計または差のいずれかであるものとして、MmodNを計算する。Mが負である場合、ロジック132は、加算器/減算器134においてMにNを加えて、マルチプレクサ136を介して結果が生成されるようにする。Mが正である場合には、ロジック132は、Nの減算を行ない、その差が正であればその差を返し、その差が負であればMを返す。この命令は、合計および差の命令と関連づけて使用することが可能であり、それにより、モジュラ加算/減算命令が不要となる。
【0044】
図15Dにおいて、スリーインワンの算術ユニットは、モジュロ加算、モジュロ減算およびモジュロ調整を、各演算処理装置内で実現される単一のユニットに組合せる。1つの命令(モジュラ加算、減算または調整)および最上位ビット(MSB)の符号入力に応答するロジック144の制御下で、加算器/減算器138は装置120および128のいずれかの機能を行ない、加算器/減算器140は、装置122、126および134のうちいずれかの機能を行なう。マルチプレクサ142は装置124、130および136に対応する。モジュロ調整演算において、MがA入力に印加され、B入力はゼロにセットされる。この組合せユニットは、速度は落ちるが、面積効率は最も高い。この組合せユニットはまた、Mathematics of Computation, Vol. 44, No. 170, April 1985, pages 519-521の、ピーター・L・モンゴメリー(Peter L. Montgomery)による「試行除算を行なわないモジュラ乗算」に記された、試行除算を行なわないモジュラ乗算のためのモンゴメリーの法を実現するのに有益である。
【0045】
モジュラ加算および減算は、従来技術によるプロセッサにおいてわずか2〜3個の命令で実現することができるが、これらの命令を暗号化チップの命令の組の特別な関数として含むことで、特定的な暗号化アルゴリズムの場合においては、わずかながら高速化につながる。
【0046】
モジュラ乗算命令は、A*BmodNを計算する。この命令に使用される乗算器は、下により詳細に説明する。暗号化チップは、後に明らかとなるであろう理由によって、全体のモジュラ乗算命令を提供することができる。
【0047】
表1は、以下の例において使用される、PEの命令の組の代表的な例を示す。他の従来技術によるRISC命令もまた実現することが可能である。
【0048】
【表1】
【0049】
レイアウトの課題
暗号化チップの一般的なレイアウトを図4に示す。ここでは、16個の演算処理装置および、512ビット幅の公開鍵PKコアユニットを想定する。ここで512ビットのPKコア語幅を選択したのは、そのレイアウトが容易であるためである。たとえば1024ビット幅は、より広いシリコン面積を必要とするであろうが、性能は倍加するであろう。
【0050】
個々の素子は、図2および図3に示した素子に匹敵し得る。16個の演算処理装置が、レイアウトの大きな領域内で左下側に1列に線形に配されており、その1つが詳細に示されている。図中、共用乗算器素子70は、図示された演算処理装置に関連づけて示されている。前述のように、32×32乗算器区分70は、各演算処理装置と関連づけられて、それぞれの演算処理装置内で32ビット乗算を行なう。これに代えて、乗算器素子70は、公開鍵ALU50のための幅の広い512×32ビット乗算器として機能するように、連結することも可能である。公開鍵PK ALU50は、秘密鍵SK素子の右側に配置され、上述のような演算処理装置で構成されている。PK ALUの隣りに、PKレジスタファイル48が配される。PK ALU50およびPKレジスタファイル48は併せて、図2において46で示されたPK処理コアを形成する。PKコアの右側には、グローバルメモリ(RAM)44が配置される。チップの上辺に沿って、制御CPU52、通信ロジック54および入出力処理ブロック40、42が配置される。グローバルデータバス38は、SK素子、PKコア46、グローバルRAM44、通信ロジック54および制御CPU52を繋ぐ。
【0051】
ローカルバス接続を含む典型的な演算処理装置のレイアウトを図5に示す。1つの演算処理装置のすべての構成要素は、ローカル演算処理装置データバス72を介して通信することができる。このバス72は、メモリとレジスタとの間のすべての転送を扱う。ここで、次に隣接するPEとの共用PEメモリ68は、図示されている演算処理装置の他の素子と直列に(in-link)配されており、これに対し、先に隣接するPEとの共用PEメモリ66は、先に隣接する演算処理装置の素子と直列に配されていることに注目されたい。プログラミングおよびテストの目的のために、すべてのPEメモリはグローバルバス38からアクセス可能である。スイッチ74は通常、ローカルバス72をグローバルバス38から切離しているが、ローカルRAM64とグローバルRAM44との間でデータ転送を可能にするように選択的に閉じることが可能である。別のスイッチ76は、ローカルバス72を独立した2つの区分に区分けすることを可能にし、これにより、制御ユニット60は、バス72上のデータ転送と同時に、RAM62から命令を読出すことが可能となる。このように、演算処理装置内の動作は、ある命令がPE ALU56内で実行されている間に次の命令が制御ユニット内で処理されるというように、パイプライン化することが可能である。暗号化コードの実行中、スイッチ74および76は通常は開かれており、これにより、命令RAMからの命令フェッチを、データメモリおよびレジスタファイルからのデータフェッチと同時に進めることができる。
【0052】
多数のマルチプロセッサアーキテクチャが提案されているが、それらの大半は、汎用マルチプロセッシングのために設計されている。このため、演算処理装置間の通信は通常、あるPEから別のPEへとデータを切換えるよう動的に構成することが可能な、切換マトリックスを使用して行なわれる。これらのスイッチの設計は非常に複雑である。このようなスイッチは暗号化には不要であるため、本発明の実施例においては、切換回路が大幅に減じられた、より簡単なPEの線形配列を用いている。
【0053】
加えて、相互配線技術として、文献に記載されているようなI/Oポートを使用するのではなく共用メモリを使用していることにより、はるかに簡単かつはるかに強力なプログラミングモデルが生成される。ここで、2つのPE、AおよびBが単一の32ビットI/Oポートに接続されているものとする。AがBに対してデータの複数語を転送するためには、Aは各語をI/Oポートに書込んで、Bがそれを読出すのを待たねばならない。これに対し、AおよびBが、通信のすべての語を保持するのに十分な大きさの共用メモリによって接続されている場合には、AはBが読出すのを待つことなくそのデータを書出すことが可能である。さらに、PE Bはどのような順序でもそれらの語を読出すことができ、また、そのデータから、進行中のジョブに応じて適宜、必要なものをピックアップして選択することもできる。最後に、共用メモリのうちあるメモリが通信に不要である場合には、そのようなメモリはローカルメモリの延長として使用されて、付加的なローカルワークスペースを提供することができることに注目されたい。
【0054】
公開鍵サポート
効率的な公開鍵暗号化のためには、公開鍵コプロセッサによって提供される効率的なモジュラ指数関数が必要である。このユニットは、以下の項目を含む。すなわち:・16個の512ビット幅のレジスタで構成される、PKレジスタファイル48・連結されたSK乗算器素子からなる、PK512×32ビット乗算器70(このユニットは、わずか32クロックサイクルで1つの512×512乗算を行なうことができる)・PK512ビット加算器ALU50、これは、2〜16サイクルで、典型的には2サイクル以下で、加算を行なうことができる・単一クロックサイクルで512ビット語をロードおよび記憶するために、PKコプロセッサからの512ビット並列アクセスのために構成される、グローバルメモリ44。
【0055】
PKコアプロセッサは、モジュラ乗算を512ビット語を使用して行なうことによって加速する。本発明のPKユニットを用いる512×512乗算演算は、下に説明する16個の演算処理装置を連結した乗算器素子を用いて、16個の512×32乗算を行なうことによって実現されるであろう。各乗算につき2クロックサイクルが必要とされかつそのような乗算が16回必要とされると仮定すると、1回の512×512乗算に必要なのは32クロックサイクルであり、1回の2048×2048乗算はわずか512クロックサイクルで行なうことができることになる。4096回の乗算を必要とする全体のモジュラ指数演算は、合計200万クロックサイクルを要することになるが、これは、先に説明したPentium(登録商標)の例に比べて80倍の改良を意味する。PKアルゴリズムにおいても同様の性能の改良が期待される。これは、先行技術に比べて大幅な性能の向上を意味し、セッション鍵をより頻繁に変更することが可能になって、セキュリティが向上することを意味する。
【0056】
512ビット加算器
加算器は、公開鍵PKユニットと秘密鍵SKユニットとの間で共用されることはない。加算演算および論理演算がPKおよびSKの双方において共通であるので、各ユニットは自身の加算器を有し、したがって、演算を同時に進行することが可能である。
【0057】
公開鍵PK ALU50内において、512ビットの単一サイクルの加算器は非常に複雑であって、ALUのクリティカルパス時間を大幅に増やすことになるであろう。このため、ALU50内の512ビット加算器は、図6に示すように、16個の32ビット加算器から形成される。動作中、ANDゲート78およびマルチプレクサ80がまず、2つの32ビットオペランド区分を、32ビット加算器A0〜A15の各々に供給する。ここで、ANDゲート78は32ビット幅の動作を表わす。各32ビット加算器は、キャリ出力に加えて、32ビット合計を計算する。1つの加算器のキャリ出力は、Dフリップフロップ79を介して、次の加算器のキャリ入力に接続される。第1のサイクル中にキャリが生成されると、それはフリップフロップ内にクロック入力され、そのフリップフロップにおいてそのキャリは、次のクロックサイクルのためのキャリ入力として利用可能となる。各合計は、Dフリップフロップ81およびマルチプレクサ80を介して同じ加算器の一方入力に戻される。この加算器の他方入力は、連続するクロックサイクル中、ANDゲート78を用いてゼロに保持される。合計を各加算器へのキャリ入力として戻し加算するステップは、32ビット加算器のうちいずれかの出力にキャリが得られる限り繰返される。
【0058】
512ビット加算器の動作は、以下の例を参照してよりよく理解されるであろう。この例においては、実際の実装時の16個の32ビット語の代わりに、4つの4ビットの2進語を使用する。
【0059】
【数1】
【0060】
ここでは、さらなるキャリがもはや得られない最終合計に達するまでに必要とされる加算は2回であった。これは典型的な場合である。加算器が暗号化演算のために使用されるので、加算される回数はある程度ランダムにばらつくと仮定すると安全であろう。初回の加算の後にキャリ出力が得られる可能性は極めて高い。しかし、最下位ビットとして戻され加算されるキャリによって最上位ビットからの別のキャリが得られる可能性は極めて低い。このため、ほとんどの加算演算はわずか2クロックサイクルしか必要としないと予測されるのである。
【0061】
512ビット加算器を構築するという最初の課題に戻って、標準的なキャリ先見型またはキャリバイパス型加算器設計を使用する場合、その加算器を通じるクリティカルパスは極めて長くなるであろう。なぜなら、キャリが、512ビットの演算を行なう何らかの最適化された回路を通じて伝搬されねばならないためである。この加算器は極めて大きくかつ低速であろう。これに対して、本発明の一実施例においては、512ビット加算器は32ビット加算器から構成されている。32ビット加算器の設計は今日ではよく知られておりまた十分に最適化されている。個々の32ビット加算器の最大クロック速度は、512ビットキャリ先見型設計のクロック速度の2倍以上であると予測される。したがって、本発明に従った2以上のサイクルの加算器は、より大きな512ビット加算器よりも、チップ面積の消費量はより少ないのに対し、通常はより高速で動作することができるであろう。
【0062】
最悪の場合、下に説明するように、16個の32ビット加算器の実装において、キャリを有さない最終合計を完全に計算するのに、16サイクルが必要となることも考えられる。ここで再び4ビットの2進語の例を使用して説明すると、以下のようになる。
【0063】
【数2】
【0064】
以上のように、4回の加算が必要であった。一般に、n個の数のグループについては、最大でn回の加算が必要とされる。
【0065】
512×32乗算器
乗算器は占有面積が広い。各秘密鍵演算処理装置は、たとえば下により詳細に説明するIDEA等の、乗算を必要と秘密鍵アルゴリズムを実現するためには、自身の乗算器を含まねばならない。各PE乗算器によって占められる面積を合わせると相当な面積となり、そこで、この面積は、512×32ビット公開鍵乗算器を実現するのに使用される。面積の節約のために、このように大きな512×32乗算器は、各秘密鍵演算処理装置において16個の32×32乗算器を連結することによって実現される。換言すれば、秘密鍵ユニットおよび公開鍵ユニットは、図4のチップレイアウト内に示すように、複数の乗算器素子を共用することが可能である。したがって、乗算器素子の使用は、秘密鍵演算処理装置とPKコアプロセッサとの間で調整されねばならない。なぜなら、PKコアプロセッサは、複数の秘密鍵演算処理装置のうちどの1つが独立して乗算演算を行なっている場合にも、乗算演算を行なうことができないためである。
【0066】
乗算器の連結を説明するために、4×4/4×N乗算器の組合せの簡単な設計を下に示す。ただし、Boothの符号化および4:2コンプレッサ等の、より進歩した乗算器設計技術もまた利用可能である。以下に、簡単な実現例を提示する。
【0067】
【数3】
【0068】
1桁の乗算は、ANDゲートを用いることによって容易に実現することができる。2つの4ビットオペランドを使用した場合、その結果は、部分積の16ビットから構成される。これらの部分積は、効率的に加算されねばならない。部分積はたとえば、2つの4ビット全加算器および1つの6ビット全加算器を使用して加算することができるが、それらは部分積の加算を行なうのに相当な時間を要するであろう。なぜなら、キャリを複数の加算器を通じて伝搬させる必要があるためである。このような加算器実装の全体としての結果は、遅すぎるであろう。よりよい方法として、加算器のキャリが通らねばならない段の数がより少なくて済むような加算器が考えられる。
【0069】
好ましい乗算器の基本的な構成要素は、3つの入力をとってそれら入力の2ビットの合計を出力する、全加算器である。図7に全加算器を、符号を用いて示すが、ここでは、2進数の代わりに四角形を使用して、一般化および簡素化を図っている。上方の3つの四角は全加算器の3つの入力を示し、下方の2つの四角は合計出力およびキャリ出力を示す。キャリが左下側にあるのは、その桁の値が合計のそれの2倍であることを示すためである。
【0070】
4×4乗算器の加算の第1の段を図8に示す。合計線の上方にある16個の四角は、そのいくつかが黒で示され、その他は白い箱として示されているが、これらは、加算されねばならないある部分積のビットを表わしている。黒で示されるビットは、この第1の段において、4つの全加算器82を使用して加算されるものである。白い箱で示すビットは、第1段では加算されずに、図8に矢印で示すように、次の加算段に備えて単に下方に送られるビットである。第1の段における加算器の合計は、合計線の下に示されている。
【0071】
第2の段を図9に示す。矢印はやはり、この現時点の段においては演算されずに単に下に送られるビットを示し、黒い箱で示されるビットは、この現時点における(すなわち第2の)段において加算されるべきビットを示す。ここでもやはり、黒い箱で示したエレメントが4つの全加算器84を使用して加算される。全加算器84によって生成される第2の段の出力には2つの数があり、これらは今度は一般的な4ビットキャリ加算器86で加算されねばならない。
【0072】
さまざまな加算器および乗算器アーキテクチャの性能を比較することは、本発明に従った乗算器の利点を説明するのに役立つであろう。4ビット加算器の簡単な実現例は、図12に示すように、直列に並んだ4つの全加算器A0〜A3で構成される。この設計においては、最も右側の加算器のキャリ出力Coutが、その左側にあるすべての加算器段のそれぞれに影響を及ぼす可能性がある。この設計におけるクリティカルパスはしたがって、4加算器段である。典型的な全加算器が2以上の論理段から構成されるので、1つの4ビット加算器の合計ゲート遅延は8段を超える場合がある。
【0073】
改良された4ビット加算器は、キャリ先見型設計のものである。3ビットのキャリ先見型加算器を図13に示す。4ビット設計はこれよりもわずかに複雑である。ANDゲート102、ORゲート104および排他的ORゲート106の動作の詳細な説明は、周知の回路であるためここでは省略する。キャリ先見型加算器の利点は、キャリが最終合計ビットまでわずか4論理ゲートで伝搬することである。より大きな数に対するより複雑な設計は、より多くの論理段を有するが、それでもキャリ連鎖型設計よりは、やはり高速である。
【0074】
全4×4乗算器において、キャリ保存型設計は、2つの全加算器および最後のキャリ先見型加算器を通じてクリティカルパスを作る。全加算器のみを使用した実現例では、クリティカルパスがより長くなるであろう。なぜなら、連鎖型キャリを使用する簡単な加算器は、キャリ先見型加算器よりも低速だからである。最後に、部分積合計の最初の2つの段で全キャリ先見型加算器を使用した場合には、結果として得られる乗算器はやはり低速となるであろう。なぜなら、キャリ先見型加算器は個々の全加算器よりは低速なためである。なお、本発明に従った乗算器設計は、同じ部分積レベルでは、あるキャリをある加算器から別の加算器へと伝搬することはない。このようにして、乗算器を通じるクリティカルパスが、部分積合計の最初の2段において、2つを超える数の全加算器を含むことを確実に防止している。
【0075】
図10は、はるかに幅の広い4×N乗算器を示す。大きな黒い箱82、84、86は、図9において使用されていたのと同じ全加算器ハードウェアを示す。この場合、全加算器が必要であるが、これは、各状況において3つの入力が合わせて加算されるためである。図9においては、すべての状況において3つの入力の加算が必要とされたわけではなかったので、より簡単な回路を使用することができた。しかし、4×Nを処理することのできるシステムを作るためには、すべての段において好ましくは全加算器が使用され、加えて、2つ以下の入力の場合にどのように処理を行なうべきかを決定する何らかの付加的な回路が必要となる。したがって、デュアルモードの加算器が複数個作られ、そのいくつかは1つの乗算器を有し、この乗算器が自身の複数入力のうち1つを供給することで、先行する段の出力または単一ビットの部分積の、どちらかが選択されるようにする。
【0076】
図11は、図10に示す囲んだ領域82、84、86を実現するのに必要とされる全加算器Aを示し、合せてその左下方に、それぞれのキャリ出力を示す。好ましい実現例においては、各加算器Aは全加算器である。加算器のうちいくつかは、4×4の場合(すなわち秘密鍵の場合)2つの入力のみを有し、これに対し、他の加算器は、4×Nの場合(すなわち公開鍵の場合)3入力を有する。2入力の加算器は、その第3の入力がイネーブル信号でゲート制御されるようにされねばならない。いくつかの加算器はまた、複数入力のうち1つを提供して先の段の出力または単一ビットの部分積のいずれかを選択するようにする、乗算器を必要とする。下方に示されたキャリ先見型加算器86は、4×4の場合に積の最終ビットを生成するために、4つの位置毎に1つのキャリ出力を必要とする。
【0077】
図11において、4×4乗算器の部分積は、以下の部分積のシナリオに対応するように参照符号が付されている。
【0078】
【数4】
【0079】
4×N乗算器については、隣接する部分積もまた考慮に入れねばならない。それらは図11において、以下のシナリオに従って参照符号が付されている。
【0080】
【数5】
【0081】
ここで、D′は、隣接する(左側または右側の)Dの等価物である。8ビットの最終合計は、S7、S6、S5、S4、S3、S2、S1、S0で示され、左側に隣接する乗算器の合計の下方3ビットは、S2′、S1′、S0′で示される。2:1乗算器88は、選択信号Selを有する。一般に、Selが論理1である場合、左側の入力がマルチプレクサの出力に渡され、反対にSelが論理0の場合には、右側の入力がマルチプレクサの出力に渡される。Sel信号はまた、ANDゲート90をゲート制御するのにも使用される。Selが論理1である場合、ANDゲートへの他方入力が出力に渡され、反対に、Selが論理0である場合、ANDゲート90はディスエーブルされて、他方入力の値にかかわらず論理0を渡す。したがって、図11の実現例においては、Selが論理1である場合には4×N乗算器の区分が実現可能となり、積は出力S6〜S3に現われる。Selが論理0であれば、4×4乗算器が実現されて、8ビットの積が出力S7〜S0に現われる。このように、図11の実現例は秘密鍵乗算器素子を示し、これは、1つの乗算器素子としても利用することができ、または、他の同様の乗算器素子と連結されて、はるかに幅の広い公開鍵乗算器を実現するのにも使用することができる。
【0082】
実現例
先に説明した暗号化チップの好ましい実施例を参照して、一般的な暗号化アルゴリズムの実現例を以下に説明する。RC5はおそらくは、実現するのが最も簡単な暗号化アルゴリズムのうちの1つであろう。これは基本的に、3つの種類の演算を利用する。すなわち、XOR、加算および回転である。これらすべては、表1に示すように、上述の演算処理装置のうちのいずれかによってサポート可能である。RC5は可変長のブロックを有するが、最も一般的には、RC5アルゴリズムの各ラウンドは、Si1およびSi2に記憶される64ビットデータブロックおよび鍵値について演算を行なう。これらは、各演算処理装置内の定数であって、そのラウンドおよびその鍵のみに依存する。データを暗号化するために、64ビットの入力ブロックは2つの32ビット語に分割され、それらはその後、前隣りのメモリ内の場所AおよびBに記憶される。出力ブロックは、後ろ隣りのメモリにおけるA_nextおよびB_nextに書込まれることになる。RC5の暗号化アルゴリズムの1ラウンドの例を以下に示す。
【0083】
【数6】
【0084】
各ラウンドは11クロックサイクルを必要とする。暗号化チップが最高400MHZで動作し得る論理プロセスを用いるように設計されている場合には、1秒あたり3600万ブロックを暗号化することが可能である。これは、ECBモードにおいて288MB/sに相当する。12ラウンド(RC5における典型的な例)を想定すると、同じクロック速度で動作する従来技術によるCPUと比較して、本発明の一実施例に従った複数PEの同時実行によって、従来技術によるソフトウェア実装に対して12倍も性能が改良されることになる。
【0085】
IDEAは、利用可能なブロックアルゴリズムのうち最も安全なものの1つであり、その構造ははるかにより複雑である。IDEAは、64ビットの平文ブロックに対して演算を行ない、128ビットの鍵が使用される。同じアルゴリズムを暗号化および解読の両方に使用する。このアルゴリズムの主要な原理は、種々の代数グループの演算、すなわち、XOR、加算モジュロ216および乗算モジュロ216+1等の演算を組合せることである。これらの演算を使用して、16ビットブロックに対する演算を行なう。
【0086】
したがってIDEAは、モジュラ乗算およびモジュラ加算の両方を使用するが、それらはソフトウェアでは費用が高くつく演算である。乗算は、IDEAのゼロの扱いによって複雑化されている。すなわち、乗算において、ゼロは(−1)モジュロ65537と解釈されるのである。この値65537が演算処理装置のレジスタファイルのレジスタr8内にプリロードされていると仮定し、また、レジスタr0がゼロを含むものと仮定して、以下に乗算マクロの例を示す。
【0087】
【数7】
【0088】
IDEAの各ラウンドは、モジュラ乗算、モジュラ加算および排他的ORから構成される。128ビットの鍵がサブ鍵へと分割される。各演算処理装置のサブ鍵は、その鍵およびその演算処理装置のみに応じて変化するので、予め計算してPE内に記憶させておくことが可能である。IDEAに入力される平文は、先に説明したように、16ビットの4つのサブブロックX1〜X4から構成される。各ラウンドは、6つのサブ鍵K1〜K6を使用し、以下のようにコード化することができる。
【0089】
【数8】
【0090】
IDEAは8ラウンドを有するので、本発明の一実施例に従った暗号化チップハードウェア実装はその実行を8倍以上加速する。さらなる加速は、ほとんどのマイクロプロセッサにおいては利用されないモジュラ乗算命令によってもたらされる。上述のコードは、1ラウンドを実行するのにおよそ50クロックサイクルを要する。400MHZにおいて、この暗号化チップは、IDEAで64MB/sのレートで暗号化することができ、これは、チューリッヒのETH大学(ETH University, Zurich)において開発された25MHZハードウェア実装よりも約3倍高速である。
【0091】
データ暗号化標準、すなわちDESは、当初、ハードウェア実装のために設計されたものであり、したがって、ソフトウェアで実現するのが最も困難なアルゴリズムである。それでも、本発明の一実施例に従えば、これは暗号化チップにおいて容易にコード化することが可能である。
【0092】
先の2つのアルゴリズムと同様に、DESもまた、64ビットブロックでデータを暗号化するブロック型暗号である。平文の64ビットブロックが入力であり、64ビットの暗号文が出力となる。ここでもやはり、暗号化と解読の両方が同じアルゴリズムを使用し、DESを対称的なアルゴリズムとしている。DESは、この場合においては56ビットの単一の鍵から、サブ鍵を作成する。これらのサブ鍵は、該当のPEおよびその56ビットの鍵に応じて変化するものであり、したがって、それらは予め計算しておくことが可能である。
【0093】
図14に示すようなDESにおける基本的な概念は、鍵に基づいてテキスト上で代入を行ない引続き置換を行なうものである。以下の演算によってDESのコアが作られている。・拡張:64ビットブロックを2つの32ビット片108、110に分割する。一方の片は暗号化によって影響を受けることがない。(これらの片は1つおきのラウンドで演算される。)影響を受ける方の片が8つの4ビットのグループに分割される。各グループは、それに隣接する2つのビットをコピーすることによって拡張される。・拡張された各グループは、112においてサブ鍵でXOR処理される。・XORの6ビットの結果を使用して、Sボックス(S-box)と呼ばれる、64エントリ×4ビット先見テーブル114をインデックスする。8個のグループの各々が自身のSボックスを使用する。・Sボックスからの出力は116において置換され、それらのビットがスクランブルされる。8個の出力から32ビットが得られる。・その32ビットの出力が、118において、そのブロックの他方の32ビット片とXOR処理される。
【0094】
これらの演算は以下のようにコード化することが可能である。すなわち:拡張は、入力語をコピーしてから、ビットをマスキングすることによって、1つが偶数のSボックス入力を表わし他方が奇数のSボックスの入力を表わす2つの語が存在するようにすることによって行なわれる。これら2つの語を、鍵情報でXOR処理し、その結果を使用して、Sボックスルックアップテーブルをインデックスする。各Sボックスにおけるデータは予め置換され、したがって、Sボックスの出力は32ビットのデータとなる。最終値はすべての構成要素の論理ORである。コードの例を以下に示す。
【0095】
【数9】
【0096】
このサンプルコードは、1ラウンドを実行するのに44クロックサイクルを必要とする。400MHZにおいて、72MB/sのデータレートが達成され得る。このレートは、1〜35MB/sの範囲のレートで暗号化を行なう、1990年代半ばに利用可能となったDESのハードウェア実装に比べて遜色のないものである。VLSIテクノロジー(VLSI Technology)のVM007は、最高200MB/sで暗号化を行なうことが可能である。
【0097】
以上の例の各々において、その性能は、従来技術におけるCPU上のソフトウェア実装よりもはるかに高速であるが、専用ハードウェア実装よりも低速であることが示されている。本発明のハードウェア実装に対する利点は、暗号化チップがプログラマブルであり、したがって、今後想定され得るものも含むどのようなアルゴリズムも実装が可能であるということである。
【0098】
特定的な公開鍵アルゴリズムの例は何ら示さなかったが、既存の方法に対して同様の改良が、本発明の好ましい実施例において説明したのと同様の技術を用いて実現され得るものと理解されたい。
【0099】
均等物
本発明をその好ましい実施例を参照して特定的に図示しかつ説明したが、当業者においては、その形および詳細に、前掲の請求の範囲によって規定される本発明の精神および範囲から離れることなく、種々の変更が行なわれ得ることが理解されるであろう。当業者においては、日常的な作業の範囲を超えることなく、ここに特定的に示した本発明の具体的な実施例に対する多くの均等物が認識されるかまたは確認されるであろう。そのような均等物は、前述の請求の範囲に包含されるものと意図される。
【符号の説明】
【0100】
22 ソース、24,28,34,36 暗号化チップ、26 ネットワーク、30 宛先、32 ルータ。
【特許請求の範囲】
【請求項1】
乗算器回路であって、
各々が第1の長さのオペランド語を受ける複数の乗算器区分と、
乗算器区分が個々の乗算器として動作するときに第1の入力セットを選択し、第2の長さのオペランド語上で動作する幅のより広い乗算器として乗算器区分を連結させるために第2の入力セットを選択する、入力セレクタとを備え、
幅のより広い乗算器は、第1の長さの第1のオペランド語、および前記第1の長さより長い語の長さの第2のオペランド語上で動作する、乗算器回路。
【請求項2】
各乗算器区分は、部分積加算器を含む、請求項1に記載の乗算器回路。
【請求項3】
前記第2の入力セットは、乗算器区分から他の乗算器区分への入力を含む、請求項2に記載の乗算器回路。
【請求項1】
乗算器回路であって、
各々が第1の長さのオペランド語を受ける複数の乗算器区分と、
乗算器区分が個々の乗算器として動作するときに第1の入力セットを選択し、第2の長さのオペランド語上で動作する幅のより広い乗算器として乗算器区分を連結させるために第2の入力セットを選択する、入力セレクタとを備え、
幅のより広い乗算器は、第1の長さの第1のオペランド語、および前記第1の長さより長い語の長さの第2のオペランド語上で動作する、乗算器回路。
【請求項2】
各乗算器区分は、部分積加算器を含む、請求項1に記載の乗算器回路。
【請求項3】
前記第2の入力セットは、乗算器区分から他の乗算器区分への入力を含む、請求項2に記載の乗算器回路。
【図1A】
【図1B】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15A】
【図15B】
【図15C】
【図15D】
【図1B】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15A】
【図15B】
【図15C】
【図15D】
【公開番号】特開2011−8285(P2011−8285A)
【公開日】平成23年1月13日(2011.1.13)
【国際特許分類】
【出願番号】特願2010−189796(P2010−189796)
【出願日】平成22年8月26日(2010.8.26)
【分割の表示】特願2006−195950(P2006−195950)の分割
【原出願日】平成11年2月26日(1999.2.26)
【出願人】(508034325)モサイド・テクノロジーズ・インコーポレーテッド (106)
【Fターム(参考)】
【公開日】平成23年1月13日(2011.1.13)
【国際特許分類】
【出願日】平成22年8月26日(2010.8.26)
【分割の表示】特願2006−195950(P2006−195950)の分割
【原出願日】平成11年2月26日(1999.2.26)
【出願人】(508034325)モサイド・テクノロジーズ・インコーポレーテッド (106)
【Fターム(参考)】
[ Back to top ]