JP5421361B2 - メッセージに対する署名を生成する方法及び装置並びにそのような署名を検証する方法及び装置 - Google Patents

Description

本発明は、一般的に暗号作成法に関し、より具体的には、ランダムオラクルに頼らないオンライン／オフライン署名方式に関する。

この節は、読者に技術の様々な態様を紹介することを目的としており、以下に記載及び／又は請求される本発明の様々な態様に関連する。この考察は、本発明の様々な態様をより良く理解することを容易にするために、読者に背景知識を提供する上で役立つと思われる。従って、これらの供述は、当然のことながらこの観点から読むべきであり、従来技術の自白として読むべきではない。

オンライン／オフライン署名方式は、電子署名の２段階生成を可能にする。最も費用のかかる計算は、署名に対するメッセージが知られる前に実施されてもよい；これがオフライン段階である。そのメッセージが一度知られると、次に比較的速い計算がオンライン段階で実施される。当業者は、この特性は、例えば電子決済又は自動料金所に向けて運転する場合において望ましく、また、計算リソースの方法では十分に足りない費用の低い装置などの時間制限されたアプリケーションに対して望ましいことを理解するであろう。

非特許文献１において、M.Girault、G.Poupard及びJ.Sternは、GPS法として知られるオンライン／オフライン署名方式を提案している。この方式の欠点は、それのセキュリティ証明が、ランダムオラクルモデルにおいて有効であることである。

標準モデルにおけるオンライン／オフライン署名方式（すなわち、ランダムオラクルに頼らない）は、B.Chevallier-Mames及びM.Joyeによって非特許文献２において提示されている。この方式の欠点は、そのパラメータ、公開キー及び秘密キーのサイズに存在し、その結果生じる署名（オンライン及びオフライン段階の両段階において）のサイズにおいても存在する。さらに、増加したサイズは、計算、保存及び送信において効率が失われる。

標準モデルにおけるもう１つのオンライン／オフライン署名方式は、K.Kurosawa及びK.Schmidt-Samoaによって非特許文献３において提示されている。この方式における欠点は、オンライン段階が、整数乗算よりも費用のかかるモジュラー乗算を含むことである。

さらに、オンライン／オフライン署名方式は、Marc Joye及びHung-Mei Linによって非特許文献４において提示されている。これらの方式は、そのオリジナル及び改良形においてTan-Yi-Siew（TYS）署名方式である。

オリジナルなTYS方式は、第1に、公開キー及び秘密キーを生成する。２つのランダム素数p=2p’+1及びq=2q’+1が選択され、p’及びq’は、素数であり、log₂p’q’＞2l+1である。N=pqである。Z^＊ _Nにおける２つの平方剰余g及びxは、gの位数がp’q’であるように選択される。最後に、ランダムのlビット整数zが選択され、h=g^-ZmodNが計算される。公開キーは、pk={g,h,x,N}であり、秘密キーは、sk={p,q,z}である。mは、署名されるべきメッセージを示す。l-ビット整数k及びl-ビット素数eは、ランダムに選択され、次の値：y=(xg^-k)^1/emodN、c=Ｈ(pk,y,m)及びt=k+cz、が計算される。メッセージmの署名は、その結果、σ＝(t,y,e)である。しかし、著者は、TYS方式が完全に不安定であることを発見し、従って、改良された方式を提供した。

その改良された方式は、４つのセキュリティ・パラメータ、l_N、l_H、l_E及びl_Kを使用し、それらは、l_E≧l_H+2及びl_K≫l_N+l_Hを満たす。改良された方式は、公開キー及び秘密キーを最初に生成する。２つのランダム素数は、p=2p’+1及びq=2q’+1であると選択され、p’及びq’は、N=pqがl_Nの長さを持つように、等しい長さの素数である。Z^＊ _Nにおける２つの平方剰余g及びxは、ランダムに選択される。最後に、h=g^-ZmodNが、ランダム整数z mod p’q’に対して計算される。公開キーは、いまだにpl={g,h,x,N}であり、秘密キーはsk={p.q,z}である。mは、署名されるべきメッセージを示す。l_Kビット整数t及びl_Eビット素数eはランダムに選択され、以下の値：y=(xg^-t)^1/emodN、c=Ｈ(pk,m)及びk=t+cz、が計算される。メッセージmの署名は、その結果、σ＝(k,y,e)である。後で分かるように、変化したのは、主に、いくつかのパラメータの長さであるが、これは、実際にTYS方式が不足しているセキュリティを提供する。しかし、Camenisch-Lysyanskaya署名方式の変形として見なされる、その改良された方式は、いまだにいくらか大量な計算を必要とし、かなり長い署名を供給する。例えば、典型的なパラメータ長である、l_N=1024、l_H＝160、l_E＝162及びl_K=1344は、1024ビットRSA係数に対して1344+1024+162=2530ビットの署名の長さをもたらす。

