JPH08254949A - Ｒｓａ暗号方式の暗号化器及び復号器に使用する高速ベキ乗剰余演算法 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 ＲＳＡ暗号方式の暗号化装置による平文の暗
号化と復号装置による暗号文の復号化を従来法と同様の
安全性を確保して高速処理可能ならしめる。 【構成】 下記（迅速計算方式）で示されるＲＳＡ暗号
方式の暗号化装置内のＭ^e ｍｏｄＲ^x −ｙ及び復合装置
内のＣ^d ｍｏｄＲ^x −ｙの演算を実行する際に、通常の
指数演算法を使用して、該演算法の第ｉステツプのＣ_i ²
ｍｏｄＲ^x −ｙのベキ乗剰余演算をｙにｙ＜Ｒ^x/2 の制
限を加えることによつて従来の除数の桁数に比例した処
理時間を要する除算を使用することなく、Ｃ_i ²≡Ｃ_i ⁽²⁾
・ｙ＋Ｃ_i ⁽¹⁾なる演算式で示される演算を２回繰り返し
実行することによつて上記のベキ乗剰余演算を高速処理
する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ＲＳＡ暗号方式を用い
た暗号化装置及び復号装置の各装置内のベキ乗剰余演算
部の処理を高速にする方法に関するものである。

【０００２】

【従来の技術】情報通信技術の発展に伴い通信路（伝送
路、メモリ等）を使用したデ−タ通信の秘密保護として
暗号化技術は情報分野にとどまらす電子送金、シヨツビ
ング、レジヤ−等の様々な分野に使用されるようになつ
た。この様なネツトワ−ク型社会にふさわしい暗号化方
式として従来より、公開鍵暗号方式が存在する。この公
開鍵暗号方式は各人（或いは各端末）が暗号化鍵と復号
化鍵とを一つづつ作成し暗号化鍵を公開し復号化鍵を秘
密に保持する方式であり、例えばＡという人宛に暗号文
を送信したい人は誰でもＡが公開した暗号化鍵を使用し
て、Ｍ^e ｍｏｄｎなる演算を実行し、平文Ｍを暗号文Ｃ
に変換する。従つて鍵配送の必要がないため利点が大き
い。公開鍵暗号方式の中でもＲＳＡ暗号方式は1978年Ｒ
ＩＶＥＳＴ，ＳＨＡＭＩＲ，ＡＤＬＥＭＡＮの３人によ
つて発明されて多大な注目を集め実用化されるに至つ
た。

【０００３】

【発明が解決しようとする課題】ＲＳＡ暗号方式は多大
の注目を集め実用化されているものの、この暗号方式は
暗号化装置による平文の暗号化、復号装置による暗号文
の復号を実行処理する際、各装置内でベキ乗演算及び剰
余演算を繰り返し使用するため暗号化及び復号に膨大な
計算時間が必要になるという解決すべき課題がある。本
発明は、法ｎを特別な形に設定することで公開鍵ｎの制
約条件が大きな２つの素数の積であるという条件のみを
有する従来方式と同様な安全性を確保して、なおかつ高
速処理可能なＲＳＡ暗号方式を提供することを目的とす
るものである。この場合における平文の暗号化通信の手
順は従来のＲＳＡ暗号方式と同じである。

【０００４】

【課題を解決するための手段】本発明の第１は〔図１〕
で示されるＲＳＡ暗号方式の暗号化装置内のＭ^e ｍｏｄ
Ｒ^x −ｙ及び復号装置内のＣ^d ｍｏｄＲ^x −ｙなる演算
を実行する際に、通常の指数演算法を使用して、該演算
法の第ｉステツプＣ_i ²ｍｏｄＲ^x −ｙのベキ乗 剰余演算をｙにｙ＜Ｒ² の制限を加えることによつて従
来の除数の桁数に比例した処理時間を要する除算を使用
することなく、Ｃ_i ²≡Ｃ_i ⁽²⁾．ｙ＋Ｃ_i ⁽¹⁾なる演算式を
を２回繰り返し実行することによつて上記ベキ乗剰余演
算を高速処理するＲＳＡ暗号方式の暗号化器及び複合器
に使用される高速ベキ乗剰余演算法を（手法Ａという）
である。

【０００５】

【図１】

