JPH04277789A - 演算装置及びこれを用いた暗号化通信方法 - Google Patents
演算装置及びこれを用いた暗号化通信方法Info
- Publication number
- JPH04277789A JPH04277789A JP3040115A JP4011591A JPH04277789A JP H04277789 A JPH04277789 A JP H04277789A JP 3040115 A JP3040115 A JP 3040115A JP 4011591 A JP4011591 A JP 4011591A JP H04277789 A JPH04277789 A JP H04277789A
- Authority
- JP
- Japan
- Prior art keywords
- integer
- storage means
- multiplication
- remainder
- input
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Storage Device Security (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は２つの整数を乗算し、そ
の結果をさらに他の整数で除算した剰余を求める演算、
すなわち、整数Ａ、Ｂ、Ｎに関して、Ａ・ Ｂ ｍｏｄ
Ｎの乗除算を行う整数の演算装置に関する。特に、Ｒ
ＳＡ暗号（池野信一，小山謙二：“現代暗号理論”，電
子情報通信学会，１９８６，６章）のような暗号化技術
に好適な大きな桁の整数の乗除算を行う演算装置に関す
るものである。 【０００２】また、本発明は上記演算装置を用いた暗号
化によって行われる、コンピュータネットワークにおけ
るホームバンク，ファームバンク，及び電子メールや電
子郵便などの様々な通信サービスに用いられる暗号化通
信方法に関する。 【０００３】 【従来の技術】従来、ｎａ・ｍビットの整数Ａとｎｂ・
ｍビットの整数Ｂとｎｎ・ｍビットの整数ＮによるＲ＝
Ａ・ Ｂ ｍｏｄ Ｎの演算を行う大きな桁の整数の乗
除算回路の方式は大きく２つに分けられる。１つは乗除
算をＣ＝Ａ・ Ｂの乗算とＤ＝Ｃ ｍｏｄ Ｎの剰余計
算の２つに分けて実行する方式と、もう１つはＡを１ビ
ット毎に分割したａｎ−ｉ（ｉ＝１・・・ｎａ・ｍ）
に対してＲ＝２・ Ｒ＋ａｎ−ｉ・Ｂ ｍｏｄ Ｎ（ｉ
＝１・・・ｎａ・ｍ）の部分積演算と剰余演算をｎａ・
ｍ回繰り返す方式である。 【０００４】 【発明が解決しようとする課題】前者の方式は乗算回路
と剰余計算回路をパイプライン化した構成を取ることが
多く、構成及び制御が比較的簡単である。しかし、この
方式は乗算結果Ｃを一旦蓄えるメモリや乗算と剰余計算
の回路を独立に持つ必要があり、小さな回路規模で装置
を実現することは困難であった。 【０００５】また、後者の方式は部分積演算とそれに対
する剰余演算であるので回路は比較的コンパクトにまと
めることができる。しかし、１回の部分積剰余演算に対
する桁上がり遅延時間の問題と、ｍｏｄ Ｎを実行する
ためのＲ＞Ｎ判定をいかに行うか等の問題があった。 【０００６】また、乗算に関しては乗算器を用いずａｎ
−ｉ ＝１の時のみ２・ ＲにＢを加算することによっ
て演算を行うことが多く、この場合少なくともｎａ・ｍ
クロック以上必要になり処理速度が低下すると言う問題
点もあった。 【０００７】また、ａｎ−ｉ を複数ビットとした場合
、大きな桁の乗算器や除算器が必要になり、大きな桁数
の乗算器や除算器はＲＯＭやセルライブラリ等がないと
いった問題があった。そして、大きな桁数の乗算器や除
算器を自分で設計する場合、小さな桁数の乗算器や除算
器の回路構成をそのまま拡張したのでは回路構成が非常
に複雑になり実現が難しかった。 【０００８】以上のように、従来の方式には種々の問題
点があり、効率的な乗除算回路の実現は難しかった。 【０００９】そこで、本発明は、上述の欠点を除去し、
大きな桁の整数に関する乗除算を、小さな回路規模で効
率よく高速に実行する演算装置を提供することを目的と
する。 【００１０】 【課題を解決するための手段】上記目的を達成するため
に、本発明では、与えられた第１、第２の整数の積を第
３の整数で除算した剰余を演算する演算装置に、値を保
持する記憶手段と、前記第１の整数を所定のビットずつ
順次入力して前記第２の整数に乗じる乗算手段と、前記
記憶手段からの入力と、前記乗算手段からの入力とを加
算し、前記記憶手段の値において前記第３の整数の最大
桁を越える部分につき、前記第３の整数に対する剰余を
求める演算を施し、その結果を前記記憶手段に出力する
演算手段とを具える。 【００１１】 【実施例】（実施例１）簡単のためにｎａ ＝ｎｂ ＝
ｎｎ ＝ｎとして説明する。ｎ・ ｍビットの３つの整
数をＡ，Ｂ，Ｎとし、Ａ・ Ｂ ｍｏｄ Ｎ＝Ｒの演算
を実行することを考える。ここで、ｍビットの小さな桁
の２つの整数ａ，ｂの乗算ａ・ ｂ＝ｃを実行する乗算
器は公知の構成によって簡単に実現できる。１例として
ＲＯＭによって簡単に構成できることは明らかである。 【００１２】Ａ，Ｂ，Ｎを各々ｍビット毎にｎ分割する
と、次のように表せる。 Ａ＝Ａｎ−１・Ｘｎ−１ ＋Ａｎ−２・Ｘｎ−２＋・・
・ ＋Ａ１・Ｘ＋Ａ０Ｂ＝Ｂｎ−１・Ｘｎ−１ ＋Ｂｎ
−２・Ｘｎ−２＋・・・ ＋Ｂ１・Ｘ＋Ｂ０Ｎ＝Ｎｎ−
１・Ｘｎ−１ ＋Ｎｎ−２・Ｘｎ−２＋・・・ ＋Ｎ１
・Ｘ＋Ｎ０ここで、Ｘ＝２ｍとし、Ａ，Ｂ，Ｎについて
ｍビット毎に上位桁から分割したビット系列を各々Ａｎ
−ｉ ，Ｂｎ−ｉ ，Ｎｎ−ｉ（ｉ＝１・・・ｎ）とす
る。この場合Ａ，Ｂ，Ｎは多項式とみなすことができ、
Ｒ＝Ａ・ Ｂ ｍｏｄ Ｎは次のように表すことができ
る。 Ｒ＝Ａ・ Ｂ−Ｑ・ Ｎ （Ｑ＝［Ａ・ Ｂ／Ｎ］）
ただし、［Ｚ］はＺを超えない整数を表す。 【００１３】従って、次のような実施例によってＲを求
めることができる。 【００１４】（アルゴリズム１） Ｒ０ ＝０ ＦＯＲ ｊ＝１ ＴＯ ｎ
Ｒｊ ＝Ｒｊ−１・Ｘ＋Ａｎ−ｊ・Ｂ−Ｑｊ−１・
Ｎ ＝Ｒｊ−１・Ｘ＋Ａｎ−ｊ
・Ｂ＋Ｅｊ−１ −Ｌｊ−１・Ｘｎ ＮＥＸＴ ＩＦ Ｒｎ ＞Ｎ ＴＨＥＮ Ｒｎ ＝Ｒｎ −
Ｑｎ・Ｎ ただし、Ｌｊ−１ ＝［Ｒｊ−１ ・
Ｘ／Ｘｎ ］＝［Ｒｊ−１ ／Ｘｎ−１ ］
Ｑｊ−１ ＝［Ｌｊ−１・Ｘｎ ／Ｎ
］，Ｑｎ ＝［Ｒｎ ／Ｎ］
Ｌｊ−１・Ｘｎ＝Ｑｊ−１・Ｎ＋Ｅｊ−１ （
Ｅｊ−１ ＜Ｎ）アルゴリズム１はＲ＞Ｎの判定を行わ
ないためにＮの最大桁であるＸｎ−１ を超えたＲｊ−
１・Ｘの値Ｌｊ−１・Ｘｎに対して、ｍｏｄ Ｎを行う
ようにしている。即ち、ビット的にＸｎ−１を超えたＲ
の係数に対してｍｏｄ Ｎを行っているのでＲ＞Ｎの判
定を必要としない。また、Ｌｊ−１・Ｘｎ ｍｏｄ Ｎ
である−Ｑｊ−１・Ｎを実行する代わりに、Ｌｊ−１・
Ｘｎを引いてその剰余であるＥｊ−１ を加えている。 即ち、Ｌｊ−１ をＥｊ−１に変換して加算している。 これによって、ｍｏｄ Ｎによる減算をすべて加算で行
うことができる。ただしこの場合、最後に１度だけＲｎ
＞Ｎを判定して、Ｒｎ ＝Ｒｎ −Ｑｎ・Ｎの演算を
行う必要があるが、これは上に示した繰り返し演算が終
わった後であり、従来のように繰り返し演算の途中でＲ
＞Ｎの判定を行う必要がないので、別の回路等で行うこ
とができ、全体の処理速度には影響しない。 【００１５】次に、Ｒｊ の演算に伴う遅延時間が大き
いという問題があった。その遅延時間をなくすために、
アルゴリズム１においてＲｊ をＲｊ，ｎ−ｉ 、Ｂを
Ｂｎ−ｉ に分解して次のアルゴリズム２のように表現
する。 （アルゴリズム２） ＦＯＲ ｊ＝１ ＴＯ ｎ ＦＯＲ ｉ＝０ ＴＯ ｎ
Ｒｊ，ｎ−ｉ ＝Ｄｊ−１，ｎ−ｉ−１ ＋Ｃｊ−
１，ｎ−ｉ−２ ＋ｄｗｍ （Ａｎ−ｊ・Ｂｎ−ｉ
） ＋ｕｐｍ（Ａ
ｎ−ｊ・Ｂｎ−ｉ−１ ）＋Ｅｊ−１，ｎ−ｉ
Ｄｊ，ｎ−ｉ ＝ｄｗｍ （Ｒｊ，ｎ−ｉ
） Ｃｊ，ｎ−ｉ ＝ｕｐｍ （Ｒｊ，
ｎ−ｉ ） ＮＥＸＴ ＮＥＸＴ ただし、Ｒｊ−１，ｎ・Ｘｎ ＝Ｑｊ−１・Ｎ＋Ｅｊ−
１ ，Ｑｊ−１ ＝［Ｒｊ−１，ｎ・Ｘｎ／Ｎ］ （１
） Ｅｊ−１ ＝Ｅｊ−１，ｎ−１・Ｘｎ−１ ＋Ｅ
ｊ−１，ｎ−２・Ｘｎ−２ ＋・・・ ＋Ｅｊ−１，１
・Ｘ ＋Ｅｊ−１
，０
（２） Ｄ
０，ｎ−ｉ−１ ＝Ｃ０，ｎ−ｉ−２ ＝Ｅ０，ｎ−ｉ
＝Ｂｎ ＝Ｂ−１＝０ ｄｗｍ （Ｚ
）：Ｚの２ｍ 桁以下の値 ｕｐｍ （
Ｚ）：Ｚの２ｍ＋１ 以上の値を２ｍ＋１ で割った値
を意味する。 【００１６】基本的にアルゴリズム１とアルゴリズム２
は同じであるが、アルゴリズム２の方がより実際の回路
の動作に近い形で表している。ここでｎ＝４の場合を考
え、アルゴリズム２を図１のような回路で乗除算器を構
成する。 【００１７】図１はＡｎ−ｊ・Ｂｎ−ｉ を演算するｍ
＊ｍビットの乗算器ｎ個と、Ｒｊ−１，ｎ の値から（
１）、（２）式によってＥｊ−１，ｎ−ｉ の値を各々
出力するＲＯＭｎ個と、２ビットのキャリーを持つ４入
力ｍビット加算器または５入力加算器ｎ＋１個と、Ｒｊ
，ｎ−ｉ を格納するｍ＋２ビットのレジスタｎ個から
構成される。このレジスタの下位ｍビットはＲｊ，ｎ−
ｉ の下位ｍ桁（ｄｗｍ （Ｒｊ，ｎ−ｉ ）＝Ｄｊ，
ｎ−ｉ ）を意味し、上位２ビットはＲｊ，ｎ−ｉ の
ｍ＋１桁以上の値（ｕｐｍ （Ｒｊ，ｎ−ｉ ）＝Ｃｊ
，ｎ−ｉ ）を意味する。これによって、各加算器毎の
桁上がりはＣｊ，ｎ−ｉ によって各クロック毎に吸収
され、次のクロックで桁上がりとして右隣のレジスタの
下位ｍビットともに加算される。従って、アリゴリズム
（１）のようなＲｊ の演算に伴う遅延時間をなくすこ
とができる。以上のようにＤｊ，ｎ−ｉ ，Ｒｊ，ｎ−
ｉ ，Ｃｊ，ｎ−ｉ はレジスタの状態を表すが、添え
字のｊはクロックを意味し、ｎ−ｉは図１において右か
ら左にｉ＝０からｉ＝ｎとなる回路の位置を示す。 従って、初期状態（ｊ＝０）においてＲ０，０ は図１
の左端のレジスタを意味し、Ｒ０，ｎ−１ ＝Ｒ０，３
は右端のレジスタを意味する。ただし、Ｒ０，ｎ ＝
Ｒ０，４ は右端の加算器からの出力を意味する。 【００１８】次に図１の動作について説明する。 【００１９】図１において各レジスタの初期状態（Ｒ０
，ｎ−ｉ−１ ）はオール０とする。このとき、Ｒ０，
ｎ−ｉ−１ ＝０であるのでＤ０，ｎ−ｉ−１ ＝Ｃ０
，ｎ−ｉ−２ ＝０である。 【００２０】最初のクロック（ｊ＝１）でＡ３ が入力
されるとＡ３・Ｂｎ−ｉ（ｉ＝１・・・４）が各乗算器
から出力される。 その値を上位と下位のｍ桁毎に分けて各加算器で加えて
各々のレジスタ（Ｒ１，ｎ−ｉ：ｉ＝１・・・ｎ ）に
格納する。このとき、Ｒ１，ｎ−ｉ（ｉ＝１・・４）
の下位ｍビットはＤ１，ｎ−ｉ として、桁上がりがあ
ればｍ＋１ビット以上はＣ１，ｎ−ｉ としてレジスタ
に格納されている。 【００２１】次のクロック（ｊ＝２）でＡ２ が入力さ
れるとＡ２・Ｂｎ−ｉ（ｉ＝１・・・４）が同様に上の
乗算器から上位と下位ｍビット毎に出力される。このと
きＲ１，４ ＝ｕｐｍ （Ａ３・Ｂ３ ）が右端のレジ
スタから加算器を通して出力されるので、それを受けて
各ＲＯＭからＥ１，ｎ−ｉ の値が各加算器に出力され
る。そのとき、その加算器の左隣にあるレジスタの下位
ｍビットＤｊ−１，ｎ−ｉ−１（ｉ＝２・・・４）も加
算器に入力されるが、２つ左隣のレジスタの上位２ビッ
トＣｊ−１，ｎ−ｉ−２ は桁上がりキャリーとして同
じ加算器に入力される。従って、加算器は２ビットのキ
ャリーを持つ４入力ｍビット加算器または５入力加算器
として構成され、ｍ＋２ビットの出力を返す。従って、
レジスタはｍ＋２ビットのレジスタで構成される。 【００２２】更に次のクロック（ｊ＝３）でＡ１ が入
力されると同様にＡ１・Ｂｎ−ｉ（ｉ＝１・・・４）が
上の乗算器から上位と下位ｍビット毎に出力される。こ
のときＲ２，４ ＝ｕｐｍ（Ａ２・Ｂ３ ）＋ｄｗｍ
（Ａ３・Ｂ３ ）＋Ｅ１，３ が右端のレジスタから加
算器を通して出力される。以下同様に、それを受けて各
ＲＯＭからＥ２，ｎ−ｉ の値が各加算器に出力され、
その加算器の左隣にあるレジスタの下位ｍビットと、２
つ左隣のレジスタの上位２ビットが同じ加算器に入力さ
れる。 【００２３】更に、ｊ＝４のクロックでＡ０ が入力さ
れたときも同様の動作を行い、その結果、各レジスタに
格納された値がＲｎ となっていることが判る。 【００２４】（実施例２）実施例１のアルゴリズム２は
乗算器からの出力をｄｗｍ （Ａｎ−ｊ・Ｂｎ−ｉ ）
とｕｐｍ（Ａｎ−ｊ・Ｂｎ−ｉ−１ ）の２つの出力に
分解しているが、Ｂを定数として扱える場合、図２及び
アルゴリズム３に示すようにＡｎ−ｊ の入力を受けて
、Ａｎ−ｊ・Ｂの値をいくつかのＲＯＭに分割してＡＢ
ｊ，ｎ−ｉ として出力することもできる。 （アルゴリズム３） ＦＯＲ ｊ＝１ ＴＯ ｎ ＦＯＲ ｉ＝０ ＴＯ ｎ
Ｒｊ，ｎ−ｉ ＝Ｄｊ−１，ｎ−ｉ−１ ＋Ｃｊ−
１，ｎ−ｉ−２ ＋ＡＢｊ，ｎ−ｉ ＋Ｅｊ−１，ｎ−
ｉ Ｄｊ，ｎ−ｉ ＝ｄｗｍ （Ｒｊ
，ｎ−ｉ ） Ｃｊ，ｎ−ｉ ＝ｕｐｍ
（Ｒｊ，ｎ−ｉ ） ＮＥＸＴ ＮＥＸＴ ただし、Ａｎ−ｊ・Ｂ＝ＡＢｊ−１，ｎ・Ｘｎ ＋ＡＢ
ｊ−１，ｎ−１・Ｘｎ−１ ＋・・・ ＋ＡＢｊ−１，
０ 【００２５】（実施例３）次に、ＲＯＭなどによる複数
ビット同士の乗算を行わず、アンド回路と加算器だけで
剰余乗算を実現させる例を説明する。 （アルゴリズム４） 【００２６】 【数１】 この装置の構成例を図４に示す。この例では、Ａｎ−ｊ
＝（ａｊ・ｍ＋ｍ−１ ，・・・ ａｊ・ｍ＋１ ，
ａｊ・ｍ ）を１ビット毎独立にｍビット同時に入力さ
せて、ａｊ・ｍ−ｋ・Ｂ（ｋ＝０・・・ｍ−１） を独
立にアンド回路３８（１） 〜３８（ｍ） によって出
力する。このとき、ａｊ・ｍ−ｋ・Ｂは、ａｊ・ｍ−ｋ
が０のとき０、１のときＢである。この出力と、左隣
のレジスタの下位ビットと、その更に左にあるレジスタ
の上位ビットと、ＲＯＭからの出力とをｍ＋３入力の加
算器によって加算していくことによって、剰余乗算が実
現できる。この時の各レジスタ４４〜４７の大きさはｍ
ビットの値のｍ＋３項の和であるから、ｍ＋ｌｏｇ２（
ｍ＋３） 以上あればよい。 【００２７】また、図１〜３において、Ｒｊ，ｎ の値
を１度レジスタにラッチさせるようにしてもよい。この
場合、Ｒｊ，ｎ の値を１度レジスタにラッチするため
に処理に必要な１クロックの最大時間は、乗算または除
算に要する時間だけでよく、アルゴリズム２〜４の演算
を短時間毎に繰り返すことができる。対応する回路構成
を図４〜６に示す。 【００２８】また、アルゴリズム１の代わりに、以下の
アルゴリズムを用いることもできる。 （アルゴリズム５） Ｒ０ ＝０ ＦＯＲ ｊ＝１ ＴＯ ｎ
Ｒｊ ＝Ｒｊ−１・Ｘ＋Ａｎ−ｊ・Ｂ−Ｑｊ−１・
Ｎ・ Ｘ ＝Ｒｊ−１・Ｘ＋Ａ
ｎ−ｊ・Ｂ＋（Ｅｊ−１ −Ｌｊ−１・Ｘｎ ）・ Ｘ
ＮＥＸＴ ＩＦ Ｒｎ ＞Ｎ ＴＨＥＮ Ｒｎ ＝Ｒｎ −
Ｑｎ・Ｎ ただし、Ｌｊ−１ ＝［Ｒｊ−１ ／
Ｘｎ ］ Ｑｊ−１ ＝［Ｌｊ
−１・Ｘｎ＋１／Ｎ］，Ｑｎ ＝［Ｒｎ ／Ｎ］
Ｌｊ−１・Ｘｎ＋１ ＝（Ｑｊ−１
・Ｎ＋Ｅｊ−１ ）・ Ｘ （Ｅｊ−１ ＜Ｎ）
ここで、Ｘは乗算器からの出力Ａｎ−ｊ・Ｂに対して剰
余Ｅｊ−１ の出力をずらすために必要であり、これに
よって図４〜５における左端のレジスタへの入力値演算
のための加算器をなくすことができる。図７〜９に、上
記アルゴリズムに対応する回路構成を示す。 【００２９】また、図７〜図９の各回路の右端に更にレ
ジスタをｃ個追加すれば、−Ｑｊ−１・Ｎ・ Ｘｃ ＝
（−Ｌｊ−１・Ｘｎ＋１ ＋Ｅｊ−１ ）・ Ｘｃ と
なるので、任意に剰余出力Ｅｊ−１ をずらすことも可
能である。 【００３０】以上によって入力値がｍビット毎にｎ分割
されて入力されるときｎ・ ｍビットの乗除算回路が効
率的に実現できることが示せた。これは、ｎａ ≠ｎ，
ｎｂ ≠ｎ，ｎｎ ≠ｎの場合にも同様の回路構成で乗
除算回路が実現できることは明かである。 【００３１】以上述べた実施例の回路では、Ｃｊ，ｎ−
ｉ によって桁上がりを一旦ホールドするために桁上が
りに関する遅延時間はなく、アルゴリズム２〜４の演算
を短時間毎に繰り返すことができる。 【００３２】また、Ｎの最大桁であるＸｎ−１ を超え
たＲｊ−１の値Ｌｊ−１・Ｘｎ に対して、ｍｏｄＮを
行うようにしているのでＲ＞Ｎの判定を行わなくてよい
。また、−Ｑｊ−１・Ｎを実行する代わりに、−Ｑｊ−
１・Ｎ＝−Ｌｊ−１・Ｘｎ ＋Ｅｊ−１ であるＥｊ−
１ を加えることによって剰余演算を全て加算によって
行っている。 【００３３】また、乗算を小さな桁毎に分解して実行し
たり（アルゴリズム２）、Ｂが定数の場合ＲＯＭによっ
て構成したり（アルゴリズム３）、乗算器を用いずアン
ドと加算器のみで乗算を実行したり（アルゴリズム４）
することによって大きな桁の乗算を行う乗算器を用いる
ことなく乗算が実行できる。従って、ＴＴＬやセルライ
ブラリなどによって小さな桁の乗算器が簡単に用いるこ
とができる場合にはアルゴルズム２、Ｂを定数として扱
える場合にはアルゴリズム３、ＲＯＭやセルライブラリ
の乗算器等がない場合はアルゴリズム４に対応する乗除
算回路が適している。 【００３４】また、図１〜９のような同一の演算素子の
繰り返しによる構成はＶＬＳＩ等の大規模回路を構成し
やすいという利点もある。 【００３５】（実施例５）次に、上述の演算装置を用い
た暗号化通信の方法を説明する。通信しようとする平文
をＭ，暗号文をＣ，公開暗号鍵をｅ，復号鍵をｄ，公開
された法をＮとすると、ＲＳＡ暗号の暗号化と復号は次
のようなべき乗剰余演算で表される。 【００３６】暗号化：Ｃ＝Ｍｅ ｍｏｄ Ｎ復号：Ｍ＝
Ｃｄ ｍｏｄ Ｎ 従って、ＲＳＡ暗号の暗号化と復号化は同様なべき乗剰
余演算回路によって実現できる。そこで、以下では暗号
化についてのみ説明する。 【００３７】べき乗剰余演算：Ｃ＝Ｍｅ ｍｏｄ Ｎは
、単純に２数の剰余乗算を行っても実現できるが、Ｍ、
ｅが大きいと、その計算量は莫大なものとなる。そのた
め、本発明では、以下のアルゴリズムに従って計算を実
行する。ただし、ｅはｋビットからなる整数であり、ｅ
＝ｅｋ，ｅｋ−１，・・・，ｅ２，ｅ１ で表されると
する。 【００３８】 ＩＮＰＵＴ Ｍ，ｅ，Ｎ
（入力） Ｃ＝
１
（初期設定） ＦＯＲ
ｉ＝ｋ ＴＯ １ ＩＦ ｅｉ＝１ ＴＨＥＮ Ｃ＝Ｃ
・ Ｍ ｍｏｄ Ｎ （演算１）
ＩＦ ｉ ＞１ ＴＨＥＮ Ｃ＝Ｃ・ Ｃ
ｍｏｄ Ｎ （演算２） ＮＥＸＴ 従って、この場合、べき乗剰余演算は、Ｃ＝Ｃ・
Ｂ ｍｏｄ Ｎ（ＢはＭまたはＣ）の剰余乗算の繰り返
しによって実現される。この剰余乗算は図１のごとき回
路によって実現できる。このアルゴリズムを効率的に実
行する回路を図２に示す。１０１、１０２は各々Ｍ，ｅ
，の値を格納するシフトレジスタであり、１０３、１０
４は各々Ｎ，Ｃの値を格納するレジスタである。また、
１０５，１０６は入力を選択するセレクタスイッチ、１
０７はレジスタ１０４のＣの値をｍビット毎（ｍは任意
の整数）に上位桁から選択しシリアルに出力するマルチ
プレクサ、１０８はＣ＝Ｃ・ Ｂ ｍｏｄ Ｎの演算を
実行する剰余乗算回路である。１０９はｅｉ＝１または
ｉ ＞１を判定して演算１，２の実行を制御したり、入
力及び初期設定時にセレクタやレジスタのクリア信号や
プリセット信号などを制御するコントローラであり、カ
ウンタとＲＯＭといくつかの論理回路によって簡単に実
現できる。 【００３９】次に、この回路の動作について説明する。 【００４０】入力は平文Ｍと公開された鍵ｅとＮである
。そこでレジスタ１０１〜１０３に、Ｍ，ｅ，Ｎをシリ
アルまたはパラレルに入力する。このとき、セレクタ１
０５はＭを選択することでＭをレジスタ１０１に入力す
る。それと同時に、レジスタ１０４にはＣの値を入力す
る代わりに、レジスタのクリア信号またはプリセット信
号によってＣ＝１となるように初期設定する。 【００４１】入力及び初期設定が終了すると、演算１，
２に示した剰余乗算が開始される。ここで、演算１，２
の違いは剰余乗算Ｃ＝Ｃ・ Ｂ ｍｏｄ Ｎにおいて、
ＢがＭかＣかの違いである。従って、演算１を実行する
ときは、セレクタ１０６はレジスタ１０１からのｍビッ
ト毎のシリアル出力Ｍを選択し、演算２を実行するとき
はマルチプレクサ１０７からのｍビット毎のシリアル出
力であるＣを選択するように制御される。また、シフト
レジスタ１０１からのｍビット毎のシリアル出力Ｍはセ
レクタ１０５を介して、再びシフトレジスタ１０１に入
力される。剰余乗算回路１０８の構成及び動作は前述の
通りである。剰余乗算回路１０８の出力するＣをレジス
タ１０４にパラレル入力し、次の剰余乗算に用いること
によって演算１，２が効率的に繰り返される。 【００４２】また、この装置で、Ｍ、ｅの代わりに、Ｃ
、ｄを入力することにより、暗号文の複号を行うことが
できる。 【００４３】 【発明の効果】以上説明したごとく、本発明の演算装置
によれば、小さな回路規模で、高速な剰余乗算が実行で
きるという効果がある。 【００４４】また、本発明演算装置は同一の演算素子の
繰り返しにより構成されるので、ＶＬＳＩ等による回路
化を実現しやすいという効果もある。 【００４５】また、本発明によれば、暗号化通信のため
の暗号化／複号装置を小さな回路規模で実現できるとい
う効果がある。
の結果をさらに他の整数で除算した剰余を求める演算、
すなわち、整数Ａ、Ｂ、Ｎに関して、Ａ・ Ｂ ｍｏｄ
Ｎの乗除算を行う整数の演算装置に関する。特に、Ｒ
ＳＡ暗号（池野信一，小山謙二：“現代暗号理論”，電
子情報通信学会，１９８６，６章）のような暗号化技術
に好適な大きな桁の整数の乗除算を行う演算装置に関す
るものである。 【０００２】また、本発明は上記演算装置を用いた暗号
化によって行われる、コンピュータネットワークにおけ
るホームバンク，ファームバンク，及び電子メールや電
子郵便などの様々な通信サービスに用いられる暗号化通
信方法に関する。 【０００３】 【従来の技術】従来、ｎａ・ｍビットの整数Ａとｎｂ・
ｍビットの整数Ｂとｎｎ・ｍビットの整数ＮによるＲ＝
Ａ・ Ｂ ｍｏｄ Ｎの演算を行う大きな桁の整数の乗
除算回路の方式は大きく２つに分けられる。１つは乗除
算をＣ＝Ａ・ Ｂの乗算とＤ＝Ｃ ｍｏｄ Ｎの剰余計
算の２つに分けて実行する方式と、もう１つはＡを１ビ
ット毎に分割したａｎ−ｉ（ｉ＝１・・・ｎａ・ｍ）
に対してＲ＝２・ Ｒ＋ａｎ−ｉ・Ｂ ｍｏｄ Ｎ（ｉ
＝１・・・ｎａ・ｍ）の部分積演算と剰余演算をｎａ・
ｍ回繰り返す方式である。 【０００４】 【発明が解決しようとする課題】前者の方式は乗算回路
と剰余計算回路をパイプライン化した構成を取ることが
多く、構成及び制御が比較的簡単である。しかし、この
方式は乗算結果Ｃを一旦蓄えるメモリや乗算と剰余計算
の回路を独立に持つ必要があり、小さな回路規模で装置
を実現することは困難であった。 【０００５】また、後者の方式は部分積演算とそれに対
する剰余演算であるので回路は比較的コンパクトにまと
めることができる。しかし、１回の部分積剰余演算に対
する桁上がり遅延時間の問題と、ｍｏｄ Ｎを実行する
ためのＲ＞Ｎ判定をいかに行うか等の問題があった。 【０００６】また、乗算に関しては乗算器を用いずａｎ
−ｉ ＝１の時のみ２・ ＲにＢを加算することによっ
て演算を行うことが多く、この場合少なくともｎａ・ｍ
クロック以上必要になり処理速度が低下すると言う問題
点もあった。 【０００７】また、ａｎ−ｉ を複数ビットとした場合
、大きな桁の乗算器や除算器が必要になり、大きな桁数
の乗算器や除算器はＲＯＭやセルライブラリ等がないと
いった問題があった。そして、大きな桁数の乗算器や除
算器を自分で設計する場合、小さな桁数の乗算器や除算
器の回路構成をそのまま拡張したのでは回路構成が非常
に複雑になり実現が難しかった。 【０００８】以上のように、従来の方式には種々の問題
点があり、効率的な乗除算回路の実現は難しかった。 【０００９】そこで、本発明は、上述の欠点を除去し、
大きな桁の整数に関する乗除算を、小さな回路規模で効
率よく高速に実行する演算装置を提供することを目的と
する。 【００１０】 【課題を解決するための手段】上記目的を達成するため
に、本発明では、与えられた第１、第２の整数の積を第
３の整数で除算した剰余を演算する演算装置に、値を保
持する記憶手段と、前記第１の整数を所定のビットずつ
順次入力して前記第２の整数に乗じる乗算手段と、前記
記憶手段からの入力と、前記乗算手段からの入力とを加
算し、前記記憶手段の値において前記第３の整数の最大
桁を越える部分につき、前記第３の整数に対する剰余を
求める演算を施し、その結果を前記記憶手段に出力する
演算手段とを具える。 【００１１】 【実施例】（実施例１）簡単のためにｎａ ＝ｎｂ ＝
ｎｎ ＝ｎとして説明する。ｎ・ ｍビットの３つの整
数をＡ，Ｂ，Ｎとし、Ａ・ Ｂ ｍｏｄ Ｎ＝Ｒの演算
を実行することを考える。ここで、ｍビットの小さな桁
の２つの整数ａ，ｂの乗算ａ・ ｂ＝ｃを実行する乗算
器は公知の構成によって簡単に実現できる。１例として
ＲＯＭによって簡単に構成できることは明らかである。 【００１２】Ａ，Ｂ，Ｎを各々ｍビット毎にｎ分割する
と、次のように表せる。 Ａ＝Ａｎ−１・Ｘｎ−１ ＋Ａｎ−２・Ｘｎ−２＋・・
・ ＋Ａ１・Ｘ＋Ａ０Ｂ＝Ｂｎ−１・Ｘｎ−１ ＋Ｂｎ
−２・Ｘｎ−２＋・・・ ＋Ｂ１・Ｘ＋Ｂ０Ｎ＝Ｎｎ−
１・Ｘｎ−１ ＋Ｎｎ−２・Ｘｎ−２＋・・・ ＋Ｎ１
・Ｘ＋Ｎ０ここで、Ｘ＝２ｍとし、Ａ，Ｂ，Ｎについて
ｍビット毎に上位桁から分割したビット系列を各々Ａｎ
−ｉ ，Ｂｎ−ｉ ，Ｎｎ−ｉ（ｉ＝１・・・ｎ）とす
る。この場合Ａ，Ｂ，Ｎは多項式とみなすことができ、
Ｒ＝Ａ・ Ｂ ｍｏｄ Ｎは次のように表すことができ
る。 Ｒ＝Ａ・ Ｂ−Ｑ・ Ｎ （Ｑ＝［Ａ・ Ｂ／Ｎ］）
ただし、［Ｚ］はＺを超えない整数を表す。 【００１３】従って、次のような実施例によってＲを求
めることができる。 【００１４】（アルゴリズム１） Ｒ０ ＝０ ＦＯＲ ｊ＝１ ＴＯ ｎ
Ｒｊ ＝Ｒｊ−１・Ｘ＋Ａｎ−ｊ・Ｂ−Ｑｊ−１・
Ｎ ＝Ｒｊ−１・Ｘ＋Ａｎ−ｊ
・Ｂ＋Ｅｊ−１ −Ｌｊ−１・Ｘｎ ＮＥＸＴ ＩＦ Ｒｎ ＞Ｎ ＴＨＥＮ Ｒｎ ＝Ｒｎ −
Ｑｎ・Ｎ ただし、Ｌｊ−１ ＝［Ｒｊ−１ ・
Ｘ／Ｘｎ ］＝［Ｒｊ−１ ／Ｘｎ−１ ］
Ｑｊ−１ ＝［Ｌｊ−１・Ｘｎ ／Ｎ
］，Ｑｎ ＝［Ｒｎ ／Ｎ］
Ｌｊ−１・Ｘｎ＝Ｑｊ−１・Ｎ＋Ｅｊ−１ （
Ｅｊ−１ ＜Ｎ）アルゴリズム１はＲ＞Ｎの判定を行わ
ないためにＮの最大桁であるＸｎ−１ を超えたＲｊ−
１・Ｘの値Ｌｊ−１・Ｘｎに対して、ｍｏｄ Ｎを行う
ようにしている。即ち、ビット的にＸｎ−１を超えたＲ
の係数に対してｍｏｄ Ｎを行っているのでＲ＞Ｎの判
定を必要としない。また、Ｌｊ−１・Ｘｎ ｍｏｄ Ｎ
である−Ｑｊ−１・Ｎを実行する代わりに、Ｌｊ−１・
Ｘｎを引いてその剰余であるＥｊ−１ を加えている。 即ち、Ｌｊ−１ をＥｊ−１に変換して加算している。 これによって、ｍｏｄ Ｎによる減算をすべて加算で行
うことができる。ただしこの場合、最後に１度だけＲｎ
＞Ｎを判定して、Ｒｎ ＝Ｒｎ −Ｑｎ・Ｎの演算を
行う必要があるが、これは上に示した繰り返し演算が終
わった後であり、従来のように繰り返し演算の途中でＲ
＞Ｎの判定を行う必要がないので、別の回路等で行うこ
とができ、全体の処理速度には影響しない。 【００１５】次に、Ｒｊ の演算に伴う遅延時間が大き
いという問題があった。その遅延時間をなくすために、
アルゴリズム１においてＲｊ をＲｊ，ｎ−ｉ 、Ｂを
Ｂｎ−ｉ に分解して次のアルゴリズム２のように表現
する。 （アルゴリズム２） ＦＯＲ ｊ＝１ ＴＯ ｎ ＦＯＲ ｉ＝０ ＴＯ ｎ
Ｒｊ，ｎ−ｉ ＝Ｄｊ−１，ｎ−ｉ−１ ＋Ｃｊ−
１，ｎ−ｉ−２ ＋ｄｗｍ （Ａｎ−ｊ・Ｂｎ−ｉ
） ＋ｕｐｍ（Ａ
ｎ−ｊ・Ｂｎ−ｉ−１ ）＋Ｅｊ−１，ｎ−ｉ
Ｄｊ，ｎ−ｉ ＝ｄｗｍ （Ｒｊ，ｎ−ｉ
） Ｃｊ，ｎ−ｉ ＝ｕｐｍ （Ｒｊ，
ｎ−ｉ ） ＮＥＸＴ ＮＥＸＴ ただし、Ｒｊ−１，ｎ・Ｘｎ ＝Ｑｊ−１・Ｎ＋Ｅｊ−
１ ，Ｑｊ−１ ＝［Ｒｊ−１，ｎ・Ｘｎ／Ｎ］ （１
） Ｅｊ−１ ＝Ｅｊ−１，ｎ−１・Ｘｎ−１ ＋Ｅ
ｊ−１，ｎ−２・Ｘｎ−２ ＋・・・ ＋Ｅｊ−１，１
・Ｘ ＋Ｅｊ−１
，０
（２） Ｄ
０，ｎ−ｉ−１ ＝Ｃ０，ｎ−ｉ−２ ＝Ｅ０，ｎ−ｉ
＝Ｂｎ ＝Ｂ−１＝０ ｄｗｍ （Ｚ
）：Ｚの２ｍ 桁以下の値 ｕｐｍ （
Ｚ）：Ｚの２ｍ＋１ 以上の値を２ｍ＋１ で割った値
を意味する。 【００１６】基本的にアルゴリズム１とアルゴリズム２
は同じであるが、アルゴリズム２の方がより実際の回路
の動作に近い形で表している。ここでｎ＝４の場合を考
え、アルゴリズム２を図１のような回路で乗除算器を構
成する。 【００１７】図１はＡｎ−ｊ・Ｂｎ−ｉ を演算するｍ
＊ｍビットの乗算器ｎ個と、Ｒｊ−１，ｎ の値から（
１）、（２）式によってＥｊ−１，ｎ−ｉ の値を各々
出力するＲＯＭｎ個と、２ビットのキャリーを持つ４入
力ｍビット加算器または５入力加算器ｎ＋１個と、Ｒｊ
，ｎ−ｉ を格納するｍ＋２ビットのレジスタｎ個から
構成される。このレジスタの下位ｍビットはＲｊ，ｎ−
ｉ の下位ｍ桁（ｄｗｍ （Ｒｊ，ｎ−ｉ ）＝Ｄｊ，
ｎ−ｉ ）を意味し、上位２ビットはＲｊ，ｎ−ｉ の
ｍ＋１桁以上の値（ｕｐｍ （Ｒｊ，ｎ−ｉ ）＝Ｃｊ
，ｎ−ｉ ）を意味する。これによって、各加算器毎の
桁上がりはＣｊ，ｎ−ｉ によって各クロック毎に吸収
され、次のクロックで桁上がりとして右隣のレジスタの
下位ｍビットともに加算される。従って、アリゴリズム
（１）のようなＲｊ の演算に伴う遅延時間をなくすこ
とができる。以上のようにＤｊ，ｎ−ｉ ，Ｒｊ，ｎ−
ｉ ，Ｃｊ，ｎ−ｉ はレジスタの状態を表すが、添え
字のｊはクロックを意味し、ｎ−ｉは図１において右か
ら左にｉ＝０からｉ＝ｎとなる回路の位置を示す。 従って、初期状態（ｊ＝０）においてＲ０，０ は図１
の左端のレジスタを意味し、Ｒ０，ｎ−１ ＝Ｒ０，３
は右端のレジスタを意味する。ただし、Ｒ０，ｎ ＝
Ｒ０，４ は右端の加算器からの出力を意味する。 【００１８】次に図１の動作について説明する。 【００１９】図１において各レジスタの初期状態（Ｒ０
，ｎ−ｉ−１ ）はオール０とする。このとき、Ｒ０，
ｎ−ｉ−１ ＝０であるのでＤ０，ｎ−ｉ−１ ＝Ｃ０
，ｎ−ｉ−２ ＝０である。 【００２０】最初のクロック（ｊ＝１）でＡ３ が入力
されるとＡ３・Ｂｎ−ｉ（ｉ＝１・・・４）が各乗算器
から出力される。 その値を上位と下位のｍ桁毎に分けて各加算器で加えて
各々のレジスタ（Ｒ１，ｎ−ｉ：ｉ＝１・・・ｎ ）に
格納する。このとき、Ｒ１，ｎ−ｉ（ｉ＝１・・４）
の下位ｍビットはＤ１，ｎ−ｉ として、桁上がりがあ
ればｍ＋１ビット以上はＣ１，ｎ−ｉ としてレジスタ
に格納されている。 【００２１】次のクロック（ｊ＝２）でＡ２ が入力さ
れるとＡ２・Ｂｎ−ｉ（ｉ＝１・・・４）が同様に上の
乗算器から上位と下位ｍビット毎に出力される。このと
きＲ１，４ ＝ｕｐｍ （Ａ３・Ｂ３ ）が右端のレジ
スタから加算器を通して出力されるので、それを受けて
各ＲＯＭからＥ１，ｎ−ｉ の値が各加算器に出力され
る。そのとき、その加算器の左隣にあるレジスタの下位
ｍビットＤｊ−１，ｎ−ｉ−１（ｉ＝２・・・４）も加
算器に入力されるが、２つ左隣のレジスタの上位２ビッ
トＣｊ−１，ｎ−ｉ−２ は桁上がりキャリーとして同
じ加算器に入力される。従って、加算器は２ビットのキ
ャリーを持つ４入力ｍビット加算器または５入力加算器
として構成され、ｍ＋２ビットの出力を返す。従って、
レジスタはｍ＋２ビットのレジスタで構成される。 【００２２】更に次のクロック（ｊ＝３）でＡ１ が入
力されると同様にＡ１・Ｂｎ−ｉ（ｉ＝１・・・４）が
上の乗算器から上位と下位ｍビット毎に出力される。こ
のときＲ２，４ ＝ｕｐｍ（Ａ２・Ｂ３ ）＋ｄｗｍ
（Ａ３・Ｂ３ ）＋Ｅ１，３ が右端のレジスタから加
算器を通して出力される。以下同様に、それを受けて各
ＲＯＭからＥ２，ｎ−ｉ の値が各加算器に出力され、
その加算器の左隣にあるレジスタの下位ｍビットと、２
つ左隣のレジスタの上位２ビットが同じ加算器に入力さ
れる。 【００２３】更に、ｊ＝４のクロックでＡ０ が入力さ
れたときも同様の動作を行い、その結果、各レジスタに
格納された値がＲｎ となっていることが判る。 【００２４】（実施例２）実施例１のアルゴリズム２は
乗算器からの出力をｄｗｍ （Ａｎ−ｊ・Ｂｎ−ｉ ）
とｕｐｍ（Ａｎ−ｊ・Ｂｎ−ｉ−１ ）の２つの出力に
分解しているが、Ｂを定数として扱える場合、図２及び
アルゴリズム３に示すようにＡｎ−ｊ の入力を受けて
、Ａｎ−ｊ・Ｂの値をいくつかのＲＯＭに分割してＡＢ
ｊ，ｎ−ｉ として出力することもできる。 （アルゴリズム３） ＦＯＲ ｊ＝１ ＴＯ ｎ ＦＯＲ ｉ＝０ ＴＯ ｎ
Ｒｊ，ｎ−ｉ ＝Ｄｊ−１，ｎ−ｉ−１ ＋Ｃｊ−
１，ｎ−ｉ−２ ＋ＡＢｊ，ｎ−ｉ ＋Ｅｊ−１，ｎ−
ｉ Ｄｊ，ｎ−ｉ ＝ｄｗｍ （Ｒｊ
，ｎ−ｉ ） Ｃｊ，ｎ−ｉ ＝ｕｐｍ
（Ｒｊ，ｎ−ｉ ） ＮＥＸＴ ＮＥＸＴ ただし、Ａｎ−ｊ・Ｂ＝ＡＢｊ−１，ｎ・Ｘｎ ＋ＡＢ
ｊ−１，ｎ−１・Ｘｎ−１ ＋・・・ ＋ＡＢｊ−１，
０ 【００２５】（実施例３）次に、ＲＯＭなどによる複数
ビット同士の乗算を行わず、アンド回路と加算器だけで
剰余乗算を実現させる例を説明する。 （アルゴリズム４） 【００２６】 【数１】 この装置の構成例を図４に示す。この例では、Ａｎ−ｊ
＝（ａｊ・ｍ＋ｍ−１ ，・・・ ａｊ・ｍ＋１ ，
ａｊ・ｍ ）を１ビット毎独立にｍビット同時に入力さ
せて、ａｊ・ｍ−ｋ・Ｂ（ｋ＝０・・・ｍ−１） を独
立にアンド回路３８（１） 〜３８（ｍ） によって出
力する。このとき、ａｊ・ｍ−ｋ・Ｂは、ａｊ・ｍ−ｋ
が０のとき０、１のときＢである。この出力と、左隣
のレジスタの下位ビットと、その更に左にあるレジスタ
の上位ビットと、ＲＯＭからの出力とをｍ＋３入力の加
算器によって加算していくことによって、剰余乗算が実
現できる。この時の各レジスタ４４〜４７の大きさはｍ
ビットの値のｍ＋３項の和であるから、ｍ＋ｌｏｇ２（
ｍ＋３） 以上あればよい。 【００２７】また、図１〜３において、Ｒｊ，ｎ の値
を１度レジスタにラッチさせるようにしてもよい。この
場合、Ｒｊ，ｎ の値を１度レジスタにラッチするため
に処理に必要な１クロックの最大時間は、乗算または除
算に要する時間だけでよく、アルゴリズム２〜４の演算
を短時間毎に繰り返すことができる。対応する回路構成
を図４〜６に示す。 【００２８】また、アルゴリズム１の代わりに、以下の
アルゴリズムを用いることもできる。 （アルゴリズム５） Ｒ０ ＝０ ＦＯＲ ｊ＝１ ＴＯ ｎ
Ｒｊ ＝Ｒｊ−１・Ｘ＋Ａｎ−ｊ・Ｂ−Ｑｊ−１・
Ｎ・ Ｘ ＝Ｒｊ−１・Ｘ＋Ａ
ｎ−ｊ・Ｂ＋（Ｅｊ−１ −Ｌｊ−１・Ｘｎ ）・ Ｘ
ＮＥＸＴ ＩＦ Ｒｎ ＞Ｎ ＴＨＥＮ Ｒｎ ＝Ｒｎ −
Ｑｎ・Ｎ ただし、Ｌｊ−１ ＝［Ｒｊ−１ ／
Ｘｎ ］ Ｑｊ−１ ＝［Ｌｊ
−１・Ｘｎ＋１／Ｎ］，Ｑｎ ＝［Ｒｎ ／Ｎ］
Ｌｊ−１・Ｘｎ＋１ ＝（Ｑｊ−１
・Ｎ＋Ｅｊ−１ ）・ Ｘ （Ｅｊ−１ ＜Ｎ）
ここで、Ｘは乗算器からの出力Ａｎ−ｊ・Ｂに対して剰
余Ｅｊ−１ の出力をずらすために必要であり、これに
よって図４〜５における左端のレジスタへの入力値演算
のための加算器をなくすことができる。図７〜９に、上
記アルゴリズムに対応する回路構成を示す。 【００２９】また、図７〜図９の各回路の右端に更にレ
ジスタをｃ個追加すれば、−Ｑｊ−１・Ｎ・ Ｘｃ ＝
（−Ｌｊ−１・Ｘｎ＋１ ＋Ｅｊ−１ ）・ Ｘｃ と
なるので、任意に剰余出力Ｅｊ−１ をずらすことも可
能である。 【００３０】以上によって入力値がｍビット毎にｎ分割
されて入力されるときｎ・ ｍビットの乗除算回路が効
率的に実現できることが示せた。これは、ｎａ ≠ｎ，
ｎｂ ≠ｎ，ｎｎ ≠ｎの場合にも同様の回路構成で乗
除算回路が実現できることは明かである。 【００３１】以上述べた実施例の回路では、Ｃｊ，ｎ−
ｉ によって桁上がりを一旦ホールドするために桁上が
りに関する遅延時間はなく、アルゴリズム２〜４の演算
を短時間毎に繰り返すことができる。 【００３２】また、Ｎの最大桁であるＸｎ−１ を超え
たＲｊ−１の値Ｌｊ−１・Ｘｎ に対して、ｍｏｄＮを
行うようにしているのでＲ＞Ｎの判定を行わなくてよい
。また、−Ｑｊ−１・Ｎを実行する代わりに、−Ｑｊ−
１・Ｎ＝−Ｌｊ−１・Ｘｎ ＋Ｅｊ−１ であるＥｊ−
１ を加えることによって剰余演算を全て加算によって
行っている。 【００３３】また、乗算を小さな桁毎に分解して実行し
たり（アルゴリズム２）、Ｂが定数の場合ＲＯＭによっ
て構成したり（アルゴリズム３）、乗算器を用いずアン
ドと加算器のみで乗算を実行したり（アルゴリズム４）
することによって大きな桁の乗算を行う乗算器を用いる
ことなく乗算が実行できる。従って、ＴＴＬやセルライ
ブラリなどによって小さな桁の乗算器が簡単に用いるこ
とができる場合にはアルゴルズム２、Ｂを定数として扱
える場合にはアルゴリズム３、ＲＯＭやセルライブラリ
の乗算器等がない場合はアルゴリズム４に対応する乗除
算回路が適している。 【００３４】また、図１〜９のような同一の演算素子の
繰り返しによる構成はＶＬＳＩ等の大規模回路を構成し
やすいという利点もある。 【００３５】（実施例５）次に、上述の演算装置を用い
た暗号化通信の方法を説明する。通信しようとする平文
をＭ，暗号文をＣ，公開暗号鍵をｅ，復号鍵をｄ，公開
された法をＮとすると、ＲＳＡ暗号の暗号化と復号は次
のようなべき乗剰余演算で表される。 【００３６】暗号化：Ｃ＝Ｍｅ ｍｏｄ Ｎ復号：Ｍ＝
Ｃｄ ｍｏｄ Ｎ 従って、ＲＳＡ暗号の暗号化と復号化は同様なべき乗剰
余演算回路によって実現できる。そこで、以下では暗号
化についてのみ説明する。 【００３７】べき乗剰余演算：Ｃ＝Ｍｅ ｍｏｄ Ｎは
、単純に２数の剰余乗算を行っても実現できるが、Ｍ、
ｅが大きいと、その計算量は莫大なものとなる。そのた
め、本発明では、以下のアルゴリズムに従って計算を実
行する。ただし、ｅはｋビットからなる整数であり、ｅ
＝ｅｋ，ｅｋ−１，・・・，ｅ２，ｅ１ で表されると
する。 【００３８】 ＩＮＰＵＴ Ｍ，ｅ，Ｎ
（入力） Ｃ＝
１
（初期設定） ＦＯＲ
ｉ＝ｋ ＴＯ １ ＩＦ ｅｉ＝１ ＴＨＥＮ Ｃ＝Ｃ
・ Ｍ ｍｏｄ Ｎ （演算１）
ＩＦ ｉ ＞１ ＴＨＥＮ Ｃ＝Ｃ・ Ｃ
ｍｏｄ Ｎ （演算２） ＮＥＸＴ 従って、この場合、べき乗剰余演算は、Ｃ＝Ｃ・
Ｂ ｍｏｄ Ｎ（ＢはＭまたはＣ）の剰余乗算の繰り返
しによって実現される。この剰余乗算は図１のごとき回
路によって実現できる。このアルゴリズムを効率的に実
行する回路を図２に示す。１０１、１０２は各々Ｍ，ｅ
，の値を格納するシフトレジスタであり、１０３、１０
４は各々Ｎ，Ｃの値を格納するレジスタである。また、
１０５，１０６は入力を選択するセレクタスイッチ、１
０７はレジスタ１０４のＣの値をｍビット毎（ｍは任意
の整数）に上位桁から選択しシリアルに出力するマルチ
プレクサ、１０８はＣ＝Ｃ・ Ｂ ｍｏｄ Ｎの演算を
実行する剰余乗算回路である。１０９はｅｉ＝１または
ｉ ＞１を判定して演算１，２の実行を制御したり、入
力及び初期設定時にセレクタやレジスタのクリア信号や
プリセット信号などを制御するコントローラであり、カ
ウンタとＲＯＭといくつかの論理回路によって簡単に実
現できる。 【００３９】次に、この回路の動作について説明する。 【００４０】入力は平文Ｍと公開された鍵ｅとＮである
。そこでレジスタ１０１〜１０３に、Ｍ，ｅ，Ｎをシリ
アルまたはパラレルに入力する。このとき、セレクタ１
０５はＭを選択することでＭをレジスタ１０１に入力す
る。それと同時に、レジスタ１０４にはＣの値を入力す
る代わりに、レジスタのクリア信号またはプリセット信
号によってＣ＝１となるように初期設定する。 【００４１】入力及び初期設定が終了すると、演算１，
２に示した剰余乗算が開始される。ここで、演算１，２
の違いは剰余乗算Ｃ＝Ｃ・ Ｂ ｍｏｄ Ｎにおいて、
ＢがＭかＣかの違いである。従って、演算１を実行する
ときは、セレクタ１０６はレジスタ１０１からのｍビッ
ト毎のシリアル出力Ｍを選択し、演算２を実行するとき
はマルチプレクサ１０７からのｍビット毎のシリアル出
力であるＣを選択するように制御される。また、シフト
レジスタ１０１からのｍビット毎のシリアル出力Ｍはセ
レクタ１０５を介して、再びシフトレジスタ１０１に入
力される。剰余乗算回路１０８の構成及び動作は前述の
通りである。剰余乗算回路１０８の出力するＣをレジス
タ１０４にパラレル入力し、次の剰余乗算に用いること
によって演算１，２が効率的に繰り返される。 【００４２】また、この装置で、Ｍ、ｅの代わりに、Ｃ
、ｄを入力することにより、暗号文の複号を行うことが
できる。 【００４３】 【発明の効果】以上説明したごとく、本発明の演算装置
によれば、小さな回路規模で、高速な剰余乗算が実行で
きるという効果がある。 【００４４】また、本発明演算装置は同一の演算素子の
繰り返しにより構成されるので、ＶＬＳＩ等による回路
化を実現しやすいという効果もある。 【００４５】また、本発明によれば、暗号化通信のため
の暗号化／複号装置を小さな回路規模で実現できるとい
う効果がある。
【図１】本発明演算装置の回路構成例を示す図である。
【図２】本発明演算装置の回路構成例を示す図である。
【図３】本発明演算装置の回路構成例を示す図である。
【図４】本発明演算装置の回路構成例を示す図である。
【図５】本発明演算装置の回路構成例を示す図である。
【図６】本発明演算装置の回路構成例を示す図である。
【図７】本発明演算装置の回路構成例を示す図である。
【図８】本発明演算装置の回路構成例を示す図である。
【図９】本発明演算装置の回路構成例を示す図である。
【図１０】暗号化・複号装置の構成例を示す図である。
１１〜１４ 乗算器
１５〜１８ ＲＯＭ
１９〜２３ 加算器
２４〜２７ レジスタ
２８〜３２ ＲＯＭ
３３〜３７ 加算器
３８（１） 〜３８（ｍ） アンド回路３９〜４３
加算器 ４４〜５０ レジスタ １０１，１０２ シフトレジスタ １０３，１０４ レジスタ １０５〜１０６ セレクタ １０７ マルチプレクサ １０８ 剰余乗算回路
加算器 ４４〜５０ レジスタ １０１，１０２ シフトレジスタ １０３，１０４ レジスタ １０５〜１０６ セレクタ １０７ マルチプレクサ １０８ 剰余乗算回路
Claims (7)
- 【請求項１】 与えられた第１、第２の整数の積を第
３の整数で除算した剰余を演算する演算装置であって、
値を保持する記憶手段と、前記第１の整数を所定のビッ
トずつ順次入力して前記第２の整数に乗じる乗算手段と
、前記記憶手段からの入力と、前記乗算手段からの入力
とを加算し、前記記憶手段の値において前記第３の整数
の最大桁を越える部分につき、前記第３の整数に対する
剰余を求める演算を施し、その結果を前記記憶手段に出
力する演算手段とを有することを特徴とする演算装置。 - 【請求項２】 前記演算手段において、前記剰余を求
める演算を施すために、前記記憶手段の値において前記
第３の整数の最大桁を越える部分につき、当該部分に代
わり、前記剰余を加えることを特徴とする請求項１記載
の演算装置。 - 【請求項３】 前記記憶手段は複数個のレジスタを有
し、前記演算手段は、それぞれが所定の桁部分同士を加
算する複数個の加算器を含み、当該レジスタは、保持し
ている値の上位桁部分と下位桁部分とを異なる加算器に
出力することを特徴とする請求項１記載の演算装置。 - 【請求項４】 前記乗算手段は、前記所定のビット数
同士の乗算を行なう複数の乗算器を含み、当該各乗算器
は、乗算結果の上位桁部分と下位桁部分とを異なる加算
器に出力することを特徴とする請求項３記載の演算装置
。 - 【請求項５】 前記乗算手段は、前記所定のビット数
ずつ入力された第１の整数の各ビットと第２の整数との
積を出力する論理回路を有することを特徴とする請求項
１記載の演算装置。 - 【請求項６】送信すべき情報Ｍに対して、与えられた整
数ｅ、Ｎから暗号Ｃ＝Ｍｅ ｍｏｄ Ｎを求めて、暗号
Ｃを送信する暗号化通信方法において、暗号化装置に、
与えられた第１、第２の整数の積を第３の整数で除算し
た剰余を演算する演算装置であって、値を保持する記憶
手段と、前記第１の整数を所定のビットずつ順次入力し
て前記第２の整数に乗じる乗算手段と、前記記憶手段か
らの入力と、前記乗算手段からの入力とを加算し、前記
記憶手段の値において前記第３の整数の最大桁を越える
部分につき、前記第３の整数に対する剰余を求める演算
を施し、その結果を前記記憶手段に出力する演算手段と
を有する演算装置を設けたことを特徴とする暗号化通信
方法。 - 【請求項７】受信した暗号Ｃに対して、与えられた整数
ｄ、Ｎから情報Ｍ＝Ｃｄ ｍｏｄ Ｎを求めて、暗号Ｃ
を情報Ｍに複号する暗号化通信方法において、複号装置
に、与えられた第１、第２の整数の積を第３の整数で除
算した剰余を演算する演算装置であって、値を保持する
記憶手段と、前記第１の整数を所定のビットずつ順次入
力して前記第２の整数に乗じる乗算手段と、前記記憶手
段からの入力と、前記乗算手段からの入力とを加算し、
前記記憶手段の値において前記第３の整数の最大桁を越
える部分につき、前記第３の整数に対する剰余を求める
演算を施し、その結果を前記記憶手段に出力する演算手
段とを有する演算装置を設けたことを特徴とする暗号化
通信方法。
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3040115A JPH04277789A (ja) | 1991-03-06 | 1991-03-06 | 演算装置及びこれを用いた暗号化通信方法 |
| AT92301856T ATE193606T1 (de) | 1991-03-05 | 1992-03-04 | Rechengerät und verfahren zum verschlüsseln/entschlüsseln von kommunikationsdaten unter verwendung desselben |
| DE69231110T DE69231110T2 (de) | 1991-03-05 | 1992-03-04 | Rechengerät und Verfahren zum Verschlüsseln/Entschlüsseln von Kommunikationsdaten unter Verwendung desselben |
| EP92301856A EP0502712B1 (en) | 1991-03-05 | 1992-03-04 | Calculating apparatus and method of encrypting/decrypting communication data by using the same |
| US07/847,672 US5313530A (en) | 1991-03-05 | 1992-03-04 | Calculating apparatus and method of encrypting/decrypting communication data by using the same |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3040115A JPH04277789A (ja) | 1991-03-06 | 1991-03-06 | 演算装置及びこれを用いた暗号化通信方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04277789A true JPH04277789A (ja) | 1992-10-02 |
Family
ID=12571846
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3040115A Pending JPH04277789A (ja) | 1991-03-05 | 1991-03-06 | 演算装置及びこれを用いた暗号化通信方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04277789A (ja) |
-
1991
- 1991-03-06 JP JP3040115A patent/JPH04277789A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR100267009B1 (ko) | 고속 암호화 처리를 위한 어레이 구조를 가지는 모듈러 곱셈장치 | |
| US5764554A (en) | Method for the implementation of modular reduction according to the Montgomery method | |
| Okada et al. | Implementation of elliptic curve cryptographic coprocessor over GF (2m) on an FPGA | |
| EP0801345B1 (en) | Circuit for modulo multiplication and exponentiation arithmetic | |
| US5313530A (en) | Calculating apparatus and method of encrypting/decrypting communication data by using the same | |
| US5121429A (en) | Digital signal processing | |
| US6061706A (en) | Systolic linear-array modular multiplier with pipeline processing elements | |
| KR100442218B1 (ko) | 몽고메리의 알고리즘을 이용한 멱승 잉여 연산기 | |
| JP3532860B2 (ja) | 剰余系表現を利用した演算装置及び方法及びプログラム | |
| JP3302043B2 (ja) | 暗号通信方法及びそのシステム | |
| JP2004258141A (ja) | モンゴメリ乗算剰余の多倍長演算のための演算装置 | |
| JP3406914B2 (ja) | 演算装置及びこれを備えた暗号化装置、復号装置 | |
| EP1504335A2 (en) | Fast multiplication circuits | |
| US5999953A (en) | Method for the production of a parameter Jo associated with the implementation of a modular operation according to the Montgomery method | |
| JP3323516B2 (ja) | 演算装置及びこれを備えた暗号化装置、復号装置 | |
| JP3210420B2 (ja) | 整数上の乗算回路 | |
| US7403965B2 (en) | Encryption/decryption system for calculating effective lower bits of a parameter for Montgomery modular multiplication | |
| US20060161610A1 (en) | Device and method for generating a sequence of numbers | |
| JP3129525B2 (ja) | 整数上の乗算回路 | |
| JPH0916379A (ja) | 通信方法とその装置 | |
| US6275837B1 (en) | Method for the implementation of an elementary modular operation according to the Montgomery method | |
| US20040081317A1 (en) | Encryption circuit achieving higher operation speed | |
| KR100858559B1 (ko) | 잉여 이진수의 덧셈 방법, 잉여 이진수의 곱셈 방법, 잉여이진수 덧셈기 및 잉여 이진수 곱셈기 | |
| JP3129526B2 (ja) | 整数上の乗算回路 | |
| Ku et al. | Design of new AB 2 multiplier over GF (2 m) using cellular automata |