M.Girault，G.Poupard，and J.Stern"On the Fly Authentication and Signature Schemes Based On Groups of Unkown Order"Jounal of Cryptography，19(4):463-487，2006 B.Chevallier-Mames and M.Joye"A Practical and Tightly Secure Signature Scheme Without Hash Function" M.Abe(editor)，Topics in Cryptography‐CT-RAS 2007，Lecture Notes in Computer Science Vol.4377，pp339-356，Springer-Verlag，2007 M.Yung et al.（editors）"New On-line/Off-line Signature Schemes Without Random Oracles" Public Key Cryptography‐PKC 2006，Lecture Notes in Computer Science Vol．3958，pp330-346，Springer-Verlag，2006 Marc Joye，Hung-Mei Lin"TYS Signature Scheme"

従って、オンライン／オフライン電子署名を供給する改善された解決策に対する必要性があることが分かる。本発明はそのような解決策を提供する。

第１態様において、本発明は、メッセージmに対する署名σを生成する方法に向けられる。y=(xg^-k)^1/e mod Nを満たす３つの整数y、e及びtが得られ、cは、eに依存し、x、g及びNは、公開キーの要素であり、x及びgは、Z^＊ _Nにおける平方剰余であり、Nはl_Nビット整数である；署名σの第1部分kが計算され、kの計算は、m及びl_Zビット整数zの整数乗算及びtの加算を含み；署名σが出力され、署名σは少なくとも３つの値k、y及びeを含む。k、e、z、N、及びhの長さにおいて、hは公開キーの整数の要素であり、それらの長さは、それぞれl_K、l_E、l_Z、l_N、及びl_Hとして示され、cとeとの間の関係を表わす所定の値bに対して以下の関係を満たす：
l_N≧2(l_E+2)；
b(l_E−1)≧l_K+1；及び
l_N−4≧l_K≫l_Z+l_H。

第１に望ましい実施形態において、eは素数でありcはeの正の整数b乗に等しい。このeのb乗を使用することによって、より短い署名が可能になる。

第２に望ましい実施形態において、Nは少なくとも２つの素数p及びqを含むRSA係数である。p=2p’+1及びq=2q’+1であるのは有利であり、p’及びq’は素数である。

第３に望ましい実施形態において、３つの値、y、e、tが素数e及び整数tを生成し；y=(xg^-t)^1/cmodNを計算することによって得られる。

第４に望ましい実施形態において、３つの値、y、e、tが、メモリに保存されたクーポンから得られる。

第５に望ましい実施形態において、メッセージmが、３つの値、y、e、tの取得と署名の第1部分kの計算ステップとの間で受け取られる。

第６に望ましい実施形態において、メッセージmは、署名σとともに出力される。

第２態様において、本発明は、メッセージmに対する署名σを証明する方法に向けられ、その署名は、本発明の第1態様による方法によって生成される。y^cg^kh^m≡x(modN)が検証され、cはeに依存し、hは公開キーの要素である。

第７に望ましい実施形態において、eが奇数であることがさらに検証される。

第１０に望ましい実施形態において、eはl_Eビット整数でありkはl_Kビット整数であることが、さらに検証される。

第３態様において、本発明は、メッセージmに対する署名σを生成する装置に向けられる。該署名装置は、y=(xg^-k)^1/emodNを満たす３つの整数y、e、tを取得するように適合されたプロセッサを含み、cはeに依存し、x、g及びNは公開キーの要素であり、x及びgは、Z^＊ _Nにおける平方剰余であり、Nはl_Nビット整数であり；署名σの第1部分kを計算し、kの計算はm及びl_Zビット整数zの整数乗算及びtの加算を含む。署名装置は、さらに、署名σを出力するように適合された出力ユニットを含み、署名σは、少なくとも３つの値、k、y及びeを含む。k、e、z、N、及びh（hは公開キーの整数要素である）の長さは、それぞれl_K、l_E、l_Z、l_N、及びl_Hとして示され、cとeとの間の関係を表わす所定の値bに対する以下の関係を満たす：
l_N≧2(l_E+2)；
b(l_E−1)≧l_K+1；及び
l_N−4≧l_K≫l_Z+l_H
第４態様において、本発明は、メッセージmに対する署名σを検証するための装置に向けられ、その署名は本発明の第１態様の方法によって生成される。その検証装置は、y^cg^kh^m≡x(modN)であることを検証するように適合され、cはeに依存し、hは公開キーの要素である。

