(57)【要約】【課題】  ３回より少ないランダム関数演算と、緊密な安全性とを両立させる。【解決手段】  暗号文ｙ＝ｃ‖ｔ又は署名σ＝ｃ’‖ｔを２つのデータを連結した連結データとして作成し、且つこの連結データを一方のデータ（必要な部分ｓ）のみに公開鍵暗号方式を用いて作成するので、公開鍵暗号方式の落し戸付一方向性関数の一方向性に対して緊密な安全性を実現できる。更に、第１のランダム関数Ｈ’の出力サイズを制限することにより、従来のＯＡＥＰ＋＋−ＥＳ方式におけるビット拡張用のランダム関数Ｇを不要としたので、ランダム関数の使用を２回に削減できる。【選択図】  図１
2005204111.tif 000002
【特許請求の範囲】
【請求項１】
２つのランダム関数を用いて公開鍵暗号方式により暗号化処理及び署名処理を実行可能な暗号化及び署名装置に用いられる暗号化及び署名方法であって、
前記暗号化処理又は署名処理の対象データｘが入力される工程と、
前記対象データｘに連結される乱数ｒを生成する工程と、
前記対象データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る工程と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記連結データｘ‖ｒのサイズ以上のサイズを有する第１ランダムデータｗを生成する工程と、
前記連結データｘ‖ｒと前記第１ランダムデータｗとの排他的論理和を算出し、処理対象データｓを生成する工程と、
前記処理対象データｓに第２のランダム関数Ｈを施して、前記第１ランダムデータｗのサイズと同じサイズを有する第２ランダムデータＨ（ｓ）を生成する工程と、
前記第１ランダムデータｗと前記第２ランダムデータＨ（ｓ）との排他的論理和を計算し、パディングデータｔを生成する工程と、
前記公開鍵暗号方式により、前記処理対象データｓに暗号化処理又は署名処理を実行する工程と、
前記実行により得られた暗号化処理データｃ又は署名処理データｃ’と前記パディングデータｔとを連結し、得られた暗号文ｃ‖ｔ又は署名ｃ’‖ｔを出力する工程と、
を備えたことを特徴とする暗号化及び署名方法。
【請求項２】
２つのランダム関数を用いて公開鍵暗号方式により暗号化処理及び署名処理を実行可能な暗号化及び署名装置であって、
前記暗号化処理又は署名処理の対象データｘを入力するための入力手段と、
前記対象データｘに連結される乱数ｒを生成する乱数生成手段と、
前記対象データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る第１の連結手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記連結データｘ‖ｒのサイズ以上のサイズを有する第１ランダムデータｗを生成する第１のランダム関数演算手段と、
前記連結データｘ‖ｒと前記第１ランダムデータｗとの排他的論理和を算出し、処理対象データｓを生成する処理対象データ生成手段と、
前記処理対象データｓに第２のランダム関数Ｈを施して、前記第１ランダムデータｗのサイズと同じサイズを有する第２ランダムデータＨ（ｓ）を演算する第２のランダム関数演算手段と、
前記第１ランダムデータｗと前記第２ランダムデータＨ（ｓ）との排他的論理和を計算し、パディングデータｔを生成するパディングデータ生成手段と、
前記公開鍵暗号方式により、前記処理対象データｓに暗号化処理又は署名処理を実行する暗号化／署名手段と、
前記実行により得られた暗号化処理データｃ又は署名処理データｃ’と前記パディングデータｔとを連結する第２の連結手段と、
前記第２の連結手段により得られた暗号文ｃ‖ｔ又は署名ｃ’‖ｔを出力する出力手段と、
を備えたことを特徴とする暗号化及び署名装置。
【請求項３】
入力された平文データｘと公開鍵暗号方式の公開鍵ｐｋとに基づいて、前記平文データｘを暗号化処理し、得られた暗号文を出力する暗号化装置であって、
前記平文データｘに連結される乱数ｒを生成する乱数生成手段と、
前記平文データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る連結手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記連結データｘ‖ｒのサイズ以上のサイズを有する第１ランダムデータｗを生成する第１のランダム関数演算手段と、
前記連結データｘ‖ｒと前記第１ランダムデータｗとの排他的論理和を算出し、処理対象データｓを生成する処理対象データ生成手段と、
前記処理対象データｓに第２のランダム関数Ｈを施して、前記第１ランダムデータｗのサイズと同じサイズを有する第２ランダムデータＨ（ｓ）を演算する第２のランダム関数演算手段と、
前記第１ランダムデータｗと前記第２ランダムデータＨ（ｓ）との排他的論理和を計算し、パディングデータｔを生成するパディングデータ生成手段と、
前記公開鍵暗号方式により、前記処理対象データｓを前記公開鍵ｐｋに基づいて暗号化処理する暗号化手段と、
前記暗号化処理により得られた暗号化処理データｃと前記パディングデータｔとを連結し、暗号文ｃ‖ｔを得る第２の連結手段と、
前記暗号文ｃ‖ｔを出力する出力手段と、
を備えたことを特徴とする暗号化装置。
【請求項４】
平文データｘ及び乱数ｒの連結データｘ‖ｒに第１のランダム関数Ｈ’を施した第１ランダムデータｗ＝Ｈ’（ｘ‖ｒ）と、前記連結データｘ‖ｒ及び前記第１ランダムデータｗの排他的論理和から得られる処理対象データｓと、前記処理対象データｓに第２のランダム関数Ｈを施して得られる第２ランダムデータＨ（ｓ）と、前記第１及び第２ランダムデータｗ，Ｈ（ｓ）の排他的論理和から得られるパディングデータｔと、公開鍵暗号方式により、前記処理対象データｓを公開鍵ｐｋに基づいて暗号化処理して得られる暗号化処理データｃとから作成され、前記暗号化処理データｃと前記パディングデータｔとを連結して得られる暗号文ｃ‖ｔが入力されたとき、この暗号文ｃ‖ｔと公開鍵暗号方式の秘密鍵ｓｋとに基づいて、前記暗号文ｃ‖ｔを復号処理し、得られた平文データｘを出力する復号装置であって、
前記暗号文ｃ‖ｔを暗号化処理データｃとパディングデータｔとに分割する第１分割手段と、
前記公開鍵暗号方式により、前記暗号化処理データｃを前記秘密鍵ｓｋに基づいて復号処理し、処理対象データｓを得る復号手段と、
前記処理対象データｓに第２のランダム関数Ｈを施して、第２ランダムデータＨ（ｓ）を演算する第２のランダム関数演算手段と、
前記第２ランダムデータＨ（ｓ）と前記パディングデータｔとの排他的論理和を算出し、第１の第１ランダムデータｗを生成する第１のランダムデータ生成手段と、
前記第１ランダムデータｗと前記処理対象データｓとの排他的論理和を算出し、連結データｘ‖ｒを生成する連結データ生成手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗ’を演算し、第２の第１ランダムデータｗ’を生成する第２のランダムデータ生成手段と、
前記第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する判定手段と、
この判定の結果、両者ｗ，ｗ’が互いに同一のとき、前記連結データｘ‖ｒを分割し、平文データｘと乱数ｒを得る第２分割手段と、
この平文データｘを出力する出力手段と、
を備えたことを特徴とする復号装置。
【請求項５】
入力された文書データｘと公開鍵暗号方式の秘密鍵ｓｋとに基づいて、前記文書データｘに署名処理し、得られた署名を出力する署名装置であって、
前記文書データｘに連結される乱数ｒを生成する乱数生成手段と、
前記文書データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る連結手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記連結データｘ‖ｒのサイズ以上のサイズを有する第１ランダムデータｗを生成する第１のランダム関数演算手段と、
前記連結データｘ‖ｒと前記第１ランダムデータｗとの排他的論理和を算出し、処理対象データｓを生成する処理対象データ生成手段と、
前記処理対象データｓに第２のランダム関数Ｈを施して、前記第１ランダムデータｗのサイズと同じサイズを有する第２ランダムデータＨ（ｓ）を演算する第２のランダム関数演算手段と、
前記第１ランダムデータｗと前記第２ランダムデータＨ（ｓ）との排他的論理和を計算し、パディングデータｔを生成するパディングデータ生成手段と、
前記公開鍵暗号方式により、前記処理対象データｓを前記秘密鍵ｓｋに基づいて署名処理する署名手段と、
前記署名処理により得られた署名処理データｃ’と前記パディングデータｔとを連結し、署名ｃ’‖ｔを得る第２の連結手段と、
前記署名ｃ’‖ｔを出力する出力手段と、
を備えたことを特徴とする署名装置。
【請求項６】
文書データｘ及び乱数ｒの連結データｘ‖ｒに第１のランダム関数Ｈ’を施した第１ランダムデータｗ＝Ｈ’（ｘ‖ｒ）と、前記連結データｘ‖ｒ及び前記第１ランダムデータｗの排他的論理和から得られる処理対象データｓと、前記処理対象データｓに第２のランダム関数Ｈを施して得られる第２ランダムデータＨ（ｓ）と、前記第１及び第２ランダムデータｗ，Ｈ（ｓ）の排他的論理和から得られるパディングデータｔと、公開鍵暗号方式により、前記処理対象データｓを秘密鍵ｓｋに基づいて署名処理して得られる署名処理データｃ’とから作成され、前記署名処理データｃ’と前記パディングデータｔとを連結して得られる署名ｃ’‖ｔが入力されたとき、この署名ｃ’‖ｔと公開鍵暗号方式の公開鍵ｐｋとに基づいて、前記署名ｃ’‖ｔの正当性を検証する署名検証装置であって、
前記署名ｃ’‖ｔを署名処理データｃ’とパディングデータｔとに分割する第１分割手段と、
前記公開鍵暗号方式により、前記署名処理データｃ’を前記公開鍵ｐｋに基づいて復元処理し、処理対象データｓを得る復元手段と、
前記処理対象データｓに第２のランダム関数Ｈを施して、第２ランダムデータＨ（ｓ）を演算する第２のランダム関数演算手段と、
前記第２ランダムデータＨ（ｓ）と前記パディングデータｔとの排他的論理和を算出し、第１の第１ランダムデータｗを生成する第１のランダムデータ生成手段と、
前記第１ランダムデータｗと前記処理対象データｓとの排他的論理和を算出し、連結データｘ‖ｒを生成する連結データ生成手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗ’を演算し、第２の第１ランダムデータｗ’を生成する第２のランダムデータ生成手段と、
前記第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する判定手段と、
この判定の結果、両者ｗ，ｗ’が互いに同一のとき、正当性をもつ署名として前記署名ｃ’‖ｔを受理する署名受理手段と、
を備えたことを特徴とする署名検証装置。
【請求項７】
２つのランダム関数を用いて公開鍵暗号方式により暗号化処理及び署名処理を実行可能な暗号化及び署名装置のコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記暗号化処理又は署名処理の対象データｘが入力される手段、
前記対象データｘに連結される乱数ｒを生成する手段、
前記対象データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る手段、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記連結データｘ‖ｒのサイズ以上のサイズを有する第１ランダムデータｗを生成する手段、
前記連結データｘ‖ｒと前記第１ランダムデータｗとの排他的論理和を算出し、処理対象データｓを生成する手段、
前記処理対象データｓに第２のランダム関数Ｈを施して、前記第１ランダムデータｗのサイズと同じサイズを有する第２ランダムデータＨ（ｓ）を生成する手段、
前記第１ランダムデータｗと前記第２ランダムデータＨ（ｓ）との排他的論理和を計算し、パディングデータｔを生成する手段、
前記公開鍵暗号方式により、前記処理対象データｓに暗号化処理又は署名処理を実行する手段、
前記実行により得られた暗号化処理データｃ又は署名処理データｃ’と前記パディングデータｔとを連結し、得られた暗号文ｃ‖ｔ又は署名ｃ’‖ｔを出力する手段、
として機能させるためのプログラム。
【請求項８】
２つのランダム関数を用いて確定的な公開鍵暗号方式により暗号化処理及び署名処理を実行可能な暗号化及び署名装置に用いられる暗号化及び署名方法であって、
前記暗号化処理又は署名処理の対象データｘが入力される工程と、
前記対象データｘに連結される乱数ｒを生成する工程と、
前記対象データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る工程と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記公開鍵暗号方式の入力サイズ以上のサイズを有する第１ランダムデータｗを生成する工程と、
前記第１ランダムデータｗに第２のランダム関数Ｇを施して、前記連結データｘ‖ｒのサイズ以上のサイズを有する第２ランダムデータＧ（ｗ）を生成する工程と、
前記連結データｘ‖ｒと前記第２ランダムデータＧ（ｗ）との排他的論理和を算出し、パディングデータｓを生成する工程と、
前記公開鍵暗号方式により、前記第１ランダムデータｗに暗号化処理又は署名処理を実行する工程と、
前記実行により得られた暗号化処理データｃ又は署名処理データｃ’と前記パディングデータｓとを連結し、得られた暗号文ｓ‖ｃ又は署名ｓ‖ｃ’を出力する工程と、
を備えたことを特徴とする暗号化及び署名方法。
【請求項９】
２つのランダム関数を用いて確定的な公開鍵暗号方式により暗号化処理及び署名処理を実行可能な暗号化及び署名装置であって、
前記暗号化処理又は署名処理の対象データｘを入力するための入力手段と、
前記対象データｘに連結される乱数ｒを生成する乱数生成手段と、
前記対象データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る第１の連結手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記公開鍵暗号方式の入力サイズ以上のサイズを有する第１ランダムデータｗを生成する第１のランダム関数演算手段と、
前記第１ランダムデータｗに第２のランダム関数Ｇを施して、前記連結データｘ‖ｒのサイズ以上のサイズを有する第２ランダムデータＧ（ｗ）を演算する第２のランダム関数演算手段と、
前記連結データｘ‖ｒと前記第２ランダムデータＧ（ｗ）との排他的論理和を算出し、パディングデータｓを生成するパディングデータ生成手段と、
前記公開鍵暗号方式により、前記第１ランダムデータｗに暗号化処理又は署名処理を実行する暗号化／署名手段と、
前記実行により得られた暗号化処理データｃ又は署名処理データｃ’と前記パディングデータｓとを連結する第２の連結手段と、
前記第２の連結手段により得られた暗号文ｓ‖ｃ又は署名ｓ‖ｃ’を出力する出力手段と、
を備えたことを特徴とする暗号化及び署名装置。
【請求項１０】
入力された平文データｘと確定的な公開鍵暗号方式の公開鍵ｐｋとに基づいて、前記平文データｘを暗号化処理し、得られた暗号文を出力する暗号化装置であって、
前記平文データｘに連結される乱数ｒを生成する乱数生成手段と、
前記平文データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る連結手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記公開鍵暗号方式の入力サイズ以上のサイズを有する第１ランダムデータｗを生成する第１のランダム関数演算手段と、
前記第１ランダムデータｗに第２のランダム関数Ｇを施して、前記連結データｘ‖ｒのサイズ以上のサイズを有する前記第２ランダムデータＧ（ｗ）を演算する第２のランダム関数演算手段と、
前記連結データｘ‖ｒと前記第２ランダムデータＧ（ｗ）との排他的論理和を算出し、パディングデータｓを生成するパディングデータ生成手段と、
前記公開鍵暗号方式により、前記第１ランダムデータｗを前記公開鍵ｐｋに基づいて暗号化処理する暗号化手段と、
前記暗号化処理により得られた暗号化処理データｃと前記パディングデータｓとを連結し、暗号文ｓ‖ｃを得る第２の連結手段と、
前記暗号文ｓ‖ｃを出力する出力手段と、
を備えたことを特徴とする暗号化装置。
【請求項１１】
平文データｘ及び乱数ｒの連結データｘ‖ｒに第１のランダム関数Ｈ’を施した第１ランダムデータｗ＝Ｈ’（ｘ‖ｒ）と、前記第１ランダムデータｗに第２のランダム関数Ｇを施して得られる第２ランダムデータＧ（ｗ）と、前記連結データｘ‖ｒ及び前記第２ランダムデータＧ（ｗ）の排他的論理和から得られるパディングデータｓと、確定的な公開鍵暗号方式により、前記第１ランダムデータｗを公開鍵ｐｋに基づいて暗号化処理して得られる暗号化処理データｃとから作成され、前記暗号化処理データｃと前記パディングデータｓとを連結して得られる暗号文ｓ‖ｃが入力されたとき、この暗号文ｓ‖ｃと前記公開鍵暗号方式の秘密鍵ｓｋとに基づいて、前記暗号文ｓ‖ｃを復号処理し、得られた平文データｘを出力する復号装置であって、
前記暗号文ｓ‖ｃをパディングデータｓと暗号化処理データｃとに分割する第１分割手段と、
前記公開鍵暗号方式により、前記暗号化処理データｃを前記秘密鍵ｓｋに基づいて復号処理し、第１の第１ランダムデータｗを得る復号手段と、
前記第１の第１ランダムデータｗに第２のランダム関数Ｇを施して、第２ランダムデータＧ（ｗ）を演算する第２のランダム関数演算手段と、
前記第２ランダムデータＧ（ｗ）と前記パディングデータｓとの排他的論理和を算出し、連結データｘ‖ｒを生成する連結データ生成手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗ’を演算し、第２の第１ランダムデータｗ’を生成するランダムデータ生成手段と、
前記第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する判定手段と、
この判定の結果、両者ｗ，ｗ’が互いに同一のとき、前記連結データｘ‖ｒを分割し、平文データｘと乱数ｒを得る第２分割手段と、
この平文データｘを出力する出力手段と、
を備えたことを特徴とする復号装置。
【請求項１２】
入力された文書データｘと確定的な公開鍵暗号方式の秘密鍵ｓｋとに基づいて、前記文書データｘに署名処理し、得られた署名を出力する署名装置であって、
前記文書データｘに連結される乱数ｒを生成する乱数生成手段と、
前記文書データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る連結手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記公開鍵暗号方式の入力サイズ以上のサイズを有する第１ランダムデータｗを生成する第１のランダム関数演算手段と、
前記第１ランダムデータｗに第２のランダム関数Ｇを施して、前記連結データｘ‖ｒのサイズ以上のサイズを有する前記第２ランダムデータＧ（ｗ）を演算する第２のランダム関数演算手段と、
前記連結データｘ‖ｒと前記第２ランダムデータＧ（ｗ）との排他的論理和を算出し、パディングデータｓを生成するパディングデータ生成手段と、
前記公開鍵暗号方式により、前記第１ランダムデータｗを前記秘密鍵ｓｋに基づいて署名処理する署名手段と、
前記署名処理により得られた署名処理データｃ’と前記パディングデータｓとを連結し、署名ｓ‖ｃ’を得る第２の連結手段と、
前記署名ｓ‖ｃ’を出力する出力手段と、
を備えたことを特徴とする署名装置。
【請求項１３】
文書データｘ及び乱数ｒの連結データｘ‖ｒに第１のランダム関数Ｈ’を施した第１ランダムデータｗ＝Ｈ’（ｘ‖ｒ）と、前記第１ランダムデータｗに第２のランダム関数Ｇを施して得られる第２ランダムデータＧ（ｗ）と、前記連結データｘ‖ｒ及び前記第２ランダムデータＧ（ｗ）の排他的論理和から得られるパディングデータｓと、確定的な公開鍵暗号方式により、前記第１ランダムデータｗを秘密鍵ｓｋに基づいて署名処理して得られる署名処理データｃ’とから作成され、前記署名処理データｃ’と前記パディングデータｓとを連結して得られる署名ｓ‖ｃ’が入力されたとき、この署名ｓ‖ｃ’と前記公開鍵暗号方式の公開鍵ｐｋとに基づいて、前記署名ｓ‖ｃ’の正当性を検証する署名検証装置であって、
前記署名ｓ‖ｃ’をパディングデータｓと署名処理データｃ’とに分割する第１分割手段と、
前記公開鍵暗号方式により、前記署名処理データｃ’を前記公開鍵ｐｋに基づいて復元処理し、第１の第１ランダムデータｗを得る復元手段と、
前記第１の第１ランダムデータｗに第２のランダム関数Ｇを施して、第２ランダムデータＧ（ｗ）を演算する第２のランダム関数演算手段と、
前記第２ランダムデータＧ（ｗ）と前記パディングデータｓとの排他的論理和を算出し、連結データｘ‖ｒを生成する連結データ生成手段と、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗ’を演算し、第２の第１ランダムデータｗ’を生成する第２のランダムデータ生成手段と、
前記第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する判定手段と、
この判定の結果、両者ｗ，ｗ’が互いに同一のとき、正当性をもつ署名として前記署名ｓ‖ｃ’を受理する署名受理手段と、
を備えたことを特徴とする署名検証装置。
【請求項１４】
２つのランダム関数を用いて確定的な公開鍵暗号方式により暗号化処理及び署名処理を実行可能な暗号化及び署名装置のコンピュータに用いられるプログラムであって、
前記コンピュータを、
前記暗号化処理又は署名処理の対象データｘが入力される手段、
前記対象データｘに連結される乱数ｒを生成する手段、
前記対象データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る手段、
前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記公開鍵暗号方式の入力サイズ以上のサイズを有する第１ランダムデータｗを生成する手段、
前記第１ランダムデータｗに第２のランダム関数Ｇを施して、前記連結データｘ‖ｒのサイズ以上のサイズを有する第２ランダムデータＧ（ｗ）を生成する手段、
前記連結データｘ‖ｒと前記第２ランダムデータＧ（ｗ）との排他的論理和を計算し、パディングデータｓを生成する手段、
前記公開鍵暗号方式により、前記第１ランダムデータｗに暗号化処理又は署名処理を実行する手段、
前記実行により得られた暗号化処理データｃ又は署名処理データｃ’と前記パディングデータｓとを連結し、得られた暗号文ｓ‖ｃ又は署名ｓ‖ｃ’を出力する手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号方式を用いた暗号化及び署名方法、装置及びプログラムに係り、特に、３回より少ないランダム関数演算と、緊密な安全性とを両立し得る暗号化及び署名方法、装置及びプログラムに関する。
【背景技術】
【０００２】
一般に、暗号方法は、共通鍵暗号方式と公開鍵暗号方式との二種類に類別できる。公開鍵暗号方式は、共通鍵方式で問題となる鍵配送を不要とする利点がある。  
例えば公開鍵暗号方式においては、各利用者Ａ，Ｂ，…は、公開鍵と秘密鍵との組を生成し、公開鍵を公開簿に登録する。ここで、各利用者Ａ，Ｂ，…は、利用者の総数とは無関係に、１組の鍵のみを用意すればよい。利用時には、例えば利用者Ａは、公開簿内の利用者Ｂの公開鍵を用いて暗号文を生成し、この暗号文を利用者Ｂに送信する。利用者Ｂは、受信した暗号文を自己の秘密鍵で復号する。このように、公開鍵暗号方式は、利用者Ａ，Ｂ間の鍵配送を不要としている。代表的な公開鍵暗号方式としては、ＲＳＡ（Rivest- Shamir- Adleman）暗号、ＥｌＧａｍａｌ暗号、楕円曲線暗号などが挙げられる。
【０００３】
以上のような公開鍵暗号方式は、ＲＳＡ関数に代表される落し戸付一方向性関数を利用している。落し戸付一方向性関数とは、ある向きの計算が容易に実行可能であるのに対し、逆向きの計算が秘密情報無しでは実行困難であるような関数である。
【０００４】
これにより、公開鍵暗号方式では、暗号文送信者がある向きの計算により暗号文を生成し、暗号文受信者が秘密情報を用いた逆向きの計算により暗号文を復号している。なお、第三者は秘密情報を持たないので、暗号文を盗聴しても逆向きの計算が困難である。
【０００５】
このような落し戸付一方向性関数の性質を暗号方式とは逆向きに使うことで、署名方式が実現される。署名方式においては、秘密情報を持つ署名者のみが、第三者に検証可能な署名を生成できる。例えば各利用者Ａ，Ｂ，…は、公開鍵と秘密鍵との組を生成し、公開鍵を公開簿に登録する。利用時には、例えば利用者Ａは、自己の秘密鍵を用いて文書から署名を生成し、文書と署名を利用者Ｂに送信する。利用者Ｂは、公開簿内の利用者Ａの公開鍵を用いて署名を復号し、署名と文書を比較して署名の正当性を検証する。代表的な署名方式としては、ＲＳＡ署名、ＥｌＧａｍａｌ署名、ＤＳＡ（Digital Signature Algorithm）などがある。
【０００６】
一方、上述した公開鍵暗号方式及び署名方式には、受動的な攻撃方法と能動的な攻撃方法が存在する。公開鍵暗号方式の場合、受動的な攻撃方法とは、攻撃者が公開情報のみを利用し、暗号文から平文を探索する方法である。能動的な攻撃方法とは、攻撃者が自らが自由に選んだ暗号文を正規の受信者に復号してもらい、復号結果を受け取れる環境下で、公開情報と暗号文から平文を探索する方法である。
【０００７】
署名方式の場合も同様であり、受動的な攻撃方法とは、攻撃者が公開情報のみを利用し、任意の文書に対する署名を出力する方法である。能動的な攻撃方法とは、攻撃者が正規の署名者に自らが自由に選んだ文書の署名を生成してもらえる環境下で、公開情報を利用し、任意の文書に対する署名を出力する方法である。
【０００８】
公開鍵暗号方式及び署名方式のいずれにしても、能動的攻撃方法は受動的攻撃方法よりも強力な攻撃方法である。能動的攻撃方法に対しても安全な暗号方式や署名方式を構成することは、より強い安全性を保証できることを意味する。
【０００９】
ここで、公開鍵暗号方式の場合、ＲＳＡ暗号のような確定的な暗号に基づき、能動的攻撃に強い暗号方式として、ベラル（Bellare）とロガウェイ（Rogaway）により、ＯＡＥＰ（Optimal Asymmetric Encryption Padding）が提案されている。ＯＡＥＰでは、暗号化したい平文を乱数を用いてパディングし、得られたパディングデータにＲＳＡ暗号などの落し戸付一方向性関数を作用させている。
【００１０】
一方、署名方式の場合、ＲＳＡ署名のような確定的な署名に基づき、能動的攻撃に強い署名方式として、前述したベラルとロガウェイにより、ＰＳＳ（Probabilistic Signature Scheme）が提案されている。ＰＳＳでは、署名したい文書を乱数を用いてパディングし、得られたパディングデータにＲＳＡ署名などの落し戸付一方向性関数を作用させている。
【００１１】
しかしながら、これらＯＡＥＰとＰＳＳは、パディングデータの生成方法（以下、パディング方式という）が互いに異なっている。このため、暗号方式（ＯＡＥＰ）と署名方式（ＰＳＳ）を実装する場合、２つのパディング方式を実装することから、実装サイズが大きくなる問題がある。
【００１２】
また、ＯＡＥＰとＰＳＳを実装する場合、両方式の鍵の組を共通化した場合に安全性が保証できるか否かが不明であることから、鍵の組を各方式毎に用意する必要がある。このため、鍵生成処理コストが増加し、鍵の保存領域も大きくなる問題がある。
【００１３】
これらの問題を解決する観点から、コロン（Coron）らは単一のパディング方式と鍵の組で、安全に暗号方式と署名方式を実現できるＰＳＳ−ＥＳ方式を提案している（例えば、非特許文献１参照）。
【００１４】
ＰＳＳ−ＥＳ方式では、図１７（ａ）に示すように、各利用者は、暗号文ｙを生成する場合と、署名σを生成する場合とで同一のパディングデータｓ‖ｗの生成処理を行う。なお、暗号文ｙを生成する場合には受信者の公開鍵ｐｋを用い、署名σを生成する場合には自らの秘密鍵ｓｋを用いる。なお、同図中、符号ｒは乱数であり、符号Ｈ’及びＧはランダム関数である。符号ｗは、平文ｘと乱数ｒの連接データｘ‖ｒにランダム関数Ｈ’を施したランダムデータ（ｗ＝Ｈ’（ｘ‖ｒ））である。なお、ランダム関数とは、例えばＳＨＡ（Secure Hash Algorithm）やＭＤ５（Message Digest Algorithm 5）などのハッシュ関数である。
【００１５】
このＰＳＳ−ＥＳ方式は、暗号方式の攻撃方法と署名方式の攻撃方法の両方を踏まえた安全性証明がなされており、２回のランダム関数Ｈ’，Ｇと、単一の鍵の組とを用いて暗号方式及び署名方式の安全性が保証される。
【００１６】
しかしながら、ＰＳＳ−ＥＳ方式の暗号方式と、落し戸付一方向性関数の逆関数計算困難さとの間は、安全性が緊密ではないことが知られている。ここで、緊密とは、ある問題を解く計算困難さと、別の問題を解く計算困難さの間の乖離度をいう。例えば緊密であるとは、落し戸付一方向性関数の逆関数演算を行なうことと、暗号方式を破ることとが同じ位に困難であることをいう。
【００１７】
一般に、暗号方式の安全性を示すには、暗号方式を破る問題を落し戸付一方向性関数の一方向性を破る問題に帰着させる。すなわち、落し戸付一方向性関数の一方向性を破る問題が困難であることにより、暗号方式の安全性を示している。このとき、暗号方式は落し戸付一方向性関数の一方向性に対して緊密な安全性をもつことが証明できれば、暗号方式を破る困難さと落し戸付一方向性関数の一方向性を破る困難さとは同等と考えられる。
【００１８】
しかしながら、ＰＳＳ−ＥＳ方式は、前述した通り、落し戸付一方向性関数の一方向性に対して安全性が緊密でないことが知られている。詳しくは、ＰＳＳ−ＥＳ方式は、落し戸付一方向性関数の部分領域一方向性との間に緊密な安全性をもつ。
【００１９】
部分領域一方向性を破るとは、落し戸付一方向性関数に対し、与えられた値の逆関数値の部分情報を求めることである。なお、部分領域一方向性が破られても一方向性関数が破られるとは限らない。逆に、一方向性関数の一方向性が破られれば、部分領域一方向性は破られる。このため、関数の部分領域一方向性を破ることは、一方向性を破ることよりも容易である。
【００２０】
すなわち、ある関数に部分領域一方向性を仮定することは、比較的容易である部分領域一方向性を破ることすら困難であるという強い仮定を設けることである。ここで、ＰＳＳ−ＥＳ方式は、部分領域一方向性を仮定するため、安全性の根拠が弱い。これは、比較的容易な部分領域一方向性を破れれば、ＰＳＳ−ＥＳ方式を破れるからである。
【００２１】
このようなＰＳＳ−ＥＳ方式は、緊密な安全性を保証できないため、安全に用いるには鍵ｐｋのサイズを大きくする必要がある。このため、ＰＳＳ−ＥＳ方式は、計算コストや鍵の保存領域を増大させる問題がある。
【００２２】
一方、落し戸付一方向性関数の一方向性との間に緊密な安全性を保証できる方式として、駒野、太田は、ＯＡＥＰ方式、ＯＡＥＰ＋＋方式、ＲＥＡＣＴ方式に基づいて、暗号及び署名方式のＯＡＥＰ−ＥＳ方式、ＯＡＥＰ＋＋−ＥＳ方式、ＲＥＡＣＴ−ＥＳ方式を提案している（例えば、非特許文献２参照）。
【００２３】
しかしながら、ＯＡＥＰ−ＥＳ方式、ＯＡＥＰ＋＋−ＥＳ方式及びＲＥＡＣＴ−ＥＳ方式は、図１７（ｂ）、図１８（ａ）〜（ｂ）に示すように、いずれも３回のランダム関数演算Ｈ’，Ｇ，Ｈを含み、実装サイズが大きくなる。
【００２４】
詳しくは、ＯＡＥＰ−ＥＳ方式は、ＰＳＳ−ＥＳ方式よりも緊密な安全性をもつが、その緊密さがＯＡＥＰ＋＋−ＥＳ方式、ＲＥＡＣＴ−ＥＳ方式に比べて小さい。このため、安全に用いるためには鍵ｐｋのサイズを大きくする必要がある。さらにＯＡＥＰ−ＥＳ方式は、３回のランダム関数Ｈ’，Ｇ，Ｈ演算を含むため、実装サイズが大きくなる。
【００２５】
ＯＡＥＰ＋＋−ＥＳ方式は、落し戸付一方向性関数の一方向性との間に十分な緊密な安全性をもつが、第１のランダム関数Ｈ’の出力ビット長を拡張するために第２のランダム関数Ｇを用いる必要がある。このため、ＯＡＥＰ＋＋−ＥＳ方式は、３回のランダム関数Ｈ’，Ｇ，Ｈが必要になり、実装サイズが大きくなる。
【００２６】
ＲＥＡＣＴ−ＥＳ方式は、落し戸付一方向性関数の一方向性との間に十分な緊密な安全性をもつが、ＥｌＧａｍａｌ暗号に代表される確率暗号を用いるため、３回のランダム関数Ｈ’，Ｇ，Ｈを用いる必要がある。また、ＲＥＡＣＴ−ＥＳ方式は、実行に時間のかかる落し戸付一方向性関数の演算結果ｚ１，ｚ１’を用いて３回目のランダム関数Ｈを計算するので、計算処理に遅延が生じる。
【非特許文献１】Ｊ．Ｓ．コロン（J. S. Coron）、Ｍ．ジョイ（M. Joye）、Ｄ．ナカッシュ（D. Naccache）、Ｐ．パイヤー（P. Paillier）、“ユニバーサル・パディング・スキーム・フォア・アールエスエイ（Universal Padding Scheme for RSA）”、アドバンセズ・イン・クリプトロジー−クリプト２００２（Advances in Cryptology − CRYPTO 2002）、シュプリンガー・フェアラーク（Springer-Verlag）、２００２年。
【非特許文献２】Ｙ．駒野（Y. Komano）、Ｋ．太田（K. Ohta）、“エフィシェント・ユニバーサル・パディング・テクニークス・フォア・マルチプリケイティブ・トラップドア・ワンウェイ・パーミュテイション（Efficient Universal Padding Techniques for Multiplicative Trapdoor One-way Permutation）”、アドバンセズ・イン・クリプトロジー−クリプト２００３（Advances in Cryptology − CRYPTO 2003）、シュプリンガー・フェアラーク（Springer-Verlag）、２００３年。
【発明の開示】
【発明が解決しようとする課題】
【００２７】
以上説明したように従来の暗号・署名方式は、緊密な安全性をもつ方式（ＯＡＥＰ−ＥＳ、ＯＡＥＰ＋＋−ＥＳ、ＲＥＡＣＴ−ＥＳ）の場合、３回のランダム関数演算が必要であり、実装サイズが大きくなる。一方、２回のランダム関数演算で済む方式（ＰＳＳ−Ｓ）の場合、安全性が緊密ではない。
【００２８】
本発明は上記実情を考慮してなされたもので、３回より少ないランダム関数演算と、緊密な安全性とを両立し得る暗号化及び署名方法、装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２９】
第１の発明は、２つのランダム関数を用いて公開鍵暗号方式により暗号化処理及び署名処理を実行可能な暗号化及び署名装置に用いられる暗号化及び署名方法であって、前記暗号化処理又は署名処理の対象データｘが入力される工程と、前記対象データｘに連結される乱数ｒを生成する工程と、前記対象データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る工程と、前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記連結データｘ‖ｒのサイズ以上のサイズを有する第１ランダムデータｗを生成する工程と、前記連結データｘ‖ｒと前記第１ランダムデータｗとの排他的論理和を算出し、処理対象データｓを生成する工程と、前記処理対象データｓに第２のランダム関数Ｈを施して、前記第１ランダムデータｗのサイズと同じサイズを有する第２ランダムデータＨ（ｓ）を生成する工程と、前記第１ランダムデータｗと前記第２ランダムデータＨ（ｓ）との排他的論理和を計算し、パディングデータｔを生成する工程と、前記公開鍵暗号方式により、前記処理対象データｓに暗号化処理又は署名処理を実行する工程と、前記実行により得られた暗号化処理データｃ又は署名処理データｃ’と前記パディングデータｔとを連結し、得られた暗号文ｃ‖ｔ又は署名ｃ’‖ｔを出力する工程と、を備えた暗号化及び署名方法である。
【００３０】
第２の発明は、２つのランダム関数を用いて確定的な公開鍵暗号方式により暗号化処理及び署名処理を実行可能な暗号化及び署名装置に用いられる暗号化及び署名方法であって、前記暗号化処理又は署名処理の対象データｘが入力される工程と、前記対象データｘに連結される乱数ｒを生成する工程と、前記対象データｘと前記乱数ｒとを連結し、連結データｘ‖ｒを得る工程と、前記連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、前記公開鍵暗号方式の入力サイズ以上のサイズを有する第１ランダムデータｗを生成する工程と、前記第１ランダムデータｗに第２のランダム関数Ｇを施して、前記連結データｘ‖ｒのサイズ以上のサイズを有する第２ランダムデータＧ（ｗ）を生成する工程と、前記連結データｘ‖ｒと前記第２ランダムデータＧ（ｗ）との排他的論理和を算出し、パディングデータｓを生成する工程と、前記公開鍵暗号方式により、前記第１ランダムデータｗに暗号化処理又は署名処理を実行する工程と、前記実行により得られた暗号化処理データｃ又は署名処理データｃ’と前記パディングデータｓとを連結し、得られた暗号文ｓ‖ｃ又は署名ｓ‖ｃ’を出力する工程と、を備えた暗号化及び署名方法である。
【００３１】
（作用）
第１及び第２の発明は、従来のＰＳＳ−ＥＳ方式（図１７（ａ））やＯＡＥＰ−ＥＳ方式（図１７（ｂ））とは異なり、図１に示すように、暗号文又は署名を２つのデータを連結した連結データとして作成し、且つこの連結データを一方のデータ（必要な部分）のみに公開鍵暗号方式を用いて作成するので、公開鍵暗号方式の落し戸付一方向性関数の一方向性に対して緊密な安全性を実現することができる。
【００３２】
ここで更に、第１の発明は、第１のランダム関数Ｈ’の出力サイズを連結データｘ‖ｒのサイズ以上のサイズとすることにより、従来のＯＡＥＰ＋＋−ＥＳ方式（図１８（ａ））におけるビット拡張用のランダム関数Ｇを不要としたので、ランダム関数の使用を２回に削減することができる。
【００３３】
一方、第２の発明は、公開鍵暗号方式の落し戸付一方向性関数に対する仮定を、ＲＳＡ暗号に代表される確定的暗号に制限したことにより、従来のＲＥＡＣＴ−ＥＳ方式（図１８（ｂ））の第３のランダム関数Ｈを不要としたので、ランダム関数の使用を２回に削減することができる。
【００３４】
従って、第１及び第２の発明は、３回より少ないランダム関数演算と、緊密な安全性とを両立することができる。
【発明の効果】
【００３５】
以上説明したように本発明によれば、３回より少ないランダム関数演算と、緊密な安全性とを両立できる。
【発明を実施するための最良の形態】
【００３６】
以下、本発明の各実施形態について図面を参照しながら説明するが、その前に各実施形態の概要を述べる。各実施形態は、前述した第１の発明に対応する図１（ａ）に示す方式１と、第２の発明に対応する図１（ｂ）に示す方式２とに分類される。
【００３７】
具体的には、方式１は第１〜第３の実施形態に対応する。第１の実施形態は暗号化／復号処理に関し、第２の実施形態は署名／検証処理に関する。第３の実施形態は第１及び第２の実施形態の組合せである。
【００３８】
同様に、方式２は第４〜第６の実施形態に対応する。第４の実施形態は暗号化／復号処理に関し、第５の実施形態は署名／検証処理に関する。第６の実施形態は第４及び第５の実施形態の組合せである。
【００３９】
各実施形態においては、公開鍵暗号方式として、ＲＳＡ暗号（ＲＳＡ署名）に代表される確定的なものを使用する。２つのランダム関数は、例えばＳＨＡなどのハッシュ関数とする。  続いて、各実施形態を具体的に述べる。
【００４０】
（第１の実施形態）
図２は本発明の第１の実施形態に係る暗号化装置の構成を示す模式図であり、図３は同実施形態における復号装置の構成を示す模式図であって、同種の要素には同一符号を付してその詳しい説明を省略し、ここでは異なる部分について主に述べる。なお、以下の各実施形態も同様にして説明する。
【００４１】
暗号化装置は、メモリ１、入出力部２、乱数発生器３、乱数メモリ４、演算器５、Ｈ’関数演算部６、Ｈ関数演算部７、公開鍵暗号暗号化部８ｅ、制御部９ｅを備えている。なお、乱数発生器３を除く各要素１，２〜９ｅは、互いにバスを介して接続されている。また、各部８ｅ，９ｅの添字ｅは、暗号化処理を表している。同様に、後述する添字ｄは復号処理を表す。
【００４２】
ここで、メモリ１は、各部２〜９ｅから読出書込可能な記憶部であり、例えば平文データｘ、公開鍵ｐｋ、連結データｘ‖ｒ、第１ランダムデータｗ、処理対象データｓ、第２ランダムデータＨ（ｓ）、パディングデータｔ、暗号化処理データｃ、暗号文ｃ‖ｔといったデータが記憶される。
【００４３】
入出力部２は、暗号化装置と外部との間のインターフェイス装置であり、例えば、ユーザの操作により、平文データｘ及び／又は公開鍵ｐｋを入力してメモリ１に書込む機能と、暗号化処理の結果、メモリ１に記憶された暗号文ｃ‖ｔを出力する機能とをもっている。
【００４４】
乱数発生器３は、暗号文又は署名生成時に必要な乱数ｒを発生させる部分であり、生成された乱数ｒを乱数メモリ４に書込む機能をもっている。
【００４５】
乱数メモリ４は、乱数発生器３から書込まれた乱数ｒを演算器５から読出可能に保持するものである。
【００４６】
演算器５は、各部６〜９ｅに制御され、メモリ１内のデータに対する多倍長の演算を実行する部分であり、例えば、排他的論理和の計算、ビット連結・分割、ビットの比較、などを実行する機能と、実行結果をメモリ１に書込む機能をもっている。
【００４７】
Ｈ’関数演算部６は、メモリ１内の連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算する機能と、得られた第１ランダムデータｗをメモリ１に書込む機能とをもっている。
【００４８】
ここで、第１のランダム関数Ｈ’は、その出力値を用いて平文又は文書と乱数の連結データにマスクをかけるために、任意のサイズ（長さ）のデータを入力とし、平文と乱数の連結データのサイズ以上のデータを出力する必要がある。さらに、マスクをかけた結果は、落し戸付一方向性関数ｆの入力となるので、暗号方式を安全に実現するためには、第１のランダム関数Ｈ’の出力のサイズを関数ｆの入力サイズｋ以上にとる必要がある。
【００４９】
Ｈ関数演算部７は、メモリ１内の処理対象データｓに第２のランダム関数Ｈを施す機能と、得られた第２ランダムデータＨ（ｓ）をメモリ１に書込む機能をもっている。ここで、第２のランダム関数Ｈは、その出力を用いて第１のランダム関数Ｈ’の出力値にマスクをかけるために、任意のサイズのデータを入力とし、第１のランダム関数Ｈ’の出力サイズ以上のサイズのデータを出力する必要がある。従って、第２のランダム関数Ｈの出力の長さは、第１のランダム関数Ｈ’と同様に、関数ｆの入力サイズｋ以上にとる必要がある。
【００５０】
公開鍵暗号暗号化部８ｅは、一方向性関数ｆを用いた公開鍵暗号方式により、メモリ１内の公開鍵ｐｋに基づいて、メモリ１内の処理対象データｓに暗号化処理を実行する機能と、得られた暗号化処理データｃをメモリ１に書込む機能をもっている。なお、公開鍵ｐｋは、復号装置を用いる暗号文受信者のものであり、予め公開簿から読出したものである。また、落し戸付一方向性関数ｆは、ＲＳＡ暗号方式に代表される公開鍵暗号方式が用いられる。落し戸付一方向性関数ｆの入出力値の長さをｋとしたとき、一般にｋは１０２４ビットや２０４８ビットなどが選択される。
【００５１】
制御部９ｅは、入力された平文データｘと公開鍵暗号方式の公開鍵ｐｋとに基づいて、平文データｘを暗号化処理し、得られた暗号文ｃ‖ｔを出力するように各部１〜８ｅを制御するものである。具体的には制御部９ｅは、図４（ａ）に示すように各部１〜８ｅを制御する機能をもっている。このような制御部９ｅは、予め制御機能を実現させるためのプログラムが装置のコンピュータにインストールされることにより実現される。これは、後述する他の制御部９ｄ〜９ｖ，１２ｅ〜１２ｖでも同様である。
【００５２】
一方、復号装置は、暗号化装置の各要素１〜９ｅのうち、乱数発生器３及び乱数メモリ４が省略され、公開鍵暗号暗号化部８ｅに代えて、公開鍵暗号復号部８ｄを有し、暗号化処理のための制御部９ｅに代えて、復号処理のための制御部９ｄを備えている。これに伴い、公開鍵暗号復号部８ｄから読出可能な秘密鍵メモリ１０を備えている。なお、復号装置の残りの要素１，２，６，７は、暗号化装置とは入出力データの内容が異なるものの、暗号化装置で述べた要素１，２，６，７と同様の処理機能をもっている。
【００５３】
ここで、公開鍵暗号復号部８ｄは、公開鍵暗号方式により、メモリ１内の暗号化処理データｃを秘密鍵メモリ１０内の秘密鍵ｓｋに基づいて復号処理し、得られた処理対象データｓをメモリ１に書込む機能をもっている。
【００５４】
制御部９ｄは、暗号化装置により得られる暗号文ｃ‖ｔが入力されたとき、この暗号文ｃ‖ｔと公開鍵暗号方式の秘密鍵ｓｋとに基づいて、暗号文ｃ‖ｔを復号処理し、得られた平文データｘを出力するように各部１〜８ｄを制御するものである。具体的には制御部９ｄは、図４（ｂ）に示すように各部１〜８ｄを制御する機能をもっている。
【００５５】
秘密鍵メモリ１０は、暗号文受信者（復号装置利用者）の公開鍵暗号方式に関する秘密鍵ｓｋを格納するメモリであり、公開鍵暗号復号部８ｄから読出可能となっている。
【００５６】
次に、以上のように構成された暗号化装置及び復号装置の動作を図４のフローチャートを用いて説明する。
【００５７】
（暗号化処理）
暗号文送信者は、平文を暗号化して暗号文を暗号文受信者に送信するため、暗号化装置を使用する。この暗号化装置では、制御部９ｅにより、図４（ａ）に示すように各部１〜８ｅが動作する。
【００５８】
始めに、入出力部２は、ユーザの操作により、暗号化処理の対象となる平文データｘを読込み、メモリ１に保存する（ＳＴ１）。
【００５９】
乱数発生器３は、平文データｘに連結される乱数ｒを生成し、この乱数ｒを乱数メモリ４に書込む（ＳＴ２）。
【００６０】
演算器５は、メモリ１内の平文データｘと乱数メモリ４内の乱数ｒとを連結し、得られた連結データｘ‖ｒをメモリ１に書込む。
【００６１】
Ｈ’関数演算部６は、メモリ１内の連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、得られた第１ランダムデータｗをメモリ１に書込む（ＳＴ３）。なお、第１ランダムデータｗのサイズは、連結データｘ‖ｒのサイズと等しいかそれより大きい。
【００６２】
演算器５は、メモリ１内の連結データｘ‖ｒと第１ランダムデータｗとの排他的論理和を算出し、得られた処理対象データｓをメモリ１に書込む（ＳＴ４）。
【００６３】
Ｈ関数演算部７は、メモリ１内の処理対象データｓに第２のランダム関数Ｈを施し、得られた第２ランダムデータＨ（ｓ）をメモリ１に書込む。なお、第２ランダムデータＨ（ｓ）のサイズは、第１ランダムデータｗのサイズと等しい。
【００６４】
演算器５は、メモリ１内の第１及び第２ランダムデータｗ，Ｈ（ｓ）の排他的論理和を計算し、得られたパディングデータｔをメモリ１に書込む（ＳＴ５）。
【００６５】
公開鍵暗号暗号化部８ｅは、一方向性関数ｆを用いた公開鍵暗号方式により、メモリ１内の公開鍵ｐｋに基づいて、メモリ１内の処理対象データｓに暗号化処理を実行し、得られた暗号化処理データｃをメモリ１に書込む（ＳＴ６）。なお、公開鍵ｐｋは、復号装置を用いる暗号文受信者のものである。
【００６６】
演算器５は、メモリ１内の暗号化処理データｃとパディングデータｔとを連結し、得られた暗号文ｃ‖ｔをメモリ１に書込む。
【００６７】
入出力部２は、暗号文ｃ‖ｔの作成完了を表示出力する。以下、入出力部２は、ユーザの操作により、メモリ１内の暗号文ｃ‖ｔを暗号文受信者（復号装置）に向けて送信出力する（ＳＴ７）。
【００６８】
（復号処理）
暗号文受信者は、暗号文を復号して平文を得るため、復号装置を使用する。この復号装置では、制御部９ｄにより、図４（ｂ）に示すように各部１〜８ｄが動作する。
【００６９】
入出力部２は、暗号文送信者から送信された暗号文ｃ‖ｔを読込み、メモリ１に保存する（ＳＴ１１）。
【００７０】
演算器５は、メモリ１内の暗号文ｃ‖ｔを暗号化処理データｃとパディングデータｔとに分割し、それぞれメモリ１に書込む。
【００７１】
公開鍵暗号復号部８ｄは、公開鍵暗号方式により、メモリ１内の暗号化処理データｃを秘密鍵メモリ１０内の秘密鍵ｓｋに基づいて復号処理し、得られた処理対象データｓをメモリ１に書込む（ＳＴ１２）。
【００７２】
Ｈ関数演算部７は、メモリ１内の処理対象データｓに第２のランダム関数Ｈを施し、得られた第２ランダムデータＨ（ｓ）をメモリ１に書込む。
【００７３】
演算器５は、メモリ１内の第２ランダムデータＨ（ｓ）とパディングデータｔとの排他的論理和を算出し、得られた第１の第１ランダムデータｗをメモリ１に書込む（ＳＴ１３）。
【００７４】
演算器５は、メモリ１内の第１ランダムデータｗと処理対象データｓとの排他的論理和を算出し、得られた連結データｘ‖ｒをメモリ１に書込む（ＳＴ１４）。
【００７５】
Ｈ’関数演算部６は、メモリ１内の連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗ’を演算し、得られた第２の第１ランダムデータｗ’をメモリ１に書込む。
【００７６】
制御部９ｄは、メモリ１内の第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する（ＳＴ１５）。
【００７７】
制御部９ｄは、この判定の結果、両者ｗ，ｗ’が互いに同一のとき、演算器５により連結データｘ‖ｒを分割し、得られた平文データｘと乱数ｒをメモリ１に書込む。
【００７８】
入出力部２は、メモリ１内の平文データｘを出力する（ＳＴ１６）。
【００７９】
一方、ステップＳＴ１５の判定の結果、両者ｗ，ｗ’が互いに異なるとき、制御部９ｄは、暗号文ｃ‖ｔを棄却し、入出力部２により「暗号文が不合格」の旨を表示出力して（ＳＴ１７）、処理を終了する。
【００８０】
（乱数ｒ及びランダム関数Ｈ’，Ｈの役割）
ここで、以上の動作における乱数ｒ、第１のランダム関数Ｈ’、第２のランダム関数Ｈの役割を述べる。
【００８１】
乱数ｒは、暗号文を確率的に生成するために用いられる。もし、乱数ｒが利用されない場合には、暗号文は平文に対して確定的に計算される。
【００８２】
ここで、「暗号文が平文に対して確率的に生成される」とは、「平文に対し、乱数に依存して暗号文が複数存在すること」を意味する。また、「暗号文が確定的に生成される」とは、「平文に対し、暗号文が一通りのみ存在すること」を意味する。
【００８３】
確定的な暗号方式では、攻撃対象の暗号文に対応する平文の候補がある場合には、攻撃者が平文の候補を暗号化し、攻撃対象の暗号文に一致するものを復号文と判断することで、暗号方式の安全性として用いられている識別不能性を破ることができる。なお、識別不能性とは、攻撃者が自由に選んだ２つの平文に対してそれぞれ暗号文作成依頼を出し、一方の平文から生成された暗号文を受け取り、その暗号文がどちらの平文から生成されたか識別不可能な性質である。
【００８４】
すなわち、確定的な暗号方式は、前述したように識別不能性を破ることができるので、安全ではない。
【００８５】
しかしながら、乱数ｒを用いて暗号文が生成される場合、攻撃者は暗号文作成依頼を出したのち、どのような乱数が選ばれて攻撃対象となる暗号文が作成されたか不明なため、識別不能性を破ることはできない。
【００８６】
乱数ｒは、攻撃者が推測できないように、全数探索により探すことが計算量的に困難となるようなサイズをもつことが必要であり、一般的には８０ビットから１６０ビットの値を選べば十分である。
【００８７】
第１のランダム関数Ｈ’は、復号により得られた復号文の正当性を保証するために用いられる。これにより、復号時に、２つのデータｗ，Ｈ’（ｘ‖ｒ）が互いに等しい場合、得られた復号文ｘが正当であると判断し、２つのデータが異なる場合には、復号を行った暗号文が不正に改竄されたデータであると判断する。これは後述する署名検証の場合も同様である。
【００８８】
第２のランダム関数Ｈは、データｗにマスクをかけて、暗号方式の安全性を保証するために用いられる。ここで、データｗは、連結データｘ‖ｒにマスクをかける成分であり、ｗに関する情報がわかれば、マスクを外し平文に関する情報を得ることが可能となる。本実施形態では、公開鍵暗号方式が安全であるとき、すなわち、落し戸付一方向性関数が一方向性をもつとき、正規復号者以外の攻撃者は暗号文ｃ‖ｔから第２のランダム関数Ｈへの入力ｓを得ることができない。このため、攻撃者はデータｗにかかったマスクを外すことができず、平文に関する情報を得ることは困難となる。
【００８９】
（暗号化方式が安全な理由）
本実施形態の暗号処理に関し、暗号化関数が一方向性を満たすのであれば安全であることの直観的な理由は次のように説明できる。暗号方式が安全であるとは、直観的には、いかなる攻撃者も暗号文から平文の１ビットの情報すら得られないときをいう。攻撃者に暗号文ｃ‖ｔが与えられたとき、対応する平文に関する情報を得るには、攻撃者はｃの逆関数値 ｓ＝ｆ-1 （ｃ）を求めなければならない。
【００９０】
理由は、仮に攻撃者がｓを復元できなければ、第２のランダム関数Ｈの性質からＨ（ｓ）の値を特定できない。このとき、Ｈ（ｓ）の各ビット０，１を攻撃者が推定できる確率は１／２でしかない。従って、攻撃者は、データｔ，Ｈ（ｓ）の排他的論理和から計算されるデータｗを特定できない。このため、攻撃者は、データｓ，ｗの排他的論理和により計算される平文に関する情報を１ビットすら得ることができない。
【００９１】
すなわち、逆関数値ｓ＝ｆ-1 （ｃ） を求めずに平文に関する情報を得ることは困難であり、暗号方式を破るためには落し戸付一方向性関数の一方向性を破ってｓ＝ｆ-1 （ｃ） を求める必要がある。
【００９２】
（能動的な攻撃に対する安全性）
本実施形態の暗号処理に関し、能動的な攻撃を行う攻撃者を考える。攻撃者は正規復号者に暗号文の復号依頼を行い、対応する平文又は暗号文が不正であるという回答を受け取り、そこで得た情報を基に攻撃を行う。
【００９３】
しかしながら、攻撃者は、平文に関する情報を得られない。すなわち、攻撃者は自ら暗号化手順に従って生成した暗号文を復号依頼文として出力したときにのみ対応する平文を受け取ることができる。逆に、攻撃者は暗号化手順に従わずに生成したデータを復号依頼文としても、復号依頼文が不正な暗号文であるという回答を得ることしかできない。この理由は次のように説明できる。
【００９４】
復号装置は、復号時に、Ｈ’（ｘ‖ｒ）＝ｗが成立しなければ暗号文ｃ‖ｔを不正な暗号文であるとして棄却する。
【００９５】
いま、ｃo‖ｔoを攻撃者が出力する復号依頼文とする。復号依頼文ｃo‖ｔoから復号手順に従って計算されるデータをｓo、ｗo、平文をｘo、乱数をｒoとする。ここで、データｗoは、データｓoを第２のランダム関数Ｈに入力して得られるＨ（ｓo）とｔoの排他的論理和で得られる値である。
【００９６】
このとき、攻撃者が暗号化手順に従って復号依頼文ｃo‖ｔoを出力していれば、攻撃者は自ら第１のランダム関数Ｈ’に復号依頼文ｘo‖ｒoを入力してランダム関数値Ｈ’（ｘo‖ｒo）を計算し、かつ、第２のランダム関数Ｈにデータｓoを入力してランダム関数値Ｈ（ｓo）を計算しているはずである。
【００９７】
従って、暗号化手順に従わずに復号依頼文を出力するとは、ランダム関数値Ｈ（ｓo）又はＨ’（ｘo‖ｒo）を計算していないときをいう。
【００９８】
まず、攻撃者がランダム関数値Ｈ（ｓo）を計算せずに復号依頼文ｃo‖ｔoを出力する場合を考える。このとき、第２のランダム関数Ｈの性質からＨ（ｓo）はランダムな値であり、Ｈ（ｓo）と復号依頼文ｔoの排他的論理和により計算される値ｗoもランダムな値である。従って、データｗo，ｓoの排他的論理和により計算されるｘo‖ｒoは、攻撃者がランダム関数値Ｈ’（ｘo‖ｒo）を求めたか否かによらず、データｗoがランダムな値であるため、一般的にはＨ’（ｘo‖ｒo）＝ｗoとならない。このため、攻撃者は、復号依頼文は不正な暗号文であるという回答を得ることしかできない。
【００９９】
次に、攻撃者がランダム関数値Ｈ（ｓo）を求めたが、ランダム関数値Ｈ’（ｘo‖ｒo）を求めずに、復号依頼文ｃo‖ｔoを生成する場合を考える。このとき、第１のランダム関数Ｈ’の性質から一般的にはＨ’（ｘo‖ｒo）＝ｗoとならない。このため、攻撃者は、復号依頼文は不正な暗号文であるという回答を得ることしかできない。
【０１００】
従って、攻撃者が能動的な攻撃を行っても情報を得ることが困難であるので、暗号化処理の安全性を証明できる。
【０１０１】
上述したように本実施形態によれば、従来のＰＳＳ−ＥＳ方式やＯＡＥＰ−ＥＳ方式とは異なり、暗号文ｃ‖ｔを２つのデータｃ，ｔを連結した連結データとして作成し、且つこの連結データを一方のデータ（必要な部分ｓ）のみに公開鍵暗号方式を用いて作成するので、公開鍵暗号方式の落し戸付一方向性関数の一方向性に対して緊密な安全性を実現することができる。また、落し戸付一方向性関数の一方向性に対して緊密な安全性をもつことを証明可能であり、より小さなサイズの鍵で一定レベルの安全性が保証できるため、鍵を記録する保存領域を縮小でき、計算コストも削減することができる。
【０１０２】
また、本実施形態は、第１のランダム関数Ｈ’の出力サイズを連結データｘ‖ｒのサイズ以上のサイズとすることにより、従来のＯＡＥＰ＋＋−ＥＳ方式におけるビット拡張用のランダム関数Ｇを不要としたので、ランダム関数の使用を２回に削減することができる。
【０１０３】
従って、本実施形態は、３回より少ないランダム関数演算と、緊密な安全性とを両立することができる。
【０１０４】
なお、上記第１の実施形態における第２のランダム関数Ｈの出力サイズは、第１のランダム関数Ｈ’の出力サイズよりも大きくすることもできる。この場合、第１のランダム関数Ｈ’の出力ｗと、第２のランダム関数Ｈの出力Ｈ（ｓ）の排他的論理和をとるとき、ビットの長さをそろえるために、第１のランダム関数の出力に固定ビットを付加する、第２のランダム関数の出力で不要な部分を削除する、などが考えられる。
【０１０５】
また、本実施形態では、第１のランダム関数Ｈ’と第２のランダム関数Ｈを同一の関数とし、ランダム関数演算部６，７を１つのみに削減することもできる。従来技術においてもランダム関数演算部を１つのみに削減可能であるが、その場合、本発明ではランダム関数演算を２回実行するのみで緊密な安全をもつ暗号及び署名方法が構成できることが、従来技術との相違点となる。
【０１０６】
さらに、本実施形態では、図５に示すように、データｓ（＝ｓ１＋ｓ２）のサイズを、公開鍵暗号系で使用する鍵のサイズｋより大きくとることができる。この場合、公開鍵暗号系で使用する鍵のサイズｋと等しい長さを持つｓの部分情報ｓ１のみを暗号化して、暗号化して得られた結果とともにｓの残りの部分ｓ２を添付すればよい。このとき、ｓのうち暗号化されなかった部分ｓ２は第１のランダム関数の出力でマスクがかけられた情報である。
【０１０７】
マスクを外すためには、落し戸付一方向性関数の逆関数演算を行いｓ全体を復元し、ｓを第２のランダム関数に入力してｗを復元し、データｗ，ｓの排他的論理和をとる必要がある。ここで、落し戸付一方向性関数の一方向性を破らずに暗号方式又は署名方式を破ることは不可能であることを上述した議論と同様にして示すことができる。このため、図５に示したｓの部分情報ｓ１のみを暗号化して残りの部分情報ｓ２を暗号化せずに添付する方法も、落し戸付一方向性関数の一方向性に依存して緊密な安全性を持つといえる。
【０１０８】
（第２の実施形態）
図６は本発明の第２の実施形態に係る署名装置の構成を示す模式図であり、図７は同実施形態における署名検証装置の構成を示す模式図である。
【０１０９】
本実施形態は、第１の実施形態の変形例であり、公開鍵ｐｋを用いる暗号化処理及び復号処理に代えて、秘密鍵ｓｋを用いる署名処理及び署名検証処理を実行するものである。
【０１１０】
ここで、署名装置は、暗号化装置の各要素１〜９ｅのうち、公開鍵暗号暗号化部８ｅに代えて、公開鍵暗号署名生成部８ｓを有し、暗号化処理のための制御部９ｅに代えて、署名処理のための制御部９ｓを備えている。これに伴い、公開鍵暗号署名生成部８ｓから読出可能な秘密鍵メモリ１０を備えている。
【０１１１】
なお、添字ｓは署名処理を表している。同様に、後述する添字ｖは署名検証処理を表す。また、署名装置の残りの要素１〜７は、暗号化装置とは入出力データの内容が異なるものの、暗号化装置で述べた要素１〜７と同様の処理機能をもっている。
【０１１２】
公開鍵暗号署名生成部８ｓは、公開鍵暗号方式により、メモリ１内の処理対象データｓを秘密鍵メモリ１０内の秘密鍵ｓｋに基づいて署名処理する機能と、得られた署名処理データｃ’をメモリ１に書込む機能とをもっている。
【０１１３】
制御部９ｓは、入力された文書データｘと公開鍵暗号方式の秘密鍵ｓｋとに基づいて、文書データｘに署名処理し、得られた署名ｃ’‖ｔを出力するように各部１〜８ｓを制御するものである。具体的には制御部８ｓは、図８（ａ）に示すように各部１〜８ｓを制御する機能をもっている。
【０１１４】
秘密鍵メモリ１０は、署名生成者（署名装置利用者）の公開鍵暗号方式に関する秘密鍵ｓｋを格納するメモリであり、公開鍵暗号署名生成部８ｓから読出可能となっている。
【０１１５】
一方、署名検証装置は、暗号化装置の各要素１〜９ｅのうち、乱数発生器３及び乱数メモリ４が省略され、公開鍵暗号暗号化部８ｅに代えて、公開鍵暗号署名検証部８ｖを有し、暗号化処理のための制御部９ｅに代えて、署名検証処理のための制御部９ｖを備えている。
【０１１６】
なお、署名検証装置の残りの要素１，２，６，７は、暗号化装置とは入出力データの内容が異なるものの、暗号化装置で述べた要素１，２，６，７と同様の処理機能をもっている。
【０１１７】
ここで、署名検証部８ｖは、公開鍵暗号方式により、メモリ１内の署名処理データｃ’を公開鍵ｐｋに基づいて復元処理し、得られた処理対象データｓをメモリ１に書込む復号機能と、メモリ１内の第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する判定機能と、この判定の結果、両者ｗ，ｗ’が互いに同一のとき、正当性をもつ署名として署名ｃ’‖ｔを受理する署名受理機能とをもっている。なお、判定機能及び署名受理機能は、署名検証部８ｖに代えて、制御部９ｖが実行してもよい。
【０１１８】
制御部９ｖは、署名装置により得られる署名ｃ’‖ｔが入力されたとき、この署名ｃ’‖ｔと公開鍵暗号方式の公開鍵ｐｋとに基づいて、署名ｃ’‖ｔの正当性を検証するように各部１〜８ｖを制御するものである。具体的には制御部９ｖは、図８（ｂ）に示すように各部１〜８ｖを制御する機能をもっている。
【０１１９】
次に、以上のように構成された署名装置及び署名検証装置の動作を図８のフローチャートを用いて説明する。
【０１２０】
（署名処理）
署名生成者は、文書に署名処理して得られた署名を署名検証者に送信するため、署名装置を使用する。この署名装置では、制御部９ｓにより、図８（ａ）に示すように各部１〜８ｓが動作する。
【０１２１】
始めに、入出力部２は、ユーザの操作により、署名処理の対象となる文書データｘを読込み、メモリ１に保存する（ＳＴ２１）。
【０１２２】
乱数発生器３は、文書データｘに連結される乱数ｒを生成し、この乱数ｒを乱数メモリ４に書込む（ＳＴ２２）。
【０１２３】
演算器５は、メモリ１内の文書データｘと乱数メモリ４内の乱数ｒとを連結し、得られた連結データｘ‖ｒをメモリ１に書込む。
【０１２４】
Ｈ’関数演算部６は、メモリ１内の連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗを演算し、得られた第１ランダムデータｗをメモリ１に書込む（ＳＴ２３）。なお、第１ランダムデータｗのサイズは、連結データｘ‖ｒのサイズと等しいかそれより大きい。
【０１２５】
演算器５は、メモリ１内の連結データｘ‖ｒと第１ランダムデータｗとの排他的論理和を算出し、得られた処理対象データｓをメモリ１に書込む（ＳＴ２４）。
【０１２６】
Ｈ関数演算部７は、メモリ１内の処理対象データｓに第２のランダム関数Ｈを施し、得られた第２ランダムデータＨ（ｓ）をメモリ１に書込む。なお、第２ランダムデータＨ（ｓ）のサイズは、第１ランダムデータｗのサイズと等しい。
【０１２７】
演算器５は、メモリ１内の第１及び第２ランダムデータｗ，Ｈ（ｓ）の排他的論理和を計算し、得られたパディングデータｔをメモリ１に書込む（ＳＴ２５）。
【０１２８】
公開鍵暗号署名生成部８ｓは、一方向性関数ｆを用いた公開鍵暗号方式により、秘密鍵メモリ１０内の秘密鍵ｓｋに基づいて、メモリ１内の処理対象データｓに署名処理を実行し、得られた署名処理データｃ’をメモリ１に書込む（ＳＴ２６）。なお、秘密鍵ｓｋは、署名装置を用いる署名生成者のものである。
【０１２９】
演算器５は、メモリ１内の署名処理データｃ’とパディングデータｔとを連結し、得られた署名ｃ’‖ｔをメモリ１に書込む。
【０１３０】
入出力部２は、署名ｃ’‖ｔの作成完了を表示出力する。以下、入出力部２は、ユーザの操作により、メモリ１内の文書データｘ及び署名ｃ’‖ｔを署名検証者（署名検証装置）に向けて送信出力する（ＳＴ２７）。
【０１３１】
（署名検証処理）
署名検証者は、署名の正当性を検証するため、署名検証装置を使用する。この署名検証装置では、制御部９ｖにより、図８（ｂ）に示すように各部１〜８ｖが動作する。
【０１３２】
入出力部２は、署名生成者から送信された文書データｘと署名ｃ’‖ｔを読込み、メモリ１に保存する（ＳＴ３１）。
【０１３３】
演算器５は、メモリ１内の署名ｃ’‖ｔを署名処理データｃ’とパディングデータｔとに分割し、それぞれメモリ１に書込む。
【０１３４】
公開鍵暗号署名検証部８ｖは、公開鍵暗号方式により、メモリ１内の署名処理データｃ’を公開鍵ｐｋに基づいて復元処理し、得られた処理対象データｓをメモリ１に書込む（ＳＴ３２）。なお、公開鍵ｐｋは、署名生成者のものである。
【０１３５】
Ｈ関数演算部７は、メモリ１内の処理対象データｓに第２のランダム関数Ｈを施し、得られた第２ランダムデータＨ（ｓ）をメモリ１に書込む。
【０１３６】
演算器５は、メモリ１内の第２ランダムデータＨ（ｓ）とパディングデータｔとの排他的論理和を算出し、得られた第１の第１ランダムデータｗをメモリ１に書込む（ＳＴ３３）。
【０１３７】
演算器５は、メモリ１内の第１ランダムデータｗと処理対象データｓとの排他的論理和を算出し、得られた連結データｘ‖ｒをメモリ１に書込む（ＳＴ３４）。
【０１３８】
Ｈ’関数演算部６は、メモリ１内の連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗ’を演算し、得られた第２の第１ランダムデータｗ’をメモリ１に書込む。
【０１３９】
署名検証部８ｖは、メモリ１内の第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する（ＳＴ３５）。署名検証部８ｖは、この判定の結果、両者ｗ，ｗ’が互いに同一のとき、演算器５により連結データｘ‖ｒを分割し、得られた平文データｘと乱数ｒをメモリ１に書込む。
【０１４０】
入出力部２は、メモリ１内の平文データｘを出力する（ＳＴ３６）。
【０１４１】
一方、ステップＳＴ３５の判定の結果、両者ｗ，ｗ’が互いに異なるとき、署名検証部８ｖは、署名ｃ’‖ｔを棄却し、入出力部２により「署名が不合格」の旨を表示出力して（ＳＴ３７）、処理を終了する。
【０１４２】
（署名方式が安全な理由）
本実施形態の署名処理が安全である旨の直観的な理由は次のように説明できる。署名方式が安全であるとは、直観的には、いかなる攻撃者も任意の文書に対して署名を偽造できないときをいう。今、攻撃者が落し戸付一方向性関数の一方向性を破らずに偽造署名を生成する場合を考える。
【０１４３】
このとき、攻撃者にとって最良の攻撃手順は、先に署名候補ｃ’を決めておき、一方向性関数を計算可能な向きに作用させてｓ＝ｆ（ｃ’）とおき、文書ｘを定めることである。攻撃者はｃ’とｓを定めると、第２のランダム関数を用いてＨ（ｓ）の値を求めることができる。次に攻撃者が行う手順は、（ｉ）データｔを定める、（ii）第１のランダム関数値ｗを定める、又は（iii）文書ｘと乱数ｒの組を定める、ことである。
【０１４４】
（ｉ）のデータｔを定めた場合、既に求めたＨ（ｓ）との排他的論理和からｗを定めることとなり、連結データｘ‖ｒはｓとｗの排他的論理和により定まる。しかし、第１のランダム関数Ｈ’の性質から一般的にはＨ’（ｘ‖ｒ）＝ｗが成り立たないため、署名の偽造は不可能である。
【０１４５】
（ii）の第１のランダム関数値ｗを定めた場合、連結データｘ‖ｒはｓとｗの排他的論理和により定まる。しかし、第１のランダム関数Ｈ’の性質から、一般的にはＨ’（ｘ‖ｒ）＝ｗは成り立たないため、署名の偽造は不可能である。
【０１４６】
（iii）の文書ｘと乱数ｒの組を定めた場合、連結データｘ‖ｒを第１のランダム関数に入力してｗ＝Ｈ’（ｘ‖ｒ）を定めることができる。しかし、第１のランダム関数の性質から、一般的にはｘ‖ｒとｗの排他的論理和はｓと等しくならないので、署名の偽造は不可能である。
【０１４７】
（能動的な攻撃に対する安全性）
本実施形態の署名処理に関し、能動的な攻撃を行う攻撃者を考える。攻撃者は正規署名者に対して、自ら選んだ文書に対して署名依頼を行い、対応する署名を受け取り、そこで得た情報を基に攻撃を行う。
【０１４８】
署名依頼により得られる情報は、受け取った署名ｃ’‖ｔの署名検証を行うことで得られる情報であり、次の［ｉ］〜［iii］の通りである。
【０１４９】
［ｉ］文書ｘに対して乱数ｒが選ばれたときに、第１のランダム関数Ｈ’に文書と乱数の連結データｘ‖ｒが入力されたときにデータｗが出力されること。
【０１５０】
［ii］連結データｘ‖ｒとデータｗとの排他的論理和のデータｓに関し、データｓを第２のランダム関数Ｈに入力して得られるＨ（ｓ）とデータｗとの排他的論理和がデータｔと等しくなること。
【０１５１】
［iii］落し戸付一方向性関数の逆関数演算ｆ-1 （ｓ）が署名処理データｃ’と等しくなること。
【０１５２】
能動的攻撃により本実施形態の署名方式が成功するか否かは、データｓに対して落し戸付一方向性関数の逆関数演算ｃ’＝ｆ-1 （ｓ）が計算できるか否かによる。今、攻撃者が能動的攻撃を行った結果、及び、自ら選んだ署名処理データｃ’を落し戸付一方向性関数に入力してデータｓを計算し、組（ｓ,ｃ’＝ｆ-1 （ｓ））を多数所有しているとする。
【０１５３】
このとき、攻撃者は署名依頼として出力した文書ｘとは異なる文書ｘ’に関し、任意の乱数ｒ’に対してｘ’‖ｒ’とＨ’（ｘ’‖ｒ’）の排他的論理和により計算されるデータｓ’が、既に所有している多数の組（ｓ,ｃ’＝ｆ-1 （ｓ））の中に（ｓ’,ｃ’’）として存在すれば、データｔ’をＨ（ｓ’）とＨ’（ｘ’‖ｒ’）との排他的論理和により計算して、偽造署名ｃ’’‖ｔ’を出力できる。
【０１５４】
しかしながら、入力と出力の排他的論理和の計算結果が、既に保存した組の特定の値に一致するような入力を見つけることは、第１のランダム関数Ｈ’の性質から困難である。このため、上記攻撃は不可能である。従って、攻撃者が能動的な攻撃により得られた情報を用いて偽造署名を出力することは困難であるので、署名方式の安全性を証明できる。
【０１５５】
上述したように本実施形態によれば、第１の実施形態を署名処理及び署名検証処理に適用しても、第１の実施形態と同様の作用効果を得ることができる。
【０１５６】
（第３の実施形態）
図９は本発明の第３の実施形態に係る暗号化及び署名装置の構成例を示す模式図である。本実施形態は、第１及び第２の実施形態の組合せ例であり、前述した暗号化処理、復号処理、署名処理及び署名検証処理のいずれも実行可能な公開鍵暗号演算部８ｅ，８ｄ，８ｓ，８ｄ及び対応する制御部９ｅ，９ｄ，９ｓ，９ｄを備えている。
【０１５７】
以上のような構成によれば、第１及び第２の実施形態のいずれの処理にも使用可能な暗号化及び署名装置を実現することができる。なお、本実施形態の暗号化及び署名装置は、暗号化処理（８ｅ，９ｅ）、復号処理（８ｄ，９ｄ）及び署名処理（８ｓ，９ｓ）及び署名検証処理（８ｖ，９ｖ）を実行可能な場合について説明したが、これに限らず、例えば暗号化処理と復号処理を実行可能な構成に変形してもよい。同様に、署名処理と署名検証処理とを実行可能な構成に変形してもよい。あるいは、暗号化処理と署名処理とを実行可能な構成に変形してもよく、同様に復号処理と署名検証処理とを実行可能な構成に変形してもよい。その他、本実施形態は、暗号化処理、復号処理、署名処理及び署名検証処理のうち、任意の２つ又は３つの組合せを実行可能な構成に変形することができる。
【０１５８】
（第４の実施形態）
図１０は本発明の第４の実施形態に係る暗号化装置の構成を示す模式図であり、図１１は同実施形態における復号装置の構成を示す模式図である。
【０１５９】
本実施形態は、第１の実施形態の変形例であり、図１（ａ）に示した方式１に代えて、図１（ｂ）に示した方式２を実行するものである。これに伴い、方式１のＨ’関数演算部７に代えて、Ｇ関数演算部１１を備えている。また、方式１の制御部９ｅ，９ｄに代えて、方式２の制御部１２ｅ，１２ｄを備えている。また、Ｈ’関数演算部６の出力がそのまま公開鍵暗号演算部の入力となるため、Ｈ’関数演算部６の出力のサイズは、公開鍵暗号方式で用いる落し戸付一方向性関数ｆの入力サイズ以上のサイズにとられている。
【０１６０】
ここで、暗号化装置及び復号装置のＧ関数演算部１１は、メモリ１内の第１ランダムデータｗに第２のランダム関数Ｇを施す機能と、得られた第２ランダムデータＧ（ｗ）をメモリ１に書込む機能とをもっている。なお、第２ランダムデータＧ（ｗ）は、連結データｘ‖ｒのサイズと等しいかそれ以上のサイズをもっている。詳しくは、暗号化装置の第２のランダム関数Ｇは、その出力Ｇ（ｗ）を用いて連結データｘ‖ｒにマスクをかけるために、任意のサイズの入力データに対し、連結データｘ‖ｒのサイズ以上のサイズのデータＧ（ｗ）を出力する必要がある。
【０１６１】
暗号化装置の制御部１２ｅは、入力された平文データｘと公開鍵暗号方式の公開鍵ｐｋとに基づいて、平文データｘを暗号化処理し、得られた暗号文ｓ‖ｃを出力するように各部１〜１１を制御するものである。具体的には制御部１２ｅは、図１２（ａ）に示すように各部１〜１１を制御する機能をもっている。
【０１６２】
復号装置の制御部１２ｄは、暗号化装置により得られる暗号文ｓ‖ｃが入力されたとき、この暗号文ｓ‖ｃと公開鍵暗号方式の秘密鍵ｓｋとに基づいて、暗号文ｓ‖ｃを復号処理し、得られた平文データｘを出力するように各部１〜１１を制御するものである。具体的には制御部１２ｄは、図１２（ｂ）に示すように各部１〜１１を制御する機能をもっている。
【０１６３】
次に、以上のように構成された暗号化装置及び復号装置の動作を図１２のフローチャートを用いて説明する。
【０１６４】
（暗号化処理）
暗号文送信者は、平文を暗号化して暗号文を暗号文受信者に送信するため、暗号化装置を使用する。この暗号化装置では、制御部１２ｅにより、図１２（ａ）に示すように各部１〜１１が動作する。
【０１６５】
始めに、ステップＳＴ４１〜ＳＴ４３は、前述したステップＳＴ１〜ＳＴ３と同様に実行される。すなわち、平文データｘと乱数ｒとの連結データｘ‖ｒからＨ’（ｘ‖ｒ）＝ｗを演算し、得られた第１ランダムデータｗがメモリ１に書込まれる。但し、第１ランダムデータｗのサイズは、公開鍵暗号方式の入力サイズと等しいかそれより大きい。
【０１６６】
続いて、Ｇ関数演算部１２は、メモリ１内の第１ランダムデータｗに第２のランダム関数Ｈを施し、得られた第２ランダムデータＨ（ｓ）をメモリ１に書込む。なお、第２ランダムデータＨ（ｓ）のサイズは、連結データｘ‖ｒのサイズと等しいかそれより大きい。
【０１６７】
演算器５は、メモリ１内の連結データｘ‖ｒと第２ランダムデータＧ（ｗ）との排他的論理和を算出し、得られたパディングデータｓをメモリ１に書込む（ＳＴ４４）。
【０１６８】
公開鍵暗号暗号化部８ｅは、一方向性関数ｆを用いた公開鍵暗号方式により、メモリ１内の公開鍵ｐｋに基づいて、メモリ１内の第１ランダムデータｗに暗号化処理を実行し、得られた暗号化処理データｃをメモリ１に書込む（ＳＴ４５）。なお、公開鍵ｐｋは、復号装置を用いる暗号文受信者のものである。
【０１６９】
演算器５は、メモリ１内の暗号化処理データｃとパディングデータｓとを連結し、得られた暗号文ｓ‖ｃをメモリ１に書込む。
【０１７０】
入出力部２は、暗号文ｓ‖ｃの作成完了を表示出力する。以下、入出力部２は、ユーザの操作により、メモリ１内の暗号文ｓ‖ｃを暗号文受信者（復号装置）に向けて送信出力する（ＳＴ４６）。
【０１７１】
（復号処理）
暗号文受信者は、暗号文を復号して平文を得るため、復号装置を使用する。この復号装置では、制御部１２ｄにより、図１２（ｂ）に示すように各部１〜１１が動作する。
【０１７２】
入出力部２は、暗号文送信者から送信された暗号文ｓ‖ｃを読込み、メモリ１に保存する（ＳＴ５１）。
【０１７３】
演算器５は、メモリ１内の暗号文ｓ‖ｃを暗号化処理データｃとパディングデータｓとに分割し、それぞれメモリ１に書込む。
【０１７４】
公開鍵暗号復号部８ｄは、公開鍵暗号方式により、メモリ１内の暗号化処理データｃを秘密鍵メモリ１０内の秘密鍵ｓｋに基づいて復号処理し、得られた第１の第１ランダムデータｗをメモリ１に書込む（ＳＴ５２）。
【０１７５】
Ｇ関数演算部１２は、メモリ１内の第１の第１ランダムデータｗに第２のランダム関数Ｈを施し、得られた第２ランダムデータＧ（ｗ）をメモリ１に書込む。
【０１７６】
演算器５は、メモリ１内の第２ランダムデータＧ（ｗ）とパディングデータｓとの排他的論理和を算出し、得られた連結データｘ‖ｒをメモリ１に書込む（ＳＴ５３）。
【０１７７】
Ｈ’関数演算部６は、メモリ１内の連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗ’を演算し、得られた第２の第１ランダムデータｗ’をメモリ１に書込む。
【０１７８】
制御部１２ｄは、メモリ１内の第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する（ＳＴ５４）。
【０１７９】
制御部１２ｄは、この判定の結果、両者ｗ，ｗ’が互いに同一のとき、演算器５により連結データｘ‖ｒを分割し、得られた平文データｘと乱数ｒをメモリ１に書込む。
【０１８０】
入出力部２は、メモリ１内の平文データｘを出力する（ＳＴ５５）。
【０１８１】
一方、ステップＳＴ５４の判定の結果、両者ｗ，ｗ’が互いに異なるとき、制御部１２ｄは、暗号文ｓ‖ｃを棄却し、入出力部２により「暗号文が不合格」の旨を表示出力して（ＳＴ５６）、処理を終了する。
【０１８２】
（乱数ｒ及びランダム関数Ｈ’，Ｈの役割）
ここで、以上の動作における乱数ｒ、第１のランダム関数Ｈ’、第２のランダム関数Ｇの役割を述べる。
【０１８３】
乱数ｒは、第１〜第３の実施形態と同様に、暗号方式を確率的にするために用いられ、一般的には８０ビットから１６０ビットの値を選べば十分である。
【０１８４】
第１のランダム関数Ｈ’は、第１〜第３の実施形態と同様に、復号により得られた復号文の正当性、及び署名検証における署名の正当性を保証するために用いられる。
【０１８５】
第２のランダム関数Ｇは、平文と乱数の連結データｘ‖ｒにマスクをかけて、暗号方式の安全性を保証するために用いられる。本実施形態では、公開鍵暗号方式が安全であるとき、すなわち、落し戸付一方向性関数が一方向性をもつとき、正規復号者以外の攻撃者は暗号文ｓ‖ｃから第２のランダム関数Ｇへの入力ｗを得ることができないので連結データｘ‖ｒにかけられたマスクを外すことができず、平文ｘに関する情報を得ることは困難となる。
【０１８６】
（暗号化方式が安全な理由）
本実施形態の暗号処理に関し、暗号化関数が一方向性を満たすのであれば安全であることの直観的な理由は次のように説明できる。攻撃者に暗号文ｓ‖ｃが与えられたとき、対応する平文に関する情報を得るためには、攻撃者はｃの逆関数値 ｗ＝ｆ-1 （ｃ）を求めなければならない。
【０１８７】
理由は、攻撃者がｗを復元できなければ、第２のランダム関数Ｇの性質からＧ（ｗ）の値を特定できない。このとき、Ｇ（ｗ）の各ビット０，１を攻撃者が推定できる確率は１/２でしかない。従って、攻撃者は、データｔ，Ｇ（ｗ）の排他的論理和により計算される連結データｘ‖ｒを特定できず、平文に関する情報を１ビットすら得ることができない。
【０１８８】
すなわち、逆関数値ｗ＝ｆ-1 （ｃ） を求めずに平文に関する情報を得ることは困難であり、暗号方式を破るためには落し戸付一方向性関数の一方向性を破ってｗ＝ｆ-1 （ｃ） を求める必要がある。
【０１８９】
（能動的な攻撃に対する安全性）
本実施形態の暗号処理に関し、能動的な攻撃を行う攻撃者を考える。攻撃者は正規復号者に暗号文の復号依頼を行い、対応する平文又は暗号文が不正であるという回答を受け取り、そこで得た情報を基に攻撃を行う。
【０１９０】
しかしながら、攻撃者は、平文に関する情報を得られない。すなわち、攻撃者は、自ら暗号化手順に従って生成した暗号文を復号依頼文として出力したときにのみ対応する平文を受け取ることができる。逆に、攻撃者は暗号化手順に従わずに生成したデータを復号依頼文としても、復号依頼文は不正な暗号文であるという回答を得ることしかできない。この理由は次のように説明できる。
【０１９１】
復号装置は、復号時に、Ｈ’（ｘ‖ｒ）＝ｗが成立しなければ暗号文ｓ‖ｃを不正な暗号文であるとして棄却する。
【０１９２】
いま、ｓo‖ｃoを攻撃者が出力する復号依頼文とする。復号依頼文ｓo‖ｃoから復号手順に従って計算されるデータをｗo、平文をｘo、乱数をｒoとする。ここで、データｗo＝ｆ-1 （ｃo）である。
【０１９３】
このとき、攻撃者が暗号化手順に従って復号依頼文ｓo‖ｃoを出力していれば、攻撃者は自ら第１のランダム関数Ｈ’にｘo‖ｒoを入力してランダム関数値を計算し、かつ、第２のランダム関数Ｇにｗoを入力してランダム関数値を計算しているはずである。
【０１９４】
従って、暗号化手順に従わずに復号依頼文を出力するとは、ランダム関数値Ｇ（ｗo）又はＨ’（ｘo‖ｒo）を計算していないときをいう。
【０１９５】
まず、攻撃者がランダム関数値Ｇ（ｗo）を計算せずに復号依頼文ｓo‖ｃoを出力する場合を考える。このとき、第２のランダム関数Ｇの性質からＧ（ｗo）はランダムな値であり、Ｇ（ｗo）と復号依頼文ｓoの排他的論理和により計算される値ｘo‖ｒoもランダムな値である。このとき、ランダムなｘo‖ｒoについて、一般的にはＨ’（ｘo‖ｒo）＝ｗoとならないので、攻撃者は、復号依頼文は不正な暗号文であるという回答を得ることしかできない。
【０１９６】
次に、攻撃者がランダム関数値Ｇ（ｗo）を求めたが、ランダム関数値Ｈ’（ｘo‖ｒo）を求めずに、復号依頼文ｓo‖ｃoを生成する場合を考える。このとき、第１のランダム関数Ｈ’の性質から一般的にはＨ’（ｘo‖ｒo）＝ｗoとならない。このため、攻撃者は、復号依頼文は不正な暗号文であるという回答を得ることしかできない。
【０１９７】
従って、攻撃者が能動的な攻撃を行っても、攻撃により情報を得ることが困難であるので、暗号化処理の安全性が証明できる。
【０１９８】
（従来技術との比較）
本実施形態は、従来のＰＳＳ−ＥＳ方式と類似する点もあるが、データ全体ではなく、パディングデータを２つにわけ、その一方のみを落し戸付一方向性関数の入力範囲とする点が異なっている。本実施形態は、先に述べたように落し戸付一方向性関数の一方向性に対して安全性を保証できる。しかし、ＰＳＳ−ＥＳ方式は暗号方式として利用した場合、一方向性のみでは安全性を示すことができない。以下に攻撃例を示す。
【０１９９】
ＰＳＳ−ＥＳ方式は、本実施形態と同一のパディング方式を用いる。すなわち、平文ｘを暗号化する際に、暗号文生成者は乱数ｒを生成し、平文ｘと乱数ｒの連結データｘ‖ｒを第１のランダム関数Ｈ’に入力してデータｗを生成する。次に、データｗを第２のランダム関数Ｇに入力して得られるＧ（ｗ）と連結データｘ‖ｒとの排他的論理和を計算し、データｓを生成する。暗号文生成者は、暗号文受信者の公開鍵に対応した暗号化関数にデータｓ，ｗを連結したデータｓ‖ｗを入力して暗号文ｙを生成する。
【０２００】
以下では、暗号化関数が一方向性関数である場合を考え、暗号方式を破る攻撃例を与える。今、暗号化関数が関数値ｙに対し、ｆ-1 （ｙ）＝ｓ‖ｗ全体を復元することは難しいが、データｓの先頭ビットｓoと、ｗに対応する各ビットを計算することが可能である性質を持つと仮定する。一般に、ｆ-1 （ｙ）全体を復元するよりは、その部分情報を復元するほうが容易なことがあり、上記性質を持つ一方向性関数を考えることには意味がある。
【０２０１】
この一方向性関数を用いて構成されたＰＳＳ−ＥＳ方式に対する攻撃者を考える。この攻撃者の目的は、暗号文ｙが与えられたときに対応する平文の何らかの情報を得ることである。暗号文ｙを受け取った攻撃者は、一方向性関数に仮定した上記性質から、データｓの先頭ビットｓoとデータｗを復元する。次に、攻撃者はデータｗを第２のランダム関数Ｇに入力してＧ（ｗ）を求める。このデータＧ（ｗ）の先頭ビットをｇoとすれば、攻撃者は先頭ビットｓo，ｇoの排他的論理和を計算し、暗号文ｙに対応する平文ｘの先頭ビットｘoの値を入手できる。
【０２０２】
従って、攻撃者はデータｓの残りのビットを求めてｆ-1 （ｙ）の全体を復元しなくとも、すなわち暗号化関数の一方向性を破らなくとも、暗号文から対応する平文の情報を得ることが可能である。
【０２０３】
このようにＰＳＳ−ＥＳ方式は、暗号化関数の一方向性に依存して安全性を示すことができない。ＰＳＳ−ＥＳ方式の安全性を保証するためには、ｆ-1 （ｙ）のうち、特に、データｗに対応したビットを求めることが困難な暗号化関数を用いる必要がある。このとき、上記攻撃例を適用できず、安全性の証明が可能である。上記性質を満たす関数は、部分領域一方向性関数とよばれる。
【０２０４】
しかし、部分領域一方向性関数は、一方向性関数よりも制約された関数であり、たとえ部分領域一方向性関数の部分領域一方向性に依存して安全性を示すことができても、暗号方式が緊密な安全性を持っているとはいえない。
【０２０５】
従って、ＰＳＳ−ＥＳ方式で一定レベルの安全性を保証するためには、鍵のサイズを大きくする等の対策が必要となり、鍵の保存領域や計算コストを増大させる等の問題が生じる。
【０２０６】
上述したように本実施形態によれば、第１の実施形態と同様に、暗号文ｓ‖ｃを２つのデータｓ，ｃを連結した連結データとして作成し、且つこの連結データを一方のデータ（必要な部分ｗ）のみに公開鍵暗号方式を用いて作成するので、公開鍵暗号方式の落し戸付一方向性関数の一方向性に対して緊密な安全性を実現することができる。これに伴い、より小さなサイズの鍵で一定レベルの安全性が保証できるため、鍵を記録する保存領域を縮小でき、計算コストも削減できる。
【０２０７】
また、本実施形態は、公開鍵暗号方式の落し戸付一方向性関数に対する仮定を、ＲＳＡ暗号に代表される確定的暗号に制限したことにより、従来のＲＥＡＣＴ−ＥＳ方式の第３のランダム関数Ｈを不要としたので、ランダム関数の使用を２回に削減することができる。これに伴い、計算時間を削減できる。例えばＲＥＡＣＴ−ＥＳ方式は、排他的論理和演算及びランダム関数演算よりも非常に大きな計算コストがかかる公開鍵暗号方式の演算をした後に、第３のランダム関数演算を行うため、全体の計算が遅延する。しかし、本実施形態では、第２のランダム関数演算とその出力Ｇ（ｗ）と、連結データｘ‖ｒとの排他的論理和演算を、公開鍵暗号演算と並列に処理することで、計算を遅延させずに高速に暗号文を生成できる。
【０２０８】
以上のように、本実施形態は、３回より少ないランダム関数演算と、緊密な安全性とを両立することができる。
【０２０９】
本実施形態は、前述同様に、第１及び第２のランダム関数Ｈ’，Ｇを同一の関数とし、ランダム関数演算部６，１１を１つのみに削減することもできる。
【０２１０】
さらに、本実施形態では、前述同様に、第１のランダム関数Ｈ’の出力ｗのサイズを、公開鍵暗号系で使用する鍵のサイズｋより大きくとることができる。この場合、公開鍵暗号系で使用する鍵のサイズｋと等しい長さを持つｗの部分情報のみを暗号化して、暗号化して得られた結果とともにｗの残りの部分を添付すればよい。
【０２１１】
マスクを外すためには、前述同様に、落し戸付一方向性関数の逆関数演算を行う必要がある。但し、落し戸付一方向性関数の一方向性を破らずに暗号方式又は署名方式を破ることは不可能である。このため、ｗの一部のみを暗号化して残りの部分は暗号化せずに添付する方法も、落し戸付一方向性関数の一方向性に依存して緊密な安全性を持つといえる。
【０２１２】
（第５の実施形態）
図１３は本発明の第５の実施形態に係る署名装置の構成を示す模式図であり、図１４は同実施形態における署名検証装置の構成を示す模式図である。
【０２１３】
本実施形態は、第２の実施形態の変形例であり、図１（ａ）に示した方式１に代えて、図１（ｂ）に示した方式２を実行するものである。これに伴い、方式１のＨ’関数演算部７に代えて、Ｇ関数演算部１１を備えている。また、方式１の制御部９ｅ，９ｄに代えて、方式２の制御部１２ｓ，１２ｖを備えている。また、Ｈ’関数演算部６の出力及びＧ関数制御部１１については、第４の実施形態に述べた通りである。
【０２１４】
署名装置の制御部１２ｓは、入力された文書データｘと公開鍵暗号方式の秘密鍵ｓｋとに基づいて、文書データｘに署名処理し、得られた署名ｓ‖ｃ’を出力するように各部１〜１１を制御するものである。具体的には制御部１２ｓは、図１５（ａ）に示すように各部１〜１１を制御する機能をもっている。
【０２１５】
署名検証装置の制御部１２ｖは、署名装置により得られる署名ｓ‖ｃ’が入力されたとき、この署名ｓ‖ｃ’と公開鍵暗号方式の公開鍵ｐｋとに基づいて、署名の正当性を検証するように各部１〜１１を制御するものである。具体的には制御部１２ｄは、図１５（ｂ）に示すように各部１〜１１を制御する機能をもっている。
【０２１６】
次に、以上のように構成された署名装置及び署名検証装置の動作を図１５のフローチャートを用いて説明する。
【０２１７】
（署名処理）
署名生成者は、文書に署名処理して得られた署名を署名検証者に送信するため、署名装置を使用する。この署名装置では、制御部１２ｓにより、図１５（ａ）に示すように各部１〜１１が動作する。
【０２１８】
始めに、ステップＳＴ６１〜６３は、前述したステップＳＴ２１〜ＳＴ２３と同様に実行される。すなわち、平文データｘと乱数ｒとの連結データｘ‖ｒからＨ’（ｘ‖ｒ）＝ｗを演算し、得られた第１ランダムデータｗがメモリ１に書込まれる。但し、第１ランダムデータｗのサイズは、公開鍵暗号方式の入力サイズと等しいかそれより大きい。
【０２１９】
続いて、Ｇ関数演算部１２は、メモリ１内の第１ランダムデータｗに第２のランダム関数Ｈを施し、得られた第２ランダムデータＨ（ｓ）をメモリ１に書込む。なお、第２ランダムデータＨ（ｓ）のサイズは、連結データｘ‖ｒのサイズと等しいかそれより大きい。
【０２２０】
演算器５は、メモリ１内の連結データｘ‖ｒと第２ランダムデータＧ（ｗ）との排他的論理和を算出し、得られたパディングデータｓをメモリ１に書込む（ＳＴ６４）。
【０２２１】
公開鍵暗号署名生成部８ｓは、一方向性関数ｆを用いた公開鍵暗号方式により、秘密鍵メモリ１０内の秘密鍵ｓｋに基づいて、メモリ１内の第１ランダムデータｗに署名処理を実行し、得られた署名処理データｃ’をメモリ１に書込む（ＳＴ６５）。なお、秘密鍵ｓｋは、署名装置を用いる署名生成者のものである。
【０２２２】
演算器５は、メモリ１内の署名処理データｃ’とパディングデータｓとを連結し、得られた署名ｓ‖ｃ’をメモリ１に書込む。
【０２２３】
入出力部２は、署名ｓ‖ｃ’の作成完了を表示出力する。以下、入出力部２は、ユーザの操作により、メモリ１内の文書データｘ及び署名ｓ‖ｃ’を署名検証者（署名検証装置）に向けて送信出力する（ＳＴ６６）。
【０２２４】
（署名検証処理）
署名検証者は、署名の正当性を検証するため、署名検証装置を使用する。この署名検証装置では、制御部１２ｖにより、図１５（ｂ）に示すように各部１〜１１が動作する。
【０２２５】
入出力部２は、署名生成者から送信された文書データｘと署名ｓ‖ｃ’を読込み、メモリ１に保存する（ＳＴ７１）。
【０２２６】
演算器５は、メモリ１内の署名ｓ‖ｃ’を署名処理データｃ’とパディングデータｓとに分割し、それぞれメモリ１に書込む。
【０２２７】
公開鍵暗号署名検証部８ｖは、公開鍵暗号方式により、メモリ１内の署名処理データｃ’を公開鍵ｐｋに基づいて復元処理し、得られた第１の第１ランダムデータｗをメモリ１に書込む（ＳＴ７２）。
【０２２８】
Ｇ関数演算部１１は、メモリ１内の第１の第１ランダムデータｗに第２のランダム関数Ｇを施し、得られた第２ランダムデータＧ（ｗ）をメモリ１に書込む。
【０２２９】
演算器５は、メモリ１内の第２ランダムデータＧ（ｗ）とパディングデータｓとの排他的論理和を算出し、得られた連結データｘ‖ｒをメモリ１に書込む（ＳＴ７３）。
【０２３０】
Ｈ’関数演算部６は、メモリ１内の連結データｘ‖ｒに第１のランダム関数Ｈ’を施してＨ’（ｘ‖ｒ）＝ｗ’を演算し、得られた第２の第１ランダムデータｗ’をメモリ１に書込む。
【０２３１】
署名検証部８ｖは、メモリ１内の第１及び第２の第１ランダムデータｗ，ｗ’が互いに同一か否かを判定する（ＳＴ７４）。署名検証部８ｖは、この判定の結果、両者ｗ，ｗ’が互いに同一のとき、演算器５により連結データｘ‖ｒを分割し、得られた平文データｘと乱数ｒをメモリ１に書込む。
【０２３２】
入出力部２は、メモリ１内の平文データｘを出力する（ＳＴ７５）。
【０２３３】
一方、ステップＳＴ７５の判定の結果、両者ｗ，ｗ’が互いに異なるとき、署名検証部８ｖは、署名ｃ’‖ｔを棄却し、入出力部２により「署名が不合格」の旨を表示出力して（ＳＴ７６）、処理を終了する。
【０２３４】
（署名方式が安全な理由）
本実施形態の署名処理が安全である旨の直観的な理由は次のように説明できる。今、攻撃者が落し戸付一方向性関数の一方向性を破らずに偽造署名を生成する場合を考える。
【０２３５】
このとき、攻撃者にとって最良の攻撃手順は、先に署名候補ｃ’を決めておき、一方向性関数を計算可能な向きに作用させてｗ＝ｆ（ｃ’）とおき、文書ｘを定めることである。攻撃者はｃ’とｗを定めると、第２のランダム関数を用いてＧ（ｗ）の値を求めることができる。次に攻撃者が行う手順は、署名ｓを定める、もしくは文書ｘと乱数ｒの組を定める、ことである。
【０２３６】
署名ｓを定めた場合、既に求めたＧ（ｗ）との排他的論理和から連結データｘ‖ｒが定まる。しかし、第１のランダム関数Ｈ’の性質から、一般的にはＨ’（ｘ‖ｒ）＝ｗが成り立たないため、署名の偽造は不可能である。
【０２３７】
一方、文書ｘと乱数ｒの組を定めた場合、連結データｘ‖ｒから生成される値Ｈ’（ｘ‖ｒ）は、第１のランダム関数の性質から、一般的にはｗとは異なる値のため、署名の偽造は不可能である。
【０２３８】
（能動的な攻撃に対する安全性）
本実施形態の署名処理に関し、能動的な攻撃を行う攻撃者を考える。攻撃者は正規署名者に対して、自ら選んだ文書に対して署名依頼を行い、対応する署名を受け取り、そこで得た情報を基に攻撃を行う。
【０２３９】
署名依頼により得られる情報は、受け取った署名ｓ‖ｃ’の署名検証を行うことで得られる情報であり、前述同様に、［ｉ］〜［iii］の通りである。
【０２４０】
［ｉ］文書ｘに対して乱数ｒが選ばれたときに、第１のランダム関数Ｈ’に文書と乱数の連結データｘ‖ｒが入力されたときにデータｗが出力されること。
【０２４１】
［ii］データｗから得られるＧ（ｗ）と連結データｘ‖ｒとの排他的論理和がデータｓと等しくなること。
【０２４２】
［iii］データｗについて、落し戸付一方向性関数の逆関数演算ｆ-1 （ｗ）が署名処理データｃ’と等しくなること。
【０２４３】
能動的攻撃により本実施形態の署名方式が成功するか否かは、データｗに対して落し戸付一方向性関数の逆関数演算ｃ’＝ｆ-1 （ｗ）が計算できるか否かによる。今、攻撃者が能動的攻撃を行った結果、及び、自ら選んだ署名処理データｃ’を落し戸付一方向性関数に入力してデータｗを計算し、組（ｗ,ｃ’＝ｆ-1 （ｗ））を多数所有しているとする。
【０２４４】
このとき、攻撃者は署名依頼として出力した文書ｘとは異なる文書ｘ’に関し、任意の乱数ｒ’に対してｘ’‖ｒ’を第１のランダム関数Ｈ’に入力して得られるｗ’＝Ｈ’（ｘ’‖ｒ’）が、既に所有している多数の組（ｗ,ｃ’＝ｆ-1 （ｗ））の中に（ｗ’,ｃ’’）として存在すれば、データｓ’をＧ（ｗ’）とｘ’‖ｒ’との排他的論理和により計算して、偽造署名ｓ’‖ｃ’’を出力できる。
【０２４５】
しかしながら、ランダム関数Ｈ’の出力が、既に保存した組の特定の値に一致するような入力を見つけることは、第１のランダム関数Ｈ’の性質から困難である。このため、上記攻撃は不可能である。従って、攻撃者が能動的な攻撃により得られた情報を用いて偽造署名を出力することは困難であるので、署名方式の安全性を証明できる。
【０２４６】
（第６の実施形態）
図１６は本発明の第６の実施形態に係る暗号化及び署名装置の構成例を示す模式図である。本実施形態は、第４及び第５の実施形態の組合せ例であり、前述した暗号化処理、復号処理、署名処理及び署名検証処理のいずれも実行可能な公開鍵暗号演算部８ｅ，８ｄ，８ｓ，８ｄ及び対応する制御部１２ｅ，１２ｄ，１２ｓ，１２ｄを備えている。
【０２４７】
以上のような構成によれば、第１及び第２の実施形態のいずれの処理にも使用可能な暗号化及び署名装置を実現することができる。また、本実施形態は、第３の実施形態と同様に、暗号化処理、復号処理、署名処理及び署名検証処理のうち、任意の２つ又は３つの組合せを実行可能な構成に変形することができる。
【０２４８】
なお、上記各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０２４９】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０２５０】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が本実施形態を実現するための各処理の一部を実行しても良い。
【０２５１】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶又は一時記憶した記憶媒体も含まれる。
【０２５２】
また、記憶媒体は１つに限らず、複数の媒体から本実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０２５３】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、本実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０２５４】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０２５５】
なお、本願発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０２５６】
【図１】本発明の各実施形態に係る暗号化及び署名方式の概要を説明するための模式図である。
【図２】本発明の第１の実施形態に係る暗号化装置の構成例を示す模式図である。
【図３】同実施形態における復号装置の構成例を示す模式図である。
【図４】同実施形態における動作を説明するためのフローチャートである。
【図５】同実施形態における変形例を説明するための模式図である。
【図６】本発明の第２の実施形態に係る署名装置の構成例を示す模式図である。
【図７】同実施形態における署名検証装置の構成例を示す模式図である。
【図８】同実施形態における動作を説明するためのフローチャートである。
【図９】本発明の第３の実施形態に係る暗号化及び署名装置の構成例を示す模式図である。
【図１０】本発明の第４の実施形態に係る暗号化装置の構成例を示す模式図である。
【図１１】同実施形態における復号装置の構成例を示す模式図である。
【図１２】同実施形態における動作を説明するためのフローチャートである。
【図１３】本発明の第５の実施形態に係る署名装置の構成例を示す模式図である。
【図１４】同実施形態における署名検証装置の構成例を示す模式図である。
【図１５】同実施形態における動作を説明するためのフローチャートである。
【図１６】本発明の第６の実施形態に係る暗号化及び署名装置の構成例を示す模式図である。
【図１７】従来の暗号化及び署名方式の概要を説明するための模式図である。
【図１８】従来の暗号化及び署名方式の概要を説明するための模式図である。
【符号の説明】
【０２５７】
１…メモリ、２…入出力部、３…乱数生成器、４…乱数メモリ、５…演算器、６…第１のランダム関数演算部、７，１１…第２のランダム関数演算部、８ｅ，８ｄ，８ｓ，８ｖ…公開鍵暗号演算部、９ｅ，９ｄ，９ｓ，９ｖ，１２ｅ，１２ｄ，１２ｓ，１２ｖ…制御部、１０…秘密鍵メモリ。
【図１】
2005204111.tif 000003
【図２】
2005204111.tif 000004
【図３】
2005204111.tif 000005
【図４】
2005204111.tif 000006
【図５】
2005204111.tif 000007
【図６】
2005204111.tif 000008
【図７】
2005204111.tif 000009
【図８】
2005204111.tif 000010
【図９】
2005204111.tif 000011
【図１０】
2005204111.tif 000012
【図１１】
2005204111.tif 000013
【図１２】
2005204111.tif 000014
【図１３】
2005204111.tif 000015
【図１４】
2005204111.tif 000016
【図１５】
2005204111.tif 000017
【図１６】
2005204111.tif 000018
【図１７】
2005204111.tif 000019
【図１８】
2005204111.tif 000020