【０００６】更に手法Ａについて詳細説明すれば、一般
に合成数ｎはＲ^x −ｙの形で表される。ここで、このｙ
の桁数に適切な制限を加えれば、法演算が除算を用いず
に乗算と加算で置き換えることが可能であり、通常の除
算で必要な除数の桁数に比例したステツプ数の削減が可
能になる。指数乗算法によりＭのベキ乗を求める場合の
第ｉステツプにおける値をＣ_i とする。第ｉステツプに
おいてｎを法とした自乗の演算を遂行する際、第ｉ＋１
ステツプにおける中間値Ｃ_i+1 は Ｃ_i ²ｍｏｄｎ─→Ｃ_i+1 (1) として求められる。ここで （ｘ，ｙは正の整数） とし、Ｃ_i ²のＲ^x 以上の部分をＣ_i ⁽²⁾、Ｒ^x 未満の部分
をＣ_i ⁽¹⁾とする。即ち、 Ｃ_i ² ＝ Ｃ_i ⁽²⁾・Ｒ^x ＋ Ｃ_i ⁽¹⁾ (3) とする。このようにすると明らかに Ｃ_i ² ≡ Ｃ_i ⁽²⁾・ｙ＋Ｃ_i ⁽¹⁾ｍｏｄｎ (4) の関係が成立する。

【０００７】 式(4) の右辺の形はｎより大であり、且つＲ^{x+2 +1}より
小である。従つてこれをあらためて Ｃ_i ⁽⁴⁾・Ｒ^x ＋ Ｃ_i ⁽³⁾ (5) とおくと、 Ｃ_i ² ≡ Ｃ_i ⁽⁴⁾・ｙ＋Ｃ_i ⁽³⁾ｍｏｄｎ (6) となる。以上により、ｎによる除算はｎが式(2) を満足
する限り２ステツプの乗算、加算により式(1) が遂行さ
れることが判る。ただし、ここでは乗算は並列処理によ
り高速化を行うものとする。

【０００８】本発明の第２は〔図１〕で示されるＲＳＡ
暗号方式の暗号化装置内のＭ^e ｍｏｄＲ^x −ｙ及び複合
装置内のｃ^d ｍｏｄＲ^x −ｙなる演算を実行する際、通
常の指数演算法を使用して、該演算法の第ｉステツプの
Ｃ_i ²ｍｏｄＲ^x −ｙなるベキ に制限をし、従来の除数の桁数に比例した処理時間を要
する除算を使用することなく、Ｃ_i ²＝Ｃ_i ⁽³⁾・ｙ² ＋Ｃ
_i ²・ｙ＋Ｃ_i ⁽¹⁾なる形の演算式を１回実行することで上
記ベキ乗剰余演算を高速処理する暗号方式の暗号化器及
び複合器に使用する高速ベキ乗剰余演算法（手法Ｂとい
う）である。

【０００９】

【図１】

【００１０】ここに、Ｃ_i ³はＣ_i ²のＲ^2x以上の部分をＲ
^2xで割つた値である。更に手法Ｂについて詳細説明すれ
ば、一般に合成数ｎはＲ^x −ｙの形で表される。ここ
で、このｙの桁数に適切な制限を加えれば、法演算が除
算を用いずに乗算と加算で置き換えることが可能であ
り、通常の除算で必要な除数の桁数に比例したステツプ
数の削減が可能になる。指数乗算法によりＭのベキ乗を
求める場合の第ｉステツプにおける値をＣ_i とする。第
ｉステツプにおいてｎを法とした自乗の演算を遂行する
際、第ｉ＋１ステツプにおける中間値Ｃ_i+1 はＣ_i ²ｍｏ
ｄｎ→Ｃ_i+1 として求まる。

【００１１】ここで、Ｃ_i ²のＲ^x 以上の部分をＣ_i ⁽²⁾，
Ｒ^x 未満の部分をＣ_i ⁽¹⁾とすると、 Ｃ_i ² ＝ Ｃ_i ⁽²⁾・Ｒ^x ＋ Ｃ_i ⁽¹⁾ ≡ Ｃ_i ⁽²⁾・ｙ ＋ Ｃ_i ⁽¹⁾ (7) となる。ここで乗算は並列処理により高速化を行うもの
とする。次にＣ² _i+1のＲ^2x以上の部分をＣ_i+1 ⁽³⁾、Ｒ^2x
未満Ｒ^x 以上の部分をＣ_i+1 ⁽²⁾、Ｒ^x 未満の部分をＣ
_i+1 ⁽¹⁾とすると、 Ｃ_i+1 ²＝Ｃ_i+1 ⁽³⁾・Ｒ^2x＋Ｃ_i+1 ⁽²⁾・Ｒ^x ＋Ｃ_i+1 ⁽¹⁾ ≡Ｃ_i+1 ⁽³⁾・ｙ² ＋Ｃ_i+1 ⁽²⁾・ｙ ＋Ｃ_i+1 ⁽¹⁾ (8) となる。そして高速化を計るために、式(8) の右辺がｎ
桁以上の場合でもＣ_i ²と同様、これをそのまま次のＣ
_i+2 ²の計算ステツプで用いる。通常、…→Ｃ_i ²→Ｃ_i+1 ²
→Ｃ_i+2 ²→…のステツプにおいて桁数は自乗計算を実行
するたびに増加するがＣ_i+1 ⁽³⁾・ｙ² の桁数がＣ_i+1 ⁽²⁾
・ｙの桁数を越えないようにｙの桁数Ｙに制限を加えれ
ば、最終のステツプでの桁数をある値以下に制限するこ
とが可能になる。以下において、このことを検討しよ
う。

