JPS6329784A - 剰余計算方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、特定の法に対する任意の数の剰余計算を高速
に行う方式に関し、特に、多倍長剰余計算を暗号化アル
ゴリズムの計算単位とするＲ３Ａ暗号方式の暗号処理速
度の高速化に適する。

〔従来の技術〕

現在、公開鍵暗号アルゴリズムとして最も有力な方法に
、Ｒ３Ａ方式がある。Ｒ３Ａ方式では、平文をＭ、暗号
文をＣ２暗号所をｅ、ｄ、ｎ　（但し、ｅ≠ｎ）とした
とき、その暗号化と復号化のアルゴリズムは、 Ｃ＝Ｍ６（ｍａｄ　ｎ）：暗号化 Ｍ＝Ｃ’　（ｍｏｄ　ｎ）　　：復号化で表わされる。

暗号化鍵の大きさは、ｎ＝２４００゜ｏ−８２２４００
以上が、暗号強度の面から適当とされている。しかし、
その反面、暗号鍵の値が大きいため、暗号計算量は大き
くなる。

従来、Ｒ３Ａ方式を実行するハードウェアにおいては、
以下の処理手順により前記の暗号化および復号化が、実
行されていた。この時、ｅは２進数ｕ＋１桁の値として
、 ｅ＝Ｅ（ｕ）２ｕ＋Ｅ（ｕ−１）・２ｕ−”＋＝−＋−
Ｅ（０）　・２０で表わすことができ、Ｅ　（ｉ）は、
２進数ｅのｉ桁目の値を示すものとする。

Ｓ　ｔｅｐ、１　：　Ｃ４−１ Ｓｔｅｐ、　２　：　ｆｏｒ　ｉ　＝　ｕ　ｔｏ　Ｏｓ
ｔｅｐ−１（ａ）Ｍｌ←Ｃ；Ｍ２←Ｃ； Ｒ４−ＭＩ　ＸＭ２　　（ｍｏｄ　　ｎ）　　；Ｃ４−
Ｒ； （ｂ）　　ｉｆ　　Ｅ　　　（ｉ）　　＝１　　ｔｈｅ
ｎＭ１←Ｃ；Ｍ２←８； Ｒ４−ＭＩ　ＸＭ２　　（ｍｏｄ　　ｎ）　　；Ｃ４−
Ｒ； ｎｅｘｔ　　１ Ｓｔｅｐ、３　　：　Ｈａｌｔ。

上記Ｓ　ｔｅｐ、　１〜３において、ｕ＋１回のループ
計算が行われる。第１回目のループ計算においては、Ｅ
　（ｕ）＝１のとき、Ｍの値をＣとして求めている。ま
た、第を回目のループ計算においては、Ｅ　（ｔ）＝１
のとき、１＝＝ｕからｉ　＝　ｔ　＋　１までに計算さ
れたＣの値の自乗とＭの値との積の剰余としてＣを求め
ている。Ｅ　（ｔ）＝Ｏの場合は、ｉ＝ｕからｉ＝ｔ＋
１までに求めた値の自乗の剰余を求めている。このよう
な手順により、Ｍ”　（ｎｏｄ　ｎ）　＝（ＭＥ（ｕ）
・２”０ＭＥ（ｕ−１）・２”−ｊ、、ＭＥ（０）・’
）　（、、ｄｎ）を再帰的に計算している。

上記の処理において、最も計算時間が掛かるのは、Ｒ８
Ａ暗号アルゴリズムの計算単位であるモジュロ計算（剰
余計算）、 Ｒ＝ＭＩＸＭ２　（＋＋＋ｏｄ　ｎ） である、この一対の乗算と除算を、同一タイミングで実
行する計算法を以下に示す。

但し、　Ｑｊ　：計算過程での商。

Ｒｊ：計算過程での剰余。

Ｍｌ、Ｍ２：計算過程での剰余、平文 Ｍ２．ｊ　：Ｍ２を、ビットごとにＱ等分に分割し、そ
のうちｊ番目のに ビット列。