第５態様において、本発明は、プロセッサにおいて実行されるとき、本発明の第１態様のメッセージmに署名する方法を実施するコンピュータプログラムサポート保存インストラクションに向けられる。

第６態様において、本発明は、プロセッサにおいて実行されるとき、本発明の第２態様のメッセージmに対する署名を検証する方法を実施するコンピュータプログラムサポート保存インストラクションに向けられる。

本発明の望ましい特徴が、以下、付属の図表を参照して限定しない例によって説明される。

本発明の望ましい実施形態に従って、メッセージmに対する電子署名を生成し、その電子署名を検証する方法を説明する図である。 本発明の望ましい実施形態に従って、少なくとも１つの電子署名を生成するためのユニットを描く図である。 本発明の望ましい実施形態に従って、メッセージmに対する電子署名を検証するためのユニットを描く図である。

図2及び3において、表わされているブロックは単に機能エンティティであり、それらは物理的に離れているエンティティに必ずしも対応しない。これらの機能エンティティは、ハードウェア、ソフトウェア、又はハードウェアとソフトウェアとの組み合わせとして実施されてもよく；さらに、1つ又はそれ以上の集積回路において実施されてもよい。

上記のように、オンライン／オフライン署名方式は、署名するメッセージの受信の前に実施される（ただし、受信の後にも自然に実施される）オフライン段階及びメッセージmが一度知られると実施されるオンライン段階を有する。メッセージmはより長いメッセージの要約であってもよいことは、当業者にとって当然のことである。

オフライン段階の第1部分はキー生成である。第１に、２つのランダム素数p及びqが生成される；望ましくはp=2p’+1、q=2q’+1であり、p’及びq’は、N=pqがl_Nの長さを持つという条件を満たすように、等しい長さの素数である。次に、２つのランダム平方剰余g及びxがZ^* _Nにおいて選択される。最後にランダムl_Zビット整数に対して、h=g^-ZmodNが計算される。

公開キーpkはその結果{g,h,x,N}であり、秘密キーskは{p,q,z}である。

オフライン段階の第２部分は、署名のオフライン部分の計算である。ランダムl_Kビット整数t及びランダムl_Eビット素数eが選択される。オフライン署名部分yが、次に、

として計算される。bは、署名方式における所定の0よりも大きい整数である。

ここで、該方式は、署名するためにメッセージmの受信の準備が整う；m∈Mであり、Mはメッセージ空間‐M={0,1}^lHを示し、それは範囲[0,2^lH−1]における整数のセットとしても見なされる。署名のオンライン部分kは次に
k=t+mz
として計算され、メッセージmの署名σ＝(k,y,e)である。

送信前に、署名のオンライン部分kはl_Kビット整数であることを検証するのが有利である；そうでなければ、他の値に基づいて他の署名を生成することが望ましい。当該方式の利点は、オンライン段階がハッシュ法無しで実施されてもよいことである。

署名σは、次に検証のために返される；必要な場合、公開キーもまた供給され、さらに、メッセージmもまた供給される。メッセージmにおける署名σ＝(k,y,e)は、以下の場合及びその場合に限り受け入れられる：
1. eは奇数のl_Eビット整数であり、
2. kはl_Kビット整数であり、

である。

該方式において、パラメータl_K、l_E、l_Z、l_N及びl_H（後者は入力メッセージmの最大長をビットで示す）は、以下の関係を所定の値bに対して満たすべきである：
l_N≧2(l_E+2)；
b(l_E−1)≧l_K+1；及び
l_N−4≧l_K≫l_Z+l_H
注目すべきは、値bも可変であり、この場合、それは公開キーpkの一部分であり得るか、又は署名σに含まれ得る。

上記の関係は、ランダムで選択されず、当業者の理解できる範囲内での単なる作業の改良形でもない。なぜならば、当業者がこれらの特定の関係を考え出す理由が無いからである。結局は、TYS方式に関して示されているように、署名方式は微妙であり、それらの改良は簡単に取り組むべきではない。これらの関係は、該方式のセキュリティの証明を可能にし、本発明の発明性の重要な部分であると考えてよい。