【００１２】ここで、 Ａ ： ｎ の桁数 Ｂ ： Ｃ_i+1 ⁽²⁾・ｙ の桁数 Ｃ ： Ｃ_i+1 ⁽³⁾・ｙ² の桁数 Ｄ ： Ｃ_i+1 ⁽³⁾ の桁数 Ｙ ： ｙ の桁数 とすると、 Ｂ ＝ Ｙ＋Ａ (9) Ｄ ＝ ２・（Ｂ＋１）−２・Ａ (10) Ｃ ＝ Ｄ＋２・Ｙ (11) である。なる条件より Ｙ＋Ａ≧２・（Ｙ＋Ａ＋１）−２・Ａ＋２・Ｙ (13) である。従つて として、最終ステツプの桁数をＢ＋１以下に制限し得る
ｙの桁数の制限範囲が求まる。なお、安全性の立場から
ｙの値は式(14)を満たす範囲でできる限り大であること
が望ましい。

【００１３】ここで、以下のことを付記する。 (イ) 数ステツプに１回程度の法演算を許容すれば、式(1
4)のｙの桁に関する制約条件を更に大きくすることが可
能であること。 (ロ) 高速演算に適した形をＲ^x −ｙとしたが、Ｒ^x ＋ｙ
の形にしても同様の高速演算が可能であること。 (ハ) ＲＳＡ暗号方式の暗号化器及び復号器以外のベキ乗
剰余演算を使用するものにも有効である。

【００１４】

【作用】上記の発明が解決すべき手段によるＲＳＡ暗号
方式を用いたデ−タ暗号通信は、平文Ｍの暗号化及び暗
号文Ｃの復号に使用する法演算が除算を用いずに乗算器
と加算器で置き換えることが可能であり、そのために通
常の除算で必要な除数の桁数に比例した演算ステツプ数
の削減が可能になつた。また、本発明方法の法ｎを使用
すれば、公開鍵をいわゆる“電話帳”に１０進表現で掲
載することを例に取れば公開鍵ｎの制約条件が大きな２
つの素数の積であるという条件のみを有する従来の方式
では法ｎを全桁数数字掲載する必要があり非常に長いも
のになるのに対し、共通鍵の掲載は、連続する９以外の
ランダムな数字の部分のみ掲載すればよいことになると
いう利点がある。

【００１５】

【表１】

【００１６】

【表２】

【００１７】次に本発明を実施例によつて説明する。

【実施例１】ＲＳＡ暗号方式において〔図１〕の平文Ｍ
の暗号化を実行する式は、 Ｍ^e ≡ Ｃｍｏｄｎ (15) であり暗号文Ｃの復号を実行する式は、 Ｃ^d ≡ Ｍｍｏｄｎ (16) である。但し、Ｍ ： メツセ−ジ Ｃ ： 暗号文 ｅ ： 公開鍵 ｄ ： 秘密鍵 ｎ ： ｐ・ｑ

【００１８】

【図１】 また一般にＲＳＡ暗号方式では２＜ｅ＜＜ｄと選ばれる
ことが多いが、本発明の高速ベキ乗剰余演算法ではｅ及
びｄには上記のような制約はない。本発明方式による暗
号通信システムの構成原理図を〔図１〕に示す。ここで
用いられる上記式(15)及び式(16)を実行する際、一般的
に指数演算法が用いられる〔図２〕。即ち、この演算法
の第ｉステツプに手法Ａを用いる。これをハ−ドウエア
構成とした場合のブロツク図を〔図３〕に示す。この
〔図３〕の回路は計算で取り扱うパラメ−タＭ、ｅ、ｙ
を記憶するためのレジスタと、Ｒ進乗算器Ｉ、II、III
と、Ｒ進加算器で構成されている。乗算器III に依存す
べき前段の処理として乗算器Ｉ，IIの結果のみである。
即ち、直列処理を必要とする部分はこの３つの部分のみ
である。よつて、指数演算法の１ステツプにあたるａ・
ｂｍｏｄｎなる計算は、この３つの直列処理部分に要す
るクロツク数で計算可能になる。

【００１９】

【実施例２】ＲＳＡ暗号方式において〔図１〕の平文Ｍ
の暗号化を実行する式は、 Ｍ^e ＝ Ｃｍｏｄｎ (15) であり暗号文Ｃの復号を実行する式は、 Ｃ^d ≡ Ｍｍｏｄｎ (16) である。但し、 Ｍ ： メツセ−ジ Ｃ ： 暗号文 ｅ ： 公開鍵 ｄ ： 秘密鍵 ｎ ： ｐ・ｑ ｐ，ｑ ： 大きな素数（秘密）

【００２０】

