(57)【要約】【課題】ＤＨ鍵交換処理時の鍵演算処理を第３者から秘匿し、第３者による主要な演算の流用あるいは改変が極めて困難な公開鍵生成装置，共有鍵生成装置，鍵交換装置及び鍵交換方法を提供する。【解決手段】乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段１１、前記乱数ｋａと前記元ｇと前記素数ｑより公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段１２、及び公開鍵配布元及び共有鍵配布先となるユーザー２の生成した公開鍵ｙｂと前記乱数生成手段１１にて生成された秘密鍵ｋａとを基に共有鍵Ｋａを作成する共有鍵生成手段２１を、１つのＬＳＩ３１に集積化して、秘密鍵ｋａがＬＳＩ３１内部で公開鍵ｙａ及び共有鍵Ｋａの生成にのみ用いられる構成とし、鍵交換装置３３の主要な暗号化演算が外部に漏れないようにする。【選択図】      図３
2004297578.tif 000002
【特許請求の範囲】
【請求項１】
乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、
前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段とを備え、
少なくとも前記乱数生成手段と前記公開鍵生成手段とが同一の半導体集積回路上に集積され、
公開鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得し、該公開鍵ｙａを公開鍵配布先となる第２のユーザーへ伝送する、
ことを特徴とする公開鍵生成装置。
【請求項２】
請求項１記載の公開鍵生成装置において、
前記公開鍵生成手段は、
前記乱数ｋａと、前記元ｇと、前記素数ｑより、前記公開鍵ｙａを、
ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑ
として、前記有限群Ｆ上で演算し出力する、
ことを特徴とする公開鍵生成装置。
【請求項３】
請求項１記載の公開鍵生成装置において、
前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、
前記公開鍵生成手段が、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、
ｙａ＝ｋａＧ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力する、
ことを特徴とする公開鍵生成装置。
【請求項４】
請求項１ないし３のいずれかに記載の公開鍵生成装置において、
前記乱数生成手段が、前記公開鍵ｙａの演算終了後に、新たな乱数を生成する、
ことを特徴とする公開鍵生成装置。
【請求項５】
乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、
共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記乱数ｋａより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、
少なくとも前記乱数生成手段と前記共有鍵生成手段とが同一の半導体集積回路上に集積され、
共有鍵配布元となる第１のユーザーの制御手段が、前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得し、前記乱数生成手段と前記共有鍵生成手段とを制御して、前記共有鍵Ｋａを導出する、
ことを特徴とする共有鍵生成装置。
【請求項６】
請求項５記載の共有鍵生成装置において、
前記共有鍵生成手段は、
前記共有鍵配布先となる第２のユーザーが生成した前記公開鍵ｙｂ＝ｇ＾ｋｂｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、
Ｋａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑ
として、前記有限群Ｆ上で演算し出力する、
ことを特徴とする共有鍵生成装置。
【請求項７】
請求項５記載の共有鍵生成装置において、
前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、
Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力する、
ことを特徴とする共有鍵生成装置。
【請求項８】
請求項５ないし７のいずれかに記載の共有鍵生成装置において、
前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成する、
ことを特徴とする共有鍵生成装置。
【請求項９】
乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、
前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、
共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記乱数ｋａより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、
少なくとも前記乱数生成手段と前記公開鍵生成手段と前記共有鍵生成手段とが同一の半導体集積回路上に集積され、
共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙｂを取得し、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出する、
ことを特徴とする鍵交換装置。
【請求項１０】
請求項９記載の鍵交換装置において、
前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより、前記公開鍵ｙａをｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力し、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記有限群Ｆ上で演算し生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵ＫａをＫａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力する、
ことを特徴とする鍵交換装置。
【請求項１１】
請求項９記載の鍵交換装置において、
前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、
前記公開鍵生成手段は、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｋａＧ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力し、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、
Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力する、
ことを特徴とする鍵交換装置。
【請求項１２】
請求項９ないし１１のいずれかに記載の鍵交換装置において、
前記乱数生成手段は、前記公開鍵ｙａと前記共有鍵Ｋａの演算がともに終了した後に、新たな乱数を生成する、
ことを特徴とする鍵交換装置。
【請求項１３】
乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、
前記乱数ｋａを一時的に記憶する秘密鍵保持手段と、
前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、
共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記秘密鍵保持手段が保持する乱数ｋａにより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、
少なくとも、前記乱数生成手段と、前記秘密鍵保持手段と、前記公開鍵生成手段と、前記共有鍵生成手段とが、同一の半導体集積回路上に集積され、
共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得して、該公開鍵ｙａを前記共有鍵配布先となる第２のユーザーへ伝送し、
前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得して、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出する、
ことを特徴とする鍵交換装置。
【請求項１４】
請求項１３記載の鍵交換装置において、
前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより前記公開鍵ｙａを、
ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑ
として、前記有限群Ｆ上で演算し出力し、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが前記乱数ｋｂより前記有限群Ｆ上で演算し生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記秘密鍵保持手段が記憶している乱数ｋａより、前記共有鍵Ｋａを、
Ｋａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑ
として、前記有限群Ｆ上で演算し出力する、
ことを特徴とする鍵交換装置。
【請求項１５】
請求項１３記載の鍵交換装置において、
前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記公開鍵生成手段は、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、
ｙａ＝ｋａＧ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力し、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記秘密鍵保持手段が記憶している乱数ｋａにより、前記共有鍵Ｋａを、
Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力する、
ことを特徴とする鍵交換装置。
【請求項１６】
請求項１３ないし１５のいずれかに記載の鍵交換装置において、
前記乱数生成手段は、前記公開鍵ｙａの演算終了後に、新たな乱数を生成する、
ことを特徴とする鍵交換装置。
【請求項１７】
請求項１３ないし１５のいずれかに記載の鍵交換装置において、
前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成し、
前記秘密鍵保持手段が、前記乱数生成手段の生成した前記新たな乱数を保持する、
ことを特徴とする鍵交換装置。
【請求項１８】
請求項９ないし１７のいずれかに記載の鍵交換装置を使用し、鍵を共有したいユーザーの双方が前記鍵を共有する、
ことを特徴とする鍵交換方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、公開されたネットワークにおける電子情報の伝送を第三者に秘匿し、安全に行うために用いられる公開鍵生成装置，共有鍵生成装置，鍵交換装置及び鍵交換方法に関し、特に第３者による装置の流用あるいは改変が極めて困難な公開鍵生成装置，共有鍵生成装置，鍵交換装置及び鍵交換方法を提供するものである。
【０００２】
【従来の技術】
従来の有限群上の離散対数問題を利用した鍵交換装置として、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ鍵交換装置（以下、ＤＨ鍵交換装置と呼ぶ）が知られている（例えば、特許文献１参照）。
【０００３】
図５に、ＤＨ鍵交換装置の従来例を示す。図５において、５１は公開鍵配布元となるユーザー１の乱数生成手段、５２はユーザー１の公開鍵生成手段、５３はユーザー１の共有鍵生成手段である。また、５４はユーザー２の乱数生成手段、５５は公開鍵配布先となるユーザー２の公開鍵生成手段、５６はユーザー２の共有鍵生成手段である。
【０００４】
以下、図５を用いて、ユーザー１の従来のＤＨ鍵交換装置とユーザー２の従来のＤＨ鍵交換装置とで、ユーザー１とユーザー２とが鍵を共有する方法について説明する。
【０００５】
有限群Ｆ上では乗算が定義されているものとする。有限群Ｆ上の元をｇ（ｇは素数である位数ｑを持つもの）とする。また、有限群Ｆ、元ｇ、素数ｑは公開されており、少なくともユーザー１とユーザー２との間で共有されているものとする。ユーザー１とユーザー２は以下のステップを経て、鍵を共有する。
【０００６】
（ステップ１）
ユーザー１は乱数生成手段５１を用いて乱数ｋａ（０＜ｋａ＜ｑ）を生成し、これをユーザー１の秘密鍵ｋａとする。同様にユーザー２は乱数生成手段５４を用いて乱数ｋｂ（０＜ｋｂ＜ｑ）を生成し、これをユーザー２の秘密鍵ｋｂとする。
【０００７】
（ステップ２）
ユーザー１は公開鍵生成手段５２を用いて公開鍵ｙａを生成する。ここで
ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑ    …（数１）
であり、ｙａは有限群Ｆ上で演算され求められる。ｍｏｄ  ｑはｑで割った余りを示す。同様にユーザー２は公開鍵生成手段５５を用いて公開鍵ｙｂを生成する。ここで、
ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑ    …（数２）
であり、ｙｂは有限群Ｆ上で演算され求められる。
【０００８】
（ステップ３）
ユーザー１はユーザー２へ公開鍵ｙａを伝送し、ユーザー２はユーザー１へ公開鍵ｙｂを伝送する。すなわち、ユーザー１とユーザー２との間で公開鍵ｙａ、公開鍵ｙｂを交換する。
【０００９】
（ステップ４）
ユーザー１は共有鍵生成手段５３を用いて鍵Ｋａを生成する。ここで、
2004297578.tif 000003
であり、Ｋａは有限群Ｆ上で演算され求められる。同様にユーザー２は共有鍵生成手段５６を用いて鍵Ｋｂを生成する。ここで、
2004297578.tif 000004
であり、Ｋｂは有限群Ｆ上で演算され求められる。
【００１０】
以上のステップ１〜４により、ユーザー１とユーザー２との間で同一の共有鍵Ｋ＝Ｋａ＝Ｋｂが生成される。
【００１１】
上記のＤＨ鍵交換装置では、有限群Ｆにおける離散対数問題の解法の困難性に基づいて装置が構成されている。すなわちｙ＝ｇ＾ｘｍｏｄｑ（０＜ｘ＜ｑ）を満たす整数ｘをｙ、ｇより求める困難性を安全性の根拠としている。
【００１２】
有限群Ｆにおける離散対数問題の解法の困難性を根拠とする暗号系として、楕円曲線暗号系が広く知られている。すなわち、有限体上の楕円曲線をＥ（Ｆ）、楕円曲線Ｅ（Ｆ）上のあらかじめユーザー１とユーザー２との間で共有されている点をＧとし、楕円曲線Ｅ（Ｆ）上の点ｘとの演算ｘＧが定義されているものとすると、数１〜数４はそれぞれ数５〜数８に書き改めることができる。
【００１３】
2004297578.tif 000005
【００１４】
以上のように、楕円曲線暗号系を使用しても、ユーザー１とユーザー２との間で同一の共有鍵Ｋ＝Ｋａ＝Ｋｂが生成される。素数ｑを１６０ビット程度に選べば、現在知られている最も効率のよい計算アルゴリズムを使用し、最新のコンピュータを用いても、現実的な時間で解は求めることができないことが知られている。
【００１５】
上述したように、ＤＨ鍵交換装置ではｇ＾ｘ（楕円曲線暗号系におけるｘＧ）が鍵交換における主要な演算処理である。通常秘密鍵ｘは素数ｑと同程度のビット長（楕円曲線暗号系では１６０ビット程度）にとられるが、ユーザー１、ユーザー２以外の悪意ある第３者がｇ＾ｘ（あるいはｘＧ）を流用、あるいは鍵長をより長く改変するようなことがあれば、より強固な公開鍵暗号系を容易に構成することも可能であり、暗号系の保安上好ましくなく、特に主要な演算に高速演算アルゴリズムを使用している場合、さらに被害は甚大なものとなる。
【００１６】
【特許文献１】
特開２００１−３５２３１９号公報（第９頁、図４）
【００１７】
【発明が解決しようとする課題】
従来の公開鍵生成装置、共有鍵生成装置、鍵交換装置、及び鍵交換方法は以上のように構成されており、第３者からの攻撃に対しなんら配慮されないＤＨ鍵交換装置が用いられており、万が一主要な演算を悪意ある第３者が流用、あるいは改変することがあれば、国家の安全保障上極めて甚大な被害をもたらすという問題点を有していた。
【００１８】
本発明は以上のような問題点を解消するためになされたもので、第３者による装置の流用、あるいは改変が極めて困難な公開鍵生成装置，共有鍵生成装置，鍵交換装置、及び鍵交換方法を提供することを目的とする。
【００１９】
【課題を解決するための手段】
上記課題を解決するために、本発明（請求項１）にかかる公開鍵生成装置は、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段とを備え、少なくとも前記乱数生成手段と前記公開鍵生成手段とが同一の半導体集積回路上に集積され、公開鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得し、該公開鍵ｙａを公開鍵配布先となる第２のユーザーへ伝送するものである。
【００２０】
また、本発明（請求項２）にかかる公開鍵生成装置は、請求項１記載の公開鍵生成装置において、前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力するものである。
【００２１】
また、本発明（請求項３）にかかる公開鍵生成装置は、請求項１記載の公開鍵生成装置において、前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記公開鍵生成手段が、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｋａＧ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力するものである。
【００２２】
また、本発明（請求項４）にかかる公開鍵生成装置は、請求項１ないし３のいずれかに記載の公開鍵生成装置において、前記乱数生成手段が、前記公開鍵ｙａの演算終了後に、新たな乱数を生成するものである。
【００２３】
また、本発明（請求項５）にかかる共有鍵生成装置は、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記乱数ｋａより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、少なくとも前記乱数生成手段と前記共有鍵生成手段とが同一の半導体集積回路上に集積され、共有鍵配布元となる第１のユーザーの制御手段が、前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得し、前記乱数生成手段と前記共有鍵生成手段とを制御して、前記共有鍵Ｋａを導出するものである。
【００２４】
また、本発明（請求項６）にかかる共有鍵生成装置は、請求項５記載の共有鍵生成装置において、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、Ｋａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力するものである。
【００２５】
また、本発明（請求項７）にかかる共有鍵生成装置は、請求項５記載の共有鍵生成装置において、前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力するものである。
【００２６】
また、本発明（請求項８）にかかる共有鍵生成装置は、請求項５ないし７のいずれかに記載の共有鍵生成装置において、前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成するものである。
【００２７】
また、本発明（請求項９）にかかる鍵交換装置は、が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記乱数ｋａより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、少なくとも前記乱数生成手段と前記公開鍵生成手段と前記共有鍵生成手段とが同一の半導体集積回路上に集積され、共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙｂを取得し、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出するものである。
【００２８】
また、本発明（請求項１０）にかかる鍵交換装置は、請求項９記載の鍵交換装置において、前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより、前記公開鍵ｙａをｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力し、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記有限群Ｆ上で演算し生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵ＫａをＫａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力するものである。
【００２９】
また、本発明（請求項１１）にかかる鍵交換装置は、請求項９記載の鍵交換装置において、前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記公開鍵生成手段は、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｋａＧ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力し、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力するものである。
【００３０】
また、本発明（請求項１２）にかかる鍵交換装置は、請求項９ないし１１のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記公開鍵ｙａと前記共有鍵Ｋａの演算がともに終了した後に、新たな乱数を生成するものである。
【００３１】
また、本発明（請求項１３）にかかる鍵交換装置は、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、前記乱数ｋａを一時的に記憶する秘密鍵保持手段と、前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記秘密鍵保持手段が保持する乱数ｋａにより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、少なくとも、前記乱数生成手段と、前記秘密鍵保持手段と、前記公開鍵生成手段と、前記共有鍵生成手段とが、同一の半導体集積回路上に集積され、共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得して、該公開鍵ｙａを前記共有鍵配布先となる第２のユーザーへ伝送し、前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得して、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出するものである。
【００３２】
また、本発明（請求項１４）にかかる鍵交換装置は、請求項１３記載の鍵交換装置において、前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより前記公開鍵ｙａを、ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力し、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが前記乱数ｋｂより前記有限群Ｆ上で演算し生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記秘密鍵保持手段が記憶している乱数ｋａより、前記共有鍵Ｋａを、Ｋａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力するものである。
【００３３】
また、本発明（請求項１５）にかかる鍵交換装置は、請求項１３記載の鍵交換装置において、前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記公開鍵生成手段は、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｋａＧ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力し、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記秘密鍵保持手段が記憶している乱数ｋａにより、前記共有鍵Ｋａを、Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力するものである。
【００３４】
また、本発明（請求項１６）にかかる鍵交換装置は、請求項１３ないし１５のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記公開鍵ｙａの演算終了後に、新たな乱数を生成するものである。
【００３５】
また、本発明（請求項１７）にかかる鍵交換装置は、請求項１３ないし１５のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成し、前記秘密鍵保持手段が、前記乱数生成手段の生成した前記新たな乱数を保持するものである。
【００３６】
また、本発明（請求項１８）にかかる鍵交換装置は、請求項９ないし１７のいずれかに記載の鍵交換装置を使用し、鍵を共有したいユーザーの双方が前記鍵を共有するものである。
【００３７】
【発明の実施の形態】
以下、本発明の実施の形態について、図面を用いて説明する。
【００３８】
（実施の形態１）
図１は、本発明の請求項１に対応する実施の形態１による公開鍵生成装置のブロック構成図を示すものである。
【００３９】
図１において、１１は乱数生成手段、１２は公開鍵生成手段、１３は１つのパッケージに収められた半導体集積回路（以下ＬＳＩと呼ぶ）、１４は半導体集積回路（ＬＳＩ）１３を制御する制御手段、１５は半導体集積回路１３、制御手段１４を含む公開鍵配布元であるユーザー１の公開鍵生成装置である。
【００４０】
以下、図１を参照しながら、本実施の形態１の公開鍵生成装置の動作について説明する。
乱数生成手段１１は、制御手段１４によって制御され、乱数ｋａを生成し、これを秘密鍵ｋａとする。ここで秘密鍵ｋａは、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとした時、０＜ｋａ＜ｑを満たしている。制御手段１４は、乱数を生成するタイミングや乱数の種、初期値の設定を行う。制御手段１４には、例えばマイクロコンピュータが使用される。
【００４１】
公開鍵生成手段１２は、上記制御手段１４により制御され、公開鍵ｙａを生成する。公開鍵ｙａは、上述した数１式に基づいて秘密鍵ｋａより求められる。生成された公開鍵ｙａは、制御手段１４によって公開鍵配布先であるユーザー２へ伝送される。
【００４２】
少なくとも乱数生成手段１１と、公開鍵生成手段１２を、ＬＳＩ１３内部に集積すれば、上記数１式の演算を他の暗号処理へ流用、あるいは改変することは非常に困難である。加えて制御手段１４を集積すれば、さらに効果が高まる。また公開鍵ｙａ生成後、乱数生成手段１１が、新たに乱数を生成するようにすれば、公開鍵ｙａは出力される毎に異なる値をとる。この時、上記数１式から明らかなように、公開鍵ｙａは、乱数の関数となる。よって、ユーザー１を含めた誰もが、本公開鍵生成装置１５を公開鍵ｙａの生成以外に流用、あるいは改変することは極めて困難である。
【００４３】
以上のように、本実施の形態１による公開鍵生成装置によれば、公開鍵生成装置１５を、乱数生成手段１１と公開鍵生成手段１２とを１つのＬＳＩ１５に集積化して構成するようにしたので、従来、何ら安全対策のなされていない演算アルゴリズムを用いて秘密鍵及び共有鍵を作製する場合に比べて、秘密鍵ｋａは、チップ内部で公開鍵ｙａの生成にのみ用いられる構成となり、公開鍵生成装置１５の数１式の演算が外部には漏れることがなく、このようなＬＳＩ１３を用いることで、本公開鍵生成装置１５を公開鍵ｙａの生成以外に流用、あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度が極めて高い。
【００４４】
なお、数１式に基づいて公開鍵ｙａを演算する例について説明したが、楕円曲線暗号を使用し、数５式に基づいて公開鍵ｙａを演算するようにしても、同様の効果が得られる。
【００４５】
また、離散対数問題に基づく公開鍵暗号系を使用すれば、どのような公開鍵暗号系に対しても同様の効果が得られることは言うまでもない。
【００４６】
（実施の形態２）
次に、本発明の請求項５に対応する実施の形態２による共有鍵生成装置について説明する。
図２は、本発明の実施の形態２による共有鍵生成装置のブロック構成図を示すものである。図２において、図１と同一符号は同一、または相当部分を示し、２１は共有鍵生成手段、２２は乱数生成手段１１と上記共有鍵生成手段２１とを含むＬＳＩ、２３はＬＳＩ２２を制御する制御手段、２４は共有鍵配布先となるユーザー２が生成した公開鍵を元に共有鍵を作成する、共有鍵配布元であるユーザー１の共有鍵生成装置を示す。以下、図２を参照しながら、本実施の形態２の共有鍵生成装置２４の動作について説明する。
【００４７】
乱数生成手段１１は制御手段２３に制御され、乱数ｋａを生成し、これを秘密鍵ｋａとする。ここで秘密鍵ｋａは、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとした時、０＜ｋａ＜ｑを満たしている。制御手段２３は乱数を生成するタイミングや乱数の種、初期値の設定を行う。制御手段２３には、例えばマイクロコンピュータが使用される。さらに制御手段２３は、共有鍵配布先となるユーザー２より数２式で表されるユーザー２の公開鍵ｙｂを取得する。共有鍵生成手段２１は制御手段２３に制御され、共有鍵Ｋａを生成する。共有鍵Ｋａは数３式に基づいてユーザー１の秘密鍵ｋａとユーザー２の公開鍵ｙｂとにより演算される。生成された共有鍵Ｋａは、例えば、制御手段１４によって秘密鍵暗号方式の鍵として用いられ、ユーザー１とユーザー２との間でこの共通の共有鍵Ｋａを用いた暗号化伝送に使用される。
【００４８】
以上の構成において、少なくとも乱数生成手段１１と共有鍵生成手段２１とをＬＳＩ２２内部に集積すれば、数３式の演算を他の暗号処理へ流用あるいは改変することは非常に困難である。加えて制御手段２３を集積すれば、さらに効果が高まる。また共有鍵Ｋａ生成後、乱数生成手段１１が新たに乱数を生成するようにすれば、共有鍵Ｋａは出力される毎に異なる値をとる。この時、数３式から明らかなように、共有鍵Ｋａは乱数の関数となる。よって、ユーザー１を含めた誰もが本共有鍵生成装置２４を共有鍵Ｋａの生成以外に流用あるいは改変することは極めて困難である。
【００４９】
以上のように、本実施の形態２による共有鍵生成装置によれば、共有鍵生成装置２４を、乱数生成手段１１と共有鍵生成手段２１とを１つのＬＳＩ２２に集積化して構成するようにしたので、秘密鍵ｋａはチップ内部で共有鍵Ｋａの生成にのみ用いられる構成となり、共有鍵生成装置２４の数３式の演算が外部には漏れることがなく、このようなＬＳＩ２２を用いることで、本共有鍵生成装置２４を共有鍵Ｋａの生成以外に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度が極めて高い。
【００５０】
なお、数３式に基づいて共有鍵Ｋａを演算する例について説明したが、楕円曲線暗号を使用し、数７式に基づいて共有鍵Ｋａを演算しても同様の効果が得られる。
また、離散対数問題に基づく公開鍵暗号系を使用すれば、どのような公開鍵暗号系に対しても同様の効果が得られることは言うまでもない。
【００５１】
（実施の形態３）
次に、本発明の請求項９に対応する実施の形態３による鍵交換装置について説明する。
図３は、本発明の実施の形態３である鍵交換装置のブロック構成図を示すものである。
【００５２】
図３において、図１または図２と同一符号は同一、または相当部分を示し、３１は乱数生成手段１１，公開鍵生成手段１２，共有鍵生成手段２１とを含むＬＳＩ、３２はＬＳＩ３１を制御する制御手段、３３は公開鍵配布元、及び共有鍵配布先となるユーザー２の生成した公開鍵を基に作成した共有鍵の配布元、となるユーザー１の鍵交換装置である。
【００５３】
以下、図３を参照しながら、実施の形態３の鍵交換装置の動作について説明する。
乱数生成手段１１は制御手段３２に制御され、乱数ｋａを生成し、これを秘密鍵ｋａとする。ここで秘密鍵ｋａは、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとした時、０＜ｋａ＜ｑを満たしている。制御手段３２は乱数を生成するタイミングや乱数の種、初期値の設定を行う。制御手段３２には、例えばマイクロコンピュータが使用される。公開鍵生成手段１２は制御手段３２に制御され、公開鍵ｙａを生成する。公開鍵ｙａは数１式に基づいて演算される。生成された公開鍵ｙａは、制御手段３２によってユーザー２へ伝送される。
【００５４】
さらに制御手段３２は、ユーザー２より数２式で表されるユーザー２の公開鍵ｙｂを取得する。共有鍵生成手段２１は制御手段３２に制御され、共有鍵Ｋａを生成する。共有鍵Ｋａは数３式に基づいて秘密鍵ｋａと公開鍵ｙｂより演算される。生成された共有鍵Ｋａは、制御手段３２によって例えば秘密鍵暗号方式の鍵として用いられ、ユーザー１とユーザー２との間の暗号化伝送に使用される。
【００５５】
少なくとも乱数生成手段１１と公開鍵生成手段１２と共有鍵生成手段２１をＬＳＩ３１内部に集積すれば、数１式および数３式の演算を他の暗号処理へ流用あるいは改変することは非常に困難である。加えて制御手段３２を集積すれば、さらに効果が高まる。また公開鍵ｙａと共有鍵Ｋａとを生成後、乱数生成手段１１が新たに乱数を生成するようにすれば、数１式および数３式から明らかなように、公開鍵ｙａと共有鍵Ｋａは乱数の関数となる。よって、ユーザー１を含めた誰もが本鍵交換装置３３を鍵交換処理以外に流用あるいは改変することは極めて困難である。
【００５６】
以上のように、本実施の形態３による鍵交換装置によれば、鍵交換装置３３を、乱数生成手段１１と公開鍵生成手段１２と共有鍵生成手段２１とを、１つのＬＳＩ１３１に集積化して構成するようにしたので、秘密鍵ｋａはチップ内部で公開鍵ｙａ、及び共有鍵Ｋａの生成にのみ用いられる構成となり、鍵交換装置３３の数１式及び数３式の演算が外部には漏れることがなく、このようなＬＳＩ１３１を用いることで本鍵交換装置３３を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難となり、第３者の不正な攻撃に対する強度が極めて高い。
【００５７】
なお、数１式および数３式に基づいて公開鍵ｙａと共有鍵Ｋａを演算する例について説明したが、楕円曲線暗号を使用し、数５式および数７式に基づいて公開鍵ｙａと共有鍵Ｋａとを演算しても同様の効果が得られる。
【００５８】
また、離散対数問題に基づく公開鍵暗号系を使用すれば、どのような公開鍵暗号系に対しても同様の効果が得られることは言うまでもない。
なお、本実施の形態３における鍵交換装置３３と同様の構成をもつ鍵交換装置をユーザー２が使用することによって、ユーザー１とユーザー２の間の鍵交換処理を極めて安全に行うことができることは説明するまでもない。
【００５９】
（実施の形態４）
次に、本発明の請求項１３に対応する実施の形態４による鍵交換装置について説明する。
図４は、本発明の実施の形態４による鍵交換装置のブロック構成図を示すものである。
【００６０】
図４において、図１または図２と同一符号は同一、または相当部分を示し、４１は秘密鍵保持手段、４２は乱数生成手段１１，公開鍵生成手段，共有鍵生成手段２１，秘密鍵保持手段４１とを含むＬＳＩ、４３はＬＳＩ４２を制御する制御手段、４４は公開鍵配布元、及び共有鍵配布先となるユーザー２の生成した公開鍵を基に作成した共有鍵の配布元、となるユーザー１の鍵交換装置である。以下、図４を参照しながら、本実施の形態４の鍵交換装置の動作について説明する。
【００６１】
乱数生成手段１１は制御手段４３に制御され、乱数ｋａを生成し、これを秘密鍵ｋａとする。ここで秘密鍵ｋａは、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとした時、０＜ｋａ＜ｑを満たしている。制御手段４３は乱数を生成するタイミングや乱数の種、初期値の設定を行う。制御手段４３には、例えばマイクロコンピュータが使用される。秘密鍵保持手段４１は秘密鍵ｋａを一時的に記憶する。公開鍵生成手段１２は制御手段４３に制御され、公開鍵ｙａを生成する。公開鍵ｙａは数１式に基づいて演算される。生成された公開鍵ｙａは、制御手段４３によってユーザー２へ伝送される。
【００６２】
さらに制御手段４３は、ユーザー２より数２式で表されるユーザー２の公開鍵ｙｂを取得する。共有鍵生成手段２１は制御手段４３に制御され、共有鍵Ｋａを生成する。共有鍵Ｋａは数３式に基づいて秘密鍵保持手段４１が記憶している秘密鍵ｋａと公開鍵ｙｂとより演算される。生成された共有鍵Ｋａは、制御手段４３によって、例えば秘密鍵暗号方式の鍵として用いられ、ユーザー１とユーザー２との間の暗号化伝送に使用される。
【００６３】
少なくとも乱数生成手段１１と公開鍵生成手段１２と共有鍵生成手段２１と秘密鍵保持手段４１とをＬＳＩ４２内部に集積すれば、数１式および数３式の演算を他の暗号処理へ流用あるいは改変することは非常に困難である。加えて制御手段４３を集積すれば、さらに効果が高まる。
【００６４】
また公開鍵ｙａを生成後、乱数生成手段１１が新たに乱数を生成するようにすれば、公開鍵ｙａは出力される毎に異なる値をとる。この時、数１式から明らかなように、公開鍵ｙａは乱数の関数となる。共有鍵生成手段２１が共有鍵Ｋａを生成する以前に、乱数生成手段１１が新たに乱数を生成しても、秘密鍵保持手段４１が秘密鍵ｋａを保持しているため、共有鍵生成手段２１は正しく共有鍵Ｋａを生成することができる。
【００６５】
加えて、共有鍵生成手段２１により共有鍵Ｋａを生成した後、乱数生成手段１１が新たに乱数を生成し、生成した乱数を秘密鍵保持手段４１が保持するようにすれば、共有鍵Ｋａは出力される毎に異なる値をとる。この時、数３式から明らかなように、共有鍵Ｋａは乱数の関数となる。
【００６６】
よって、ユーザー１を含めた誰もが本鍵交換装置を鍵交換処理以外に流用あるいは改変することは極めて困難である。またＬＳＩ４２の外部に出力される公開鍵ｙａ、共有鍵Ｋａを観測しても乱数の関数となっているため、公開鍵生成手段１２と共有鍵生成手段２１の構成を類推することすら不可能である。
【００６７】
以上のように、本実施の形態４による鍵交換装置によれば、鍵交換装置４４を、乱数生成手段１１と公開鍵生成手段１２と共有鍵生成手段２１と秘密鍵保持手段４１とを１つのＬＳＩ４２に集積化して構成するようにしたので、秘密鍵ｋａはチップ内部で公開鍵ｙａ、及び共有鍵Ｋａの生成にのみ用いられる構成となり、鍵交換装置４４の数１式及び数３式の演算が外部には漏れることがなく、このようなＬＳＩ４２を用いることで本鍵交換装置４４を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難となり、第３者の不正な攻撃に対する強度が極めて高い。
【００６８】
加えて、共有鍵生成手段２１が共有鍵Ｋａを生成する以前に、乱数生成手段１１が新たに乱数を生成しても、共有鍵生成手段２１が正しく共有鍵Ｋａを生成することができる。
【００６９】
なお、数１式および数３式に基づいて公開鍵ｙａと共有鍵Ｋａを演算する例について説明したが、楕円曲線暗号を使用し、数５式および数７式に基づいて公開鍵ｙａと共有鍵Ｋａを演算しても同様の効果が得られる。
【００７０】
また、離散対数問題に基づく公開鍵暗号系を使用すれば、どのような公開鍵暗号系に対しても同様の効果が得られることは言うまでもない。
【００７１】
なお、本実施の形態４における鍵交換装置４４と同様の構成をもつ鍵交換装置をユーザー２が使用することによって、ユーザー１とユーザー２の間の鍵交換処理を極めて安全に行うことができることは説明するまでもない。
【００７２】
【発明の効果】
以上のように、本発明の請求項１にかかる公開鍵生成装置によれば、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段とを備え、少なくとも前記乱数生成手段と前記公開鍵生成手段とが同一の半導体集積回路上に集積され、公開鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得し、該公開鍵ｙａを公開鍵配布先となる第２のユーザーへ伝送するものとしたので、秘密鍵ｋａは半導体集積回路のチップ内部で公開鍵ｙａの生成にのみ用いられる構成となり、鍵交換装置の演算が外部には漏れることがなく、このような集積回路を用いることで本公開鍵生成装置を公開鍵ｙａの生成以外に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００７３】
また、本発明の請求項２にかかる公開鍵生成装置によれば、請求項１記載の公開鍵生成装置において、前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力するものとしたので、有限群Ｆにおける離散対数問題の解法の困難性を根拠とした暗号系において、公開鍵生成装置を公開鍵ｙａの生成以外に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００７４】
また、本発明の請求項３にかかる公開鍵生成装置によれば、請求項１記載の公開鍵生成装置において、前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記公開鍵生成手段が、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｋａＧ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力するものとしたので、楕円曲線暗号系においても、公開鍵生成装置を公開鍵ｙａの生成以外に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００７５】
また、本発明の請求項４にかかる公開鍵生成装置によれば、請求項１ないし３のいずれかに記載の公開鍵生成装置において、前記乱数生成手段が、前記公開鍵ｙａの演算終了後に、新たな乱数を生成するものとしたので、公開鍵ｙａは出力される毎に異なるものとなり、第３者の不正な攻撃に対する強度をさらに高いものとすることができるという効果が得られる。
【００７６】
また、本発明の請求項５にかかる共有鍵生成装置は、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記乱数ｋａより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、少なくとも前記乱数生成手段と前記共有鍵生成手段とが同一の半導体集積回路上に集積され、共有鍵配布元となる第１のユーザーの制御手段が、前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得し、前記乱数生成手段と前記共有鍵生成手段とを制御して、前記共有鍵Ｋａを導出するものとしたので、秘密鍵ｋａは半導体集積回路のチップ内部で共有鍵Ｋａの生成にのみ用いられる構成となり、鍵交換装置の演算が外部には漏れることがなく、このような集積回路を用いることで本共有鍵生成装置を共有鍵Ｋａの生成以外に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００７７】
また、本発明の請求項６にかかる共有鍵生成装置は、請求項５記載の共有鍵生成装置において、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、Ｋａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力するものとしたので、有限群Ｆにおける離散対数問題の解法の困難性を根拠とした暗号系において、共有鍵生成装置を共有鍵Ｋａの生成以外に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００７８】
また、本発明の請求項７にかかる共有鍵生成装置は、請求項５記載の共有鍵生成装置において、前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力するものとしたので、楕円曲線暗号系においても、共有鍵生成装置を共有鍵Ｋａの生成以外に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００７９】
また、本発明の請求項８にかかる共有鍵生成装置は、請求項５ないし７のいずれかに記載の共有鍵生成装置において、前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成するものとしたので、共有鍵Ｋａは出力される毎に異なるものとなり、第３者の不正な攻撃に対する強度をさらに高いものとすることができるという効果が得られる。
【００８０】
また、本発明の請求項９にかかる鍵交換装置は、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記乱数ｋａより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、少なくとも前記乱数生成手段と前記公開鍵生成手段と前記共有鍵生成手段とが同一の半導体集積回路上に集積され、共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙｂを取得し、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出するものとしたので、秘密鍵ｋａは半導体集積回路のチップ内部で公開鍵ｙａ、及び共有鍵Ｋａの生成にのみ用いられる構成となり、鍵交換装置の演算が外部には漏れることがなく、このような集積回路を用いることで本鍵交換装置を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難となり、第３者の不正な攻撃に対する強度が極めて高いものとすることができるという効果が得られる。
【００８１】
また、本発明の請求項１０にかかる鍵交換装置は、請求項９記載の鍵交換装置において、前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより、前記公開鍵ｙａをｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力し、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記有限群Ｆ上で演算し生成した前記公開鍵ｙｂ＝ｇ＾ｋｂｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵ＫａをＫａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力するものとしたので、有限群Ｆにおける離散対数問題の解法の困難性を根拠とした暗号系において、鍵交換装置を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００８２】
また、本発明の請求項１１にかかる鍵交換装置は、請求項９記載の鍵交換装置において、前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記公開鍵生成手段は、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｋａＧ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力し、前記共有鍵生成手段は、前記共有鍵配布先となる前記第２のユーザーが、前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力するものとしたので、楕円曲線暗号系においても、鍵交換装置を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００８３】
また、本発明の請求項１２にかかる鍵交換装置は、請求項９ないし１１のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記公開鍵ｙａと前記共有鍵Ｋａの演算がともに終了した後に、新たな乱数を生成するものとしたので、公開鍵ｙａ、及び共有鍵Ｋａは出力される毎に異なるものとなり、第３者の不正な攻撃に対する強度をさらに高いものとすることができるという効果が得られる。
【００８４】
また、本発明の請求項１３にかかる鍵交換装置は、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、前記乱数ｋａを一時的に記憶する秘密鍵保持手段と、前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記秘密鍵保持手段が保持する乱数ｋａにより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段とを備え、少なくとも、前記乱数生成手段と、前記秘密鍵保持手段と、前記公開鍵生成手段と、前記共有鍵生成手段とが、同一の半導体集積回路上に集積され、共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得して、該公開鍵ｙａを前記共有鍵配布先となる第２のユーザーへ伝送し、前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得して、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出するものとしたので、秘密鍵ｋａは半導体集積回路のチップ内部で公開鍵ｙａ、及び共有鍵Ｋａの生成にのみ用いられる構成となり、鍵交換装置の演算が外部には漏れることがなく、このような集積回路を用いることで本鍵交換装置を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難となり、第３者の不正な攻撃に対する強度が極めて高いものとすることができるという効果が得られるのに加えて、共有鍵生成手段が共有鍵Ｋａを生成する以前に、乱数生成手段が新たに乱数を生成しても、共有鍵生成手段は正しく共有鍵Ｋａを生成することができるという効果が得られる。
【００８５】
また、本発明の請求項１４にかかる鍵交換装置は、請求項１３記載の鍵交換装置において、前記公開鍵生成手段は、前記乱数ｋａと前記元ｇと前記素数ｑより前記公開鍵ｙａを、ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力し、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが前記乱数ｋｂより前記有限群Ｆ上で演算し生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと前記秘密鍵保持手段が記憶している乱数ｋａより前記共有鍵Ｋａを、Ｋａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力するものとしたので、有限群Ｆにおける離散対数問題の解法の困難性を根拠とした暗号系において、鍵交換装置を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００８６】
また、本発明の請求項１５にかかる鍵交換装置は、請求項１３記載の鍵交換装置において、前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記公開鍵生成手段は、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｋａＧ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力し、前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記秘密鍵保持手段が記憶している乱数ｋａにより、前記共有鍵Ｋａを、Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑとして、前記楕円曲線Ｅ（Ｆ）上で演算し出力するものとしたので、楕円曲線暗号系においても、鍵交換装置を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度を極めて高いものとすることができるという効果が得られる。
【００８７】
また、本発明の請求項１６にかかる鍵交換装置は、請求項１３ないし１５のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記公開鍵ｙａの演算終了後に、新たな乱数を生成するようにしたので、公開鍵ｙａ、及び共有鍵Ｋａは出力される毎に異なるものとなり、第３者の不正な攻撃に対する強度をさらに高いものとすることができるという効果が得られる。
【００８８】
また、本発明の請求項１７にかかる鍵交換装置は、請求項１３ないし１５のいずれかに記載の鍵交換装置において、
【００８９】
前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成し、前記秘密鍵保持手段が、前記乱数生成手段の生成した前記新たな乱数を保持するようにしたので、共有鍵生成手段が共有鍵Ｋａを生成する以前に、乱数生成手段が新たに乱数を生成しても、共有鍵生成手段が正しく共有鍵Ｋａを生成することができるという効果が得られる。
【００９０】
また、本発明の請求項１８にかかる鍵交換方法は、請求項９ないし１７のいずれかに記載の鍵交換装置を使用し、鍵を共有したいユーザーの双方が前記鍵を共有するようにしたので、鍵交換装置の演算が外部には漏れることがなく、このような集積回路を用いることで暗号鍵生成、または鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難となり、第３者の不正な攻撃に対する強度が極めて高いものとすることができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の実施の形態１における公開鍵生成装置の構成を示すブロック構成図である。
【図２】本発明の実施の形態２における共有鍵生成装置の構成を示すブロック構成図である。
【図３】本発明の実施の形態３における鍵交換装置の構成を示すブロック構成図である。
【図４】本発明の実施の形態４における鍵交換装置の構成を示すブロック構成図である。
【図５】従来の鍵交換装置の構成を示すブロック構成図である。
【符号の説明】
１１  乱数生成手段
１２  公開鍵生成手段
１３，２２，３１，４２  ＬＳＩ
１４，２３，３２，４３  制御手段
１５  公開鍵生成装置
２１  共有鍵生成手段
２４  共有鍵生成装置
３３，４４  鍵交換装置
４１  秘密鍵保持手段
【図１】
2004297578.tif 000006
【図２】
2004297578.tif 000007
【図３】
2004297578.tif 000008
【図４】
2004297578.tif 000009
【図５】
2004297578.tif 000010
【手続補正書】
【提出日】平成16年4月1日(2004.4.1)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、
前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、を備え、
少なくとも前記乱数生成手段と前記公開鍵生成手段とが同一の半導体集積回路上に集積され、
公開鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得し、該公開鍵ｙａを公開鍵配布先となる第２のユーザーへ伝送する、
ことを特徴とする公開鍵生成装置。
【請求項２】
請求項１記載の公開鍵生成装置において、
前記公開鍵生成手段は、
前記乱数ｋａと、前記元ｇと、前記素数ｑより、前記公開鍵ｙａを、
ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑ
として、前記有限群Ｆ上で演算し出力する、
ことを特徴とする公開鍵生成装置。
【請求項３】
請求項１記載の公開鍵生成装置において、
前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、
前記公開鍵生成手段が、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、
ｙａ＝ｋａＧ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力する、
ことを特徴とする公開鍵生成装置。
【請求項４】
請求項１ないし３のいずれかに記載の公開鍵生成装置において、
前記乱数生成手段が、前記公開鍵ｙａの演算終了後に、新たな乱数を生成する、
ことを特徴とする公開鍵生成装置。
【請求項５】
乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、
共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記乱数ｋａより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段と、を備え、
少なくとも前記乱数生成手段と前記共有鍵生成手段とが同一の半導体集積回路上に集積され、
共有鍵配布元となる第１のユーザーの制御手段が、前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得し、前記乱数生成手段と前記共有鍵生成手段とを制御して、前記共有鍵Ｋａを導出する、
ことを特徴とする共有鍵生成装置。
【請求項６】
請求項５記載の共有鍵生成装置において、
前記共有鍵生成手段は、
前記共有鍵配布先となる第２のユーザーが生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、
Ｋａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑ
として、前記有限群Ｆ上で演算し出力する、
ことを特徴とする共有鍵生成装置。
【請求項７】
請求項５記載の共有鍵生成装置において、
前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、
Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力する、
ことを特徴とする共有鍵生成装置。
【請求項８】
請求項５ないし７のいずれかに記載の共有鍵生成装置において、
前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成する、
ことを特徴とする共有鍵生成装置。
【請求項９】
乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、
前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、
共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記乱数ｋａより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段と、を備え、
少なくとも前記乱数生成手段と、前記公開鍵生成手段と、前記共有鍵生成手段とが同一の半導体集積回路上に集積され、
共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙｂを取得し、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出する、
ことを特徴とする鍵交換装置。
【請求項１０】
請求項９記載の鍵交換装置において、
前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより、前記公開鍵ｙａをｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力し、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記有限群Ｆ上で演算し生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵ＫａをＫａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑとして、前記有限群Ｆ上で演算し出力する、
ことを特徴とする鍵交換装置。
【請求項１１】
請求項９記載の鍵交換装置において、
前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、
前記公開鍵生成手段は、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、ｙａ＝ｋａＧ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力し、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記乱数ｋａにより、前記共有鍵Ｋａを、
Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力する、
ことを特徴とする鍵交換装置。
【請求項１２】
請求項９ないし１１のいずれかに記載の鍵交換装置において、
前記乱数生成手段は、前記公開鍵ｙａと前記共有鍵Ｋａの演算がともに終了した後に、新たな乱数を生成する、
ことを特徴とする鍵交換装置。
【請求項１３】
乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、
前記乱数ｋａを一時的に記憶する秘密鍵保持手段と、
前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、
共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記秘密鍵保持手段が保持する前記乱数ｋａにより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段と、を備え、
少なくとも、前記乱数生成手段と、前記秘密鍵保持手段と、前記公開鍵生成手段と、前記共有鍵生成手段とが、同一の半導体集積回路上に集積され、
共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得して、該公開鍵ｙａを前記共有鍵配布先となる第２のユーザーへ伝送し、
前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得し、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出する、
ことを特徴とする鍵交換装置。
【請求項１４】
請求項１３記載の鍵交換装置において、
前記公開鍵生成手段は、前記乱数ｋａと、前記元ｇと、前記素数ｑより前記公開鍵ｙａを、
ｙａ＝ｇ＾ｋａ  ｍｏｄ  ｑ
として、前記有限群Ｆ上で演算し出力し、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが前記乱数ｋｂより前記有限群Ｆ上で演算し生成した前記公開鍵ｙｂ＝ｇ＾ｋｂ  ｍｏｄ  ｑと、前記秘密鍵保持手段が記憶している乱数ｋａより、前記共有鍵Ｋａを、
Ｋａ＝ｙｂ＾ｋａ  ｍｏｄ  ｑ
として、前記有限群Ｆ上で演算し出力する、
ことを特徴とする鍵交換装置。
【請求項１５】
請求項１３記載の鍵交換装置において、
前記有限群Ｆを有限体上の楕円曲線Ｅ（Ｆ）とし、前記楕円曲線Ｅ（Ｆ）の元をＧとし、前記公開鍵生成手段は、前記乱数ｋａと、前記元Ｇと、前記素数ｑより、前記公開鍵ｙａを、
ｙａ＝ｋａＧ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力し、
前記共有鍵生成手段は、前記共有鍵配布先となる第２のユーザーが、前記乱数ｋｂより前記楕円曲線Ｅ（Ｆ）上で演算し生成した前記公開鍵ｙｂ＝ｋｂＧ  ｍｏｄ  ｑと、前記秘密鍵保持手段が記憶している乱数ｋａにより、前記共有鍵Ｋａを、
Ｋａ＝ｋａｙｂ  ｍｏｄ  ｑ
として、前記楕円曲線Ｅ（Ｆ）上で演算し出力する、
ことを特徴とする鍵交換装置。
【請求項１６】
請求項１３ないし１５のいずれかに記載の鍵交換装置において、
前記乱数生成手段は、前記公開鍵ｙａの演算終了後に、新たな乱数を生成し、
前記秘密鍵保持手段は、前記乱数生成手段の生成した前記新たな乱数を保持する、
ことを特徴とする鍵交換装置。
【請求項１７】
請求項１３ないし１５のいずれかに記載の鍵交換装置において、
前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成し、
前記秘密鍵保持手段は、前記乱数生成手段の生成した前記新たな乱数を保持する、
ことを特徴とする鍵交換装置。
【請求項１８】
請求項９ないし１７のいずれかに記載の鍵交換装置を使用し、公開鍵を共有したい第１のユーザーと第２のユーザーの双方が各々で生成した前記公開鍵を交換して、該交換した公開鍵を元に、第１のユーザーと第２のユーザー各々が共有鍵を作成する、
ことを特徴とする鍵交換方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
また、本発明（請求項１３）にかかる鍵交換装置は、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、前記乱数ｋａを一時的に記憶する秘密鍵保持手段と、前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記秘密鍵保持手段が保持する前記乱数ｋａにより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段と、を備え、少なくとも、前記乱数生成手段と、前記秘密鍵保持手段と、前記公開鍵生成手段と、前記共有鍵生成手段とが、同一の半導体集積回路上に集積され、共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得して、該公開鍵ｙａを前記共有鍵配布先となる第２のユーザーへ伝送し、前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得し、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出するものである。


