JPH11331149A - 公開鍵暗号方法および装置 - Google Patents

Abstract

(57)【要約】 【課題】(1) 回覧者がコメントを付けて署名するよう
な多重ディジタル署名においては、従来の方法だと、N
重ディジタル署名の長さは単一ディジタル署名の長さを
単純にN倍したものになり長さの面で不満足である。 (2) 楕円暗号に関しては、システム鍵Pの位数nの長さ
になるべく依存しないようにディジタル署名を構成でき
ることが望ましい。 【解決手段】メッセージMが与えられたときに、(1) ハ
ッシュ関数Hを用いて、 e＝H(M)を満たすeを求める処
理と、(2) 乱数を変換して得られる数値xに対して、ハ
ッシュ関数Hの出力値よりも短い出力値を出力するよう
なハッシュ関数hを用いて、 r＝h(x)を満たすrを求め
る処理、を含む公開鍵暗号方法によりディジタル署名を
生成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、コンピュータネッ
トワークにおけるセキュリティを確保する技術に関す
る。

【０００２】

【従来の技術】電子的な商取引文書等に従来の印鑑に相
当する機能を付与するディジタル署名は、ネットワーク
の高度利用を可能とする技術として期待されている。従
来、電子メール暗号化技術PEM(Privacy Enhanced Mai
l)等においては電子メール1通当たりただ１つのディジ
タル署名を取り扱うに過ぎなかったが、今後の電子商取
引（エレクトロニックコマース）においては、購入者ば
かりでなく流通業者、販売者、金融関係者他の多数のデ
ィジタル署名が付いた電子文書が取り扱われ、これに対
応した多重ディジタル署名の技術が必要になる。ここ
で、多数のディジタル署名付きの電子文書を渡された人
は、自分のディジタル署名1個を生成する前に他人のデ
ィジタル署名N個の正当性を検証しなければならず、使
い勝手をよくするためにはディジタル署名N個の検証速
度を速くする必要がある。さらに、電子商取引において
は、電子文書の処理過程で複数人によりコメント追記が
なされる可能性がありこれにも対処できる必要がある。
従来、ディジタル署名技術の一例が、J. Koeller, A.
J. Menezes, M.Qu and S. A. Vanstone, Stan
dard for RSA, Diffie-Hellman and Related Pub
lic-Key Cryptography Elliptic Curve Systems
(Draft 8),IEEE P1363 Standard, IEEE, May 3,
1996に開示されている。

【０００３】図10は上記公知例の実施例を示す。図10に
おいて、ネットワーク1001にシステム管理者のコンピュ
ータ1002、ユーザAのコンピュータ1003、および、ユー
ザBのコンピュータ1004が接続され相互に通信されるよ
うになっている。次に図10における各装置の動作を示
す。

【０００４】システムセットアップ システム管理者のコンピュータ1002は、楕円曲線1006を
生成し、E上で位数n1008のシステム鍵P1007を生成する
とともに、それらを公開ファイル1005に掲載しておく。

【０００５】鍵生成 ユーザAのコンピュータ1003内において、鍵生成機能101
1は、次の処理を行う。 ステップ１：区間[2, n-2]の間でランダムに整数d_Aを
選ぶ。 ステップ２：Q_A＝d_APを計算する。 ステップ３：Q_A1015を公開鍵として公開する。つまり、
公開鍵Q_A1015は、ユーザAの識別名とともにネットワー
ク1001経由でシステム管理者のコンピュータ1002に送信
され、そこで、公開ファイル1005内のユーザ名Aの欄100
9にユーザAの識別名が書き込まれるととも に、公開鍵
Q_Aの欄1010に公開鍵Q_A1015の値が書き込まれる。 ステップ４：ユーザAのコンピュータ1003は、秘密鍵d_A1
014の値を該ユーザAの秘密鍵として保持する。

【０００６】ディジタル署名生成 ユーザAのコンピュータ1003内において、ディジタル署
名生成機能1033は次の処理を行う。