【図１】 また一般にＲＳＡ暗号では２＜ｅ＜＜ｄと選ばれること
が多いが、本発明の高速ベキ乗剰余演算法ではｅ及びｄ
にはこのような制約はない。本発明方式による暗号通信
システムの構成原理図を〔図１〕に示す。ここで用いら
れる上記式(15)及び式(16)を実行する際、一般的に指数
演算法が用いられる〔図２〕。即ち、この演算法の第ｉ
ステツプにし手法Ｂを用いる。これをハ−ドウエア構成
した場合のブロツク図を〔図４〕に示す。この〔図４〕
の回路は計算で取り扱うパラメ−タＭ、ｅ、ｙ、ｙ² を
記憶するためのレジスタと、Ｒ進乗算器Ｉ、II、III
と、Ｒ進加算器で構成されている。この回路の乗算器I
I、III は並列計算可能であり、乗算器II、III に依存
すべき前段の処理として乗算器Ｉの結果のみである。即
ち、直列処理を必要とする部分はこの２つの部分のみで
ある。よつて、指数演算法の１ステツプにあたるａ・ｂ
ｍｏｄｎなる計算は、この２つの直列処理部分に要する
クロツク数で計算可能になる。

【００２１】

【発明の効果】本発明の効果を纏めると次の通りであ
る。 (1) 本発明によつてＲＳＡ暗号方式を使用した暗号通信
における平文の暗号化と復号にかかる時間の著しい短縮
が従来のＲＳＡ暗号方式と同程度の安全性を確保したう
え可能となつた。即ち、多大の計算ステツプを必要とす
るベキ乗剰余演算を１ステツプで処理することが可能に
なつた。 (2) 本発明の法ｎを使用することによつて公開鍵の管理
用メモリ（いわゆる電話帳）の節約が可能となつた。あ
わせて公開鍵を暗号化装置又は、復号装置に手入力する
ことも可能である。

【図面の簡単な説明】

【図１】迅速計算システム示す構成原理図。

【図２】指数乗算法のアルゴリズムのフロ−チヤ−ト。

【図３】図２に従つてハ−ドウエア構成を取らしめた場
合の自乗剰余回路を示す一実施例。

【図４】図２に従つてハ−ドウエア構成を取らしめた場
合の自乗剰余回路を示す他の一実施例。

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成８年１月１２日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】全文

【補正方法】変更

【補正内容】

【書類名】 明細書

【発明の名称】 ＲＳＡ暗号方式の暗号化器及び復号
器に使用する高速ベキ乗剰余演算法

【特許請求の範囲】

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ＲＳＡ暗号方式を用い
た暗号化装置及び復号装置の各装置内のベキ乗剰余演算
部の処理を高速にする方法に関するものである。

【０００２】

【従来の技術】情報通信技術の発展に伴い通信路（伝送
路、メモリ等）を使用したデータ通信の秘密保護として
暗号化技術は情報分野にとどまらす電子送金、シヨツビ
ング、レジヤー等の様々な分野に使用されるようになつ
た。この様なネツトワーク型社会にふさわしい暗号化方
式として従来より、公開鍵暗号方式が存在する。この公
開鍵暗号方式は各人（或いは各端末）が暗号化鍵と復号
化鍵とを一つづつ作成し暗号化鍵を公開し復号化鍵を秘
密に保持する方式であり、例えばＡという人宛に暗号文
を送信したい人は誰でもＡが公開した暗号化鍵を使用し
て、Ｍ^ｅｍｏｄｎなる演算を実行し、平文Ｍを暗号文Ｃ
に変換する。従つて鍵配送の必要がないため利点が大き
い。公開鍵暗号方式の中でもＲＳＡ暗号方式は１９７８
年ＲＩＶＥＳＴ，ＳＨＡＭＩＲ，ＡＤＬＥＭＡＮの３人
によつて発明されて多大な注目を集め実用化されるに至
つた。

【０００３】

【発明が解決しようとする課題】ＲＳＡ暗号方式は多大
の注目を集め実用化されているものの、この暗号方式は
暗号化装置による平文の暗号化、復号装置による暗号文
の復号を実行処理する際、各装置内でベキ乗演算及び剰
余演算を繰り返し使用するため暗号化及び復号に膨大な
計算時間が必要になるという解決すべき課題がある。本
発明は、法ｎを特別な形に設定することで公開鍵ｎの制
約条件が大きな２つの素数の積であるという条件のみを
有する従来方式と同様な安全性を確保して、なおかつ高
速処理可能なＲＳＡ暗号方式を提供することを目的とす
るものである。この場合における平文の暗号化通信の手
順は従来のＲＳＡ暗号方式と同じである。

【０００４】

