(57)【特許請求の範囲】
【請求項１】
自装置内で素数をもとに暗号鍵を生成する暗号装置であって、
予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の第１の素数を生成する第１の素数生成手段と、
前記ｎビット以下のすべての素数および前記第１の素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段と、
前記所定のビット長の第２の素数を用いて暗号鍵を生成する暗号鍵生成手段とを備え、
前記第２の素数生成手段は、
前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする暗号装置。
【請求項２】
自装置内で暗号鍵を生成する暗号装置であって、
予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成手段と、
前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記ｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段と、
前記所定のビット長の素数を用いて暗号鍵を生成する暗号鍵生成手段とを備え、
前記第２の素数生成手段による素数判定は、
前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、該素数候補Ｎiを合成数でないと判定することを特徴とする暗号装置。
【請求項３】
自装置内で暗号鍵を生成する暗号装置であって、
予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成手段と、
前記第１の素数生成手段により生成された２ｎビット以下の第１の素数および前記ｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段と、
前記第１および第２の素数生成手段を用いて生成された０．４ｍビットの第２の素数および前記第２の素数をもとに０．５ｍビットの第３の素数を生成する第３の素数生成手段と、
前記第１および第２の素数生成手段を用いて生成された他の０．４ｍビットの第２の素数、前記第３の素数生成手段により生成された０．５ｍビットの第３の素数および前記ｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成手段と、
前記第４の素数生成手段により生成された前記ｍビットの第４の素数を用いて暗号鍵を生成する暗号鍵生成手段とを備え、
前記第２の素数生成手段は、
前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする暗号装置。
【請求項４】
暗号装置内で素数をもとに暗号鍵を生成する暗号鍵生成方法であって、
前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の第１の素数を生成し、
前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数および前記第１の素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成し、
この第２の素数を生成する際に、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを生成し、
前記所定のビット長の第２の素数を用いて前記暗号装置内のコプロセッサにより暗号鍵を生成することを特徴とする暗号鍵生成方法。
【請求項５】
暗号装置内で素数をもとに暗号鍵を生成する暗号鍵生成方法であって、
前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、
前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記第１の素数生成ステップにて合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップと、
前記所定のビット長の素数を用いて前記暗号装置内のコプロセッサにより暗号鍵を生成する暗号鍵生成ステップとを有し、
前記第２の素数生成ステップによる素数判定は、
前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、該素数候補Ｎiを合成数でないと判定することを特徴とする暗号鍵生成方法。
【請求項６】
暗号装置内で素数をもとに暗号鍵を生成する暗号鍵生成方法であって、
前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、
前記第１の素数生成ステップにて生成された２ｎビット以下の第１の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップと、
前記第１および第２の素数生成ステップにより生成された０．４ｍビットの第２の素数および前記第２の素数をもとに前記暗号装置内のコプロセッサにより０．５ｍビットの第３の素数を生成する第３の素数生成ステップと、
前記第１および第２の素数生成ステップにより生成された他の０．４ｍビットの第２の素数、前記第３の素数生成ステップにより生成された０．５ｍビットの第３の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成ステップと、
前記第４の素数生成ステップにて生成された前記ｍビットの第４の素数を用いて前記コプロセッサにより暗号鍵を生成する暗号鍵生成ステップとを有し、
前記第２の素数生成ステップは、
前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする暗号鍵生成方法。
【請求項７】
予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の素数を生成する第１の素数生成手段と、
前記ｎビット以下のすべての素数および前記２ｎビット以下の素数をもとに２ｎビットより大きい前記所定のビット長の素数を生成する第２の素数生成手段とを備え、
前記第２の素数生成手段は、
前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする素数生成装置。
【請求項８】
予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成手段と、
前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記ｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段とを備え、
前記第２の素数生成手段による素数判定は、
前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、該素数候補Ｎiを合成数でないと判定することを特徴とする素数生成装置。
【請求項９】
予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成手段と、
前記第１の素数生成手段により生成された２ｎビット以下の第１の素数および前記ｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段と、
前記第１および第２の素数生成手段を用いて生成された０．４ｍビットの第２の素数および前記第２の素数をもとに０．５ｍビットの第３の素数を生成する第３の素数生成手段と、
前記第１および第２の素数生成手段を用いて生成された他の０．４ｍビットの第２の素数、前記第３の素数生成手段により生成された０．５ｍビットの第３の素数および前記ｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成手段とを備え、
前記第２の素数生成手段は、
前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする素数生成装置。
【請求項１０】
暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の第１の素数を生成し、
前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数および前記２ｎビット以下の素数をもとに２ｎビットより大きい前記所定のビット長の素数を生成し、
この第２の素数を生成する際に、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを生成することを特徴とする素数生成方法。
【請求項１１】
暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、
前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記第１の素数生成ステップにて合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップとを有し、
前記第２の素数生成ステップによる素数判定は、
前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、該素数候補Ｎiを合成数でないと判定することを特徴とする素数生成方法。
【請求項１２】
暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、
前記第１の素数生成ステップにて生成された２ｎビット以下の第１の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップと、
前記第１および第２の素数生成ステップにより生成された０．４ｍビットの第２の素数および前記第２の素数をもとに前記暗号装置内のコプロセッサにより０．５ｍビットの第３の素数を生成する第３の素数生成ステップと、
前記第１および第２の素数生成ステップにより生成された他の０．４ｍビットの第２の素数、前記第３の素数生成ステップにより生成された０．５ｍビットの第３の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成ステップとを有し、
前記第２の素数生成ステップは、
前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする素数生成方法。
【請求項１３】
暗号装置のコンピュータに、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の第１の素数を生成する手順と、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数および前記第１の素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する手順を実行させるためのプログラムであって、前記第２の素数を生成する手順としては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得る手順を含むプログラムを記録したコンピュータ読取り可能な記録媒体。
【請求項１４】
暗号装置のコンピュータに、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記第１の素数生成ステップにて合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップとを実行させるためのプログラムであって、前記第２の素数生成ステップとしては、前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得るステップを含むプログラムを実行させるためのプログラムを記録したコンピュータ読取り可能な記録媒体。
【請求項１５】
暗号装置のコンピュータに、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、前記第１の素数生成ステップにて生成された２ｎビット以下の第１の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップと、前記第１および第２の素数生成ステップにより生成された０．４ｍビットの第２の素数および前記第２の素数をもとに前記暗号装置内のコプロセッサにより０．５ｍビットの第３の素数を生成する第３の素数生成ステップと、前記第１および第２の素数生成ステップにより生成された他の０．４ｍビットの第２の素数、前記第３の素数生成ステップにより生成された０．５ｍビットの第３の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成ステップとを実行させるためのプログラムであって、前記第２の素数生成ステップとしては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得るステップを含むプログラムを記録したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号処理、復号処理、認証処理などに用いる暗号鍵を自装置内で生成する暗号装置及び暗号鍵生成方法、並びに素数生成装置及び素数生成方法に関する。
【０００２】
【従来の技術】
昨今、情報処理の技術が進歩するにつれて情報を電子化して扱うことが通常行なわれるようになってきた。また、単にデータを電子化するだけでなく、電子貨幣システムや著作権に係る電子化情報の配布システムなど新たなサービスも開発されている。このような電子化情報を扱う場合に、企業秘密やプライベートなデータ、電子貨幣情報、著作権に係る電子化情報など、特定の者だけが閲覧等可能で、それ以外の者には内容を秘匿したい情報の蓄積や通信などにあたっては、暗号技術が使用される。
【０００３】
例えば、ホストコンピュータ間で暗号通信を行なう場合、送信側では共通鍵あるいは相手の公開鍵でデータを暗号化し、受信側ではこれを共通鍵あるいは自分の秘密鍵で復号することで、特定の鍵情報を持つ者だけが暗号化データを復号可能とすることができる。また例えば鍵情報を用いた認証処理により情報の正当性の検証を可能としている。
【０００４】
ところで、秘密鍵暗号では乱数生成機能が存在するだけで共通鍵の生成を容易に行なうことができる。これに対して、公開鍵暗号の公開鍵及び秘密鍵の生成は、秘密鍵暗号の共通鍵生成ほど簡単な処理ではない。特に、公開鍵及び秘密鍵を生成するためには、大きなビット長の素数が必要になるため、計算量の増加が避けられない。この大きなビット長の素数を高速に生成するための方法として、メモリを利用したテーブル処理が存在するが、この場合、非常に多くの素数を記憶しておく必要があり、メモリ資源の限られた暗号装置（例えば処理機能を有するＩＣカードを暗号装置として用いるもの）においてはこのテーブル処理は適切ではないとされてきた。このような理由から従来では、公開鍵暗号の公開鍵及び秘密鍵は、通常、パーソナルコンピュータ等の高速なＣＰＵと十分なメモリが存在する環境で生成する必要があった。
【０００５】
また、各ユーザの公開鍵を管理・公開するセンターが公開鍵及び秘密鍵を生成し、各ユーザに秘密鍵を配送する場合、安全性を考慮した鍵配送メカニズムが必須である。従って、センターが大量の秘密鍵を配送及び管理することは、かなりの負担であった。
【０００６】
また、個々のユーザがパーソナルコンピュータ等で公開鍵及び秘密鍵を生成し、秘密鍵を外部記憶装置に転送及び保持する場合、一時的であっても、パーソナルコンピュータのメモリ上に生成された鍵が存在することになり、それがオンラインの状態ならば、鍵が破壊あるいは改ざんされる可能性がある。また、秘密鍵生成機能の誤操作等により既に生成された鍵が破壊あるいは改ざんされる可能性がある。さらに、鍵が破壊あるいは改ざんなどされたことを検出することはできないという問題点もあった。
【０００７】
【発明が解決しようとする課題】
従来、素数をもとに暗号鍵（公開鍵、秘密鍵、共通鍵）を生成する場合、大きなビット長の素数を生成する必要があるため、多量のコンピュータ資源を必要とする問題点があった。
【０００８】
また、従来、秘密鍵生成機能の再起動により既に生成された鍵が破壊される可能性があるという問題点があった。
また、従来、鍵が破壊あるいは改ざんなどされたことを検出することはできないという問題点があった。
【０００９】
本発明は、上記事情を考慮してなされたものであり、自装置内でより少ないコンピュータ資源を利用して、暗号鍵生成のもととなる十分な大きさの素数を生成可能な暗号装置及び暗号鍵生成方法を提供することを目的とする。
【００１０】
また、本発明は、暗号鍵を安全に管理可能な暗号装置及び暗号鍵生成方法を提供することを目的とする。また、本発明は、より少ないコンピュータ資源を利用してより大きい素数を生成可能な素数生成装置及び素数生成方法を提供することを目的とする。
【００１１】
【課題を解決するための手段】
本発明（請求項１）は、自装置内で素数をもとに暗号鍵を生成する暗号装置であって、予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の第１の素数を生成する第１の素数生成手段と、前記ｎビット以下のすべての素数および前記第１の素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段と、前記所定のビット長の第２の素数を用いて暗号鍵を生成する暗号鍵生成手段とを備え、前記第２の素数生成手段としては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする。
【００１２】
本発明（請求項２）は、自装置内で暗号鍵を生成する暗号装置であって、予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成手段と、前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記ｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段と、前記所定のビット長の素数を用いて暗号鍵を生成する暗号鍵生成手段とを備え、前記第２の素数生成手段による素数判定としては、前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、該素数候補Ｎiを合成数でないと判定することを特徴とする。
【００１３】
本発明（請求項３）は、自装置内で暗号鍵を生成する暗号装置であって、予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成手段と、前記第１の素数生成手段により生成された２ｎビット以下の第１の素数および前記ｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段と、前記第１および第２の素数生成手段を用いて生成された０．４ｍビットの第２の素数および前記第２の素数をもとに０．５ｍビットの第３の素数を生成する第３の素数生成手段と、前記第１および第２の素数生成手段を用いて生成された他の０．４ｍビットの第２の素数、前記第３の素数生成手段により生成された０．５ｍビットの第３の素数および前記ｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成手段と、前記第４の素数生成手段により生成された前記ｍビットの第４の素数を用いて暗号鍵を生成する暗号鍵生成手段とを備え、前記第２の素数生成手段としては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする。
【００１６】
本発明（請求項４）は、暗号装置内で素数をもとに暗号鍵を生成する暗号鍵生成方法であって、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の第１の素数を生成し、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数および前記第１の素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成し、この第２の素数を生成する際に、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを生成し、前記所定のビット長の第２の素数を用いて前記暗号装置内のコプロセッサにより暗号鍵を生成することを特徴とする。
【００１７】
本発明（請求項５）は、暗号装置内で素数をもとに暗号鍵を生成する暗号鍵生成方法であって、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記第１の素数生成ステップにて合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップと、前記所定のビット長の素数を用いて前記暗号装置内のコプロセッサにより暗号鍵を生成する暗号鍵生成ステップとを有し、前記第２の素数生成ステップによる素数判定としては、前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、該素数候補Ｎiを合成数でないと判定することを特徴とする。
【００１８】
本発明（請求項６）は、暗号装置内で素数をもとに暗号鍵を生成する暗号鍵生成方法であって、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、前記第１の素数生成ステップにて生成された２ｎビット以下の第１の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップと、前記第１および第２の素数生成ステップにより生成された０．４ｍビットの第２の素数および前記第２の素数をもとに前記暗号装置内のコプロセッサにより０．５ｍビットの第３の素数を生成する第３の素数生成ステップと、前記第１および第２の素数生成ステップにより生成された他の０．４ｍビットの第２の素数、前記第３の素数生成ステップにより生成された０．５ｍビットの第３の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成ステップと、前記第４の素数生成ステップにて生成された前記ｍビットの第４の素数を用いて前記コプロセッサにより暗号鍵を生成する暗号鍵生成ステップとを有し、前記第２の素数生成ステップとしては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする。
【００２１】
本発明（請求項７）は、予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の素数を生成する第１の素数生成手段と、前記ｎビット以下のすべての素数および前記２ｎビット以下の素数をもとに２ｎビットより大きい前記所定のビット長の素数を生成する第２の素数生成手段とを備え、前記第２の素数生成手段としては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする。
【００２２】
本発明（請求項８）は、予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成手段と、前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記ｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段とを備え、前記第２の素数生成手段による素数判定としては、前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、該素数候補Ｎiを合成数でないと判定することを特徴とする。
【００２３】
本発明（請求項９）は、予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成手段と、前記第１の素数生成手段により生成された２ｎビット以下の第１の素数および前記ｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成手段と、前記第１および第２の素数生成手段を用いて生成された０．４ｍビットの第２の素数および前記第２の素数をもとに０．５ｍビットの第３の素数を生成する第３の素数生成手段と、前記第１および第２の素数生成手段を用いて生成された他の０．４ｍビットの第２の素数、前記第３の素数生成手段により生成された０．５ｍビットの第３の素数および前記ｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成手段とを備え、前記第２の素数生成手段としては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする。
【００２４】
本発明（請求項１０）は、暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の第１の素数を生成し、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数および前記２ｎビット以下の素数をもとに２ｎビットより大きい前記所定のビット長の素数を生成し、この第２の素数を生成する際に、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを生成することを特徴とする。
【００２５】
本発明（請求項１１）は、暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記第１の素数生成ステップにて合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップとを有し、前記第２の素数生成ステップによる素数判定としては、前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、該素数候補Ｎiを合成数でないと判定することを特徴とする。
【００２６】
本発明（請求項１２）は、暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、前記第１の素数生成ステップにて生成された２ｎビット以下の第１の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップと、前記第１および第２の素数生成ステップにより生成された０．４ｍビットの第２の素数および前記第２の素数をもとに前記暗号装置内のコプロセッサにより０．５ｍビットの第３の素数を生成する第３の素数生成ステップと、前記第１および第２の素数生成ステップにより生成された他の０．４ｍビットの第２の素数、前記第３の素数生成ステップにより生成された０．５ｍビットの第３の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成ステップとを有し、前記第２の素数生成ステップとしては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得ることを特徴とする。
【００２７】
本発明（請求項１３）は、暗号装置のコンピュータに、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の第１の素数を生成する手順と、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数および前記第１の素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する手順を実行させるためのプログラムであって、前記第２の素数を生成する手順としては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得る手順を含むプログラムを記録したコンピュータ読取り可能な記録媒体を要旨とする。
【００２８】
本発明（請求項１４）は、暗号装置のコンピュータに、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、前記第１の素数をもとに該第１の素数より大きい素数候補を生成し、前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数を少なくとも用いた素数判定により該素数候補が合成数でないと判定された場合には該素数候補を新たな第１の素数とし該新たな第１の素数をもとに該素数候補より大きい新たな素数候補を生成する処理を再帰的に繰り返すとともに、素数候補が合成数であると判定された場合には前記第１の素数生成ステップにて合成数と判定された時点での第１の素数をもとに素数候補を生成し直しあらためて該処理を再帰的に繰り返すことにより、２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップとを実行させるためのプログラムであって、前記第２の素数生成ステップとしては、前記素数候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得るステップを含むプログラムを実行させるためのプログラムを記録したコンピュータ読取り可能な記録媒体を要旨とする。
【００２９】
本発明（請求項１５）は、暗号装置のコンピュータに、前記暗号装置内でランダムアクセス可能な不揮発性メモリに格納された素数テーブルに格納された予め定められたｎビット以下のすべての素数を用いて所定の２ｎビット以下の乱数を素数判定することにより２ｎビット以下の第１の素数を生成する第１の素数生成ステップと、前記第１の素数生成ステップにて生成された２ｎビット以下の第１の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとに２ｎビットより大きい所定のビット長の第２の素数を生成する第２の素数生成ステップと、前記第１および第２の素数生成ステップにより生成された０．４ｍビットの第２の素数および前記第２の素数をもとに前記暗号装置内のコプロセッサにより０．５ｍビットの第３の素数を生成する第３の素数生成ステップと、前記第１および第２の素数生成ステップにより生成された他の０．４ｍビットの第２の素数、前記第３の素数生成ステップにより生成された０．５ｍビットの第３の素数および前記不揮発性メモリに格納された素数テーブルに格納されたｎビット以下のすべての素数をもとにｍビットの第４の素数を生成する第４の素数生成ステップとを実行させるためのプログラムであって、前記第２の素数生成ステップとしては、前記第２の素数の候補Ｎiを前記ｎビット以下のすべての素数で試行割算し、いずれの素数でも割り切れないとき、所定のａiについて第１式のフェルマーテストａiＮi−１≡１（ｍｏｄ  Ｎi）の関係を満たすか否かを計算し、第１式の関係を満たすとき、第２式の最大公約数ｇｃｄ（ａi(Ｎi−１)／Ｆi −１，Ｎi）≠１の関係（但し、Ｆi：第１の素数）を満たすか否かを計算し、第２式の関係を満たすとき、前記素数の候補Ｎiから第２の素数Ｎiを得るステップを含むプログラムを記録したコンピュータ読取り可能な記録媒体を要旨とする、好ましくは、前記プログラムはコンピュータに生成された前記素数を用いて暗号鍵を生成させる手順を含むものであるようにしてもよい。
【００３０】
好ましくは、前記プログラムはコンピュータに生成された前記暗号鍵を用いて暗号化対象となるデータを暗号化させる手順を含むものであるようにしてもよい。
【００３３】
なお、以上の装置に係る発明は方法に係る発明としても成立し、方法に係る発明は装置に係る発明としても成立する。
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムを記録したコンピュータ読取り可能な記録媒体としても成立する。
【００３４】
本発明（請求項１、２、３、４、５、６、７〜１２）において、ｎビットは好ましくは２の倍数である。例えばｎビット＝２５６＝２8 の場合、２５６以下の素数は全部で５３個である。また、所定のビット長は、例えば２５６ビットあるいは３８４ビットである。また、ｍは、例えば２５６あるいは３８４である。
【００３５】
また、第２〜第４の素数生成では、前記ｎビット以下のすべての素数を用いる素数判定（エラトステネスのふるい）の次に少なくともフェルマーテストを行なうのが好ましい。
【００３６】
また、好ましくは、前記暗号装置や前記素数生成装置は、プログラム記憶手段、プログラムを実行する演算手段、データの読み出し及び書き込み可能なメモリ手段及び外部との通信を行なう手段を備えても良い。
【００３７】
また、前記暗号装置や前記素数生成装置は、例えばパーソナルコンピュータで実現することができる。あるいはＩＣカードで実現することもできる。本発明（請求項１、２、３、４）によれば、確定的素数判定方法と、第１の素数を素数判定するときに用いる（第１の素数）1/2 以下の素数を格納した素数テーブルとを組合わせることによって、暗号装置のメモリ容量に対応したサイズのテーブルを利用することが可能になる。
【００３８】
したがって、豊富なメモリを持つパーソナルコンピュータのような暗号装置でなく、メモリ容量が限定されている暗号装置（例えばＩＣカード）であっても装置上に容易に鍵（例えば公開鍵暗号における公開鍵及び秘密鍵）の生成機能を実装することが可能になる。
【００３９】
また、扱うデータ量が少ないので、高速に鍵を生成することができる。
また、確定的素数判定方法を用いるので、確実に素数を得ることができ、安全な鍵を得ることができる。
【００４０】
また、装置に鍵生成機能を持たせることにより、鍵に対する安全性を向上させ、鍵の管理を容易にすることができる。
また、個々の暗号装置内で鍵を生成し、暗号装置内で暗号処理及び復号処理を行なうならば、鍵は決して暗号装置外に出ることがないので、鍵に対する高い安全性を保つことができる。
【００４１】
また、公開鍵暗号において、個々の暗号装置が秘密鍵および公開鍵を生成することにより、鍵を管理するセンターは、個々の暗号装置に対し鍵生成及び配送をする必要がなくなり、鍵生成及び管理に伴う処理の負担が軽減される。
【００４２】
本発明（請求項７〜１２）によれば、確定的素数判定方法と、第１の素数を素数判定するときに用いる（第１の素数）1/2 以下の素数を格納した素数テーブルとを組合わせることによって、装置のメモリ容量に対応したサイズのテーブルを利用することが可能になる。
【００４３】
したがって、豊富なメモリを持つパーソナルコンピュータのような装置でなく、メモリ容量が限定されている装置（例えばＩＣカード）であっても装置上に容易に素数生成機能を実装することが可能になる。
【００４４】
また、扱うデータ量が少ないので、高速に素数を生成することができる。また、確定的素数判定方法を用いるので、確実に素数を得ることができる。  
【００４７】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
図１は、本発明の一実施形態に係る暗号装置の構成を示す図である。
本実施形態の暗号装置１は、ＣＰＵ２、プログラム記憶部３、演算部４、乱数生成部５、ランダムアクセス可能な不揮発メモリ６、不揮発性メモリ７、アドレス及びデータバス８を備えている。
【００４８】
本実施形態では、プログラム記憶部３に格納されたプログラムをＣＰＵ２で実行する形で各機能を実現するものとしている。このプログラムは、素数生成のためのサブプログラムと鍵生成のためのサブプログラムとを少なくとも含む。なお、素数生成のためのサブプログラムと、鍵生成のためのサブプログラムとを独立実施することも可能である。
【００４９】
また、本実施形態では、処理速度を上げるために所定の演算については演算部４を利用する。演算部４には、例えばコプロセッサを用いる。ただし、演算部４を設けなくても構わない。
【００５０】
また、図１では、乱数生成部５を明に示しているが、乱数生成部５は独立のハードウェアで実現しても良いし、プログラムとＣＰＵ２で実現しても良い。本実施形態では、後者であるとする。なお、乱数は外部の装置から入力するようにしても構わない。
【００５１】
プログラム記憶部３は、例えばＲＯＭである。
なお、プログラム（本実施形態を実現するための手順を含むプログラム）を外部から（例えば、記録媒体から読み込んでもしくはネットワークを介して取得して）インストールする構成を採用することも可能である。このような場合、プログラム記憶部３には、例えばＥＥＰＲＯＭもしくはＲＡＭもしくはハードディスク装置などを用いることができる。
【００５２】
ランダムアクセス可能な不揮発性メモリ６は、例えばＲＡＭである。このメモリ６には、計算に必要なデータや計算途中のデータなどを格納する。
不揮発性メモリ７は、例えばＥＥＰＲＯＭである。このメモリ７には、生成された鍵などを格納する。
【００５３】
また、暗号装置１は、図示しない所望のインタフェースを介して外部からデータを入力し、また外部にデータを出力する。このインタフェースは、例えば、ユーザインタフェース、通信インタフェースなど、種々のものが考えられる。例えば、暗号装置１がＩＣカードである場合、所定の通信インタフェースを介して外部の計算機とデータの受け渡しを行なう。
【００５４】
そして、暗号装置１、所望の暗号機能、すなわち例えばこのインタフェースを介して入力されたデータに対して暗号化あるいは復号化などの処理を行ない、あるいはデータの認証処理を行ない、また外部の表示装置、通信回線あるいは記憶装置に対して、入力されたデータあるいは処理したデータなどを出力する機能を有するものとする。この機能は、例えばプログラムにより実現する。また、この機能をサブプログラムとして上記の素数生成のためのサブプログラムと鍵生成のためのサブプログラムとを含むプログラムに組み込んで実施することも可能である。
【００５５】
ところで、本実施形態では、素数判定に用いる素数を格納した素数テーブルを用いる。この素数テーブルは、ランダムアクセス可能な不揮発性メモリ６に格納する。ここでは、始めにワードサイズの２倍のビット長の素数を生成し、その素数を基にそれより大きい所定のサイズの素数を生成することを前提として、素数テーブルにはワードサイズ以下の素数を格納しておくものとする。例えば、ワードサイズが８ビットである場合、２５６以下のすべての素数（５３個の素数）を格納しておく。
【００５６】
図２に、公開鍵及び秘密鍵生成に用いる素数を生成する素数生成処理のフローチャートを示す。
処理１：まず、乱数生成部５においてワードサイズの２倍のビット長の奇数をランダムに生成する（ステップＳ１）。
【００５７】
処理２：生成された奇数について、素数テーブルに格納されているワードサイズ以下の素数を用いて演算部４において試行割算（エラトステネスのふるい）を行なう（ステップＳ２）。
【００５８】
処理３：生成された奇数が素数テーブル内の全ての素数で割り切れない場合、この奇数を素数と判定し、Ｆ０  に代入する。素数テーブル内のいずれかの素数で割り切れた場合、処理１に戻る（ステップＳ３）。
【００５９】
処理４：以下の処理ループのためのパラメータｉ＝０とする（ステップＳ４）。
処理５：素数Ｆｉ  を基に、乱数生成部５において、Ｒｉ  ＜Ｆｉ  を満たす乱数Ｒｉ  を生成し（ステップＳ５）、Ｎｉ  ＝２Ｒｉ  Ｆｉ  ＋１で表される素数候補Ｎｉ  を作る（ステップＳ６）。
【００６０】
処理６：素数候補Ｎｉ  に対し、素数判定の前処理として、素数テーブルに格納されている素数を用いて演算部４において試行割算を行なう（ステップＳ７）。処理７：素数候補Ｎｉ  が、素数テーブル内のいずれかの素数で割り切れた場合、素数候補Ｎｉ  は合成数であると判定し、処理５に戻る（ステップＳ８）。そして、Ｆｉ  の値はそのままで、乱数生成部５においてＲｉ  （Ｒｉ  ＜Ｆｉ  ）を生成し直し、新しい素数候補Ｎｉ  を生成する。
【００６１】
処理８：素数候補Ｎｉ  について、所定のａｉ  について、式（１）を満たすかどうか演算部４において計算する（フェルマーテスト）（ステップＳ９）。満たさない場合、処理５に戻る（ステップＳ１０）。
【００６２】
【数１】
0003626340.tif 000002
【００６３】
処理９：素数候補Ｎｉ  について、所定のａｉ  について、式（２）を満たすかどうか演算部４において計算する（ステップＳ１１）。満たさない場合、処理５に戻る（ステップＳ１２）。
【００６４】
【数２】
0003626340.tif 000003
【００６５】
処理１０：素数候補Ｎｉ  が所定のビットサイズに達していないならば、Ｆｉ  ＝Ｎｉ  、ｉ＋＝１（ｉを１増加）とし（ステップＳ１３，Ｓ１４）、処理５に戻る。素数候補Ｎｉ  が所定のビット長に達するように、Ｒｉ  のビット長を増加（Ｒｉ  ＜Ｆｉ  ）させることで調整する。
【００６６】
処理１１：以上のようにして、素数候補Ｎｉ  が所定のビットサイズに達したならば、素数Ｎｉ  を得る。
上記の処理８と処理９においては、ａｉ  ＝２を用いるのが好ましい。上記の試行割算では、ワードサイズ以下の素数を含む前記素数テーブルを使用するが、Ｆ０  以下の素数による試行割算を前処理として施すことで、殆どの合成数を除去することが可能である。よって、素数判定にかける素数候補が絞られることにより、効率良く素数判定を行なうことができる。
【００６７】
また、上記の判定式では、ａｉ  ＝２という小さな底の計算で処理するので計算が容易となる。通常、底ａｉ  は、２だけではなく、小さな素数から順に用いて素数判定処理を行なうが、ａｉ  をこのように変化させなくても支障はない。それは、ａｉ  ＝２のときに、素数候補が素数であるにもかかわらず、素数ではないと判定されるケースは非常に小さいからである。
【００６８】
よって、効率性と実用性を備えた底として、ａｉ  ＝２を用いる。上記の処理１１までの実行で、求められた素数のビットサイズがｎビットとすると、（素数−１）にｎ／２ビット程度の素数を持たせることができる。これにより、素因数分解法の一手法であるｐ−１法を回避できる。
【００６９】
さらにｐ＋１法に対処するためには、（素数＋１）にも大きなビットサイズの素数を持たせる必要がある。図２の処理を用いて素数を生成し、図３の処理でｐ±１法に対処できる素数を生成する。
【００７０】
処理１２：まず、図２の処理を用いて０．４ｎビットの素数（ｓ，ｔ）を生成する（ステップＳ２１，Ｓ２２）。
処理１３：０．５ｎビットの素数候補を、ｒ＝２ａｔ＋１となるように生成する（ステップＳ２３）。
【００７１】
処理１４：素数候補に対し、素数判定の前処理として、素数テーブルに格納されている素数を用いて演算部４において試行割算を行なう（ステップＳ２４）。素数候補が、素数テーブル内のいずれかの素数で割り切れた場合、素数候補Ｎは合成数であると判定し、ａ＋＝１のようにａの値を調整し、処理１３に戻る（ステップＳ２５）。
【００７２】
処理１５：素数候補について、式（３）を満たすかどうか演算部４において計算する（ステップＳ２６）。満たさない場合、ａ＋＝１のようにａの値を調整し、処理１３に戻る（ステップＳ２７）。
【００７３】
【数３】
0003626340.tif 000004
【００７４】
処理１６：素数候補について、式（４）を満たすかどうか演算部４において計算する（ステップＳ２８）。満たさない場合、ａ＋＝１のようにａの値を調整し、処理１４に戻る（ステップＳ２９）。
【００７５】
【数４】
0003626340.tif 000005
【００７６】
処理１７：ｎビットの素数Ｎを、Ｎ＝１＋２（ｂｓ−ｒ−１  （ｍｏｄ  ｓ））ｒとなるように生成し（ステップＳ３０）、上記の処理１４の試行割算および判定、処理１５の計算および判断、処理１６の計算および判断と同じ処理を行なう（ステップＳ３１〜Ｓ３６）。この試行割算で素数候補Ｎが合成数と判定された場合およびいずれかの計算で素数判定式が成立しない場合、ｂ＋＝１のようにｂの値を調整し、再度、上記一連の処理を行なう。
【００７７】
処理１８：生成した素数Ｎが所定のビット長を持つならば終了する（ステップＳ３７）。所定のビット長に達していないならば処理１７に戻り、素数候補Ｎが所定のビット長を持つようにｂ＋＝１のようにｂの値を調整し素数判定を行なう。
【００７８】
さて、以上のようにして素数を生成したら、次に、これら素数をもとに公開鍵及び秘密鍵を生成する。以下、各暗号方式における公開鍵及び秘密鍵の生成について説明する。
【００７９】
ＲＳＡ暗号における公開鍵及び秘密鍵の生成に際しては、上記の処理を用いて２個の素数ｐ、ｑを生成し、ｎ＝ｐｑを公開除数とし、ｅｄ＝１  （ｍｏｄ  ｌｃｍ（ｐ−１，ｑ−１））なるｅ、ｄをそれぞれ、秘密べき指数、公開べき指数として用いる（ｌｃｍは最小公倍数を表す）。
【００８０】
ラビン暗号における公開鍵及び秘密鍵で用いる素数ｐ、ｑは、式（５）、式（６）の制限があるので、ｐ、ｑ各々について、上記処理１６まで処理した後、処理１７の代わりに次の処理１７´を行なう。
【００８１】
【数５】
0003626340.tif 000006
【００８２】
処理１７´：ｐ＝２Ｆｐ  Ｒｐ  ＋１、ｑ＝２Ｆｑ  Ｒｑ  ＋１、（ｐ、ｑはｎビットの素数候補）、Ｆｐ  、Ｆｑ  は０．５ｎビットの素数、Ｒｐ  、Ｒｑ  は０．４ｎビットの乱数である。Ｆｐ  、Ｒｐ  は、処理１７の各々（ｂｓ−ｒ−１  （ｍｏｄ  ｓ））、ｒに相当する。Ｆｐ  Ｒｐ  とＦｑ  Ｒｑ  について、４｜Ｆｐ  Ｒｐ  −１、４｜Ｆｑ  Ｒｑ  −３を満たすものを探す。そして、ｐ、ｑについて、上記の処理１４の試行割算および判定、処理１５の計算および判断、処理１６の計算および判断と同じ処理を行なう（ステップＳ３１〜Ｓ３６）。
【００８３】
処理１７´で生成されたｐ、ｑを用いて、ｎ＝ｐｑを公開除数とし、ｅｄ＝１（ｍｏｄ  （１／２）・ｌｃｍ（ｐ−１，ｑ−１））なるｅ、ｄをそれぞれ、秘密べき指数、公開べき指数として用いる。
【００８４】
公開鍵暗号系で用いられるプラム整数ｍ＝ｐｑは、素数ｐ、ｑは、式（７）、式（８）の制限があるので、上記の処理１７´におけるＦｐ  Ｒｐ  とＦｑ  Ｒｑ  について、２｜Ｆｐ  Ｒｐ  −１、２｜Ｆｑ  Ｒｑ  −１を満たすものを探す。そして、ｐ、ｑについて、上記の処理１４の試行割算および判定、処理１５の計算および判断、処理１６の計算および判断と同じ処理を行なう（ステップＳ３１〜Ｓ３６）。
【００８５】
【数６】
0003626340.tif 000007
【００８６】
ＤＳＡの鍵に必要な素数は、上記の処理１７´において、素数候補がｐ＝２Ｒｐ  ｑｑ´＋１となるように素数ｑ´を生成し、ｐ−１に２個の素数を持たせ、素数判定を行なう。これにより、ｑ｜ｐ−１を満たすｐ、ｑから、ｇ＝ｈ（ｐ−１）／ｑ  （ｍｏｄ  ｐ）＞１なるｇと乱数ｘを用いて、ｙ＝ｇｘ    （ｍｏｄ  ｐ）を算出し、ｐ、ｑ、ｇ、ｙを公開鍵、ｘを秘密鍵として用いる。
【００８７】
以上のように本実施形態によれば、確定的素数判定方法と、素数Ｆ０  を素数判定するときに用いる（Ｆ０  ）１／２  以下の素数を格納した素数テーブルとを組合わせることによって、暗号装置のメモリ容量に対応したサイズのテーブルを利用することが可能になる。
【００８８】
したがって、豊富なメモリを持つパーソナルコンピュータのような暗号装置でなく、メモリ容量が限定されている暗号装置（例えばＩＣカード）であっても装置上に容易に公開鍵暗号における公開鍵及び秘密鍵の生成機能を実装することが可能になる。
【００８９】
また、扱うデータ量が少ないので、高速に鍵を生成することができる。
また、確定的素数判定方法を用いるので、確実に素数を得ることができ、安全な鍵を得ることができる。
【００９０】
また、素因数分解による攻撃に強い鍵を得ることができる。
また、装置に鍵生成機能を持たせることにより、鍵に対する安全性を向上させ、鍵の管理を容易にすることができる。
【００９１】
また、個々の暗号装置内で鍵を生成し、暗号装置内で暗号処理及び復号処理を行なうならば、鍵は決して暗号装置外に出ることがないので、鍵に対する高い安全性を保つことができる。
【００９２】
なお、前述したように素数テーブルをメモリ６内に設ける代わりに、素数テーブルに相当するものをプログラムの中に作り込むようにしても良い。
また、本実施形態では、素数をもとに公開鍵暗号における秘密鍵と公開鍵を生成するものについて説明したが、前述した方法で生成した素数をもとに共通鍵を生成しても構わない。
【００９３】
次に、鍵生成プログラムの実行制御について説明する。
暗号装置１において、鍵生成プログラムが起動され、一旦、鍵が生成されたならば、その鍵は不揮発性メモリ７に格納される。本実施形態では、それと同時に、同じく不揮発性メモリ７に存在する鍵生成制御ビットを立てるようにする。
【００９４】
この鍵生成制御ビットにより、鍵生成プログラムの実行を制御する。つまり、鍵生成プログラムを実行するのに先だって、鍵生成制御ビットを調べ、鍵生成制御ビットがオフの状態ならば、鍵生成プログラムを実行させ、オンの状態ならば鍵生成プログラムを起動しない。
【００９５】
これによって、暗号装置１が生成した鍵に対し、鍵生成プログラムの再起動等により、既に生成された鍵が破壊されることを防ぐことができる。
その他の鍵生成プログラムの実行制御方法として、予め、暗号装置１内に保存されている秘密の認証コードと同一コードが入力されたときのみ鍵生成プログラムを起動する方法も考えられる。この方法は、認証コードをマスクに書き込んでおくかまたは発行時の初期段階で書き込み、後の鍵生成時に同一コードを入力し鍵生成プログラムを起動するものである。この鍵生成プログラムの実行制御方法は、既に生成された暗号鍵を変更する場合にも用いることもできる。つまり、正しい認証コードを入力した場合にのみ、鍵生成プログラムが実行可能であり、生成された暗号鍵を不揮発性メモリ７に格納することができる。
【００９６】
次に、図４を参照しながら暗号装置９内に格納されている鍵の検証について説明する。
まず、鍵が生成されたならば、直ちに、生成された鍵のハッシュ値を計算し、生成された鍵（図中１１）と、そのハッシュ値（図中１０）とを対応付けて不揮発性メモリ７に保存しておく。
【００９７】
しかして、暗号処理や復号処理あるいは認証処理にて鍵を使用する前に、不揮発性メモリ７に格納されている鍵（図中１１）のハッシュ値を計算し（図中１２）、予め不揮発性メモリ７に保存されていたハッシュ値（図中１０）と一致判定部１３において比較する。一致したならば成功を示す制御信号を出力して暗号処理や復号処理の実行を可能とし、一致しないならば、失敗を示す制御信号を出力して暗号処理や復号処理の実行を不可とする。
【００９８】
そして、制御信号が成功、すなわちハッシュ値の一致を示している場合にのみ、暗号処理を起動し、制御信号が失敗、すなわちハッシュ値の不一致を示している場合には、暗号処理を起動させない。
【００９９】
このように暗号装置９で生成された鍵を用いて暗号処理や復号処理を行なう際に、格納されている鍵の検証を行なうことによって、何らかの原因で破壊された鍵による暗号処理や復号処理を回避することができる。
【０１００】
次に、図５を参照しながらユーザ側と公開鍵を管理・公開するセンター側との間でのユーザの鍵の正当性の確認について説明する。
暗号装置１９で生成された公開鍵及び秘密鍵については、センター１７がそれらの正当性を確認する手段が必要である。その一手法として、図５に示す方法がある。
【０１０１】
まず、センター１７は、情報処理装置１８から、暗号装置１９により生成された公開鍵ｋを受け取る。
次に、センター１７は、乱数Ｒを生成し（図中２０）、その乱数Ｒを暗号装置１９により生成された公開鍵ｋを用いて暗号化し（図中２１）、情報処理装置１８へ送信する（図中２２）。
【０１０２】
情報処理装置１８は、外部インタフェース３０を介して暗号装置１９に公開鍵ｋで暗号化された乱数Ｒを送信する。
暗号装置１９は、その公開鍵ｋで暗号化された乱数Ｒを、公開鍵とペアである秘密鍵を用いて復号化する（図中２３）。
【０１０３】
復号化された乱数Ｒは、暗号装置１９から情報処理装置１８を介してセンターに送信する（図中２５）。
そして、センター１７では、一致判定部２６により自ら生成した乱数と暗号装置１９から送信された乱数について検証を行なう。
【０１０４】
一致したならば、暗号装置１９はセンター１７が所有する公開鍵に対して正当な秘密鍵を保持しているので、センター１７は暗号装置１９に公開鍵証明書を発行する。
【０１０５】
このように、個々の暗号装置が秘密鍵および公開鍵を生成することにより、鍵を管理するセンターは、個々の暗号装置に対し鍵生成及び配送をする必要がなくなり、鍵生成及び管理に伴う処理の負担が軽減される。
【０１０６】
なお、本発明は、コンピュータに所定の手順を実行させるための（あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるための）プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０１０７】
【発明の効果】
本発明によれば、予め定められたｎビット以下の値のすべての素数をもとに２ｎビット以下の素数を生成し、この生成された素数をもとに順次大きな素数を生成して所定のビット長の第２の素数生成するので、必要なメモリ容量を少なく済ませることができる。
【０１０８】
したがって、メモリ容量が限定されている暗号装置に鍵生成機能を実装することが可能になる。また、扱うデータ量が少ないので、高速に鍵を生成することができる。
【０１０９】
また、外部とのやり取りなしに暗号装置内で鍵を生成するので、鍵に対する安全性を向上させることができるとともに、鍵の管理を容易にすることができる。また、本発明によれば、暗号装置内で既に鍵が生成されている場合、再度鍵が生成されないようにするので、既に生成された鍵が新たに生成された鍵で破壊されるようなことを防ぐことができる。
【０１１０】
また、本発明によれば、暗号装置内で生成された鍵を用いて暗号処理や復号処理を行なう際に、格納されている鍵の検証を行なうことによって、何らかの原因で破壊された鍵による暗号処理や復号処理を回避することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る暗号化装置の構成を示す図
【図２】同実施形態に係る素数生成手順を示すフローチャート
【図３】同実施形態に係る素数生成手順を示すフローチャート
【図４】同実施形態に係る暗号装置における鍵検証の一例を示す図
【図５】同実施形態に係る鍵の正当性検証の一例を示す図
【符号の説明】
１…暗号装置
２…ＣＰＵ
３…プログラム記憶部
４…演算部
５…乱数生成部
６…ランダムアクセス可能な不揮発メモリ
７…不揮発メモリ
８…バス
９…暗号装置
１２…ハッシュ値算出部
１３，２６…一致判定部
１７…センター
１８…方法処理装置
１９…暗号装置
【図１】
0003626340.tif 000008
【図２】
0003626340.tif 000009
【図３】
0003626340.tif 000010
【図４】
0003626340.tif 000011
【図５】
0003626340.tif 000012