JPH0619393A - 依頼計算装置 - Google Patents
依頼計算装置Info
- Publication number
- JPH0619393A JPH0619393A JP5068866A JP6886693A JPH0619393A JP H0619393 A JPH0619393 A JP H0619393A JP 5068866 A JP5068866 A JP 5068866A JP 6886693 A JP6886693 A JP 6886693A JP H0619393 A JPH0619393 A JP H0619393A
- Authority
- JP
- Japan
- Prior art keywords
- calculation
- main device
- conversion
- client
- predetermined
- 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
Abstract
(57)【要約】
【目的】 安全性を確保し、かつ演算速度の早い依頼計
算装置を提供することを目的とする。 【構成】 Md mod nを計算する際に、べき指数dに依
存しないべき指数b(j)を用いて上記の式を変形す
る。そして、べき指数b(j)をサーバ側に伝送して上
記の式の演算を行なう。 【効果】 b(j)はべき指数dに依存しないので、べ
き指数dに関する情報は外部に漏れることはない。
算装置を提供することを目的とする。 【構成】 Md mod nを計算する際に、べき指数dに依
存しないべき指数b(j)を用いて上記の式を変形す
る。そして、べき指数b(j)をサーバ側に伝送して上
記の式の演算を行なう。 【効果】 b(j)はべき指数dに依存しないので、べ
き指数dに関する情報は外部に漏れることはない。
Description
【0001】
【産業上の利用分野】本発明は安全性の高い計算依頼が
可能で秘密に依存しない演算のみを補助装置に依頼する
依頼計算装置に関する。
可能で秘密に依存しない演算のみを補助装置に依頼する
依頼計算装置に関する。
【0002】
【従来の技術】一般に、通信情報処理システムの安全確
保の為に、公開鍵暗号が盛んに研究されている。RSA
暗号をはじめ多くの公開鍵暗号は次の(1)式で示され
るようなべき乗剰余計算を基本演算として構成されてい
る。
保の為に、公開鍵暗号が盛んに研究されている。RSA
暗号をはじめ多くの公開鍵暗号は次の(1)式で示され
るようなべき乗剰余計算を基本演算として構成されてい
る。
【0003】 C=Md mod n …(1) ここで暗号としての強度を確保するために通常、各変数
C,M,n,dは512 ビット程度以上の大きさの値を用
いる。そのため処理ステップ数が非常に大きくなり、処
理速度の比較的小さい装置でこれを演算しようとすると
多くの処理時間がかかるという問題が生じる。
C,M,n,dは512 ビット程度以上の大きさの値を用
いる。そのため処理ステップ数が非常に大きくなり、処
理速度の比較的小さい装置でこれを演算しようとすると
多くの処理時間がかかるという問題が生じる。
【0004】さらに、RSA暗号の復号変換では(1)
式のべき指数dを秘密に保たなければならないので演算
を行うときのべき指数の扱いには特に注意が必要であ
る。暗号の鍵となるdやnをICカードの様なアクセス
制御機能のある記憶媒体にいれておくと安全で携帯に便
利である。しかし、ICカード以外の装置がべき乗を行
うのであれば、ICカードからべき乗計算装置に鍵d,
nを送らねばならず第3者にdが漏れる可能性が生ず
る。また、ICカード自身の持つ中央処理ユニット(C
PU)でべき乗計算を行うことも考えられるが、一般に
ICカードのCPUの数値計算能力はあまり大きくない
ので実用的な処理時間を達成するのは困難である。
式のべき指数dを秘密に保たなければならないので演算
を行うときのべき指数の扱いには特に注意が必要であ
る。暗号の鍵となるdやnをICカードの様なアクセス
制御機能のある記憶媒体にいれておくと安全で携帯に便
利である。しかし、ICカード以外の装置がべき乗を行
うのであれば、ICカードからべき乗計算装置に鍵d,
nを送らねばならず第3者にdが漏れる可能性が生ず
る。また、ICカード自身の持つ中央処理ユニット(C
PU)でべき乗計算を行うことも考えられるが、一般に
ICカードのCPUの数値計算能力はあまり大きくない
ので実用的な処理時間を達成するのは困難である。
【0005】そこで、従来より、処理の高速化とべき指
数の秘密の確保をともに実現する方式として、安全に補
助装置に計算を依頼する方法が提案されており、これは
依頼計算法とよばれている。通常、依頼計算はクライア
ント、サーバおよび両者を結ぶ通信回線の3つの部分か
らなる装置によって実行される。この内、クライアント
は目的とする処理に関わる秘密情報を持つ装置でサーバ
と比べて演算能力が相対的に劣っている。また、サーバ
はクライアントから依頼された処理内容を実行し、結果
を通信回線を介してクライアントに返す。このような処
理において、第3者にクライアントの秘密情報を漏らさ
ずに、サーバの補助によって全体の処理時間を短縮する
のが依頼計算である。ちなみにRSA暗号の復号変換に
ついて依頼計算法を構成しようという場合、クライアン
トの秘密情報は(1)式のべき指数dである。
数の秘密の確保をともに実現する方式として、安全に補
助装置に計算を依頼する方法が提案されており、これは
依頼計算法とよばれている。通常、依頼計算はクライア
ント、サーバおよび両者を結ぶ通信回線の3つの部分か
らなる装置によって実行される。この内、クライアント
は目的とする処理に関わる秘密情報を持つ装置でサーバ
と比べて演算能力が相対的に劣っている。また、サーバ
はクライアントから依頼された処理内容を実行し、結果
を通信回線を介してクライアントに返す。このような処
理において、第3者にクライアントの秘密情報を漏らさ
ずに、サーバの補助によって全体の処理時間を短縮する
のが依頼計算である。ちなみにRSA暗号の復号変換に
ついて依頼計算法を構成しようという場合、クライアン
トの秘密情報は(1)式のべき指数dである。
【0006】そして、これまでに提案されている、べき
乗計算の為の依頼計算の具体的なプロトコルの例とし
て、松本らの方式(文献:松本他、”Speeding,up,secr
et,computations,with,insecure,auxiliary,devices",,
Proc.,of,Crypto'88,,Springer,Lecture,Notes,in,Comp
uter,Science,,403,,pp.497-506,(1988))とその改良版
や変形版(文献:C.-S.,Laih, 他:"Two,efficient,serv
er-aided,secret,computation,protocols",,ASIACRYPT'
91アブストラクト集,,1991,92年出版予定)がある。
しかしこの2つのプロトコルでは、サーバの演算が秘密
指数dの値と完全には独立でないのでクライアント単独
で計算を行う場合に比べて安全性が劣化している。これ
に対し、これらの方式で起こっていた安全性の低下を防
止できる方式として、Quisquaterらはサーバの処理を秘
密指数dの値に依存しない様に構成する方式を提案して
いる(文献:J.J.Quisquater, 他:”Speeding,up,smar
t,card,RSA,computations,with,insecure,coprocessor
s",,SMART,CARD,2000講演論文集,1989年10
月)。しかしながら、Quisquaterらの方式は通信量やク
ライアント/サーバの処理量が大きく、より効率的な方
式の提案が望まれていた。
乗計算の為の依頼計算の具体的なプロトコルの例とし
て、松本らの方式(文献:松本他、”Speeding,up,secr
et,computations,with,insecure,auxiliary,devices",,
Proc.,of,Crypto'88,,Springer,Lecture,Notes,in,Comp
uter,Science,,403,,pp.497-506,(1988))とその改良版
や変形版(文献:C.-S.,Laih, 他:"Two,efficient,serv
er-aided,secret,computation,protocols",,ASIACRYPT'
91アブストラクト集,,1991,92年出版予定)がある。
しかしこの2つのプロトコルでは、サーバの演算が秘密
指数dの値と完全には独立でないのでクライアント単独
で計算を行う場合に比べて安全性が劣化している。これ
に対し、これらの方式で起こっていた安全性の低下を防
止できる方式として、Quisquaterらはサーバの処理を秘
密指数dの値に依存しない様に構成する方式を提案して
いる(文献:J.J.Quisquater, 他:”Speeding,up,smar
t,card,RSA,computations,with,insecure,coprocessor
s",,SMART,CARD,2000講演論文集,1989年10
月)。しかしながら、Quisquaterらの方式は通信量やク
ライアント/サーバの処理量が大きく、より効率的な方
式の提案が望まれていた。
【0007】なお、べき指数を秘密にするという前提を
置かない一般のべき乗計算を少ない乗算回数で実現する
方法については、これまで種々の方式が提案されてい
る。しかし、それらの方式は、依頼計算とは違って、べ
き乗をサーバとクライアントが分担し、しかもクライア
ント以外にはべき指数を漏らさないようにすることを目
的としていない。従ってそれらの方式をそのままの形で
依頼計算の目的を達成するために用いることは困難であ
る。
置かない一般のべき乗計算を少ない乗算回数で実現する
方法については、これまで種々の方式が提案されてい
る。しかし、それらの方式は、依頼計算とは違って、べ
き乗をサーバとクライアントが分担し、しかもクライア
ント以外にはべき指数を漏らさないようにすることを目
的としていない。従ってそれらの方式をそのままの形で
依頼計算の目的を達成するために用いることは困難であ
る。
【0008】
【発明が解決しようとする課題】このように、従来の依
頼計算装置では、前記松本らの方式では安全性に乏しく
第3者に解読される危険性があり、Quisquaterらの方式
では、処理量が多く演算に長時間を要するという欠点が
あった。
頼計算装置では、前記松本らの方式では安全性に乏しく
第3者に解読される危険性があり、Quisquaterらの方式
では、処理量が多く演算に長時間を要するという欠点が
あった。
【0009】この発明はこのような従来の課題を解決す
るためになされたもので、その目的とするところは、高
い安全性を確保し、かつ、演算に要する時間を短縮し得
る依頼計算装置を提供することにある。
るためになされたもので、その目的とするところは、高
い安全性を確保し、かつ、演算に要する時間を短縮し得
る依頼計算装置を提供することにある。
【0010】
【課題を解決するための手段】請求項1記載の本発明
は、演算手段を有する主装置と演算手段を有する1つな
いしは複数の補助装置から構成される依頼計算装置にお
いて、前記依頼計算装置はべき乗剰余計算: Md mod n を実行するものであり、前記主装置は固有の秘密情報で
あるべき指数dを有し、前記主装置は前記べき指数dを
2より大きな正整数bを基数としたb進数表現: d=Σ di bi により展開した全ての係数di を保持し、前記補助装置
は、所定の底であるMと所定の法であるnと、前記基数
bを割り切る所定の整数βに依存し、前記d及び前記係
数di のいずれにも依存しない変換として、Mに対しβ
乗を繰り返しnで剰余をとった複数の値を計算し、これ
らの計算結果を主装置に送信し、主装置は補助装置から
受信した複数の計算値と、自装置内に保持する前記複数
の係数diと前記nに依存した変換により、べき乗剰余
計算結果を主装置内に得ることを特徴とする。
は、演算手段を有する主装置と演算手段を有する1つな
いしは複数の補助装置から構成される依頼計算装置にお
いて、前記依頼計算装置はべき乗剰余計算: Md mod n を実行するものであり、前記主装置は固有の秘密情報で
あるべき指数dを有し、前記主装置は前記べき指数dを
2より大きな正整数bを基数としたb進数表現: d=Σ di bi により展開した全ての係数di を保持し、前記補助装置
は、所定の底であるMと所定の法であるnと、前記基数
bを割り切る所定の整数βに依存し、前記d及び前記係
数di のいずれにも依存しない変換として、Mに対しβ
乗を繰り返しnで剰余をとった複数の値を計算し、これ
らの計算結果を主装置に送信し、主装置は補助装置から
受信した複数の計算値と、自装置内に保持する前記複数
の係数diと前記nに依存した変換により、べき乗剰余
計算結果を主装置内に得ることを特徴とする。
【0011】請求項2記載の本発明は、演算手段を有す
る主装置と演算手段を有する1つないしは複数の補助装
置から構成される依頼計算装置において、前記主装置は
固有の秘密情報を有し、前記秘密情報に依存した秘密計
算を実行するものであり、前記主装置は、乱数発生手段
を有し、前記秘密計算を実行していない時点において、
前記乱数発生手段により複数の乱数を発生し、前記複数
の乱数から所定の変換により得られる乱数依存データを
計算し、前記乱数と前記乱数依存データを保存し、秘密
計算実行時には、前記補助装置は前記秘密情報に依存し
ない所定の変換を実行して得られる第一の変換値を前記
主装置に送信し、前記主装置は前記第一の変換値に前記
乱数を作用させる所定の変換を実行して得られる第二の
変換値を前記補助装置に送信し、前記補助装置は所定の
変換により得られる第三の変換値を前記主装置に送信
し、前記主装置は第三の変換値と前記乱数依存データに
依存した所定の変換を実行して秘密計算の実行結果を自
装置内に得ることを特徴とする。
る主装置と演算手段を有する1つないしは複数の補助装
置から構成される依頼計算装置において、前記主装置は
固有の秘密情報を有し、前記秘密情報に依存した秘密計
算を実行するものであり、前記主装置は、乱数発生手段
を有し、前記秘密計算を実行していない時点において、
前記乱数発生手段により複数の乱数を発生し、前記複数
の乱数から所定の変換により得られる乱数依存データを
計算し、前記乱数と前記乱数依存データを保存し、秘密
計算実行時には、前記補助装置は前記秘密情報に依存し
ない所定の変換を実行して得られる第一の変換値を前記
主装置に送信し、前記主装置は前記第一の変換値に前記
乱数を作用させる所定の変換を実行して得られる第二の
変換値を前記補助装置に送信し、前記補助装置は所定の
変換により得られる第三の変換値を前記主装置に送信
し、前記主装置は第三の変換値と前記乱数依存データに
依存した所定の変換を実行して秘密計算の実行結果を自
装置内に得ることを特徴とする。
【0012】請求項3記載の本発明は、第1項記載のべ
き指数dを2より大きな正整数bを基数としたb進数表
現: d=Σ di bi により展開した全ての係数di に対し、複数の整数から
なる2つの集合が規定され、前記係数di の全ては、前
記集合のうち第一の集合の一要素と前記集合のうち第二
の集合の一要素の積に対し基数bを法として合同な関係
を有し、主装置は個々の係数di に対応する第一の集合
の要素と第二の集合の要素をそれぞれ対にして保持し、
補助装置は、所定の底であるMと所定の法であるnと、
前記基数bを割り切る所定の整数βと、前記第二の集合
の個々の要素に依存した複数のべき乗剰余計算を実行
し、該計算結果を前記主装置に送信し、前記主装置は、
前記補助装置から受信した計算値と、自装置内に保持す
る前記複数の係数di に対応した第一の集合の各要素と
前記nに依存した変換により、べき乗剰余計算結果を主
装置内に得ることを特徴とする。
き指数dを2より大きな正整数bを基数としたb進数表
現: d=Σ di bi により展開した全ての係数di に対し、複数の整数から
なる2つの集合が規定され、前記係数di の全ては、前
記集合のうち第一の集合の一要素と前記集合のうち第二
の集合の一要素の積に対し基数bを法として合同な関係
を有し、主装置は個々の係数di に対応する第一の集合
の要素と第二の集合の要素をそれぞれ対にして保持し、
補助装置は、所定の底であるMと所定の法であるnと、
前記基数bを割り切る所定の整数βと、前記第二の集合
の個々の要素に依存した複数のべき乗剰余計算を実行
し、該計算結果を前記主装置に送信し、前記主装置は、
前記補助装置から受信した計算値と、自装置内に保持す
る前記複数の係数di に対応した第一の集合の各要素と
前記nに依存した変換により、べき乗剰余計算結果を主
装置内に得ることを特徴とする。
【0013】
【作用】上述の如く構成すれば、補助装置が計算する値
は、主装置が保持する秘密情報dに依存していないので
これからdに関する秘密が主装置外に漏れることはな
い。このことは本発明の全てに対して成立する。
は、主装置が保持する秘密情報dに依存していないので
これからdに関する秘密が主装置外に漏れることはな
い。このことは本発明の全てに対して成立する。
【0014】本願第一の発明では、補助装置が実行する
部分はM<bi mod n (i=0,1,2,…,1-1)(但し、1は
b進数表現による指数dのサイズ)である。秘密情報d
がどのような値であっても、補助装置が実行するこれら
の演算結果のほとんど全ては以降の主装置での計算に利
用される。すなわち、補助装置が計算し、送信するデー
タ数は必要最低限のものである。このことにより通信時
間および補助装置の計算時間が共に短縮され、べき乗剰
余結果を得るまでの時間が短縮される。
部分はM<bi mod n (i=0,1,2,…,1-1)(但し、1は
b進数表現による指数dのサイズ)である。秘密情報d
がどのような値であっても、補助装置が実行するこれら
の演算結果のほとんど全ては以降の主装置での計算に利
用される。すなわち、補助装置が計算し、送信するデー
タ数は必要最低限のものである。このことにより通信時
間および補助装置の計算時間が共に短縮され、べき乗剰
余結果を得るまでの時間が短縮される。
【0015】本願第二の発明では、主装置の空き時間に
乱数生成を行う。秘密情報dに依存したデータであって
も予め生成した乱数を作用させることにより、dに依存
しないデータに変換できる。すなわち、乱数を作用させ
ることにより、dに依存した所定の計算を、秘密が漏れ
ないように補助装置に依頼できる。このことにより補助
装置に依頼できる計算部分が拡大し、全体として計算時
間が短縮される。
乱数生成を行う。秘密情報dに依存したデータであって
も予め生成した乱数を作用させることにより、dに依存
しないデータに変換できる。すなわち、乱数を作用させ
ることにより、dに依存した所定の計算を、秘密が漏れ
ないように補助装置に依頼できる。このことにより補助
装置に依頼できる計算部分が拡大し、全体として計算時
間が短縮される。
【0016】本願第三の発明では、べき指数dをb進数
展開した個々の係数di を2整数の積で表現する。但
し、2つの整数は予め定められた2つの集合に1つずつ
含まれる。一方の集合の全要素に依存して定まる計算を
補助装置が実行し、それ以外の部分を主装置が実行す
る。補助装置の計算するデータは、その全てが主装置の
演算に必要ではない。しかし、既知の2集合の積で表現
するため、例えば既知の集合の要素の和で表現する場合
に比べて、不要なデータの割合が少なくなり、補助装置
に必要な計算量と必要な通信量が減少する。
展開した個々の係数di を2整数の積で表現する。但
し、2つの整数は予め定められた2つの集合に1つずつ
含まれる。一方の集合の全要素に依存して定まる計算を
補助装置が実行し、それ以外の部分を主装置が実行す
る。補助装置の計算するデータは、その全てが主装置の
演算に必要ではない。しかし、既知の2集合の積で表現
するため、例えば既知の集合の要素の和で表現する場合
に比べて、不要なデータの割合が少なくなり、補助装置
に必要な計算量と必要な通信量が減少する。
【0017】
【実施例】以下、本発明の実施例を図面に基づいて説明
する。
する。
【0018】演算手順の説明の前にまず本発明の適用が
最も有効である場合として、ICカードシステムを例に
とり、その典型的なハードウェア構成を図2を参照しな
がら説明する。
最も有効である場合として、ICカードシステムを例に
とり、その典型的なハードウェア構成を図2を参照しな
がら説明する。
【0019】同図において、ICカード203とはCP
Uとメモリ、外部との通信端子を持つ名刺大のプラステ
ィック・カードである。秘密指数dと法nはICカード
203のメモリに記録されている。特に、dはカード外
に漏れることがないようにアクセス制御されている。
Uとメモリ、外部との通信端子を持つ名刺大のプラステ
ィック・カードである。秘密指数dと法nはICカード
203のメモリに記録されている。特に、dはカード外
に漏れることがないようにアクセス制御されている。
【0020】ICカード203は読み取り・書き込み用
のインタフェース装置すなわちリーダ・ライタ202を
介して端末201に接続される。端末201にはべき乗
を高速に行える演算能力の高いCPUがあってICカー
ド203のべき乗計算を補助する。ICカード203が
以下の説明における「クライアント」に相当し、端末が
「サーバ」に相当する。またリーダ・ライタ202を含
むICカード203と端末201が交換する情報の伝送
路が「通信回線」に相当する。
のインタフェース装置すなわちリーダ・ライタ202を
介して端末201に接続される。端末201にはべき乗
を高速に行える演算能力の高いCPUがあってICカー
ド203のべき乗計算を補助する。ICカード203が
以下の説明における「クライアント」に相当し、端末が
「サーバ」に相当する。またリーダ・ライタ202を含
むICカード203と端末201が交換する情報の伝送
路が「通信回線」に相当する。
【0021】図1は、本発明が適用された依頼計算装置
の典型的な構成を示すブロック図である。なお、同図は
必ずしもICカードシステムに限定されない。クライア
ント1の代表的な機能ブロックとして、クライアントの
動作を制御する制御部11と、2つの整数値を乗じて結
果を法の値で割った余りを求める剰余乗算処理部12
と、秘密のべき指数を格納するべき指数レジスタ13
と、中間結果等を格納するメモリ14と、外部との通信
を行うための通信処理部16と、これらの間のデータの
授受を実現する為の内部バス15がある。クライアント
1は通信回線3を介してサーバ2とデータのやりとりが
できる。サーバの代表的な構成ブロックは、制御部21
と、剰余乗算処理部22と、メモリ23と、内部バス2
4、および通信処理部25で構成される。一般に、サー
バのべき乗処理能力はクライアントのべき乗処理能力に
比べて相当に高い。
の典型的な構成を示すブロック図である。なお、同図は
必ずしもICカードシステムに限定されない。クライア
ント1の代表的な機能ブロックとして、クライアントの
動作を制御する制御部11と、2つの整数値を乗じて結
果を法の値で割った余りを求める剰余乗算処理部12
と、秘密のべき指数を格納するべき指数レジスタ13
と、中間結果等を格納するメモリ14と、外部との通信
を行うための通信処理部16と、これらの間のデータの
授受を実現する為の内部バス15がある。クライアント
1は通信回線3を介してサーバ2とデータのやりとりが
できる。サーバの代表的な構成ブロックは、制御部21
と、剰余乗算処理部22と、メモリ23と、内部バス2
4、および通信処理部25で構成される。一般に、サー
バのべき乗処理能力はクライアントのべき乗処理能力に
比べて相当に高い。
【0022】次に、本発明に基づく第1実施例を図3に
示すフローチャートに基づいて説明する。クライアント
の処理の目的はべき指数dの秘密を保ちつつ、最終的に
C=Md mod nを得ることである。なお、以下に示す各
フローチャートでは、図中の1点鎖線の右側がサーバ側
の処理を示し、左側がクラアント側の処理を示す。
示すフローチャートに基づいて説明する。クライアント
の処理の目的はべき指数dの秘密を保ちつつ、最終的に
C=Md mod nを得ることである。なお、以下に示す各
フローチャートでは、図中の1点鎖線の右側がサーバ側
の処理を示し、左側がクラアント側の処理を示す。
【0023】
【外1】 のビット数をmとするとき、dのビット数も通常m程度
である。
である。
【0024】
【数1】 但し、0≦dj ≦2k −1。このべき指数dはクライア
ント以外には秘密である。なお、以下の説明で記号「a
←b」は値bを変数aに代入することを表す。また、
(2)式における2kjが特許請求の範囲に示すb(j)
である。そして、クライアントとサーバは以下の各ステ
ップに従って処理を進める。図中の処理ステップ番号は
以下の手続きのそれと対応している。
ント以外には秘密である。なお、以下の説明で記号「a
←b」は値bを変数aに代入することを表す。また、
(2)式における2kjが特許請求の範囲に示すb(j)
である。そして、クライアントとサーバは以下の各ステ
ップに従って処理を進める。図中の処理ステップ番号は
以下の手続きのそれと対応している。
【0025】ステップST1:クライアントはM,nを
サーバに送る。
サーバに送る。
【0026】ステップST2:サーバは以下の(a)〜
(c)の処理を行う。
(c)の処理を行う。
【0027】(a)初期設定。
【0028】y0 ←M
【外2】 yj ←yj-1 ∧2k mod n(注意:記号a∧bはaのb
乗を表す)
乗を表す)
【外3】 次に、クライアントはサーバから逐次送られてくる、y
j (j=1,2,…,
j (j=1,2,…,
【外4】 乗算して行く。
【0029】ステップST3:添え字i=1,2,…,
2k −1について初期化する。
2k −1について初期化する。
【0030】z(i)←1
【外5】 但し、y0 =Mとし、dj =0についてはyj は掛けな
い。
い。
【0031】z(dj )←{z(dj )・yj }mod n そして、クライアントは以下の処理を行う。
【0032】ステップST5:添え字i=2k −2,2
k −3,…,2,1についてこの順に、 z(i)←{z(i)・z(i+1)}mod n を計算する。
k −3,…,2,1についてこの順に、 z(i)←{z(i)・z(i+1)}mod n を計算する。
【0033】ステップST6:ステップST5をもう一
度繰り返す。
度繰り返す。
【0034】ステップST7:メモリz(1)の内容が
求める結果である。
求める結果である。
【0035】以上の手順でz(1)にC=Md mod nが
得られる理由は以下の通りである。まず、yj は定義か
ら次のように表現される。
得られる理由は以下の通りである。まず、yj は定義か
ら次のように表現される。
【0036】 yj ={M∧2k j }mod n …(3) ステップST3,ST4の結果、z(i)にはdj =i
を満たす任意の添え字jを持つyj が累積されている。
式で表現すると、次の(4)式となる。
を満たす任意の添え字jを持つyj が累積されている。
式で表現すると、次の(4)式となる。
【0037】
【数2】 ここで、
【数3】 に(4)を代入して項の順序を入れ換えて、Mのべき指
数を添え字jの大きい順に並べると(5)式のMを底と
するべき指数はdに等しくなることがわかる。すなわち
(4)式と(5)式によってC=Md mod nが計算でき
る。ところで、ス
数を添え字jの大きい順に並べると(5)式のMを底と
するべき指数はdに等しくなることがわかる。すなわち
(4)式と(5)式によってC=Md mod nが計算でき
る。ところで、ス
【外6】 計算している。従って以上の手続きによってクライアン
トは目的の演算結果を得ることができる。
トは目的の演算結果を得ることができる。
【0038】さて、このような手順による依頼計算の性
能について考察する。
能について考察する。
【0039】べき指数の秘匿性:上記の手順によれば通
信回線を流れる情報や、サーバの処理は秘密のべき指数
dの値に依存していない。従ってdに関する情報は以上
の手順によってクライアント外に漏れることはない。
信回線を流れる情報や、サーバの処理は秘密のべき指数
dの値に依存していない。従ってdに関する情報は以上
の手順によってクライアント外に漏れることはない。
【0040】サーバの処理量0 サーバの処理の内、最も
手間のかかる部分は通常ステップST2(b)のべき乗
剰余計算部分である。ステップST2(b)では(m−
k)回の剰余乗算を必要とする。
手間のかかる部分は通常ステップST2(b)のべき乗
剰余計算部分である。ステップST2(b)では(m−
k)回の剰余乗算を必要とする。
【0041】クライアントの処理量:クライアントの処
理の内、最も手間のかかるのは、ステップST4とステ
ップST5,ST6の剰余乗算である。それらのステッ
プで
理の内、最も手間のかかるのは、ステップST4とステ
ップST5,ST6の剰余乗算である。それらのステッ
プで
【外7】 通信量:サーバとクライアントの間でやり取りされるメ
ッセージを、mビットのブロックを単位として数える。
ステップST1とステップST2(c)の通信
ッセージを、mビットのブロックを単位として数える。
ステップST1とステップST2(c)の通信
【外8】 メモリ量:演算に関わるメモリ量をmビットのブロック
を単位として概算すると、サーバはyi とM,nの3ブ
ロック、クライアントはM,yj ,z(i)、n、およ
びdの(2k +3)ブロックである。
を単位として概算すると、サーバはyi とM,nの3ブ
ロック、クライアントはM,yj ,z(i)、n、およ
びdの(2k +3)ブロックである。
【0042】以上は他の方式の特性と共に表1にまとめ
る。また、暗号システムで用いられる典型的な法nのビ
ット数は512ビットなので、その場合の具体的性能を
表2にまとめる。他の方式との比較は後ほどまとめて行
う。
る。また、暗号システムで用いられる典型的な法nのビ
ット数は512ビットなので、その場合の具体的性能を
表2にまとめる。他の方式との比較は後ほどまとめて行
う。
【0043】なお、RSA暗号のべき乗計算を行う場合
には、法nは桁数がnの半分程度の2つの素数p,qの
積であり、クライアントは通常その値を知っている。整
数論の性質からnを法とする剰余乗算1回は、p,qを
法とする剰余乗算を各1回行い結果を中国剰余定理で合
成することでも実現できる。このことを利用してクライ
アントが行う剰余乗算を法p,法qに分けて実行するこ
とが可能である。その場合の利点としては、法p,法q
で考えると法nでべき乗を考える場合と比べてべき指数
の長さが約半分となるので、サーバがクライアントに送
るyj の数が第1実施例で示した数の約半分ですむ点で
ある。そのため通信量の削減と、サーバの演算量の削減
を達成できる。以下の実施例においても、クライアント
の剰余乗算を法pと法qに分けて行うことによって、第
1実施例の場合と全く同様に通信量とサーバの演算量の
削減を達成できる。
には、法nは桁数がnの半分程度の2つの素数p,qの
積であり、クライアントは通常その値を知っている。整
数論の性質からnを法とする剰余乗算1回は、p,qを
法とする剰余乗算を各1回行い結果を中国剰余定理で合
成することでも実現できる。このことを利用してクライ
アントが行う剰余乗算を法p,法qに分けて実行するこ
とが可能である。その場合の利点としては、法p,法q
で考えると法nでべき乗を考える場合と比べてべき指数
の長さが約半分となるので、サーバがクライアントに送
るyj の数が第1実施例で示した数の約半分ですむ点で
ある。そのため通信量の削減と、サーバの演算量の削減
を達成できる。以下の実施例においても、クライアント
の剰余乗算を法pと法qに分けて行うことによって、第
1実施例の場合と全く同様に通信量とサーバの演算量の
削減を達成できる。
【0044】次に本発明に基づく第2実施例を図4に示
すフローチャートに基づいて説明する。まず、べき指数
dはmビットの2進数であるとし、そのビット位置を最
下位ビットから順に、ビット位置0、その隣をビット位
置1、と定義する。そして、
すフローチャートに基づいて説明する。まず、べき指数
dはmビットの2進数であるとし、そのビット位置を最
下位ビットから順に、ビット位置0、その隣をビット位
置1、と定義する。そして、
【外9】 出されていてクライアントのみがそれを記憶している。
【0045】ブロック切り出しは次の様に行う。2進表
現されたべき指数を最下位ビットから最上位ビットの方
向に走査し、ビット「1」が現れるまで走査を続ける。
ビット「1」が現れたら、そのビットから上位ビットに
むけて、そのビットを含むkビットを第1のブロックu
1 として切り出す。また、前記ビット「1」のビット位
置をw(1)と表す。以下同様にして、まだ切り出しの
行なわれていないビットを最上位ビットまで走査し、ビ
ット「1」が現れる度にブロックの切り出しを行う。こ
のときdは次の(6)式の様に表される。
現されたべき指数を最下位ビットから最上位ビットの方
向に走査し、ビット「1」が現れるまで走査を続ける。
ビット「1」が現れたら、そのビットから上位ビットに
むけて、そのビットを含むkビットを第1のブロックu
1 として切り出す。また、前記ビット「1」のビット位
置をw(1)と表す。以下同様にして、まだ切り出しの
行なわれていないビットを最上位ビットまで走査し、ビ
ット「1」が現れる度にブロックの切り出しを行う。こ
のときdは次の(6)式の様に表される。
【0046】
【数4】 ブロックの切り出し方から、ur は奇数かつ1≦ur ≦
2k −1を満たす。以
2k −1を満たす。以
【外10】 ある。
【0047】ステップST11:クライアントはM,n
をサーバに送る。
をサーバに送る。
【0048】ステップST12:サーバは以下の(a)
〜(c)処理を行う。
〜(c)処理を行う。
【0049】(a)初期設定。
【0050】y0 ←M (b)添え字j=1,2,…,mについて2乗計算を繰
り返す。
り返す。
【0051】yj ←(yj-1 ∧2)mod n (c)y1 ,y2 ,…,ym をクライアントに送る。
【0052】次に、クライアントはサーバから逐次送ら
れてくる、yj (j=1,2,…,
れてくる、yj (j=1,2,…,
【外11】 モリz(i)(i=1,2,…,2k-1 )に以下の様に
累積乗算して行く。但し、y0 =Mとする。
累積乗算して行く。但し、y0 =Mとする。
【0053】ステップST13:添え字i=1,2,
…,2k-1 について初期化を行う。
…,2k-1 について初期化を行う。
【0054】z(i)←1
【外12】 z((ur +1)/2)←{z((ur +1)/2)・
yw(r)}mod n そして、クライアントは以下の処理を行う。
yw(r)}mod n そして、クライアントは以下の処理を行う。
【0055】ステップST15:添え字i=2k-1 −
1,2k-1 −2,…,2,1についてこの順に、 z(i)←z(i)・z(i+1)mod n を計算する。
1,2k-1 −2,…,2,1についてこの順に、 z(i)←z(i)・z(i+1)mod n を計算する。
【0056】ステップST16:w←z(1) ステップST17:ステップST15の処理を繰り返
す。
す。
【0057】 ステップST18:z(1)←w・z(1)2 mod n ステップST19:メモリz(1)の内容が求める結果
である。
である。
【0058】以上の手順でz(1)にC=Md mod nが
得られる理由は第1実施例の場合とほぼ同様に説明でき
るが、本実施例ではべき指数を分解したブロックur が
すべて奇数であることを利用してステップST15〜S
T18の処理を行うので、同じkを用いた場合、必要な
z(i)の数が第1実施例に比べて半分で済むこと、ま
たステップST15〜ST18の手数もほぼ半分で済む
点が異なっている。第2実施例についても性能を表1,
2に示す。第2実施例の特徴は後に方式の比較の項で明
らかにする。
得られる理由は第1実施例の場合とほぼ同様に説明でき
るが、本実施例ではべき指数を分解したブロックur が
すべて奇数であることを利用してステップST15〜S
T18の処理を行うので、同じkを用いた場合、必要な
z(i)の数が第1実施例に比べて半分で済むこと、ま
たステップST15〜ST18の手数もほぼ半分で済む
点が異なっている。第2実施例についても性能を表1,
2に示す。第2実施例の特徴は後に方式の比較の項で明
らかにする。
【0059】次に本発明に基づく第3実施例を図5に示
すフローチャートに基づいて説明す
すフローチャートに基づいて説明す
【外13】 されていて、クライアントのみが各ブロックの値を知っ
ている。
ている。
【0060】ステップST21:クライアントはM,n
をサーバに送る。
をサーバに送る。
【0061】次いで、サーバは次の処理を行う。
【0062】ステップST22:初期設定を行う。
【0063】r←1,y0 (1)←M,w←M ステップST23:添え字i=1,2,…,2k −1に
ついて剰余乗算を行う。 yi (r)←{yi-1 (r)・M}mod n ステップST24:r,y1 (r),y2 (r),…,
y−(2k −1)の内容をクライアントに送る。ここで
y−x は下付きの添字がx であることを表す。
ついて剰余乗算を行う。 yi (r)←{yi-1 (r)・M}mod n ステップST24:r,y1 (r),y2 (r),…,
y−(2k −1)の内容をクライアントに送る。ここで
y−x は下付きの添字がx であることを表す。
【0064】
【外14】 ステップST28:r←r+1 ステップST29:次のようにy0 (r)を再設定して
ステップST23に戻る。
ステップST23に戻る。
【0065】w←(w∧2k )mod n y0 (r)←w そして、クライアントの処理は以下である。
【0066】ステップST25:ステップステップST
24でサーバから送られてくる、yi(r)(i=0,
1,2,…,2k −1)の値を、以下の規則で累積乗算
して行く。ただし、dr =0の場合には掛ける操作を行
なわない。
24でサーバから送られてくる、yi(r)(i=0,
1,2,…,2k −1)の値を、以下の規則で累積乗算
して行く。ただし、dr =0の場合には掛ける操作を行
なわない。
【0067】z←(z・ydr (r))mod n ステップST26:r=1ならばステップST27に進
む。
む。
【0068】ステップST27:メモリzの内容が求め
る結果である。
る結果である。
【0069】この手順によってC=Md mod nが得られ
ることは明らかである。
ることは明らかである。
【0070】次に本発明に基づく第4実施例を図6、図
7に示すフローチャートに基づいて
7に示すフローチャートに基づいて
【外15】 れクライアントに記憶されているとする。
【0071】まず、クライアントはべき乗計算に先だっ
て以下の前処理を行う。
て以下の前処理を行う。
【0072】ステップST31:n未満の(2k −1)
個の乱数ri (i=1,2,…,2k−1)を生成す
る。
個の乱数ri (i=1,2,…,2k−1)を生成す
る。
【0073】ステップST32:次の(7)式で定義さ
れるRを計算する。
れるRを計算する。
【0074】
【数5】 ステップ33:Rの法nにおける逆数R-1を計算する。
定義からRとR-1は次の(8)式を満たす。
定義からRとR-1は次の(8)式を満たす。
【0075】 (R・R-1)mod n=1 …(8) ステップST34:クライアントはM,nをサーバに送
る。
る。
【0076】そして、サーバは以下の処理を行う。
【0077】ステップST35:初期設定。
【0078】y0 ←M
【外16】 yj ←yj-1 ∧2k mod n(注意:記号a∧bはaのb
乗を表す)
乗を表す)
【外17】 次いで、クライアントはサーバから逐次送られてくる、
yj (j=1,2,…
yj (j=1,2,…
【外18】 積乗算して行く。但し、y0 =Mとし、また、dj =0
に対してはyj は掛けない。
に対してはyj は掛けない。
【0079】ステップST38:添え字i=1,2,
…,2k −1について初期化する。
…,2k −1について初期化する。
【0080】z(i)←ri
【外19】 。
【0081】z(dj )←{z(dj )・yj }mod n ステップST40:z(i)(i=1,2,…,2k −
1)をサーバに送る。
1)をサーバに送る。
【0082】その後、サーバは送られたz(i)の値を
メモリw(i)にコピーし以下の処理を行う。
メモリw(i)にコピーし以下の処理を行う。
【0083】ステップST41:添え字i=2k −2,
2k −3,…,2,1についてこの順に、 w(i)←{w(i)・w(i+1)}mod n を計算する。
2k −3,…,2,1についてこの順に、 w(i)←{w(i)・w(i+1)}mod n を計算する。
【0084】ステップST42:ステップST41のス
テップをもう一度繰り返す。
テップをもう一度繰り返す。
【0085】ステップST43:w(1)の内容をクラ
イアントに送る。
イアントに送る。
【0086】ステップST44:クライアントはサーバ
から受け取ったw(1)の値をz(1)にコピーし、 z(1)←{z(1)・R-1}mod n を計算し最終結果をz(1)に得る(ステップST4
5)。
から受け取ったw(1)の値をz(1)にコピーし、 z(1)←{z(1)・R-1}mod n を計算し最終結果をz(1)に得る(ステップST4
5)。
【0087】この手順は第1実施例を基本形としてい
る。両者の相違点は第1実施例ではクライアントが行っ
ているステップST5,ST6の処理を、本実施例では
ステップST41〜ST43においてサーバに行わせて
いる点である。但し、z(i)の値からべき指数に関す
る情報がサーバに漏れないように、ステップST38の
初期化に乱数を掛け込んでいる。またステップST43
を終了した段階でクライアントが受け取った値は最終結
果のR倍である。これを補正する為にステップST44
では受信結果にRの逆数R-1を掛けている。ステップS
T33でRの逆数R-1を予め計算してあるのでステップ
ST44の処理は剰余乗算1回の手間で完了する。
る。両者の相違点は第1実施例ではクライアントが行っ
ているステップST5,ST6の処理を、本実施例では
ステップST41〜ST43においてサーバに行わせて
いる点である。但し、z(i)の値からべき指数に関す
る情報がサーバに漏れないように、ステップST38の
初期化に乱数を掛け込んでいる。またステップST43
を終了した段階でクライアントが受け取った値は最終結
果のR倍である。これを補正する為にステップST44
では受信結果にRの逆数R-1を掛けている。ステップS
T33でRの逆数R-1を予め計算してあるのでステップ
ST44の処理は剰余乗算1回の手間で完了する。
【0088】なお、本実施例のステップST31〜ST
33はMが定まる前に行えるので、クライアントのCP
Uの空き時間を利用して予め計算しておける。そこで、
事前には行えないステップST34以降にクライアント
が行う乗算回数を、第1実施例のクライアントの乗算回
数と比較すると、本実施例の計算量の方が減っている。
通信時間を無視し、サーバが十分高速であるという仮定
の下では、本実施例は第1実施例よりも処理時間を短縮
できる。
33はMが定まる前に行えるので、クライアントのCP
Uの空き時間を利用して予め計算しておける。そこで、
事前には行えないステップST34以降にクライアント
が行う乗算回数を、第1実施例のクライアントの乗算回
数と比較すると、本実施例の計算量の方が減っている。
通信時間を無視し、サーバが十分高速であるという仮定
の下では、本実施例は第1実施例よりも処理時間を短縮
できる。
【0089】さて、次に本発明に基づく第5実施例を図
8,図9に示すフローチャートに基づいて説明する。本
実施例は第2実施例を基本形としており、第4実施例と
同様の変形を加えている。本実施例によれば4つの実施
例の内最もクライアントの計算量を削減できる。ここで
ステップST51〜ST53の計算量は比較に含めてい
ないことに注意する必要がある。
8,図9に示すフローチャートに基づいて説明する。本
実施例は第2実施例を基本形としており、第4実施例と
同様の変形を加えている。本実施例によれば4つの実施
例の内最もクライアントの計算量を削減できる。ここで
ステップST51〜ST53の計算量は比較に含めてい
ないことに注意する必要がある。
【0090】
【外20】 出されていてクライアントのみがそれを記憶している。
【0091】まず、クライアントはべき乗計算に先だっ
て以下の前処理を行う。
て以下の前処理を行う。
【0092】ステップST51:n未満の2k-1 個の乱
数ri (i=1,2,…,2k-1 )を生成する。
数ri (i=1,2,…,2k-1 )を生成する。
【0093】ステップST52:次式で定義されるRを
計算する。
計算する。
【0094】
【数6】 ステップST53:(R・R-1)mod n=1を満たすR
-1を求める。
-1を求める。
【0095】ステップST54:クライアントはM,n
をサーバに送る。
をサーバに送る。
【0096】次いで、サーバは以下の処理を行う。
【0097】ステップST55:初期設定。
【0098】y0 ←M ステップST56:添え字j=1,2,…,mについて
2乗計算を繰り返す。
2乗計算を繰り返す。
【0099】yj ←(yj-1 ∧2)mod n ステップST57:y1 ,y2 ,…,ym をクライアン
トに送る。
トに送る。
【0100】そして、クライアントはサーバから逐次送
られてくる、yj (j=1,2,…
られてくる、yj (j=1,2,…
【外21】 z(i)(i=1,2,…,2k-1 )に以下の様に累積
乗算して行く。但し、y0 =Mとする。
乗算して行く。但し、y0 =Mとする。
【0101】ステップST58:添え字i=1,2,
…,2k-1 についてz(i)の初期化を行う。
…,2k-1 についてz(i)の初期化を行う。
【0102】z(i)←ri
【外22】 z((ur +1)/2)←{z((ur +1)/2)・
yw(r)}mod n ステップST60:メモリz(i)(i=1,2,…,
2k-1 )の値をサーバに送る。
yw(r)}mod n ステップST60:メモリz(i)(i=1,2,…,
2k-1 )の値をサーバに送る。
【0103】その後、サーバは受け取った値をメモリg
(i)(i=1,2,…,2k-1 )にコピーし、以下の
処理を行う。
(i)(i=1,2,…,2k-1 )にコピーし、以下の
処理を行う。
【0104】ステップST61:添え字i=2k-1 −
1,2k-1 −2,…,2,1についてこの順に、 g(i)←{g(i)・g(i+1)}mod n を計算する。
1,2k-1 −2,…,2,1についてこの順に、 g(i)←{g(i)・g(i+1)}mod n を計算する。
【0105】ステップST62:v←g(1) ステップST63:ステップST61の処理を繰り返
す。
す。
【0106】ステップST64:g(1)←(v・g
(1)2 )mod n ステップST65:g(1)の値をクライアントに送
る。
(1)2 )mod n ステップST65:g(1)の値をクライアントに送
る。
【0107】ステップST66:クライアントはサーバ
から受け取ったg(1)の値をZ(1)にコピーし、 z(1)←{z(1)・R-1}mod n を計算し最終結果をz(1)に得る。
から受け取ったg(1)の値をZ(1)にコピーし、 z(1)←{z(1)・R-1}mod n を計算し最終結果をz(1)に得る。
【0108】次に、第1実施例から第7実施例における
処理量及びメモリ量に関する比較を以下の表1に示す。
但し、実施例6と実施例7では、H={1,−1,2,
−2},K=[b/3]の場合を取りあげた。
処理量及びメモリ量に関する比較を以下の表1に示す。
但し、実施例6と実施例7では、H={1,−1,2,
−2},K=[b/3]の場合を取りあげた。
【0109】次に、本発明に基づく第6の実施例を図1
0に示すフローチャートに基づいて説明する。本実施例
においてはべき指数dの分解を以下のように行う。
0に示すフローチャートに基づいて説明する。本実施例
においてはべき指数dの分解を以下のように行う。
【0110】
【数7】 但し、hj ∈H={α1 ,α2 ,…,αt },0≦kj ≦
kなる整数。すなわち個々のdj をdj =hj kj mod
b なるhj とkj の積に分解して表す。このようなべき
指数の分解の一例は、文献:E.Brickell, 他:"Fast Ex
ponentiation with Precomputation",Proc.of EUROCRIP
T'92, pp.193-201" にて述べられている。具体的には、 (1) H={1,-1}, K=「(b-1)/2 」。尚、記号「a」は
a以上の最小整数を表わす。
kなる整数。すなわち個々のdj をdj =hj kj mod
b なるhj とkj の積に分解して表す。このようなべき
指数の分解の一例は、文献:E.Brickell, 他:"Fast Ex
ponentiation with Precomputation",Proc.of EUROCRIP
T'92, pp.193-201" にて述べられている。具体的には、 (1) H={1,-1}, K=「(b-1)/2 」。尚、記号「a」は
a以上の最小整数を表わす。
【0111】(2) H={1,-1,2,-2},K=[b/3] 、但し、
bは奇数。尚、記号[a]はa以下の最大の整数を表わ
す。
bは奇数。尚、記号[a]はa以下の最大の整数を表わ
す。
【0112】はそのような分解の例である。
【0113】ステップST61:M,n の送信 クライアントはM.n をサーバに送る。
【0114】ステップST62:サーバの演算 サーバは以下の式により表現される全てのyij(0≦ i≦
1-1, 1≦ j≦t )を計算し、結果をクライアントに送
る。
1-1, 1≦ j≦t )を計算し、結果をクライアントに送
る。
【0115】yij={M>(αj bi )}mod n (0≦
i≦1-1, 1≦ j≦t ) ステップST63:クライアントの演算 クライアントはサーバから逐次送られてくるyij(0≦ i
≦1-1,1 ≦ j≦t )に対し、M>(hi bi )mod n (0
≦ i≦1-1)の値を選択する。選択される値は、同じ第1
添え字 iをもつ t個のyijの中から高々1つであり、合
計でも高々1個である。第1添え字 iに対し、選択され
た値をyi*と書くことにする。
i≦1-1, 1≦ j≦t ) ステップST63:クライアントの演算 クライアントはサーバから逐次送られてくるyij(0≦ i
≦1-1,1 ≦ j≦t )に対し、M>(hi bi )mod n (0
≦ i≦1-1)の値を選択する。選択される値は、同じ第1
添え字 iをもつ t個のyijの中から高々1つであり、合
計でも高々1個である。第1添え字 iに対し、選択され
た値をyi*と書くことにする。
【0116】次に、以下の計算を実行して所望の値Sを
求める。
求める。
【0117】
【数8】 但し、
【数9】 上記のz(u)はki =j であるyi*を全ての i(0≦ i
≦1-1)について累積した結果である。
≦1-1)について累積した結果である。
【0118】z(j)(1≦ j≦k)の値を個別にメモリに格
納した後、べき乗積を実行する場合には、ステップST
63は以下のステップに分解される。
納した後、べき乗積を実行する場合には、ステップST
63は以下のステップに分解される。
【0119】(a) メモリz(j)(j=1,2,…,k) への累積 クライアントは添え字j=1,2,…, kについてメモリz
(j) を1に設定し、さらに添え字i=0,1,2,…, l-1につ
いて累積乗算を行う。
(j) を1に設定し、さらに添え字i=0,1,2,…, l-1につ
いて累積乗算を行う。
【0120】 z( ki )={z( ki ) ・yi*・mod n (b) クライアントは添え字j=K-1, K-2, …,2,1につい
てこの順に、以下の計算を行う。
てこの順に、以下の計算を行う。
【0121】z(j) ={z(j) ・z(j+1)}mod n (C) クライアントは(b) の計算をもう一度繰り返す。メ
モリz(1) の内容が求める結果である。
モリz(1) の内容が求める結果である。
【0122】この第6の実施例では、サーバに依頼する
計算と通信量が第1の実施例および第2の実施例より多
く、第3の実施例よりも少ない。逆に、クライアントの
乗算回数は第1・第2の実施例よりも少なく、第3の実
施例よりも多い。このため、第1・第2の実施例と比較
して、サーバの処理能力と通信速度がより大きく、クラ
イアントの処理能力がより小さい場合に第6の実施例の
手順は有効となる。
計算と通信量が第1の実施例および第2の実施例より多
く、第3の実施例よりも少ない。逆に、クライアントの
乗算回数は第1・第2の実施例よりも少なく、第3の実
施例よりも多い。このため、第1・第2の実施例と比較
して、サーバの処理能力と通信速度がより大きく、クラ
イアントの処理能力がより小さい場合に第6の実施例の
手順は有効となる。
【0123】次に、前記第6の実施例のうち、クライア
ントがステップST63にて実行するべき乗積計算をサ
ーバに依頼する第7の実施例を説明する。図11にフロ
ーチャートを示した。クライアントのべき指数の分解は
第6の実施例と同様に行われているものとする。
ントがステップST63にて実行するべき乗積計算をサ
ーバに依頼する第7の実施例を説明する。図11にフロ
ーチャートを示した。クライアントのべき指数の分解は
第6の実施例と同様に行われているものとする。
【0124】 ステップST71:クライアントの事前処理 まず、クライアントはK個の乱数rj (1≦ j≦k)を発生
する。但し、乱数rjはn未満の整数である。さらに、
次式で定義される値RとR-1を求める。
する。但し、乱数rjはn未満の整数である。さらに、
次式で定義される値RとR-1を求める。
【0125】
【数10】 R・R-1=1 mod n 以上の処理はべき乗計算Md mod n を実行する以前に行
う。例えばクライアント内のCPU のアイドル時間を利用
してこの処理を行い、結果を幾つかクライアント内のメ
モリに保存しておく。
う。例えばクライアント内のCPU のアイドル時間を利用
してこの処理を行い、結果を幾つかクライアント内のメ
モリに保存しておく。
【0126】ステップST72:M,n の送信 クライアントはM,n をサーバに送る。
【0127】ステップST73:サーバの演算 サーバは以下の式により表現される全てのyij(0≦ i≦
1-1, 1≦ j≦t)を計算し、結果をクライアントに送る。
1-1, 1≦ j≦t)を計算し、結果をクライアントに送る。
【0128】yij={M>(αj bi )}mod n (0≦ i
≦1-1, 1≦ j≦t) (1*t)個のデータであるyijの送信においては、クライ
アント側でデータの識別ができるように送信の順序を規
定しておく。
≦1-1, 1≦ j≦t) (1*t)個のデータであるyijの送信においては、クライ
アント側でデータの識別ができるように送信の順序を規
定しておく。
【0129】 ステップST74:クライアントによる累積乗算 クライアントはサーバから逐次送られてくるyij(0≦ i
≦1-1, 1≦ j≦t)に対し、M>(hi bi )mod n (0≦
i≦1-1)の値を抽出する。抽出される値は、同じ第1添
え字 iをもつ t個のyijの中から高々1つずつであり、
合計でも高々1個である。第1添え字 iに対し、選択さ
れた値をyi*と書く事にする。
≦1-1, 1≦ j≦t)に対し、M>(hi bi )mod n (0≦
i≦1-1)の値を抽出する。抽出される値は、同じ第1添
え字 iをもつ t個のyijの中から高々1つずつであり、
合計でも高々1個である。第1添え字 iに対し、選択さ
れた値をyi*と書く事にする。
【0130】クライアントは添え字j=1,2,…, Kについ
てメモリz(j) をrj に設定し、さらに添え字i=0,1,2,
…,1-1について以下の累積乗算を行う。
てメモリz(j) をrj に設定し、さらに添え字i=0,1,2,
…,1-1について以下の累積乗算を行う。
【0131】z(ki )=z(ki )・yi* mod n 以上により得られたz(j) (1≦ j≦k)をサーバに送る。
【0132】 ステップST75:サーバによるべき乗積計算 サーバは以下のwを求め、クライアントに送る。
【0133】
【数11】 ステップST76:クライアントによる後処理 クライアントは以下の計算により所望の値Sを求める。
【0134】S=(wR-1)mod n
【表1】 ただし、表1において、以下のように定義する。
【0135】(前処理1)=(2k-1 個の乱数生成)+
(剰余乗算(2k+1 −4回)+(逆数計算1回) (前処理2)=(2k-1 個の乱数生成)+(剰余乗算
(2k )回)+(逆数計算1回) (前処理3)=([b/3]個の乱数生成)+(剰余乗
算(2[b/3]−2)回)+(逆数計算1回) 記号[a]はa以上で最小の整数を表す。
(剰余乗算(2k+1 −4回)+(逆数計算1回) (前処理2)=(2k-1 個の乱数生成)+(剰余乗算
(2k )回)+(逆数計算1回) (前処理3)=([b/3]個の乱数生成)+(剰余乗
算(2[b/3]−2)回)+(逆数計算1回) 記号[a]はa以上で最小の整数を表す。
【0136】この表で使用されている記号の定義をまと
める。mはべき指数dのサイズである。すなわち、m=
[log2 d]+1 である。実施例1から5におけるkは2進
表現のべき指数を分割したブロックサイズ(ビット数)
である。実施例6と7におけるbはべき指数dを分割す
る基数(dをb進数表現する)であり、lはb進数表現
したときのdの桁数である。すなわち、l(エル)=[l
ogb d]+1 である。さらに、実施例6と7におけるExp
(b)はb乗剰余計算に必要な剰余乗算の回数を表し、Inv
は逆数計算に要する処理時間を剰余乗算1回に要する
処理時間で割った換算値を表す。
める。mはべき指数dのサイズである。すなわち、m=
[log2 d]+1 である。実施例1から5におけるkは2進
表現のべき指数を分割したブロックサイズ(ビット数)
である。実施例6と7におけるbはべき指数dを分割す
る基数(dをb進数表現する)であり、lはb進数表現
したときのdの桁数である。すなわち、l(エル)=[l
ogb d]+1 である。さらに、実施例6と7におけるExp
(b)はb乗剰余計算に必要な剰余乗算の回数を表し、Inv
は逆数計算に要する処理時間を剰余乗算1回に要する
処理時間で割った換算値を表す。
【0137】そして、表1において、乗算回数はdのビ
ットパターンに応じて若干変動するが、ここでは最悪値
を示している。
ットパターンに応じて若干変動するが、ここでは最悪値
を示している。
【0138】表2にm=512の場合の具体的演算量・
メモリ量の比較を示す。ここでは簡単の為にk=5とし
て計算した。
メモリ量の比較を示す。ここでは簡単の為にk=5とし
て計算した。
【0139】RSA暗号の秘密変換に提案の方式を利用
することを想定すると、m=512がよく用いられる。
各方式のパラメータk,bを最適に選ぶ必要があるが、
ここでは簡単のためにk=5,b=33とした場合の具
体値を表2に示す。但し、実施例6と7においてExp(b)
=6, Inv=10とした。
することを想定すると、m=512がよく用いられる。
各方式のパラメータk,bを最適に選ぶ必要があるが、
ここでは簡単のためにk=5,b=33とした場合の具
体値を表2に示す。但し、実施例6と7においてExp(b)
=6, Inv=10とした。
【0140】
【表2】 ただし、表2において以下のように定義する。
【0141】(前処理1)=(31個の乱数生成)+(剰
余乗算60回)+(逆数計算1回) (前処理2)=(16個の乱数生成)+(剰余乗算32回)
+(逆数計算1回) (前処理3)=(11個の乱数生成)+(剰余乗算20回)
+(逆数計算1回) 以上の実施例ではクライアントは演算結果C=Md mod
nを外部に出さないものとして説明してきた。そして、
そのとき以上の依頼計算手続きはクライアント以外には
dに関する情報を一切漏らしていない。ただし、以上述
べた手順だけではクライアントの得た結果が正しいか否
かのチェックはしていないので、不正なサーバが所定の
値以外をクライアントに返して演算を妨害する行為に対
しては無力である。何らかの手段で演算結果が正しいこ
とを確認できると好都合である。幸いRSA暗号の変換
についてはC=Md mod nの逆変換が簡単に行えるよう
にパラメータを選ぶことができるので、依頼計算を実行
した後に結果Cを逆変換して元のMに戻ればCが正しい
ことを確認できる。このような確認計算を検算と呼ぶ。
RSA暗号で利用できる具体的な検算式として(11)
式がある。
余乗算60回)+(逆数計算1回) (前処理2)=(16個の乱数生成)+(剰余乗算32回)
+(逆数計算1回) (前処理3)=(11個の乱数生成)+(剰余乗算20回)
+(逆数計算1回) 以上の実施例ではクライアントは演算結果C=Md mod
nを外部に出さないものとして説明してきた。そして、
そのとき以上の依頼計算手続きはクライアント以外には
dに関する情報を一切漏らしていない。ただし、以上述
べた手順だけではクライアントの得た結果が正しいか否
かのチェックはしていないので、不正なサーバが所定の
値以外をクライアントに返して演算を妨害する行為に対
しては無力である。何らかの手段で演算結果が正しいこ
とを確認できると好都合である。幸いRSA暗号の変換
についてはC=Md mod nの逆変換が簡単に行えるよう
にパラメータを選ぶことができるので、依頼計算を実行
した後に結果Cを逆変換して元のMに戻ればCが正しい
ことを確認できる。このような確認計算を検算と呼ぶ。
RSA暗号で利用できる具体的な検算式として(11)
式がある。
【0142】 M=Ce mod n …(11) ここで重要なのは指数eをdに比べて十分小さく設定で
きるので(11)式は短時間で計算できる点である。
きるので(11)式は短時間で計算できる点である。
【0143】ところで、具体的な装置でクライアントが
ICカードの場合には、演算結果CはICカードから外
部に出力される場合が多いと考えられる。その場合にも
べき指数dの安全性を確保するには検算がかなり有効で
ある。しかし、dに関する情報をクライアント外部に漏
らさない目的に対しては、検算の効果は100%でな
い。そこで、検算を行って正しい結果でない場合には、
その回数を数えて記憶しておき一定回数以上誤った場合
には警報を鳴らして所有者に知らせるといった方法を併
用することが望ましい。
ICカードの場合には、演算結果CはICカードから外
部に出力される場合が多いと考えられる。その場合にも
べき指数dの安全性を確保するには検算がかなり有効で
ある。しかし、dに関する情報をクライアント外部に漏
らさない目的に対しては、検算の効果は100%でな
い。そこで、検算を行って正しい結果でない場合には、
その回数を数えて記憶しておき一定回数以上誤った場合
には警報を鳴らして所有者に知らせるといった方法を併
用することが望ましい。
【0144】これまで依頼計算についてRSA暗号の復
号変換を念頭に置いて説明してきたが、本発明の適用は
必ずしもRSA暗号に限定されず、べき指数をクライア
ント以外に秘匿したい様々な応用に対して適用可能であ
る。RSA暗号以外の適用例としてDiffieとHelmanが提
案している鍵共有プロトコルが考えられる。なお、クラ
イアントの具体例としてはICカードが挙げられるが、
本発明の適用は必ずしもICカードに限定されるもので
もない。サーバや通信回線も本発明の主旨を越えない範
囲であれば、具体的実現法を限定するものではない。
号変換を念頭に置いて説明してきたが、本発明の適用は
必ずしもRSA暗号に限定されず、べき指数をクライア
ント以外に秘匿したい様々な応用に対して適用可能であ
る。RSA暗号以外の適用例としてDiffieとHelmanが提
案している鍵共有プロトコルが考えられる。なお、クラ
イアントの具体例としてはICカードが挙げられるが、
本発明の適用は必ずしもICカードに限定されるもので
もない。サーバや通信回線も本発明の主旨を越えない範
囲であれば、具体的実現法を限定するものではない。
【0145】
【発明の効果】以上説明したように、本発明では、べき
指数を秘密とするべき乗計算を、補助装置の助けを借り
つつ、しかもべき指数を補助装置など外部装置に漏らす
こと無く効率よく計算できるという効果が得られる。
指数を秘密とするべき乗計算を、補助装置の助けを借り
つつ、しかもべき指数を補助装置など外部装置に漏らす
こと無く効率よく計算できるという効果が得られる。
【図1】本発明が適用される依頼計算装置の構成を示す
ブロック図である。
ブロック図である。
【図2】ICカード利用システムを示す構成図である。
【図3】本発明の第1実施例の動作を示すフローチャー
トである。
トである。
【図4】本発明の第2実施例の動作を示すフローチャー
トである。
トである。
【図5】本発明の第3実施例の動作を示すフローチャー
トである。
トである。
【図6】本発明の第4実施例の動作を示すフローチャー
トの第1の分図である。
トの第1の分図である。
【図7】本発明の第4実施例の動作を示すフローチャー
トの第2の分図である。
トの第2の分図である。
【図8】本発明の第5実施例の動作を示すフローチャー
トの第1の分図である。
トの第1の分図である。
【図9】本発明の第5実施例の動作を示すフローチャー
トの第2の分図である。
トの第2の分図である。
【図10】本発明の第6実施例の動作を示すフローチャ
ートである。
ートである。
【図11】本発明の第7実施例の動作を示すフローチャ
ートである。
ートである。
1 クライアント 2 サーバ 3 通信回路 201 端末 202 リーダ・ライタ 203 ICカード
Claims (3)
- 【請求項1】 演算手段を有する主装置と演算手段を有
する1つないしは複数の補助装置から構成される依頼計
算装置において、前記依頼計算装置はべき乗剰余計算: Md mod n を実行するものであり、 前記主装置は固有の秘密情報であるべき指数dを有し、
前記主装置は前記べき指数dを2より大きな正整数bを
基数としたb進数表現: d=Σ di bi により展開した全ての係数di を保持し、 前記補助装置は、所定の底であるMと所定の法であるn
と、前記基数bを割り切る所定の整数βに依存し、前記
d及び前記係数di のいずれにも依存しない変換とし
て、Mに対しβ乗を繰り返しnで剰余をとった複数の値
を計算し、これらの計算結果を主装置に送信し、 主装置は補助装置から受信した複数の計算値と、自装置
内に保持する前記複数の係数di と前記nに依存した変
換により、べき乗剰余計算結果を主装置内に得ることを
特徴とする依頼計算装置。 - 【請求項2】 演算手段を有する主装置と演算手段を有
する1つないしは複数の補助装置から構成される依頼計
算装置において、前記主装置は固有の秘密情報を有し、
前記秘密情報に依存した秘密計算を実行するものであ
り、 前記主装置は、乱数発生手段を有し、前記秘密計算を実
行していない時点において、前記乱数発生手段により複
数の乱数を発生し、前記複数の乱数から所定の変換によ
り得られる乱数依存データを計算し、前記乱数と前記乱
数依存データを保存し、 秘密計算実行時には、前記補助装置は前記秘密情報に依
存しない所定の変換を実行して得られる第一の変換値を
前記主装置に送信し、前記主装置は前記第一の変換値に
前記乱数を作用させる所定の変換を実行して得られる第
二の変換値を前記補助装置に送信し、前記補助装置は所
定の変換により得られる第三の変換値を前記主装置に送
信し、前記主装置は第三の変換値と前記乱数依存データ
に依存した所定の変換を実行して秘密計算の実行結果を
自装置内に得ることを特徴とする依頼計算装置。 - 【請求項3】 第1項記載のべき指数dを2より大きな
正整数bを基数としたb進数表現: d=Σ di bi により展開した全ての係数di に対し、 複数の整数からなる2つの集合が規定され、前記係数d
i の全ては、前記集合のうち第一の集合の一要素と前記
集合のうち第二の集合の一要素の積に対し基数bを法と
して合同な関係を有し、 主装置は個々の係数di に対応する第一の集合の要素と
第二の集合の要素をそれぞれ対にして保持し、 補助装置は、所定の底であるMと所定の法であるnと、
前記基数bを割り切る所定の整数βと、前記第二の集合
の個々の要素に依存した複数のべき乗剰余計算を実行
し、該計算結果を前記主装置に送信し、 前記主装置は、前記補助装置から受信した計算値と、自
装置内に保持する前記複数の係数di に対応した第一の
集合の各要素と前記nに依存した変換により、べき乗剰
余計算結果を主装置内に得ることを特徴とする依頼計算
装置。
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP5068866A JPH0619393A (ja) | 1992-03-31 | 1993-03-26 | 依頼計算装置 |
Applications Claiming Priority (3)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP4-77881 | 1992-03-31 | ||
JP7788192 | 1992-03-31 | ||
JP5068866A JPH0619393A (ja) | 1992-03-31 | 1993-03-26 | 依頼計算装置 |
Publications (1)
Publication Number | Publication Date |
---|---|
JPH0619393A true JPH0619393A (ja) | 1994-01-28 |
Family
ID=26410054
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP5068866A Pending JPH0619393A (ja) | 1992-03-31 | 1993-03-26 | 依頼計算装置 |
Country Status (1)
Country | Link |
---|---|
JP (1) | JPH0619393A (ja) |
Cited By (10)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2008519303A (ja) * | 2004-11-04 | 2008-06-05 | フランス テレコム | 双線形アプリケーションの計算の安全化された委託方法 |
JP2008520145A (ja) * | 2004-11-11 | 2008-06-12 | サーティコム コーポレーション | 汎用鍵導出関数サポートのための安全インタフェース |
JP2008523641A (ja) * | 2004-12-06 | 2008-07-03 | 三菱電機株式会社 | 入力画像シーケンスを安全に処理する方法及びシステム |
JP2008177966A (ja) * | 2007-01-22 | 2008-07-31 | Mitsubishi Electric Corp | 情報処理装置及び演算方法 |
JP2008203581A (ja) * | 2007-02-21 | 2008-09-04 | Matsushita Electric Works Ltd | ネットワークシステム |
JP2011053607A (ja) * | 2009-09-04 | 2011-03-17 | Nippon Telegr & Teleph Corp <Ntt> | 代理計算依頼装置、代理計算依頼方法、代理計算依頼プログラム、記録媒体 |
JP2011513787A (ja) * | 2008-03-05 | 2011-04-28 | イルデト・コーポレート・ビー・ヴイ | ホワイトボックス実装 |
JP4786547B2 (ja) * | 2004-12-06 | 2011-10-05 | 三菱電機株式会社 | 入力画像を安全に処理する方法 |
JP2012078446A (ja) * | 2010-09-30 | 2012-04-19 | Nippon Telegr & Teleph Corp <Ntt> | 不正検知方法、秘密計算システム、計算装置、計算プログラム |
US8634562B2 (en) | 2004-11-11 | 2014-01-21 | Certicom Corp. | Secure interface for versatile key derivation function support |
-
1993
- 1993-03-26 JP JP5068866A patent/JPH0619393A/ja active Pending
Cited By (13)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP4740253B2 (ja) * | 2004-11-04 | 2011-08-03 | フランス・テレコム | 双線形アプリケーションの計算の安全化された委託方法 |
JP2008519303A (ja) * | 2004-11-04 | 2008-06-05 | フランス テレコム | 双線形アプリケーションの計算の安全化された委託方法 |
JP2008520145A (ja) * | 2004-11-11 | 2008-06-12 | サーティコム コーポレーション | 汎用鍵導出関数サポートのための安全インタフェース |
US8634562B2 (en) | 2004-11-11 | 2014-01-21 | Certicom Corp. | Secure interface for versatile key derivation function support |
JP2008523641A (ja) * | 2004-12-06 | 2008-07-03 | 三菱電機株式会社 | 入力画像シーケンスを安全に処理する方法及びシステム |
JP4877788B2 (ja) * | 2004-12-06 | 2012-02-15 | 三菱電機株式会社 | 入力画像シーケンスを安全に処理する方法及びシステム |
JP4786547B2 (ja) * | 2004-12-06 | 2011-10-05 | 三菱電機株式会社 | 入力画像を安全に処理する方法 |
JP2008177966A (ja) * | 2007-01-22 | 2008-07-31 | Mitsubishi Electric Corp | 情報処理装置及び演算方法 |
JP2008203581A (ja) * | 2007-02-21 | 2008-09-04 | Matsushita Electric Works Ltd | ネットワークシステム |
JP2011513787A (ja) * | 2008-03-05 | 2011-04-28 | イルデト・コーポレート・ビー・ヴイ | ホワイトボックス実装 |
US8670559B2 (en) | 2008-03-05 | 2014-03-11 | Irdeto Corporate B.V. | White-box implementation |
JP2011053607A (ja) * | 2009-09-04 | 2011-03-17 | Nippon Telegr & Teleph Corp <Ntt> | 代理計算依頼装置、代理計算依頼方法、代理計算依頼プログラム、記録媒体 |
JP2012078446A (ja) * | 2010-09-30 | 2012-04-19 | Nippon Telegr & Teleph Corp <Ntt> | 不正検知方法、秘密計算システム、計算装置、計算プログラム |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
US5745571A (en) | Cryptographic communications method and system | |
US7231040B1 (en) | Multiprime RSA public key cryptosystem | |
Bosselaers et al. | Integrity Primitives for Secure Information Systems: Final Ripe Report of Race Integrity Primitives Evaluation | |
EP0656709B1 (en) | Encryption device and apparatus for encryption/decryption based on the Montgomery method using efficient modular multiplication | |
US4736423A (en) | Technique for reducing RSA Crypto variable storage | |
US20090245507A1 (en) | Data processing system and data processing method | |
JP4137385B2 (ja) | 公開鍵および秘密鍵による暗号化方法 | |
EP0936776A2 (en) | A network system using a threshold secret sharing method | |
JP2008293034A (ja) | タイミング攻撃を阻止する標準化されたモジュラべき乗を計算することにより復号メカニズムを実行する方法と装置 | |
US7688973B2 (en) | Encryption apparatus, decryption apparatus, key generation apparatus, program, and method | |
JPH09230786A (ja) | データの暗号化方法及び装置 | |
US5369708A (en) | Fast server-aided computation system and method for modular exponentiation without revealing client's secret to auxiliary device | |
US6772942B2 (en) | Arithmetic circuit to increase the speed of a modular multiplication for a public key system for encryption | |
EP0502441A2 (en) | Key distribution system for distributing a cipher key between two subsystems by one-way communication | |
US6769062B1 (en) | Method and system of using an insecure crypto-accelerator | |
JPH0619393A (ja) | 依頼計算装置 | |
US6236729B1 (en) | Key recovery method and system | |
JP2003177668A (ja) | 秘密量をもった計算をスクランブルする方法 | |
JPH10500502A (ja) | 離散対数をベースとした公開キーによる暗号化方法 | |
JPH0548980B2 (ja) | ||
US5761310A (en) | Communication system for messages enciphered according to an RSA-type procedure | |
JP2004054128A (ja) | 暗号化装置 | |
KR100340102B1 (ko) | 알에스에이 공개키 암호 고속화 장치 및 방법 | |
CN1985458B (zh) | 增强的自然蒙哥马利指数掩蔽和恢复的方法和装置 | |
US7382875B2 (en) | Cryptographic method for distributing load among several entities and devices therefor |