JP2005072650A - 被検証装置、検証装置、被検証方法及び検証方法 - Google Patents

Abstract

【課題】全てのＰＳＰＡＣＥクラス及びＮＰクラスの問題が適用可能なメッセージ認証方式を実現する。
【解決手段】被検証装置は、秘密情報Ｔから Ｚ＝Ｔ^２ ｍｏｄ ｎ なるＺ、ｎを安全な方法で届ける（Ｓ１）。被検証装置は、送信するメッセージから前方誤り訂正符号を用いて乱数Ｒｉを生成し、Ｘｉ＝Ｒｉ^２ｍｏｄ ｎ を計算してＸｉを送る（Ｓ２）。検証装置は、０又は１をランダムに選び、選んだｂｉを送る（Ｓ３）。被検証装置は、ｂｉ＝０のときＹｉ（＝Ｒｉ）を、ｂｉ＝１のときＹｉ（＝ＴＲｉ ｍｏｄ ｎ）を送る（Ｓ４）。そして、検証装置は、ｂｉ＝０のときＸｉ＝Ｙｉ^２ ｍｏｄ ｎ が成立するか否かを、ｂｉ＝１のときＺＸｉ＝Ｙｉ^２ｍｏｄ ｎ が成立するか否かを検査する（Ｓ５）。検証装置は、ｂｉ＝０に対する回答情報Ｙｉ（＝Ｒｉ）に前方誤り訂正符号を適用して受信メッセージを復元する。この送受信には、被検証装置の正当性の検証が伴っているため、メッセージ認証の機能を果たす。
【選択図】 図１

Description