−”、ｋＱ＝ｍ（ｍ；Ｍ２の桁数） Ｍ２＝Ｍ２．ｆｌ・２”−１）ｋ＋Ｍ２．（Ｑ−１）・
２（Ｑ−２）ｋ＋・・・＋Ｍ２，１・２０（−）ニーを
越えない、最大の整数とする。

＜Ｒ＝ＭＩ　ＸＭ２（ｍａｄ　ｎ）の計算アルゴリズム
〉５ｔｅｐ、１　：　Ｒｕ＋１＋０ ８ｔｅｐ、　２　：　ｆｏｒ　ｊ　＝　Ｑ　ｔｏ　ｌ　
５ｔｅｏ−１Ｑｊ←［（（２Ｋ・Ｒｊ　＋　１）＋（Ｍ
　１・Ｍ２．ｊ））÷ｎコ Ｒｊ←（２に−Ｒｊ　＋　１）＋（Ｍ　１・Ｍ２．ｊ）
−Ｑ　ｊ　＋ｎ　　ｎｅｘｔ　　ｊ Ｓ　ｔｅｐ、３　　：　　Ｈａｌｔ。

（Ｒ＝Ｒ１＝Ｍ’ｌ　ＸＭ２（ｍｏｄ　　ｎ））公知例
（宮口庄司；Ｒ３Ａ公開分装号の高速計算法と暗号ＬＳ
Ｉの構成／情報処理学会論文誌Ｎｏｖ、１９８３．Ｖｏ
ｌ、２４．　Ｎａ６．　ｐ　ｐ　７６４−７７１参照）
では、Ｑｊの計算において、近似と補正処理を行い高速
化を計っている。

〔発明が解決しようとする問題点〕

前記公知例では、高速化に伴い暗号ＬＳＩのハードウェ
アが増加し、計算アルゴリズムも複雑なものとなってい
る。また、除算の処理ステップ数が多いため、処理が遅
くなるという欠点がある。

本発明の目的は、多倍長剰余計算の高速化を簡単な装置
により実現することにより、これを計算単位とするＲ３
Ａ暗号方式の処理速度を向上し、実用的なＲ３Ａ公開鍵
暗分装置を提供することにある。

〔問題点を解決するための手段〕

第２の実施例では、剰余を求める際、第１の実施例のよ
うに、商を求めて被除数から減算する手順を用いず、剰
余計算が加減乗算を保存する性質を用いる。すなわち Ａ　（Ｉｌｏｄ　ｎ）　＝　（Ａ　Ｑ・２　（Ｑ−””
（ｎｏｄ　ｎ）＋　Ａ　Ｑ−ｔ・２　（”　−２）ｋ”
（ｍｏｄ　ｎ）　＋　−＋　Ａ　ｘ・２　”（ｍｏｄ　
ｎ）　＋　Ｓ　）（ｍｏ、ｄ　ｎ）この様にして、２進
被除数Ａ（２ｍ桁）の上位ｍ桁をに桁（ｋ≧２）単位に
分割し、各単位で求まる除数ｎ　（ｍ桁）に対する部分
剰余と波除数下位ｍ桁Ｓを加算及び補正することにより
、剰余を求め高速化を可能にしている。

ただし、この場合、各に桁単位の被除数の上記除数ｎに
対する剰余を算出する必要がある。そこで、本発明にお
いては予め該除数に対する被除数（ｋ桁単位）の剰余の
値を計算し、ＲＯＭカード。

光カードといった外部記憶装置に記憶しておき、必要に
応じて任意の被除数の部分剰余を直接参照できる被除数
／剰余テーブルを作成しておく、また、多倍長の部分剰
余加算にはビットスライス形の並列加算方式を採用する
。

〔作用〕

被除数／剰余テーブル参照方式は、商を求める過程を省
略し、多倍長除算を複数個の部分剰余の加算に変換する
ことにより、処理ステップ数を削減することができ、同
時に、並列計算を可能としたことにより、多倍長剰余計
算の高速化が達成できる。また、簡単な構成で剰余計算
装置が実現できる。

