JPH02204768A - メッセージ変換方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は、暗号を利用するデータ通信等に適用可能なメ
ツセージ変換方法に関する。

（従来の技術） 暗号が提供するセキュリティ・サービスを利用する場合
、鍵情報をいかに安全に利用者に配送するか、または鍵
情報をどのように保管するかは重要な問題である。

１９７８年にＲｌｖｅｓｔ等によって提案された公開鍵
暗号Ｒ９Ａ　　（ＲｉＬ、Ｒｌｖｅｓｔ、Ａ、Ｓｈａｍ
ｉｒ　ａｎｄ　Ｌ、Ａｄｌａ＋ａｎ：“Ａ　ｍｅｔｈｏ
ｄ　ｏｆ　ｏｂｔａｉｎｉｎｇ　ｄｉｇｉｔａｌ　ｓｉ
ｇｎａｔｕｒｅｓ　ａｎｄ　　ｃｒｙｐｔｏｓｙｓｙｔ
ｅｏ＋ｓ　　　、Ｃｏｌｌｌｌ１．ｏｆ　　ＡＣＭ、ｐ
ｐ、１２０−１２６′）はこのような鍵配送問題のかな
りの部分を解決できる暗号方式として注目される。Ｒ３
Ａ暗号は本発明の基盤をなすので、ここで詳しく説明す
る。

鍵生成 まず、任意の相異なる大きな素数ｐとｑを生成する。生
成したｐとｑの積としてｎ−ｐ　’　ｑを作る。また、
ｐ、ｑよりＬ−λ（ｎ）−ＬＣＭ　（ｐ−１、ｑ−１）
を求める。ここでλはカーマイケル関数を表し、Ｌ　Ｃ
Ｍ　（ｐ−Ｉ　５ｑ−１）はｐ−１、Ｑ−１の間の最小
公倍数を表す。次にＬと互いに索な適当な整数ｅを選び
（３≦ｅ≦Ｌ−１）　、法りの下でのｅの乗法逆光ｄを
求める。

ｅ−ｄ＝Ｉ　ｌ５ｏｄ　Ｌ　　　　　　　　（１）この
ようにして生成された（ｅ、ｎ）が暗号化の鍵であり、
復号化は（ｄＳｎ）を用いて行うことができる。

平文Ｍと暗号Ｃは共にｎ未満の整数である。暗号化は次
のようにして行う。

Ｃ”Ｍ　　ｓ＋ｏｄ、ｎ　　　　　　　　　　　　（２
）また、ＣからＭは次のようにして求められる。

Ｍ−Ｃ’ｇ＋ｏｄ、ｎ　　　　　　　　　　　　　（３
）この復号化の変換は、受信者の秘密情報であるｐ、ｑ
を利用すると高速化することができる。その方法につい
てはＪ、Ｊ、Ｑｕｉｓｑｕａｔａｒ等による文献″Ｐａ
５ｔ　ｄｃｃ１ｐｈｅｒａ＋ｃｎｔ　ａ１ｇｏｒｉｔｈ
＋＋＋　Ｉ’ｏｒ　ＲＳＡ　ｐｕｂｌｉｃ−ｋＱ７　ｃ
ｒｙｐｔｏｓｙｓｔｅｍ　　、ＥＩｅｅＬｒＯｎ、ＬＯ
ｌｔ、１１８＋２１．ｐｐ、９０５−９０７（Ｏｃｉ、
１９８２）に詳しく述べられている。

式（３）の値を計算するのに法ｎの下で直接求めるので
はなく、まず、法ｐとｑの下で計算を進めておき、得ら
れた結果から中国剰余定理を利用して平文を求めるので
ある。（中国剰余定理については、たとえば池野・小山
著「現代暗号理論」電子通信学会編（ｐ１９　）を参照
。）この方法を具体的に説明するために、Ｃ１、Ｃ％ｄ
　　、ｄ　　、ｍ　　％ｍ　を次のように定義、する。

Ｃｔ　−Ｃｍｏｄ、ｐＳ Ｃ２−Ｃｍｏｄ、ｑ ｄ　１−　ｄ　　ｎ＋ｏｄ、（ｐ−１）、ｄ　２−　ｄ
　　ｍｏｄ、（ｑ−１）　（５）ｍ、　−Ｍ　　ｍｏｄ
、Ｉ）ｓ ｍ２−Ｍ　ｌｌ１ｏｄ、ｑ この時、次式が成立する。

ｄｌｍｏｄ、ｐ ｍｔ　　″Ｃ１ これより平文Ｍは次の連立合同式の根として求められる
。

Ｍ＝ｍｌ（ｍｏｄ、ｐ　）　　　　　　　　　　　　（
９）ＭＥｍ２　（ｍｏｄ、Ｑ） （ｌＯ） １？ｓＡ暗号は以上のような手続きで実現されるが、こ
こでのこの暗号の要点を整理すると、Ａ、各人ごと異な
る公開鍵はｅ％ｎはリストのような形で公開されており
、だれでもアクセスできる。

Ｂ、秘密鍵ｄ、ｐｓ　Ｑ、λ（ｎ）は個人の秘密であり
、他人に知られないように十分注意する必要がある。

Ｃ１暗号化機能のほかに署名機能がある。