模範とともに、典型的な値l_H＝160、l_N＝1024、l_Z＝160、l_K＝380、l_E＝128、及びb=3であり、1024ビットRSA係数に対して1532ビットのみの署名を与える。

図１は、メッセージmの電子署名を生成する方法及びその電子署名を検証する方法を、本発明の望ましい実施形態に従って説明する。フローチャートは、上記の手順を説明する。ステップ110において、公開キーpk及び秘密キーskが生成される。次に、電子署名のオフライン部分yがステップ120において生成される。一度メッセージmがステップ130において受信されると、ステップ140においてオンライン部分kが計算され、完成した電子署名σを生成するために使用される。その電子署名σ及び公開キーは、ステップ150において送信され、電子署名σはステップ160において検証される。

図２は、本発明の望ましい実施形態に従って少なくとも１つの電子署名を生成するためのユニット210を説明する。電子署名ユニット210は、署名するべきメッセージmを受信するように適合された入力ユニット230及び電子署名σを送信するように適合された出力ユニット240を含む。その出力ユニット240は、署名に対して使用された公開キーpkを送信するのに適合されている。出力ユニット240もまた、メッセージmを対応する電子署名σ（及び場合によっては公開キーpk）と一緒に又はそれとは別に送信するように適合されていてもよい。当然のことながら、入力ユニット230及び出力ユニット240は、入力／出力ユニット（非表示）として組み合わされてもよい。

電子署名ユニット210は、受信されたメッセージmに対する電子署名を生成するための計算を実施するように適合された少なくとも１つのプロセッサ220（以下、「プロセッサ」）をさらに含む。そのデジタル保存ユニットは、また、計算に必要なデータを保存するように適合されたメモリ250も含む。

当然のことながら、当業者、電子署名装置210が多数のいわゆるクーポン（すなわち、あらかじめ計算されたオフライン署名部分）を保存することが可能である。そのようなクーポンは、例えば製造中など、電子署名ユニット210の外部のソースによって供給されてもよく、その場合、入力ユニット230（又は他の適切なユニット；非表示）がそのようなクーポンを受信するように適合されていることがさらに分かるであろう。

当業者は、電子署名ユニット210が署名するメッセージmを生成することも可能であることを理解するであろう。この場合、出力ユニット240は、有利にも、メッセージmを送信するようにさらに適合されている。

図２は、また、上記に記載されたように、プロセッサ220において実行される場合、模範的なCD-ROMなどの、メッセージmを署名する方法を実施するインストラクションを保存するコンピュータプログラムサポート260を説明する。

図３は、本発明の望ましい実施形態に従って、メッセージmの電子署名を検証するためのユニット310を説明する。その検証ユニット310は、電子署名σを受信するように適合された入力330及び必要な場合、その署名に使用される公開キーpkを含む。当然のことながら、検証ユニット310は、電子署名ユニットに対応する多数の公開キーを有してもよい。検証ユニット310は、さらに、電子署名σが正確であるか否かの情報を出力するように適合されている。検証ユニット310は、また、署名されるべきメッセージmを送信するためのユニット（出力ユニット340に含まれてもよい）も含んでよい。入力ユニット330は、また、メッセージmを、対応する電子署名σ（及び場合によっては公開キーpk）とともに又はそれとは別に受信するように適合されていてもよい。

検証ユニット310は、さらに、電子署名σを検証するのに必要な計算を実施するように適合された少なくとも１つのプロセッサ320（以下、「プロセッサ」）、及びメッセージm、特にメッセージm自体を検証するために必要なデータを保存するように適合されたメモリ350を含む。

図３は、また、上記に記載されたように、プロセッサ320において実行される場合、模範的なCD-ROMなどの、メッセージmを署名する方法を実施するインストラクションを保存するコンピュータプログラムサポート360を説明する。

当該記載において開示される各特徴及び（適切な箇所において）請求項及び図表は、独立して又は適切な如何なる組み合わせにおいて提供されてもよい。ハードウェアにおいて実施されるとして記載された特徴は、ソフトウェアにおいても実施されてもよく、またその逆の場合でもよい。接続は、該当する場合、無線接続又は有線接続として実施されてもよく、必ずしも直接又は専用の接続でなくてもよい。

当然のことながら、当該記載及び請求項において、「ランダム」という用語は、「ランダム又は疑似ランダム」として解釈されるべきである。