【０００７】ステップ１：メッセージM1016を入力す
る。 ステップ２：ハッシュ関数H1028を用いてハッシュ値e＝
H(M)を計算する。 ステップ３：乱数生成関数1029を用いて、区間[2, n-
2]の間で乱数kを選ぶ。 ステップ４：「楕円E上のスカラー倍」1030により、(x,
y)＝k・Pを計算する。 ステップ５：計算「r＝x＋e (mod n) 」1031によ
り、 r＝x＋e (mod ｎ）を計算する。 ステップ６：計算「ｓ＝kーd_Ar (mod n)」1032に秘密
鍵d_A1017を入力して、s＝kーd_Ar (mod n)を計算す
る。 ステップ７：メッセージM1016とディジタル署名(s, r)
1019をネットワーク1001経由でユーザBのコンピュータ1
024宛に送信する。なお、ディジタル署名生成機能1033
内の計算に必要なパラメータとして、システム管理者の
コンピュータ1002内の公開ファイル1005のなかの楕円曲
線1006、システム鍵P1007、および、位数n1008が参照さ
れる。

【０００８】ディジタル署名検証 ユーザBのコンピュータ1004内において、ディジタル署
名検証機能1023は、次の処理を行う。

【０００９】ステップ１：システム管理者のコンピュー
タ1002の公開ファイル1005から、ユーザAの公開鍵Q_A101
0をとってきて、公開鍵Q_A1020とする。また、システム
管理者のコンピュータ1002の公開ファイル1005から、シ
ステム鍵P1007をとってきて、システム鍵P1019とする。
また、ユーザAのコンピュータ1003から送られてきたデ
ィジタル署名(s, r)1019を入力し、ディジタル署名(s,
r)1021とする。また、ユーザAのコンピュータ1003か
ら送られてきたメッセージM1016を入力し、メッセージM
1022とする。 ステップ２：システム鍵P1019と、公開鍵Q_A1020、ディ
ジタル署名(s, r)1021を、「楕円E上のスカラー倍と加
算」1024に入力し、(x, y)＝sP＋rQ_Aの計算を行う。 ステップ３：メッセージM1022をハッシュ関数H1025に入
力し、ハッシュ値e＝H(M)を計算する。 ステップ４：計算「r＝x＋e (mod n) 」1026におい
て、r＝x＋e (mod n)を計算する。 ステップ５：判定「r＝r？ 」1027において、もしr＝r
であった場合、「認証する」を出力する。さもなけれ
ば、「認証せず」を出力する。なお、ディジタル署名検
証機能1023内の計算に必要なパラメータとして、システ
ム管理者のコンピュータ1002内の公開ファイル1005のな
かの楕円曲線1006、システム鍵P1007、および、位数n10
08が参照される。このような処理により、ディジタル署
名(s, r)はメッセージMに対してユーザAが生成した電
子的な捺印として機能する。すなわち、ユーザBはメッ
セージMとディジタル署名(s, r)の組をユーザAが生成
した証拠として保持することができる。さらに、ユーザ
BはメッセージMとディジタル署名(s, r)の組の正当性
を認証できるが、それを最初に生成することはできな
い。このことから、ユーザAは、後になって、ディジタ
ル署名(s, r)を生成したという事実を否定することは
できない。

【００１０】

【発明が解決しようとする課題】しかし、上記公知例に
おいては次の不満足点があった。 (1) ディジタル署名の長さが長い いま、次のように各パラメータのビット長が与えられて
いるとする。 (a) システム鍵Pの位数nを表すビット長：lnビット
（例、160ビット） (c) ハッシュ関数Hの出力を表すビット長：LHビット
（例、160ビット） (d) 秘密鍵d[A]_Aのビット長：LDビット（例、128ビッ
ト） ここで、ハッシュ関数Hの出力長の例である160ビット
は、Hが衝突回避性という特性をもつために必要な長さ
であるとされている。衝突回避性とは、同じ出力値とな
るような異なる二つの入力値を見つけるのが計算量的に
困難である、という意味である。Hの出力値が160ビット
である場合、誕生日のパラドクスというアタック方法に
よって、平均して２⁸⁰回程度の試行で同じ出力値となる
ような異なる二つの入力値を見つけることができるが、
これは計算量的に困難である。また、システム鍵Pの位
数nのビット長の例である160ビットは、楕円曲線上の加
法に関する離散対数問題が実行困難となるために必要な
ビット長を満足するものである。このとき、ディジタル
署名(s, r)のうちsの長さはlnビット、rの長さはlnビ
ットとなり、合計ln＋lnビット（例、320ビット）と長
くなってしまう。これにより、処理時間が長くなった
り、多くの計算機資源を必要として高価格になってしま
う。 (2) ディジタル署名の長さが楕円曲線パラメータであ
る位数nの長さに依存して決まる。このため、将来、安
全性の理由等でnの長さが長くなった場合、ディジタル
署名の長さも長くなる。従来の公開鍵暗号では、年月の
経過とともに解読方法およびコンピュータ性能が発展し
パラメータの長さを長くせざるを得なくなったという経
緯がある。これは、今後の楕円暗号においても同様であ
る可能性がある。つまり、楕円暗号についても、年月の
経過とともに解読方法およびコンピュータ性能が発展し
パラメータnの長さを長くせざるを得なくなると予想さ
れる。システム鍵Pの位数nの長さになるべく依存しない
ようにディジタル署名を構成できることが望ましい。

【００１１】したがって、本発明の目的は、ディジタル
署名の長さが短く、またディジタル署名の長さが楕円曲
線パラメータである位数nの長さに依存しない、ディジ
タル署名に適した公開鍵暗号方法及び、それを用いた装
置を提供することである。

【００１２】

【課題を解決するための手段】上記目的を達成するた
め、本発明ではメッセージMが与えられたときに、それ
に押印したことを電子的に認証するためのディジタル署
名を生成、あるいは、検証する方法であって、(1)ハッ
シュ関数Hを用いて、 e＝H(M)を満たすeを求める処理
と、(2)乱数を変換して得られる数値xに対して、ハッシ
ュ関数Hの出力値よりも短い出力値を出力するようなハ
ッシュ関数hを用いて、 r＝h(x)を満たすrを求める処
理、を含むことを特徴とする。

【００１３】さらに具体的にはN人のユーザi(i＝1, ・・
・, N)がそれぞれメッセージあるいはコメントM[i]を付
け加えて順番に押印したことを電子的に認証するための
多重ディジタル署名を生成、あるいは、検証する方法で
あって、(1)ハッシュ関数Hを用いて、e[i]＝H(M[i])を
計算する処理と、(2)乱数を変換して得られる数値x[i]
に対して、ハッシュ関数Hの出力値よりも短い出力値を
出力するようなハッシュ関数hを用いて、 r[i]＝h(x
[i])を満たすr[i]を求める処理、をi＝1からNまでの各i
について行うことを含むことを特徴とする。

【００１４】さらに具体的にはメッセージM[1]が与えら
れたきに、楕円曲線上で定義される加算を用いて、ディ
ジタル署名(s[1], r[1])を生成する方法であって、(1)
ハッシュ関数Hを用いて、 e[1]＝H(M[1])を満たすeを
求め、(2)乱数k[1]を生成し、(3)楕円曲線上のシステム
鍵Pをk[1]倍した点、すなわち、(x[1], y[1])＝k[1]・P
を満たす点(x[1], y[1])を求め、(4)ハッシュ関数Hの
出力値よりも短い出力値を出力するようなハッシュ関数
hを用いて、 r[1]＝h(x[1])を満たすr[1]を求め、(5)
楕円曲線上のシステム鍵Pの位数n、および、秘密鍵d
[1]を使って、s[1]＝k[1]＋d[1](e[1]＋r[1]) (mod
n)を満たすs[1]を求め、(6) 得られた数値の組(s[1],
r[1])をディジタル署名として出力する、ことを特徴
とする。

【００１５】さらに具体的にはメッセージM[1]とディジ
タル署名(s[1], r[1])が与えられたときに、それらの
検証を行う方法であって、(1)ハッシュ値e[1]＝H(M[1])
を計算し、(2)Q[1]＝d[1]・ Pを満足するように予め
生成され登録された公開鍵Q[1]を入力し、(3)楕円曲線
上の点、(x[1], y[1])＝s[1]・ P−(e[1]＋r[1])・ Q
[1]を計算し、(4)ハッシュ関数Hの出力値よりも短い出
力値を出力するようなハッシュ関数hを用いてr[1]＝h(x
[1])を計算し、(5)もし、 r₁＝r₁なら、認証された由
を示すデータを出力し、(6)もし、 r₁≠r₁なら、認証
されなかった由を示すデータを出力する、ことを特徴と
する。

【００１６】さらに具体的にはN人のユーザi(i＝1, ・・
・, N)がそれぞれメッセージあるいはコメントM[1]を付
け加えて順番に押印したことを電子的に認証するための
多重ディジタル署名を認証する方法であって、ユーザi
(i≧3)は、(1)i−1個のメッセージあるいはコメントM
[1], ・・・ , M[i-1]、および、一つ前の順番のユーザ
i−1が生成した(i−1)重ディジタル署名(r[i-1], s
[1], ・・・ , s[i-1])を入力し、k=i-1について(2)ハ
ッシュ値e[k]＝H(M[k])を計算し、(3)Q[k]＝d[k]・ Pを
満足するように予め生成され登録された公開鍵Q[k]を入
力し、(4)楕円曲線上の点、(x[k], y[k]) ＝s[k]・ P
− (e[k]＋ r[k])・ Q[k]を計算し、(5)ハッシュ関数
Hの出力値よりも短い出力値を出力するようなハッシュ
関数hを用いたスカラ演算によりr[k-1]＝r[k](+)h(x[k]
||s[k-1]||s[k-2]||...||s[1])を計算し、(6)さらにハ
ッシュ値e[k-1]=H(M[k-1])を計算し、(7)Q[k-1]=d[k-1]
・ Pを満足するように予め生成され登録された公開鍵Q
[k-1]を入力し、(8)楕円曲線上の点、(x[k-1], y[k-
1])=s[k-1]・ P- (e[k-1]+ r[k-1])・Q[k-1]を計算
し、(9)ハッシュ関数Hの出力値よりも短い出力値を出力
するようなハッシュ関数hを用いてr[k-1]=h(x[k-1])を
計算し、(10)もし、r[k-1]≠r[k-1]なら、認証されなか
った由を示すデータを出力し、(11)もし、r[k-1]＝r[k-
1]かつk=2なら、認証された由を示すデータを出力し、
(12)(10)、(11)以外の場合なら生成されたr[k-1]をr[k-
1]として、k:=k-1について(2)項から行うことを特徴と
する。

【００１７】さらに具体的にはN人のユーザi(i＝1, ・・
・, N)がそれぞれメッセージあるいはコメントM[i]を付
け加えて順番に押印したことを電子的に認証するための
多重ディジタル署名を生成する方法であって、ユーザi
(i≧2)は、(1)前記の(x[i-1], y[i-1])を入力し、(2)
ハッシュ値e[i]=H(M[i])を計算し、(3)乱数k[i]を生成
し、(4)楕円曲線上の点、(x[i], y[i])=k[i]・ Pを計
算し、(5)ハッシュ関数Hの出力値よりも短い出力値を出
力するようなハッシュ関数hを用いてr[i]=r[i-1] (+)h
(x[i]||s[i-1])を計算し、(6)ユーザiの秘密鍵d[i]を用
いてs[i]=k[i]+d[i](e[i]+r[i])を計算し、(7)得られた
数値の組(r[i],s[1], ... ,s[i])をディジタル署名と
して出力することを特徴とする。

【００１８】

【発明の実施の形態】図1は本発明の第一の実施例を示
す図であり、ネットワーク101にAのパソコン102、およ
び、Bのパソコン103、Cのパソコン104が接続されてい
る。これらのパソコンは図12に示すような構成となって
おり、以下の処理を実現するものである。なお、以下説
明する署名作成や検証のための各アルゴリズムは、パソ
コン1201内のCPU1202がディスク1203やメモリ1204に保
存されているプログラムをメモリ1204に記憶されている
秘密鍵1205などのデータを用いながら実行することで、
実行される。またこれらのディスクに保存されるプログ
ラム1206はFDやCD-ROMなどの記憶媒体1207によりドライ
ブ1208を通じてロードされるか、またはネットワーク12
09を通じてダウンロードされるものである。Aのパソコ
ン102では、単一ディジタル署名生成アルゴリズムAL[1]
105、システム鍵P117、Aの秘密鍵d[1]118により、Aの作
成文書M[1]110に対するA氏署名(s[1], r[1])111が作成
され、ネットワーク101経由でBのパソコン103に送信さ
れる。Bのパソコン103では単一ディジタル署名検証アル
ゴリズムAL[1]106、システム鍵P119、Aの公開鍵Q[1]120
によりA氏作成文書M[1]110とA氏署名(s[1], r[1])111
の組としての正当性を検証する。この署名が正しく認証
されれば、二重ディジタル署名生成アルゴリズムAL[2]1
07、システム鍵P119、秘密鍵d[2]121を用いてA氏作成文
書M[1]115 、A氏署名(s[1], r[1])111、B氏追加文書M
[2]114に対するA氏、B氏の二重ディジタル署名(r[2],
s[1], s[2])113が作成され、ネットワーク101経由でC
のパソコン104に送信される。Cのパソコン104では二重
ディジタル署名検証アルゴリズムAL[2]108、システム鍵
P122、Aの公開鍵Q[1]123、Bの公開鍵Q[2]124を用いて、
A氏作成文書M[1]115、B氏追加文書M[2]114とA氏、B氏の
二重ディジタル署名(r [2], s[1], s[2])113の組と
しての正当性が検証される。

【００１９】図2は、図1における単一ディジタル署名生
成アルゴリズムAL[1]105の処理フローを示す。以下各処
理中において楕円曲線上におけるスカラー倍計算を演算
子・で示し、2つのバイナリデータ間のビット毎の排他
的論理和演算を(+)で示す。単一ディジタル署名生成アルゴリズムAL[1] ステップ201：はじめ ステップ202：A氏作成文書M[1]110、秘密鍵d[1]118、シ
ステム鍵P117を入力する。 ステップ203：LHビットの乱数k[1]を生成する。 ステップ204：(x[1], y[1])＝k[1]・ Pを計算する。 ステップ205：LH/2ビットのハッシュ値r[1]＝h(x[1])
を計算する。 ステップ206：LHビットのハッシュ値e[1]＝H(M[1]) を
計算する。 ステップ207：s[1]＝k[1]＋d[1](e[1]＋r[1]) (mod
n)を計算する。 ステップ208：単一ディジタル署名(s[1],r[1])111の値
を出力する。 ステップ209：おわり この処理によって生成される単一ディジタル署名(s[1],
r[1])は、A氏がメッセージM[1]に押印して得られる印
影に相当する。つまり、メッセージM[1]が与えられたと
き、A氏だけが保管する印鑑相当の秘密鍵d[1]を使用し
た場合にのみ、単一ディジタル署名(s[1], r[1])は生
成される。ここで楕円曲線のパラメータである位数nの
長さを160ビット、全ハッシュ関数Hの出力値の長さを16
0ビット、半ハッシュ関数の出力値の長さを80ビットと
すると、従来方式による単一ディジタル署名の長さは32
0ビットとなるのに対して、本実施例では、240ビットと
なる。図3は、図1における単一ディジタル署名検証アル
ゴリズムAL[1]106の処理フローを示す。

【００２０】単一ディジタル署名検証アルゴリズムAL
[1] ステップ301：はじめ ステップ302：A氏作成文書M[1]110、単一ディジタル署
名(s[1], r[1])111を入力する。 ステップ303：システム鍵P119、公開鍵Q[1]120を入力す
る。 ステップ304：LHビットのハッシュ値e[1]＝H(M[1]) を
計算する。 ステップ305：(x[1],y[1])＝s[1]・ P - (e[1]＋r[1]
(mod n))・ Q[1]を計算する。 ステップ306：LH/2ビットのハッシュ値r[1]＝h(x[1])を
計算する。 ステップ307：もしr[1]＝r[1]なら、ステップ308に進
む。さもなければ、ステップ309に進む。 ステップ308：「認証する」を出力し、ステップ310に進
む。 ステップ309：「認証せず」を出力する。 ステップ310：おわり この処理では、単一ディジタル署名(s[1],r[1])は正し
い印影であるかどうかを確認することに相当する処理を
行う。つまり、メッセージM[1]と単一ディジタル署名(s
[1], r[1])を受け取ったB氏は、印鑑登録票に相当する
公開鍵Q[1]を参照することで、その正当性を確認する。
ここで、B氏はA氏の印鑑に相当する秘密鍵d[1]を知るこ
となしに確認ができていることに注意する。

【００２１】図4は、図1における二重ディジタル署名生
成アルゴリズムAL[2]107の処理フローを示す。ここで現
れる追加文書とは、もとの文書への追加、削除、訂正、
コメントなどを施した新たな文書、またはもとの文書と
の差分を示す文書を示すものである。二重ディジタル署名生成アルゴリズムAL[2] ステップ401：はじめ ステップ402：B氏追加文書M[2]114、システム鍵P119、
および、秘密鍵d[2]121を入力する。 ステップ403：A氏のメッセージM[1]に対する認証された
単一ディジタル署名(r[1],s[1])を入力する。 ステップ404：LHビットの乱数k[2]を生成する。 ステップ405：(x[2],y[2])＝k[2]・ Pを計算する。 ステップ406：r[2]=r[1](+)h(x[2]||s[1])を計算する。 ステップ407：LHビットのハッシュ値e[2]＝H(M[2])を計
算する。 ステップ408：s[2]＝k[2]＋d[2](e[2]＋r[2]) (mod
n)を計算する。 ステップ409：二重ディジタル署名(r[2],s[1],s[2])113
の値を出力する。 ステップ410：おわり この処理によって生成される二重ディジタル署名(r[2],
s[1],s[2])は、A氏が生成した単一ディジタル署名(s
[1], r[1])付きメッセージM[1]にB氏がコメントM[2]を
付け加えたうえで書類全体に押印して得られる印影に相
当する。つまり、他人の単一ディジタル署名(s[1], r
[1])付きメッセージM[1]が与えられ、かつ、本人が書き
加えたいコメントM[2]があったとき、B氏だけが保管す
る印鑑相当の秘密鍵d[2]を使用した場合にのみ、それら
書類全体に押印したことを示す二重ディジタル署名(r
[2],s[1],s[2])が生成される。この二重署名では以前の
署名に検証のため必要であったデータr[1]は二重署名に
は必要ない。ここで楕円曲線のパラメータである位数n
の長さを160ビット、全ハッシュ関数Hの出力値の長さを
160ビット、半ハッシュ関数の出力値の長さを80ビット
とすると、従来方式による二重ディジタル署名の長さは
640ビットとなるのに対して、本実施例では、400ビット
となる。

【００２２】図5は、図1の二重ディジタル署名検証アル
ゴリズムAL[2]108の処理フローを示す。二重ディジタル署名検証アルゴリズムAL[2] ステップ501：はじめ ステップ502：A氏作成文書M[1]115、B氏追加文書M[2]11
4、および、二重ディジタル署名(r[2],r[1],r[2]) 113
を入力する。 ステップ503：システム鍵P122、公開鍵Q[1]123、およ
び、公開鍵Q[2]124を入力する。 ステップ504：LHビットのハッシュ値e[2]＝H(M[2])を計
算する。 ステップ505：(x[2],y[2])＝s[2]・ P-(e[2]＋r[2])Q
[2]を計算する。 ステップ506：r[1]＝r[2](+)h(x[2]||s[1])を計算す
る。 ステップ507：LHビットのハッシュ値e[1]＝H(M[1])を計
算する。 ステップ508：(x[1],y[1])＝s[1]・ P-(e[1]＋r[1])Q
[1]を計算する。 ステップ509：LH/2ビットのハッシュ値r[1]＝h(x[1])を
計算する。 ステップ510：もしr[1]＝r[1]ならば、ステップ511に進
む。さもなければ、ステップ512に進む。 ステップ511：「認証する」を出力し、ステップ513に進
む。 ステップ512：「認証せず」を出力する。 ステップ513：おわり この処理では、二重ディジタル署名(r[2],s[1],s[2])は
正しい印影であるかどうかを確認することに相当する処
理を行う。つまり、メッセージM[1]、メッセージM[2]と
二重ディジタル署名(r[2],s[1],s[2])を受け取ったC氏
は、印鑑登録票に相当する公開鍵Q[1]、Q[2]を参照する
ことで、その署名は正にA氏、および、B氏によってなさ
れたものであることを確認する。ここで、C氏はA氏の印
鑑に相当する秘密鍵d[1]、および、B氏の印鑑に相当す
る秘密鍵d[2]のいずれをも知ることなしに確認ができて
いることに注意する。

【００２３】次に他の実施例を説明する。上記実施例で
は、２つの秘密鍵d[1]、d[2]を作用させて生成される二
重ディジタル署名の実施例を示した。ここで示す方法
は、一般にN個の秘密鍵d[1],d[2],... ,d[N]を作用さ
せて生成されるN重ディジタル署名に拡張したものであ
る。

【００２４】図６は、N＝3とした場合の拡張の例を示し
ている。図６においては、ネットワーク101には、Aのパ
ソコン102、Bのパソコン103、Cのパソコン104に加え、
新たにDのパソコン606が接続されている。またDのパソ
コンも第1の実施例と同様に図12のような構成をしてお
り、以下のアルゴリズムは、ディスクやメモリに保存さ
れたプログラムがCPUによって実行されることで、実行
される。さらにCのパソコン104には、二重ディジタル署
名検証アルゴリズムAL[2]108、システム鍵P122、公開鍵
Q[1]123、公開鍵Q[2]124に加え、新たに三重ディジタル
署名生成アルゴリズムAL[3]604、秘密鍵d[3]605が設定
されている。Cのパソコン104は、Cの作成文書601を生
成、多重ディジタル署名し、Dのパソコン606に送信す
る。Cの署名付き作成文書601はA氏作成文書613、B氏追
加文書614と、新たにC氏追加文書603、A氏、B氏、C氏に
よる多重ディジタル署名602が追加されている。Dのパソ
コン606には、三重ディジタル署名検証アルゴリズムAL
[3]607、システム鍵P608、公開鍵Q[1]609、公開鍵Q[2]6
10、公開鍵Q[3]611が設定されている。

【００２５】図７は、図６におけるCのパソコン104の三
重ディジタル署名生成アルゴリズムAL[3]604の処理フロ
ーを示す。三重ディジタル署名生成アルゴリズムAL[3] ステップ701：はじめ ステップ702：C氏追加文書M[3]603、秘密鍵d[3]605、シ
ステム鍵P122、A氏、B氏による二重ディジタル署名(r
[2],s[1],s[2])を入力する。 ステップ703：LHビットの乱数k[3]を生成する。 ステップ704：(x[3],y[3])＝k[3]・ Pを計算する。 ステップ705：r[3]＝r[2](+)h(x[3]||s[1]||s[2]) を
計算する。 ステップ706：LHビットのハッシュ値e[3]＝H(M[3]) を
計算する。 ステップ707：s[3]＝k[3]＋d[3](e[3]＋r[3]) (mod
n)を計算する。 ステップ708：三重ディジタル署名(r[3],s[1],s[2],s
[3])113の値を出力する。 ステップ709：おわり この処理によって生成される三重ディジタル署名(r[3],
s[1],s[2],s[3])は、A氏、B氏の二重ディジタル署名(r
[2],s[1],s[2])付きメッセージM[1],M[2]にC氏がコメン
トM[3]を付け加えたうえで書類全体に押印して得られる
印影に相当する。つまり、他人の二重ディジタル署名(r
[2],s[1],s[2])付きメッセージM[1],M[2]が与えられ、
かつ、本人が書き加えたいコメントM[3]があったとき、
C氏だけが保管する印鑑相当の秘密鍵d[3]を使用した場
合にのみ、それら書類全体に押印したことを示す三重デ
ィジタル署名(r[3],s[1],s[2],s[3])が生成される。ま
た、ここで楕円曲線のパラメータである位数nの長さを1
60ビット、全ハッシュ関数Hの出力値の長さを160ビッ
ト、半ハッシュ関数の出力値の長さを80ビットとする
と、従来方式による三重署名の長さは960ビットとなる
のに対して、本実施例では、560ビットとなる。

【００２６】図8は、図6におけるD氏のパソコン606の三
重ディジタル署名検証アルゴリズムAL[3]607の処理を示
す。二重ディジタル署名検証アルゴリズムAL[3] ステップ801：はじめ ステップ802： A氏作成文書M[1]613、B氏追加文書M[2]
614、 C氏追加文書M[3]603、および、三重ディジタル
署名(r[3],s[1],s[2],s[3])602を入力する。 ステップ803：システム鍵P608、公開鍵Q[1]609、公開鍵
Q[2]610、および、公開鍵Q[3]611を入力する。 ステップ804：LHビットのハッシュ値e[3]＝H(M[3])を計
算する。 ステップ805：(x[3],y[3])＝s[3]・ P-(e[3]＋r[3])Q
[3]を計算する。 ステップ806：r[2]＝r[3](+)h(x[3]||s[1]||s[2])を計
算する。 ステップ807：LHビットのハッシュ値e[2]＝H(M[2])を計
算する。 ステップ808：(x[2],y[2])＝s[2]・ P-(e[2]＋r[2])Q
[2]を計算する。 ステップ809：LH/2ビットのハッシュ値r[2]＝h(x[2])を
計算する。 ステップ810：もしr[2]＝r[2]ならば、ステップ811に進
む。さもなければ、ステップ812に進む。 ステップ811： r[2]=r[2]としてAL[2]のステップ505に
進む。 ステップ812：「認証せず」を出力する。 ステップ813：おわり この処理では、三重ディジタル署名(r[3],s[1],s[2],s
[3])が正しい印影であるかどうかを確認することに相当
する処理を行う。つまり、メッセージM[1]、メッセージ
M[2]、メッセージM[3]と三重ディジタル署名(r[3],s
[1],s[2],s[3])を受け取ったD氏は、印鑑登録票に相当
する公開鍵Q[1],Q[2]_,Q[3]を参照することで、その署名
は正にA氏、 B氏、および、C氏によってなされたもの
であることを確認する。ここで、D氏はA氏の印鑑に相当
する秘密鍵d[1]、B氏の印鑑に相当する秘密鍵d[2]、お
よび、C氏の印鑑に相当する秘密鍵d[2]のいずれをも知
ることなしで確認ができていることに注意する。

【００２７】同様に、N＝4以上の場合についても、この
方法を拡張することができる。つまり、一般に、N人の
ユーザi(i＝1, ・・・, N)がそれぞれメッセージあるい
はコメントM[i]を付け加えて順番に押印したことを電子
的に認証するための多重ディジタル署名を認証する方法
として、次のようにしてもよい。

【００２８】ユーザi(3≦i≦N)による(i-1)重ディジタ
ル署名の検証手順 ステップ901：はじめ ステップ902：i-1個のメッセージあるいはコメントM
[1],・・・,M[i-1]、および、一つ前の順番のユーザi-1が
生成した(i-1)重ディジタル署名(r[i-1],s[1],...,s[i-
1])を入力する。 ステップ903：j=1からi-1について、Q[j]=d[j]・Pとなる
ように予め生成され登録された公開鍵Q[j]を入力する。 ステップ904：j=1からi-1について、各々がLHビット長
のハッシュ値e[j]=H(M[j])を計算する。 ステップ905：k=i-1とする。 ステップ906：楕円曲線上の点、(x[k],y[k])=s[k]・ P-
(e[k]+r[k])・ Q[k]を計算する。 ステップ907：r[k-1]=r[k] (+)h(x[k]||s[1]||s[2]|
|...||s[k-1])を計算する。 ステップ908：さらに楕円曲線上の点、(x[k-1],y[k-1])
=s[k-1]・ P-(e[k-1],r[k-1])・ Q[k]を計算する。 ステップ909：r[k-1]=h(x[k-1])を計算する。 ステップ910：もし、r[k-1]≠r[k-1]なら、認証せず、
を出力し、ステップ913へ進む。 ステップ911：もし、r[k-1]=r[k-1]かつk≠3なら、r[k-
1]=r[k-1]とし、k:=k-1として ステップ906へ進む。 ステップ912：これら以外の場合、認証、を出力しステ
ップ913へ進む。 ステップ913：おわり また、N人のユーザi(i＝1,..., N)がそれぞれメッセー
ジあるいはコメントM[i]を付け加えて順番に押印したこ
とを電子的に認証するための多重ディジタル署名を生成
する方法として、次のようにしてもよい。ユーザi(2≦i≦N)による多重ディジタル署名の生成手順 ステップ1001：はじめ ステップ1002：ユーザiの追加文書M[i]、秘密鍵d[i]、
システム鍵P、ユーザi-1までのi-1重ディジタル署名(r
[i-1],s[1],...,s[i-1])を入力する。 ステップ1003：LHビットの乱数k[i]を生成する。 ステップ1004：(x[i],y[i])＝k[i]・ Pを計算する。 ステップ1005：r[i]＝r[i-1](+)h(x[i]||s[1]||...||s
[i-1]) を計算する。 ステップ1006：LHビットのハッシュ値e[i]＝H(M[i])
を計算する。 ステップ1007：s[i]＝k[i]＋d[i](e[i]＋r[i]) (mod
n)を計算する。 ステップ1008：多重ディジタル署名(r[i],s[1],...,s
[i])113の値を出力する。 ステップ1009：おわり いま、一般に、N重ディジタル署名を行う場合、従来方
式では署名長が320×Nビットになるのに対して、本実施
例では、署名長は80＋160×Nビットとなる。Nが大きい
場合、本実施例による署名長は従来方式によるものに比
べて約1/2となり、ディジタル署名の長さが大幅に削減
される。

【００２９】さらに他の実施例を説明する。上記実施例
では、楕円曲線上で定義される加算を利用した多重ディ
ジタル署名の実施例を示したが、一般にアーベル群上で
定義されるニ項演算を利用して同様に多重ディジタル署
名を実現してもよい。例えば、nを1,000ビット程度の大
きな素数として、1からn-1までの整数の集合Z_nにおい
て、法nのもとでの乗算を定義するとZ_nはアーベル群を
なす。システム鍵P(1＜P＜n)を適当に選び、秘密鍵dと
公開鍵Qの間には、 Q＝P^d (mod n) ………………………………………………………………(1) の関係式が成立するようにしておく。(1)において、Q、
P、 nが与えられたときdを求める問題は離散対数問
題と呼ばれ、nが大きいとき、その問題を解くことは計
算量的に困難となる。

【００３０】このようにしておくと、例えば、第一の実
施例の単一ディジタル署名生成アルゴリズムAL[1]は次
のように変形される。単一ディジタル署名生成アルゴリズムAL[1] ステップ201：はじめ ステップ202：A氏作成文書M[1] 、秘密鍵d[1]、システ
ム鍵Pを入力する。 ステップ203：LHビットの乱数k[1]を生成する。 ステップ204：x₁＝P^k1を計算する。 ステップ205：LH/2ビットのハッシュ値r[1]＝h(x[1])
を計算する。 ステップ206：LHビットのハッシュ値e[1]＝H(M[1]) を
計算する。 ステップ207：s[1]＝k[1]＋d[1](e[1]＋r[1]) (mod
n)を計算する。 ステップ208：単一ディジタル署名(s[1],r[1])の値を出
力する。 ステップ209：おわり このように変形して得られる単一ディジタル署名(s[1],
r[1])は第一の実施例と同様の効果をもたらす。多重デ
ィジタル署名についても同様の変形をして、同様の効果
を得ることできる。

【００３１】なお、上記各実施例における文書とは、デ
ィジタル化されたマルチメディアデータであれば、音
声、静止画像、動画像、写真、さらにそれらが合わさっ
たものなどでもよい。

【００３２】

【発明の効果】以上説明したように、本発明により、 (1)ディジタル署名の長さを短くできる。これにより、
多重ディジタル署名を用いても、高速処理を実現するこ
とが可能になる。また、小さな計算機資源でのシステム
構築が可能となりより安価なシステムを供給することが
できる。

【００３３】(2)ディジタル署名の長さを位数nの長さに
依存しないようにできる。全ハッシュ関数Hの出力の長
さは、乱数kの長さよりも十分長いとすれば、署名のう
ち、s列の長さは[全ハッシュ関数Hの出力の長さ]＋[秘
密鍵dの長さ]以下に抑えることができる。よって、位数
nの長さとは無関係にN重ディジタル署名の長さは、[半
ハッシュ関数Hの出力の長さ]＋d＋N×[全ハッシュ関数h
の出力の長さ]、以下にすることができる。

【図面の簡単な説明】

【図１】本発明の第一の実施例を示すシステム構成例。

【図２】図１のシステム構成のうちAのパソコンの単一
署名生成処理フロー。

【図３】図１のシステム構成のうちBのパソコンの単一
署名検証処理フロー。

【図４】図１のシステム構成のうちBのパソコンの二重
署名生成処理フロー。

【図５】図１のシステム構成のうちCのパソコンの二重
署名検証処理フロー。

【図６】本発明の第二の実施例を示すシステム構成例。

【図７】図６のシステム構成のうちCのパソコンの三重
署名生成処理フロー。

【図８】図６のシステム構成のうちDのパソコンの三重
署名検証処理フロー。

【図９】一般にユーザーiによる(i-1)重多重署名検証処
理フロー。

【図１０】一般にユーザーiによる(i-1)重多重署名生成
処理フロー。

【図１１】従来例を示す図。

【図１２】各実施例中のパソコンの構成図。

【符号の説明】

ネットワーク101、Aのパソコン102、Bのパソコン103、C
のパソコン104、システム鍵P117、 Aの公開鍵Q₁120、B
の公開鍵Q₂123、 Aの秘密鍵d₁118、 Bの秘密鍵d₂12
1、単一ディジタル署名生成アルゴリズムAL₁105、単一
ディジタル署名検証アルゴリズムAL₁107、二重ディジタ
ル署名生成アルゴリズムAL₂106、二重ディジタル署名検
証アルゴリズムAL₂108、 Aの作成文書M₁110、A氏署名
(s₁, r₁)111、B氏追加箇所M₂114、A氏、B氏署名(s₂,
r₁, ｒ_２）１１３

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号 ＦＩ Ｈ０４Ｌ 9/00 ６７３Ｄ

Claims (6)

【特許請求の範囲】
1. 【請求項１】メッセージMが与えられたときに、それに
   押印したことを電子的に認証するためのディジタル署名
   を生成、あるいは、検証する方法であって、 (1)ハッシュ関数Hを用いて、 e＝H(M)を満たすeを求め
   る処理と、 (2)乱数を変換して得られる数値xに対して、ハッシュ関
   数Hの出力値よりも短い出力値を出力するようなハッシ
   ュ関数hを用いて、 r＝h(x)を満たすrを求める処理、 を含むことを特徴とする公開鍵暗号方法および装置。
2. 【請求項２】N人のユーザi(i＝1, ・・・, N)がそれぞれ
   メッセージあるいはコメントM[i]を付け加えて順番に押
   印したことを電子的に認証するための多重ディジタル署
   名を生成、あるいは、検証する方法であって、 (1)ハッシュ関数Hを用いて、e[i]＝H(M[i])を計算する
   処理と、 (2)乱数を変換して得られる数値x[i]に対して、ハッシ
   ュ関数Hの出力値よりも短い出力値を出力するようなハ
   ッシュ関数hを用いて、 r[i]＝h(x[i])を満たすr[i]を
   求める処理、 をi＝1からNまでの各iについて行うことを含むことを特
   徴とする請求項１記載の公開鍵暗号方法および装置。
3. 【請求項３】メッセージM[1]が与えられたきに、楕円曲
   線上で定義される加算を用いて、ディジタル署名(s[1],
   r[1])を生成する方法であって、 (1)ハッシュ関数Hを用いて、 e[1]＝H(M[1])を満たすe
   を求め、 (2)乱数k[1]を生成し、 (3)楕円曲線上のシステム鍵Pをk[1]倍した点、すなわ
   ち、(x[1], y[1])＝k[1]・Pを満たす点(x[1], y[1])を
   求め、 (4)ハッシュ関数Hの出力値よりも短い出力値を出力する
   ようなハッシュ関数ｈを用いて、 ｒ［１］＝h(x[1])
   を満たすr[1]を求め、 (5) 楕円曲線上のシステム鍵Pの位数n、および、秘密
   鍵d[1]を使って、s[1]＝k[1]＋d[1](e[1]＋r[1]) (mod
   n)を満たすs[1]を求め、 (6) 得られた数値の組(s[1], r[1])をディジタル署名
   として出力する、 ことを特徴とする請求項１記載の公開鍵暗号方法および
   装置。
4. 【請求項４】メッセージM[1]とディジタル署名(s[1],
   r[1])が与えられたときに、それらの検証を行う方法で
   あって、 (1)ハッシュ値e[1]＝H(M[1]) を計算し、 (2)値よりも短い出力値を出力するようなハッシュ関数h
   を用いてr[1]＝h(x[1])を計算し、 (3)もし、 r₁＝r₁なら、認証された由を示すデータを
   出力し、 (4)もし、 r₁≠r₁なら、認証されなかった由を示すデ
   ータを出力する、 ことを特徴とする請求項１記載の公開鍵暗号方法および
   装置。
5. 【請求項５】N人のユーザi(i＝1, ・・・, N)がそれぞれ
   メッセージあるいはコメントM[1]を付け加えて順番に押
   印したことを電子的に認証するための多重ディジタル署
   名を認証する方法であって、 ユーザi(i≧3)は、 (1)i−1個のメッセージあるいはコメントM[1], ・・・ ,
   M[i-1]、および、一つ前の順番のユーザi−1が生成し
   た(i−1)重ディジタル署名(r[i-1], s[1], ・・・ , s
   [i-1])を入力し、k=i-1について (2)ハッシュ値e[k]＝H(M[k])を計算し、 (3)Q[k]＝d[k]・ Pを満足するように予め生成され登録
   された公開鍵Q[k]を入力し、 (4)楕円曲線上の点、(x[k], y[k]) ＝s[k]・ P− (e
   [k]＋ r[k])・ Q[k]を計算し、 (5)ハッシュ関数Hの出力値よりも短い出力値を出力する
   ようなハッシュ関数hを用いたスカラ演算によりr[k-1]
   ＝r[k](+)h(x[k]||s[k-1]||s[k-2]||...||s[1])を計算
   し、 (6)さらにハッシュ値e[k-1]=H(M[k-1])を計算し、 (7)Q[k-1]=d[k-1]・ Pを満足するように予め生成され登
   録された公開鍵Q[k-1]を入力し、 (8)楕円曲線上の点、(x[k-1], y[k-1])=s[k-1]・ P-
   (e[k-1]+ r[k-1])・Q[k-1]を計算し、 (9)ハッシュ関数Hの出力値よりも短い出力値を出力する
   ようなハッシュ関数hを用いてr[k-1]=h(x[k-1])を計算
   し、 (10)もし、r[k-1]≠r[k-1]なら、認証されなかった由を
   示すデータを出力し、 (11)もし、r[k-1]＝r[k-1]かつk=2なら、認証された由
   を示すデータを出力し、 (12)(10)、(11)以外の場合なら生成されたr[k-1]をr[k-
   1]として、k:=k-1について(2)項から行うことを特徴と
   する請求項２記載の公開鍵暗号方法および装置。
6. 【請求項６】N人のユーザi(i＝1, ・・・, N)がそれぞれ
   メッセージあるいはコメントM[i]を付け加えて順番に押
   印したことを電子的に認証するための多重ディジタル署
   名を生成する方法であって、 ユーザi(i≧2)は、 (1)前記の(x[i-1], y[i-1])を入力し、 (2)ハッシュ値e[i]=H(M[i])を計算し、 (3)乱数k[i]を生成し、 (4)楕円曲線上の点、(x[i], y[i])=k[i]・ Pを計算
   し、 (5)ハッシュ関数Hの出力値よりも短い出力値を出力する
   ようなハッシュ関数hを用いてr[i]=r[i-1] (+)h(x[i]|
   |s[i-1])を計算し、 (6)ユーザiの秘密鍵d[i]を用いてs[i]=k[i]+d[i](e[i]+
   r[i])を計算し (7)得られた数値の組(r[i],s[1], ... ,s[i])をディ
   ジタル署名として出力することを特徴とする請求項２記
   載の公開鍵暗号方法および装置。