【課題を解決するための手段】本発明の第１は下記（迅
速計算方式）で示されるＲＳＡ暗号方式の暗号化装置内
のＭ^eｍｏｄＲ^ｘ−ｙ及び復号装置内のＣ^ｄｍｏｄＲ^ｘ
−ｙなる演算を実行する際に、通常の指数演算法を梗用
して、該演算法の第ｉステツプＣ_ｉ ^２ｍｏｄＲ^ｘ−ｙの
べキ乗剰余演算をｙにｙ＜Ｒ^ｘ／２の制限を加えること
によつて従来の除数の桁数に比例した処理時間を要する
除算を使用することなく、Ｃ_ｉ ^２≡Ｃ_ｉ ^（２）．ｙ＋Ｃ
_ｉ ^（１）なる演算式をを２回繰り返し実行することによ
つて上記ベキ乗剰余演算を高速処理するＲＳＡ暗号方式
の暗号化器及び複合器に使用される高速ベキ乗剰余演算
法を（手法Ａという）である。

【０００５】 ここに、Ｍ：平文（メツセージ） ｅ：公開鍵 Ｒ^ｘ−ｙ：公開鍵、ｎ［Ｒ，ｘ（ｎの桁数），ｙは小さ
くない整数］ ｃ：暗号文 ｄ：秘密鍵 Ｃ_ｉ：指数演算法で使用される第ｉステツプにおける値 Ｃ_ｉ ^（１）：Ｃ_ｉ ²のＲ^ｘ未満の部分の値 Ｃ^ｉ（２）：Ｃ_ｉ ^２のＲ^ｘ以上の部分をＲ^ｘで割つた値

【０００６】更に手法Ａについて詳細説明すれば、一般
に合成数ｎはＲ^ｘ−ｙの形で表される。ここで、このｙ
の桁数に適切な制限を加えれば、法演算が除算を用いず
に乗算と加算で置き換えることが可能であり、通常の除
算で必要な除数の桁数に比例したステツプ数の削減が可
能になる。指数乗算法によりＭのべキ乗を求める場合の
第ｉステツプにおける値をＣ_ｉとする。第ｉステツプに
おいてｎを法とした自乗の演算を遂行する際、第ｉ＋１
ステツプにおけ牽中間値Ｃ_ｉ＋１は Ｃ_ｉ ^２ｍｏｄｎ−→Ｃ_ｉ＋１（１） として求められる。ここで ｎ ＝ Ｒ^ｘ−ｙ ｙ ＜ Ｒ^ｘ／２ （２） （ｘ，ｙは正の整数） とし、Ｃ_ｉ ^２のＲ^ｘ以上の部分をＣ_ｉ ^（２）、Ｒ^ｘ未満
の部分をＣ_ｉ（^１）とする。即ち、 Ｃ_ｉ ^２ ＝
Ｃ_ｉ ^（２）・Ｒ^ｘ＋Ｃ_ｉ ^（１） （３） とする。このようにすると明らかに Ｃ_ｉ ^２ ≡ Ｃ_ｉ ^（２）・ｙ＋Ｃ_ｉ ^（１）ｍｏｄｎ （４） の関係が成立する。

【０００７】式（４）の右辺の形はｎより大であり、且
つＲ^{ｘ＋ｘ／２＋１}より小である。従つてこれをあらた
めて Ｃ_ｉ ^（４）・Ｒ^ｘ＋ Ｃ_ｉ ^（３） （５） とおくと、 Ｃ_ｉ ^２≡Ｃ_ｉ ^（４）・ｙ＋Ｃ_ｉ ^（３）ｍｏｄｎ （６） となる。以上により、ｎによる除算はｎが式（２）を満
足する限り２ステツプの乗算、加算により式（１）が遂
行されることが判る。ただし、ここでは乗算は並列処理
により高速休を行うものとする。

【０００８】本発明の第２は下記（迅速計算方式）で示
されるＲＳＡ暗号方式の暗号化装置のＭ^ｅｍｏｄＲ^ｘ−
ｙ及び複合装置内のｃ^ｄｍｏｄＲ^ｘ−ｙなる演算を実行
する際、通常の指数演算法を使用して、該演算法の第ｉ
ステツプのＣ_ｉ ^２ｍｏｄＲ^ｘ に制限をし、従来の除数の桁数に比例した処理時間を要
する除算を使用することなく、Ｃ_ｉ ^２＝Ｃ_ｉ ^（３）・ｙ
^２＋Ｃ_ｉ ^２・ｙ＋Ｃ_ｉ ^（１）なる形の演算式を１回実行
することで上記ベキ乗剰余演算を高速処理する暗号方式
の暗号化器及び複合器に使用する高速ベキ乗剰余演算法
（手法Ｂという）である。

【０００９】 ここに、Ｍ，ｅ，Ｒ^ｘ−ｙ，Ｃ，ｄ，Ｃ_ｉは上記第１の
場合と同一である。 Ｃ_ｉ ^（２）：Ｃ_ｉ ^２のＲ^ｘ以上Ｒ^２ｘ未満の部分をＲ^ｘ
で割つた値 Ｃ_ｉ ^（３）：Ｃ_ｉ ^２のＲ^２ｘ以上の部分をＲ^２Ｘで割つ
た値