請求項において見られる参照符号は、説明だけを目的としており、請求項の範囲に対して限定する効果は有していないものとする。

Claims (15)

1. 電子署名装置においてメッセージmに対する署名σを生成する方法であって、
   前記電子署名装置のプロセッサにより、y＝(xg^-t)^1/cmodNを満たす３つの整数y、e及びtを取得するステップであり、c=e ^b であり、bは正の整数であり、x、g及びNは公開キーの要素であり、x及びgはZ^* _Nの平方剰余であり、Nはl_Nビットの整数である、ステップと、
   前記電子署名装置の前記プロセッサにより、署名σの第１部分kを計算するステップであり、kの計算は、m及びl_Zビットの整数zの整数乗算及びtの加算を含む、ステップと、
   前記電子署名装置の出力ユニットにより、前記署名σを出力するステップであり、該署名σは少なくとも３つの値、k、y及びeを有する、ステップと、
   を含み、
   k、e、z、N及び前記公開キーの整数要素であるhの長さが、それぞれl_K、l_E、l_Z、l_N、及びl_Hとして示される場合、以下の関係：
   l_N≧2(l_E+2)；
   b(l_E−1)≧l_K+1；及び
   l_N−4≧l_K
   を満たす、方法。
2. l_Kがl_Z+l_Hよりも大きい、請求項１に記載の方法。
3. Nは、少なくとも２つの素数p及びqを含むRSA係数である、請求項１又は２に記載の方法。
4. p=2p’+1及びq=2q’+1であり、p’及びq’は素数である、請求項３に記載の方法。
5. ３つの値y、e及びtを取得するステップは、
   素数e及び整数tを生成するステップと、
   y=(xg^-t)^1/cmodNを計算するステップと、
   を含む請求項１乃至４のいずれか１項に記載の方法。
6. 前記３つの値y、e及びtは、メモリに保存されたクーポンから取得される、請求項１に記載の方法。
7. 前記取得するステップと前記計算するステップとの間に、前記電子署名装置の受信機により、前記メッセージmを受信するステップをさらに含む、請求項１乃至６のいずれか１項に記載の方法。
8. 前記出力するステップが、前記メッセージmを出力するステップをさらに含む、請求項１乃至７のいずれか１項に記載の方法。
9. 電子署名検証装置におけるメッセージmに対する署名σの検証方法であって、
   該署名は請求項１乃至８のいずれか１項に記載の方法によって生成され、
   前記電子署名検証装置の検証ユニットにより、y^cg^kh^m≡x(modN)を検証するステップであり、cはeに依存し、hは前記公開キーの要素である、ステップを含む、検証方法。
10. 前記電子署名検証装置の前記検証ユニットにより、eが奇数であることを検証するステップをさらに含む、請求項９に記載の方法。
11. 前記電子署名検証装置の前記検証ユニットにより、eがl_Eビットの整数でありkはl_Kビットの整数であることを検証するステップをさらに含む、請求項９又は１０に記載の方法。
12. メッセージmに対する署名σを生成する装置であって、
    cがeに依存し、bは正の整数であり、x、g及びNは公開キーの要素であり、x及びgはZ^* _Nの平方剰余であり、Nはl_Nビットの整数である場合、y＝(xg^-t)^1/cmodNを満たす３つの整数y、e及びtを取得し、m及びl_Zビットの整数zの整数乗算及びtの加算を含む、署名σの第１部分kの計算をするように適合されたプロセッサと、
    少なくとも３つの値k、y及びeを含む前記署名σを出力するように適合された出力ユニットと、
    を含み、
    k、e、z、N及び前記公開キーの整数要素であるhの長さは、それぞれl_K、l_E、l_Z、l_N、及びl_Hとして示される場合、以下の関係：
    l_N≧2(l_E+2)；
    b(l_E−1)≧l_K+1；及び
    l_N−4≧l_K
    を満たす、装置。
13. メッセージmに対する署名σを検証する装置であって、
    該署名は請求項１乃至８のいずれか1項に記載の方法によって生成され、
    cがeに依存し、hは前記公開キーの要素である場合、y^cg^kh^m≡x(modN)を検証するように適合されたプロセッサ、を含む装置。
14. プロセッサに対して、請求項１乃至８のいずれか１項に記載のメッセージmに署名する方法を実施させるためのコンピュータプログラム。
15. プロセッサに対して、請求項９乃至１１のいずれか１項に記載のメッセージmに署名を検証する方法を実施させるためのコンピュータプログラム。

Images