(57)【要約】【課題】  小さな回路規模で高速に多倍長演算を実現する多倍長演算装置を提供すること。【解決手段】  本発明の多倍長演算装置１１０は、直列接続される複数の多ビット加算器１２０を含む。本多ビット加算器１２０は、各々が多倍長数の一部を構成する被加数および加数が入力される入力部Ａ，Ｂと、被加数と加数との下位ビットを加算し、和の下位ビットを出力する下位ビット加算器１２２と、加数の上位ビットが被加数の上位ビットに対する減基数の補数であるという関係を満たすか否かを判定する判定回路１２４と、被加数および加数の上位ビットを加算する第１上位ビット加算器１２６と、被加数と加数との上位ビットを加算する第２上位ビット加算器１２８と、判定の結果に対応して第１上位ビット加算器１２６または下位ビット加算器１２２の桁上がりを当該多ビット加算器１２０の桁上がり出力として選択する選択回路１３０とを含む。【選択図】  図２
2011221878.tif 000002
【特許請求の範囲】
【請求項１】
直列接続される複数の多ビット加算器を含む多倍長演算装置であって、前記多ビット加算器は、
各々が多倍長数の一部を構成する被加数および加数が入力される入力部と、
前記被加数と前記加数との下位ビットを加算し、和の下位ビットを出力する下位ビット加算器と、
前記加数の上位ビットが前記被加数の上位ビットに対する減基数の補数であるという関係を満たすか否かを判定する判定回路と
前記被加数および前記加数の上位ビットを加算する第１上位ビット加算器と、
前記下位ビット加算器が出力する桁上がりを含めて、前記被加数と前記加数との上位ビットを加算し、和の上位ビットを出力する第２上位ビット加算器と、
前記判定の結果に対応して、前記第１上位ビット加算器または前記下位ビット加算器が出力する桁上がりを当該多ビット加算器の桁上がり出力として選択する選択回路と
を含む、多倍長演算装置。
【請求項２】
前記選択回路は、前記関係が満たされないと判定された場合には、前記第１上位ビット加算器が出力する桁上がりを選択し、前記関係が満たされると判定された場合には、前記下位ビット加算器が出力する桁上がりを選択する、請求項１に記載の多倍長演算装置。
【請求項３】
前記多ビット加算器は、さらに、
前記下位ビット加算器が出力する桁上がりをクロックサイクル毎に保持し、前記選択回路に出力する保持回路と、
前記関係が満たされると判定された場合には、前記下位ビット加算器が出力する桁上がりと前記保持回路の出力とが不一致の間、桁上がり伝播中であることを示す信号を出力する通知部と
を含む、請求項１または２に記載の多倍長演算装置。
【請求項４】
前記多倍長演算装置は、さらに、
多倍長数の被加数および加数をそれぞれｒ個のｎビットの被加数および加数に分割し、ｒ個の多ビット加算器それぞれに入力し、前記ｒ個の多ビット加算器すべての桁上がり伝播の完了を待つことによって、多倍長数の加算結果を確定する多倍長加算器
を含む、請求項１〜３のいずれか１項に記載の多倍長演算装置。
【請求項５】
前記多倍長演算装置は、前記多倍長数の被加数および加数を前記多倍長加算器に入力し、結果として出力される前記多倍長数の和を用いて、多倍長数の剰余算、多倍長数の剰余付き乗算または多倍長数のべき乗剰余演算を実行する、請求項４に記載の多倍長演算装置。
【請求項６】
前記判定回路は、前記被加数の上位ビットと前記加数の上位ビットとの各ビットの排他的論理和を演算し、少なくとも１つのビットの結果が偽である場合に、前記関係を満足しないと判定し、すべてのビットの結果が真である場合に、前記関係を満足すると判定する、請求項１〜５のいずれか１項に記載の多倍長演算装置。
【請求項７】
前記上位ビットのビット数が、前記下位ビットのビット数未満である、請求項１〜６いずれか１項に記載の多倍長演算装置。
【請求項８】
直列接続される複数の複数桁の加算器を含む多倍長演算装置であって、前記複数桁の加算器が、
各々が多倍長数の一部を構成する被加数および加数が入力される入力部と、
下位桁側からの桁上がりと独立に、前記被加数および前記加数の加算による桁上がりを演算する桁上がり演算手段と、
下位桁側からの確定した桁上がりを含め演算し、前記被加数と前記加数との和を出力する和演算手段と、
前記加数の一部の桁が、前記被加数の対応する一部の桁に対する減基数の補数であるという関係を満たさない場合に、前記桁上がり演算手段による桁上がりを当該複数桁の加算器の確定した桁上がり出力として選択する選択回路と
を含む、多倍長演算装置。
【請求項９】
請求項１〜８のいずれか１項に記載された多倍長演算装置を含む、暗号化装置。
【請求項１０】
請求項１〜８のいずれか１項に記載された多倍長演算装置を含む、復号装置。
【請求項１１】
直列接続される複数の多ビット加算器を用いて多倍長演算を実行する方法であって、前記多ビット加算器が、入力部と、下位ビット加算器と、第１上位ビット加算器と、第２上位ビット加算器と、判定回路と、前記判定回路の出力に応じて出力を選択する選択回路とを含み、前記方法は、
前記入力部が、各々が多倍長数の一部を構成する被加数および加数の入力を受けるステップと、
前記判定回路が、前記加数の上位ビットが前記被加数の上位ビットに対する減基数の補数であるという関係を満たすか否かを判定するステップと、
前記選択回路が、前記関係が満たされないと判定された場合に前記第１上位ビット加算器による前記被加数および前記加数の上位ビットを加算した結果生じる桁上がりを当該多ビット加算器の桁上がり出力として選択するステップと、
前記下位ビット加算器が、前記被加数と前記加数との下位ビットの和を出力するステップと、
前記第２上位ビット加算器が、前記下位ビット加算器が出力する桁上がりを含めた加算結果である前記被加数と前記加数との上位ビットの和を出力するステップと
を含む、演算方法。
【請求項１２】
前記選択回路が、前記関係が満たされると判定された場合に前記下位ビット加算器が出力する桁上がりを選択するステップを含む、請求項１１に記載の演算方法。
【請求項１３】
前記多ビット加算器が備える通知部が、前記関係が満たされると判定された場合であって、前記下位ビット加算器が出力する桁上がりと、前記下位ビット加算器と前記選択回路との間に設けられる保持回路の出力とが不一致の間、桁上がり伝播中であることを示す信号を出力するステップと、
前記保持回路が、クロックの供給に対応して前記下位ビット加算器の桁上がりを保持し、前記選択回路に出力するステップと
をさらに含む、請求項１１または１２に記載の演算方法。
【請求項１４】
各々が多倍長数の一部を構成する被加数および加数が入力される入力部と、
前記被加数と前記加数との下位ビットを加算し、和の下位ビットを出力する下位ビット加算器と、
前記加数の上位ビットが前記被加数の上位ビットに対する減基数の補数であるという関係を満たすか否かを判定する判定回路と、
前記被加数および前記加数の上位ビットを加算する第１上位ビット加算器と、
前記下位ビット加算器が出力する桁上がりを含めて、前記被加数と前記加数との上位ビットを加算し、和の上位ビットを出力する第２上位ビット加算器と、
前記判定の結果に対応して、前記第１上位ビット加算器または前記下位ビット加算器が出力する桁上がりを当該多ビット加算器の桁上がり出力として選択する選択回路をそれぞれ含む複数の多ビット加算器が直列接続された回路構成を、プログラマブル・ロジック・デバイス上に実現するためのデバイス実行可能なプログラム。
【請求項１５】
前記選択回路は、前記関係が満たされないと判定された場合には、前記第１上位ビット加算器が出力する桁上がりを選択し、前記関係が満たされると判定された場合には、前記下位ビット加算器が出力する桁上がりを選択することを特徴とする、請求項１４に記載のプログラム。
【請求項１６】
請求項１４または１５に記載のプログラムをコンピュータ可読に記録する記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多倍長数の演算処理に関し、より詳細には、小さな回路規模で高速に多倍長演算を実現する多倍長演算装置、該多倍長演算装置を備える暗号化装置、該多倍長演算装置を備える復号装置、該多倍長演算装置が実行する演算方法、該多倍長演算装置を実現するためのプログラム、および該プログラムを記録する記録媒体に関する。
【背景技術】
【０００２】
近年、インターネットバンキング、オンラインショッピングなどが一般的なものとなり、その際のクレジットカード番号など重要な個人情報のやり取りを安全に行うために、ＳＳＬ（Secure Sockets Layer）など、公開鍵暗号化方式、秘密鍵暗号化方式および電子署名などを組み合わせて安全な通信を確立する技術が利用されている。
【０００３】
上記公開鍵暗号化方式のアルゴリズムとしては、ＲＳＡ（Rivest-Shamir-Adleman）方式が最も普及しているアルゴリズムの１つとして知られている。ＲＳＡ方式は、大きな桁数の素数の積を元の２つの整数に素因数分解することが困難であるという素因数分解問題を安全性の根拠とした公開鍵暗号化方式である。ＲＳＡ方式では、公開鍵と秘密鍵とを作成して公開鍵を公開し、公開鍵を用いて暗号化された暗号文を受け取り、秘匿している秘密鍵を用いて復号を行う。暗号化処理および復号処理では、いずれの処理においても、べき乗剰余演算によって平文および暗号文間を変換する。鍵のサイズは、セキュリティ上の観点から１，０２４ビット以上のものが用いられており、平文および暗号文のサイズも同程度のサイズとなるため、多倍長整数のべき乗剰余演算を必要とし、処理負荷が大きく、処理時間も長期化する。
【０００４】
一方、従来より、ＲＳＡ方式は、回路設計の複雑性、スループットの制限等の観点から、主としてソフトウェアにより実装されてきたが、処理負荷が集中するサーバ装置やネットワーク機器等への用途に、暗号化処理および復号処理を高速にハードウェア上で実現する技術の開発への要請が高まっている。
【０００５】
ＲＳＡ方式のハードウェア実装においては、ブースの乗算またはモンゴメリの乗算のアルゴリズムを適用して、多倍長整数のべき乗剰余演算の高速化を図る技術が知られている。例えば、モンゴメリの乗算アルゴリズムを適用することにより、剰余演算を、シフト演算、加算および乗算に置き換え、多倍長演算の四則演算において最も処理時間がかかる除算処理を回避し、一定の高速化を図ることができる。しかしながら、剰余付き乗算が繰り返し実行されるため、さらなる高速化のためには、剰余付き乗算自体を高速に実現する回路設計が課題となる。
【０００６】
この剰余付き乗算の高速化に関連して、非特許文献１は、ＦＰＧＡ（Field Programmable Gate Array）において、パイプライン化、冗長表現演算、ブロックＲＡＭを用いたテーブル参照を適用することにより、高速化を図る技術を開示する（非特許文献１）。上記非特許文献１は、モンゴメリ乗算における桁上がりによる遅延による問題点を指摘し、この桁上がりによる遅延を軽減させる目的で、オペランドをｒビットのブロックに分割し、このブロックに２ビットの冗長ビットを付加し、それぞれブロック毎に独立に計算することを可能とし、モンゴメリ乗算における桁上がりによる遅延を軽減する冗長表現手法を開示している。また非特許文献１は、モンゴメリ乗算回路をパイプライン化することにより、モンゴメリ演算を高速化する技術についても開示する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】「ＦＰＧＡに特化した高速なパイプライン化ＲＳＡ暗号回路の実装」、川上  賢介，重本  耕司，中野  浩嗣、第５回情報科学ワークショップ、ｐｐ１５−１６、２００９年
【発明の概要】
【発明が解決しようとする課題】
【０００８】
一方、べき乗剰余演算のハードウェア実装を検討してみると、モンゴメリの乗算であれ、ブースの乗算であれ、他の演算アルゴリズムであれ、多倍長整数の加算における桁上がりの伝播が、回路における遅延を生じさせ、高速化のボトルネックとなっている。すなわち、多倍長整数の加算における桁上がりを高速に処理することができれば、アルゴリズムにかかわらず、ＲＳＡ方式の暗号化処理および復号処理を高速化することができると考えられる。また、ＲＳＡ暗号化方式に限らず、Diffie-Hellman鍵交換アルゴリズム、楕円曲線暗号方式などにおいても、多倍長整数のべき乗剰余演算を用いているため、桁上がりを高速に処理することができれば、多倍長整数のべき乗剰余演算を用いる種々の演算処理の高速化を図ることができると考えられる。
【０００９】
一方、加算器における桁上がり伝播による遅延を回避する技術としては、桁上がり先読み加算器（Carry Look Ahead Adder）が知られている。しかしながら、この桁上がり先読み加算器では、桁上げ信号を別の論理回路で生成し、基本論理素子の段数を小さくすることができるものの、桁数が大きくなるに伴い回路が複雑化し、回路規模や消費電力が飛躍的に増大してしまう。
【００１０】
また、加算や減算の繰り返し演算、乗算、除算などの複雑な演算に適用する目的では、桁上げ保存加算器（Carry save adder）も知られている。桁上げ保存加算器では、桁上げを伝播させずに、各桁で独自に桁上げと中間和を計算し、計算の最後において、桁上げと中間和とを加算し、最終的な和を得る。しかしながら、この桁上げ保存加算器では、桁上げを蓄積するためのレジスタまたはバッファが必要となり、回路規模が増大してしまう。
【００１１】
したがって、上述した桁上がり先読み加算器や桁上げ保存加算器では、１，０２４ビット以上の多倍長演算が求められるセキュリティ分野では、回路規模がきわめて大きくなってしまう。桁上がり先読み加算器や桁上げ保存加算器は、あらゆる入力による演算結果が一定時間内に確定することを保証するという設計思想に基づくものである。このようなアプローチは、研究開発目的等、ＲＳＡ暗号の暗号化および復号の演算の高速化を追求するという目的では有用であるが、一般的な汎用品に実装する上では過剰性能かつ高コストとなる。
【００１２】
すなわち、暗号化処理および復号処理でボトルネックとなっている、多倍長整数の加算における桁上がりを、小さな回路規模で高速に処理することを可能とし、ひいてはコスト、消費電力を低減することができる技術の開発が望まれていた。
【００１３】
本発明は、上記従来技術に鑑みてなされたものであり、本発明は、ＲＳＡ暗号化方式等で不可欠な剰余付き乗算などの多倍長演算を、当該多倍長演算の基本単位となる多倍長数の加算における桁上がり伝播に起因する遅延を短縮し、小さな回路規模で高速に多倍長演算を処理することができる多倍長演算装置、暗号化装置、復号装置、演算方法、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明者等は、上記従来技術に鑑み、あらゆる入力による演算結果が一定時間内に確定することを保証するという設計思想に拘泥されることなく、鋭意検討を加えた結果、暗号化処理等の演算においては、扱う数値が統計的に充分にランダムであり、加算の際の桁上がりの伝播長が、統計的に見れば平均値は長くはなく、ある桁で桁上がりが生じた場合、それより下位桁からの桁上がりがその桁を越えて伝播することはないという点に着目し、桁上がりの伝播を確率的に処理することにより、多倍長整数の高速な演算を小さな回路規模で実現可能であることを見出し、本発明に至ったのである。
【００１５】
すなわち本発明によれば、下記特徴を有する複数の多ビット加算器が直列接続された多倍長演算装置が提供される。本発明の多倍長演算装置を構成する多ビット加算器は、各々が多倍長数の一部を構成する被加数および加数が入力される入力部と、これら被加数と加数との下位ビットを加算する下位ビット加算器と、上位ビットを処理する手段とを備える。多ビット加算器は、上位ビットを処理する手段として、加数の上位ビットが被加数の上位ビットに対する減基数の補数であるという関係を満たすか（つまり、後述するキャリー・トラッピングが可能となる一定条件が満たさないか）否かを判定する判定回路と、上記下位ビット加算器の桁上がりにかかわらず上位ビットを加算する第１上位ビット加算器と、下位ビット加算器が出力する桁上がりを含めて、上位ビットを加算する第２上位ビット加算器とを備える。そして、選択回路により、上記判定回路による判定の結果に対応して、第１上位ビット加算器または下位ビット加算器が出力する桁上がりを当該多ビット加算器の桁上がり出力として選択する。多倍長数の被加数および加数の和は、第２上位ビット加算器および下位ビット加算器が出力する。
【００１６】
さらに本発明によれば、下記特徴を有する複数の複数桁の加算器が直列接続された多倍長演算装置が提供される。本発明の複数桁の加算器は、入力される被加数および加数の加算による桁上がりを、下位桁側からの桁上がりと独立に演算する桁上がり演算手段と、下位桁側からの確定した桁上がりを含め演算し、被加数と加数との和を出力する和演算手段とを備える複数桁の加算器から構成される。複数桁の加算器は、さらに、選択回路を含んで構成され、選択回路は、加数の一部の桁が、被加数の対応する一部の桁に対する減基数の補数であるという関係を満たさない場合には、上記桁上がり演算手段による桁上がりを当該多ビット加算器の確定した桁上がり出力として選択する。
【００１７】
さらに本発明によれば、上記多ビット加算器を用いて多倍長演算を実行する演算方法が提供される。本発明の演算方法では、当該多ビット加算器の入力部が、被加数および加数の入力を受けるステップと、上記判定回路が、上述した関係を満たすか否かを判定するステップと、上記選択回路が、上述した関係が満たされないと判定された場合に第１上位ビット加算器による桁上がりを当該多ビット加算器の桁上がり出力として選択するステップと、上記下位ビット加算器が、下位ビットの和を出力するステップと、上記第２上位ビット加算器が、下位ビット加算器が出力する桁上がりを含めた加算結果である上位ビットの和を出力するステップとを含む。
【００１８】
また、さらに本発明によれば、上記多倍長演算装置を含んで構成される暗号化装置および復号装置、上記多倍長演算装置をプログラマブル・ロジック・デバイス上に実現するためのプログラム、ならびに該プログラムを記録する記録媒体が提供される。
【発明の効果】
【００１９】
上記構成によれば、入力される数値が統計的に充分にランダムであれば、多ビット加算器の上位側へ出力する桁上がりを、高い確率で、その下位側から入力される桁上がりと無関係に確定することができる。これにより、小さな回路規模で、桁上がり伝播に起因したアナログ的な遅延を好適に短縮し、動作クロックへの制限を緩和することができ、ひいては、回路規模に対して、全体的なスループットを向上することができる。
【図面の簡単な説明】
【００２０】
【図１】本実施形態の多倍長加算器の全体的な概略構成を示す図。
【図２】本実施形態のｎビット加算器の回路構成を示す図。
【図３】キャリー・トラッピングが可能な一定条件が満たされる場合のｎビット加算器における桁上がりの伝播経路を示す図。
【図４】キャリー・トラッピングが可能な一定条件が満たされない場合のｎビット加算器における桁上がりの伝播経路を示す図。
【図５】本実施形態の多倍長加算器を使用した多倍長整数の加算方法を示すフローチャート。
【図６】本実施形態のｎビット加算器における各素子が出力する論理レベルの遷移を模式的に示すタイミングチャート。
【発明を実施するための形態】
【００２１】
以下、本発明を図面に示した特定の実施形態をもって説明するが、本発明は、図面に示した実施形態に限定されるものではない。なお、以下に説明する実施形態では、本発明の多倍長演算装置の一例として、種々の多倍長演算の基本単位である多倍長整数の加算を処理する加算器（以下、多倍長加算器という。）を用いて説明する。
【００２２】
図１は、本実施形態の多倍長加算器の全体的な概略構成１００を示す図である。図１に示す多倍長加算器１１０は、ｒ個のｎビット（ｎ桁）の多ビット加算器（以下、ｎビット加算器という。）１２０−１〜１２０−ｒが直列接続されて構成される。多倍長加算器１１０には、全体でｒ×ｎビットのビット長をそれぞれ有する被加数および加数が、前段の回路から入力され、多倍長加算器１１０は、これらｒ個のｎビット加算器１２０を用いて、ｒ×ｎビットの被加数および加数の加算を実行し、ｒ×ｎビットの和と、適宜１ビットの桁あふれとを、演算結果として後段の回路へ出力する。
【００２３】
各々のｎビット加算器１２０は、ｎビットの被加数が入力される入力部Ａと、ｎビットの加数が入力される入力部Ｂと、適宜前段からの桁上がりが入力される入力部Ｃｉとを備える。各々のｎビット加算器１２０には、上記ｒ×ｎビットの多倍長整数の被加数および加数のうち、各々のｎビット加算器１２０に割り振られたｎビット分が、それぞれ入力部Ａおよび入力部Ｂを介して入力され、適宜前段からの桁上がりが入力部Ｃｉを介して入力されて、各々のｎビット加算器１２０は、割り振られたｎビット分についての加算を実行する。
【００２４】
各々のｎビット加算器１２０は、さらに、演算結果として、ｎビット分の和を出力する出力部Ｓと、その桁上がりを出力する出力部ＣＯとを備える。最下位のｎビット加算器１２０−１の出力部ＣＯが出力する信号Ｃ１は、その１つ上位のｎビット加算器１２０−２の入力部Ｃｉに入力され、同様に、最上位のｎビット加算器１２０−ｒの入力部Ｃｉには、その１つ下位のｎビット加算器（図示せず）からの信号Ｃｒ−１が入力される。このように下位側から上位側へ桁上がりが伝達されることにより、ｒ×ｎビットの多倍長整数の被加数および加数の正しい加算結果が得られることになる。
【００２５】
一方、このような多倍長整数の加算器を、桁上げ伝播加算器（Ripple Carry Adder）として構成した場合、最悪の場合、最下位桁から最上位桁までの桁上がり伝播が発生し、このアナログ的な遅延時間が顕著なものとなる。このため、この遅延時間を考慮して演算装置の動作クロックが制限されることになる。一方、全体を桁上げ先読み加算器や桁上げ保存加算器として構成すると、桁数の増加に伴い回路規模が飛躍的に増大する。
【００２６】
そこで本実施形態の多倍長加算器１１０では、ｒ×ｎビットの加算器をｒ個のｎビット加算器１２０に分割して構成するとともに、ｎビット加算器１２０各々に上記桁上がり伝播を分断する仕組みを設ける。この桁上がりの伝播を分断する仕組みは、詳細は後述するが、一定の条件が満たされる場合、ｎビット加算器１２０の上位側への桁上がりを、その下位側から伝達される桁上がりと無関係に確定することができるという、新奇な着想に基づくものである。
【００２７】
一方、この仕組みでは、上記一定の条件が満たされない場合も発生し得るが、この場合、ｎビット加算器１２０は、その下位側から伝達される桁上がりに応じた正しい桁上がりをクロック毎に上位側のｎビット加算器１２０に伝達する。そして、この状態の発生を監視できるようにするため、ｎビット加算器１２０は、通知部Ｐを備え、桁上がりをクロック毎に上位側の伝達する場合は、通知部Ｐを介して、この桁上がりが伝播中である旨を通知する信号（例えば論理レベル「１」）を伝播監視部１４０に出力する。
【００２８】
すべてのｎビット加算機１２０について上記一定の条件が満たされる場合には、１クロックサイクルで正しい加算結果が得られることになる。一方、少なくとも１つのｎビット加算器１２０において上記一定の条件が満たされない場合には、ｎビット加算器１２０の通知部Ｐの信号すべてが桁上がりが伝播中ではない旨を通知する信号（例えば論理レベル「０」）となるまでクロックを供給し、桁上がりの伝播が収束するのを待つことにより、正しい加算結果を得る。この場合、１クロックないし数クロックの遅延を生じさせるが、入力される数値が統計的に充分にランダムであれば、このような遅延を生じさせる確率がきわめて低いため、正しい演算結果が得られるまでの時間の期待値は、１クロックに近似することになる。
【００２９】
以下、図１に示したｎビット加算器１２０の詳細について説明する。図２は、ｎビット加算器１２０の回路構成を示す。なお、説明の便宜上、注目するｎビット加算器１２０の上位側のものを上位側ｎビット加算器１２０Ｈと参照し、下位側のものを下位側ｎビット加算器１２０Ｌと参照する。図２に示すｎビット加算器１２０では、入力されるｎビットの被加数および加数は、さらに２つに分割して処理され、ｎビット加算器１２０は、ｎビットのうち上位ｍビットを処理する回路と、ｎビットのうち下位ｎ−ｍビットを処理する回路とに分けて構成されている。
【００３０】
ｎビット加算器１２０は、下位ｎ−ｍビットを処理する回路として、ｎ−ｍビット長の加算を処理するｎ−ｍビット加算器（以下、下位ビット加算器という。）１２２を備える。下位ビット加算器１２２は、ｎビットのうち下位ｎ−ｍビットを処理し、当該ｎビット加算器１２０に入力される被加数Ａ（ｎビット）および加数Ｂ（ｎビット）のうちの下位ｎ−ｍビットについての加算を実行し、演算結果として、下位ｎ−ｍビットの和Ｓおよび桁上がりＣＯを出力する。ここで、下位ビット加算器１２２は、当該ｎビット加算器１２０が最下位のものでなければ、下位側ｎビット加算器１２０Ｌから伝達される桁上がりを含めて演算する。
【００３１】
一方、上位ｍビットを処理する回路としては、ｎビット加算器１２０は、上位ｍビットの加算結果における桁上がりを監視する桁上がり監視回路１２４と、２つのｍビット加算器１２６，１２８とを備える。以下、第１番目のｍビット加算器１２６を第１上位ビット加算器と参照し、第２番目のｍビット加算器１２８を第２上位ビット加算器と参照する。また、ｎビット加算器１２０は、上記桁上がり監視回路１２４から出力される信号を選択制御信号として、上位側ｎビット加算器１２０Ｈへ出力する桁上がり（当該ｎビット加算器１２０が最上位のものであれば桁あふれ）の伝達経路を選択するセレクタ１３０を備える。桁上がり監視回路１２４およびセレクタ１３０は、それぞれ、本実施形態の判定回路および選択回路を構成する。また、第１上位ビット加算器１２６は、本実施形態の桁上がり演算手段を構成することができ、下位ビット加算器１２２および第２上位ビット加算器１２８は、本実施形態の和演算手段を構成することができる。
【００３２】
なお、上述した下位ビット加算器１２２、第１上位ビット加算器１２６および第２上位ビット加算器１２８の個々の多ビット加算器は、桁上がり伝播加算器（ＲＣＡ）や桁上がり先読み加算器（ＣＬＡ）など、いかなる構成の多ビット加算器として実装することができる。多ビット加算器１２２，１２６，１２８を例えば桁上がり先読み加算器として構成しても、扱う数値のビット長が、多倍長整数のビット長ｒ×ｎから分割され、さらに上位と下位とに分割されたものであるため、回路規模を一定範囲内に抑制することができるからである。
【００３３】
桁上がり監視回路１２４は、被加数Ａおよび加数Ｂの上位ｍビット中のビット間の排他論理和を演算し、上位ｍビットすべての排他論理和が「真（１）」である場合には、論理レベル「１」を出力し、一方、上位ｍビット中の少なくともいずれか１つのビットの排他論理和が「偽（０）」である場合には、論理レベル「０」を出力する。桁上がり監視回路１２４の論理レベル「０」は、後述するキャリー・トラッピングが可能な一定条件が満たされていることを示し、論理レベル「１」は、キャリー・トラッピングが可能な一定条件が満たされていないことを示す。なお、説明の便宜上、具体的な論理レベルを用いて説明するが、他の実施形態では、論理レベルが逆であってもよいことは言うまでもない。
【００３４】
以下、本発明のキャリー・トラッピングについて説明する。本発明のキャリー・トラッピングとは、多ビットの加算において、ある桁で桁上がりが発生すると、それより下位の桁からの桁上がりは、その桁で停止し、その桁を越えて桁上がりが伝播しなくなることをいう。つまり、加算の結果「０」となるビット（キャリー・トラップ）が存在すれば、それよりも下位桁から伝達される桁上がりは、その桁に捕捉され、それよりも上位桁の桁上がりに影響を及ぼさないことになる。また、多ビットの加算において、加算の結果「０」となるビットが存在しない場合というのは、加算の結果、桁上がりを発生させない最大の数値となることを意味するため、被加数が加数の１の補数（２進数における減基数１の補数）となる関係を満たす被加数および加数の一部の組み合わせを除き、キャリー・トラッッピングが可能な条件が満たされることになる。
【００３５】
このようなキャリー・トラップの有無は、上記桁上がり監視回路１２４により判定することができる。すなわち、被加数Ａと被加数Ｂの上位ビットの少なくともいずれか１ビット間の排他論理和が「偽（０）」であるという条件が満たされれば、キャリー・トラップが発生することになる。したがって、上記桁上がり監視回路１２４が「０」を出力する場合、下位ビット加算器１２２からの桁上がりは、上位ｍビットの加算結果中に捕捉され、上位側に伝播されない。つまり、上位ｍビットの加算結果については、桁上がりに限れば、下位ビット加算器１２２からの桁上がりに関係なく、確定することができることになる。
【００３６】
そこで、このような下位ビット加算器１２２の演算結果に依存しない上位ｍビットの桁上がりについては、第１上位ビット加算器１２６において演算し、その一方で、上位ｍビットの和については、第２上位ビット加算器１２８において、下位ビット加算器１２２からの桁上がりの伝達を受けて、正しい和を演算する。
【００３７】
図３は、キャリー・トラッピングが可能な一定条件が満たされる場合のｎビット加算器１２０における桁上がりの伝播経路を示す図である。図３に示す例では、被加数Ａの上位ｍビットが「０００１０１１１」であり、加数Ｂの上位ｍビットが「１１１０１０１０」とされている。この場合、上位ｍビットの下位側から２番目のビットで桁上がりが発生し、キャリー・トラップが生成されるため、桁上がり監視回路１２４は、キャリー・トラッピングが可能であることを示す論理レベル「０」を出力する。
【００３８】
第１上位ビット加算器１２６は、自身への桁上がりの入力が「０」であるとして、上位ｍビットを加算し、その結果である桁上がり有り「１」を出力する。この場合、第１上位ビット加算器１２６の桁上がりの演算結果は、入力される桁上がりとは無関係に同一の値となる。ｎビット加算器１２０のセレクタ１３０は、上記桁上がり監視回路１２４が出力する論理レベル「０」に対応して、第１上位ビット加算器１２６が出力する桁上がりを当該ｎビット加算器１２０の桁上がり出力Ｃ０として選択し、上位側ｎビット加算器１２０Ｈへ出力する。この場合、第１上位ビット加算器１２６は、下位ビット加算器１２２および下位側ｎビット加算器１２０Ｌとはアナログ的に切り離されているため、下位側ｎビット加算器１２０Ｌの桁上がり、さらにこれに依存する下位ビット加算器１２２からの桁上がりの確定を待たずに、上位側に出力する桁上がりが確定される。
【００３９】
上位ｍビットの和については、第１上位ビット加算器１２６の和出力ではなく、第２上位ビット加算器１２８が、下位ビット加算器１２２から伝達される桁上がりに応じた上位ｍビットの正しい和を出力する。したがって、第２上位ビット加算器１２８および下位ビット加算器１２２の合計ｎビットで構成される和が当該ｎビット加算器１２０の和Ｓとして出力される。
【００４０】
図４は、キャリー・トラッピングが可能な一定条件が満たされない場合のｎビット加算器１２０における桁上がりの伝播経路を示す図である。図４に示す例では、被加数Ａの上位ｍビットが「０００１０１０１」であり、被加数Ｂの上位ｍビットが「１１１０１０１０」とされている。この場合、上位ｍビットすべてのビットにおいて排他論理和が「真（１）」であり、キャリー・トラップが存在しないため、桁上がり監視回路１２４は、キャリー・トラッピングできないことを示す論理レベル「１」を出力する。
【００４１】
この場合、下位ビット加算器１２２からの桁上がりは、上位ｍビットの加算結果中に捕捉されず、そのままｍビットを伝播することになるため、下位ビット加算器１２２の桁上がりは、当該ｎビット加算器１２０の最終的な桁上がりと一致することになる。そこで本実施形態では、セレクタ１３０は、上記桁上がり監視回路１２４が出力する論理レベル「１」に対応して、下位ビット加算器１２２が出力する桁上がりを当該ｎビット加算器１２０の桁上がり出力Ｃ０として選択し、上位側ｎビット加算器１２０Ｈへ出力する。
【００４２】
また、下位ビット加算器１２２が出力する桁上がりをそのまま上位側ｎビット加算器１２０Ｈに伝達すると、ｍビット分の伝播遅延が短縮されるとは言え、多数のｎビット加算器１２０を直列接続した場合、遅延時間が顕著となる。そこで、本実施形態の多ビット加算器１２０では、クロック毎に、下位ビット加算器１２２が出力する桁上がりをＤ型フリップフロップ１３２にセットし、セレクタ１３０を介して上位側ｎビット加算器１２０Ｈに伝達する。
【００４３】
下位ビット加算器１２２の桁上がり出力と、Ｄ型フリップフロップ１３２の出力とがＸＯＲ素子１３６に入力され、このＸＯＲ素子１３６の出力と桁上がり監視回路１２４の出力とがＡＮＤ素子１３４に入力される。このＡＮＤ素子１３４の出力は、当該ｎビット加算器１２０の通知部Ｐの出力となる。通知部Ｐは、桁上がり監視回路１２４が論理レベル「０」を出力している間は、桁上がり非伝播を通知する信号レベル「０」を出力し、桁上がり監視回路１２４が論理レベル「１」を出力している間は、Ｄ型フリップフロップ１３２の保持状態に応じた論理レベルを出力する。すなわち、Ｄ型フリップフロップ１３２に下位ビット加算器１２２の桁上がりが保持されるまで、言い換えると下位ビット加算器１２２の桁上がりとＤ型フリップフロップ１３２の出力Ｑとが一致するまで、通知部Ｐは、桁上がり伝搬中を通知する論理レベル「１」を出力する。
【００４４】
なお、Ｄ型フリップフロップ１３２の初期値が下位ビット加算器１２２の桁上がりと等しい場合には、桁上がりがクロックに対応してセットされる以前に、下位ビット加算器１２２の桁上がり出力と、Ｄ型フリップフロップ１３２の出力とが一致することになり、非伝搬「０」が通知される。その場合でも、正しい桁上がりが既に上位側ｎビット加算器１２０Ｈに伝達されているため、問題は生じない。また、上位ｍビットの和については、上記桁上がり監視回路１２４が「０」を出力する場合と同様に、下位ビット加算器１２２からの桁上がりが入力される第２上位ビット加算器１２８において、正しい和が演算される。
【００４５】
図５は、本実施形態の多倍長加算器１１０による多倍長整数の加算方法を示すフローチャートである。図５に示す加算方法は、加算すべき多倍長整数の被加数および加数が多倍長加算器１１０に入力されたことに応答して、ステップＳ１００から開始される。ステップＳ１０１では、多倍長加算器１１０が、前段の回路から入力された多倍長整数の被加数および加数をｎビット毎に分割し、各ｎビット加算器１２０に入力する。
【００４６】
ステップＳ１０２では、多倍長加算器１１０は、各ｎビット加算器１２０の通知部Ｐから出力される信号を監視し、すべての信号が非伝播を示す論理レベル「０」であるか否かを判定する。ステップＳ１０２で、少なくとも１つのｎビット加算器１２０が伝播中を示す論理レベル「１」を出力していた場合（ＮＯ）には、制御はステップＳ１０３へ進められる。ステップＳ１０３では、多倍長加算器１１０は、例えば、演算結果の確定待ちであることを示す信号を出力し、正しい演算結果を待つため、各ｎビット加算器１２０にクロックを供給し、制御はステップＳ１０２へループさせられる。
【００４７】
一方、ステップＳ１０２で、すべてのｎビット加算器１２０が非伝播を示す論理レベル「０」を出力していた場合（ＹＥＳ）には、制御はステップＳ１０４へ進められる。この場合、当該クロックサイクル中に正しい演算結果が得られるため、ステップＳ１０４では、多倍長加算器１１０は、各ｎビット加算器１２０から出力されたｎビットの和Ｓを合わせて、正しい多倍長整数の加算結果を出力し、ステップＳ１０５で当該演算方法は終了する。そして、加算すべき次ぎの多倍長整数の被加数および加数が入力される場合には、つぎのクロックサイクルで同様の演算方法が開始される。
【００４８】
図６は、本実施形態のｎビット加算器１２０における各素子が出力する論理レベルの遷移を模式的に示すタイミングチャートである。図５に示す１番目および２番目のクロックサイクルは、注目するｎビット加算器１２０においてキャリー・トラッピングを可能とする条件が満たされない場合に対応する。
【００４９】
まず当該ｎビット加算器１２０の入力部Ａ，Ｂに非加数および加数（ｎビット）が入力されると、桁上がり監視回路１２４は、排他論理和を演算し、論理レベル「１」を出力する。これを受けて、セレクタ１３０は、論理レベル「１」に対応する桁上がり伝播経路、つまり下位ビット加算器１２２からの桁上がりに選択を切り替える（図示せず）。一方、下位ビット加算器１２２は、下位ｎ−ｍビットの加算結果を確定し、正しい下位ｎ−ｍビットの和を出力するとともに、図６の例示では、桁上がりＣｏ［１］を出力する。下位ビット加算器１２２からの桁上がりの伝達を受けて、第２上位ビット加算器１２８は、上位ｍビットの加算結果を確定し、正しい上位ｍビットの和を出力する（図示せず）。一方、Ｄ型フリップフロップ１３２では、その初期値「０」が下位ビット加算器１２２の桁上がり「１」と一致しないため、通知部Ｐは、桁上がり伝播であることを示す論理レベル「１」を出力する。この場合、当該ｎビット加算器１２０の通知部Ｐからの論理レベル「１」の出力に対応して、次ぎの第２番目のクロックサイクルでは、桁上がりの伝播待ちが行なわれる。
【００５０】
第２番目のクロックサイクルでは、サイクル初期のクロックの立ち上がりに対応して、下位ビット加算器１２２の桁上がりＣｏ［１］がＤ型フリップフロップ１３２にセットされ、桁上がり伝播中が解除され、論理レベル「０」が出力される。このとき、下位ビット加算器１２２の桁上がりＣＯが、セレクタ１３０を介して上位側ｎビット加算器１２０Ｈに送られる（図示せず）。残りの上位側ｎビット加算器１２０Ｈすべてにおいて、キャリー・トラッピングが可能となる条件が満たされれば、このクロックサイクル中に正しい演算結果が確定する。他にキャリー・トラッピングが可能となる条件が満たされない上位側ｎビット加算器１２０Ｈが存在する場合には、正しい演算結果が確定するまでにさらなるクロックを必要とする可能性がある。
【００５１】
図６に示す３番目のクロックサイクルは、注目するｎビット加算器１２０においてキャリー・トラッピングを可能とする条件が満たされる場合に対応する。この場合、ｎビット加算器１２０に非加数および加数が入力されると、桁上がり監視回路１２４は、排他論理和を演算し、論理レベル「０」を出力する。これを受けて、セレクタ１３０は、論理レベル「０」に対応する桁上がり伝播経路、つまり第１上位ビット加算器１２６からの桁上がりに選択を切り替える（図示せず）。そして、第１上位ビット加算器１２６の桁上がりが、セレクタ１３０を介して上位側ｎビット加算器１２０Ｈに送られる（図示せず）。
【００５２】
一方、下位ビット加算器１２２は、下位ｎ−ｍビットの加算結果を確定し、正しい下位ｎ−ｍビットの和を出力するとともに、図６の例示では、桁上がりＣｏ［０］を出力する。下位ビット加算器１２２からの桁上がりの伝達を受けて、第２上位ビット加算器１２８は、上位ｍビットの加算結果を確定し、正しい上位ｍビットの和を出力する（図示せず）。ここでは、桁上がり監視回路１２４が論理レベル「０」を出力しているため、Ｄ型フリップフロップ１３２の保持状態に関係なく、通知部Ｐは、非伝播であることを示す論理レベル「０」を出力する。残りの上位側ｎビット加算器１２０Ｈすべてにおいて、キャリー・トラッピングが可能となる条件が満たされれば、このクロックサイクル中に正しい演算結果が確定する。キャリー・トラッピングが可能となる条件が満たされないものが存在する場合には、さらなるクロックを必要となる場合がある。
【００５３】
図６に示す４番目のクロックサイクルは、注目するｎビット加算器１２０においてキャリー・トラッピングを可能とする条件が満たされない場合に対応する。このサイクルでは、桁上がり監視回路１２４は、論理レベル「１」を出力し、下位ビット加算器１２２は、図６の例示では、桁上がりＣｏ［１］を出力する。ここでは、Ｄ型フリップフロップ１３２の初期値が、桁上がりＣｏ［１］をセットする前に既に下位ビット加算器１２２の桁上がり「１」と一致しているため、通知部Ｐは、論理レベル「０」を出力する。そして、下位ビット加算器１２２の桁上がりＣＯと同値のＤ型フリップフロップ１３２の出力Ｑが、セレクタ１３０を介して上位側ｎビット加算器１２０Ｈに送られる（図示せず）。残りの上位側ｎビット加算器１２０Ｈすべてにおいて、キャリー・トラッピングが可能となる条件が満たされれば、このクロックサイクル中に正しい演算結果が確定する。他にキャリー・トラッピングが可能となる条件が満たされない上位側ｎビット加算器１２０Ｈが存在する場合には、正しい演算結果が確定するまでにさらなるクロックを必要とする可能性がある。
【００５４】
以上説明したように、本実施形態の多倍長加算器１１０によれば、各ｎビット加算器１２０において、キャリー・トラッピングを可能とする一定の条件が満たされる場合、その上位側への桁上がりを、その下位側からの桁上がりと無関係に確定することができる。そして、上位側への桁上がりを演算する第１上位ビット加算器１２６は、下位ビット加算器１２２および下位側ｎビット加算器１２０Ｌから切り離されており、下位桁側からの桁上がり伝播を分断し、そのアナログ的な遅延の影響を上位側に及ぼさない。
【００５５】
一方、キャリー・トラッピングを可能とする一定の条件が満たされない場合には、クロックサイクル中に伝播の確定を保証するのではなく、クロックサイクル毎に下位ビット加算器１２２の桁上がりを上位側ｎビット加算器１２０Ｈに伝達し、正しい演算結果が得られるまで待つ。この場合、１クロックないし数クロック分の遅延を生じさせうるが、入力される数値が統計的に充分にランダムであれば、このような遅延を生じさせる確率はきわめて低い。各ｎビット加算器１２０において正しい加算結果が得られるまでの時間は、確率１−２−ｍで１クロックとなり、正しい加算結果が得られるまでの時間の期待値は、１クロックに近似させることができる。
【００５６】
すなわち、本実施形態の多倍長加算器１１０は、遅延が最大化する確率の低い事象に合わせてクロックサイクル内に桁上がりの伝播が収束することを保証するという設計思想ではなく、確率の低い事象が発生した場合は、複数のクロックで処理することによって、動作クロックへの制限を緩和し、全体的な演算の高速化を図るものである。
【００５７】
なお、ｎビットを上位ｍビットとｎ−ｍビットとに分割する際のｍ：ｎ−ｍの比は、上述した１クロック内で正しい演算結果が得られる確率を増加させる観点からｍを大きくする方が望ましいと考えられるが、ｎビット加算器１２０の桁上がりを早期に確定し、動作クロック数を高める観点からは、ｍはｎ−ｍ未満の値とすることが好ましい。
【００５８】
また、上述した実施形態では、多倍長加算器を一例として説明してきが、加算器は種々の演算器の基本単位となるため、本多倍長加算器１１０を使用して、多倍長数の減算、乗算器、剰余算、剰余付き乗算器、べき乗剰余演算器等の多倍長演算装置を構成することができる。また、ＲＳＡ方式等の暗号化処理および復号処理のそれぞれの処理においても、上記乗剰余演算、剰余付き乗算など、多倍長整数の加算が繰り返し実行されることから、本多倍長加算器を使用して暗号化装置および復号装置を好適に構成することもできる。
【００５９】
なお、本実施形態による多倍長加算器、該多倍長加算器を含む他の多倍長演算装置、暗号化装置、復号装置は、例えば、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）などのプログラマブル・ロジック・デバイス（ＰＬＤ）上に実装することができ、あるいはＡＳＩＣ（特定用途向集積）として実装することができる。ＰＬＤとして実装する場合には、当該多倍長演算装置の回路構成をＰＤＬ上に実現するためにＰＤＬにダウンロードする回路構成データ（ビットストリームデータ）、回路構成データを生成するためのＨＤＬ（Hardware Description Language）、ＶＨＤＬ（Very High Speed Integrated Circuits) HDL）、（Verilog-HDL）により記述されたデータなどの制御プログラムを記録する記録媒体により配布することができる。
【００６０】
以上説明説明したように、本発明の実施形態によれば、ＲＳＡ暗号化方式等で不可欠な剰余付き乗算などの多倍長演算を、当該多倍長演算の基本単位となる多倍長数の加算における桁上がり伝播に起因する遅延を短縮し、小さな回路規模で高速に多倍長演算を処理することができる多倍長演算装置、暗号化装置、復号装置、演算方法、プログラムおよび記録媒体を提供することができる。
【実施例】
【００６１】
以下、本実施形態の多倍長加算器を用いてＲＳＡ方式の暗号処理回路を実装した場合について説明する。
【００６２】
（実施例）
上記実施形態の多倍長加算器を用いて構成したＲＳＡ方式の暗号処理回路を、ＦＰＧＡ（Ｖｉｒｔｅｘ（登録商標）５ファミリ（スピードグレード−３）：Ｘｉｌｉｎｘ（登録商標）社）上に実装し、評価を行った。ハードウェアアルゴリズムの記述には、ＶＨＤＬを使用した。なお、ｎビット加算器は、上位８ビットと、下位２４ビットの合計３２ビットで構成し、３２個のｎビット加算器を直列接続して、１，０２４ビットの多倍長加算器とした。ＲＳＡ方式における法のビット長Ｎを１，０２４ビットとし、筆算方式のＲＳＡ方式の暗号処理回路をＦＰＧＡに実装したところ、回路規模が約１，５００スライス、１ブロックＲＡＭであり、最高動作周波数は、１８０ＭＨｚを達成した。
【００６３】
（考察）
筆算方式では、ＲＳＡ暗号の単位処理当たりの所要クロック数の平均値は、１２．２５×Ｄ×Ｎ＋３．５×Ｄクロックとされ、１，０２４ビットの法を用いる場合、１２，５４７．５×Ｄクロックとなる。ここで、Ｄは、べき部のビット長を表す。本発明の多倍長加算器では、加算に必要な時間が１クロックに近似できるため、上記動作周波数では、べき部Ｄが３ビット長の場合、概ね４．７Ｍｂｐｓの処理速度を達成することができることになる。また、べき部Ｄが１，０２４ビットの場合でも、１４．３ｋｂｐｓを達成することができる。
【００６４】
従来技術では、ＲＳＡ方式の暗号化処理をＦＰＧＡ上に実装する場合、例えば非特許文献１に示すように、１，０２４ビットでは、５０００スライス、６４ＤＳＰブロック、２９〜１２５ブロックＲＡＭを超えるリソースが一般に必要となる。非特許文献１が示す実験結果は、モンゴメリの乗算を用いているため、単純な比較はできないが、本発明によれば、筆算方式においてさえ、１５００スライス、１ブロックＲＡＭという、きわめて少ないリソース使用量で実装することができることが理解される。さらに、非特許文献１には、パイプライン化前の動作周波数が８６．２ＭＨｚである点にも言及がなされているが、これに対し本発明では、このような小さな回路規模にもかかわらず、上記スペックのＦＰＧＡにおいて最高１８０ＭＨｚで動作させることができ、高いスループットが達成できることが理解される。
【００６５】
これまで本発明を、特定の実施形態および実施例をもって説明してきたが、本発明は、上述した実施形態または実施例に限定されるものではなく、他の実施形態、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【符号の説明】
【００６６】
１００…概略構成、１１０…多倍長加算器、１２０…ｎビット加算器、１２２…下位ビット加算器、１２４…桁上がり監視回路、１２６…第１上位ビット加算器、１２８…第２上位ビット加算器、１３０…セレクタ、１３２…Ｄ型フリップフロップ、１３４…ＡＮＤ素子、１３６…ＸＯＲ素子、１４０…伝播監視部、Ａ…入力部、Ｂ…入力部、Ｃｉ…入力部、ＣＯ…出力部、Ｓ…出力部、Ｐ…通知部
【図１】
2011221878.tif 000003
【図２】
2011221878.tif 000004
【図３】
2011221878.tif 000005
【図４】
2011221878.tif 000006
【図５】
2011221878.tif 000007
【図６】
2011221878.tif 000008