【００１０】こごに、Ｃ_ｉ ^３はＣ_ｉ ^２のＲ^２Ｘ以上の部
分をＲ^２Ｘで割つた値である。更に手法Ｂについて詳細
説明すれば、一般に合成数ｎはＲ^Ｘ−ｙの形で表され
る。ここで、このｙの桁数に適切な制限を加えれば、法
演算が除算を用いずに乗算と加算で置き換えることが可
能であり、通常の除算で必要な除数の桁数に比例したス
テツプ数の削減が可能になる。指数乗算法によりＭのベ
キ乗を求める場合の第ｉステツプにおける値をＣ_ｉとす
る。第ｉステツプにおいてｎを法とした自乗の演算を遂
行する際、第ｉ＋１ステツプにおける中間値Ｃ_ｉ ^ｉ＋１
はＣ_ｉ ^２ｍｏｄｎ→Ｃ_ｉ＋１として求まる。

【００１１】ここで、Ｃ_ｉ ^２のＲ^Ｘ以上の部分をＣ_ｉ
^（２），Ｒ^Ｘ未満の部分をＣ_ｉ ^（１）とすると、
Ｃ_ｉ ^２ ＝ Ｃ_ｉ ^（２）・Ｒ^Ｘ＋ Ｃ_ｉ ^（１）≡Ｃ_ｉ
^（２）・ｙ＋Ｃ_ｉ ^（１） （７）となる。ここで乗算
は並列処理により高速化を行うものとする。次にＣ^２
_ｉ＋１のＲ^２ｘ以上の部分をＣ_ｉ＋１ ^（３）、Ｒ^２Ｘ未
満Ｒ^Ｘ以上の部分をＣ_ｉ＋１ ^（２）、Ｒ^Ｘ未満の部分を
Ｃ_ｉ＋１ ^（１）とすると、Ｃ_ｉ＋１ ^２＝Ｃ_ｉ＋１ ^（３）
・Ｒ^２ｘ＋Ｃｉ＋Ｃ_ｉ＋１ ^（１） ＝Ｃ_ｉ＋１
^（３）・ｙ^２＋Ｃ_ｉ＋１ ^（２）・ｙ ＋Ｃ_ｉ＋１ ^（１）
（８）となる。そして高速化を計るために、式（８）の
右辺がｎ桁以上の場合でもＣ_ｉ ^２と同様、これをそのま
ま次のＣ_ｉ＋２ ^２の計算ステツプで用いる。通常、…→
Ｃ_ｉ ^２→Ｃ_ｉ＋１ ^２→Ｃ_ｉ＋２ ^２→…のステツプにおい
て桁数は自乗計算を実行するたびに増加するがＣ_ｉ＋１
^（３）・ｙ^２の桁数がＣ_ｉ＋１ ^（２）・ｙの桁数を越え
ないようにｙの桁数Ｙに制限を加えれば、最終のステツ
プでの桁数をある値以下に制限することが可能になる。
以下において、このことを検討しよう。

【００１２】ここで、 Ａ ：ｎ の桁数 Ｂ ： Ｃ_ｉ＋１ ^（２）・ｙ の桁数 Ｃ ： Ｃ_ｉ＋１ ^（３）・ｙ^２の桁数 Ｄ ： Ｃ_ｉ＋１ ^（３） の桁数 Ｙ：ｙ の桁数 とすると、 Ｂ ＝ Ｙ＋Ａ （９） Ｄ ＝ ２・ （Ｂ＋１）−２・Ａ （１０） Ｃ ＝ Ｄ＋２・Ｙ （１１） である。 Ｂ ≧ Ｃ （１２） なる条件より Ｙ＋Ａ≧２・ （Ｙ＋Ａ＋１）−２・Ａ＋２・Ｙ （１３） である。従つて として、最終ステツプの桁数をＢ＋１以下に制限し得る
ｙの桁数の制限範囲が求まる。なお、安全性の立場から
ｙの値は式（１４）を満たす範囲でできる限り大である
ことが望ましい。

【００１３】ここで、以下のことを付記する。 （イ）数ステツプに１回程度の法演算を許容すれば、式
（１４）のｙの桁に関する制約条件を更に木きくするこ
とが可能であること。 （ロ）高速演算に適した形をＲ^ｘ−ｙとしたが、Ｒ^ｘ＋
ｙの形にしても同様の高速演算が可能であること。 （ハ）ＲＳＡ暗号方式の暗号化器及び復号器以外のベキ
乗剰余演算を使用するものにも有効である。

【００１４】