Ｄ、Ｒ３Ａ暗号の安全性を保障するためには秘密鍵ｐＳ
ｑの桁数を各々十進百桁程度の大きさに選ぶ必要がある
。ｎはこの場合、十進二百桁程度の数になり、ＲＳＡの
暗号化・復号化変換は膨大な処理量の計算となる。

多くの人が加入するネットワークでＲＳＡ暗号の利点を
最大限に引出せる運用法としては、各人に個別に鍵を発
行して、可搬の記憶媒体にその鍵を記憶させ、それを各
自が持ち歩くのがよい。この時、上記Ｂに述べた点は運
用上非常に重要である。Ｂの条件を満足させることので
きる個人の秘密鍵の格納媒体としては、ＩＣカードが携
帯性のある個人対応の計算装置および記憶装置として最
も好適である。しかしながら、実際にＩＣカードを利用
したＲＳＡ暗号のシステムを構築しようとすると次のよ
うな二つの問題が生ずる。

ＩＣカードに鍵を格納した場合、上記Ｂの要求から、理
想的にはＩＣカード内でＲＳＡの復号変換および署名作
成を行うのが良い。ＩＣカードにはパスワード照合によ
るアクセス制御機能があるので、ＩＣカード内で変換を
行えばｄ、ｐＳＱ’ｔλ（ｎ）がＩＣカード外に洩れる
心配はなくなるからである。しかしながら、現状では上
記りに述べたことおよびＩＣカードの計算力不足が理由
でＲＳＡ暗号の変換をＩＣカードで行った場合に、実用
上十分な処理速度を達成することができない。

これは前記Ｑｕｉｓｑｕａｔｅｒ等の高速化手法を用い
ても同様である。また、ＲＳＡ専用の高速演算ＬＳＩを
ＩＣカードに実装することも考えられるが、カードコス
トの増大は避けられない。

一方、ＩＣカードを単にアクセス制御機能のある、鍵メ
モリとして利用することは容易である。

手間のかかる暗号変換は計算能力の高いＩＣカード外の
装置、たとえば端末装置に行わせることによって実用的
な処理速度を達成可能である。しかし、この場合にはｄ
を端末装置に渡すことになるので、端末装置の設計およ
び維持管理に十分な注意を怠ると、端末装置経由でｄが
他人に洩れる恐れがある。また、偽の端末装置によって
知らぬ間にｄを盗まれるかもしれない。

このような二つの問題点を解決するために、最近、端末
装置には秘密鍵ｄに関する情報をもらさずに、端末装置
の計算力のみを借りてＩＣカードが効率よ＜　ＲＳＡの
暗号変換を行える手段が提案された。これを提案者らに
ならって以下「依頼計算法」と呼ぶことにする。依頼計
算そのものはひろい概念であるが、これをＲＳＡ暗号の
変換に応用する手法で本発明と関連が深い方式は文献「
安全な計算依頼法について」　（加藤、松本、今井、１
９８８年　暗号と情報セキュリティ　シンポジウム資Ｉ
Ｆ−３，１９８ｇ、２月）に示されている。以下、その
方式を説明するとともに、第７図にその手順を概念的に
示す。

準備として、まず次の関係式を満たすｒ１ｒ　ｑ　、Ｒ
を求める。

ｒ　　　−Ｒ’　ｍｏｄ（＋）−１）　　　　　　　　
　　　　　（１１）ｒ　　　−Ｒ’　ｌ！１ｏｄ（Ｑ−
１）　　　　　　　　　　　　　　（１２）ただし、χ
（「）−℃（ｒ）　十ｗ　（ｒ）−２と定義するとき、
ｒ　　、ｒ　　は、 ｑ χ（「）十χ（ｒ　　）　　　　　　　（１３）ｑ が小さい数であるように選ばれる。なお、Ｊ２（「）は
ｒのビット長、ｗ（ｒ）はｒのハミング重みを表わし、
χ（「）はｒを指数とするべき乗剰余計算に要する剰余
乗算の回数を表わしている。

また、 ｗ　　＝ｑ　（ｑ−’　　ａ＋ｏｄｐ）　　ｍｏｄｎ。

ｗ　　＝ｐ　（ｐ−’　　ｍｏｄｑ）　　ｍｏｄｎ　　
　　（１４）も計算しておく。ＩＣカード内にはｒ　　
Ｓｒ　　。

ｑ ＲＳｄ、ｐＳｑ、λ（ｎ）、ｙｌ、ｗ　　Ｓｗ　　が記
ｑ 憶されている。

次にＩＣカードはｄの代わりに、 ｄ’　＝ｄ　φＲｍｏｄλ（ｎ）　　　　　　　（１５
）を用いて、端末装置に対してＣをｄ′で変換したＭ′
の計算を依頼する（ステップ７０１．７０２）。ただし
、 Ｍ’　−ＣＩＩｏｄ　ｎ、　　　　　　　　　（１Ｂ）
端末装置は計算したＭ′をＩＣカードに送り返す（ステ
ップ７０３）。ＩＣカードはこれを次式によって変換し
、平文Ｍを得る（ステップ７０４）ｐ Ｍ＝　（（Ｍ’　ｍｏｄｐ）　　ｆｆ１ｏｄ　ｐ）　ｗ
　十ｑ （Ｍ’　ｎｏｄｑ）　　　ａ＋ｏｄｑ）　ｗ　　）　ｔ
ｎｏｄｎ（１３）式が小さい値になるようなｒ　　、ｒ
　　を選ｑ んでいるので、（１７）式に現れるべき乗剰余計算は計
算力の比較的小さなＩＣカードでも効率よく計算するこ
とができる。また、端末装置に対してはｄを直接示すの
ではなく、（１５）式による変換を施したｄ′を見せる
だけなので安全性は高くなる。このように依頼計算によ
れば、秘密鍵ｄの機密性を増しつつ端末装置の計算力を
借りて効率良く復号変換を行うことができる。