【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
また、本発明（請求項１６）にかかる鍵交換装置は、請求項１３ないし１５のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記公開鍵ｙａの演算終了後に、新たな乱数を生成し、前記秘密鍵保持部は、前記乱数生成部の生成した前記新たな乱数を保持するものである。


【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
また、本発明（請求項１７）にかかる鍵交換装置は、請求項１３ないし１５のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成し、前記秘密鍵保持手段は、前記乱数生成手段の生成した前記新たな乱数を保持するものである。


【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００３６
【補正方法】変更
【補正の内容】
【００３６】
また、本発明（請求項１８）にかかる鍵交換装置は、請求項９ないし１７のいずれかに記載の鍵交換装置を使用し、公開鍵を共有したい第１のユーザーと第２のユーザーの双方が各々で生成した前記公開鍵を交換して、該交換した公開鍵を元に、第１のユーザーと第２のユーザー各々が共有鍵を作成するものである。


【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
以上のように、本実施の形態１による公開鍵生成装置によれば、公開鍵生成装置１５を、乱数生成手段１１と公開鍵生成手段１２とを１つのＬＳＩ１３に集積化して構成するようにしたので、従来、何ら安全対策のなされていない演算アルゴリズムを用いて秘密鍵及び共有鍵を作製する場合に比べて、秘密鍵ｋａは、チップ内部で公開鍵ｙａの生成にのみ用いられる構成となり、公開鍵生成装置１５の数１式の演算が外部には漏れることがなく、このようなＬＳＩ１３を用いることで、本公開鍵生成装置１５を公開鍵ｙａの生成以外に流用、あるいは改変することが極めて困難な状態となり、第３者の不正な攻撃に対する強度が極めて高い。