【０００１】
【発明の属する技術分野】
本発明は、一方向性関数を用いた対話証明を行う被検証装置及び検証装置、これらの各々にて行われる被検証方法及び検証方法に関する。
【０００２】
【従来の技術】
２者間の通信でメッセージを改竄されることなく届ける（改竄された場合はそれを検知できる）方式として、ハッシュ関数を使う方法と電子署名がある。通信する２者（通信端末Ａと通信端末Ｂとする）が、あらかじめ秘密の共有鍵を共有していれば、鍵付きハッシュ関数（ＨＭＡＣ−ＳＨＡ１、ＨＭＡＣ−ＭＤ５）等でメッセージダイジェストを生成して添付することにより、改竄を検知できる。この方法は、通信端末Ａと通信端末Ｂがあらかじめ秘密を共有していなければできない。
【０００３】
通信端末Ａと通信端末Ｂが秘密を共有していない場合は、公開鍵、秘密鍵を用いて電子署名する。通信端末Ａが通信端末Ｂに電子署名してメッセージを送信する場合、まず通信端末Ａは自分の公開鍵を公開する。通信端末Ｂは通信端末Ａの公開鍵を取得する。次に通信端末Ａは通信端末Ｂに送信するメッセージを自分の秘密鍵を用いて電子署名を作成し、これを添付して通信端末Ｂに送信する。通信端末Ｂは通信端末Ａから送られてきたメッセージと電子署名を通信端末Ａの公開鍵を用いて検証でき、メッセージが改竄されていないかを確認できる。
【０００４】
この公開鍵、秘密鍵を用いて電子署名するアルゴリズムの多くは、現状では数論の素因数分解問題及び離散対数問題に基づいている（下記の特許文献１、２参照）。前者は大きな整数の素因数分解は計算量的に困難であるという特性に基づいており、ＲＳＡ署名等がある。後者は、ｍｏｄ ｐ による剰余体（ｐは素数）での離散対数の計算が計算量的に困難であるという特性に基づいており、Ｅｌｇａｍａｌ署名やＤＳＡ署名等がある。
【特許文献１】
特開２００２−２０７４２６号公報
【特許文献２】
特開２００２−１３５２４２号公報
【０００５】
【発明が解決しようとする課題】
現状では、素因数分解問題や離散対数問題は高速に解くための解法が研究されており、秘密鍵が解読されないためには、１０２４ビットの公開鍵が必要と言われている。また、楕円曲線上の離散対数問題では、１６０ビットで安全と言われている。
【０００６】
しかしながら、これらの問題が今後も安全という保証は無く、鍵長を長くしてもすぐに解けてしまう解法が見つかるかもしれない。即ち、素因数分解問題及び離散対数問題以外の問題も含む広い範囲の問題に適用可能で、電子署名と同等の効果を持つメッセージ送受信方式が待望されていた。
【０００７】
本発明は、上記課題を解決するために成されたものであり、送信側と受信側の間に介在する第三者による情報の改竄を防止することを目的とする。
【０００８】
【課題を解決するための手段】
本願発明者は、素因数分解問題及び離散対数問題以外の問題でも実現でき、電子署名と同等の効果を持つメッセージ送受信に関する発明をした。本発明は、一方向性関数を利用した対話証明方式を応用し、通信する２者間でメッセージを改竄されることなく送受信できる方式である。一方向性関数を利用した対話証明方式は、一方向性関数が存在するすべてのＰＳＰＡＣＥ問題をベースにして実現できることが証明されている（文献「Ｓｈａｍｉｒ， Ａ．， ＊ＩＰ＝ＰＳＰＡＣＥ＊ Ｐｒｏｃ． ｏｆ ＦＯＣＳ， ｐｐ．１１−１５， １９９０」参照）。本発明は、この対話証明方式のフローの中でメッセージを送受信できる方式であり、素因数分解問題及び離散対数問題以外のＰＳＰＡＣＥ問題及びＮＰ問題をベースにして電子署名と同等のメッセージ送受信を実現できることになる。
【０００９】
以下、まず、一方向性関数を利用した対話証明の原理について説明し、その後、本発明の詳細を述べる。
【００１０】
［一方向性関数を利用した対話証明の原理］
一方向性関数を利用した対話証明方式を用いることにより、ある秘密情報を持っている装置は、その秘密情報を漏らさずに「秘密情報を持っていること」を相手に認識させることができる。その原理としては、まず秘密情報を持っていることを証明する装置（被検証装置）は、ある演算を乱数に施して得た演算結果を検証装置に送る。次に検証装置は、０か１かを任意に選び（例えば、コイン投げをして表か裏かでもよい）、選んだ値を被検証装置に送る。被検証装置は、その値が０であれば乱数そのものを検証装置に送り、その値が１であれば乱数と秘密情報とを演算して得た演算結果を送る。そして、検証装置は、被検証装置から送信されたこれらの情報が公知の関係を満たしているかどうかを検証する。
【００１１】
仮に、被検証装置が秘密情報を持っていないとすると、被検証装置はこの検証に５０％の確率でしか合格できない。したがって、このような検証を多くの回数繰り返すことによって、被検証装置が秘密情報を持っているか否かを、限りなく１００％に近い確率で検証することができる。ここでは、一例として、図１を用いて、平方剰余問題を用いた対話証明方式を説明する。
【００１２】
ステップＳ１として、被検証装置は、秘密情報Ｔから Ｚ＝Ｔ^２ ｍｏｄ ｎ なるＺ及びｎを検証装置に安全な方法で届ける。ここで、ｎ ＝ ｐｑ（ｐとｑは大きい素数）であるため、ｎを素因数分解するのは非常に難しい。
【００１３】
ステップＳ２として、被検証装置は、乱数Ｒを選び、Ｘ＝Ｒ^２ ｍｏｄ ｎ を計算し、得られたＸを検証装置に送る。
【００１４】
ステップＳ３として、検証装置は、ｂとして０又は１のうち何れかを二者択一的にランダムに選び、選んだｂを被検証装置に送る。
【００１５】
ステップＳ４として、被検証装置は、次のＹを検証装置に送る。ｂ ＝ ０のとき、Ｙ ＝ Ｒであり、ｂ ＝ １のとき、Ｙ ＝ ＴＲ ｍｏｄ ｎ である。
【００１６】
そして、ステップＳ５として、検証装置は、次式が成立するか否かを検査する。即ち、ｂ ＝ ０ のときは、Ｘ ＝ Ｙ^２ ｍｏｄ ｎ が成立するか。ｂ ＝ １ のときは、ＺＸ ＝ Ｙ^２ｍｏｄ ｎ が成立するか。
【００１７】
以上のような対話証明方式では、被検証装置が本当に秘密情報Ｔを知っていたら、ステップＳ５での検証にはいつも合格する。上記のステップＳ２〜Ｓ５をｋ回繰り返せば、偽の被検証装置がだまし続けられる確率は、（１／２）^ｋとなる。
【００１８】
なお、ステップＳ２〜Ｓ５をｋ回繰り返すのを省略して、代わりに、ステップＳ２で乱数をｋ個（Ｒ_１， Ｒ_２，…Ｒ_ｋ）生成し、Ｘ＝ Ｒ^２ ｍｏｄ ｎで計算した結果（Ｘ_１， Ｘ_２，…Ｘ_ｋ）を送る。次のステップＳ３で検証装置は、二者択一的にランダムに選んだｋ個の｛０，１｝の列（ｂ_１， ｂ_２，…ｂ_ｋ）を被検証装置に送り、同様にステップＳ４で、被検証装置は回答の列（Ｙ_１， Ｙ_２，…Ｙ_ｋ）を検証装置に送る。そして、検証装置は、回答の列（Ｙ_１， Ｙ_２，…Ｙ_ｋ）を１つ１つ検査し、それら全てが正解であったときのみ、被検証装置が秘密情報を持っていることを認定する。以上のようにして、一方向性関数を利用して対話証明を適正に行うことができる。
【００１９】
［本発明に関する請求の範囲］
以下、本発明に関する請求の範囲を述べる。
【００２０】
前述した目的を達成するため、本発明に係る被検証装置は、請求項１に記載したように、送信メッセージの入力を受け付け、前記送信メッセージから冗長情報を、当該冗長情報から前記送信メッセージを生成できるよう設計された計算式に基づいて生成し、生成された冗長情報及び生成に利用された計算式を出力する冗長情報生成手段と、前記冗長情報生成手段により出力された冗長情報と計算式とを連結させる計算式連結手段と、前記計算式連結手段による連結で得られた計算式連結済み冗長情報を乱数として用いて、検証装置との間で一方向性関数を用いた対話証明を行う対話証明手段とを備え、前記対話証明手段は、対話証明において、乱数に対し一方向性関数の演算を行った演算結果を第１のメッセージとして送信し、検証装置から確率的な質問を受信し、受信された質問に応じて、乱数そのもの、又は、乱数と秘密情報から得られる値に対し一方向性関数の演算を行った演算結果を、第２のメッセージとして送信することを特徴とする。
【００２１】
ここで、冗長情報生成手段は、請求項２に記載したように、前方誤り訂正符号を用いて冗長情報を生成する構成とすることが望ましく、前方誤り訂正符号を用いて生成された冗長情報が付加されたメッセージの受信側での誤り訂正を可能とし、メッセージ再送を不要とすることができる。
【００２２】
また、冗長情報生成手段は、請求項３に記載したように、送信メッセージに乱数ビットを付加し、付加後のメッセージから、前方誤り訂正符号を用いて前記冗長情報を生成する構成とすることが望ましく、送信メッセージに乱数ビットを付加することで悪意の第三者によるリプレイアタックを防止することができる。
【００２３】
更に、上記の被検証装置では、請求項４に記載したように、前方誤り訂正符号としてリードソロモン符号が用いられ、冗長データと当該冗長データの生成に利用された累乗数とを連結したものが乱数として対話証明に用いられる構成とすることが望ましく、処理時間を短縮化し、大量の前方誤り訂正符号を高速に送受信することができる。
【００２４】
前述した目的を達成するため、本発明に係る検証装置は、請求項５に記載したように、冗長情報と当該冗長情報から送信メッセージを生成できるよう設計された計算式とが連結された計算式連結済み冗長情報を、乱数として用いる被検証装置、との間で一方向性関数を用いた対話証明を行う対話証明手段と、送信メッセージを生成するメッセージ生成手段とを備え、前記対話証明手段は、対話証明において、乱数に対し一方向性関数の演算を行った演算結果を第１のメッセージとして受信し、被検証装置へ確率的な質問を送信して、当該質問に応じた回答として、乱数そのもの、又は、乱数と秘密情報から得られる値に対し一方向性関数の演算を行った演算結果を、第２のメッセージとして受信し、送信した質問、第１のメッセージ及び第２のメッセージに基づいて被検証装置の証明を行い、被検証装置の正当性が証明された場合、質問に応じた回答のうち乱数そのものを出力し、前記メッセージ生成手段は、出力された乱数に含まれている冗長情報及び計算式に基づいて送信メッセージを生成することを特徴とする。
【００２５】
ここで、メッセージ生成手段は、請求項６に記載したように、前方誤り訂正符号を用いて検証済みのメッセージから受信メッセージを生成する構成とすることが望ましく、前方誤り訂正符号により誤り訂正を可能とし、メッセージ再送を不要とすることができる。
【００２６】
また、上記の検証装置では、請求項７に記載したように、前方誤り訂正符号としてリードソロモン符号が用いられる構成とすることが望ましく、処理時間を短縮化し、大量の前方誤り訂正符号を高速に送受信することができる。
【００２７】
ところで、上記の被検証装置に関する請求項は、以下のように被検証方法に関する請求項として、記述することができる。即ち、本発明に係る被検証方法は、請求項８に記載したように、検証装置との間で一方向性関数を用いた対話証明を行う被検証装置における被検証方法であって、送信メッセージの入力を受け付け、前記送信メッセージから冗長情報を、当該冗長情報から前記送信メッセージを生成できるよう設計された計算式に基づいて生成し、生成された冗長情報及び生成に利用された計算式とを連結させ、連結で得られた計算式連結済み冗長情報を乱数として用い、当該乱数に対し一方向性関数の演算を行った演算結果を第１のメッセージとして送信し、検証装置から確率的な質問を受信し、受信された質問に応じて、乱数そのもの、又は、乱数と秘密情報から得られる値に対し一方向性関数の演算を行った演算結果を、第２のメッセージとして送信することを特徴とする。
【００２８】
また、上記の検証装置に関する請求項は、以下のように検証方法に関する請求項として、記述することができる。即ち、本発明に係る検証方法は、請求項９に記載したように、冗長情報と当該冗長情報から送信メッセージを生成できるよう設計された計算式とが連結された計算式連結済み冗長情報を、乱数として用いる被検証装置、との間で一方向性関数を用いた対話証明を行う検証装置における検証方法であって、乱数に対し一方向性関数の演算を行った演算結果を第１のメッセージとして被検証装置から受信し、被検証装置へ確率的な質問を送信し、当該質問に応じた回答として、乱数そのもの、又は、乱数と秘密情報から得られる値に対し一方向性関数の演算を行った演算結果を、第２のメッセージとして受信し、送信した質問、第１のメッセージ及び第２のメッセージに基づいて被検証装置の証明を行い、被検証装置の正当性が証明された場合、質問に応じた回答のうち乱数そのものを出力し、出力された乱数に含まれている冗長情報及び計算式に基づいて送信メッセージを生成することを特徴とする。
【００２９】
［本発明によるメッセージ送受信の説明］
本発明は、一方向性関数を用いた対話証明方式の乱数（Ｒ_１， Ｒ_２，…Ｒ_ｋ）の選び方を工夫することにより、任意のビット列を通信相手に改竄されることなく届けられる方式である。改竄された場合には改竄されたことを検知できる。以降、通信端末Ａと通信端末Ｂが通信をする場合として話を進める。
【００３０】
本発明は、まず、通信端末Ａが２つの素数ｐとｑを選び、ｎ ＝ ｐｑとなる ｎを生成する。次に秘密情報Ｔから、Ｚ＝Ｔ^２ ｍｏｄ ｎ になるＺを算出し、Ｚとｎを公開する。通信端末Ｂは通信端末ＡのＺとｎを取得する。
【００３１】
次に、秘密情報Ｔを持っている通信端末Ａは、通信端末Ｂに送信したいメッセージＭをｍ個の同じサイズのデータに等分割し、ｍ個の分割データから前方誤り訂正符号を用いてｋ個の冗長データを生成する（ｋ ＞ ｍ）。このｋ個の冗長情報を（ｒ_１， ｒ_２，… ｒ_ｋ）とし、ｒ_ｉを計算するために用いた計算式をそれぞれ（ｆ_１， ｆ_２，… ｆ_ｋ）とする。そしてそれぞれの（ｒ_ｉ， ｆ_ｉ）のペアを乱数（Ｒ_１， Ｒ_２，…Ｒ_ｋ）とし、Ｘ＝ Ｒ^２ｍｏｄ ｎで計算した結果（Ｘ_１， Ｘ_２，…Ｘ_ｋ）を通信端末Ｂに送信する。
【００３２】
メッセージＭを等分割できない場合は、等分割できるようにメッセージＭを乱数でパディングする。このパディングの中にはメッセージＭのサイズを特定できる値も入れておく。
【００３３】
次に、通信端末Ｂは、二者択一的にランダムに選んだｋ個の｛０，１｝の列（ｂ_１， ｂ_２，…ｂ_ｋ）を通信端末Ａに送る。通信端末Ａは、通信端末Ｂからの｛０，１｝の列（ｂ_１， ｂ_２，…ｂ_ｋ）に従って、以下の回答（Ｙ_１， Ｙ_２，…Ｙ_ｋ）を通信端末Ｂに送る。
【００３４】
ｂ_ｉ＝ ０ のとき Ｙ_ｉ ＝ Ｒ_ｉ
ｂ_ｉ ＝ １ のとき Ｙ_ｉ ＝ ＴＲ_ｉ ｍｏｄ ｎ
【００３５】
通信端末Ｂは、通信端末Ａから送られてきた（Ｙ_１， Ｙ_２，…Ｙ_ｋ）が次式を満たすかどうかを検査する。
【００３６】
ｂ_ｉ＝ ０ のとき Ｘ_ｉ ＝ Ｙ_ｉ ^２ ｍｏｄ ｎ
ｂ_ｉ ＝ １ のとき ＺＸ_ｉ ＝ Ｙ_ｉ ^２ ｍｏｄ ｎ
【００３７】
通信端末Ｂは、ｉ が１〜ｋ において、すべて上式を満たしたときのみ、通信端末Ａと確実に通信していると決定する。
【００３８】
通信端末Ｂは、通信端末Ａと確実に通信していると決定した後、ｂ_ｉ ＝ ０ のときに送られてきたＲ_ｉ を用いて、通信端末Ａが上記説明でｍ個に分割したメッセージＭを、前方誤り訂正符号を用いて復号する。
【００３９】
以上の手順により、通信端末Ａは、任意のメッセージを、改竄されることなく通信端末Ｂに届けることができる。もし、上記の手順での何れかの通信におけるメッセージが改竄された場合、直ちに通信端末Ｂの検査結果より異常が検知される。また、通信端末Ｂ及び通信経路で通信内容を全て盗聴した通信端末であっても、通信端末Ａの秘密情報Ｔを計算することはできない。
【００４０】
【発明の実施の形態】
以下、本発明に関する実施形態について説明する。ここでは、平方剰余問題に基づいた一方向性関数による対話証明方式を用い、前方誤り訂正符号としてリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号を用い、被検証装置（通信端末Ａ）が検証装置（通信端末Ｂ）に８１９２ビットのメッセージを送信する場合を説明する。
【００４１】
［装置構成］
まず、被検証装置及び検証装置の構成について説明する。
【００４２】
図４には、被検証装置４０１の機能ブロック構成を示す。この図４に示すように、被検証装置４０１は、送信したいメッセージである送信メッセージ４０５を入力とし、当該送信メッセージから冗長情報４０６を計算式（当該冗長情報４０６から送信メッセージを復元できるよう設計された計算式）４０７に基づいて生成し、冗長情報４０６と計算式４０７を出力する冗長情報生成手段４０２と、冗長情報４０６と上記生成に利用した計算式４０７とを連結させる計算式連結手段４０３と、連結で得られた計算式連結済み冗長情報４０８を入力とし、入力された計算式連結済み冗長情報４０８を乱数として用いて、図５の検証装置５０１と対話証明を行う対話証明手段４０４とで構成される。このうち対話証明手段４０４は、乱数からＸ （Ｘ＝Ｒ^２ ｍｏｄ ｎ）を生成し第１のメッセージ４０９としてを出力する。また、対話証明手段４０４は、検証装置５０１からの確率的な質問（０か１か）である第２のメッセージ４１０が入力されると、その質問に対する回答を生成し、生成された回答を第３のメッセージ４１１として出力する。
【００４３】
図５には、検証装置５０１の機能ブロック構成を示す。この図５に示すように、検証装置５０１は、図４の被検証装置４０１と対話証明を行う際に検証済みの第３のメッセージ５０７を出力する対話証明手段５０２と、検証済みの第３のメッセージ５０７が入力されると、当該第３のメッセージ５０７に含まれている冗長情報と計算式とに基づいてメッセージを生成し（即ち、図４の送信メッセージ４０５を復元し）、生成されたメッセージを受信メッセージ５０８として出力するメッセージ生成手段５０３とで構成される。
【００４４】
［処理内容］
以下、本実施形態の処理として、平方剰余問題に基づいた一方向性関数による対話証明方式を用い、前方誤り訂正符号としてリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号を用いて、被検証装置（通信端末Ａ）が検証装置（通信端末Ｂ）に８１９２ビットのメッセージを送信する処理を図６、図７、図２、図３に基づいて説明する。なお、図６は被検証装置（通信端末Ａ）における処理を、図７は検証装置（通信端末Ｂ）における処理をそれぞれ示し、図２は乱数の生成処理を示し、図３はメッセージ送受信手順を示している。
【００４５】
まず、通信端末Ａは２つの素数ｐ、ｑを選択するとともに、１０２４ビットの秘密情報Ｔをランダムに生成する（図６のＳ６０１）。そして、通信端末Ａは、ｎ ＝ ｐｑとなる１０２４ビットのｎを生成し、秘密情報Ｔから、Ｚ＝Ｔ^２ｍｏｄ ｎ なる１０２４ビットのＺを算出し、Ｚとｎを公開する（図６のＳ６０２）。なお、Ｓ６０１及びＳ６０２の処理の動作主体については通信端末Ａに限定されるものではなく、通信端末Ａ、Ｂ以外の管理センターがＳ６０１及びＳ６０２の処理を行い、素数ｐ、ｑ及び秘密情報Ｔを通信端末Ａへ安全な方法で通知してもよい。
【００４６】
一方の通信端末Ｂは、通信端末Ａが公開したＺとｎを取得する（図７のＳ７０１）。なお、Ｓ７０１〜Ｓ７１１の処理は対話証明手段５０２により実行される。
【００４７】
次に、通信端末Ａは、冗長情報生成手段４０２及び計算式連結手段４０３によって、以下のようにして、通信端末Ｂに送信したい８１９２ビットのメッセージＭから計算式連結済み冗長情報を生成する（図６のＳ６０３）。即ち、通信端末Ａは、図３に示すように、通信端末Ｂに送信したい８１９２ビットのメッセージＭを５１２ビットのデータ１６個に分割し（図３のＳ３０１）、分割された１６個のデータからＧＦ（２^１６）で計算するリードソロモン符号（前方誤り訂正符号）を用いて３２個の冗長データ（ｒ_１， ｒ_２，… ｒ_３２）を生成する（Ｓ３０２）。なお、３２個の冗長データ（ｒ_１， ｒ_２，… ｒ_３２）を計算するためのＧＦ（２^１６）の累乗数はそれぞれ、０〜２^１６−１の間でランダムに選択される。ここでは、ＧＦ（２^１６）で計算するリードソロモン符号は１６ビットごとに計算するため、５１２ビットのｒ_ｉを計算するために、３２のブロックに分けて計算する。それぞれのブロックを計算する累乗数は１６ビットで表現できるため、３２のブロックの累乗数の組は５１２ビットで表現でき、これをそれぞれの（ｒ_１， ｒ_２，… ｒ_３２）に対して（ｆ_１， ｆ_２，… ｆ_３２）とする。そして、通信端末Ａは、（ｒ_ｉ， ｆ_ｉ）のペアをそれぞれ（Ｒ_１， Ｒ_２，… Ｒ_３２）とする（Ｓ３０３）。このとき、Ｒ_ｉは５１２ビット のｒ_ｉ と５１２ビットのｆ_ｉ のペアなので１０２４ビットになる。このようにして計算式連結済み冗長情報が生成される。
【００４８】
なお、図２には、Ｎビットのメッセージを送信する場合の乱数（Ｒ_１， Ｒ_２，… Ｒ_ｋ）の生成処理を示す。ここで、図２の乱数生成処理を概説する。
【００４９】
Ｎビットの送信メッセージが入力されると（図２のＳ２０１）、メッセージが（５１２ビットの整数倍＋４４８ビット）になるように乱数ビットがパディングされる（Ｓ２０２）。そして、Ｎを表す６４ビットがパディングの後ろに付加される（Ｓ２０３）。これにより、メッセージは５１２ビットの整数倍になる（ここでは、５１２ビットのｍ倍とする）。
【００５０】
次に、メッセージは、ｍ個の５１２ビットデータに分割される（Ｓ２０４）。なお、分割された５１２ビットデータを、Ｄ（１），Ｄ（２），…Ｄ（ｍ）とする。そして、それぞれの５１２ビットデータは３２個の１６ビットブロックに分割される（Ｓ２０５）。なお、５１２ビットデータＤ（１）を分割して得られた１６ビットブロックをＢ（１，１），Ｂ（１，２），…Ｂ（１，３２）とし、５１２ビットデータＤ（ｍ）を分割して得られた１６ビットブロックをＢ（ｍ，１），Ｂ（ｍ，２），…Ｂ（ｍ，３２）とする。
【００５１】
次に、カウンタｉが０にリセットされ（Ｓ２０６）、以後、カウンタｉが２ｍに等しくなるまで、後述のＳ２０８〜Ｓ２１５の処理が繰り返される。
【００５２】
Ｓ２０８では、５１２ビットの空データが生成され（Ｓ２０８）、０〜６５５３５の中での乱数が３２個生成される（Ｓ２０９）。なお、生成された乱数をｆ（ｉ，１），ｆ（ｉ，２），… ｆ（ｉ，３２）とする。そして、カウンタｊが１にリセットされ（Ｓ２１０）、以後、カウンタｊが３２を超えるまで、Ｂ（１，ｊ），Ｂ（２，ｊ），…Ｂ（ｍ，ｊ）と累乗数ｆ（ｉ，ｊ）を用いてリードソロモン符号化を行い冗長データｒ（ｉ，ｊ）を生成する処理（Ｓ２１２）とカウンタｊを１つカウントアップする処理（Ｓ２１３）とが繰り返される。
【００５３】
カウンタｊが３２を超えると、Ｓ２１１〜Ｓ２１３のループを抜け、Ｓ２１４にて、冗長データｒ（ｉ，１），ｒ（ｉ，２），… ｒ（ｉ，３２）と乱数ｆ（ｉ，１），ｆ（ｉ，２），… ｆ（ｉ，３２）とが連結され、１０２４ビットのデータＲ_ｉとして出力される。その後、カウンタｉが１つカウントアップされてＳ２０７へ戻る。
【００５４】
その後、カウンタｉが２ｍに等しくなるまで、後述のＳ２０８〜Ｓ２１５の処理が繰り返される。その結果、冗長データｒ（ｉ，１），ｒ（ｉ，２），… ｒ（ｉ，３２）と乱数ｆ（ｉ，１），ｆ（ｉ，２），… ｆ（ｉ，３２）とが連結された１０２４ビットのデータＲ_ｉが（Ｒ_１，Ｒ_２，…Ｒ_３２）の３２個出力されることとなる。
【００５５】
以上のようにして乱数（Ｒ_１，Ｒ_２，…Ｒ_３２）が生成され、出力される。
【００５６】
図６、図７へ戻って、次に、通信端末Ａは、（Ｒ_１，Ｒ_２，…Ｒ_３２）から、Ｘ＝ Ｒ ｍｏｄ ｎで計算した結果（Ｘ_１，Ｘ_２，…Ｘ_３２）を第１のメッセージとして通信端末Ｂに送信する（Ｓ６０４）。なお、Ｓ６０４以降の処理は対話証明手段４０４により実行される。
【００５７】
通信端末Ｂは、上記第１のメッセージを受信し（Ｓ７０２）、確率的な質問として３２個の｛０，１｝のうち０が１６個以上になるようにランダムに選んだ３２個の｛０，１｝の列（ｂ_１，ｂ_２，…ｂ_３２）を通信端末Ａに送信する（Ｓ７０３）。通信端末Ａは、通信端末Ｂからの３２個の｛０，１｝の列（ｂ_１，ｂ_２，…ｂ_３２）を受信する（Ｓ６０５）。
【００５８】
次に、通信端末Ａは、通信端末Ｂからの｛０，１｝の列（ｂ_１，ｂ_２，…ｂ_３２）に従って、以下の回答（Ｙ_１，Ｙ_２，…Ｙ_３２）を通信端末Ｂに送る（図３のＳ３０４）。
【００５９】
ｂ_ｉ＝ ０ のとき Ｙ_ｉ ＝ Ｒ_ｉ
ｂ_ｉ ＝ １ のとき Ｙ_ｉ ＝ ＴＲ_ｉ ｍｏｄ ｎ
【００６０】
ここで、通信端末Ａが回答Ｙを送信する手順を、図６のＳ６０６〜Ｓ６１１に沿って説明する。Ｓ６０６ではカウンタｉが１にリセットされ、以後、カウンタｉが最大数ｋ（ここでは「３２」）に等しくなるまで、後述のＳ６０８〜Ｓ６１１の処理が繰り返される。Ｓ６０８では、ｂ_ｉが０であるか否かを判断し、ｂ_ｉが０であればＳ６０９にてＹ_ｉ＝ Ｒ_ｉとなるＹ_ｉを通信端末Ｂに送信する。
【００６１】
一方、ｂ_ｉが０でなければ（１であれば）、Ｓ６１０にてＹ_ｉ＝ ＴＲ_ｉ ｍｏｄ ｎとなるＹ_ｉを通信端末Ｂに送信する。その後、Ｓ６１１でカウンタｉが１つカウントアップされてＳ６０７へ戻る。
【００６２】
その後、カウンタｉが最大数ｋを超えるまで、Ｓ６０８〜Ｓ６１１の処理が繰り返される。その結果、通信端末Ａは、通信端末Ｂからの｛０，１｝の列（ｂ_１，ｂ_２，…ｂ_３２）に応じた回答（Ｙ_１，Ｙ_２，…Ｙ_３２）を通信端末Ｂに送信することとなる。
【００６３】
図７に戻り、通信端末Ｂは、通信端末Ａから送られてきた回答（Ｙ_１，Ｙ_２，…Ｙ_３２）を受信し、受信した回答が次式を満たすかどうかを、図７のＳ７０５〜Ｓ７１０に沿って検査する。
【００６４】
ｂ_ｉ＝ ０ のとき Ｘ_ｉ ＝ Ｙ_ｉ ^２ ｍｏｄ ｎ
ｂ_ｉ ＝ １ のとき ＺＸ_ｉ ＝ Ｙ_ｉ ^２ ｍｏｄ ｎ
【００６５】
ここで、通信端末Ｂが回答Ｙを検査する手順を説明する。図７のＳ７０５ではカウンタｉが１にリセットされ、以後、カウンタｉが最大数ｋ（ここでは「３２」）に等しくなるまで、後述のＳ７０７〜Ｓ７１０の処理が繰り返される。Ｓ７０７では、ｂ_ｉが０であるか否かを判断し、ｂ_ｉが０であればＳ７０８にてＸ_ｉ＝ Ｙ_ｉ ^２ ｍｏｄ ｎが成立するか否かを判断する。もし、不成立ならば、検証結果が異常であるとして処理を終了する。Ｘ_ｉ＝ Ｙ_ｉ ^２ ｍｏｄ ｎが成立するならば、Ｓ７１０へ進む。
【００６６】
一方、Ｓ７０７にてｂ_ｉが０でなければ（１であれば）、Ｓ７０９にてＺＸ_ｉ ＝ Ｙ_ｉ ^２ｍｏｄ ｎが成立するか否かを判断する。もし、不成立ならば、検証結果が異常であるとして処理を終了する。ＺＸ_ｉ ＝ Ｙ_ｉ ^２ｍｏｄ ｎが成立するならば、Ｓ７１０へ進む。
【００６７】
Ｓ７１０ではカウンタｉが１つカウントアップされてＳ７０６へ戻る。その後、カウンタｉが最大数ｋを超えるまで、Ｓ７０７〜Ｓ７１０の処理が繰り返される。その結果、通信端末Ｂは、通信端末Ａから送られてきた回答（Ｙ_１，Ｙ_２，…Ｙ_３２）が上記の式を満たすかどうかを１つずつ検査することとなる。但し、通信端末Ｂは、ｉ が１〜３２ において、すべて上式を満たしたときのみ、通信端末Ａとの通信を継続し、ひとつでも上式を満たさないと判断されたら、その時点で通信を中止する（予め通信を中止する正解率の閾値を定めておき、設定以上の正解率が得られる場合には通信を継続するようにしても良い）。
【００６８】
全ての検証結果が正常である場合、通信端末Ｂは、図７のＳ７１１にて、ｂ_ｉが０の場合の回答Ｙ_ｉを出力する。
【００６９】
そして、通信端末Ｂは、メッセージ生成手段５０３により、以下のようにして前方誤り訂正符号を用いてメッセージＭを生成（復元）する（Ｓ７１２、図３のＳ３０５）。即ち、通信端末Ｂは、ｂ_ｉ ＝ ０のときのＹ_ｉ（Ｒ_ｉ）の１６個をそれぞれｒ_ｉとｆ_ｉ とに分割し、リードソロモン符号でｒ_ｉ を ｆ_ｉ の累乗数で復号処理をして、８１９２ビットのメッセージを復元する。
【００７０】
リードソロモン符号は、３２個の冗長情報のうちどの１６個を利用しても元々のメッセージを復元できるが、累乗数をランダムに選んでいるため偶然他の冗長データと同じ累乗数を選んでしまった冗長データは復元処理には使えなくなる。この場合は、１７個目のｂ_ｉ＝ ０のＹ_ｉ（Ｒ_ｉ）が必要になる。
【００７１】
以上説明した一連の処理により、対話証明の検証に合格した際に復元された８１９２ビットのメッセージは、改竄されていないメッセージであり、平方剰余問題においても電子署名と同等のメッセージ送受信が実現したことになる。
【００７２】
【発明の効果】
以上説明したように、本発明によれば、一方向性関数を利用した対話証明方式を応用してメッセージを改竄されることなく通信相手に届けることができる。この方式は、一方向性関数が存在する全てのＰＳＰＡＣＥ問題及びＮＰ問題をベースにして実現でき、素因数分解問題や離散対数問題の高速な解法が発見されたとしても、他のＰＳＰＡＣＥ問題及びＮＰ問題で電子署名と同等のことができる。また、楕円曲線上の離散対数問題よりも短い鍵長で同等の難しさのＰＳＰＡＣＥ問題及びＮＰ問題があれば、公開鍵長の短い電子署名を実現できる。
【図面の簡単な説明】
【図１】一方向性関数を利用した対話証明方式のシーケンス図である。
【図２】乱数の生成処理を示す流れ図である。
【図３】メッセージ送受信手順を説明するための図である。
【図４】被検証装置の機能ブロック図である。
【図５】検証装置の機能ブロック図である。
【図６】被検証装置における処理を示す流れ図である。
【図７】検証装置における処理を示す流れ図である。
【符号の説明】
４０１…被検証装置、４０２…冗長情報生成手段、４０３…計算式連結手段、４０４…対話証明手段、５０１…検証装置、５０２…対話証明手段、５０３…メッセージ生成手段。