さて、実用的なシステムに上記の依頼計算法を適用した
場合を考察してみることにする。（１５）式の変換は事
前に行うことができるので、復号変換開始以降、実際に
行わなければならないのは（１６）、（１７）式の変換
のみである。（１７）式の変換の右辺は（１Ｂ）式で計
算されるＭ′を含んでいるので、（＋７）式は（１６）
式の処理が終わってからでないと実行できない。すなわ
ち、復号変換の処理時間は、（１６）および（１７）式
の処理に要する演算時間の和で定まることになる。一方
、端末装置が行う（１Ｇ）式の変換は、たとえば汎用の
高性能汎用１６ビツトマイクロプロセツサである１８０
２８６で実行してもｎが５１２ビット程度のときには約
３０秒の処理時間を要する。したがって、外部計算装置
をよほど高性能の専用マシンで実現しない限り、ここで
説明した依頼計算によって演算時間を十分小さくするこ
とは不可能である。

以上まとめると、まずＲＳＡ暗号は計算の手間が大きい
ので、ＩＣカードのような計算力が比較的小さい装置で
実行させようとすると多大な計算時間を要する。また、
Ｒ９Ａの計算を高速に行える外部装置を用意して、これ
を計算させようとす・えと、復号変換やディジタル署名
作成に必要な秘密情報を外部装置に知られてしまい、不
正使用される恐れがあった。また「依頼計算」を用いて
秘密情報は外部装置にもらすことなく、外部装置の計算
力のみを借りて効率よく変換を行う手法が提案されてい
るが、従来、提案されている方法では、確かにＩＣカー
ドが行うべき処理の量は減らすことはできるものの、Ｉ
Ｃカードが実行する計算と外部装置が行う計算とは同時
に並列処理することができず、外部装置が極めて高速な
処理を行うのでなければ、°その効果は半減してしまう
方式であった。

（発明が解決しようとする課題） 以上の問題点に鑑み、本発明の目的は、端末装置の処理
とＩＣカードの処理の大部分とを同時に行える方式を提
供することによって、依頼計算に要する処理時間を従来
方式に比べて大幅に短縮させ、さらに、端末装置および
ＩＣカードの処理速度を過剰に速くする必要をなくし、
端末装置のコストおよびＩＣカードのコストを押えるこ
とにイるＯ ［発明の構成］ （課題を解決するための手段） 本発明は、メツセージブロックＣを他のメツセージブロ
ックＭに変換するメツセージ変換方法であって、秘密鍵
ｎ、ｄを有している第１の装置がｍ個の乱数Ｒｔ　　（
ｔ−１、・・・、ｍ）を生成するとともに、この乱数Ｒ
ｉを用いて秘密鍵ｄからｄ′を生成する過程と、ｄ′お
よびｎが前記第１の装置から第２の装置に転送される過
程と、前記第２の装置がメツセージブロックＣから ｄ′ Ｍ−−Ｃｌ１ｏｄ　　ｎ を算出する過程と、前記第２の装置がＭ′を算出してい
るのと並行して前記第１の装置は乱数ＲｉとｎからＸを
算出する過程と、Ｍ′が前記第２の装置から前記第１の
装置に転送される過程と、前記第１の装置が Ｍ＝Ｍ′Ｘｍｏｄｎ によりメツセージブロックＭを算出する過程と、を具備
することを特徴とする。

（作用） このように構成されたメツセージ変換方法では、まず第
２装置が知るのは公知のｄ′とｎとＣおよびＭ′のみで
あり、特に秘密鍵ｄを直接知ることができないので、第
２の装置にｄを持ち逃げするなどという不正な機能を仕
組もうとしても不可能となる。また、第１の装置が実行
する演算のうち、Ｘｐｌ、　ＸｑｌまたはＸＩを求める
部分は、第２の装置の演算とは独立に行える。また、乱
数ｒｐ１、ｒ、ｔのビット長に制約をつければ、Ｘｐｌ
、ＸＱ−１を計算する演算量も削減できる。

（実施例） 本発明の実施例を以下に述べる。説明の都合上、第１図
に示すように計算依頼側をＩＣカード、計算請負側を端
末装置として以下説明するが、依頼側と請負側は独立な
装置、ソフトなど、この節での説明を越えない範囲で任
意である。また、実施例の説明では暗号文Ｃを平文Ｍに
戻す処理に関する依願計算として説明するが、同一の変
換で実現されるディジタル署名の作成にも本発明は適用
松導鳩る・ 第２図はこのメツセージ変換方法１こ用いられる端末装
置２の斜視図である。

同図に示されるようにこの端末装置２は本体１、デイス
プレィ３、キーボード５、リードライタ７を有している
。そしてリードライタ７にＩＣカード９が挿入され、本
体】にフロッピィ−ディスク１１が挿入される。