〔発明の実施例〕

以下、本発明の動作を第１図及び第２図を用いて説明す
る。

第１図は、本発明である高速多倍長剰余計算装置の構成
を示している。装置は、剰余計算処理を行う部分１と除
数及び除数に対応する複数個の部分剰余を記憶したテー
ブルを含む外部記憶装置３から成る。

本装置への入力データ１０は被除数であり、レジスタ１
２に格納される。レジスタ１２に格納されたデータの上
位ｍ桁をに桁（ｋ≧２）ずつ分割し、そのに桁の値を部
分剰余検索用パラメータとしてレジスタ１３に格納する
。外部記憶装置３に記憶されている剰余テーブル２１及
び除数２２は、内部記憶装置２に取り込まれ、部分剰余
はレジスタ１３の値により参照されレジスタ１４へ、除
数はレジスタ１７へ格納される。また、レジスタ１２に
格納されているデータの下位ｍ桁をレジスタ１５に取り
込む、このレジスタ１４のデータとレジスタ１７のデー
タのうちセレクタ２３で選ばれたどちらか一方のデータ
とレジスタ１５のデータを並列加減算処理部１６によっ
て処理し、その結果により比較処理部１８がループまた
は終了処理を行う、また、これらの処理は、記憶装置を
内部に含む制御装置１９により制御される。以上の繰り
返しにより、出力データ１１が剰余として得られる。

次に、第１図の構成要素の動作を第２図のフローチャー
トに沿って被除数入力から剰余出力までの処理の流れを
説明する。

く剰余計算〉 ステップ１１０：被除数（２ｍ桁）を入力し、上位ｍ桁
の値をＡとし、下位 ｍ桁の数をＳとする。

ステップ１２０：Ａの値をに桁ずつ分割し、その値を下
位桁から順にＡｉ （ｉ＝１．２．・・・・・・Ｑ：ｍ＝ Ｑ　−ｋ）とする。

ステップ１３０：Ｑ−＋ｉにセットする。

ステップ１４０　：　Ａ、の値をパラメータとし部分剰
余ｒｌ　　（ｍ桁）を記憶領 域より参照する。

ステップ１５０　：　　（Ｓｉ　ｒ＋　）　→Ｓ（注）
Ｓの桁数：ｍ−＋ｍ＋Δｍ ステップ１６０：ｉ≧２ならば、ｉ　−１→ｉとしてス
テップ１４０へ飛ぶ。

ステップ１７０：６ｍ　＝　Ｏならば、ステップ２００
へ飛ぶ。

ステップ１８０：Ｓの上位Δｍ桁をに桁ずつ分割し、そ
の値を下位桁から順 にＳｉ　　（ｉ＝１．２．・・・ｐ） とする。

ただし、Δｍ＝αｋ（α： 正の整数）とするように必要 とあらば、Ｓの上位に′０′ を付加する。

ステップ１９０：Ｓｌ→Ａｔ　、　ｐ−＋２Ｓ（下位ホ
桁の値）→Ｓ としてステップ１３０へ飛ぶ。

ステップ２００　：　５４Ｒｚ ステップ２１０：　　（Ｓ−Ｂ）→Ｒ２ステップ２２０
　：　Ｒ２＜Ｏならば、Ｒ＝　ＲＩＲ２≧Ｏならば、Ｒ
＝　Ｒｚ ステップ２３０　：　Ｈａｌｔ　　剰余Ｒ以上の手順に
より、剰余を高速に求めることができる。最後に、簡単
な一実施例として具体的な数値を用いて処理手順を説明
する。

