(57)【要約】【課題】先行技術の問題の少なくとも一部を解決する、楕円曲線の点へのハッシング方法を提供する。【解決手段】グループの要素、特に、楕円曲線の点へのハッシングに関する。入力メッセージは、例えば、ＳＨＡ−１及びＭＤ５等の通例のハッシングアルゴリズムを通され、グループの要素との乗法においてスカラーとして使用される。その結果が、必然的に、グループの要素でもある。利点は、ハッシングアルゴリズムのセキュリティが、基礎を成す通例のハッシングアルゴリズムのセキュリティと同等である点である。また、装置も提供される。【選択図】図１
2010191419.tif 000002
【特許請求の範囲】
【請求項１】
任意の有限な長さの文字列をグループの要素にハッシングする方法であって、装置において、
前記文字列をスカラーへマッピングする第１ハッシングアルゴリズムから生ずる第１ハッシュ値を得るステップと、
前記グループの第２要素を得るよう、前記第１ハッシュ値の少なくとも第１部分と前記グループの所定の第１要素との間でスカラー乗法を行うステップと、
前記グループの前記第２要素を出力するステップと
を有する方法。
【請求項２】
前記グループは、楕円曲線の点を有する、請求項１記載の方法。
【請求項３】
前記第１ハッシュ値を得るステップは、前記文字列を取得し、前記スカラーを得るよう該文字列について前記第１ハッシュ値を計算するステップを有する、請求項１記載の方法。
【請求項４】
前記グループの前記第１要素は、最大次数の要素である、請求項１記載の方法。
【請求項５】
前記グループの第４要素を得るよう、前記第１ハッシュ値の第２部分と前記グループの所定の第３要素との間でスカラー乗法を行うステップと、
前記グループの第５要素を得るよう、前記グループの前記第２要素及び前記グループの前記第４要素を足し合わせるステップと
を更に有する請求項１記載の方法。
【請求項６】
任意の有限な長さの文字列をグループの要素にハッシングする装置であって、
前記文字列をスカラーへマッピングする第１ハッシングアルゴリズムから生ずる第１ハッシュ値を得る手段と、
前記グループの第２要素を得るよう、前記第１ハッシュ値と前記グループの所定の第１要素との間でスカラー乗法を行う手段と、
前記グループの前記第２要素を出力する手段と
を有する装置。
【請求項７】
前記グループは、楕円曲線の点を有する、請求項６記載の装置。
【請求項８】
前記第１ハッシュ値を得る手段は、前記第１ハッシュ値を計算するよう構成される、請求項６記載の装置。
【請求項９】
前記グループの前記第１要素は、最大次数の要素である、請求項６記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、暗号化に関し、具体的に、楕円曲線（elliptic  curve）の点へのハッシングに関する。
【背景技術】
【０００２】
本項目は、以下本明細書中に記載され、あるいは、特許請求の範囲で請求される本発明の様々な態様に関連する当該技術の様々な側面を紹介することを目的とする。ここでの記載は、本発明の様々な態様のより良い理解を助けるべく、背景情報を読み手に与えるのに役立つと信じられる。然るに、当然ながら、かかる記載は、先行技術の承認としてではなく、この観点から読まれるべきである。
【０００３】
ハッシュ関数は、入力としてメッセージ（通常、文字列（string）として表される。）をとり、固定長のハッシュ値（「メッセージ・ダイジェスト」又は「デジタル・フィンガープリント」とも呼ばれる。）を生成する。より具体的に、ハッシュ関数ｈは、任意の有限の長さのビット列を固定長（例えば、Ｉビット）のビット列へマッピングする（ｈ：｛０，１｝＊→｛０，１｝Ｉ；ｍ｜→ｈ（ｍ））。ハッシュ値ｈ（ｍ）は、入力文字列ｍのコンパクトな表現である。
【０００４】
暗号アプリケーションに関し、ハッシュ関数は付加的な特性を必要としうる：
−  原像計算困難性（Preimage  resistance）：出力ｖを考えると、ｖへハッシングする入力ｕ（すなわち、ｈ（ｕ）＝ｖ）を見つけることは、計算的に実行不可能である。
−  第２原像計算困難性（Second-image  resistance）：ｕ及びｖ＝ｈ（ｕ）の組を考えると、ｖへハッシングする第２入力ｕ’≠ｕ（すなわち、ｈ（ｕ’）＝ｖ＝ｈ（ｕ））を見つけることは、計算的に実行不可能である。
−  衝突困難性（Collision  resistance）：同じ値へハッシングする何らかの２つの異なる入力ｕ及びｕ’（すなわち、ｕ≠ｕ’の場合に、ｈ（ｕ）＝ｈ（ｕ’））を見つけることは、計算的に実行不可能である。
−  ランダムオラクル（Random  oracle）：幾つかのセキュリティ・プルーフ（security  proofs）は、ハッシュ関数の出力がランダムオラクルとして振る舞うと仮定する。これは、M.Bellare及びP.Rogawayにより著された「Random  Oracles  are  Practical：A  Paradigm  for  Designing  Efficient  Protocols」、1st  ACM  Conference  on  Computer  and  Communications  security、６２〜７３頁、ACM  Press、１９９３年で記載される、いわゆるランダムオラクルモデルである。
【０００５】
ハッシュ関数は、デジタル署名を含む多くの暗号アプリケーションで用いられており、それらは、現代の暗号化アルゴリズムの設計において基本的な役割を果たし、それらは、メッセージ認証コード（ＭＡＣ（Message  Authentication  Code））を構成する働きをすることができる。ＭＡＣは、秘密キーＫによってインデックスを付される一群の関数ｈKである。ＭＡＣについては、例えば、２００２年３月に公開されたＦＩＰＳ１９８及び２００７年６月に公開されたＦＩＰＳ１９８−１（いずれも「The  Keyed-Hash  Message  Authentication  Code（ＨＭＡＣ）」（Federal  Information  Processing  Standards  Publication）と呼ばれる。）に記載されている。
【０００６】
幾つかの暗号アプリケーションは、楕円曲線の点へのハッシングを必要とする。これは、例えば、D.Boneh及びM.Franklinにより著された「Identity-Based  Encryption  from  the  Weil  Pairing」（SIAM  Journal  of  Computing、32(3)：５８６〜６１５頁、２００３年）に記載されるもの等、同一性（identity）に基づく暗号化スキームを含む。このスキームは、旧来の証明書（certificate）に基づく暗号化よりもずっと簡単な公開キー・インフラストラクチャを特色とする。このスキームは楕円曲線点上の双一次対を使用する。特に、いわゆる‘抽出（extract）’プロシージャは、任意の有限な文字列を所与の楕円曲線の点へマッピングするハッシュ関数を必要とする。
【０００７】
Ｇ（太字）が楕円曲線の点のグループ（又はサブグループ）を表す場合に、問題は、入力として文字列ｍをとるハッシュ関数をどのように設計し、楕円曲線の点を表すハッシュ値Ｈ：｛０，１｝＊→Ｇ，ｍ｜→Ｈ（ｍ）∈Ｇを生成するのかである。
【０００８】
１つのこのような方法は、N.Koblitzにより著された「A  Course  in  Number  Theory  and  Cryptography」第６章の２、Graduate  Texts  in  Mathematics第１１４巻、シュプリンガー・フェルラーグ版、第２版、１９９４年に記載される技術から得られる。κは、試み（try）について成功の可能性が約０．５である場合に、方法の失敗可能性がおおよそ２−κであるように、試みの最大数に対応する大きな整数を表すとする。また、Ｅは、ワイエスシュトラスの式：
Ｅ：ｙ２＋ａ１ｘｙ＋ａ３ｙ＝ｘ３＋ａ２ｘ２＋ａ４ｘ＋ａ６
によって与えられる有限場Ｆ（太字）ｑに対して楕円曲線を表すとする。ここで、曲線パラメータａｉ∈Ｆｑ（１≦ｉ≦６）。
【０００９】
楕円曲線Ｅの点の組は、無限遠点と呼ばれる特別の点Ｏとともに、このワイエスシュトラスの式を満足する対（ｘ，ｙ）によって与えられる。入力メッセージｍを考えると、ｖ＝ｈ（ｍ）は最初に計算される。ここで、ｈ：｛０，１｝＊→｛０，１｝Ｉは何らかの適切なハッシュ関数（例えば、ＳＨＡ（Secure  Hash  Standard）の一種）であり、ｖは範囲［０，２Ｉ−１］にある整数と見なされる。夫々のｊ＝１，２，．．．，κ，ｍ’ｊについて、ｍ’ｊ＝ｖκ＋ｊが定義される。ｑ＞２Ｉκである場合に、多項式表現を用いて、そのように定義される整数ｍ’ｊとＦｑの要素の組との間には１対１の対応関係がある。ｘｊはｍ’ｊに対応するＦｑ要素を表す。次いで、ｊ＝１，２，．．．，κについて、座標ｘ＝ｘｊであり、ｙについてワイエスシュトラス式を解く試みが行われる。解が存在する場合は、それはｙｊで表される。
【００１０】
［外１］
2010191419.tif 000003
が、解が見つけられる｛１，．．．，κ｝の中で最小のｊを表す場合に、これは、
［外２］
2010191419.tif 000004
を表す。
【００１１】
この方法に伴う問題は、それがサイドチャネル解析及び欠陥解析を通して入力に関する情報を漏らすことである。これは、基礎を成すアプリケーションの安全性を危うくする。これは、また、出力分布に幾分の偏りを導入し、ランダムオラクルモデルに基づくセキュリティ・プルーフを無効にし、又は弱らせうる。更に、この方法の反復特性は幾らかの効率の悪さを引き起こす。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Barreto  Paul  S.  L.  M.及びHae  Kim  Y.著、「Fast  hashing  onto  elliptic  curves  over  fields  of  characteristic  3」、２００１年１１月１５日、１〜１１頁、IACRウェブサイト
【非特許文献２】Han  Song、Yeung  Winson  K  Y、Wang  Jie著、「Identity-based  confirmer  signatures  from  pairings  over  elliptic  curves」、PROCEEDINGS  OF  THE  4TH  ACM  CONFERENCE  ON  ELECTRONIC  COMMERCE、２００３年６月９〜１２日、２６２〜２６３頁、アメリカ合衆国、カリフォルニア州、サンディエゴ
【発明の概要】
【発明が解決しようとする課題】
【００１３】
従って、当然のことながら、先行技術の問題の少なくとも一部を解決する、楕円曲線の点へのハッシング方法が必要とされる。本発明は、かかる解決法を提供する。
【課題を解決するための手段】
【００１４】
第１の態様で、本発明は、任意の有限な長さの文字列をグループの要素にハッシングする方法を対象とする。前記文字列をスカラーへマッピングする第１ハッシングアルゴリズムから生ずる第１ハッシュ値が得られる。前記スカラーの少なくとも第１部分は、出力される前記グループの第２要素を得るよう、前記グループの所定の第１要素を乗じられる。
【００１５】
第１の好ましい実施形態で、前記グループは、楕円曲線の点を有する。
【００１６】
第２の好ましい実施形態で、前記文字列についての前記第１ハッシュ値は、前記スカラーを得るよう計算によって得られる。
【００１７】
第３の好ましい実施形態で、前記グループの前記第１要素は、最大次数の要素である。
【００１８】
第４の好ましい実施形態で、当該方法は、前記グループの第４要素を得るよう、前記第１ハッシュ値の第２部分と、前記グループの所定の第３要素との間でスカラー乗法を行うステップと、前記グループの第５要素を得るよう、前記グループの前記第２要素及び前記グループの前記第４要素を足し合わせるステップとを更に有する。
【００１９】
第２の態様で、本発明は、任意の有限な長さの文字列をグループの要素にハッシングする装置を対象とする。装置は、前記文字列をスカラーへマッピングする第１ハッシングアルゴリズムから生ずる第１ハッシュ値を得る手段と、前記グループの第２要素を得るよう、前記第１ハッシュ値と前記グループの所定の第１要素との間でスカラー乗法を行う手段と、前記グループの前記第２要素を出力する手段とを有する。
【００２０】
第１の好ましい実施形態で、前記グループは、楕円曲線の点を有する。
【００２１】
第２の好ましい実施形態で、前記第１ハッシュ値を得る手段は、前記第１ハッシュ値を計算するよう構成される。
【００２２】
第３の好ましい実施形態で、前記グループの前記第１要素は、最大次数の要素である。
【発明の効果】
【００２３】
本発明の実施形態によれば、先行技術の問題の少なくとも一部を解決する、楕円曲線の点へのハッシング方法を提供することが可能となる。
【図面の簡単な説明】
【００２４】
【図１】本発明の好ましい実施形態に従う装置を表す。
【発明を実施するための形態】
【００２５】
以下、本発明の好ましい特徴は、添付の図面を参照して、限定されない例によって、記載される。
【００２６】
先行技術の解決法と比較して、本発明は、楕円曲線の点へのハッシングのために根本的に異なるアプローチをとる。当該方法は、楕円曲線上の所定の点から開始し、グループの特性、すなわち、グループの要素とスカラーとの間の乗算はグループの通常は異なる要素を与えるという特性、に依存する。楕円局線の点へハッシングを行うよう、通例のハッシングアルゴリズムの出力はスカラーと見なされ、楕円曲線上の点はグループの要素（element  of  group）として見なされる。当業者には明らかなように、可能な出力の組を拡大することから、最大次数の要素を所定の点として使用することが有利である。
【００２７】
より具体的に、ｈ：｛０，１｝＊→｛０，１｝Ｉは、任意の有限長のビット列を長さＩのビット列へマッピングする通例のハッシュ関数を表す、とする。このようなハッシュ関数の例は、メッセージダイジェス５（ＭＤ５）及びＳＨＡ−１である。また、Ｅは楕円曲線を、Ｇ（太字）はそのサブグループを、Ｐ（太字）は少なくとも２Ｉの次数のＧの点を表す、とする。その場合に、本発明の所定の実施形態に従うハッシング方法は以下のように表される：
【００２８】
【数１】
2010191419.tif 000005
このハッシュ関数は、実行するのが容易であり、所与の楕円曲線上の点へのマッピングを行う。更に、２つの異なる入力メッセージｍ及びｍ’に関して、ｏｒｄ（Ｐ）＝２Ｉであるから、ｈ（ｍ）＝ｈ（ｍ’）が成立する場合且つその場合に限り、Ｈ（ｍ）＝Ｈ（ｍ’）という結果になる。結果として、ハッシュ関数Ｈの安全性は、基礎を成すハッシュ関数ｈの安全性と同じである。当然のことながら、ハッシュ関数及び楕円曲線に対する一般的な攻撃がスクエアルート・アタック（square-root  attacks）である場合に、提案される構成は最適である。
【００２９】
当業者には明らかなように、当該方法の多数の変形例が可能である。例えば、グループの１又はそれ以上の所定の要素は、乗算の後に加えられてよい。他の可能性は、ハッシュ値とグループにおける複数の要素との間で別個のスカラー乗法を行い、その後に、その結果を足し合わせることである（この加算が更なる要素をもたらす場合に、この合計は要素の加算の結果をスカラーに乗じたのと同じである。）。
【００３０】
更なる他の可能性は、ｎ個の、有利に相異なった、部分に分けられているスカラーハッシュ値を得、それらの部分とグループのｎ個の異なる要素との間でスカラー乗法を行い、次いで、その結果を足し合わせることである。言い換えると（ｎ＝２についての変形例を表す。）、ｈ（ｍ）＝ｈ１‖ｈ２及びＨ（ｍ）＝［ｈ１］Ｐ１＋［ｈ２］Ｐ２。ここで、Ｐ（太字）１及びＰ（太字）２はグループ内の要素である。
【００３１】
図１は、本発明の好ましい実施形態に従う装置を表す。装置１００は、他の装置（図示せず。）と通信を行うよう構成される少なくとも１つのインターフェースユニット（Ｉ／Ｏ）１１０と、少なくとも１つのプロセッサ（ＣＰＵ）１２０と、データ（例えば、中間計算結果）を記憶するよう構成される少なくとも１つのメモリ１３０とを有する。プロセッサ１２０は、場合により計算によって入力文字列のハッシュ値を得、グループの要素、有利に楕円曲線の点、との乗算のためにハッシュ値をスカラーとして用い、その結果を出力することによって、上述される方法を実行するよう構成される。例えばＣＤ−ＲＯＭ又はＤＶＤ等の、コンピュータプログラムプロダクト１４０は、本発明の実施形態のいずれかに従う方法を実行する命令をプロセッサ１２０に実行させる命令を有するコンピュータプログラムを記憶している。
【００３２】
本発明の方法は、入力値が楕円曲線の点へマッピングされるべきときはいつでも使用されてよい。当該方法は十分に一般的であり、例えば、ＭＤ５、ＳＨＡ及びＨＭＡＣ等の暗号規格で推奨されているものを含め、あらゆる既知の（通例の）ハッシュ関数に適合することができる。より重要なことには、当該方法の安全性は、基礎を成す（通例の）ハッシュ関数の安全性と同じである。
【００３３】
当業者には明らかなように、本発明の好ましい実施形態に従う方法は楕円曲線に限定されない。すなわち、それは、例えば、超楕円曲線又は有限場若しくは有限環の乗法群、あるいはそれらのサブグループ等の、あらゆるグループへ容易に適用され得る。
【００３４】
本明細書並びに（必要に応じて）特許請求の範囲及び図面に開示されている夫々の特徴は、独立して、又は何らかの適切な組合せで、提供されてよい。ハードウェアで実施されるよう記載される特徴は、また、ソフトウェアで実施されてもよく、逆もまた同様である。接続は、適用可能な場合に、無線接続又は有線（必ずしも直接ではない。）若しくは専用の接続として実施されてよい。
【００３５】
特許請求の範囲中に現れる参照符号は、単なる実例としてであり、特許請求の範囲の適用範囲に対する限定効果を有さない。
【符号の説明】
【００３６】
１００  装置
１１０  インターフェース
１２０  プロセッサ
１３０  メモリ
１４０  コンピュータプログラムプロダクト
【図１】
2010191419.tif 000006
【外国語明細書】
2010191419000001.pdf