Claims (9)

1. 送信メッセージの入力を受け付け、前記送信メッセージから冗長情報を、当該冗長情報から前記送信メッセージを生成できるよう設計された計算式に基づいて生成し、生成された冗長情報及び生成に利用された計算式を出力する冗長情報生成手段と、
   前記冗長情報生成手段により出力された冗長情報と計算式とを連結させる計算式連結手段と、
   前記計算式連結手段による連結で得られた計算式連結済み冗長情報を乱数として用いて、検証装置との間で一方向性関数を用いた対話証明を行う対話証明手段と、を備え、前記対話証明手段は、対話証明において、
   乱数に対し一方向性関数の演算を行った演算結果を第１のメッセージとして送信し、
   検証装置から確率的な質問を受信し、受信された質問に応じて、乱数そのもの、又は、乱数と秘密情報から得られる値に対し一方向性関数の演算を行った演算結果を、第２のメッセージとして送信する、ことを特徴とする被検証装置。
2. 前記冗長情報生成手段は、前方誤り訂正符号を用いて前記冗長情報を生成することを特徴とする請求項１に記載の被検証装置。
3. 前記冗長情報生成手段は、前記送信メッセージに乱数ビットを付加し、付加後のメッセージから、前方誤り訂正符号を用いて前記冗長情報を生成することを特徴とする請求項１に記載の被検証装置。
4. 前方誤り訂正符号としてリードソロモン符号が用いられ、
   冗長データと当該冗長データの生成に利用された累乗数とを連結したものが乱数として対話証明に用いられることを特徴とする請求項２又は３に記載の被検証装置。