く設定〉 除数：　１０１０１１０１１　（ｍ　＝　９桁）被除数
：　１０１０１０１０１０１０１０１０１０　（２ｍ　
＝　１８桁）ジャンプパラメーター：に＝３ テーブル検索用パラメータ：０００≦ＡＩ≦１１１被除
数／剰余テーブル： く剰余計算〉 ■部分剰余の加算 １、入力データ設定（ステップ１１０）ｍ　＝　９　；
　Ａ　＝　１０１０１０１０１Ｓ　＝０１０１０１０１
０ ２、検索用パラメータ、検索回数の設定（ステップ１２
０） ｋ＝３．Ａ１＝１０１．Ａｚ＝０１０゜−Ａｓ＝１０１ Ｑ＝ｍ／に；Ｑ＝３ ３、部分剰余検索及び加算（ステップ１３０〜ステツプ
１６０） Ａ１＝　１０１　；　ｒ　ｚ＝０１０００００１１Ａｚ
＝　０１０　；　ｒｚ＝０１１０１００１１Ａ３：’＝
　１０１　；　ｒ　５＝０００１１１０００Ｓ　＝（Ｓ
　＋　ｒｚ＋　ｒｚ＋　ｒ３）＝１０００１１１０００
■剰余算出の補正（Δｍ≠０） １、各種データ設定（ステップ１７０〜ステツプ１９ｏ
） Ｓｚ＝ＯＯ１；Ａｘ＝ＯＯ１ ｐ＝ｌ　；　１２＝１ Ｓ　＝ＯＯ０１１１０００ ２、部分剰余検索及び加算（ステップ１３０〜ステツプ
１６０） Ａ　Ｉ　＝　ＯＯ１；　ｒ　ｘ　＝　０１０１００１０
１Ｓ　＝（ｒｔ＋　５）＝０１１０１１１０１３、剰余
の決定（ステップ１７０．ステップ２００〜ステツプ２
３０） ６ｍ　＝　Ｏ；　Ｒｚ＝０１１０１１１０１Ｒ２＜Ｏ；
剰余Ｒ：　Ｒｚ＝０１１０１１１０１上記実施例におい
て、従来の除算による剰余計算方式が商決定・減算のス
テップを９回（２ｍ−ｍ）必要としたのに対し、本方式
では部分剰余検索・加算のステップ３回（（２ｍ−ｍ）
／ｋ）と若干の補正ステップにより多倍長剰余計算が達
成できる。

被検数　　　　　　　除数 剰余：　１１０１１１０１　（Ｒ＜ｎ）〔発明の効果〕 本発明による剰余計算アルゴリズムの計算時間は、２進
数２ｍ桁の被除数と２進数ｍ桁の除数からその編余を求
める時、除算による剰余計算方式の計算時間をＴ　（２
ｍ　−ｍ）とすると、約Ｔ（（２ｍ−ｍ）／ｋ）となる
。従って、ジャンプパラメータにの値が１の場合、同等
のものとなるが、ｋに２以上の値を取ることにより、本
発明の計算法は、ｋ倍の速さで計算することができる。

また、前記公知例で示した多倍長の除算計算法を使用し
た場合と比べると、公知例では、まず、多倍長の除算計
算により商を求め、その商を使って剰余を求めている。

そのため、計算アルゴリズムや演算回路は、複雑なもの
になっている０本発明では、商を求める手順を省き、部
分剰余を使用した加算の繰り返しと補正の減算だけで直
接的に剰余を求めている。このため、処理も少なく演算
回路も簡単なものでよい、また、剰余計算を加減算に変
換したことにより、並列計算が可能となる。

これらのことから、本発明の多倍長剰余計算装置は、簡
単な装置によって実現でき、高速で多倍長の剰余計算を
実行できる。

【図面の簡単な説明】

第１図は本発明による高速多倍剰余計算装置のブロック
構成図、第２図は剰余計算処理のフローチャートである
。 ３−外部記慣多４１ 第　２　０

Claims (1)

1. 【特許請求の範囲】 １、特定の除数に対する剰余テーブルを予め記憶装置に
   格納しておき、任意の被除数が与えられた時、被除数を
   特定桁数で分割し、各区分に対する部分剰余を該剰余テ
   ーブルにより求め、各部分剰余の加算及び補正を並列計
   算することを特徴とする剰余計算方式。 ２、前記剰余テーブルは、メモリーカードに入れること
   を特徴とする第１項の剰余計算方式。