JPH10511778A

JPH10511778A - ２つの処理装置の間における秘密鍵による通信プロトコルの実行方法

Info

Publication number: JPH10511778A
Application number: JP8520265A
Authority: JP
Inventors: ムライヒ，ダビッド; ナカシェ，ダビッド
Original assignee: ゲンプリ
Priority date: 1994-12-28
Filing date: 1995-12-26
Publication date: 1998-11-10
Also published as: AU4451696A; EP0800691B1; DE69509127T2; CA2208983A1; WO1996020461A1; DE69509127D1; US6226382B1; FR2728981B1; EP0800691A1; ATE179009T1; ES2132764T3; FR2728981A1

Abstract

(57)【要約】２つの処理装置の間の秘密鍵によるプロトコルを実行する方法であって、該処理装置の少くとも１つは可搬式の記憶用媒体である。この装置は例えばモジュール式の多重化のような操作を実行する見地からモジュール式の演算操作を実行するデジタル処理回路に適合させられ、処理回路は秘密鍵暗号化作用を実行するために用いられ、該秘密鍵暗号化作用は、一連の反転可能の操作から成り、２つの操作、すなわちモジュール式演算操作と２値式論理操作、の少くとも１つの組合せを具備し、該操作は、送信されるべき通信文を暗号化または署名付与するため、または受信した通信文を解読するために適用される。

Description