第３図はＩＣカード９の構成を示すブロック図であり、
このＩＣカード９はＩ１０コンタクト１３、ＣＰＵ１５
、データメモリ１７、プログラムメモリ１９とを有する
。

第４図は本体１の構成を示すブロック図であり、この本
体１はデイスプレィコントローラ２１、中央処理装置２
３、メインメモリ２５、第１通信ボート２７、第２通信
ボート２９、フロッピィ−ディスクドライバ３１、キー
ボード（Ｉｌｏ）３３とを有し、これらが内部データバ
ス３５で接続される。デイスプレィコントローラ２１は
デイスプレィ３を制御する。中央処理装置２３はこの端
末」置２全体を制御する。メインメモリ２５はフロッピ
ーディスク１１に記憶されているデータの蓄菰等を行う
。

第１通信ボート２７は通信回線１２に接続され、この通
信回線１２は他の端末装置２と接続されている。第２通
信ボート２９はリードライタフに接続されている。フロ
ッピィ−ディスクドライバ３１はフロッピィ−ディスク
１１を駆動する。キーボード（Ｉｌｏ）３３はキーボー
ド５と接続されている。

次にこの端末装置２とＩＣカード９を用いてメツセージ
変換方法について説明する。

まず、準備として（１１）、（１２）によく似た式（１
８）、（１９）を満たす適当な乱数の組ｒ１ｒ　ｑ　、
Ｒを求める。

ｒ　　　−Ｒｎｏｄ　　　（ｐ−１）　　　　　　　　
　　　　　（１ｇ）ｒ　　　−Ｒｆｆ１ｏｄ　　　（ｑ
−１）　　　　　　　　　　　　　（１９）この時、従
来技術と同様に、 χ（ｒ　　）＋χ（ｒ　　）　　　　　　　　（２０）
ｑ が比較的小さい数であるという制約を課す。

（Ｉ８）、（１９）式の連立方程式は、「、ｒ９を適当
に定めてその後に求めるもので、解の存在条件および解
法は、たとえば、高木貞治：　“初等整数輪講義°、共
立出版、　ｐｐ、３１−４５に示されている。この連立
方程式の解はＬ−ＬＣＭ　（ｐ−１、ｑ−１）を法とし
て唯一定まる。また、必要に応じて、ｗ　　＝ｑ　（ｑ
−’ＩＩｏｄ　ｐ　）　ｔＡｏｄ　ｎ　。

ｗ　　　　−ｐ　　　（ｐ’　　ａ＋ｏｄ　　ｑ　　）
　　ａ＋ｏｄ　　ｎ　　　　　　　　（２１）も計算し
ておく。後に述べるようにＷ　　ＳＷ　　はｑ 必ず用意しなければならない定数ではない。本実施例に
おいてはＩＣカード内にはｒ　　′、ｒ　　ｓｄｓｑ ｐ　、’ｑ　、λ（ｎ）、ｎ、ｄ’　　ｗ　　Ｓｗ　　
が記憶ｑ されている。

本発明の最も単純で、かつ最もその効果が顕著な実施例
として、ｄからｄ′を求める変換を、ｄ’　−（ｄ−Ｒ
）　　ｏ＋ｏｄλ（ｎ）　　　　　（２２）と定義する
場合を説明する。

端末装置２の処理フローを示したのが第５図である。

まず、ユーザは端末装置２に向かうとともに、丑”分゛
のＩＣカード９を端末装置２に接続されたＩＣカード９
のリーダ・ライタ７に挿入する（ステップ５０１）。

そして、端末装置２の適当なキーを叩き使用開始を端末
装置２に知らせる。この時、同時にり一ダ・ライタ７を
介してＩＣカード９にクロックおよび電源が供給され、
適当な初期化（ステップ５０２）の後にＩＣカード９は
通信待ち状態となる。

端末装置２はＩＣカード９のユーザ確認を行うために、
ユーザに対してパスワードの入力を指示する（ステップ
５０３）。

パスワードが入力されない場合（スッテブ５０４）１時
間をチエツクしくステップ５０５）、時間切れの場合は
タイムアウトとなり、そうでない場合はステップ５０３
に戻る。パスワードが入力されるとＩＣカード９にパス
ワードが転送され（ステップ５０６）、　　このパスワ
ードはＩＣカード９内に記憶されている登録パスワード
と比較され、照合結果が端末装置２に転送される（ステ
ップ５０７）。照合結果が一致していれば（ステツメ：
・・−・ 、ｖ、、ｖ’２％　０８　）　、Ｉ　Ｃカード９は使用
可能状態となるが、一致しない場合にはＩＣカードは使
用不能である。ユーザからのコマンド入力があると（ス
テップ５０９）、終了コマンドであるかないかが判断さ
れ（ステップ５１０）、コマンドサブルーチンの実行が
行われる（ステップ５１１）。

次にコマンドサブルーチンの実行について述べる。

これ以降の手順は、第１図に示されている。

端末装置２はこの暗号文ＣをまずＩＣカード９宛てに伝
送しくステップ１０１）、同時にＩｃカード９のメモリ
に書込まれているｄ′とｎを読み出す（ステップ１０２
〉。端末装置２はこの二つの情報を用いて暗号文Ｃから
、Ｍ′を次式に従って計算する（ステップ１０３）。