【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
乱数生成手段１１は制御手段２３に制御され、乱数ｋａを生成し、これを秘密鍵ｋａとする。ここで秘密鍵ｋａは、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとした時、０＜ｋａ＜ｑを満たしている。制御手段２３は乱数を生成するタイミングや乱数の種、初期値の設定を行う。制御手段２３には、例えばマイクロコンピュータが使用される。さらに制御手段２３は、共有鍵配布先となるユーザー２より数２式で表されるユーザー２の公開鍵ｙｂを取得する。共有鍵生成手段２１は制御手段２３に制御され、共有鍵Ｋａを生成する。共有鍵Ｋａは数３式に基づいてユーザー１の秘密鍵ｋａとユーザー２の公開鍵ｙｂとにより演算される。生成された共有鍵Ｋａは、例えば、制御手段２３によって秘密鍵暗号方式の鍵として用いられ、ユーザー１とユーザー２との間でこの共通の共有鍵Ｋａを用いた暗号化伝送に使用される。


【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５６
【補正方法】変更
【補正の内容】
【００５６】
以上のように、本実施の形態３による鍵交換装置によれば、鍵交換装置３３を、乱数生成手段１１と公開鍵生成手段１２と共有鍵生成手段２１とを、１つのＬＳＩ３１に集積化して構成するようにしたので、秘密鍵ｋａは、チップ内部で公開鍵ｙａ、及び共有鍵Ｋａの生成にのみ用いられる構成となり、鍵交換装置３３の数１式及び数３式の演算が外部には漏れることがなく、このようなＬＳＩ３１を用いることで本鍵交換装置３３を鍵交換以外の暗号化処理に流用あるいは改変することがを極めて困難となり、第３者の不正な攻撃に対する強度が極めて高い。


