(57)【要約】【課題】送信者は受信者の公開鍵を用いて送信者側装置１００内で暗号文を作成し、通信回線３００を介して受信者側装置２００に送信し、受信者は秘密鍵を用いて暗号文の復号化を行う公開鍵暗号通信方法において、攻撃者が不正な暗号文を受信側装置２００に入力することにより得られたエラーメッセージから暗号文を解読するといった攻撃方法に対して安全な公開鍵暗号通信方法を提供する。【解決手段】不正な暗号文が受信者側装置２００に入力されて復号化処理を行った場合、受信者側装置２００において該不正な暗号文を拒絶する原因（エラーメッセージの内容）の識別が難しくなるように暗号化および復号化処理を行う。【選択図】図１
2004012826.tif 000002
【特許請求の範囲】
【請求項１】
送信者側装置において、メッセージデータを暗号化し暗号文を作成するとともに当該暗号文を受信者側装置へ送信し、前記受信者側装置において、前記暗号文を受信して復号化する公開鍵暗号通信方法であって、
前記送信者側装置において、
入力されたメッセージデータに対し第一のパディングを行い、パディングされたメッセージデータを変換するとともに、当該変換されたデータのハッシュ値を得るステップと、
前記変換されたデータと前記ハッシュ値とを連接したデータに対し、必要に応じて任意のビット値を持つビットを付加して前記公開鍵暗号の平文空間に含まれる任意の元となりうるように第二のパディングを行うステップと、
前記第二のパディングを行った結果得られたデータを暗号化し暗号文を作成して前記受信者側装置に送信するステップとを行い、
前記受信者側装置において、
前記送信者側装置から送信された暗号文を受信し、復号化するステップと、
前記復号化されたデータに対して、前記第一のパディングによるパディングのチェックを行い、当該データの正当性を判別するステップとを行うことを特徴とする公開鍵暗号通信方法。
【請求項２】
送信者側装置において、メッセージデータを公開鍵暗号の暗号化関数ｆを用いて暗号化し暗号文を作成するとともに当該暗号文を受信者側装置へ送信し、前記受信者側装置において、前記暗号文を受信して前記公開鍵暗号の復号化関数ｆ−１を用いて復号化する公開鍵暗号通信方法であって、
前記送信者側装置において、
入力されたメッセージデータに対しパディングを行い、前記パディングされたメッセージデータを変換するとともに、当該変換されたデータのハッシュ値を得るステップと、
前記変換されたデータと前記ハッシュ値とを連接したデータｖのデータ長がｋビットであり、かつ、前記公開鍵暗号の平文空間Ａが
【数１】
2004012826.tif 000047
である場合、前記データｖに対して、
【数２】
2004012826.tif 000048
なるｗを計算するステップと、
前記暗号化関数ｆを用いて暗号文ｙ＝ｆ（ｗ）を作成して前記受信者側装置に送信するステップとを行い、
前記受信者側装置において、
前記送信者側装置から送信された暗号文を受信し、
受信した前記暗号文ｙに対して前記復号化関数をｆ−１を用いて、
【数３】
2004012826.tif 000049
なるデータｖ’を計算し、前記パディングの規則に従って前記暗号文ｙを復号化するステップとを行うことを特徴とする公開鍵暗号通信方法。
【請求項３】
送信者側装置において、メッセージデータｍ∈｛０，１｝ｎを公開鍵暗号の暗号化関数ｆを用いて暗号化し暗号文ｙを作成するとともに当該暗号文ｙを受信者側装置へ送信し、前記受信者側装置において、前記暗号文ｙを受信して前記公開鍵暗号の復号化関数ｆ−１を用いて復号化するとともに前記暗号文ｙが不正なものであった場合にエラーメッセージを出力する公開鍵暗号通信方法であって、
前記送信者側装置において、
前記公開鍵暗号の暗号化関数ｆに対して（但し、
【数４】
2004012826.tif 000050
とする。）、前記メッセージデータｍから、
【数５】
2004012826.tif 000051
を計算するステップと（但し、
【数６】
2004012826.tif 000052
ｋ＝ｎ＋ｋ０＋ｋ１とする。）、
【数７】
2004012826.tif 000053
を計算するステップと（但し、記号ａ｜｜ｂはａとｂの連接を意味する。）、
前記暗号文ｙをｙ＝ｆ（ｘ）にて作成して前記受信者側装置に送信するステップとを行い、
前記受信者側装置において、
前記送信者側装置から送信された暗号文ｙを受信し、前記公開鍵暗号の復号化関数ｆ−１を用いて、
【数８】
2004012826.tif 000054
なるｂ’、ｓ’、ｔ’を計算するステップと、
【数９】
2004012826.tif 000055
なるｒ’を計算するステップと、
【数１０】
2004012826.tif 000056
なるｍ’およびｚ’を計算するステップと、
【数１１】
2004012826.tif 000057
を出力するステップ（但し、「＊」は、暗号文を不正なものとみなし拒否したことを意味するエラーメッセージである。）とを行うことを特徴とする公開鍵暗号通信方法。
【請求項４】
送信者側装置において、メッセージデータｍ∈｛０，１｝ｎをＲＳＡ暗号の公開鍵（ｅ，Ｎ）を用いて暗号化し暗号文ｙを作成するとともに当該暗号文を受信者側装置へ送信し、前記受信者側装置において、前記暗号文ｙを受信して前記公開鍵暗号の秘密鍵ｄを用いて復号化するとともに前記暗号文ｙが不正なものであった場合にエラーメッセージを出力する公開鍵暗号通信方法であって、
前記送信者側装置において、
前記ＲＳＡ暗号の公開鍵（ｅ，Ｎ）に対して（但し、
【数１２】
2004012826.tif 000058
とする。）、前記メッセージデータｍから、
【数１３】
2004012826.tif 000059
を計算するステップと（但し、
【数１４】
2004012826.tif 000060
ｋ＝ｎ＋ｋ０＋ｋ１とする。）、
【数１５】
2004012826.tif 000061
を計算するステップと（但し、記号ａ｜｜ｂはａとｂの連接を意味する。）、
前記暗号文ｙを
【数１６】
2004012826.tif 000062
によって作成して前記受信者側装置に送信するステップとを行い、
前記受信者側装置において、
前記送信者側装置から送信された暗号文ｙを受信し、前記公開鍵暗号の秘密鍵ｄを用いて、
【数１７】
2004012826.tif 000063
なるｂ’、ｓ’、ｔ’を計算するステップと、
【数１８】
2004012826.tif 000064
なるｒ’を計算するステップと、
【数１９】
2004012826.tif 000065
なるｍ’およびｚ’を計算するステップと、
【数２０】
2004012826.tif 000066
を出力するステップ（但し、「＊」は、暗号文を不正なものとみなし拒否したことを意味するエラーメッセージである。）とを行うことを特徴とする公開鍵暗号通信方法。
【請求項５】
送信者側装置において、メッセージデータｍ∈｛０，１｝ｎを公開鍵暗号の暗号化関数ｆを用いて暗号化し暗号文ｙを作成するとともに当該暗号文ｙを受信者側装置へ送信し、前記受信者側装置において、前記暗号文ｙを受信して前記公開鍵暗号の復号化関数ｆ−１を用いて復号化するとともに前記暗号文ｙが不正なものであった場合にエラーメッセージを出力する公開鍵暗号通信方法であって、
前記送信者側装置において、
前記公開鍵暗号の暗号化関数ｆに対して（但し、
【数２１】
2004012826.tif 000067
とする。）、前記メッセージデータｍから、
【数２２】
2004012826.tif 000068
を計算するステップ（但し、
【数２３】
2004012826.tif 000069
ｋ＝ｎ＋ｋ０＋ｋ１とする。）と、
【数２４】
2004012826.tif 000070
を計算するステップ（但し、記号ａ｜｜ｂはａとｂの連接を意味する。）と、
前記暗号文ｙをｙ＝ｆ（ｘ）にて作成して前記受信者側装置に送信するステップとを行い、
前記受信者側装置において、
前記送信者側装置から送信された暗号文ｙを受信し、前記公開鍵暗号の復号化関数ｆ−１を用いて、
【数２５】
2004012826.tif 000071
なるｂ’、ｓ’、ｔ’を計算するステップと、
【数２６】
2004012826.tif 000072
なるｒ’を計算するステップと、
【数２７】
2004012826.tif 000073
なるｍ’を計算するステップと（但し、
【数２８】
2004012826.tif 000074
とする。）、
【数２９】
2004012826.tif 000075
を出力するステップ（但し、「＊」は、暗号文を不正なものとみなし拒否したことを意味するエラーメッセージである。）とを行うことを特徴とする公開鍵暗号通信方法。
【請求項６】
送信者側の装置において、メッセージデータｍ∈｛０，１｝ｎをＲＳＡ暗号の公開鍵（ｅ，Ｎ）を用いて暗号化し暗号文ｙを作成するとともに当該暗号文を受信者側装置へ送信し、前記受信者側装置において、前記暗号文ｙを受信して前記公開鍵暗号の秘密鍵ｄを用いて復号化するとともに前記暗号文ｙが不正なものであった場合にエラーメッセージを出力する公開鍵暗号通信方法であって、
前記送信者側装置において、
前記ＲＳＡ暗号の公開鍵（ｅ，Ｎ）に対して（但し、
【数３０】
2004012826.tif 000076
とする。）、前記メッセージデータｍから、
【数３１】
2004012826.tif 000077
を計算するステップ（但し、
【数３２】
2004012826.tif 000078
ｋ＝ｎ＋ｋ０＋ｋ１とする。）と、
【数３３】
2004012826.tif 000079
を計算するステップ（但し、記号ａ｜｜ｂはａとｂの連接を意味する。）と、
前記暗号文ｙを
【数３４】
2004012826.tif 000080
によって作成して前記受信者側装置に送信するステップとを行い、
前記受信者側装置において、
前記送信者側装置から送信された暗号文ｙを受信し、前記公開鍵暗号の秘密鍵ｄを用いて、
【数３５】
2004012826.tif 000081
なるｂ’、ｓ’、ｔ’を計算するステップと、
【数３６】
2004012826.tif 000082
なるｒ’を計算するステップと、
【数３７】
2004012826.tif 000083
なるｍ’を計算するステップ（但し、
【数３８】
2004012826.tif 000084
とする。）と、
【数３９】
2004012826.tif 000085
を出力するステップ（但し、「＊」は、暗号文を不正なものとみなし拒否したことを意味するエラーメッセージである。）とを行うことを特徴とする公開鍵暗号通信方法。
【請求項７】
メッセージデータを暗号化し暗号文を作成するとともに当該暗号文を送信する送信者側装置と、前記暗号文を受信して復号化するとともに前記暗号文が不正なものであった場合にエラーメッセージを出力する受信者側装置とを備える公開鍵暗号通信装置であって、
前記送信者側装置は、
入力されたメッセージデータに対し第一のパディングを行い、当該パディングされたメッセージデータを変換し、当該変換されたデータのハッシュ値を得るとともに、前記変換されたデータと前記ハッシュ値とを連接したデータに対し、必要に応じて任意のビット値を持つビットを付加して前記公開鍵暗号の平文空間に含まれる任意の元となりうるように第二のパディングを行うパディング処理手段と、
前記第二のパディングを行った結果得られたデータを暗号化し暗号文を作成する暗号化手段と、
前記作成した暗号文を前記受信者側装置に送信する送信手段とを備え、
前記受信者側装置は、
前記送信者側装置から送信された暗号文を受信する受信手段と、
前記受信した暗号文を復号化する復号化手段と、
前記復号化手段において復号化されたメッセージデータに対して、前記第一のパディングによるパディングのチェックを行い、当該データの正当性を判別するパディングチェック手段と、
前記パディングチェック手段において、受信した暗号文が正当なものと判別された場合、前記復号化手段において復号化されたメッセージデータを出力し、不正なものと判別された場合、エラーメッセージを出力する出力手段とを備えたことを特徴とする公開鍵暗号通信装置。
【請求項８】
情報処理装置で読み取り可能なプログラムであって、
前記プログラムは、前記情報処理装置に、請求項１から請求項６に記載のいずれか１つの公開鍵暗号通信方法における送信者側装置での処理を行わせることを特徴とするプログラム。
【請求項９】
情報処理装置で読み取り可能なプログラムであって、
前記プログラムは、前記情報処理装置に、請求項１から請求項６に記載のいずれか１つの公開鍵暗号通信方法における受信者側装置での処理を行わせることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号通信技術に関し、特に、公開鍵暗号通信技術に関する。
【０００２】
【従来の技術】
近年、安全性の証明が可能な公開鍵暗号への関心が高まっている。例えば、「Ｍ．　Ｂｅｌｌａｒｅ，　Ａ．　Ｄｅｓａｉ，　Ｄ．　Ｐｏｉｎｔｃｈｅｖａｌ　ａｎｄ　Ｐ．　Ｒｏｇａｗａｙ　：　Ｒｅｌａｔｉｏｎｓ　Ａｍｏｎｇ　Ｎｏｔｉｏｎｓ　ｏｆ　Ｓｅｃｕｒｉｔｙ　ｆｏｒ　Ｐｕｂｌｉｃ−Ｋｅｙ　Ｅｎｃｒｙｐｔｉｏｎ　Ｓｃｈｅｍｅｓ，　Ｐｒｏｃ．　ｏｆ　Ｃｒｙｐｔｏ’９８，ＬＮＣＳ１４６２，　Ｓｐｒｉｎｇｅｒ　Ｖｅｒｌａｇ，　ｐｐ．２６−４５　（１９９８）」（以下、文献１と呼ぶ）にあるように、現在、公開鍵暗号においては、適応的選択暗号文攻撃に対して強秘匿（ＩＮＤ−ＣＣＡ２）であることが最も安全であると考えられている。ＩＮＤ−ＣＣＡ２であることが証明可能な公開鍵暗号方式としては、「Ｄ．　Ｄｏｌｖｅ，　Ｃ．　Ｄｗｏｒｋ　ａｎｄ　Ｍ．　Ｎａｏｒ：　Ｎｏｎ−Ｍａｌｌｅａｂｌｅ　Ｃｒｙｐｔｏｇｒａｐｈｙ，　Ｉｎ　２３ｒｄＡｎｎｕａｌ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆＣｏｍｐｕｔｉｎｇ，　ｐｐ．５４２−５５２　（１９９１）」（以下、文献２と呼ぶ）に記載されている暗号方法、「Ｍ．　Ｎａｏｒ　ａｎｄ　Ｍ．　Ｙｕｎｇ　：　Ｐｕｂｌｉｃ−Ｋｅｙ　Ｃｒｙｐｔｏｓｙｓｔｅｍｓ　Ｐｒｏｖａｂｌｙ　Ｓｅｃｕｒｅａｇａｉｎｓｔ　Ｃｈｏｓｅｎ　Ｃｉｐｈｅｒｔｅｘｔ　Ａｔｔａｃｋｓ，　Ｐｒｏｃ．　ｏｆ　ＳＴＯＣ，　ＡＣＭ　Ｐｒｅｓｓ，　ｐｐ．４２７−４３７（１９９０）」（以下、文献３と呼ぶ）に記載されている暗号方法、「Ｒ．　Ｃｒａｍｅｒ　ａｎｄＶ．　Ｓｈｏｕｐ　：　Ａ　Ｐｒａｃｔｉｃａｌ　Ｐｕｂｌｉｃ　Ｋｅｙ　Ｃｒｙｐｔｏｓｙｓｔｅｍ　Ｐｒｏｖａｂｌｙ　Ｓｅｃｕｒｅ　ａｇａｉｎｓｔ　Ａｄａｐｔｉｖｅ　Ｃｈｏｓｅｎ　Ｃｉｐｈｅｒｔｅｘｔ　Ａｔｔａｃｋ，　Ｐｒｏｃ．　ｏｆ　Ｃｒｙｐｔｏ９８，　ＬＮＣＳ１４６２，　Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，　ｐｐ．１３−２５　（１９９８）」（以下、文献４と呼ぶ）に記載されている暗号方法、「Ｍ．　Ｂｅｌｌａｒｅ　ａｎｄ　Ｐ．　Ｒｏｇａｗａｙ　：　Ｏｐｔｉｍａｌ　Ａｓｙｍｍｅｔｒｉｃ　Ｅｎｃｒｙｐｔｉｏｎ　　Ｈｏｗ　ｔｏ　Ｅｎｃｒｙｐｔ　ｗｉｔｈ　ＲＳＡ，　Ｐｒｏｃ．　ｏｆ　Ｅｕｒｏｃｒｙｐｔ’９４，　ＬＮＣＳ９５０，　Ｓｐｒｉｎｇｅｒ　Ｖｅｒｌａｇ，　ｐｐ．９２−１１１　（１９９４）」（以下、文献５と呼ぶ）に記載されている暗号方式、「Ｖ．　Ｓｈｏｕｐ　：　ＯＡＥＰ　Ｒｅｃｏｎｓｉｄｅｒｅｄ，　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ−Ｃｒｙｐｔｏ２００１，　ＬＮＣＳ　２１３９，　Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，　ｐｐ．２３９−２５９　（２００１）」（以下、文献６と呼ぶ）、「Ｍ．　Ｂｅｌｌａｒｅ　ａｎｄ　Ｐ．Ｒｏｇａｗａｙ　：　Ｒａｎｄｏｍ　Ｏｒａｃｌｅｓ　ａｒｅ　Ｐｒａｃｔｉｃａｌ　−−　Ａ　Ｐａｒａｄｉｇｍ　ｆｏｒ　Ｄｅｓｉｇｎｉｎｇ　Ｅｆｆｉｃｉｅｎｔ　Ｐｒｏｔｏｃｏｌ，　Ｆｉｒｓｔ　ＡＣＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｅｃｕｒｉｔｙ，　ｐｐ．６２−−７３　（１９９３）」（以下、文献７と呼ぶ）に記載されている暗号方式、等が知られている。
【０００３】
また、「Ｊ．Ｍａｎｇｅｒ：　Ａ　Ｃｈｏｓｅｎ　Ｃｉｐｈｅｒｔｅｘｔ　Ａｔｔａｃｋ　ｏｎ　ＲＳＡ　Ｏｐｔｉｍａｌ　ＡｓｙｍｍｅｔｒｉｃＥｎｃｒｙｐｔｉｏｎ　Ｐａｄｄｉｎｇ　（ＯＡＥＰ）　ａｓ　ｓｔａｎｄａｒｄｉｚｅｄ　ｉｎ　ＰＫＣＳ＃１　ｖ２．０，　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ−Ｃｒｙｐｔｏ２００１，　ＬＮＣＳ　２１３９，　Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，　ｐｐ．２３０−２３８　（２００１）」（以下、文献８と呼ぶ）において、文献５に記載の方法（ＲＳＡ−ＯＡＥＰ）に対する実装攻撃が提案された。文献８に記載の実装攻撃は、不正な暗号文に対して受信者側装置において復号化処理を行う際に、インテグリティチェックによるエラーとパディングチェックによるエラーの両方のエラーを攻撃者が知り得ることを利用して行なわれる。
【０００４】
ここで、インテグリティチェックとは、従来、正当な暗号文は、常に最上位ビットが０であることを利用して行われるチェックであり、最上位ビットが１か０かをチェックするものである。そして、パディングチェックとは、正当な暗号文を暗号化するにあたって、付加したパディングをチェックするものである。
【０００５】
本実装攻撃は、ＲＳＡ−ＯＡＥＰの場合、送付した暗号文に対するエラーの理由がわかると、暗号が解けることを利用した攻撃で、たとえ、受信者側装置にエラーの理由を具体的に通知する機能がなくても、その理由を返すまでの時間を計測することで、攻撃者は拒絶理由を知ることが可能である。
【０００６】
【発明が解決しようとする課題】
このような攻撃を防ぐために、例えば、復号化エンジン（または装置）において最上位ビットを虫して処理を行うなどの方法も考えられる。しかし、この場合も、復号化エンジン部分の情報がもれるような仕掛けがあった場合には、復号化エンジンは文献８に記載の方法による攻撃が可能となり、依然、安全性に問題が残る。
【０００７】
本発明は、このような事情に鑑み、不正な暗号文を復号化エンジン（または装置）に入力することにより得られたエラーメッセージから暗号文を解読するといった攻撃方法、例えば、上記文献８に記載の実装攻撃など、に対して安全な公開鍵暗号通信技術を提供する。
【０００８】
【課題を解決するための手段】
上記課題を解決するために、本発明では、不正な暗号文が受信者側の装置に入力された場合でも、攻撃者が、そのエラーの理由を識別できないようにする。すなわち、受信者側装置において不正な暗号文を拒絶する理由を１つとし、不正な暗号文が受信者側装置に入力された場合でも、攻撃者が、不正であることの根拠をパディングチェック以外に知ることができないようにする。
【０００９】
具体的には、送信者側装置において、メッセージデータを暗号化し暗号文を作成するとともに当該暗号文を受信者側装置へ送信し、前記受信者側装置において、前記暗号文を受信して復号化する公開鍵暗号通信方法であって、
前記送信者側装置において、
入力されたメッセージデータに対し第一のパディングを行い、パディングされたメッセージデータを変換するとともに、当該変換されたデータのハッシュ値を得るステップと、
前記変換されたデータと前記ハッシュ値とを連接したデータに対し、必要に応じて任意のビット値を持つビットを付加して前記公開鍵暗号の平文空間に含まれる任意の元となりうるように第二のパディングを行うステップと、
前記第二のパディングを行った結果得られたデータを暗号化し暗号文を作成して前記受信者側装置に送信するステップとを行い、
前記受信者側装置において、
前記送信者側装置から送信された暗号文を受信し、復号化するステップと、
前記復号化されたデータに対して、前記第一のパディングによるパディングのチェックを行い、当該データの正当性を判別するステップとを行うことを特徴とする公開鍵暗号通信方法を提供する。
【００１０】
なお、本発明において、暗号化対象となる平文（メッセージともいう）は、文字列のみならず、画像や音、あるいは、送信データの暗号化のために使用する共通鍵など、あらゆるディジタルデータが該当する。
【００１１】
また、本明細書および図面において、”＋”を円で囲んだ記号は、排他的論理和を示している。
【００１２】
本発明においては、前述のように、変換されたデータとハッシュ値とを連接したデータに対し、必要に応じて任意のビット値を持つビットを付加して公開鍵暗号の平文空間に含まれる任意の元となりうるように第二のパディングを行うため、復号化処理エンジンにおけるインテグリティチェックが無意味となり、エラーの根拠はパディングのチェックによるもののみとなる。
【００１３】
このため、たとえ攻撃者が、多種多様な不正な暗号文を送信したとしても、不正と判断された根拠は１つしかわからず、不正と判断された原因を利用して暗号を解読することが困難となり、従来の手法と比べて、安全性の高いものとなる。例えば、文献５に記載のＯＡＥＰをパディングの方法として選んだ場合、本発明の暗号化エンジンは、公開鍵暗号の暗号化関数ｆに対して（但し、
【００１４】
【数４０】
2004012826.tif 000003
【００１５】
とする。）、メッセージｍ∈｛０，１｝ｎから、
【００１６】
【数４１】
2004012826.tif 000004
【００１７】
を計算し（但し、
【００１８】
【数４２】
2004012826.tif 000005
【００１９】
ｋ＝ｎ＋ｋ０＋ｋ１とする。）、さらに、
【００２０】
【数４３】
2004012826.tif 000006
【００２１】
を計算し、暗号文ｙをｙ＝ｆ（ｘ）にて作成する。ここで、記号ａ｜｜ｂはａとｂの連接を意味する。
【００２２】
一方、本発明の復号化処理エンジンは、前記公開鍵暗号の復号化関数ｆ−１を用いて、
【００２３】
【数４４】
2004012826.tif 000007
【００２４】
なるｂ’、ｓ’、ｔ’を計算し、さらに、
【００２５】
【数４５】
2004012826.tif 000008
【００２６】
なるｒ’を計算し、ｓ’とｒ’とを用い、
【００２７】
【数４６】
2004012826.tif 000009
【００２８】
なるｍ’およびｚ’を計算し、
【００２９】
【数４７】
2004012826.tif 000010
【００３０】
を復号化結果として出力する。ここで、復号化結果の出力が「＊」場合は、復号化エンジンが、暗号文を不正なものとみなし拒否したことを意味する。
【００３１】
【発明の実施の形態】
以下、本発明の実施の形態について説明する。
【００３２】
まず、以下の各実施形態に共通する公開鍵暗号通信システムの構成について説明する。
【００３３】
図１は、本発明の各実施形態に共通する公開鍵暗号通信システムの概略構成図である。本図に示すように、本実施の形態における公開鍵暗号通信システムは、暗号化処理を行って暗号文を作成する送信者側装置１００と、復号化処理を行って平文を復元する受信者側装置２００とが、通信回線３００を介して接続された構成を有している。
【００３４】
図２は、図１に示す送信者側装置１００の概略構成図である。本図に示すように、送信者側装置１００は、暗号化対象の平文を含む各種情報の入力を受付ける入力装置１０１と、パディング処理装置１０２と、ハッシュ値計算装置１０３と、暗号化装置１０４と、通信回線３００を介して受信者側装置２００と通信を行う通信装置１０５とを備えている。
【００３５】
図３は、図１に示す受信者側装置２００の概略構成図である。本図に示すように、受信者側装置２００は、通信回線３００を介して送信者側装置１００と通信を行う通信装置２０１と、復号化装置２０２と、パディング処理装置２０３と、ハッシュ値計算装置２０４と、復号結果を含む各種情報を出力する出力装置２０５とを備えている。
【００３６】
上記構成の送信者側装置１００および受信者側装置２００は、図４に示すような、ＣＰＵ４０１と、メモリ４０２と、ＨＤＤ等の外部記憶装置４０３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体４０４から情報を読み出す読取装置４０５と、キーボードやマウスなどの入力装置４０６と、ディスプレイなどの出力装置４０７と、通信回線３００を介して相手装置と通信を行うための通信装置４０８とを備えた一般的なコンピュータシステムにおいて、ＣＰＵ４０１がメモリ４０２上にロードされた所定のプログラムを実行することにより実現することができる。
【００３７】
この所定のプログラムは、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、外部記憶装置４０３にダウンロードされ、それから、メモリ４０２上にロードされてＣＰＵ４０１により実行されるようにしてもよい。また、読取装置４０５を介して記憶媒体４０４から、あるいは、通信装置４０８を介して通信回線３００から、メモリ４０２上に直接ロードされ、ＣＰＵ４０１により実行されるようにしてもよい。
【００３８】
送信者側装置１００は、入力装置１０１で受付けたメッセージ文に対し、パディング処理装置１０２とハッシュ値計算装置１０３とにおいて、第一のパディングを行い、そのパディングされたメッセージ文を変換するとともに、その変換されたデータのハッシュ値を得、さらに、変換されたデータとそのハッシュ値とを連接したデータに対し、必要に応じて任意のビット値を持つビットを付加して公開鍵暗号の平文空間に含まれる任意の元となりうるように第二のパディングを行う。そして、送信者側装置１００は、暗号化装置１０４を用いてその第二のパディングの結果得られたデータを暗号化し暗号文を作成して、通信装置１０５から、通信回線３００を介して、その暗号文を受信者側装置２００に送信する。
【００３９】
受信者側装置２００は、通信装置２０１によって送信者側装置１００から送信された暗号文を受信し、復号化装置２０２とパディング処理装置２０３とハッシュ値計算装置２０４とを用いてその暗号文を復号化し、その復号化されたデータに対して、前述の第一のパディングによるパディングのチェックを行い、そのデータの正当性を判別し、その結果を出力装置２０５から出力する。
【００４０】
また、送信者側装置１００は、受付けたメッセージ文に対し、上記パディング処理装置１０２とハッシュ値計算装置１０３によってパディングを行い、ｋビットのデータ長を持つデータｖを作成する。公開鍵暗号の平文空間Ａが、ｋ＋１ビットである場合、データｖの先頭に０か１を任意に１ビット加えデータｗを計算する。ここで、データｖの先頭に１をパディングした時に、平文空間Ａの元でなくなる場合は、データｖをそのままデータｗとする。暗号化装置１０４によって、データｗを公開鍵暗号の暗号化関数ｆを用いて暗号文ｙ＝ｆ（ｗ）を作成し、通信装置１０５から送信する。
【００４１】
受信者側装置２００は、通信装置２０１によって受信した暗号文ｙに対し、復号化装置２０２において、復号化関数ｆ−１を用いて復号化し、パディング処理装置２０３とハッシュ値計算装置２０４によって、メッセージの正当性をチェックし、正当と判断した場合は、出力装置２０５から復号化されたメッセージを、不正と判断した場合は、出力装置２０５からエラーを出力する。
【００４２】
以下に、具体的なパディング方法および暗号化・復号化関数による、本発明の実施の形態を説明する。なお、図１〜図４に示される装置および構成は以下の各実施形態に共通するものである。
（第一実施形態）
本発明の第一実施形態について説明する。図５は、本発明の第一実施形態の、送信者側装置１００内で、メッセージ文ｍから暗号文ｙを算出するまでの動作手順を説明するための図である。そして、図６は、本発明の第一実施形態の、受信者側装置２００で、受け取った暗号文ｙを復号化するまでの動作手順を説明するための図である。
【００４３】
本実施の形態は、
【００４４】
【数４８】
2004012826.tif 000011
【００４５】
なる暗号化関数ｆを持つ公開鍵暗号に、パディングの方法として文献５に記載されているＯＡＥＰ　（Ｏｐｔｉｍａｌ　Ａｓｙｍｍｅｔｒｉｃ　Ｅｎｃｒｙｐｔｉｏｎ）を用いるものである。この場合の、暗号化および復号化手順について以下に説明する。
【００４６】
送信者側装置１００内の入力装置１０１において、メッセージ文の送信者から、メッセージ文ｍ∈｛０，１｝ｎの入力を受付けると（図５：ステップＳＴ５０１）、送信者側装置１００は、パディング処理装置１０２とハッシュ値計算装置１０３において、メッセージ文ｍにＯｋｏビットを付加することでパディングしたものを暗号化することで得られるｓ、および、ｓのハッシュ値から得られるｔを下記のように求める。
【００４７】
【数４９】
2004012826.tif 000012
【００４８】
（但し、
【００４９】
【数５０】
2004012826.tif 000013
【００５０】
ｋ＝ｎ＋ｋ０＋ｋ１とする。）（図５：ステップＳＴ５０２）。さらに、前述のｓ、ｔを連接し、その平文空間Ａにビット長を合わせるため、下記の計算を行う。
【００５１】
【数５１】
2004012826.tif 000014
【００５２】
ここで、記号ａ｜｜ｂはａとｂの連接を意味する（図５：ステップＳＴ５０３、ＳＴ５０４、ＳＴ５０５、ＳＴ５０６）。本計算により、正当な処理を経て得られた暗号文であっても最上位ビットが１である可能性がうまれ、受信者側装置で最上位ビットが０か１かで正当性、不当性を判断するインテグリティチェックが無意味なものとなる。
【００５３】
送信者側装置１００は、暗号化装置１０４において、上記の計算結果ｘから、公開鍵暗号ｆを用い、暗号文ｙ＝ｆ（ｘ）を計算し（図５：ステップＳＴ５０７）、通信装置１０５を用いて、暗号文ｙを受信者側装置２００に通信回線３００を介して送信する。
受信者側装置２００は、通信装置２０１において暗号文ｙを受信し（図６：ステップＳＴ６０１）、復号化装置２０２において、公開鍵暗号の秘密鍵ｆ−１を用いて
【００５４】
【数５２】
2004012826.tif 000015
【００５５】
なるｂ’、ｓ’、ｔ’を計算する（図６：ステップＳＴ６０２）。さらに、得られたｓ’のハッシュ値とｔ’とを用い、パディング処理装置２０３、ハッシュ値計算装置２０４において、
【００５６】
【数５３】
2004012826.tif 000016
【００５７】
なるｒ’を計算し（図６：ステップＳＴ６０３）、このｒ’とｓ’とから、
【００５８】
【数５４】
2004012826.tif 000017
【００５９】
なるｍ’およびｚ’を計算し（図６：ステップＳＴ６０４）、出力装置２０５を用いて復号化結果として、復号化されたメッセージｍ’または「＊」を以下のように出力する。
【００６０】
【数５５】
2004012826.tif 000018
【００６１】
（図６：ステップＳＴ６０５、ＳＴ６０６、ＳＴ６０７）。これは、受信者側装置２００は、ｚ’が、受信者側装置１００のパディング処理において付加された０ｋｏであった場合のみ、メッセージが正当なものと判断するものである。つまり、復号化結果の出力が「＊」の場合は、受信者側装置２００は、この暗号文を不正なものとみなし拒否したことを意味する。
【００６２】
本実施形態では、受信者側装置２００におけるパディングのチェックのみで、その暗号文が不正かどうかのチェックを行うことができる。すなわち、受信した暗号文の正当性のチェックとして、パディングチェックしか行わないものである。このため、不正な暗号文を受信者側装置２００に入力した攻撃者は、出力された結果から、不正であると判断された根拠として、パディングのチェック以外の理由を知ることができない。これにより、パディングチェック以外によるエラーを、攻撃者が知り得ることにより行われる文献８に記載の実装攻撃を防ぐことが可能になる。
（第二実施形態）
本実施形態は第一実施形態の変形例であり、文献５に記載のＲＳＡ−ＯＡＥＰに適用したものである。以下に、本実施形態における、暗号化および復号化手順について説明する。
【００６３】
送信者側装置１００内の入力装置１０１において、メッセージ文の送信者から、メッセージ文ｍ∈｛０，１｝ｎの入力を受付けると、送信者側装置１００は、パディング処理装置１０２とハッシュ値計算装置１０３において、
【００６４】
【数５６】
2004012826.tif 000019
【００６５】
を計算する（但し、
【００６６】
【数５７】
2004012826.tif 000020
【００６７】
ｋ＝ｎ＋ｋ０＋ｋ１とする。）。さらに、その結果のｓ、ｔを用いて、
【００６８】
【数５８】
2004012826.tif 000021
【００６９】
を計算する。ここで、記号ａ｜｜ｂはａとｂの連接を意味する。
【００７０】
送信者側装置１００は、暗号化装置１０４において、上記の計算結果ｘを用い、
【００７１】
【数５９】
2004012826.tif 000022
【００７２】
を計算する。但し、ＲＳＡ暗号の公開鍵（ｅ，Ｎ）および秘密鍵ｄにおいて、
【００７３】
【数６０】
2004012826.tif 000023
【００７４】
なる関係がある。送信者側装置１００は通信装置１０５を用いて、暗号文ｙを受信者側装置２００に通信回線３００を介して送信する。
受信者側装置２００は、通信装置２０１を用いて暗号文ｙを受信し、ＲＳＡ暗号の秘密鍵ｄを用いて復号化装置２０２において、
【００７５】
【数６１】
2004012826.tif 000024
【００７６】
なるｂ’、ｓ’、ｔ’を計算する。さらに、得られたｓ’、ｔ’を用い、パディング処理装置２０３、ハッシュ値計算装置２０４において、
【００７７】
【数６２】
2004012826.tif 000025
【００７８】
なるｒ’を計算し、このｒ’とｓ’とから、
【００７９】
【数６３】
2004012826.tif 000026
【００８０】
なるｍ’およびｚ’を計算し、出力装置２０５を用いて復号化結果として、
【００８１】
【数６４】
2004012826.tif 000027
【００８２】
を出力する。これは、受信者側装置２００は、ｚ’が、受信者側装置１００のパディング処理において付加された０ｋｏであった場合のみ、メッセージが正当なものと判断するものである。つまり、復号化結果の出力が「＊」の場合は、受信者側装置２００は、この暗号文を不正なものとみなし拒否したことを意味する。
【００８３】
このように、第一実施形態の暗号化および復号化の処理方法を、ＲＳＡ−ＯＡＥＰに適用した場合であっても、受信者側装置２００においてパディングのチェックのみで、その暗号文が不正かどうかのチェックを行うことができる。すなわち、受信した暗号文の正当性のチェックとして、受信者側装置２００において、パディングチェックしか行わないものである。このため、不正な暗号文を受信者側装置２００に入力した攻撃者は、出力された結果から、不正であると判断された根拠として、パディングのチェック以外の理由を知ることができない。これにより、本実施形態においても、パディングチェック以外によるエラーを、攻撃者が知り得ることにより行われる文献８に記載の実装攻撃を防ぐことが可能になる。
（第三実施形態）
本実施形態は、
【００８４】
【数６５】
2004012826.tif 000028
【００８５】
なる暗号化関数ｆを持つ公開鍵暗号に、パディングの方法として文献６に記載のＯＡＥＰ＋を用いるものである。この場合の、暗号化および復号化手順について以下に説明する。
【００８６】
送信者側装置１００内の入力装置１０１において、メッセージ文の送信者から、メッセージ文ｍ∈｛０，１｝ｎの入力を受付けると、パディング処理装置１０２とハッシュ値計算装置１０３において、
【００８７】
【数６６】
2004012826.tif 000029
【００８８】
を計算する（但し、
【００８９】
【数６７】
2004012826.tif 000030
【００９０】
ｋ＝ｎ＋ｋ０＋ｋ１とする。）。さらに、得られたｓ、ｔを用いて、
【００９１】
【数６８】
2004012826.tif 000031
【００９２】
を計算する。ここで、記号ａ｜｜ｂはａとｂの連接を意味する。
【００９３】
送信者側装置１００は、暗号化装置１０４において、上記の計算結果ｘを用い、ｙ＝ｆ（ｘ）を計算し、通信装置１０５を用いて、暗号文ｙを受信者側装置２００に通信回線３００を介して送信する。
受信者側装置２００は、通信装置２０１において暗号文ｙを受信し、復号化装置２０２において、
【００９４】
【数６９】
2004012826.tif 000032
【００９５】
なるｂ’、ｓ’、ｔ’を計算する。さらに、パディング処理装置２０３、ハッシュ値計算装置２０４において、
【００９６】
【数７０】
2004012826.tif 000033
【００９７】
なるｒ’を計算し、このｒ’とｓ’とから、
【００９８】
【数７１】
2004012826.tif 000034
【００９９】
なるｍ’を計算し（但し、
【０１００】
【数７２】
2004012826.tif 000035
【０１０１】
である）、出力装置２０５を用いて復号化結果として、
【０１０２】
【数７３】
2004012826.tif 000036
【０１０３】
を出力する。これは、受信者側装置２００は、ｚ’が、受信者側装置１００のパディング処理において付加されたものであった場合のみ、メッセージが正当なものと判断するものである。つまり、復号化結果の出力が「＊」の場合は、受信者側装置２００は、この暗号文を不正なものとみなし拒否したことを意味する。
【０１０４】
このように、パディングの方法として文献６に記載のＯＡＥＰ＋を用いた場合であっても、受信者側装置２００においてパディングのチェックのみで、その暗号文が不正かどうかのチェックを行うことができる。すなわち、受信した暗号文の正当性のチェックとして、受信者側装置２００において、パディングチェックしか行わないものである。このため、不正な暗号文を受信者側装置２００に入力した攻撃者は、出力された結果から、不正であると判断された根拠として、パディングのチェック以外の理由を知ることができない。これにより、本実施形態においても、パディングチェック以外によるエラーを、攻撃者が知り得ることにより行われる文献８に記載の実装攻撃を防ぐことが可能になる。
（第四実施形態）
本実施形態は第三実施形態の変形例であり、文献６に記載のＲＳＡ−ＯＡＥＰ＋に適用したものである。以下に、本実施形態における暗号化および復号化手順について説明する。
送信者側装置１００内の入力装置１０１において、メッセージ文の送信者から、メッセージ文ｍ∈｛０，１｝ｎの入力を受付けると、送信者側装置１００は、パディング処理装置１０２とハッシュ値計算装置１０３において、
【０１０５】
【数７４】
2004012826.tif 000037
【０１０６】
を計算する（但し、
【０１０７】
【数７５】
2004012826.tif 000038
【０１０８】
ｋ＝ｎ＋ｋ０＋ｋ１とする。）。さらに、その結果のｓ、ｔを用いて、
【０１０９】
【数７６】
2004012826.tif 000039
【０１１０】
を計算する。ここで、記号ａ｜｜ｂはａとｂの連接を意味する。
【０１１１】
送信者側装置１００は、暗号化装置１０４において、上記の計算結果ｘを用い、、
【０１１２】
【数７７】
2004012826.tif 000040
【０１１３】
を計算する。但し、ＲＳＡ暗号の公開鍵（ｅ，Ｎ）および秘密鍵ｄにおいて、
【０１１４】
【数７８】
2004012826.tif 000041
【０１１５】
なる関係がある。送信者側装置１００は通信装置１０５を用いて、暗号文ｙを受信者側装置２００に通信回線３００を介して送信する。
受信者側装置２００は、通信装置２０１を用いて暗号文ｙを受信し、ＲＳＡ暗号の秘密鍵ｄを用いて復号化装置２０２において、
【０１１６】
【数７９】
2004012826.tif 000042
【０１１７】
なるｂ’、ｓ’、ｔ’を計算する。さらに、得られたｓ’、ｔ’を用い、パディング処理装置２０３、ハッシュ値計算装置２０４において、
【０１１８】
【数８０】
2004012826.tif 000043
【０１１９】
なるｒ’を計算し、このｒ’とｓ’とから、
【０１２０】
【数８１】
2004012826.tif 000044
【０１２１】
なるｍ’を計算し（但し、
【０１２２】
【数８２】
2004012826.tif 000045
【０１２３】
である）、出力装置２０５を用いて復号化結果として、
【０１２４】
【数８３】
2004012826.tif 000046
【０１２５】
を出力する。これは、受信者側装置２００は、ｚ’が、受信者側装置１００のパディング処理において付加されたものであった場合のみ、メッセージが正当なものと判断するものである。つまり、復号化結果の出力が「＊」の場合は、受信者側装置２００は、この暗号文を不正なものとみなし拒否したことを意味する。
【０１２６】
このように、第三実施形態の暗号化および復号化の処理方法を、ＲＳＡ−ＯＡＥＰ＋に適用した場合であっても、受信者側装置２００においてパディングのチェックのみで、その暗号文が不正かどうかのチェックを行うことができる。すなわち、受信した暗号文の正当性のチェックとして、受信者側装置２００において、パディングチェックしか行わないものである。このため、不正な暗号文を受信者側装置２００に入力した攻撃者は、出力された結果から、不正であると判断された根拠として、パディングのチェック以外の理由を知ることができない。これにより、本実施形態においても、パディングチェック以外によるエラーを、攻撃者が知り得ることにより行われる文献８に記載の実装攻撃を防ぐことが可能になる。
【０１２７】
以上、本発明の実施形態について、説明した。なお、本発明は、上記の各実施形態に限定されるものではなく、その要旨の範囲内で数々の変形が可能である。
【０１２８】
例えば、上記の各実施例では、パディングの方法としては、ＯＡＥＰとＯＡＥＰ＋を用いる場合を例にとり説明したが、本発明は、その他様々なパディング方法についても適用することができる。例えば、文献９「Ｄ．Ｂｏｎｅｈ．：　Ｓｉｍｐｌｉｆｉｅｄ　ＯＡＥＰ　ｆｏｒ　ｔｈｅ　ＲＳＡ　ａｎｄ　Ｒａｂｉｎ　ｆｕｎｃｔｉｏｎｓ，　Ａｄｖａｎｃｅｓ　ｉｎ　Ｃｒｙｐｔｏｌｏｇｙ−Ｃｒｙｐｔｏ２００１，　ＬＮＣＳ２１３９，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，　ｐｐ．２７５−２９１　（２００１）」に記載のＳＡＥＰおよびＳＡＥＰ＋、また、文献１０「Ｅ．　Ｆｕｊｉｓａｋｉ　ａｎｄ　Ｔ．　Ｏｋａｍｏｔｏ．：　Ｈｏｗ　ｔｏ　Ｅｎｈａｎｃｅ　ｔｈｅ　Ｓｅｃｕｒｉｔｙ　ｏｆ　Ｐｕｂｌｉｃ−Ｋｅｙ　Ｅｎｃｒｙｐｔｉｏｎ　ａｔ　Ｍｉｎｉｍｕｍ　Ｃｏｓｔ，　Ｐｕｂｌｉｃ　Ｋｅｙ　Ｃｒｙｐｔｏｇｒａｐｈｙ，　ＬＮＣＳ１５６０，　Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，　ｐｐ．　５３−６８　（１９９９）」に記載のパディング方法にも適用可能である。
【０１２９】
また、本発明の方法によると、攻撃者（復号化エンジンを含める）は、最上位ビットの値を確率的にしか判断できないため、復号化エンジンへの質問の数が増えるに伴い、最上位ビットを全て正しく予想できる確率は指数関数的に増大する。このため、復号化エンジンにおいて最上位ビットを無視して処理を行うなどの攻撃に対しても、安全性の高い暗号化および復号化装置を提供できる。
なお、上記の各実施形態での各計算は、ＣＰＵがメモリ上にロードされたプログラムを実行することにより行われるものとして説明した。しかし、プログラムによるものだけではなく、いずれかの計算を行う装置は、ハードウエア化された演算装置であって、他の演算装置や、ＣＰＵと、データのやりとりを行うものであっても良い。
【０１３０】
【発明の効果】
本発明によれば、不正な暗号文を復号化エンジン（または装置）に入力することにより得られたエラーメッセージから暗号文を解読するといった攻撃方法に対して安全な暗号化および復号化処理を行うことが可能となる。
【図面の簡単な説明】
【図１】本発明の各実施形態に共通するシステムの概略構成図である。
【図２】図１に示す送信者側装置１００の概略構成図である。
【図３】図１に示す受信者側装置２００の概略構成図である。
【図４】送信者側装置１００および受信者側装置２００のハードウエア構成例を示す図である。
【図５】本発明の第一実施形態の、送信者側装置１００内の動作手順を説明するための図である。
【図６】本発明の第一実施形態の、受信者側装置２００内の動作手順を説明するための図である。
【符号の説明】
１００…送信者側装置、１０１…入力装置、１０２…パディング処理装置、１０３…ハッシュ値計算装置、１０４…暗号化装置、１０５…通信装置、２００…受信者側装置、２０１…通信装置、２０２…復号化装置、２０３…パディング処理装置、２０４…ハッシュ値計算装置、２０５…出力装置
【図１】
2004012826.tif 000086
【図２】
2004012826.tif 000087
【図３】
2004012826.tif 000088
【図４】
2004012826.tif 000089
【図５】
2004012826.tif 000090
【図６】
2004012826.tif 000091