Ｍ’　−Ｃｄｍｏｄ　ｎ　　　　　　　　　（２３）端
末装置２は計算したＭ′をＩＣカード９に送る（ステッ
プ１０５）。

一方、ＩＣカード９は端末装置２の計算と並行して、（
２４）〜（２６）式に従って定数Ｘを求める（ステップ
１０４）。

Ｘｐ　−（Ｃｍｏｄ　ｐ）　”　ｍａｄ　　ｐ　　　　
　（２４）Ｘｑ　＝　　（Ｃｍｏｄ　ｑ）　　ｒｑＩＩ
ｌｏｄ　　ｑ　　　　　（２５）を計算し、次式によっ
てＸを求める。

Ｘ−（（Ｘｐ　）　ｒｐａ＋ｏｄ　ｐ）　ｗｐ＋　（Ｘ
ｑ　）　　　ｍａｄ　Ｑ）　ＷＱ　）　ｍｏｄ　ｎ　　
　（２６）ここで、（２４）〜（２６）式について補足
説明しておく。

（２４）、（２５）式はＸに関する連立方程式と見るこ
とができるが、中国剰余定理よりこの２式を満たすＸは
一意に定まる。そして、その−解法が（２Ｂ）式の右辺
である。ここでは先に計算したＷｐ、ｗｑなる二つの補
助変数を用いてＸを導出している。

しかし、（２４）　、（２５）を満たすＸの導出法はこ
れに限らない。たとえば前出のＪ、Ｊ、Ｑｕｌｓｑｕａ
ｔｅｒ等による文献’Ｆａｓｔ　ｄｅｃｉｐｈｅｒｍｅ
ｎｔ　ａｌｇｏｒｉｔｈｍ　ｆ’。

ｒ　Ｒ３Ａ　ｐｕｂｌｉｃ−ｋｅｙ　ｃｒｙｐｔｏｓｙ
ｓｔｅｍ　　　、ＩＥＩｅｃｔｒｏｎ、Ｌｃｔｔ、　、
ｉｌｌ、　２１．ｐｐ、９０５−９０７（Ｏｃｔ、１９
８２）にはこの種の連立方程式の別な解法が示されてい
る。

パシたがって、（２Ｇ）式によるＸの導出および補助変
数ｗ、ｗ　　の使用は本質的ではなく、（２４）ｐｑ （２５）を同時に満たすＸを求めることのみが本質であ
る。それゆえ、この実施例が本発明を実際に応用する場
合のＸの求め方を限定するものではない。

さて、ＩＣカード９が本来求めたかった平文Ｍは暗号文
Ｃを、 Ｍ−Ｃ’　ｌｌ１ｏｄ　　ｎ　　　　　　　　　　　　
　（２７）と変換して得られるが、このＭは端末装置２
が計算したＭ′とＩＣカード９が計算したＸとから次式
によって求められる（ステップ１０６）。

Ｍ　−（Ｍ′−Ｘ）　ｌｌ１ｏｄ　ｎ　　　　　　　　
（２８）この計算は、この例ではＩＣカード９の内部で
行われる。ＩＣカードは得られたＭを復号結果として端
末装置２に伝送する（ステップ１０７）。

端末装置２はこれをデイスプレィに表示するとともに、
ユーザからの指示で補助記憶装置に書込んで一連の復号
化手続きを終了し、ユーザはリーダ・ライタ７からＩＣ
カード９を抜き取り、作業を終了する。

ここて、本実施例において手続きの過程で知ることので
きる端末装置２はＭとＭ′からＸを容易に求められるの
で、（２８）式の計算はＩＣカード９で行わないで端末
装置・２で行っても良いことを注意しておく。そのよう
な手順のときには端末装置２がＩＣカード９にＭ′を伝
送するのではなく、ＩＣカード９が端末装置２に対して
Ｘを伝送することになる。

以上の手続きの中で、（２８）式でＭが正しく計算でき
ることは、以下のように説明される。

まず、（２４）〜（２６）より、 Ｘ−ＣＲｓｏｄ　ｎ　　　　　　　　　　　　　（２９
）である。これは（従来の技術）でふれた中国剰余定理
より明らかである。

一方、 Ｍ’＃Ｃｔｘｏｄｎ 、　　ｃ　（ｄ−Ｒ）ｎ＋ｏｄλ　（ロ）−Ｒ −Ｃｍｏｄｎ −ｃ’ｃ″″ＲＩｌｏｄｎ ｍａｄ　　ｎ （２９）、（３０）式より、 ｄ−Ｒ’Ｒ （Ｍ’　　−Ｘ）ｓｏｄ　　ｎ　　−（ＣＣ−Ｃ）ｍａ
ｄ　　ｎ−Ｃｄｔｓ。ｄｎ −Ｍ　　　　　　　　　　　　　　（３１）これで（２
８）式が成立つことが示された。

