(57)【要約】【課題】  ＮＴＲＵ署名の偽造を防止し、署名の信頼性を向上させる。【解決手段】  まず、Ｌ及びｒ（ｘ）を、デジタル署名生成装置１０とデジタル署名検証装置２０に格納しておく。そして、デジタル署名生成装置１０は、Ｌに基づきＮＴＲＵ署名を正規化した第１の正規多項式である候補多項式と、ｒ（ｘ）に基づき第１の正規多項式を順次変形した候補多項式とを、既定の順序でＮＴＲＵ署名検証し、最初に合格であると判断された候補多項式を署名として出力する。また、デジタル署名検証装置２０は、Ｌに基づき、署名である署名多項式を正規化した第２の正規多項式である検証多項式、或いは上述のｒ（ｘ）に基づき第２の正規多項式を順次変形した検証多項式を、デジタル署名生成装置での処理に対応する既定の順序でＮＴＲＵ署名検証する。そして、最初に合格であると判断された検証多項式が署名多項式と等しくない場合、署名が不合格である旨を出力する。【選択図】        図１
2005236904.tif 000002
【特許請求の範囲】
【請求項１】
多項式の正規化基準を示す正規化基準情報を格納した正規化基準情報格納手段と、
多項式の変形基準を示す変形基準情報を格納した変形基準情報格納手段と、
ＮＴＲＵ（登録商標）署名であるＮＴＲＵ多項式を生成するＮＴＲＵ署名生成手段と、
前記正規化基準情報に示された正規化基準に基づき、前記ＮＴＲＵ多項式を正規化した正規多項式を生成する正規化手段と、
前記正規多項式を署名候補である候補多項式とする初期候補設定手段と、
前記変形基準情報に示された変形基準に基づいて当該正規多項式を変形し、新たな候補多項式を順次生成する変形手段と、
デジタル署名検証装置での処理に対応する既定の順序で、前記候補多項式のＮＴＲＵ署名検証を行うＮＴＲＵ署名検証手段と、
前記ＮＴＲＵ署名検証手段において最初に合格であると判断された前記候補多項式を署名として出力する署名出力手段と、
を特徴とするデジタル署名生成装置。
【請求項２】
請求項１記載のデジタル署名生成装置であって、
前記正規化基準情報及び前記変形基準情報は、
デジタル署名検証装置と共有の秘密情報である、
ことを特徴とするデジタル署名生成装置。
【請求項３】
請求項１或いは２に記載のデジタル署名生成装置において、
前記ＮＴＲＵ署名検証手段は、
前記候補多項式が１つ設定されるたびに、当該候補多項式の検証を行う手段であり、
前記変形手段は、
前記候補多項式のＮＴＲＵ署名検証が不合格であった場合に、新たな前記候補多項式を生成する手段である、
ことを特徴とするデジタル署名生成装置。
【請求項４】
請求項１から３の何れかに記載のデジタル署名生成装置であって、
前記ＮＴＲＵ多項式は、
Ｎを自然数とした場合における、Ｎ−１次の多項式ｓ（ｘ）であり、
前記正規化基準情報は、
０以上Ｎ未満の整数Ｌであり、
前記変形基準情報は、
関数ｒ（ｘ）であり、
前記正規化手段は、
ｑを自然数とし、前記ＮＴＲＵ多項式ｓ（ｘ）のＬ次の係数をｓＬとした場合における、
【数１】
2005236904.tif 000014
の演算結果を前記正規多項式ｓ’（ｘ）とする手段であり、
前記初期候補設定手段は、
前記正規多項式ｓ’（ｘ）を前記候補多項式ｓ’’（ｘ）とし、
前記変形手段は、
前記候補多項式ｓ’’（ｘ）のＬ次の係数をｓ’’Ｌとした場合における、
【数２】
2005236904.tif 000015
の演算結果を新たな前記候補多項式ｓ’’（ｘ）とする手段である、
ことを特徴とするデジタル署名生成装置。
【請求項５】
請求項１から３の何れかに記載のデジタル署名生成装置であって、
前記ＮＴＲＵ多項式は、
Ｎを自然数とした場合における、Ｎ−１次の多項式ｓ（ｘ）であり、
前記正規化基準情報は、
基準値Ｅと、０以上Ｎ未満の整数Ｌであり、
前記変形基準情報は、
関数ｒ（ｘ）であり、
前記正規化手段は、
ｑを自然数とし、前記ＮＴＲＵ多項式ｓ（ｘ）のＬ次の係数をｓＬとした場合における、
【数３】
2005236904.tif 000016
の演算結果を前記正規多項式ｓ’（ｘ）とする手段であり、
前記初期候補設定手段は、
前記正規多項式ｓ’（ｘ）を前記候補多項式ｓ’’（ｘ）とし、
前記変形手段は、
前記候補多項式ｓ’’（ｘ）のＬ次の係数をｓ’’Ｌとした場合における、
【数４】
2005236904.tif 000017
の演算結果を新たな前記候補多項式ｓ’’（ｘ）とする手段である、
ことを特徴とするデジタル署名生成装置。
【請求項６】
多項式の正規化基準を示す正規化基準情報を格納した正規化基準情報格納手段と、
多項式の変形基準を示す変形基準情報を格納した変形基準情報格納手段と、
署名である署名多項式の入力を受け付ける署名入力手段と、
前記正規化基準情報に示された正規化基準に基づき、前記署名多項式を正規化した正規多項式を生成する正規化手段と、
前記正規多項式を検証対象である検証多項式とする初期対象設定手段と、
前記変形基準情報に示された変形基準に基づいて前記正規多項式を変形し、新たな検証多項式を順次生成する変形手段と、
デジタル署名生成装置での処理に対応する既定の順序で、前記検証多項式のＮＴＲＵ署名検証を行うＮＴＲＵ署名検証手段と、
前記ＮＴＲＵ署名検証手段において最初に合格であると判断された前記検証多項式が前記署名多項式と等しくない場合に、前記署名が不合格である旨を出力する署名判定手段と、
を有することを特徴とするデジタル署名検証装置。
【請求項７】
請求項６記載のデジタル署名検証装置であって、
前記正規化基準情報及び前記変形基準情報は、
デジタル署名生成装置と共有の秘密情報である、
ことを特徴とするデジタル署名検証装置。
【請求項８】
請求項６或いは７に記載のデジタル署名検証装置であって、
前記ＮＴＲＵ署名検証手段は、
前記署名多項式の入力後、前記正規多項式の生成前に、前記署名多項式の検証を行い、前記検証多項式が１つ設定されるたびに、当該検証多項式の検証を行う手段であり、
前記正規化手段は、
前記ＮＴＲＵ署名検証手段において前記署名多項式が合格であると判断され、なおかつ、当該署名多項式が正規化された多項式でなかった場合に、前記正規多項式を生成する手段であり、
前記変形手段は、
前記検証多項式のＮＴＲＵ署名検証が不合格であった場合に、新たな前記検証多項式を生成する手段である、
ことを特徴とするデジタル署名検証装置。
【請求項９】
請求項６から８の何れかに記載のデジタル署名検証装置であって、
前記署名多項式は、
Ｎを自然数とした場合における、Ｎ−１次の多項式ｕ（ｘ）であり、
前記正規化基準情報は、
０以上Ｎ未満の整数Ｌであり、
前記変形基準情報は、
関数ｒ（ｘ）であり、
前記正規化手段は、
ｑを自然数とし、前記署名多項式ｕ（ｘ）のＬ次の係数をｕＬとした場合における、
【数５】
2005236904.tif 000018
の演算結果を前記正規多項式ｕ’（ｘ）とする手段であり、
前記初期対象設定手段は、
前記正規多項式ｕ’（ｘ）を前記検証多項式ｕ’’（ｘ）とし、
前記変形手段は、
前記検証多項式ｕ’’（ｘ）のＬ次の係数をｕ’’Ｌとした場合における、
【数６】
2005236904.tif 000019
の演算結果を新たな前記検証多項式ｕ’’（ｘ）とする手段である、
ことを特徴とするデジタル署名検証装置。
【請求項１０】
請求項６から８の何れかに記載のデジタル署名検証装置であって、
前記署名多項式は、
Ｎを自然数とした場合における、Ｎ−１次の多項式ｕ（ｘ）であり、
前記正規化基準情報は、
基準値Ｅと、０以上Ｎ未満の整数Ｌであり、
前記変形基準情報は、
関数ｒ（ｘ）であり、
前記正規化手段は、
ｑを自然数とし、前記署名多項式ｕ（ｘ）のＬ次の係数をｕＬとした場合における、
【数７】
2005236904.tif 000020
の演算結果を前記正規多項式ｕ’（ｘ）とする手段であり、
前記初期対象設定手段は、
前記正規多項式ｕ’（ｘ）を前記検証多項式ｕ’’（ｘ）とし、
前記変形手段は、
前記検証多項式ｕ’’（ｘ）のＬ次の係数をｕ’’Ｌとした場合における、
【数８】
2005236904.tif 000021
の演算結果を新たな前記検証多項式ｕ’’（ｘ）とする手段である、
ことを特徴とするデジタル署名検証装置。
【請求項１１】
多項式の正規化基準を示す正規化基準情報、及び多項式の変形基準を示す変形基準情報を、デジタル署名生成装置のメモリとデジタル署名検証装置のメモリに格納しておき、
前記デジタル署名生成装置が有する、
ＮＴＲＵ署名生成手段において、ＮＴＲＵ署名であるＮＴＲＵ多項式を生成し、
第１の正規化手段において、前記正規化基準情報に示された正規化基準に基づき、前記ＮＴＲＵ多項式を正規化した第１の正規多項式を生成し、
初期候補設定手段において、前記第１の正規多項式を署名候補である候補多項式とし、
第１のＮＴＲＵ署名検証手段において、前記候補多項式のＮＴＲＵ署名検証を行い、
前記候補多項式が合格であった場合、署名出力手段において、当該候補多項式を署名として出力し、
前記候補多項式が不合格であった場合、第１の変形手段において、前記変形基準情報に示された変形基準に基づいて前記第１の正規多項式を変形することにより新たな候補多項式を生成する処理と、前記第１のＮＴＲＵ署名検証手段において当該候補多項式のＮＴＲＵ署名検証を行う処理とを、当該候補多項式が合格となるまで繰り返し、合格となった当該候補多項式を、署名出力手段において署名として出力し、
前記デジタル署名検証装置が有する、
署名入力手段において、前記署名である署名多項式の入力を受け付け、
第２のＮＴＲＵ署名検証手段において、前記署名多項式のＮＴＲＵ署名検証を行い、
前記署名多項式が不合格であれば、署名判定手段において、当該署名が不合格である旨を出力し、
前記署名多項式が合格であり、なおかつ、当該署名多項式が正規化された多項式であった場合、前記署名判定手段において、当該署名が合格である旨を出力し、
前記署名多項式が合格であり、なおかつ、当該署名多項式が正規化された多項式でなかった場合、第２の正規化手段において、前記正規化基準情報に示された正規化基準に基づき、前記署名多項式を正規化した第２の正規多項式を生成し、
初期対象設定手段において、前記第２の正規多項式を検証対象である検証多項式とし、
前記第２のＮＴＲＵ署名検証手段において、前記検証多項式のＮＴＲＵ署名検証を行い、
前記第２の正規多項式である前記検証多項式が合格であれば、前記署名判定手段において、前記署名が不合格である旨を出力し、
前記第２の正規多項式である前記検証多項式が不合格であれば、第２の変形手段において、前記変形基準情報に示された変形基準に基づいて前記第２の正規多項式を変形した新たな検証多項式を生成し、
前記検証多項式と前記署名とが等しくなるか、或いは、前記署名多項式と等しく無い前記検証多項式が合格となるまで、第２の変形手段において、前記検証多項式の生成を繰り返し、
前記検証多項式と前記署名多項式とが等しくなった場合、前記署名判定手段において、前記署名が合格である旨を出力し、前記署名多項式と等しく無い前記検証多項式が合格となった場合、前記署名判定手段において、前記署名が不合格である旨を出力する、
ことを特徴とするデジタル署名方法。
【請求項１２】
請求項１から５の何れかに記載の署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項１３】
請求項６から１０の何れかに記載の署名検証装置としてコンピュータを機能させるためのプログラム。
【請求項１４】
請求項１２記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【請求項１５】
請求項１３記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に、デジタル署名の安全性を向上させるデジタル署名生成装置、デジタル署名検証装置、デジタル署名方法、それらをコンピュータ上で実現するためのプログラム、及びそのプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
従来より、多項式環の性質を利用した署名技術が知られている。ＮＴＲＵＳｉｇｎ（署名）と呼ばれる署名アルゴリズムもその一つである（例えば、非特許文献１、非特許文献２参照。）。以下にこのＮＴＲＵ署名の概要について説明する。
＜前処理＞
まず、デジタル署名生成装置及びデジタル署名検証装置に対する共通パラメータｑ，Ｎを設定する。なお、実際の状況では、例えば非特許文献１及び非特許文献２にあるように、ｑ＝１２８、Ｎ＝２５１等の値が適切であると考えられている。
また、デジタル署名生成装置が安全に保持する秘密情報として、秘密鍵ｆ（ｘ）,ｇ（ｘ）,Ｆ（ｘ）,Ｇ（ｘ）∈Ｚｑ［ｘ］／（ｘＮ−１）を設定する。なお、鍵ｆ（ｘ）,ｇ（ｘ）,Ｆ（ｘ）,Ｇ（ｘ）は、
ｆ（ｘ）Ｇ（ｘ）−ｇ（ｘ）Ｆ（ｘ）＝ｑｍｏｄ Φ（ｘ）
Φ（ｘ）＝１＋ｘ＋ｘ２＋…＋ｘＮ−１  …(1)
を満たすものとする。また、Ｚｑ［ｘ］／（ｘＮ−１）は、ｑを法とした剰余類を係数とする変数ｘの多項式であって、変数ｘの指数がＮを法とした剰余類となっているものを意味する。
さらに、公開鍵としてｈ（ｘ）＝ｆ（ｘ）−１＊ｇ（ｘ） ｍｏｄ ｑを設定する。ここで、ｆ（ｘ）−１は、ｆ（ｘ）−１・ｆ（ｘ）＝１ ｍｏｄ ｘＮ−１を満たすものを意味する。
【０００３】
＜ＮＴＲＵ署名生成アルゴリズムの概要＞
署名したいメッセージをＭとする。これに予め定められたハッシュ関数を適用し、予め定められた方法によって適当に、多項式の組（ｍ１（ｘ）,ｍ２（ｘ））を計算する。ただし、ｍ１（ｘ）,ｍ２（ｘ）∈Ｚｑ［ｘ］／（ｘＮ−１）である。
次に、以下を満たすＡ（ｘ）,Ｂ（ｘ）,ａ（ｘ）,ｂ（ｘ）∈Ｚｑ［ｘ］／（ｘＮ−１）を計算する。
Ｇ（ｘ）＊ｍ１（ｘ）‐Ｆ（ｘ）＊ｍ２（ｘ）＝Ａ（ｘ）＋ｑＢ（ｘ）
−ｇ（ｘ）＊ｍ１（ｘ）＋ｆ（ｘ）＊ｍ２（ｘ）＝ａ（ｘ）＋ｑｂ（ｘ）
そして、ｓ（ｘ）＝ｆ（ｘ）＊Ｂ（ｘ）＋Ｆ（ｘ）＊ｂ（ｘ） ｍｏｄ ｑを署名として出力する（ｓ（ｘ）∈Ｚｑ［ｘ］／（ｘＮ−１））。
＜ＮＴＲＵ署名検証アルゴリズムの概要＞
まず、上述の署名生成アルゴリズムと同一の方法によって、メッセージＭから多項式の組（ｍ１（ｘ）,ｍ２（ｘ））を計算する。また、署名ｓ（ｘ）、公開鍵ｈ（ｘ）、共通パラメータｑからｔ（ｘ）＝ｓ（ｘ）＊ｈ（ｘ） ｍｏｄ ｑを計算し、
‖ｓ（ｘ）−ｍ１（ｘ）‖２＋‖ｔ（ｘ）−ｍ２（ｘ）‖２  …(2)
を計算する。
【０００４】
ここで、‖α（ｘ）‖は、多項式
【数９】
2005236904.tif 000003
に対するcentered normを示し、次の式の右辺で定義される。
【数１０】
2005236904.tif 000004
この式（４）に示すように、centered norm‖α（ｘ）‖は、上述の式（３）に示した多項式α（ｘ）の係数αｉ（ｉ＝０,１,…,Ｎ−１）の分散を示しており、その値が小さいほど係数αｉのばらつきも小さいことを意味している。
【０００５】
ここで、署名ｓ（ｘ）が前述のＮＴＲＵ署名生成アルゴリズムによって正しく生成されていた場合、式（２）が有する多項式ｓ（ｘ）−ｍ１（ｘ）及びｔ（ｘ）−ｍ２（ｘ）の係数のばらつきは共に小さくなる。この場合、これらのcentered norm‖ｓ（ｘ）−ｍ１（ｘ）‖及び‖ｔ（ｘ）−ｍ２（ｘ）‖の値も小さくなり、それを合計した上述の式（２）の値も小さくなる。
ここではこの性質を利用し、この式（２）で示される合計値‖ｓ（ｘ）−ｍ１（ｘ）‖２＋‖ｔ（ｘ）−ｍ２（ｘ）‖２と、予め与えられた定数Ｎｂ（「NormBound」という。）の２乗（Ｎｂ２）との大小を比較することにより、署名ｓ（ｘ）の正当性を検証する。具体的には、‖ｓ（ｘ）−ｍ１（ｘ）‖２＋‖ｔ（ｘ）−ｍ２（ｘ）‖２≦Ｎｂ２であれば、署名の検証結果として「合格」を出力し、‖ｓ（ｘ）−ｍ１（ｘ）‖２＋‖ｔ（ｘ）−ｍ２（ｘ）‖２＞Ｎｂ２であれば「不合格」を出力する。
【非特許文献１】J. Hoffstein, N. Graham, J. Pipher, J. Silverman, and W. Whyte, “NTRUSign: Digital Signatures Using the NTRU Lattice,” CT-RSA’03, Lecture Notes in Computer Science 2612, Springer-Verlag, 122-140, 2003.
【非特許文献２】Consortium for Efficient Embedded Security. Efficient Embedded Security Standard (EESS)#1: Implementation Aspects of NTRUEncrypt and NTRUSign. Available from http://www.ceesstandards.org.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、従来のＮＴＲＵ署名生成アルゴリズムは、高い確率で署名の偽造を行うことができるという問題点がある。以下にその理由を説明する。
まず、α（ｘ）が係数の値が小さいＮ−１次多項式である場合、centered norm‖α（ｘ）‖は、定数ｋに対して‖α（ｘ）‖≒‖α（ｘ）＋ｋΦ（ｘ）‖となる性質がある（性質１）。
つまり、前述のようにcentered norm‖α（ｘ）‖は、多項式α（ｘ）の係数のばらつきの大きさを示している。ここで、前述の式（１）のようにΦ（ｘ）＝１＋ｘ＋ｘ２＋…＋ｘＮ−１であるため、α（ｘ）＋ｋΦ（ｘ）は、通常、多項式α全体をシフトしたものすぎない。よって、通常、‖α（ｘ）‖＝‖α（ｘ）＋ｋΦ（ｘ）‖となる。しかし、ＮＴＲＵ署名に用いる多項式の係数はＺｑ［ｘ］の集合に属するため、Ｚｑの代表元として{‐ｑ／２+１,‐ｑ／２+２,…,ｑ／２}をとった場合、この係数がｑ／２＋１となると、その値は再び‐ｑ／２＋１に戻る。すなわちこの係数ｑ／２に１を加算するとその係数は‐ｑ／２＋１となる。よって定数ｋの取り方によっては多項式α（ｘ）の係数のばらつきが変動することもあり、この場合には‖α（ｘ）‖≒‖α（ｘ）＋ｋΦ（ｘ）‖となる。
【０００７】
次に、多項式α（ｘ）に対し、α（ｘ）Φ（ｘ）＝α（１）Φ（ｘ）という関係が成立するという性質がある（性質２）。
つまり、ＮＴＲＵ署名では多項式α（ｘ）はＺｑ［ｘ］／（ｘＮ−１）の集合に属しｘＮ−１＊ｘ＝ｘ０＝１となる。そのため、上述の式（１）（３）よりα（ｘ）Φ（ｘ）を計算すると、
α（ｘ）Φ（ｘ）
＝（α０＋α１ｘ＋α２ｘ２＋・・・＋αＮ−１ｘＮ−１）＊（１＋ｘ＋ｘ２＋…＋ｘＮ−１）
＝（α０＋α１＋α２＋・・・＋αＮ−１）＋（α０＋α１＋α２＋・・・＋αＮ−１）ｘ＋・・・＋（α０＋α１＋α２＋・・・＋αＮ−１）ｘＮ−１
＝（α０＋α１＋α２＋・・・＋αＮ−１）＊（１＋ｘ＋ｘ２＋…＋ｘＮ−１）
＝α（１）Φ（ｘ）
となる。
【０００８】
ここで、攻撃者が１つの署名ｓ（ｘ）を入手できたとする。この場合、この攻撃者は任意の定数ｋを選択し、偽造署名
ｓ’（ｘ）＝ｓ（ｘ）＋ｋΦ（ｘ）…(5)
を計算することができる。
ここで、この偽造署名ｓ’（ｘ）と公開鍵ｈ（ｘ）、共通パラメータｑを用いると、
ｔ’（ｘ）＝ｓ’（ｘ）＊ｈ（ｘ） ｍｏｄ ｑ
＝ｈ（ｘ）ｓ（ｘ）＋ｈ（ｘ）ｋΦ（ｘ）ｍｏｄ ｑ  …(6)
となる。また、前述のようにｔ（ｘ）＝ｓ（ｘ）＊ｈ（ｘ） ｍｏｄ ｑであり、上述の（性質２）が成り立つため、式（６）は、
ｔ’（ｘ）＝ｈ（ｘ）ｓ（ｘ）＋ｈ（１）ｋΦ（ｘ）ｍｏｄ ｑ
＝ｔ（ｘ）＋ｈ（１）ｋΦ（ｘ）ｍｏｄ ｑ  …(7)
と変形できる。
【０００９】
また、上述の偽造署名Ｓ’に対し、前述のＮＴＲＵ署名検証アルゴリズムにおける式（２）を適用すると、
‖ｓ’（ｘ）−ｍ１（ｘ）‖２＋‖ｔ’（ｘ）−ｍ２（ｘ）‖２  …(8)
となる。
また、上述の式（５）及び前述の（性質１）より、
‖ｓ’（ｘ）−ｍ１（ｘ）‖
＝‖ｓ（ｘ）＋ｋΦ（ｘ）−ｍ１（ｘ）‖
≒‖ｓ（ｘ）−ｍ１（ｘ）‖  …(10)
となり、さらに上述の式（７）及び前述の（性質１）より、
‖ｔ’（ｘ）−ｍ２（ｘ）‖
＝‖ｔ（ｘ）＋ｈ（１）ｋΦ（ｘ）−ｍ２（ｘ）‖
≒‖ｔ（ｘ）−ｍ２（ｘ）‖  …(11)
となる。
【００１０】
この式（１０）（１１）より、式（８）は、
‖ｓ’（ｘ）−ｍ１（ｘ）‖２＋‖ｔ’（ｘ）−ｍ２（ｘ）‖２
≒‖ｓ（ｘ）−ｍ１（ｘ）‖２＋‖ｔ（ｘ）−ｍ２（ｘ）‖２
と変形できる。そして、正当な署名ｓ（ｘ）は、
‖ｓ（ｘ）−ｍ１（ｘ）‖２＋‖ｔ（ｘ）−ｍ２（ｘ）‖２≦Ｎｂ２
を満たすことから、高い確率で
‖ｓ’（ｘ）−ｍ１（ｘ）‖２＋‖ｔ’（ｘ）−ｍ２（ｘ）‖２≦Ｎｂ２
となり、この偽造署名ｓ’（ｘ）も正当であると判断されることになる。これは、正当な署名ｓ（ｘ）を１つ知っていれば、ＮＴＲＵ署名検証アルゴリズムにおいて高い確率で正当であると判断される偽造署名Ｓ’（ｘ）を生成できることを意味する。
【００１１】
この発明はこのような点に鑑みてなされたものであり、ＮＴＲＵ署名の偽造を防止し、署名の信頼性を向上させることが可能なデジタル署名生成装置を提供することを目的とする。
また、この発明の他の目的は、ＮＴＲＵ署名の偽造を防止し、署名の信頼性を向上させることが可能なデジタル署名検証装置を提供することである。
さらに、この発明の他の目的は、ＮＴＲＵ署名の偽造を防止し、署名の信頼性を向上させることが可能なデジタル署名方法を提供することである。
【課題を解決するための手段】
【００１２】
本発明では上記課題を解決するために、まず、多項式の正規化基準を示す正規化基準情報、及び多項式の変形基準を示す変形基準情報を、デジタル署名生成装置のメモリとデジタル署名検証装置のメモリに格納しておく。
そして、署名生成時、デジタル署名生成装置は、この正規化基準に基づきＮＴＲＵ署名を正規化した第１の正規多項式である候補多項式と、この変形基準に基づき第１の正規多項式を変形して順次生成される新たな候補多項式とを、デジタル署名検証装置での処理に対応する既定の順序でＮＴＲＵ署名検証し、最初に合格であると判断された候補多項式を署名として出力する。
また、署名検証時、デジタル署名検証装置は、上述の正規化基準に基づき、署名である署名多項式を正規化した第２の正規多項式である検証多項式、或いは上述の変形基準に基づき第２の正規多項式を変形して順次生成される新たな検証多項式を、デジタル署名生成装置での処理に対応する既定の順序でＮＴＲＵ署名検証する。そして、最初に合格であると判断された検証多項式が署名多項式と等しくない場合、署名が不合格である旨を出力する。
【００１３】
ここで、デジタル署名生成装置における多項式の正規化処理の基準となる正規化基準情報と、多項式の変形処理の基準となる変形基準情報は、デジタル署名検証装置における同処理のものと同じである。従って、デジタル署名生成装置において、この正規化基準に基づきＮＴＲＵ署名を正規化した第１の正規多項式である候補多項式と、この変形基準に基づき第１の正規多項式を変形して順次生成される新たな候補多項式とを、デジタル署名検証装置での処理に対応する既定の順序でＮＴＲＵ署名検証し、最初に合格であると判断された候補多項式（署名多項式）は、デジタル署名検証装置において、この正規化基準に基づき、この署名多項式を正規化した第２の正規多項式である検証多項式、或いは上述の変形基準に基づき第２の正規多項式を変形して順次生成される新たな検証多項式を、デジタル署名生成装置での処理に対応する既定の順序でＮＴＲＵ署名検証し、最初に合格であると判断された検証多項式と等しいはずである。
【００１４】
しかし、前述のように、攻撃者が署名多項式を任意にシフトし、他の署名多項式を偽造した場合、この偽造された署名多項式は、上述の正規化基準に基づき正規化し、或いはさらに変形基準に基づき変形して生成された候補多項式を、既定の順序でＮＴＲＵ署名検証し、最初に合格となった多項式と異なることになる。本発明のデジタル署名検証装置は、この違いを検出することにより、ＮＴＲＵ署名の偽造を発見する。
【発明の効果】
【００１５】
以上のように、本発明では、正当なデジタル署名生成装置とデジタル署名検証装置で共有される正規化基準情報及び変形基準情報に基づき、デジタル署名生成装置において、多項式を変形し、既定の順序でＮＴＲＵ署名検証し、最初に合格となった多項式を署名して出力する。そして、デジタル署名検証装置において、これらの正規化基準情報及び変形基準情報に基づき署名多項式を変形し、既定の順序でＮＴＲＵ署名検証し、最初に合格となった多項式が最初の署名多項式と等しくない場合、当該署名が不合格であると判断する。これにより、ＮＴＲＵ署名の偽造を防止し、署名の信頼性を向上させることが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態を図面を参照して説明する。
〔第１の実施の形態〕
まず、本発明における第１の実施の形態について説明する。
＜構成＞
図１は、本形態におけるデジタル署名システム１の構成を例示した図である。
図１に例示するように、デジタル署名システム１は、デジタル署名を生成するデジタル署名生成装置１０、及びデジタル署名を検証するデジタル署名検証装置２０を有している。
【００１７】
＜デジタル署名生成装置＞
この例のデジタル署名生成装置１０は、公知のコンピュータに所定のプログラムを実行させることにより構成され、正規化基準情報格納部１１、変形基準情報格納部１２、メッセージ入力部１３、ＮＴＲＵ署名生成部１４、正規化部１５、初期候補設定部１６、変形部１７、ＮＴＲＵ署名検証部１８及び署名出力部１９を有している。
図２の（ａ）は、正規化部１５の詳細構成を例示した図であり、（ｂ）は、変形部１７の詳細構成を例示した図である。
図２の（ａ）に例示するように、この例の正規化部１５は、共通パラメータ格納部１５ａ、多項式生成部１５ｂ、多項式スカラー倍部１５ｃ、多項式加算部１５ｄ、及び剰余計算部１５ｅを有している。また、図２の（ｂ）に例示するように、この例の変形部１７は、共通パラメータ格納部１７ａ、多項式生成部１７ｂ、多項式スカラー倍部１７ｃ、多項式加算部１７ｄ、及び剰余計算部１７ｅを有している。
【００１８】
ここで、剰余計算部１５ｅ,１７ｅは、整数ｍを入力とし、整数ｓに対してｍ＝ｑｓ＋ｒとなる０以上ｑ未満の自然数ｒを計算し、ｒがｔｍａｘ以下であればそのまま出力し、ｔｍａｘよりも大きければｒ−ｑを出力する。なお、パラメータｑ, ｔｍａｘの内容については後述する。
また、多項式スカラー倍部１５ｃ,１７ｃは、多項式ａ（ｘ）と整数ｖが与えられたとき、ａ（ｘ）の係数をそれぞれｖ倍した値を剰余計算部１５ｅ,１７ｅに入力し、その出力をそれぞれ係数とする多項式を出力する（多項式ａ（ｘ）＊ｖを計算し、その係数をｍｏｄｑしたものを出力する。）。
さらに、多項式加算部１５ｄ,１７ｄは、多項式ａ（ｘ）と多項式ｂ（ｘ）が与えられたとき、おのおのの係数を加算して剰余計算部１５ｅ,１７ｅに入力し、その出力をそれぞれ係数とする多項式を出力する（多項式ａ（ｘ）＋ｂ（ｘ）を計算し、その係数をｍｏｄｑしたものを出力する。）。
【００１９】
図３の（ａ）は、ＮＴＲＵ署名生成部１４の詳細構成を例示した図であり、（ｂ）は、ＮＴＲＵ署名検証部１８の詳細構成を例示した図である。
図３の（ａ）に例示するように、この例のＮＴＲＵ署名生成部１４は、共通パラメータ格納部１４ａ、秘密鍵格納部１４ｂ、ハッシュ演算部１４ｃ及び署名演算部１４ｄを有している。また、図３の（ｂ）に例示するように、この例のＮＴＲＵ署名検証部１８は、共通パラメータ格納部１８ａ、公開鍵格納部１８ｂ、ハッシュ演算部１８ｃ、乗算部１８ｄ及び比較部１８ｅを有している。なお、署名演算部１４ｄは、前述した剰余計算部、多項式加算部、多項式スカラー倍部等によって構成され、乗算部１８ｄは、乗算装置、剰余計算部等によって構成される。
【００２０】
＜デジタル署名検証装置＞
この例のデジタル署名検証装置２０は、公知のコンピュータに所定のプログラムを実行させることにより構成され、正規化基準情報格納部２１、変形基準情報格納部２２、署名入力部２３、正規化部２４、初期対象設定部２５、変形部２６、ＮＴＲＵ署名検証部２７及び署名判定部２８を有している。
なお、正規化部２４は正規化部１５と同様な構成であり、変形部２６は変形部１７と同様な構成であり、ＮＴＲＵ署名検証部２７はＮＴＲＵ署名検証部１８と同様な構成であるため、それらの詳細は省略する。
【００２１】
＜前処理＞
まず、デジタル署名生成装置１０及びデジタル署名検証装置２０に対する共通パラメータとして自然数ｑ,Ｎを設定する。また、デジタル署名生成装置１０が安全に保持する秘密情報として、ＮＴＲＵ署名の秘密鍵ｆ（ｘ）,ｇ（ｘ）,Ｆ（ｘ）,Ｇ（ｘ）∈Ｚｑ［ｘ］／（ｘＮ−１）を設定する。さらに、その公開鍵としてｈ（ｘ）＝ｆ（ｘ）−１＊ｇ（ｘ） ｍｏｄ ｑを設定する。なお、これらの詳細については前述の通りである。
また、０以上Ｎ未満の整数の定数Ｌを定める。さらに、適当なｑ個の元からなる０を含む整数の連続した区間Ｔ（例えば、Ｔ＝{‐ｑ／２+１,‐ｑ／２+２,…,ｑ／２}等）を定める。また、Ｔの元のうち最大のものをｔｍａｘとおく。
また、{ｒｎ（０）｜ｎ∈Ｎ}＝Ｔとなる関数ｒ（ｘ）を設定する。ただし、ｒｎ（ｘ）は、関数ｒ（ｘ）をｎ回繰り返し施すことを意味する。つまり、０に対して関数ｒ（ｘ）をＮ回以下作用させることにより、Ｔの全ての元をとることができる。なお、このような関数ｒ（ｘ）としては、例えば、ｒ（ｘ）＝ｘ＋１ ｍｏｄ ｑ等を例示できる。
【００２２】
この例の場合、以上のように設定されたｑ,Ｎ,ｔｍａｘは、デジタル署名生成装置１０のＮＴＲＵ署名生成部１４、正規化部１５、変形部１７及びＮＴＲＵ署名生成部１４の共通パラメータ格納部１４ａ,１５ａ,１７ａ,１８ａに格納され、同様に、デジタル署名検証装置２０の正規化部２４、変形部２６及びＮＴＲＵ署名検証部２７にも格納される。また、ｑ,ｔｍａｘは、署名判定部２８にも格納される。
また、秘密鍵ｆ（ｘ）,ｇ（ｘ）,Ｆ（ｘ）,Ｇ（ｘ）は、デジタル署名生成装置１０のＮＴＲＵ署名生成部１４が有する秘密鍵格納部１４ｂに、公開鍵ｈ（ｘ）は、ＮＴＲＵ署名検証部１８の公開鍵格納部１８ｂに格納され、公開鍵ｈ（ｘ）は、同様に、デジタル署名検証装置２０のＮＴＲＵ署名検証部２７にも格納される。
また、定数Ｌは、多項式の正規化条件を示す正規化基準情報として、メモリである正規化基準情報格納部１１,２１に格納される。さらに、関数ｒ（ｘ）は、多項式の変形基準を示す変形基準情報として、メモリである変形基準情報格納部１２,２２に格納される。なお、定数Ｌ及び関数ｒ（ｘ）は、デジタル署名生成装置１０とデジタル署名検証装置２０とで共有される秘密情報である。
【００２３】
＜署名生成処理＞
次に、デジタル署名生成装置１０において行われる署名生成処理について説明する。
図４は、本形態における署名生成処理を説明するためのフローチャートである。以下、このフローチャートに沿って、この署名生成処理を説明していく。
［ステップＳ１］
まず、メッセージ入力部１３においてメッセージＭの入力を受け付け、入力されたメッセージＭをＮＴＲＵ署名生成部１４、ＮＴＲＵ署名検証部１８及び署名出力部１９に送る。
［ステップＳ２］
メッセージＭを受け取ったＮＴＲＵ署名生成部１４は、このメッセージＭのＮＴＲＵ署名であるＮＴＲＵ多項式ｓ（ｘ）を生成する（ステップＳ２）。
【００２４】
すなわち、ハッシュ演算部１４ｃにおいて（図３の（ａ））、このメッセージＭにハッシュ関数を適用し、予め定められた方法によって適当に、多項式の組（ｍ１（ｘ）,ｍ２（ｘ））を計算し、署名演算部１４ｄに送る。署名演算部１４ｄは、秘密鍵格納部１４ｄから秘密鍵ｆ（ｘ）,ｇ（ｘ）,Ｆ（ｘ）,Ｇ（ｘ）を、共通パラメータ格納部１４ａからｑ,Ｎ,ｔｍａｘを抽出し、
Ｇ（ｘ）＊ｍ１（ｘ）‐Ｆ（ｘ）＊ｍ２（ｘ）＝Ａ（ｘ）＋ｑＢ（ｘ）
−ｇ（ｘ）＊ｍ１（ｘ）＋ｆ（ｘ）＊ｍ２（ｘ）＝ａ（ｘ）＋ｑｂ（ｘ）
を満たすＡ（ｘ）,Ｂ（ｘ）,ａ（ｘ）,ｂ（ｘ）∈Ｚｑ［ｘ］／（ｘＮ−１）を計算する。そして、Ｎ−１次の多項式ｓ（ｘ）＝ｆ（ｘ）＊Ｂ（ｘ）＋Ｆ（ｘ）＊ｂ（ｘ） ｍｏｄ ｑを署名として出力する（ｓ（ｘ）∈Ｚｑ［ｘ］／（ｘＮ−１））。このように出力されたＮＴＲＵ多項式ｓ（ｘ）は、正規化部１５に送られる。
【００２５】
［ステップＳ３］
ＮＴＲＵ多項式ｓ（ｘ）が送られた正規化部１５は、正規化基準情報格納部１１から定数Ｌを抽出し、その定数Ｌ（「正規化基準」に相当）に基づき、ＮＴＲＵ多項式ｓ（ｘ）を正規化した（第１の）正規多項式ｓ’（ｘ）を生成する。
すなわち、まず、多項式生成部１５ｂ（図２の（ａ））において、共通パラメータ格納部１５ａからパラメータＮを抽出してＮ−１次の多項式
【数１１】
2005236904.tif 000005
を生成し、多項式スカラー倍部１５ｃに送る。これを受け取った多項式スカラー倍部１５ｃは、別途に入力された定数ＬとＮＴＲＵ多項式ｓ（ｘ）から、ＮＴＲＵ多項式ｓ（ｘ）のＬ次の係数ｓＬを求め、式（１２）の係数を‐ｓＬ倍して剰余計算部１５ｅに送る。剰余計算部１５ｅは、前述のように処理を行い、その出力を多項式スカラー倍部１５ｃに返す。多項式スカラー倍部１５ｃは、剰余計算部１５ｅからの出力を各項の係数とする多項式
【数１２】
2005236904.tif 000006
を多項式加算部１５ｄに送る。
【００２６】
式（１３）の多項式を受け取った多項式加算部１５ｄは、この多項式の各係数と、別途に入力されたＮＴＲＵ多項式ｓ（ｘ）の各係数を加算し、剰余計算部１５ｅに送る。剰余計算部１５ｅは、前述のように処理を行い、その出力を多項式加算部１５ｄに返す。多項式加算部１５ｄは、この剰余計算部１５ｅからの出力を各項の係数とする多項式
【数１３】
2005236904.tif 000007
の演算結果を正規多項式ｓ’（ｘ）とし、初期候補設定部１６及び変形部１７に送る。
【００２７】
［ステップＳ４］
正規多項式ｓ’（ｘ）を受け取った初期候補設定部１６は、正規多項式ｓ’（ｘ）を、署名候補である候補多項式ｓ’’（ｘ）とする。即ち、ｓ’’（ｘ）←ｓ’（ｘ）とおく。設定された候補多項式ｓ’’（ｘ）は、変形部１７及びＮＴＲＵ署名検証部１８に送られる。
［ステップＳ５］
ＮＴＲＵ署名検証部１８において、メッセージＭ及び候補多項式ｓ’’（ｘ）を入力し、候補多項式ｓ’’（ｘ）のＮＴＲＵ署名検証を行う。
すなわち、まず、ハッシュ演算部１８ｃにおいて（図３の（ｂ））、メッセージＭから多項式の組（ｍ１（ｘ）,ｍ２（ｘ））を計算し、比較部１８ｅに送る。なお、この生成方法は、前述のハッシュ演算部１４ｃ（図３の（ａ））と同一である。また、乗算部１８ｄにおいて、公開鍵格納部１８ｂから公開鍵ｈ（ｘ）を、共通パラメータ格納部１８ａからパラメータｑ,ｔｍａｘを抽出し、入力されたｓ’’（ｘ）からｔ’’（ｘ）＝ｓ’’（ｘ）＊ｈ（ｘ） ｍｏｄ ｑを計算する。算出されたｔ’’（ｘ）は比較部１８ｅに送られ、比較部１８ｅは、入力されたｔ’’（ｘ）, ｓ’’（ｘ）, ｍ１（ｘ）,ｍ２（ｘ）を用い、
‖ｓ’’（ｘ）−ｍ１（ｘ）‖２＋‖ｔ’’（ｘ）−ｍ２（ｘ）‖２ 
を計算し、その演算結果が定数Ｎｂ（NormBound）以下であるか否かを判断する。ここで、‖ｓ’’（ｘ）−ｍ１（ｘ）‖２＋‖ｔ’’（ｘ）−ｍ２（ｘ）‖２≦Ｎｂ２であれば、比較部１８ｅにおいて「合格（ＯＫ）」を出力し、そうでなければ「不合格（ＮＧ）」を出力する。
【００２８】
［ステップＳ６］
次に、ＮＴＲＵ署名検証部１８において、ＮＴＲＵ署名検証が合格となったか否かを判断する。ここで、合格となった場合、ステップＳ７に進む。一方、不合格となった場合、ステップＳ８に進む。
［ステップＳ７］
ＮＴＲＵ署名検証部１８おいて、候補多項式ｓ’’（ｘ）を署名出力部１９に送る。そして、署名出力部１９において、メッセージＭと共に、この候補多項式ｓ’’（ｘ）を署名である署名多項式ｕ（ｘ）として出力し、処理を終了する。
【００２９】
［ステップＳ８］
変形部１７において、変形基準情報格納部１２から関数ｒ（ｘ）（「変形基準」に相当）を抽出し、これに基づいて入力された候補多項式ｓ’’（ｘ）を変形し、新たな候補多項式ｓ’’（ｘ）を生成する。
すなわち、まず、多項式生成部１７ｂ（図２の（ｂ））において、共通パラメータ格納部１７ａからパラメータＮを抽出し、前述の式（１２）で示したＮ−１次の多項式を生成して、多項式スカラー倍部１７ｃに送る。これを受け取った多項式スカラー倍部１７ｃは、別途に入力された定数Ｌと候補多項式ｓ’’（ｘ）から、候補多項式ｓ’’（ｘ）のＬ次の係数ｓ’’Ｌを求め、これを入力された関数ｒ（ｘ）に代入する（ｒ（ｓ’’Ｌ））。そして、多項式スカラー倍部１７ｃは、式（１２）の係数をｒ（ｓ’’Ｌ）して剰余計算部１７ｅに送り、剰余計算部１７ｅは、前述のように処理を行い、その出力を多項式スカラー倍部１７ｃに返す。
【００３０】
多項式スカラー倍部１７ｃは、剰余計算部１７ｅからの出力を各項の係数とする多項式
【数１４】
2005236904.tif 000008
を多項式加算部１７ｄに送る。
式（１５）の多項式を受け取った多項式加算部１７ｄは、この多項式の各係数と、別途に入力された正規多項式ｓ’（ｘ）の各係数を加算し、剰余計算部１７ｅに送る。剰余計算部１７ｅは、前述のように処理を行い、その出力を多項式加算部１７ｄに返す。多項式加算部１７ｄは、この剰余計算部１７ｅからの出力を各項の係数とする多項式
【数１５】
2005236904.tif 000009
の演算結果を新たな候補多項式ｓ’’（ｘ）として、ＮＴＲＵ署名検証部１８に出力する。
【００３１】
［ステップＳ９］
次に、変形部１７において、新たに生成された候補多項式ｓ’’（ｘ）のＬ次の係数ｓ’’Ｌが、０ ｍｏｄｑと等しくないか否かを判断する。ここで、これらが等しいと判断された場合、署名を出力することなく異常終了する。一方、これらが等しくない判断された場合、新たに生成された候補多項式ｓ’’（ｘ）をＮＴＲＵ署名検証部１８に送り、ステップＳ５の処理に戻る。
【００３２】
＜署名生成処理の具体例＞
次に、具体例を用い、上述の処理を概念的に説明する。
図６は、上述のステップＳ３の正規多項式ｓ’（ｘ）の生成処理を説明するためのグラフである。ここで、（ａ）はＮＴＲＵ多項式ｓ（ｘ）の各係数を、（ｂ）は正規多項式ｓ’（ｘ）の各係数を示している。なお、このグラフにおける縦軸は多項式の各係数値を示し、横軸はその次数を示している。
この図に示すように、本形態における正規化とは、ＮＴＲＵ多項式ｓ（ｘ）のＬ次（ｉ＝Ｌ）の係数ｓＬが０となるように、各係数値を減算する処理である。ただし、その減算結果は、前述のように剰余計算部１５ｅでｍｏｄｑがとられている。そのため、係数値と減算値によっては、図６に示したものと異なり、正規多項式ｓ’（ｘ）の各係数値が、ＮＴＲＵ多項式ｓ（ｘ）の各係数値を単にスライドしたものとならない場合がある。
【００３３】
図７は、このような状況を示したグラフである。なお、図７の（ａ）はＮＴＲＵ多項式ｓ（ｘ）の各係数を、（ｂ）は正規多項式ｓ’（ｘ）の各係数を示している。
この例の場合、図７の（ａ）に示す、ＮＴＲＵ多項式ｓ（ｘ）におけるＡ次,Ｂ次,Ｃ次（ｉ＝Ａ,Ｂ,Ｃ）の係数の他項の係数に対する相対値は、図７の（ｂ）に示す、正規多項式ｓ’（ｘ）におけるＡ次,Ｂ次,Ｃ次（ｉ＝Ａ,Ｂ,Ｃ）の係数の他項の係数に対する相対値と異なる。
図８は、ステップＳ８の処理において、図７の（ｂ）に例示した正規多項式ｓ’（ｘ）から生成された候補多項式ｓ’’（ｘ）の各係数の値を示したグラフである。ここで（ａ）はｒ（ｓ’’Ｌ）=Ｄとなる場合の例であり、（ｂ）はｒ（ｓ’’Ｌ）=Ｅの場合の例である。
【００３４】
この図に示すように、本形態における正規多項式ｓ’（ｘ）の変形とは、正規多項式ｓ’（ｘ）のＬ次（ｉ＝Ｌ）の係数がｒ（ｓ’’Ｌ）となるように、各係数値にｒ（ｓ’’Ｌ）を加算する処理である。ただし、その演算結果は、前述のように剰余計算部１７ｅでｍｏｄｑがとられている。そのため、係数値とｒ（ｓ’’Ｌ）の値によっては、図８の（ａ）のように、新たな候補多項式ｓ’’（ｘ）の各係数値が、正規多項式ｓ’（ｘ）の各係数値を単にスライドしたものとなる場合もあれば、図８の（ｂ）のように、新たな候補多項式ｓ’’（ｘ）の各係数値が、正規多項式ｓ’（ｘ）の各係数値を単にスライドしたものとならない場合もある。
【００３５】
＜事例１＞
ここで、ステップＳ２において、図６の（ａ）に示すＮＴＲＵ多項式ｓ（ｘ）が生成され、ステップＳ３において、図６の（ｂ）に示す正規多項式ｓ’（ｘ）が生成されたとする。この場合、正規多項式ｓ’（ｘ）の各係数の値は、ＮＴＲＵ多項式ｓ（ｘ）の各係数の値をスライドさせただけのものであり、それらのばらつきも変化しない。そして、ステップＳ４において、まず、正規多項式ｓ’（ｘ）が候補多項式ｓ’’（ｘ）とされるため、その直後のステップＳ５における候補多項式ｓ’’（ｘ）の検証は合格となる（「発明が解決しようとする課題」参照。）。そして、このＮＴＲＵ署名検証部１８において最初に合格と判断された候補多項式ｓ’’（ｘ）が署名ｕ（ｘ）として出力される（ステップＳ７）。
【００３６】
＜事例２＞
また、ステップＳ２において、図７の（ａ）に示すＮＴＲＵ多項式ｓ（ｘ）が生成され、ステップＳ３において、図７の（ｂ）に示す正規多項式ｓ’（ｘ）が生成されたとする。この場合、正規多項式ｓ’（ｘ）の各係数の値は、ＮＴＲＵ多項式ｓ（ｘ）の各係数の値をスライドさせたものではない。よってそのばらつきも変化する。そして、ステップＳ４において、まず、正規多項式ｓ’（ｘ）が候補多項式ｓ’’（ｘ）とされるため、その直後のステップＳ５における候補多項式ｓ’’（ｘ）の検証は不合格となる場合がある。ここで、この検証が不合格となり、次に、ステップＳ８において、図８の（ａ）に示す新たな候補多項式ｓ’’（ｘ）が生成されたものとする。ここでは、ｓ’’Ｌ＝０ｍｏｄ ｑでないため（ステップＳ９）、ステップＳ５に戻り、新たな候補多項式ｓ’’（ｘ）の検証が行われる。そして、再び不合格であり（ステップＳ６）、ステップＳ８において図８の（ｂ）に示す新たな候補多項式ｓ’’（ｘ）が生成されたものとする。そして、ｓ’’Ｌ＝０ｍｏｄ ｑでないため（ステップＳ９）、ステップＳ５に戻り、この新たな候補多項式ｓ’’（ｘ）の検証が合格となったとする。その場合、この最初に合格と判断された図８の（ｂ）に示す候補多項式ｓ’’（ｘ）が署名ｕ（ｘ）として出力される（ステップＳ７）。
【００３７】
＜署名検証処理＞
次に、デジタル署名検証装置２０において行われる署名検証処理について説明する。
図５は、本形態における署名検証処理を説明するためのフローチャートである。以下、このフローチャートに沿って、この署名検証処理を説明していく。
［ステップＳ１１］
署名入力部２３において、署名であるＮ−１次の署名多項式ｕ（ｘ）とメッセージＭの入力を受け付ける。入力された署名多項式ｕ（ｘ）は、正規化部２４、ＮＴＲＵ署名検証部２７及び署名判定部２８に送られ、メッセージＭは、ＮＴＲＵ署名検証部２７に送られる。
［ステップＳ１２］
ＮＴＲＵ署名検証部２７において、入力された署名多項式ｕ（ｘ）とメッセージＭから、この署名多項式ｕ（ｘ）のＮＴＲＵ署名検証を行う（ステップＳ５と同様な手順）。この判定結果は署名判定部２８に送られる。
【００３８】
［ステップＳ１３］
署名判定部２８において、ステップＳ１２における検証が合格であるか否かを判断する。ここで不合格であった場合、署名判定部２８において、署名は不合格である旨を出力し処理を終了する（ステップＳ２２）。一方、ステップＳ１２における検証が合格であった場合、ステップＳ１４に進む。
［ステップＳ１４］
署名判定部２８において、正規化基準情報格納部２１から定数Ｌを抽出し、署名多項式ｕ（ｘ）のＬ次の係数ｕＬが０であるか否か、すなわち、署名多項式ｕ（ｘ）が正規化された多項式であるか否かを判断する。
ここで、署名多項式ｕ（ｘ）のＬ次の係数ｕＬが０であった場合、署名判定部２８において、署名は合格である旨を出力し処理を終了する（ステップＳ２１）。これは、後述のように、署名多項式ｕ（ｘ）を正規多項式ｕ’（ｘ）に正規化し、この正規多項式ｕ’（ｘ）を検証多項式ｕ’（ｘ）とした場合に、最初にＮＴＲＵ署名検証部２７において合格と判断された検証多項式ｕ’（ｘ）が署名多項式ｕ（ｘ）と等しくなることに相当する。
一方、署名多項式ｕ（ｘ）のＬ次の係数ｕＬが０でなかった場合、ステップＳ１５に進む。
【００３９】
［ステップＳ１５］
正規化部２４において、正規化基準情報格納部２１から定数Ｌを抽出し、その定数Ｌ（「正規化基準」に相当）に基づき、署名多項式ｕ（ｘ）を正規化した（第２の）正規多項式ｕ’（ｘ）を生成する。すなわち、多項式加算部、多項式スカラー倍部及び剰余計算部等を用い、前述のステップＳ３と同様な処理により、
【数１６】
2005236904.tif 000010
の演算結果を正規多項式ｕ’（ｘ）とする。なお、ｕＬは、署名多項式ｕ（ｘ）のＬ次の係数を示す。
このように生成された正規多項式ｕ’（ｘ）は、初期対象設定部２５及び変形部２６に送られる。
【００４０】
［ステップＳ１６］
正規多項式ｕ’（ｘ）を受け取った初期対象設定部２５は、正規多項式ｕ’（ｘ）を、検証対象である検証多項式ｕ’’（ｘ）とする。即ち、ｕ’’（ｘ）←ｕ’（ｘ）とおく。設定された検証多項式ｕ’’（ｘ）は、変形部２６及びＮＴＲＵ署名検証部２７に送られる。
［ステップＳ１７］
ＮＴＲＵ署名検証部２７において、メッセージＭ及び検証多項式ｕ’’（ｘ）を入力し、ステップＳ５と同様な方法により、検証多項式ｕ’’（ｘ）のＮＴＲＵ署名検証を行い、その検証結果を署名判定部２８に送る。
［ステップＳ１８］
次に、署名判定部２８において、ＮＴＲＵ署名検証部２７におけるＮＴＲＵ署名検証が合格であったか否かを判断する。ここで、ＮＴＲＵ署名検証が合格であった場合、署名判定部２８において、署名が不合格である旨を出力し、処理を終了する（ステップＳ２２）。一方、ＮＴＲＵ署名検証が不合格であった場合、ステップＳ１９に進む。
【００４１】
［ステップＳ１９］
変形部２６において、変形基準情報格納部２２から関数ｒ（ｘ）（「変形基準」に相当）を抽出し、これに基づいて入力された正規多項式ｕ’（ｘ）を変形し、新たな検証多項式ｕ’’（ｘ）を生成する。
すなわち、多項式加算部、多項式スカラー倍部及び剰余計算部等を用い、前述のステップＳ８と同様な処理により、
【数１７】
2005236904.tif 000011
の演算結果を新たな検証多項式ｕ’’（ｘ）とする。なお、ｕ’’Ｌは、検証多項式ｕ’’（ｘ）のＬ次の係数を示す。
このように生成された検証多項式ｕ’’（ｘ）は、ＮＵＲＵ署名検証部２７及び署名判定部２８に送られる。
【００４２】
［ステップＳ２０］
署名判定部２８において、ｕ’’Ｌ＝ｕＬ ｍｏｄ ｑとなるか否かを判断する。
すなわち、署名判定部２８は、正規化基準情報格納部２１から定数Ｌを抽出し、入力された検証多項式ｕ’’（ｘ）及び署名多項式ｕ（ｘ）から、それぞれのＬ次の係数ｕ’’Ｌ,ｕＬを算出する。そして、剰余計算部を用い、ｕ’’Ｌ ｍｏｄ ｑとｕＬ ｍｏｄ ｑを算出し、ｕ’’Ｌ＝ｕＬ ｍｏｄ ｑとなるか否かを判断する。ここで、ｕ’’Ｌ＝ｕＬ ｍｏｄ ｑであると判断された場合、署名判定部２８において、署名が合格である旨を出力し、処理を終了する（ステップＳ２１）。一方、ｕ’’Ｌ＝ｕＬ ｍｏｄ ｑであると判断された場合、ステップＳ１７に戻る。
【００４３】
＜署名検証処理の具体例＞
次に、具体例を用い、上述の処理を概念的に説明する。
図９から図１１は、本形態における署名検証処理を概念的に説明するためのグラフである。なお、これらのグラフにおける縦軸は多項式の各係数値を示し、横軸はその次数を示している。
＜事例１＞
ステップＳ１１の処理において、図９に示す正当な署名多項式ｕ（ｘ）が入力されたものとする。図９に示すように、この署名多項式ｕ（ｘ）のＬ次の係数ｕＬは０であり、このｕ（ｘ）は正規化された多項式である。この署名多項式ｕ（ｘ）のＮＴＲＵ署名は合格であるものとすると、ステップＳ１３からステップＳ１４の処理に進み、さらにｕＬ＝０であるため、署名出力部１９において、署名が合格である旨が出力し、処理を終了する。
【００４４】
＜事例２＞
ステップＳ１１の処理において、図１０の（ａ）に示す正当な署名多項式ｕ（ｘ）が入力されたものとする。図１０の（ａ）に示すように、この署名多項式ｕ（ｘ）のＬ次の係数ｕＬはＥである。この署名多項式ｕ（ｘ）のＮＴＲＵ署名は合格であるものとすると、ステップＳ１３からステップＳ１４の処理に進み、さらにｕＬ＝０でないため、ステップＳ１６において、この署名多項式ｕ（ｘ）が正規化され、図１０の（ｂ）に示す正規多項式ｕ’（ｘ）が生成される。次に、ステップＳ１６の処理において、この正規多項式ｕ’（ｘ）が検証多項式ｕ’’（ｘ）として設定され、ステップＳ１７において、そのＮＴＲＵ署名検証が行われる。ここで、このＮＴＲＵ署名が不合格であるとすると、ステップＳ１９において新たな検証多項式ｕ’’（ｘ）を生成する。この新たな検証多項式ｕ’’（ｘ）が図１０の（ｃ）に示すものであるとすると、そのＬ次の係数ｕ’’ＬはＥとなり、署名多項式ｕ（ｘ）のＬ次の係数ｕＬと等しくなる。これは、ＮＴＲＵ署名検証部２７で最初に合格であると判断された検証多項式ｕ’’（ｘ）が署名多項式ｕ（ｘ）と等しいことを意味している。この場合、ステップＳ２１の処理において、署名が合格である旨を出力する。
【００４５】
＜事例３＞
ステップＳ１１の処理において、図１１の（ａ）に示す署名多項式ｕ（ｘ）が入力されたものとする。なお、この署名多項式ｕ（ｘ）は正当に生成されたものではなく、攻撃者が任意に生成したものであり、ＮＴＲＵ署名検証が不合格となるものであるとする。
この場合、ステップＳ１２による署名多項式ｕ（ｘ）のＮＴＲＵ署名検証が不合格となり、ステップＳ２２の処理において、署名が不合格である旨が出力される。
つまり、前述のように、正当に生成された署名多項式は、規定の順序（ステップＳ３〜Ｓ９の手順）でステップＳ５のＮＴＲＵ署名検証を行い、最初に合格であると判断された候補多項式である。そのため、ステップＳ１２でのＮＴＲＵ署名検証が不合格となる署名多項式は必ず不当なものである。
【００４６】
＜事例４＞
ステップＳ１１の処理において、図１１の（ｂ）に示す署名多項式ｕ（ｘ）が入力されたものとする。なお、この署名多項式ｕ（ｘ）は正当に生成されたものではなく、攻撃者が、図１０の（ａ）に示した正当な署名多項式の各係数にＦ−Ｅを加算して生成した偽造署名であり、図１０の（ａ）に署名多項式の各係数を単にスライドさせたものとなっている。
この場合、ステップＳ１２におけるＮＴＲＵ署名検証は合格となる。また、この署名多項式ｕ（ｘ）のＬ次の係数ｕＬ＝Ｆであり、０ではないため（ステップＳ１４）、ステップＳ１５において、正規多項式ｕ’（ｘ）が生成される。この場合、この正規多項式ｕ’（ｘ）は、図１０の（ｂ）のようになる。次に、ステップＳ１６において、この正規多項式ｕ’（ｘ）を検証多項式ｕ’’（ｘ）とし、ステップＳ１７における検証多項式ｕ’’（ｘ）のＮＴＲＵ署名検証が不合格となり、ステップＳ１９において新たな検証多項式ｕ’’（ｘ）が生成される。この新たな検証多項式ｕ’’（ｘ）は図１０の（ｃ）のようになりｕ’’Ｌ=Ｅである。また、上述のようにｕＬ＝Ｆであるため、ステップＳ１７に戻り（ステップＳ２０）、この新たな検証多項式ｕ’’（ｘ）のＮＴＲＵ署名検証が行われる。このＮＴＲＵ署名検証は合格となり、ステップＳ２２において、署名が不合格である旨が出力される。すなわち、ＮＴＲＵ署名検証部２７において最初に合格であると判断された図１０の（ｃ）に示す検証多項式ｕ’’（ｘ）が、図１１の（ｂ）に示す署名多項式ｕ（ｘ）と等しくないため、署名が不合格である旨が出力される。
【００４７】
前述のように、正当に生成された署名多項式ｕ（ｘ）は、デジタル署名検証装置２０での処理（ステップＳ１５〜Ｓ２０）に対応する規定の順序（ステップＳ３〜Ｓ９：すなわち、正規多項式ｓ’（ｘ）である最初の候補多項式ｓ’’（ｘ）、最初の候補多項式ｓ’’（ｘ）のＬ次の係数を用いて生成した新たな候補多項式ｓ’’（ｘ）、この新たな候補多項式ｓ’’（ｘ）のＬ字の係数を用いて順次生成する新たな新たな候補多項式ｓ’’（ｘ）という順序）でＮＴＲＵ署名検証を行い、最初に合格であると判断された候補多項式ｓ’’（ｘ）である。
【００４８】
また、デジタル署名検証装置２０における署名多項式ｕ（ｘ）の検証は、デジタル署名生成装置１０での処理（ステップＳ３〜Ｓ９）に対応する規定の順序（ステップＳ１５〜Ｓ２０：すなわち、正規多項式である署名多項式ｕ（ｘ）（ステップＳ１２〜Ｓ１３）、最初の検証多項式ｕ’’（ｘ）のＬ次の係数を用いて生成した新たな検証多項式ｕ’’（ｘ）、この新たな検証多項式ｕ’’（ｘ）のＬ字の係数を用いて順次生成する新たな新たな検証多項式ｕ’’（ｘ）という順序）でＮＴＲＵ署名検証を行う。
そのため、入力された署名多項式ｕ（ｘ）が正当である場合、デジタル署名検証装置２０においてＮＴＲＵ署名検証が最初になる多項式は署名多項式ｕ（ｘ）に一致するはずである。事例４では、これが一致しないことにより、署名が不当であることを判断したものである。
【００４９】
〔第２の実施の形態〕
次に、本発明における第２の実施の形態について説明する。
第２の実施の形態は、第１の実施の形態の変形例であり、正規化基準情報に基準値Ｅが追加される点、前述の定数Ｌと基準値Ｅを用い、正規化部における正規化を行う点が、第１の実施の形態と相違する。以下では、第１の実施の形態との相違点のみを説明し、共通する事項については説明を省略する。
＜構成＞
図１２は、本形態におけるデジタル署名システム１００の構成を例示した図である。なお、図１２において第１の実施の形態と同様な機能構成については、図１と同じ符号を付した。
図１２に例示するように、デジタル署名システム１００は、デジタル署名を生成するデジタル署名生成装置１００、及びデジタル署名を検証するデジタル署名検証装置１２０を有している。
【００５０】
＜デジタル署名生成装置＞
本形態におけるデジタル署名生成装置１１０は、第１の実施の形態における正規化基準情報格納部１１に換えて正規化基準情報格納部１１１が設けられ、正規化部１５に換えて正規化部１１５が設けられる点のみが第１の実施の形態と相違する。
＜デジタル署名検証装置＞
本形態におけるデジタル署名生成装置２１０は、第１の実施の形態における正規化基準情報格納部２１に換えて正規化基準情報格納部２１１が設けられ、正規化部２４に換えて正規化部１２４が設けられる点のみが第１の実施の形態と相違する。
＜前処理＞
正規化基準情報格納部１１１,１２１に正規化基準情報に相当する基準値Ｅと定数Ｌが格納される点のみが、第１の実施の形態と相違する。ここで、基準値Ｅは、正規化部１１５,１２４における正規化が行われた際、正規化多項式のＬ次の係数がとるべき値を示している。これは、この値を０に固定していた第１の実施の形態と相違する。なお、基準値Ｅは、デジタル署名生成装置１１０とデジタル署名検証装置１２０とで共有する秘密情報である。
【００５１】
＜署名生成処理＞
本形態の第１の実施の形態との相違点は、ステップＳ３において、正規化部１１５が正規化基準情報格納部１１１から基準値Ｅと定数Ｌを抽出し、
【数１８】
2005236904.tif 000012
の演算結果を正規多項式ｓ’（ｘ）とする点、及びステップＳ９において、ｓ’’Ｌ＝０ ｍｏｄ qであるか否かを判断する換わりに、ｓ’’Ｌ＝Ｅ ｍｏｄ qであるか否かを判断する点である。
【００５２】
＜署名検証処理＞
本形態の第１の実施の形態との相違点は、ステップＳ１５において、正規化部１２４が正規化基準情報格納部１２１から基準値Ｅと定数Ｌを抽出し、
【数１９】
2005236904.tif 000013
の演算結果を正規多項式ｕ’（ｘ）とする点、及びステップＳ１４において、ｕＬ＝０であるか否かを判断する換わりに、ｕＬ＝Ｅであるか否かを判断する点である。
以上のような構成としても第１の実施の形態と同様、ＮＴＲＵ署名の偽造を防止できる。さらに、秘密情報として基準値Ｅを追加したことにより、より安全性を向上することができる。
なお、本発明は上述の各実施の形態に限定されるものではない。
【００５３】
例えば、前述の実施の形態では、デジタル署名生成装置１０,１１０において候補多項式が１つ設定されるたびに、ＮＴＲＵ署名検証部１８が当該候補多項式の検証を行い、この候補多項式のＮＴＲＵ署名検証が不合格であった場合に、変形手段１７が、新たな候補多項式を生成することとしていた。しかし、デジタル署名生成装置１０,１１０において候補多項式を複数個一度に生成し、それをデジタル署名生成装置２０,１２０と共有される規定の順序でＮＴＲＵ署名検証することとしてもよい。
すなわち、前述の実施の形態では、候補多項式が不合格であった場合、変形部１７において、関数ｒ（ｘ）に基づいて正規多項式を変形することにより新たな候補多項式を生成する処理と、ＮＴＲＵ署名検証部１８において当該候補多項式のＮＴＲＵ署名検証を行う処理とを、当該候補多項式が合格となるまで繰り返し、合格となった当該候補多項式を、署名出力部１９において署名として出力していた。しかし、複数の候補多項式をまとめて生成し、規定の順序で、この候補多項式のＮＴＲＵ署名検証を行い、最初に合格となった当該候補多項式を署名として出力してもよい。
【００５４】
同様に、前述の実施の形態では、デジタル署名検証装置２０,１２０において、ＮＴＲＵ署名検証部２７は、署名多項式の入力後、正規多項式の生成前に、署名多項式の検証を行い、検証多項式が１つ設定されるたびに、当該検証多項式の検証を行い、正規化部２４,１２４は、ＮＴＲＵ署名検証２７において署名多項式が合格であると判断され、なおかつ、当該署名多項式が正規化された多項式でなかった場合に、正規多項式を生成し、変形部２６は、検証多項式のＮＴＲＵ署名検証が不合格であった場合に、新たな検証多項式を生成することとしていた。しかし、デジタル署名検証装置２０,１２０において、一度に正規多項式及び複数の検証多項式を生成し、それをデジタル署名生成装置１０,１１０と共有される規定の順序でＮＴＲＵ署名検証することとしてもよい。
【００５５】
すなわち、前述の実施の形態では、検証多項式と署名多項式とが等しくなるか、或いは、署名多項式と等しく無い検証多項式が合格となるまで、変形部２６において、検証多項式の生成を繰り返し、検証多項式と署名多項式とが等しくなった場合、署名判定部２８において、署名が合格である旨を出力し、署名多項式と等しく無い検証多項式が合格となった場合、署名判定部において、署名が不合格である旨を出力していた。しかし、複数の検証多項式をまとめて生成し、規定の順序で、この検証多項式のＮＴＲＵ署名検証を行い、最初にＮＴＲＵ署名検証が合格となった当該検証多項式と署名多項式とが等しくなった場合、署名が合格である旨を出力し、等しくなかった場合、署名が不合格である旨を出力してもよい。
また、前述の実施の形態で示した正規化基準及び正規化部１５,２４,１１５,１２４で行われる正規化方法は単なる例示であり、他の正規化基準を用い、異なる正規化方法によって多項式の正規化を行うこととしてもよい。ただし、デジタル署名生成装置１０,１１０とデジタル署名検証装置２０,１２０の正規化基準及び正規化方法は同じでなければならない。
【００５６】
さらに、前述の実施の形態で示した変形基準及び変形部１７,２６で行われる多項式の変形方法は単なる例示であり、他の変形基準を用い、異なる変形方法によって多項式の変形を行うこととしてもよい。ただし、デジタル署名生成装置１０,１１０とデジタル署名検証装置２０,１２０の変形基準及び変形方法は同じでなければならない。
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図面の簡単な説明】
【００５９】
【図１】第１の実施の形態におけるデジタル署名システムの構成を例示した図。
【図２】（ａ）は、第１の実施の形態における正規化部の詳細構成を例示した図、（ｂ）は、変形部の詳細構成を例示した図。
【図３】（ａ）は、第１の実施の形態におけるＮＴＲＵ署名生成部の詳細構成を例示した図、（ｂ）は、ＮＴＲＵ署名検証部の詳細構成を例示した図。
【図４】第１の実施の形態における署名生成処理を説明するためのフローチャート。
【図５】第１の実施の形態における署名検証処理を説明するためのフローチャート。
【図６】正規多項式の生成処理を説明するためのグラフ。
【図７】正規多項式の生成処理を説明するためのグラフ。
【図８】候補多項式の各係数の値を示したグラフ。
【図９】署名検証処理を概念的に説明するためのグラフ。
【図１０】署名検証処理を概念的に説明するためのグラフ。
【図１１】署名検証処理を概念的に説明するためのグラフ。
【図１２】第２の実施の形態におけるデジタル署名システムの構成を例示した図。
【符号の説明】
【００６０】
１,１００  デジタル署名システム
１０,１１０  デジタル署名生成装置
２０,１２０  デジタル署名検証装置
１１,２１,１１１,１２１  正規化基準情報格納部
１２,２２  変形基準情報格納部
１５,２４,１１５,１２４  正規化部
１７,２６  変形部
【図１】
2005236904.tif 000022
【図２】
2005236904.tif 000023
【図３】
2005236904.tif 000024
【図４】
2005236904.tif 000025
【図５】
2005236904.tif 000026
【図６】
2005236904.tif 000027
【図７】
2005236904.tif 000028
【図８】
2005236904.tif 000029
【図９】
2005236904.tif 000030
【図１０】
2005236904.tif 000031
【図１１】
2005236904.tif 000032
【図１２】
2005236904.tif 000033