【作用】上記の発明が解決すべき手段によるＲＳＡ暗号
方式を用いたデータ暗号通信は、平文Ｍの暗号化及び暗
号文Ｃの復号に使用する法演算が除算を用いずに乗算器
と加算器で置き換えることが可能であり、そのために通
常の除算で必要な除数の桁数に比例した演算ステツプ数
の削減が可能になつた。また、本発明方法の法ｎを使用
すれば、公開鍵をいわゆる“電話帳”に１０進表現で掲
載することを例に取れば公開鍵ｎの制約条件が大きな２
つの素数の積であるという条件のみを有する従来の方式
では法ｎを全桁数数字掲載する必要があり非常に長いも
のになるのに対し、共通鍵の掲載は、連続する９以外の
ランダムな数字の部分のみ掲載すればよいことになると
いう利点がある。

【００１５】

【表１】

【００１６】

【表２】

【００１７】次に本発明を実施例によつて説明する。１

【実施例１】ＲＳＡ暗号方式において下記（迅速計算方
式）の平文Ｍの暗号化を実行する式は、 Ｍ^ｅ≡Ｃｍｏｄｎ （１５） であり暗号文Ｃの復号を実行する式は、 Ｃ^ｄ≡Ｍｍｏｄｎ （１６） である。但し、 Ｍ： メツセージ Ｃ： 暗号文 ｅ： 公開鍵 ｄ： 秘密鍵 ｎ：ｐ・ｑ ｐ，ｑ ： 大きな素数（秘密）

【００１８】 こごに、Ｍ：平文（メツセージ） ｅ：公開鍵 Ｒ^ｘ−ｙ：公開鍵、ｎ［Ｒ，ｘ（ｎの桁数），ｙは小さ
くない整数］ ｃ：暗号文 ｄ：秘密鍵 Ｃ^ｉ：指数演算法で使用される第ｉステツプにおける値 Ｃ_ｉ ⁽¹⁾：のＣ_ｉ ^２のＲ^ｘ未満の部分の値 Ｃ_ｉ ^（２）：Ｃ_ｉ ^２のＲ^ｘ以上の部分をＲ^ｘで割つた値

【００１９】また一般にＲＳＡ暗号方式では２＜ｅ＜＜
ｄと選ばれることが多いが、本発明高速ベキ乗剰余演算
法ではｅ及びｄには上記のような制約はない。本発明方
式による暗号通信システムの構成原理図を上記（迅速計
算方式）に示す。ここで用いられる上記式（１５）及び
式（１６）を実行する際、一般的に指数演算法が用いら
れる〔図１〕。即ち、この演算法の第ｉステツプに手法
Ａを用いる。これをハードウエア構成とした場合のブロ
ツク図を〔図２〕に示す。この〔図２〕の回路は計算で
取り扱うパラメータＭ、ｅ、ｙを記憶するためのレジス
タと、Ｒ進乗算器Ｉ、ＩＩ、ＩＩＩと、Ｒ進加算器で構
成されている。乗算器ＩＩＩに依存すべき前段の処理と
して乗算器Ｉ，ＩＩの結果のみである。即ち、直列処理
を必要とする部分はこの３つの部分のみである。よつ
て、指数演算法の１ステツプにあたるａ・ｂｍｏｄｎな
る計算は、この３つの直列処理部分に要するクロツク数
で計算可能になる。

【００２０】

【図１】

【００２１】

【図２】

【００２２】

【実施例２】ＲＳＡ暗号方式において下記（迅速計算方
式）の平文Ｍの暗号化を実行する式は、 Ｍ^ｅ＝ Ｃｍｏｄｎ （１５） であり暗号文Ｃの復号を実行する式は、 Ｃ^ｄ＝ Ｍｍｏｄｎ （１６） である。但し、 Ｍ： メツセージ Ｃ： 暗号文 ｅ： 公開鍵 ｄ： 秘密鍵 ｎ：ｐ・ｑ ｐ，ｑ ： 大きな素数（秘密） また一般にＲＳＡ暗号では２＜ｅ＜＜ｄと選ばれること
が多いが、本発明の高速ベキ乗剰余演算法ではｅ及びｄ
にはこのような制約はない。本発明方式による暗号通信
システムの構成原理図を下記（迅速計算方式）に示す。
ここで用いられる上記式（１５）及び式（１６）を実行
する際、一般的に指数演算法が用いられる〔図１〕。即
ち、この演算法の第ｉステツプにし手法Ｂを用いる。こ
れをハードウエア構成した場合のブロツク図を〔図３］
に示す。この〔図３］の回路は計算で取り扱うパラメー
タＭ、ｅ、ｙ、ｙ^２を記憶するためのレジスタと、Ｒ進
乗算器Ｉ、ＩＩ、ＩＩＩと、Ｒ進加算器で構成されてい
る。この回路の乗算器ＩＩ、ＩＩＩは並列計算可能であ
り、乗算器ＩＩ１、ＩＩＩに依存すべき前段の処理とし
て乗算器Ｉの結果のみである。即ち、直列処理を必要と
する部分はこの２つの部分のみである。よつて、指数演
算法の１ステツプにあたるａ・ｂｍｏｄｎなる計算は、
この２つの直列処理部分に要するクロツク数で計算可能
になる。