次に、計算の手間について考察する。まず、（１８）〜
（２２）までの計算は変換を開始する以前に準備してお
くことができる。暗号文Ｃが与えられ、初めて実行可能
な部分の計算のみを考慮すればよい。Ｃが与えられて以
降実行する手続きとして、 ■ＩＣカード９が行う、（２４）〜（２６）式によって
Ｘを求めること、 ■端末装置２が行う（２３）式の計算、■ＩＣカード９
が行う（２８）式の計算、がある。このうち最も演算手
段が多いのは■の端末装置２の計算である。具体的には
この値はλ（ｄ′）で表されるが、ｎが５１２ビツトの
場合には、これは最悪で１０２４回程度Ｏ５１２ビツト
のべき乗剰余３１算になる。次に、演算手数が多いのは
■である。■のうち支配的なのは（２４）、（２５）の
計算であり、それはχ（ｒ　　）＋χ（「）回の２５６
ビツトのべき乗剰余演算である。ｒ、ｒ９を予め小さく
選んでおくことにより、この演算量が押えられる。また
、ＩＣカードが行う■の演算は５１２ビツトの剰余乗算
１回である。全体として■■の演算が支配的である。さ
らに、本発明において特に注意すべきは、■の手続きと
■の手続きが独立であり、同時に並列処理できるという
ことである。たとえば、■の処理が汎用パソコンで３０
秒かかるとするとき、ｒ　　、ｒ　　を適当なビット長
に定めてＩＣカードでの■の演算時間を３０秒程度にす
れば、復号に要する総演算時間はほぼ３０秒となる。■
〜■の処理に要する時間を各々ＴＩ、Ｔ２　、Ｔ３で表
すと、一般に総演算時間Ｔは、Ｔ−Ｍａ　ｘ　（Ｔｌ　
、Ｔ２　）　＋Ｔ３：Ｍａ　ｘ　（Ｔｌ　、　Ｔ２　）
　　　　　　　（３２）で表せることになる。ただし、
Ｍ　ａ　ｘ　（Ａ％　Ｂ）はＡＳＢのうち、大きい方を
取る関数である。

第１の実施例において、Ｍ′と（Ｘｐ　、　Ｘｑ　）の
１組、もしくはこの組と等価な値を用いてＭを導く手順
はここに示した方法に限らない。別の導出法を次に示す
。

Ｍより次の２式から、 Ｍ’　　　−Ｍ’　１ｌｏｄ　ｐ　　　　　　　　　　
（３３）Ｍ’　　　−Ｍ’　ｍｏｄ　ｑ　　　　　　　
　　　（３４）Ｍ’　　、Ｍ’　　を求めて、 ｑ Ｍ　　−Ｍ’　　　ΦＸｐ　ｌｌ１ｏｄ　ｐ　　　　　
　　（３５）ｐ Ｍ　　−Ｍ’　　　・Ｘ　　ｎ＋ｏｄｑ　　　　　　　
（３Ｂ）ｑ　　　　　　　　ｑ　　　　　９ を得る。（３５）　、（３Ｂ）を連立させれば所望のＭ
が得られる。

本発明の第２の実施例として第６図に従って、ｄからｄ
′を求める変換を、 ｄ′−（ｄ十Ｒ）ｌｌｏｄλ（ｎ）　　　　　（３７）
と定義する場合を説明する。これ以降の実施例の説明で
は端末装置２の起動や、ＩＣカード９の初期化に関する
説明は省略し、演算の手続きのみ順序を追って説明する
。Ｒは第１の実施例で用いたものと同じとする。第１の
実施例同様に、端末装置２は外部から与えられた暗号文
ＣをＩＣカード（ζ伝送しくステップ６０１）、ＩＣカ
ードからｄｎを受取る（ステップ６０２）。端末装置２
は第１の実施例同様、次式で与えられる、Ｍ′を計算す
る（ステップ６０３）。

ｄ。

Ｍ’　−Ｃｍｏｄ　ｎ　　　　　　　　　　（３ｇ）端
末装置２は計算したＭ′をＩＣカード９に送り返す（ス
テップ６０７）。

一方、ＩＣカード９は、 Ｘ　　＝　　（Ｃｎｏｄ　ｐ）　　ｒｐｒＡｏｄ　　ｐ
　　　　　（３９）Ｘ　　−（ＣＩＩｏｄ　ｑ）　　ｒ
ｑｓｏｄ　　ｑ　　　　　（４０）を計算しく′７．テ
ップ６０４）、次式によってＸを求める（ステップ６０
５）。

Ｘ−（（Ｘ　　）　　ｒｐＩｌｏｄ　ｐ）　　ｗ　　＋
ｐ （Ｘ　　）　”　ｓｏｄ　ｑ）　　ｗ　　ｌ　　ｍｏｄ
　ｎ　　（４１）ｑ さらに、方程式 ％式％（４２） を解いてＸ−１を求める（ステップ６０６）。この解法
は拡張ユークリッドの互除法と呼ばれ、詳細は、たとえ
ば前出の「現代暗号理論」を参照。

さて、ＩＣカードが本来求めたかった値、ＭはＭ　−Ｃ
’　ｇｏｄ　ｎ　　　　　　　　　　　　　（４３）で
あるが、これは端末装置２が計算したＭ′とＩＣカード
が計算したＸ−１とから次式によって求められる（ステ
ップ６０８）。

Ｍ　−（Ｍ’　　・Ｘ−’　）　１ｌｏｄ　ｎ　　　　
　　　（４４）ＩＣカード９は得られた結果を端末装置
２に伝送し処理を終了する（ステップ６０９）。

