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