【００２３】

【図３】

【００２４】 ここに、Ｍ，ｅ，Ｒ^ｘ−ｙ，Ｃ，ｄ，Ｃ_ｉは実施例１の
場合と同一である。 Ｃ_ｉ ^（２）：Ｃ_ｉ ^２のＲ^Ｘ以上Ｒ^２ｘ未満の部分をＲ^Ｘ
で割つた値 Ｃ_ｉ ^（３）：Ｃ_ｉ ^２のＲ^２ｘ以上の部分をＲ^２ｘで割つ
た値

【００２５】

【発明の効果】本発明の効果を纏めると次の通りであ
る。 （１）本発明によつてＲＳＡ暗号方式を使用した暗号通
信における平文の暗号化と復号にかかる時間の著しい短
縮が従来のＲＳＡ暗号方式と同程度の安全性を確保した
うえ可能となつた。即ち、多大の計算ステツプを必要と
するベキ乗剰余演算を１ステツプで処理することが可能
になつた。 （２）本発明の法ｎを使用することによつて公開鍵の管
理用メモリ（いわゆる電話帳）の節約が可能となつた。
あわせて公開鍵を暗号化装置又は、復号装置に手入力す
ることも可能である。

【図面の簡単な説明】

【図１】指数乗算法のアルゴリズムのフローチヤート。

【図２】図１に従つてハードウエア構成を取らしめた場
合の自乗剰余回路を示す一実施例。

【図３】図１に従つてハードウエア構成を取らしめた場
合の自乗剰余回路を示す他の一実施例。

【手続補正２】

【補正対象書類名】図面

【補正対象項目名】全文

【補正方法】変更

【補正内容】

【図１】

【図２】

【図３】

Claims (2)

【特許請求の範囲】
1. 【請求項１】 下記〔図１〕で示されるＲＳＡ暗号方式
   の暗号化装置内のＭ^e ｍｏｄＲ^x −ｙ及び複合装置内の
   Ｃ^d ｍｏｄＲ^x −ｙの演算を実行する際に、通常の指数
   演算法を使用して、該演算法の第ｉステツプのＣ_i ² ｍ
   ｏｄＲ^x −ｙ のベキ乗剰余演算をｙにｙ＜Ｒ² の制限を加えることに
   よつて従来の除数の桁数に比例した処理時間を要する除
   算を使用することなく、Ｃ_i ²≡Ｃ_i ⁽²⁾．ｙ＋Ｃ_i ^{( 1)}なる
   演算式で示される演算を２回繰り返し実行することによ
   つて上記のベキ乗剰余演算を高速処理することを特徴と
   するＲＳＡ暗号方式の暗号化器び複合器に使用される高
   速ベキ乗剰余演算法。 【図１】（迅速計算方式） ここに、Ｍ：平文（メツセ−ジ） ｅ：公開鍵 Ｒ^x −ｙ：公開鍵、ｎ〔Ｒ，ｘ（ｎの桁数），ｙは小さ
   くない整数〕 ｃ：暗号文 ｄ：秘密鍵 Ｃ_i ：指数演算法で使用される第ｉステツプにおける値 Ｃ_i ⁽¹⁾：Ｃ_i ²のＲ^x 未満の部分の値 Ｃ_i ⁽²⁾：Ｃ_i ²のＲ^x 以上の部分をＲ^x で割つた値 を示す。
2. 【請求項２】 〔図１〕で示されるＲＳＡ暗号方式の暗
   号化装置内のＭ^e ｍｏｄＲ^x −ｙ及び複合装置内のＣ^d
   ｍｏｄＲ^x −ｙなる演算を実行する際、通常の指数演算
   法を使用して、該演算処理の第ｉステツプのＣ_i ²ｍｏｄ
   Ｒ^x −ｙなる 例した処理時間を要する除算を使用することなく、Ｃ_i ²
   ＝Ｃ_i ⁽³⁾・ｙ² ＋Ｃ_i ⁽²⁾・ｙ＋Ｃ_i ⁽¹⁾なる形の演算式を
   １回実行することで上記ベキ乗剰余演算を高速処理する
   ことを特徴とするＲＳＡ暗号方式の暗号化器及び複合器
   に使用される高速ベキ乗剰余演算法。 【図１】ここに、Ｍ，ｅ，Ｒ^x −ｙ，Ｃ，ｄ，Ｃ_i は実
   施例１の場合と同一である。 Ｃ_i ⁽²⁾：Ｃ_i ²のＲ^x 以上Ｒ^2x未満の部分をＲ^x で割つた
   値 Ｃ_i ⁽³⁾：Ｃ_i ²のＲ^2x以上の部分をＲ^2xで割つた値 を示す。