（４４）式でＭが正しく計算できることは以下のように
説明される。

まず、（３５）〜（３８）および中国剰余定理より、Ｘ
−１−Ｃ″″Ｒｍｏｄ　　ｎ　　　　　　　　　　（４
５）である。

一方、 Ｍ　’　　＝　（：　’Ｌ’１１０ｄ　ｎ＝　Ｃ（ｄ＋
Ｒ）　ｍａｄ　λ（ｎ）ｓｏｄ　ｎｄ＋Ｒ −Ｃｔｎｏｄｎ −ＣｄＣＲＩＩｌｏｄ　ｎ　　　　　　　　　（４６）
（２９）、（３０）式より、 Ｒ−Ｒ （Ｍ’　　・Ｘ−’）＋ｏｄｎ−（ＣＣ＊Ｃ）ｍｏｄｎ
＝Ｃ’ｍｏｄｎ −Ｍ　　　　　　　　　　　　（４７）これで（２８）
式が成立つことが示された。

第２の実施例において、Ｍ′と（Ｘｐ　ＳＸｑ　）組も
しくはこの組と等価な値を用いてＭを導く手順はここに
示した方法に限らない。

たとえば、予めＣ−１を拡張ユークリッドの互除法によ
り計算しておけば、 Ｘｐ　’　−（Ｃ−’　ＩＩｏｄ　ｐ　）　”　ｆｆ１
ｏｄ　　ｐ　　　（４８）Ｘｑ　’　−（Ｃ−’　ＩＩ
ｏｄ　ｑ　）　ｒｑｍｏｄ　　ｑ　　　（４９）が計算
でき、これを用いてＸ−１を計算できる。Ｍの導出は（
４０）式同様に行えば良い。

また、Ｍより次の２式から、 Ｍ’　　　−Ｍ’　ｆｌｌｏｄ　ｐ　　　　　　　　　
　（５０）Ｍ’　　　−Ｍ’　ｇｏｏｄ　ｑ　　　　　
　　　　　（５１）Ｍ’　　、Ｍ’　　を求めて、 ｑ Ｍ　　−Ｍ’　　　・Ｘ　　−’ａｏｄｐ　　　　　　
（５２）ｐ　　　　　　　ｐ　　　　　ｐ Ｍ　　−Ｍ’　　　・Ｘ　　−’ｎ＋ｏｄｑ　　　　　
　（５３）ｑ　　　　　　　　ｑ　　　　　ｑ を得る。（４８）、（４９）を連立させれば所望のＭが
得られる。第２の実施例の効果も第１の実施例の説明の
最後に述べたことと同様である。

第３の実施例として、より一般化された方式を説明する
。第１、第２の実施例では各々カーマイケル関数λ（ロ
）を法とする代数系の上で唯一の乱数Ｒを用いていた。

第３の実施例ではｍ個の乱数Ｒｉ（１−１、・・・、Ｉ
Ｉ；ＩＩＩ≧１）を用いた一般形について説明する。ま
ず、各乱数Ｒｉは、各々次の方程式を満たしているとす
る。

Ｒｉａ＋ｏｄ　ｐ　−ｒ　１ｐ　　　　　　　　　　　
（５４）Ｒｉｍｏｄ　ｑ　＝　ｒ　ｉｑ　　　　　（５
５）なお、第１の実施例同様、 χ（ｒ　ｉｐ）＋χ（ｒ　、９）　　　　　　　　（５
［ｉ）の大きさに適当な制約を付けるものとする。（５
４）〜（５６）式よりわかるように、先にｒ　　Ｓｒ　
　をｉｐ　　　１ｑ 定めて、それからＲｉを求める。

このようにして求めたＲｉを用いて次のようなＸからｙ
への変換ｆ−１をそれぞれ定める。

ｙ＝ｆｌ　　（Ｒｉ，ｘ）　　　　　　　　　（５７）
このように定めたｍ個の変換を合成した変換を用いてｄ
をｄ′に変換する。

ｄ’　−ｆｍ　　（Ｒｉ１，・・・、ｆ　２（Ｒ２、ｆ
　１（Ｒｉ、ｄ）戸・・）　　　　　　　　　　　　　
　　　　　　　　（５８）ｆｌの具体的定義としては次
の３種類を用いることができる。

ｙｍｘｅ（Ｒｉ−１）　ｆｆ１ｏｄ　λ（ｎ）　　　　
　（５９）ｙ−（ｘ−Ｒｉ）　ｍｏｄ　λ（ｎ）　　　
　　　（６０）ｙ　−（ｘ　＋ＲＩ　）　ｌ１ｏｄ　λ
（ｎ）　　　　　　（ａｔ）（５９）式は従来の技術で
述べた関数であり、（６０）（６１）式はそれぞれ、第
１、第２の実施例で示した関数である。これらの任意の
組合わせを用いて依頼計算を実現できる。

前の例と同様に、（５８）式で求めたｄ′をＩＣカード
９は端末装置２に送る。端末装置２は、次式によりＭ′
を求める。

ｄ。

Ｍ’　−Ｃｓｏｄ　ｎ、　　　　　　　　　（６２）端
末装置２はＭ′をＩＣカード９に送り返し、ＩＣカード
９はこれを（５８）式の変換手順によって定まるＭ導出
の手順に従ってＭ′からＭを求める。