【発明の詳細な説明】２つの処理装置の間における秘密鍵による通信プロトコルの実行方法本発明は、少なくとも１つがチップカードのような可搬式記憶媒体である２つの処理装置の間で通信プロトコルを使用するための方法を目的とする。現在、情報の秘密性は、最大の関心事の１つであることを続けている。情報は、評価が時に困難である場合があるにしても、形態の如何を問わず固有の価値を有していることは明らかであるようにみえる。かくして、一企業ひいては一国家の富は、大部分が、その過去、現在さらには将来におけるその活動を凝縮したものを収納している増々増大する巨大な書類及び電子文書の中に存在している。その保有者が保護を裏づけていた紙の書類は、アクセスができるかぎり困難となっている場所に隠されてきた。電子郵便及びファイリングの拡張は、問題を一変させ、同じ自己防衛の必要性に応えることのできる解決法を探究させる誘因となっている。この分野においてもたらされた回答は、人物の一群により、或る一定の瞬間に秘密情報を分割することにある。今日までに使用されてきた方法は、基礎演算（２進加算、シフト、順列）を行なえるいかなる装置上ででも実行できる単純な演算に基づくものである。これらの方法は、その性質自体のため、難点が発見し難くしかも致命的な欠点の無い論理を有する１つの機械を作るのに、きわめてち密で時間のかかる設計作業を必要とする。システムの安全保護全体が基づいている秘密は、反対の場合には実際に開示されることになり、この開示はこのときこのシステムの破綻をひき起こすことになる。従って、効果的なプロトコルの構築は、時間的にも資源的にもきわめて重い投資である。要するに、最大限の適合可能性の追求は、処理すべき情報量が大きいだけになお一層性能の制限を導く。本発明はこの問題を解決し、特に、システムの信頼性がこのハードウェアが保守する情報の秘密性にのみ基づいているという事実によりひき起こされる製造上の制約条件を除去することを可能にするものである。本発明に従うと、この制約条件を一方では保守される秘密にそして他方では行なわれる処理すなわちプロトコル自体に分布させることが提案されている。この目的で、本発明に従うと、この方法は、公開鍵による暗号通信プロトコル（DH，E1 Gamal，Schnorr，Fiat-Shamir等）の枠内で複雑な演算（例えばモジュール式演算を使用する操作等）の実施に当初割当てられた資源（物質的又は論理的）の利用により凍結された秘密鍵による暗号通信プロトコルを実現することを可能にする。複雑な演算（例えばモジュール式計算など）を実行できるようにする計算資源の備わった装置が今まで知られてきており、例としては、Thomson社のST16CF54 回路、Philips社の83C852/5又はSLE44CP200といった回路を挙げることができる。本発明に従うと、このような資源は、適切な形で、すなわちわずかな時間しかとらずしかも処理対象の情報の変形という点でデータに対する効果が高いような演算を利用することによって、利用される。原理は、装置の性質（単なる8051又は6805形式のマイクロ制御装置、80×86又は680×０系統のプロセッサ、進化したプロセッサ（PENTIUM、Alphaチップ、SUN又はRISC）及びパラレルプロセッサ（例えば HYPERCUBE機）の如何にかかわらず、暗証を再構築できる人物のみが復号できる暗号化された通信文（メッセージ）を得るべく秘密鍵と普通の文字での情報を組合わせることによって、装置自体の心臓部と複雑な演算専用の資源を同時に活用する演算を組合わせることにある。このように、本発明は、モジュール式計算が例えば80ビット、160ビット又は 512ビット又はそれ以上の大きな数に関するものとなる可能性があり、しかも２つの演算の組合せしか必要としない安全保護性のきわめてすぐれたシステムを提案する。本発明は、より特定的には、少なくとも１つが可搬式記憶媒体である２つの処理装置の間の秘密鍵によるプロトコルの実用方法であって、モジュール式乗算の演算を使用するモジュール式計算形式の演算を実行するに適したデジタルの処理回路を装置に設置する段階、１つはモジュール式計算形式のもので他の１つは２値論理に関するものである２つの演算の組合せを少なくとも含む一連の可逆的演算から成る秘密鍵による暗号化関数を使用するためにこの処理回路を利用する段階、および、暗号化又は署名のため伝送されるべきメッセージに対して、又は復号するため受理したメッセージに対してこの関数を適用する段階、を含むことを主たる特徴とする方法実現することを目的としている。あらゆる長さのメッセージを処理するためには、あらゆる処理の前にＮビットのｑ個のブロックｘへの分割を行なう。本発明の他の１つの目的によれば、秘密鍵による暗号化関数は、モジュール式乗算を使用する順列であるものと排他的論理和論理演算という２つの演算の１つの組合せを含み、このようにして、ｆは、であるものであり、ここにｘは、メッセージのＮビットの１ブロックを表わし、Ｋ₁及びＫ₂は、Ｎ個のビット上の第１及び第２の秘密鍵を表わし、ｎは、Ｎビットの奇数の数を表わし、＊は、モジュロｎ乗算の演算を表わしている。本発明の他の１つの形態によれば、使用者は、Ｋ₁≠Ｋ₂又はＫ₁＝Ｋ₂を選択することができる。本発明の他の１つの形態によれば、１つの装置はメッセージを送る際に、反復的に関数ｆを各ブロックｘ_iに対して適用することから成る第１の処理をメッセージ上で実施する。好ましくは、４以上の反復数ｐを用いる。このようにして、第１の実施形態によれば、Aj及びAkは互いに下記のプロトコルに従い通信する。プロトコルは、 ● 装置Ajは、予めＮビットの（ｑ＋１）個のブロックに分割されたメッセージＭの各々のブロックｘを、メッセージの暗号化されたである）となるような形で暗号化し、 ● 装置は、装置Akに対して（ｑ＋１）ｙ個のブロックを送り、 ● 装置Akは各ｙについて、ｙを復号しｘを得るようにブロックｙれたもののＮビットのブロックを表わす）となるようなｆの逆関数である。ベき数ｐは、f^p（x）＝ f(f(f(f(x))))の要領で関数ｆ及びｇをｐ回適用することを表わしている。従って関数ｆを反復的に適用する。提案された反復回数は、プロトコルの安全保障性を保証する。実際的には、メッセージのハッシングは以下の段階を行なうことから成る。メッセージの第１のブロックｘ₁の暗号化されたものｙ_iを計算し、この場合 y₁＝E(x₁)であり、メッセージのブロックｘ_iの残りの部品について y_i＝ E(x_i して最後のブロックをとる。他の１つの実施形態によれば、装置Aj及びAkが互いに通信し合う場合、装置Aj は予めメッセージをＮビットのｑ＋１個のブロックに分割し、ブロックを２つのレジスタの中に入れる。１つのメッセージのブロックｘ_iが第１のレジスタ内に入れられ、次のブロックｘ_i+1は第２のレジスタの中に入れられる。装置Ajは、１つのメッセージを送った時点で、下記の形の暗号化関数ｆによりメッセージの暗号化を行なう。暗号化関数は： ● f(x_i，x_i+1)＝ y_i，y_i+1で ● E(x_i，x_i+1)＝ f^p（x_i，x_i+1） ● y_i＝ x_i+1 である。装置は、装置Akへ（ｑ＋１）ｙ個のブロックを送る。装置Akは、各々のブロックｙ_iについて、(y_i，y_i+1)を復号し(x_i，x_i+1)を得る態様でD(y_i，y_i+1)＝ g^p(y_i，y_i+1)の演算を行ない、関数ｇはｆの逆関数であり、この関数は g(y_i，ｙ_i+1)＝x_i，x_i+1、 x_i+1＝y_i、および、により定義される。装置Akはこのようにしてメッセージを再構築する。復号を可能にする逆方向の応用は、順方向の応用と全く同じ形式のものである。従って、上述のように複数の関数ｆを適用することにより、対称的な暗号化システムを構築することが可能である。この場合、反復数は、このスキーマに第１の解決法と同等の安全保護を与えるように８以上の数として選択されることになる。ブロックｘの暗号化及び暗号化されたもののブロックｙの復号を可能にするこの関数に基づくプロトコルは、下記の通りである。このプロトコルは： y、ここに、ｇは、以上で定義づけしたとおりｆの逆関数であり、ｙは、暗号化されたもののＮビットのブロックを表わす。前述の暗号化関数は、任意の長さのメッセージをハッシングするために利用できるであろう。１つのメッセージのハッシングは、ハッシングされたメッセージ値を表わす最後の暗号化された値しか保存しないように、暗号化されたブロック毎に値を組合わせることによって行なわれる。実際的には、メッセージのハッシングは、次の段階を実施することから成る。 E(x_i，x_i+1)＝f⁸(x_i，x_i+1)であるとして、メッセージの最初の２つのブロック（ｘ₁，ｘ₂）の暗号化されたもの（ｙ₁ ，ｙ₂）を計算し、この場合y₁，y₂＝E(x_l，x₁)であり、メッセージのブロック対(x_i，x_i+1)の残りの部分について算を行ない、ハッシングされたメッセージ値として最後のブロックをとる。暗号化するか又はハッシングすべきモジュロ、鍵及びブロックのビット長Ｎは、好ましくは、使用する装置に応じて、80ビット又は 160，512，640，1024又はそれ以上である。モジュロとして利用される数は奇数となる。好ましくは同様に、数ｎ＝２^N−１を利用する。可搬式機器は、チップカード又はPCMCIAカード、バッジ、非接触型カード又はその他全ての安全保障のモジュールを備えた機器となる。交換される信号は、電気信号又は赤外線信号又はラジオ波であることが考えられる。本発明のその他の特徴及び利点は、図面を参照しながら、全く制限的意味をもたない例として示される記述からより明らかになるであろう。図面において、第１図は、本発明による方法を使用する装置の概念的な図を表わす。第２図は、１つのメッセージの暗号化／復号段階中に、本発明によるデジタル処理回路を利用した他の１つの装置Akと装置Ajの間で伝送されるデータを表わす。この記述へ下記の部分においては、例として、単純化を期してチップカードの場合が処理装置の一例として取り上げられる。ここで提案されている本発明によれば、各々のチップカードは、処理ユニットの CPU11、通信インターフェイス10、ランダムアクセスメモリ(RAN)及び／又は読出し専用メモリ(ROM)14及び／又は消去可能プログラム可能ROM(一般には電気的消去・書込み可能 PROM)(EPROM又はEEPROM)で構成されている。各カードは、提案される手順に応じてメッセージの暗号化及び／又は復号を行なうことができる。チップカードのメモリ ROM14及び／又はユニットの CPU11は、大きい数字に対する算術演算特に乗算、反転及びモジュール式低減を迅速に行なうことを可能にする。既知の要領で、これらの演算の幾つかをまとめることを考えることができる（例えば、モジュール式低減を直接乗算に組み込むことができる）。 DESのようなアルゴリズムの実行の場合と同様に、RAMメモリは、暗号化しなければならないメッセージＭのＮ個のビット上にブロックｘを包含する。E(E)PROM 記憶装置15は、キーＫ，Ｋ₁及びＫ₂を包含する。ユニットの CPU11は、既知の態様で、アドレス及びデータバス16、通信インターフェイス10を介して、メモリ13，14及び15の読取り及び書込み演算を指令する。各々のチップカードは、物理的保護17により外界から保護されている。これらの保護は、無許可のあらゆるエンティティが秘密鍵Ｋを得るのを妨げるに充分なものでなければならぬ。これに関連して今日最も使用されている技術は安全保障のモジュール内へチップを内蔵することそして温度、光ならびに異常クロック周波数及び電圧の変動を検出することのできる装置をチップに備えることである。メモリアクセスのスクランブルのような、特殊ではあるが既知のものである設計技術も同様に利用される。チップカードと同じ機能を有する安全保障のモジュールを利用する装置は、同様の態様で暗号化及び復号の演算を実行することができるであろう。提案される本発明の一般的枠内において、通常公開鍵暗号通信形式の演算に割当てられた資源を用いる対称な暗号化アルゴリズムの使用は、以下に記す処理を実行し、カードを本発明による他の１つのカードであることが可能な確認装置の間で少なくとも下記の信号を交換することにより実行される。この信号とは：予め、長さＬのメッセージの暗号化を行なう装置は、このメッセージを分割してＮビットの（ｑ＋１）個のブロックを得る。ｒ＜ＮでＬ＝（ｑ＊Ｎ＋ｒ）ビットである場合、装置はメッセージをｑ＋１個のブロック、すなわち、長さＮビットのブロックｑ個とｒビットのブロック１個に分割する。Ｎビットのｑ＋１個のブロックを得るように（ｑ＋１）１番目のブロックを零で補完し、次に、下記の演算を行なうことにより各ブロックｘ_iを暗号化する。この演算とは：ＫはＮビット上の秘密鍵を表わし、ｎはＮビットの奇数の数を表わし、その後、装置は、復号を行なう装置へ暗号化されたものの（ｑ＋１）ｙ_i個のブロックを送る。メッセージの復号を行なう装置は、各々のブロックｙ_iについて下記の計算を行なう。この計算は： mod n＝ x_i、であり、最後に装置はメッセージＭ＝ｘ₁｜ｘ₂｜．．．｜ｘ_i+1を再構築する。本発明の第２の変形形態は、暗号化すべきメッセージのブロックを含むＮビットの２つのレジスタ上で動作する公開鍵暗号通信に通常割当てられた資源を用いる、対称的暗号化の第２の実施形態を提案することを目的とする。長さＬの１つのメッセージの暗号化を実行する装置は、前述のとおり切断を行なう。ｒ＜Ｎで長さＬ＝（ｑ＊Ｎ＋ｒ）ビットのメッセージについて、この装置はこのメッセージをｑ＋１個のブロックすなわち、長さＮビットのブロックｑ個とｒビットのブロック１個に切断する。この装置は、零で（ｑ＋１）ｉ番目のブロックを補完し、次に、下記の計算を行なうことにより各ブロックｘ_i暗号化する。この計算は： E(x_i，x_i+1)＝f⁸(x_i，x_i+1) ここに、f(x_i，x_i+1)＝y_i，y_i+1 y_i＝x_i+1 Ｋ₁及びＫ₂はＮビット上の秘密鍵ｎはＮビットの奇数の数次に、装置は、復号を実行する装置へ、暗号化されたものの（ｑ＋１）ｙ_i個のブロックを送る。メッセージの復号を実行する装置は、各々のブロックｙ_i上で下記の計算を行なう。この計算は： D(y_i，y_i+1)＝ g^*（y_i，y_i+1）ここに、g(y_i，y_i+1)＝ x_i，x_i+1 x_i+1＝ y_i である。最後に、装置はメッセージＭ＝ｘ₁｜ｘ₂｜．．．｜ｘ_q+1を再構築する。処理をより良く理解するための一例として、関数ｆの２つの相互作用を行なう場合、下記の関係式が得られる。この関係式は：である。本発明による方法は、例えば、これを電子的署名又は上述のような秘密鍵プロトコルの使用に応用するべく、メッセージのハッシングを実現できるようにする。すなわち、例えば、以下の要領でメッセージのハッシングを行なうため前述のアルゴリズムの２つの暗号化関数を利用することである。すなわち、第１の変形形態は下記のとおりである。この変形形態は：メッセージの最初のブロックｘ₁の暗号化されたものｙ₁を計算し、この場合 y₁＝E(x₁)であり、メッセージのブロックｘ_iの残りの部分についてy_i＝ E(x_i 最後のブロックをとる。第２の変形形態は下記のとおりである。この変形形態は： E(x_i，x_i+1)＝f⁸(x_i，x_i+1)として、メッセージの最初の２つのブロック(ｘ₁，ｘ₂)の暗号化されたもの(ｙ₁，ｙ₂ )を計算し、この場合y₁，y₂＝E(x₁，x₁)であり、メッセージのブロック対(x_i，x_i+1)の残りのものについて、算し、ハッシングされたメッセージ値として最後のブロックをとる。このように、本発明は、通常公開鍵暗号通信に割当てられる処理回路をメッセージを交換する装置の中に導入したために、凍結された秘密鍵による暗号化プロトコルを提供することを可能にする。

Claims

【特許請求の範囲】１．少なくとも１つが可搬式記憶媒体である２つの処理装置の間における秘密鍵によるプロトコルの実行方法であって、該方法は、モジュール式乗算の演算を使用するモジュール式演算形式の演算を実行するに適するデジタルの処理回路を装置に設置する段階、１つはモジュール式計算形式のもので他の１つは２値論理に関するものである２つの演算の組合せを少なくとも含む一連の可逆的演算から成る秘密鍵による暗号化関数を使用するためにこの処理回路を利用する段階；および、暗号化又は署名のため伝送されるべき通信文に対し、又は復号するため受理した通信文に対しこの関数を適用する段階、を具備することを特徴とする実行方法。２．デジタル処理回路があらゆる処理の前にＮビットのｘ_i個のブロックへの分割を実行することを特徴とする請求の範囲１記載の方法。３．一連の演算は、モジュール式乗算を使用する順列であるものと排他的論理和論理演算という２つの演算の１つの組合せを少なくとも含み、この組合せは、という秘密鍵暗号化関数ｆにより定義され、ここに、ｘは、通信文のＮビットの１ブロックを表わし、Ｋ₁及びＫ₂は、Ｎ個のビット上の第１及び第２の秘密鍵を表わし、ｎは、Ｎビットの奇数の数を表わし、＊は、モジュロｎ乗算の演算を表わす、ことを特徴とする請求の範囲１又は２記載の方法。４．１つの装置が通信文を送る際に、反復的に関数ｆを各ブロックｘ_iに対して適用することから成る第１の処置を通信文上で実行することを特徴とする請求の範囲３記載の方法。５．反復数ｐが少なくとも４に等しいことを特徴とする請求の範囲４記載の方法。６．装置Aj及びAkが互いに、 ● 予め装置Ajが通信文をＮビットの（ｑ＋１）個のブロックに分割し、 ● 装置Ajは、通信文の暗号化されたブロックｇが、E(x)＝ f^p（x Ｍの各々のブロックｘを暗号化し、 ● 装置は、装置Akに対し（ｑ＋１）ｙ個のブロックを送出し、 ● 装置Akは、各ｙについて、ブロックｙの復号を実行するためD( あり、ここにｙは暗号化されたもののＮビットのブロックを表わす、というプロトコルに従い互いに通信することを特徴とする請求の範囲１〜５のいずれか１項に記載の方法。７．通信文は、Ｎビットの（ｑ＋１）個のブロックに分割され、１つの通信文の１つのブロックｘ_iは第１のレジスタ内に置かれ、その次のブロックｘ_i+1は第２のレジスタの中に入れられ、又装置は、f(x_i，x_i+1)＝ y_i，y_i+1としてE(x_i， x_i+1)＝ f^P(x った後、暗号化された通信文を送出し、装置は、装置Akに対して（ｑ＋１）ｙ_i個のブロックを送出し、装置Akは各々のブロックｙ_iについて、(y_i ，y_i+1)を復号し(x_i，x_i+1)を得る形でD(y_i，y_i+1)＝ g^p(y_i，y_i+1)の演算を行ない、ここに関数ｇはｆの逆関数であり、この関数はg(y_i，y_i+1)＝ x_i，x_i+1( なお式中 x 構築する、ことを特徴とする請求の範囲１〜６のいずれか１項に記載の方法。８．処理回路は通信文のハッシングを実行するために利用され、装置Ajが長さＬの通信文Ｍをハッシングした時点で、回路は、E(x メッセージの第１のブロックｘ₁の暗号化されたものｙ_iをy₁＝E(x₁)として計算し、後のブロックを採用する、ことを特徴とする請求の範囲１〜６のいずれか１項に記載の方法。９．通信文のハッシングを行なうために処理回路が利用され、及びこのとき装置Ajが長さＬの通信文Ｍをハッシングした時点で回路は、E(x_i，x_i+1)＝f⁸(x_i， x_i+1)の段階を実行し、その場合に、通信文の最初の２つのブロック（ｘ₁，ｘ₂）の暗号化されたもの（ｙ₁，ｙ₂ ）をy₁，y₂＝E(x₁，x₁)として計算し、メッセージのブロック対(x_i，x_i+1)の残りの部分について算を行ないハッシングされた通信文の値として最後のブロックを採用する、ことを特徴とする請求の範囲７記載の方法。 10．モジュール式計算が大きな数に関するものである、ことを特徴とする請求の範囲１〜９のいずれか１項に記載の方法。 11．機器｛Aj｝がチップカード、PCMCIAカード、バッジ、非接触型カード、その他全ての可搬式の機器又はこれらの可搬式の機器と同じ機能を有する安全モジュールを備えた他の全ての装置である、ことを特徴とする請求の範囲１〜10のいずれか１項に記載の方法。 12．各々の機器Ai間の通信が電子信号の交換によって実行される、ことを特徴とする請求の範囲１〜11のいずれか１項に記載の方法。 13．各機器Ai間の通信が、ラジオ波又は赤外線信号の交換により実現される、ことを特徴とする請求の範囲１〜12のいずれか１項に記載の方法。