【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００８４
【補正方法】変更
【補正の内容】
【００８４】
また、本発明の請求項１３にかかる鍵交換装置は、乗算が定義された有限群Ｆ上の元をｇ、前記ｇの素数である位数をｑとし、０＜ｋａ＜ｑとなる乱数ｋａを生成する乱数生成手段と、前記乱数ｋａを一時的に記憶する秘密鍵保持手段と、前記乱数ｋａと、前記元ｇと、前記素数ｑより、公開鍵ｙａを前記有限群Ｆ上で演算し出力する公開鍵生成手段と、共有鍵配布先となる第２のユーザーが発生した０＜ｋｂ＜ｑとなる乱数ｋｂより生成された公開鍵ｙｂと、前記秘密鍵保持手段が保持する前記乱数ｋａにより、共有鍵Ｋａを前記有限群Ｆ上で演算し出力する共有鍵生成手段と、を備え、少なくとも、前記乱数生成手段と、前記秘密鍵保持手段と、前記公開鍵生成手段と、前記共有鍵生成手段とが、同一の半導体集積回路上に集積され、共有鍵配布元となる第１のユーザーの制御手段が、前記乱数生成手段と前記公開鍵生成手段とを制御して前記公開鍵ｙａを取得して、該公開鍵ｙａを前記共有鍵配布先となる第２のユーザーへ伝送し、前記共有鍵配布先となる第２のユーザーより前記公開鍵ｙｂを取得し、前記共有鍵生成手段を制御して前記共有鍵Ｋａを導出するものとしたので、秘密鍵ｋａは半導体集積回路のチップ内部で公開鍵ｙａ、及び共有鍵Ｋａの生成にのみ用いられる構成となり、鍵交換装置の演算が外部には漏れることがなく、このような集積回路を用いることで本鍵交換装置を鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難となり、第３者の不正な攻撃に対する強度が極めて高いものとすることができるという効果が得られるのに加えて、共有鍵生成手段が共有鍵Ｋａを生成する以前に、乱数生成手段が新たに乱数を生成しても、共有鍵生成手段は正しく共有鍵Ｋａを生成することができるという効果が得られる。