前の同量様（６０）式、（６１）式に対応する変換につ
いては、端末装置２での計算と平行して、Ｘ”　−（Ｃ
ｇｏｄ　　ｐ）　　　　　　　ｌ１ｏｄ　　ｐ　　　　
　　　　（［ｉ３）１ｐ Ｘ”　−（Ｃｌ１ｏｄ　Ｑ）　　　　ｍｏｄ　ｑ　　　
　（８４）ｌｑ など、Ｍ′からＭを求める変換に必要な値を計算するこ
とができる。本例で具体的にどうしてＭを求めるかは従
来技術および第１、第２の実施例を繰返し適用するだけ
で容易に実現できるので、これ以上の説明は省略するこ
とにする。

［発明の効果］ 以上説明したように本発明によれば、端末装置の処理と
ＩＣカードの処理の大部分を同時に行える方式を提供し
、依頼計算に要する処理時間を従来方式に比べて大幅に
短縮することができる。さらに、本発明によれば端末装
置およびＩＣカードの処理速度を過剰に速くする必要が
なく、端末装置のコストおよびＩＣカードコストを押え
ることができる。

【図面の簡単な説明】

第１図は本発明の実施例に係るメツセージ変換方法の処
理フローを示す図、第２図は端末装置２の斜視図、第３
図はＩＣカード９の構成を示すブロック図、第４図は端
末装置２の構成を示すブロック図、第５図は端末装置２
の処理を示すフローチャート、第６１！！ｆ）は他の実
施例に係るメツセージ変換方法の処理フローを示す図、
第７図は従来の処理フローを示す図である。 １；・・・・・・・・本体 ９・・・・・・・・・ＩＣカード １１・・・・・・・・・フロッピィーディク１５・・・
・・・・・・ＣＰＵ ２３・・・・・・・・・中央処理装置 ２５・・・・・・・・・メインメモリ 出願人　　　　　　株式会社　東芝

Claims (3)

【特許請求の範囲】
1. （１）メッセージブロックＣを他のメッセージブロック
   Ｍに変換するメッセージ変換方法であって、秘密鍵ｎ、
   ｄを有している第１の装置がｍ個の乱数Ｒ＿ｉ（ｉ＝１
   、・・・、ｍ）を生成するとともに、この乱数Ｒ＿ｉを
   用いて秘密鍵ｄからｄ′を生成する過程と、 ｄ′およびｎが前記第１の装置から第２の装置に転送さ
   れる過程と、 前記第２の装置がメッセージブロックＣからＭ′＝Ｃ＾
   ｄ′　ｍｏｄ　ｎ を算出する過程と、 前記第２の装置がＭ′を算出しているのと並行して前記
   第１の装置は乱数Ｒ＿ｉとｎからＸを算出する過程と、 Ｍ′が前記第２の装置から前記第１の装置に転送される
   過程と、 前記第１の装置が Ｍ＝Ｍ′・Ｘ　ｍｏｄ　ｎ によりメッセージブロックＭを算出する過程と、を具備
   することを特徴とするメッセージ変換方法。
2. （２）メッセージブロックＣを他のメッセージブロック
   Ｍに変換するメッセージ変換方法であって、秘密鍵ｎ、
   ｄを有している第１の装置がｍ個の乱数Ｒ＿ｉ（ｉ＝１
   、・・・、ｍ）を生成するとともに、この乱数Ｒ＿ｉを
   用いて秘密鍵ｄからｄ′を生成する過程と、 ｄ′およびｎが前記第１の装置から第２の装置に転送さ
   れる過程と、 前記第２の装置がメッセージブロックＣからＭ′＝Ｃ＾
   ｄ′　ｍｏｄ　ｎ を算出する過程と、 前記第２の装置がＭ′を算出しているのと並行して前記
   第１の装置は乱数Ｒ＿ｉとｎからＸ＾−＾１を算出する
   過程と、 Ｍ′が前記第２の装置から前記第１の装置に転送される
   過程と、 前記第１の装置が Ｍ＝Ｍ′・Ｘ＾−＾１　ｍｏｄ　ｎ によりメッセージブロックＭを算出する過程と、を具備
   することを特徴とするメッセージ変換方法。
3. （３）メッセージブロックＣを他のメッセージブロック
   Ｍに変換するメッセージ変換方法であって、秘密鍵ｎ、
   ｄを有している第１の装置がｍ個の乱数Ｒ＿ｉ（ｉ＝１
   、・・・、ｎ）を生成するとともに、この乱数Ｒ＿ｉを
   用いて秘密鍵ｄからｄ′を生成する過程と、 ｄ′およびｎが前記第１の装置から第２の装置に転送さ
   れる過程と、 前記第２の装置がメッセージブロックＣからＭ′＝Ｃ＾
   ｄ′　ｍｏｄ　ｎ を算出する過程と、 前記第２の装置がＭ′を算出しているのと並行して前記
   第１の装置は乱数Ｒ＿ｉとｎからＸおよびＸ＾−＾１を
   算出する過程と、 Ｍ′が前記第２の装置から前記第１の装置に転送される
   過程と、 前記第１の装置が Ｍ′、Ｘ、Ｘ＾−＾１をもちいてメッセージブロックＭ
   を算出する過程と、 を具備することを特徴とするメッセージ変換方法。