5. 冗長情報と当該冗長情報から送信メッセージを生成できるよう設計された計算式とが連結された計算式連結済み冗長情報を、乱数として用いる被検証装置、との間で一方向性関数を用いた対話証明を行う対話証明手段と、
   送信メッセージを生成するメッセージ生成手段と、を備え、
   前記対話証明手段は、対話証明において、
   乱数に対し一方向性関数の演算を行った演算結果を第１のメッセージとして受信し、
   被検証装置へ確率的な質問を送信して、当該質問に応じた回答として、乱数そのもの、又は、乱数と秘密情報から得られる値に対し一方向性関数の演算を行った演算結果を、第２のメッセージとして受信し、
   送信した質問、第１のメッセージ及び第２のメッセージに基づいて被検証装置の証明を行い、
   被検証装置の正当性が証明された場合、質問に応じた回答のうち乱数そのものを出力し、
   前記メッセージ生成手段は、
   出力された乱数に含まれている冗長情報及び計算式に基づいて送信メッセージを生成する、ことを特徴とする検証装置。
6. 前記メッセージ生成手段は、前方誤り訂正符号を用いて前記検証済みのメッセージから受信メッセージを生成することを特徴とする請求項５に記載の検証装置。
7. 前方誤り訂正符号としてリードソロモン符号が用いられることを特徴とする請求項６に記載の検証装置。
8. 検証装置との間で一方向性関数を用いた対話証明を行う被検証装置における被検証方法であって、
   送信メッセージの入力を受け付け、
   前記送信メッセージから冗長情報を、当該冗長情報から前記送信メッセージを生成できるよう設計された計算式に基づいて生成し、
   生成された冗長情報及び生成に利用された計算式とを連結させ、
   連結で得られた計算式連結済み冗長情報を乱数として用い、当該乱数に対し一方向性関数の演算を行った演算結果を第１のメッセージとして送信し、
   検証装置から確率的な質問を受信し、
   受信された質問に応じて、乱数そのもの、又は、乱数と秘密情報から得られる値に対し一方向性関数の演算を行った演算結果を、第２のメッセージとして送信する、ことを特徴とする被検証方法。
9. 冗長情報と当該冗長情報から送信メッセージを生成できるよう設計された計算式とが連結された計算式連結済み冗長情報を、乱数として用いる被検証装置、との間で一方向性関数を用いた対話証明を行う検証装置における検証方法であって、
   乱数に対し一方向性関数の演算を行った演算結果を第１のメッセージとして被検証装置から受信し、
   被検証装置へ確率的な質問を送信し、
   当該質問に応じた回答として、乱数そのもの、又は、乱数と秘密情報から得られる値に対し一方向性関数の演算を行った演算結果を、第２のメッセージとして受信し、
   送信した質問、第１のメッセージ及び第２のメッセージに基づいて被検証装置の証明を行い、
   被検証装置の正当性が証明された場合、質問に応じた回答のうち乱数そのものを出力し、
   出力された乱数に含まれている冗長情報及び計算式に基づいて送信メッセージを生成する、ことを特徴とする検証方法。

Images