【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００８７
【補正方法】変更
【補正の内容】
【００８７】
また、本発明の請求項１６にかかる鍵交換装置は、請求項１３ないし１５のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記公開鍵ｙａの演算終了後に、新たな乱数を生成し、前記秘密鍵保持部は、前記乱数生成部の生成した前記新たな乱数を保持するようにしたので、公開鍵ｙａ、及び共有鍵Ｋａは出力される毎に異なるものとなり、第３者の不正な攻撃に対する強度をさらに高いものとすることができるという効果が得られる。


【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００８８
【補正方法】削除
【補正の内容】
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００８９
【補正方法】変更
【補正の内容】
【００８９】
また、本発明の請求項１７にかかる鍵交換装置は、請求項１３ないし１５のいずれかに記載の鍵交換装置において、前記乱数生成手段は、前記共有鍵Ｋａの演算終了後に、新たな乱数を生成し、前記秘密鍵保持手段は、前記乱数生成手段の生成した前記新たな乱数を保持するようにしたので、共有鍵生成手段が共有鍵Ｋａを生成する以前に、乱数生成手段が新たに乱数を生成しても、共有鍵生成手段が正しく共有鍵Ｋａを生成することができるという効果が得られる。


【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００９０
【補正方法】変更
【補正の内容】
【００９０】
また、本発明の請求項１８にかかる鍵交換方法は、請求項９ないし１７のいずれかに記載の鍵交換装置を使用し、公開鍵を共有したい第１のユーザーと第２のユーザーの双方が各々で生成した前記公開鍵を交換して、該交換した公開鍵を元に、第１のユーザーと第２のユーザー各々が共有鍵を作成するようにしたので、鍵交換装置の演算が外部には漏れることがなく、このような集積回路を用いることで暗号鍵生成、または鍵交換以外の暗号化処理に流用あるいは改変することが極めて困難となり、第３者の不正な攻撃に対する強度が極めて高いものとすることができるという効果が得られる。


【手続補正１４】
【補正対象書類名】図面
【補正対象項目名】図５
【補正方法】変更
【補正の内容】
【図５】
2004297578.tif 000011