JPH05128132A - デイジタル署名方式 - Google Patents

デイジタル署名方式

Info

Publication number
JPH05128132A
JPH05128132A JP3287505A JP28750591A JPH05128132A JP H05128132 A JPH05128132 A JP H05128132A JP 3287505 A JP3287505 A JP 3287505A JP 28750591 A JP28750591 A JP 28750591A JP H05128132 A JPH05128132 A JP H05128132A
Authority
JP
Japan
Prior art keywords
signature
signer
result
electronic document
calculation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP3287505A
Other languages
English (en)
Inventor
Toshiharu Harada
俊治 原田
Makoto Tatebayashi
誠 館林
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Holdings Corp
Original Assignee
Matsushita Electric Industrial Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Matsushita Electric Industrial Co Ltd filed Critical Matsushita Electric Industrial Co Ltd
Priority to JP3287505A priority Critical patent/JPH05128132A/ja
Publication of JPH05128132A publication Critical patent/JPH05128132A/ja
Pending legal-status Critical Current

Links

Abstract

(57)【要約】 【目的】 本発明の目的は、通信ネットワークを介して
やり取りされる電子文書の正当性を、複数の署名者の生
成した数値データたるディジタル署名を用いて確認する
方法において、その署名確認の処理が、従来より少ない
方法を提供することを目的とする。 【構成】 システムパラメタを設定する１０システム管
理者と、電子文書Ｍに対する署名(t1,t2,…,ti,Si)を生
成するN人の２０署名者Ai(ｉ＝1〜N)と、署名を確認す
る３０認証者AN+1からなり、認証者AN+1は、各署名者の
署名を、高次の高速指数演算法を利用して一括して確認
するため、処理量が従来より少なくできる。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】数値データ化された種々のビジネ
ス文書をコンピュータや通信ネットワークを介して電子
的にやり取りしたり蓄積するときに、その電子文書の作
成者や承認者を確認したり、電子文書の内容の正当性を
確認したりするためのディジタル署名方式に係わる。と
くに、複数の人が、一つの文書の内容の正しさを保証す
るためのディジタル署名方式に係わる。
【０００２】
【従来の技術】コンピュータネットワークの発達に伴っ
て、さまざまな契約文書や取引文書がコンピュータネッ
トワークを介して電子的にやり取りされたり、蓄積され
るようになってきている。しかし、このようなネットワ
ークを介してやり取りされる電子文書の内容の正しさ
や、発行者などの確認に、従来の紙をベースとした文書
のやり取りにおいて、その文書の正しさや発行者などの
確認に用いられている捺印やサインをそのまま数値デー
タ化して用いることはできない。なぜなら、捺印やサイ
ンをそのまま数値データ化したデータは容易にコピーで
きるためである。
【０００３】この問題を解決する手段として、暗号技術
を利用したディジタル署名法がある。すなわちディジタ
ル署名法を利用すれば、数値データ化した電子文書に対
して、その文書の正当性を保証する人（署名者）が作成
する電子データ（このデータをディジタル署名と呼ぶ）
を捺印やサインの代わりに用いることで、その文書の正
当性の確認を行うことができる。
【０００４】ところでビジネス社会で交わされる文書の
中には、一つの文書に対して、複数の人間が、その文書
の正当性を保証するために捺印やサインをする場合があ
る。例えば稟議書、決裁書などである。
【０００５】このような文書の場合、捺印やサインを行
なう者（署名者）が、他の署名者の署名を認証後、署名
する場合が多い。
【０００６】以下では、このような複数人の捺印やサイ
ンの必要な文書を、ネットワークを介して電子的にやり
とりしたり、蓄積したりするために、従来からよく知ら
れているディジタル署名法を直接利用する方法、すなわ
ち一つの文書に対して、複数の署名者がそれぞれ署名す
る方法を従来例として説明する。この従来例は各署名者
の署名を一つ一つ確認すること必要があるため、署名を
確認する認証者の署名確認に要する処理量が大きいとい
う問題がある。 ・従来例 ここでは、ディジタル署名法として、エルガマル(ElGam
al) の提案したElGamal 署名法を用いる場合について簡
単に説明する。
【０００７】ここで用いるエルガマル署名法は、”ア
パブリック キー クリプトシステム アンド シグニ
チャスキーム ベイスト オン ディスクリートロガリ
ズム”プロシーディング オブ クリプト84(T.E.ElGam
al:"A public key cryptosystem and signature scheme
based on discrete logarithm",Proc.Crypto84)に詳し
く述べられている。
【０００８】従来例の構成を図６に示す。同図からわか
るように、従来例は、全ユーザに共通の署名用パラメー
タを発行するシステム管理者と、ある文書の正当性を保
証するために署名を作成する複数のユーザ（署名者）
と、その署名を確認するユーザ（認証者）で構成され
る。
【０００９】とくに、ここではN 人の署名者A1,A2,…,A
Nが、署名者A1→署名者A2→…→署名者ANの順番である
数値データ化された電子文書Ｍに対して署名を作成し、
認証者AN+1が作成された署名を確認するものとする。こ
の方法は初期設定ステップ、署名作成ステップ、署名確
認ステップより構成される。 〔システム初期設定ステップ〕 [1] システムの管理者は、素数ｐとｐを法とする有限体
の元で、その元を(p-1)の約数ｑでべき乗すると初めて
１になる元ｇを決定し、一方向性関数ｆをつぎのように ｆ(x)＝ｇx mod ｐ 決定する。なお、(ｃ＝ａ mod ｂ) は、ａをｂで割った
ときの余りがｃであることを意味する。ただし、ここで
x はｑ未満の数値とする。また入力値をｑ未満の数値に
圧縮するハッシュ関数ｈを決定する。そして、一方向性
関数ｆ、ハッシュ関数ｈを全てのユーザに通知する。
【００１０】なお、ハッシュ関数は、異なる入力{di}、
{di'} に対して、同じ出力となるような入力{di}、{d
i'} を求めることが困難な関数であり、具体的には、DE
Sなどのブロック暗号を利用する方式が、国際標準化機
構(ISO) で検討されている。 [2] 各署名者Ai(i＝1,2,…,N) は、各自、次式を満たす
(xi,yi)を求める。
【００１１】 yi＝ｆ(xi)＝ｇxi mod ｐ (1) ここでyiは署名確認用のパラメータとして他の全てのユ
ーザに公開し、xiは署名作成用のパラメータとして各署
名者自身が秘密に保持する。なお署名者Aiは、秘密の署
名作成用パラメータxiの管理を厳重にする必要がある。
なぜなら、xiを手にいれた第３者は、Aiに成り変わって
容易に署名を偽造できるからである。またシステム管理
者は、公開されている(ｇ,ｐ,yi)から(1) 式を用いて署
名者Aiの秘密であるxiを求めることが困難となるよう、
素数ｐを500 ビット程度に、またｑは少なくとも150ビ
ット程度に選ぶ必要がある。このとき、最高速のコンピ
ュータを用いてもxiを求めることは計算量的に不可能で
あると考えられる。
【００１２】〔署名の作成ステップ〕 （１）署名者A1は、ｑ 未満の正整数である乱数r1を発
生し、さらに数値データ化された電子文書Ｍを適当なハ
ッシュ関数h を用いてｑ未満の正整数値h(Ｍ)に変換
し、次式より署名(t1,s1) t1＝ｇr1 mod ｐ (2) s1＝(h(Ｍ)-x1×t1)×r1-1 mod ｑ (3) を生成する。そしてこの署名(t1,s1)と電子文書Ｍを署
名者A2に通知する。次に、各署名者Aj(j＝2〜N)は、A2,
A3,…,ANの順番で、次の手順を行う。 （２） 署名者Ajは、Aj-1から通知された署名{s1,s2,
…,sj-1,t1,t2,…,tj-1}と電子文書Ｍに対して、次の等
式が成り立つことを確認する。
【００１３】 ｇ-h(M)×tksk×yktk＝１ mod ｐ (ただしk＝1〜j-1) (4) (4)式が成り立つ場合署名者Aj-1から受け取った署名は
電子文書Ｍに対する正しい署名であると判断し、署名者
A1と同様の手順で自身の署名(sj,tj)を作成する。すな
わち、ｑ未満の正整数である乱数rjを発生し、さらに数
値データ化された電子文書Ｍを適当なハッシュ関数h を
用いてｑ未満の正整数h(Ｍ)に変換し、次式より署名(t
1,s1) tj＝ｇrj mod ｐ (5) sj＝(h(Ｍ)-xj×tj)×rj-1 mod ｑ (6) を生成し、次の署名者Aj+1(j＝2,3,…N)に（署名者ANの
場合は認証者AN+1）に署名{s1,s2,…,sj,t1,t2,…,tj}
と電子文書Ｍを通知する。
【００１４】〔署名の確認ステップ〕 （３） 認証者AN+1は、最終署名者ANから通知された署
名{s1,s2,…,sN,t1,t2,…,tN}と電子文書Ｍに対して、
次の等式が成り立つことを確認する。
【００１５】 ｇ-h(M)×tksk×yktk＝１ mod ｐ (ただしk＝1〜N) (7) (7)式が成り立つ場合署名者ANから受け取った署名は電
子文書Ｍに対する正しい署名であると判断し、電子文書
Ｍと署名{s1,s2,…,sN,t1,t2,…,tN}を保存する。
【００１６】以上が、従来例１の構成である。次に、従
来例１の署名作成時（(2)、(3)、(5)、(6)式）、および
署名確認時（(4)、(7)式）の処理量について考察する。
【００１７】ここでは処理量を、法ｐの桁数(log2ｐビ
ット)程度の数値に対する乗算剰余演算の回数で表わす
ことにする。これは、この従来例の構成において乗算剰
余演算以外の処理は、乗算剰余演算の処理に比較して無
視できるほど小さいためである。
【００１８】ところで、ある数値ｘを、ある数値ｙでべ
き乗し、その結果をある数値ｐで割った余りｚを求める
というべき乗剰余演算 ｚ＝ｘy mod ｐ (8) は、高速指数演算法と呼ばれる方法を利用すると効率的
に計算できる。高速指数演算法は、例えば電子通信学会
編「現代暗号理論」第１章に詳しく述べられているが、
基本的には、ある数値ａとある数値ｂの積を数値ｐで割
った余りｃを求めるという乗算剰余演算 ｃ＝ａ×ｂ mod ｐ と特に、この乗算剰余演算においてｂ＝ａの場合である
２乗剰余演算 ｃ＝ａ×ａ mod ｐ を繰り返し用いて実行される。この方法を利用すると
(8) 式のべき乗剰余演算は、乗算剰余演算（２乗剰余演
算も含む）を 平均〔{2−(1/2)}×log2ｙ〕回 繰り返せば実行できる。ただしここで(log2ｙ)は、数値
ｙを２進数で表現したときの桁数（ビット数）である。
【００１９】以上の高速指数演算法を用いれば、従来例
の処理量、例えば(7)式の認証者の署名確認に必要な処
理量は、 平均〔{2−(1/2)}×log2ｑ×2×N ＋{2−(1/2)}×log2
ｐ×N 〕 回 となる（(7)式におけるsk,h(M)は、いずれも数値ｑと同
程度の桁数(log2ｑビット)であり、tkは、log2ｐは数値
ｐの桁数（ビット数）と同程度であり、Nは署名者数で
ある）。従って、例えばｐおよびｑの桁数（ビット数）
がともに500とするとき、署名確認の処理量に、乗算剰
余演算を平均2250×N 回実行する必要があり、署名者数
N が大きいと処理量が大きく非実用的である。
【００２０】ところで、高速指数演算法を拡張すると、 ｚ＝x1y1×x2y2×…×xkyk mod ｐ (9) のようなｋ個の被べき乗数（x1,x2,…,xk）に対するべ
き乗剰余演算（以降ではｋ次べき乗剰余演算と呼ぶ）の
計算を一括して効率的に行なうことができる。このよう
なｋ次のべき乗剰余演算に対する高速指数演算法を以降
では高次の高速指数演算法あるいは、ｋ次高速指数演算
法と呼ぶ。なおｋ＝１のとき従来の高速指数演算法とな
る。
【００２１】この高次の高速指数演算法は、通常（ｋ＝
１）の高速指数演算法と同様にして 平均〔{2−(1/2)k}×log2ｙ〕 回 の乗算剰余演算（ここでkは、被べき乗数の個数、log2
ｙは、べきである各yiの桁数（ビット数）であり、簡単
のためすべて等しいとする）と、乗算剰余演算における
次式で与えられる乗数Xm Xm＝x1y1m×…×xkykm modｐ (10) の全ての取り得る値を計算するために、〔(2k-k-1)〕回
の乗算剰余演算が必要である（ここでyjm(j＝1〜k)は、
べき数である各yj(j＝1〜k)を２進数に展開したときの
係数 yj＝(yj0,…,yjm,…)＝Σyjm×2m (yjm＝{0,1}) である）。すなわち、(9)式のｋ次べき乗剰余演算に必
要な乗算剰余演算の回数は、合計 平均〔{2−(1/2)k}×log2ｙ＋(2k-k-1)〕 回 となる。これに対して各数値xiに対するべき乗剰余演算
（xiyi mod ｐ）を通常の高速指数演算法を用いて個々
に求め、その後ｚを求める場合、 平均〔{2−(1/2)} ×log2ｙ×k＋k-1〕回 の乗算剰余演算が必要である。これらのことから、次の
(H1)、あるいは(H2)の条件が満たされれば、(9)式のｋ
次べき乗剰余演算に、ｋ次の高速指数演算法を利用する
方が処理量が少なくなる。
【００２２】(H1) (10)式のXmを事前に計算できる場
合。 (H2) kが比較的小さい場合。目安として、kが 2k+1／k＜3×log2ｙ を満たすとき（kは被べき乗数の個数、log2ｙは、べき
数である各yiの桁数（ビット数））。そして、この(H1)
あるいは(H2)の条件が満たされるとき(10)式の演算に関
する処理量は無視できると考えてよい。
【００２３】以上のことを踏まえると従来例では、署名
確認の処理（(4)、(7)式）に、通常の高速指数演算法を
個々に適用するより、ｋ(=3)次高速指数演算法を適用す
る方が処理量を小さくできる（k=3、べき数の大きさ(lo
g2ｙ)＞150とするとき(H2)が成立することは明か）。以
下にｋ(=3)次高速指数演算法を適用する場合の各署名作
成者Ai(i＝1〜N)および認証者の処理量を示す。
【００２４】署名者Aiの署名の作成：平均〔{2−(1/2)}
×log2 ｑ〕回 署名の確認：平均〔{2−(1/2)3}×log2ｑ×(i-1)〕回 認証者Aiの署名の確認：平均〔{2−(1/2)3}×log2 ｑ×
N〕回 ここで、log2ｑは数値ｑの桁数（ビット数）であり、N
は署名者数である。なお、(1)式〜(7)式におけるsk,h
(M)は、いずれも数値ｑと同程度の桁数(log2ｑビッ
ト)、tkは、数値ｐと同程度の桁数(log2ｑビット)とな
るが、ここでは簡単のためｐとｑを同程度の桁数（ビッ
ト数）としている。
【００２５】このように各署名者の署名作成に要する処
理量は、各署名者で全く同じであるが、各署名者の署名
確認に要する処理量は、自分より先に署名を施した署名
者の署名に比例する（署名者Aiの場合、自分より先に(i
-1)人が署名を施していることに注意されたい）。また
認証者の署名確認の処理量は、各署名者の署名を一つ一
つ確認するため署名者数N に比例する。具体的にｑを50
0ビットに選ぶ場合、認証者の署名確認（(7)式）に必要
な乗算剰余演算の回数は約(950×N)回必要となり、通常
(ｋ＝１)の高速指数演算法を個々に用いる前述の場合よ
り処理量は少なくなるものの依然として、署名者数N が
大きいと処理量が大きく非実用的である。
【００２６】
【発明が解決しようとする課題】このように以上で述べ
た従来例の構成による複数人によるディジタル署名法で
は、署名の確認時の処理量が、署名者数N に比例して大
きくなるという問題点を有する。
【００２７】本発明は以上の問題点に鑑みて試されたも
のであり、署名確認の処理が、従来例より減少せしめる
複数人によるディジタル署名法を提供することを目的と
する。
【００２８】
【課題を解決するための手段】以上の目的を達成するた
めに請求項１に係わる発明においては、各署名者Ai(ｉ
＝1〜N)および認証者AN+1は、２つのデータd1、d2に対
する、ある第１の演算op1 の結果op1〔d1,d2〕をその入
力値とするときの出力値ｆ(op1〔d1,d2〕)が、データd1
をその入力値とするときの出力値ｆ(d1)とデータd2に対
するある第２の演算op2 の結果op2〔ｆ(d1),d2〕に等し
くなり、かつ２つ以上のデータd1,d2,…,dn (n≧2)に対
するある第３の演算op3 の結果op3〔d1,d2,…,dn〕をそ
の入力値とするときの出力値ｆ(op3〔d1,d2,…,dn〕)
が、前記データd1,d2,…,dn のそれぞれをその入力値と
するときの各出力値ｆ(d1),ｆ(d2),…,ｆ(dn) に対する
ある第４の演算op4 の結果op4〔ｆ(d1),ｆ(d2),…,ｆ(d
n)〕に等しくなる一方向性関数ｆと、１つ以上のデータ
d1,d2,…,dn(n≧1) を入力値とするときに、その各入力
値に依存した、ある定められた長さの圧縮データｈ(d1,
d2, …,dj)を出力するハッシュ関数と、各署名者Ai(ｉ
＝1〜N)の署名を確認するための署名確認用パラメータy
i(ｉ＝1〜N)を保持しており、さらに、各署名者Ai(ｉ＝
1〜N)は、それぞれ各自の署名を作成するための署名確
認用パラメータxiを秘密に保持している。
【００２９】なお署名作成用パラメータxiは、前述の一
方向性関数ｆに入力したときの出力が、署名確認用パラ
メータyiに等しくなるように設定する。
【００３０】そして、複数の署名者がそれぞれの署名を
生成する署名生成ステップと、認証者が署名生成ステッ
プで生成された各署名者の署名を確認する署名確認ステ
ップを設ける。そして、上述の第４の演算op4の結果op4
〔ｆ(d1),ｆ(d2),…,ｆ(dn)〕を求めるのに、高速指数
演算法を拡張した高次の高速指数演算法を用いものとす
る。そして、その署名作成ステップは、署名者A1が、秘
密に生成した乱数r1を用いてt1＝ｆ(r1)を求め、電子文
書Ｍとこのt1を用いてh1＝ｈ(Ｍ,t1) を求め、このh1と
署名作成用パラメータx1に対するある第１の演算の結果
op1〔h1,x1〕を求め、この結果と先の乱数r1に対するあ
る第３の演算の結果S1＝op3〔op1〔h1,x1〕,r1〕を求
め、以上の{t1,S1} を署名者A1の署名として、電子文書
Ｍとともに署名者A2に通知するステップと、署名者Aj(j
＝2〜N)が、A2,A3,…,ANの順番で、署名者Aj-1(j＝2〜
N) より通知された署名{t1,t2,…,tj-1} に対するある
第４の演算の結果Tj-1＝op4〔t1,t2,…,tj-1〕を求め、
電子文書Ｍと署名{t1,t2,…,tj-1} を用いてhk＝ｈ(Ｍ,
tk) (k＝1〜j-1) を求め、このhkと署名確認用パラメー
タyk(k＝1〜j-1) に対するある第２の演算の結果op2〔y
k,hk〕(k＝1〜j-1) を求め、この第２の演算の結果の第
４の演算に関する逆数であるop2〔yk,hk〕-1 (k＝1〜j
-1) を求め、この逆数と署名者Aj-1(j＝2〜N) より通知
された署名Sj-1を用いてｆ(Sj-1)を求め、このｆ(Sj-1)
に対する第４の演算の結果Tj-1'＝op4〔ｆ(Sj-1),op2
〔y1,h1〕-1,op2〔y2,h2〕-1,…,op2〔yj-1,hj-1〕-1〕
を求め、この第４の演算の結果Tj-1'が先に求めたTj-1
に一致すれば署名{t1,t2,…,tj-1,Sj-1}が電子文書Ｍに
対する署名者Aj(j＝1〜j-1) の署名であると認識するス
テップと署名者Aj(j＝2〜N) が乱数rjを秘密に生成し、
この乱数rjを用いてtj＝ｆ(rj)を求め、電子文書Ｍとこ
のtjを用いてhj＝ｈ(Ｍ,tj) を求め、このhjと署名作成
用パラメータxjに対する第１の演算の結果op1〔hj,xj〕
を求め、この第１の演算の結果と乱数rjに対する第３の
演算の結果sj＝op3〔op1〔hj,xj〕,rj〕を求め、この第
３の演算結果sjと署名者Aj-1(j＝2〜N) より通知された
署名Sj-1に対する第３の演算の結果Sj＝op3〔Sj-1,sj〕
を求め、以上の{t1,t2,…,tj,Sj}を署名者Ajの署名とし
て電子文書Ｍとともに次の署名者（または認証者）Aj+1
(j＝2〜N)に通知するステップより構成される。
【００３１】また署名確認ステップは、認証者AN+1が、
署名者ANより通知された署名{t1,t2,…,tN} に対する第
４の演算の結果TN＝op4{t1,t2,…,tN}を求め、電子文書
Ｍと署名{t1,t2,…,tN}を用いてhk＝ｈ(Ｍ,tk) (k＝1〜
N)を求め、このhkと署名確認用パラメータyk (k＝1〜N)
に対する第２の演算の結果op2〔yk,hk〕(k＝1〜N) を求
め、この第２の演算の結果の第４の演算に関する逆数op
2〔yk,hk〕-1 (k＝1〜N)を求め、署名者ANより通知され
た署名SNを用いてｆ(SN)を求め、この逆数とｆ(SN)に対
する第４の演算の結果TN'＝op4〔{ｆ(SN),op2〔y1,h1〕
-1,op2〔y2,h2〕-1,…,op2〔yN,hN〕-1〕を求め、この
演算結果TN'がTNに一致すれば署名{t1,t2,…,tN,SN}が
電子文書Ｍに対する署名者Aj (j＝1〜N) の署名である
と認識するステップより構成される。
【００３２】請求項２に係わる発明においては、各署名
者Ai(ｉ＝1〜N)および認証者AN+1は、請求項１に係わる
発明の場合と同じ構成の一方向性関数ｆとハッシュ関数
ｈと署名作成用パラメータxiと署名確認用パラメータyi
を保持している。
【００３３】そして、署名作成ステップは、署名者A1
が、秘密に生成した乱数r1を用いてT1＝t1＝ｆ(r1)を求
め、電子文書ＭとこのT1を用いてh1＝ｈ(Ｍ,T1) を求
め、このh1と署名作成用パラメータx1に対するある第１
の演算の結果op1〔h1,x1〕を求め、この結果と先の乱数
r1に対するある第３の演算の結果S1＝op3〔op1〔h1,x
1〕,r1〕を求め、以上の{T1,S1} を署名者A1の署名とし
て、電子文書Ｍとともに署名者A2に通知するステップ
と、署名者Aj(j＝2〜N)が、A2,A3,…,ANの順番で、署名
者Aj-1(j＝2〜N) より通知された電子文書Ｍと署名{T1,
T2,…,Tj-1} を用いてhk＝ｈ(Ｍ,Tk) (k＝1〜j-1)を求
め、このhkと署名確認用パラメータyk(k＝1〜j-1) に対
するある第２の演算の結果op2〔yk,hk〕(k＝1〜j-1) を
求め、この第２の演算の結果の第４の演算に関する逆数
であるop2〔yk,hk〕-1 (k＝1〜j-1) を求め、この逆数
と署名者Aj-1(j＝2〜N) より通知された署名Sj-1を用い
てｆ(Sj-1)を求め、このｆ(Sj-1)に対する第４の演算の
結果Tj-1'＝op4〔ｆ(Sj-1),op2〔y1,h1〕-1,op2〔y2,h
2〕-1,…,op2〔yj-1,hj-1〕-1〕 を求め、この第４の演
算の結果Tj-1'がTj-1に一致すれば署名{T1,T2,…,Tj-1,
Sj-1}が電子文書Ｍに対する署名者Aj(j＝1〜j-1) の署
名であると認識するステップと署名者Aj(j＝2〜N) が乱
数rjを秘密に生成し、この乱数rjを用いてtj＝ｆ(rj)を
求め、このtjとTj-1に対する第４の演算の結果op4〔tj,
Tj-1〕を求め、電子文書ＭとこのTjを用いてhj＝ｈ(Ｍ,
Tj) を求め、このhjと署名作成用パラメータxjに対する
第１の演算の結果op1〔hj,xj〕を求め、この第１の演算
の結果と乱数rjに対する第３の演算の結果sj＝op3〔op1
〔hj,xj〕,rj〕を求め、この第３の演算結果sjと署名者
Aj-1(j＝2〜N) より通知された署名Sj-1に対する第３の
演算の結果Sj＝op3〔Sj-1,sj〕を求め、以上の{T1,T2,
…,Tj,Sj}を署名者Ajの署名として電子文書Ｍとともに
次の署名者（または認証者）Aj+1(j＝2〜N) に通知する
ステップより構成される。
【００３４】また署名確認ステップは、認証者AN+1が、
署名者ANより通知された電子文書Ｍと署名{T1,T2,…,T
N}を用いてhk＝ｈ(Ｍ,Tk) (k＝1〜N)を求め、このhkと
署名確認用パラメータyk (k＝1〜N)に対する第２の演算
の結果op2〔yk,hk〕(k＝1〜N)を求め、この第２の演算
の結果の第４の演算に関する逆数op2〔yk,hk〕-1 (k＝1
〜N)を求め、署名者ANより通知された署名SNを用いてｆ
(SN)を求め、この逆数とｆ(SN)に対する第４の演算の結
果TN'＝op4〔{ｆ(SN),op2〔y1,h1〕-1,op2〔y2,h2〕-1,
…,op2〔yN,hN〕-1〕を求め、この演算結果TN'がTNに一
致すれば署名{T1,T2,…,TN,SN}が電子文書Ｍに対する署
名者Aj (j＝1〜N) の署名であると認識するステップよ
り構成される。
【００３５】請求項３に係わる発明においては、各署名
者Ai(ｉ＝1〜N)および認証者AN+1は、請求項１に係わる
発明の場合と同じ構成の一方向性関数ｆとハッシュ関数
ｈと署名作成用パラメータxiと署名確認用パラメータyi
を保持している。
【００３６】そして、署名作成ステップは、署名者A1
が、秘密に生成した乱数r1を用いてt1＝ｆ(r1)を求め、
電子文書Ｍとt1を用いてh1＝ｈ(Ｍ,t1) を求め、このh1
と署名作成用パラメータx1に対する第１の演算の結果op
1〔h1,x1〕を求め、この第１の演算の結果と先の乱数r1
に対する第３の演算の結果S1＝op3〔op1〔h1,x1〕,r1〕
を求め、以上の{h1,S1} を署名者A1の署名として電子文
書Ｍとともに署名者A2に通知するステップと、署名者Aj
(j＝2〜N)が、A2,A3,…,ANの順番で、署名者Aj-1(j＝2
〜N)より通知された署名{h1,h2,…,hj-1}と署名確認用
パラメータyk(k＝1〜j-1) に対する第２の演算の結果op
2〔yk,hk〕(k＝1〜j-1) を求め、この第２の演算の結果
の第４の演算op4 に関する逆数であるop2〔yk,hk〕-1
(k＝1〜j-1)を求め、署名者Aj-1(j＝2〜N)より通知され
た署名Sj-1を用いてｆ(Sj-1)を求め、この逆数とf(Sj-
1)に対する第４の演算の結果Tj-1'＝op4〔ｆ(Sj-1),op2
〔y1,h1〕-1,op2〔y2,h2〕 -1,…,op2〔yj-1,hj-1〕-1〕
を求め、この第４の演算の結果Tj-1'と電子文書Ｍを用
いて求めたh(Ｍ,Tj-1')が、署名者Aj-1(j＝2〜N)より通
知された署名hj-1に一致すれば署名{h1,h2,…,hj-1,Sj-
1}が電子文書Ｍに対する署名者Aj(j＝1〜j-1)の署名で
あると認識するステップと、署名者Aj(j＝2〜N) が秘密
に生成した乱数rjを用いてtj＝ｆ(rj)を求め、このtjと
先に求めたTj-1'に対する第４の演算結果Tj＝op4〔tj,T
j-1'〕を求め、電子文書ＭとこのTjを用いてhj＝ｈ(Ｍ,
Tj) を求め、このhjと署名作成用パラメータxjに対する
第１の演算の結果op1〔hj,xj〕を求め、この第１の演算
の結果と先の乱数rjに対する第３の演算の結果sj＝op3
〔op1〔hj,xj〕,rj〕を求め、この第３の演算の結果sj
と署名者Aj-1(j＝2〜N)より通知された署名Sj-1に対す
る第３の演算の結果Sj＝op3〔Sj-1,sj〕を求め、以上の
〔h1,h2,…,hj,Sj〕を署名者Ajの署名として、電子文書
Ｍとともに署名者（または認証者）Aj+1(j＝2〜N) に通
知するステップより構成される。また、署名確認ステッ
プは、認証者AN+1が、署名者ANより通知された署名{h1,
h2,…,hN} と署名確認用パラメータyk (k＝1〜N)に対す
る第２の演算の結果op2〔yk,hk〕(k＝1〜N) を求め、こ
の第２の演算の結果の第４の演算に関する逆数op2〔yk,
hk〕-1 (k＝1〜N) を求め、署名者ANより通知された署
名SNを用いてｆ(SN)を求め、この逆数とf(SN)に対する
第４の演算の結果TN'＝op4〔ｆ(SN),op2〔y1,h1〕-1,op
2〔y2,h2〕-1,…,op2〔yN,hN〕-1〕を求め、この第４の
演算の結果TN'と電子文書Ｍを用いて求めたh(Ｍ,TN')
が署名者ANより通知された署名hNに一致すれば署名{h1,
h2,…,hj-1,Sj-1}が電子文書Ｍに対する署名者Aj(j＝1
〜N) の署名であると認識するステップより構成され
る。
【００３７】請求項４に係わる発明においては、特に一
方向性関数ｆとして、ある素数もしくは素数のべき乗値
である数値ｐを用いて構成される有限体上で定義される
関数で、(ｐ−１)の約数である数値ｑでべき乗すると初
めてこの有限体上の乗法に関する単位元１に等しくなる
元ｇをある数値ａでべき乗する関数ｆ(ａ)＝ｇa を用
い、第１の演算として、先の数値ｑを法とする乗算演算
を用い、第２の演算として、先の有限体上で定義される
べき乗演算を用い、第３の演算として先の数値ｑを法と
する加算を用い、第４の演算として先の有限体上で定義
される乗算を用いる。
【００３８】請求項５に係わる発明においては、特に一
方向性関数ｆとして、ある合成数ｎを法とする剰余環上
で定義される関数で、ｎのオイラー関数値φ(ｎ)に互い
に素なある数値ｅでべき乗し、先の合成数ｎで除したと
きの剰余を求める関数ｆ(ａ)＝ａe mod ｎを用い、第１
の演算と第２の演算として、先の剰余環上で定義される
べき乗演算を用い、第３の演算と第４の演算として先の
剰余環上で定義される乗算演算を用いる。
【００３９】請求項６に係わる発明においては、特に一
方向性関数ｆとして、ある有限体上で構成される楕円曲
線上で定義される関数で、ある数値ｑでこの楕円曲線上
定義されるスカラー倍演算を行うと初めて同じくこの楕
円曲線上定義される加算演算に関する単位元（楕円曲線
上の点）∞に等しくなる点Ｇをある数値ａでスカラー倍
する関数ｆ(ａ)＝ａ×Ｇを用い、第１の演算として先の
数値ｑを法とする乗算を用い、第２の演算として先の楕
円曲線上で定義されるスカラー倍演算を用い、第３の演
算として先の数値ｑを法とする加算演算を用い、第４の
演算としてこの楕円曲線上で定義される加算を用いる。
【００４０】
【作用】上記請求項において示した構成により、署名者
Ai(i＝1〜N）が、電子文書Ｍに対して、それぞれの秘密
に保持している署名作成用パラメータxiを用いて作成し
た署名{t1,t2,…tN,sN}あるいは{h1,h2,…hN,sN}を、認
証者AN+1が、各署名者Ai（i＝1〜N）の署名確認用パラ
メータyi（i＝1〜N）を用いて、正に署名者Ai(i＝1〜N)
の作成した署名であるかどうかを、高速指数演算法を拡
張した高次の高速指数演算法を用いて一括して確認でき
るため、署名確認の処理量が減少できる。
【００４１】また、署名者A1を除く各署名者Ai（i＝2〜
N）は、各自の署名を作成する前に、署名者Ai-1より通
知された署名{t1,t2,…ti-1,Si-1}あるいは{h1,h2,…hi
-1,Si-1}を、各署名者Aj（j＝1〜j-1）の署名確認用パ
ラメータyj（j＝1〜i-1）を用いて、各署名者Aj(j＝1〜
i-1) の作成した署名であることを高次の高速指数演算
法を用いて一括して確認できるため、署名確認の処理量
が減少できる。
【００４２】また、上記請求項３の構成により、ハッシ
ュ関数の出力hiを署名として用いるため署名のデータ量
をハッシュ関数の出力ビット数を削減することで、署名
のデータ量を削減できる。
【００４３】また、請求項４の構成の一方向性関数ｆを
用いることにより各署名者Ai（i＝1〜N）の署名確認用
パラメータyiを用いて、署名者Aiの秘密である署名作成
用パラメータxiを求めることは、素数ｐが十分に大きい
とき事実上不可能となる。
【００４４】また、請求項５の構成の一方向性関数ｆを
用いることにより各署名者Ai（i＝1〜N）の署名確認用
パラメータyiを用いて、署名者Aiの秘密である署名作成
用パラメータxiを求めることは、数値ｎが少なくとも２
つの大きな素因数を持つ場合、事実上不可能となる。
【００４５】また、請求項６の構成の一方向性関数ｆを
用いることにより各署名者Ai（i＝1〜N）の署名確認用
パラメータyiを用いて、署名者Aiの秘密である署名作成
用パラメータxiを求めることは、いわゆる楕円曲線上の
離散対数問題に帰着され事実上不可能となる。
【００４６】
【実施例】
・実施例１ 図１は本発明の実施例１におけるディジタル署名方式の
構成を示すものである。実施例１は、同図に示すよう
に、システムパラメータを決定するシステム管理者と、
N 人の署名者Aj(j＝1〜N) と認証者AN+1で構成される。
そして、N 人の署名者Aj(j＝1〜N)が、A1,A2,…,ANの順
番に、ある文書Ｍに対する署名を作成し、その署名を認
証者AN+1が確認する。以下同図を参照しながら実施例の
動作をシステム初期設定ステップ、署名作成ステップ、
署名確認ステップの順に詳しく説明する。 １）システム初期設定ステップ （１） システムの管理者は、素数ｐとｐを法とする有
限体の元で、その元を、(p-1) の約数ｑでべき乗すると
初めて１になる元ｇを決定し、一方向性関数ｆを、つぎ
のように ｆ(x)＝ｇx mod ｐ (11) 決定する。ただしここで入力x はｑ未満の正整数値とす
る。また入力値をｑ未満の正整数値に圧縮するハッシュ
関数ｈを決定する。そして、一方向性関数ｆ、ハッシュ
関数ｈを全てのユーザに通知する。
【００４７】なお、ハッシュ関数は、異なる入力データ
組{di}、{di'} に対して、同じ出力データとなるような
データ{di}、{di'} を求めることが困難な関数であり、
具体的には、DESなどのブロック暗号を利用する方式
が、国際標準化機構(ISO) で検討されており、ここでは
それを用いることを想定している。
【００４８】なお、十分な安全性を確保するためｐは、
500ビット程度以上の素数とし、ｑは、少なくとも150
ビット程度以上の数値とし、(11)式におけるf(x)、ｇ、
ｐからｘを求めることを困難とする。（なお安全性につ
いての詳しい議論は後述する。）なお、ｑは、安全性と
処理量のトレードオフによって定められるパラメータで
ある。すなわち、ｑ＝(p-1)とするとき最も安全性が高
くなるが、処理量は最も多くなる。逆にｑを150ビット
程度とすると、安全性は相対的劣るものの、処理量は少
なくできる。 （２） 各ユーザAiは、各自秘密に署名作成用パラメー
タxiとしてｑ未満の正整数値を生成する。そしてその署
名作成用パラメータxiを、システム管理者より通知され
た一方向性関数ｆ(x) に入力し、署名確認用パラメータ
yiを生成する。
【００４９】 yi＝ｆ(xi)＝ｇxi mod ｐ (12) そして署名作成用パラメータxiを秘密に保持する一方、
署名確認用パラメータyiを他のユーザに公開する。 ２）署名作成ステップ ユーザA1,A2,…,ANが、それぞれ署名者として、ある数
値データ化された電子文書Ｍに対して署名し、ユーザAN
+1が、認証者として、その署名を確認する場合について
説明する。なお署名者A1,A2,…,ANの署名順は署名者A1
→署名者A2→…→署名者ANの順とする。また署名者A2以
降は、先に署名を施した署名者の署名を確認した後署名
を行なう。 （１） 署名者A1は、署名作成用パラメータx1（秘密）
を用いて、電子文書Ｍに対して、以下の手順で署名(t1,
S1) を作成し、その署名を署名者A2に通知する。
【００５０】[1]ｑ未満の乱数r1を生成し、r1を一方向
性関数ｆに入力する。 t1＝gr1 mod ｐ (13) [2]電子文書Ｍとt1をハッシュ関数ｈに入力する。
【００５１】 h1＝ｈ(Ｍ,t1) (14) [3]署名作成用パラメータx1を用いて次式を計算する。
【００５２】 S1＝s1＝(h1×x1＋r1) mod ｑ (15) （２） 署名者Aj(j＝2〜N)は、それぞれ署名者Aj-1よ
り通知された署名(t1,t2,…,tj-1,Sj-1)が正しい署名で
あることを以下の手順により確認する。
【００５３】[1]署名tk(k＝1〜j-1)に対して次式を求め
る。 Tj-1＝(t1×t2×…×tj-1) mod ｐ (16) [2]tkと電子文書Ｍに対して次式を求める。
【００５４】 hk＝ｈ(Ｍ,tk) (k＝1〜j-1) (17) [3]次式が成り立つことを確認する。
【００５５】 Tj-1'＝(ｇSj-1×y1-h1×y2-h2×…×yj-1-hj-1) mod ｐ ＝Tj-1 (18) ここで、(18)式が成り立てば署名者Aj-1(j＝2〜N)から
通知された署名(t1,t2,…,tj-1,Sj-1)が、署名者A1〜Aj
-1の署名の相違ないと認識する（この理由については後
述する）。
【００５６】次に、署名者Aj(j＝2〜N)は、以下の手順
で(tj,Sj) を作成し、(t1,t2,…,tj,Sj)を署名として次
の署名者（もしくは認証者）Aj+1(j＝2〜N)に通知す
る。
【００５７】[4]ｑ未満の乱数rjを生成し、rjを一方向
性関数ｆに入力する。 tj＝grj mod ｐ (19) [5]電子文書Ｍとtjをハッシュ関数ｈに入力する。
【００５８】hj＝ｈ(Ｍ,tj) [6]署名作成用パラメータxj（秘密）を用いて次式を計
算する。
【００５９】 sj＝(hj×xj＋rj) mod ｑ (20) [7]求めたsjと署名者Aj-1より受け取ったSj-1を用いて
次式を計算する。
【００６０】 Sj＝(sj＋Sj-1)（＝(s1+s2+…+sj-1)） mod ｑ (21) ３）署名確認ステップ （１） 認証者AN+1は、署名者ANより通知された署名(t
1,t2,…,tN,SN)が正しい署名であることを以下の手順に
より確認する。
【００６１】[1]署名tk(k＝1〜N)に対して次式を求め
る。 TN＝(t1×t2×…×tN) mod ｐ (22) [2]tkと電子文書Ｍに対して次式を求める。
【００６２】 hk＝ｈ(Ｍ,tk) (k＝1〜N) (23) [3]次の確認式が成り立つことを確認する。
【００６３】 TN'＝(ｇSN×y1-h1×y2-h2×…×yN-hN) mod ｐ ＝TN (24) ここで(24)式が成り立てば署名(t1,t2,…,tN,SN)が署名
者Aj(j＝1〜N)の正しい署名であると認識し、電子文書
Ｍと署名(t1,t2,…,tN,SN)を保存する。ところで署名者
Aj(j=2〜N)が(18)式の成立を、また認証者AN+1が(24)式
の成立を確認することで、署名の正しさを確認できる。
なぜなら、 (24)式の左辺TN'＝(ｇSN×y1-h1×y2-h2×…×yN-hN) mod ｐ ＝ｇ(s1+s2+…+sN)×y1-h1×y2-h2×…×yN-hN) mod ｐ ((21)式より) ＝ｇs1×ｇs2×…ｇsN×y1-h1×y2-h2×…×yN-hN) mod ｐ ＝ｇ(h1*x1+r1)×ｇ(h2*x2+r2)…×ｇ(hN*xN+rN) ×y1-h1×y2-h2×…×yN-hN) mod ｐ ((20)式より) ＝(y1h1×ｇr1)×(y2h2×ｇr2)×…×(yNhN×ｇrN) ×y1-h1×y2-h2×…×yN-hN) mod ｐ ((12)式より) ＝ｇr1×ｇr2×…×ｇrN mod ｐ ＝(t1×t2×…×tN) mod ｐ ((19)式より) ＝TN＝(24)式の右辺 ((16)式より) となるためである（(18)式についても同様）。
【００６４】以上が実施例１の構成と動作である。次
に、実施例１における署名作成および署名確認時の処理
量を示す。なお各処理におけるべき乗剰余演算には、従
来例のところで述べた高次の高速指数演算法を用いるも
のとし、各処理量を、従来例と同様に、乗算剰余演算の
何回で表す。ただし、従来例のところで述べたように高
次の高速指数演算法が有効となる(H2)の条件、すなわち
〔2k+1/k＜3×log2ｙ〕（ここでkは被べき乗数の個数、
log2ｙはべき数の桁数（ビット数））を満たすため、各
処理におけるべき乗剰余演算は、10次以下の高速指数演
算法を利用するものとする。この理由は、べき数の桁数
log2ｑは150以上としているため、 2k+1/k＜3×150 を満たす最大のkは10であるからである。
【００６５】そして、例えば(24)式の署名確認の処理の
場合（これには(N+1)次のべ乗剰余演算が必要）、仮に
署名者数Nが10人未満であれば、(N+1)次の高速指数演算
法を１回用いれば(24)式の演算が行える。一方、署名者
数N が10人以上の場合、(24)式の演算を次式 10×(L-1)＜N≦10×L を満たすL 個の10次以下のべき乗剰余演算に分割し、そ
のL 個の10次以下のべき乗剰余演算に対して、それぞれ
10次以下の高速指数演算法を行えばよい。
【００６６】なおこのとき10次以下のべき乗剰余演算に
は 〔{2−(1/2)10}×log2ｑ〕＜〔2×log2ｑ〕回 の乗算剰余演算が必要である。以上のことから、一般に
署名者数Nが、 10×(L-1)＜N≦10×L の場合、署名作成者Ai(ｉ＝１〜N）の各処理量は、以下
のとおりとなる。
【００６７】 署名の作成：平均 〔{2−(1/2) }×log2ｑ〕 回 署名の確認：平均（高々） 〔2×log2ｑ×J〕回 （ここでJ は、10×(J-1)＜j≦10×Jを満たすものとする） 同様に、認証者AN+1の処理は、以下のとおりとなる。
【００６８】 署名の確認：平均（高々） 〔2×log2ｑ×L〕回 なお(13)式〜(24)式における各べき数ri,Si,hi(i＝1〜
N) は、ｑと同程度の桁数(log2ｑビット)の数値であ
る。
【００６９】従って例えば、認証者AN+1の署名確認の処
理量は、ｑを500ビットに選ぶとき高々1000×L 回程度
の乗算剰余演算が必要となる（ただしL は、N/10程
度）。
【００７０】以上のことより、実施例１における署名確
認の処理量は、従来例に比較して最大約1/10(＝L／N)
に削減できる。特にｑを150ビット程度に選ぶ場合、高
々300×L 回程度の乗算剰余演算で実行できる。
【００７１】ところで実施例１における署名のデータ量
は、 (log2ｐ×N＋log2ｑ) ビット となる。
【００７２】次に実施例１の安全性について説明する。
安全性については (1)署名作成用のパラメータを解読する攻撃に対して (2)偽の署名を偽造する攻撃に対して の２つの点について考慮必要がある。
【００７３】(1)について、まずyiからいわゆる離散対
数問題を解くことで直接xi求める攻撃に対しては、ｐを
500ビット程度とすれば、たとえ最高速のコンピュータ
を用いても解けないことが知られている。また、このと
き、xiを悉皆的に探索する攻撃や、署名{t1,t2,…,tN,S
N)からxjを求める攻撃についても不可能と考えられる。
一方、偽の文書M'に対する偽造署名(t1',t2',…,tN',S
N')を作成する攻撃について、まず、tk'(k＝1,2,…,N)
を適当に与えて(22)、(24)式を満たすSNを求めること
は、離散対数問題解くことに帰着されるため、ｐを500
ビット程度とすれば、事実上困難となる。逆にSNを適当
に与えて(22)、(24)式を満たすtk'(k＝1,2,…,N)を求め
ることは、与えられたｙ,M'に対してyh(t,M')＝ｔを満
たすｔを求めることに帰着される。これについては、ｐ
を500ビット、ハッシュ関数h の出力hiを150ビット程度
とすれば、事実上困難になると考えられる。なお実施例
１では、ｐとして素数を選んだが、ｐとしてある素数
ｐ'のべき乗値に選んでも同様に構成できる、だだしこ
の場合、乗算剰余演算（ａ×ｂmodｐ）を、ｐで構成さ
れる有限体上の乗算に置き換える。 〔実施例２〕実施例１では、署名者Ajの署名を(tj(j＝
１〜j),Sj)としたが、実施例１における(Tj(j＝１〜j),
Sj)を署名とすることがきる。この方法を実施例２とし
て以下に説明する。
【００７４】図２は本発明の実施例２におけるディジタ
ル署名方式の構成を示すものである。実施例２も実施例
１と同様に、システムパラメータを決定するシステム管
理者と、N 人の署名者Aj(j＝1〜N) と認証者AN+1で構成
される。そして、N 人の署名者Aj(j＝1〜N)が、A1,A2,
…,ANの順番に、ある文書Ｍに対する署名を作成し、そ
の署名を認証者AN+1が確認する。以下同図を参照しなが
ら実施例２の動作を説明する。ただしシステム初期設定
ステップは実施例１と全く同じであるので省略し、署名
作成ステップ、署名確認ステップについて詳しく説明す
る。 ２）署名作成ステップ ユーザA1,A2,…,ANが、それぞれ署名者として、ある数
値データ化された電子文書Ｍに対して署名し、ユーザAN
+1が、認証者として、その署名を確認する場合について
説明する。なお署名者A1,A2,…,ANの署名順は署名者A1
→署名者A2→…→署名者ANの順とする。また署名者A2以
降は、先に署名を施した署名者の署名を確認した後署名
を行なう。 （１） 署名者A1は、署名作成用パラメータx1（秘密）
を用いて、電子文書Ｍに対して、以下の手順で署名(T1,
S1) を作成し、その署名を署名者A2に通知する。
【００７５】[1]ｑ未満の乱数r1を生成し、r1を一方向
性関数ｆに入力する。 T1＝t1＝gr1 mod ｐ (25) [2]電子文書Ｍとt1をハッシュ関数ｈに入力する。
【００７６】 h1＝ｈ(Ｍ,T1) (26) [3]署名作成用パラメータx1を用いて次式を計算する。
【００７７】 S1＝s1＝(h1×x1＋r1) mod ｑ (27) （２） 署名者Aj(j＝2〜N)は、それぞれ署名者Aj-1よ
り通知された署名(T1,T2,…,Tj-1,Sj-1)が正しい署名で
あることを以下の手順により確認する。
【００７８】[1]Tkと電子文書Ｍに対して次式を求め
る。 hk＝ｈ(Ｍ,Tk) (k＝1〜j-1) (28) [2]次式が成り立つことを確認する。
【００７９】 Tj-1'＝(ｇSj-1×y1-h1×y2-h2×…×yj-1-hj-1) mod ｐ ＝Tj-1 (29) ここで、(29)式が成り立てば署名者Aj-1(j＝2〜N)から
通知された署名(T1,T2,…,Tj-1,Sj-1)が、署名者A1〜Aj
-1の署名の相違ないと認識する。
【００８０】次に、署名者Aj(j＝2〜N)は、以下の手順
で(Tj,Sj) を作成し、(T1,T2,…,Tj,Sj)を署名として次
の署名者（もしくは認証者）Aj+1(j＝2〜N)に通知す
る。
【００８１】[3]ｑ未満の乱数rjを生成し、rjを一方向
性関数ｆに入力する。 tj＝grj mod ｐ (30) [4]Tjを求める。
【００８２】 Tj＝tj×Tj-1（＝(t1×t2×…×tj-1)） mod ｐ (31) [5]電子文書Ｍとtjをハッシュ関数ｈに入力する。 hj＝ｈ(Ｍ,Tj) (32) [6]署名作成用パラメータxj（秘密）を用いて次式を計
算する。
【００８３】 sj＝(hj×xj＋rj) mod ｑ (33) [7]求めたsjと署名者Aj-1より受け取ったSj-1を用いて
次式を計算する。
【００８４】 Sj＝(sj＋Sj-1)（＝(s1+s2+…+sj-1)） mod ｑ (34) ３）署名確認ステップ （１） 認証者AN+1は、署名者ANより通知された署名(T
1,T2,…,TN,SN)が正しい署名であることを以下の手順に
より確認する。
【００８５】[1]Tkと電子文書Ｍに対して次式を求め
る。 hk＝ｈ(Ｍ,Tk) (k＝1〜N) (35) [2]次の確認式が成り立つことを確認する。
【００８６】 TN'＝(ｇSN×y1-h1×y2-h2×…×yN-hN) mod ｐ ＝TN (36) ここで(36)式が成り立てば署名(T1,T2,…,TN,SN)が署名
者Aj(j＝1〜N)の正しい署名であると認識し、電子文書
Ｍと署名(T1,T2,…,TN,SN)を保存する。なお、正しく作
成された署名(T1,T2,…,Tj,Sj)に対して(29)、(36)式が
成り立つことは実施例１の(24)式場合と同様にして確か
められる。
【００８７】次に、実施例２の処理量および署名のデー
タ量は、実施例１の処理量と全く同じである。また安全
性についても同様の議論が成り立つ。
【００８８】なお、実施例２においては、ｐとして素数
を選んだが、ｐとして素数のべき乗に選んでも同様に構
成できる、だだしこの場合、乗算剰余演算（ａ×ｂmod
ｐ）を、ｐで規定される有限体上の乗算に置き換える。 〔実施例３〕実施例１では、署名者Ajの署名を(tj(j＝
１〜j),Sj)としたが、実施例１における(hj(j＝１〜j),
Sj)を署名とすることがきる。この方法を実施例３とし
て以下に説明する。
【００８９】図３は本発明の実施例３におけるディジタ
ル署名方式の構成を示すものである。実施例３も実施例
１と同様に、システムパラメータを決定するシステム管
理者と、N 人の署名者Aj(j＝1〜N) と認証者AN+1で構成
される。そして、N 人の署名者Aj(j＝1〜N)が、A1,A2,
…,ANの順番に、ある文書Ｍに対する署名を作成し、そ
の署名を認証者AN+1が確認する。以下同図を参照しなが
ら実施例２の動作を説明する。ただしシステム初期設定
ステップは実施例１と全く同じであるので省略し、署名
作成ステップ、署名確認ステップについて詳しく説明す
る。 ２）署名作成ステップ ユーザA1,A2,…,ANが、それぞれ署名者として、ある数
値データ化された電子文書Ｍに対して署名し、ユーザAN
+1が、認証者として、その署名を確認する場合について
説明する。なお署名者A1,A2,…,ANの署名順は署名者A1
→署名者A2→…→署名者ANの順とする。また署名者A2以
降は、先に署名を施した署名者の署名を確認した後署名
を行なう。 （１） 署名者A1は、署名作成用パラメータx1（秘密）
を用いて、電子文書Ｍに対して、以下の手順で署名(h1,
S1) を作成し、その署名を署名者A2に通知する。
【００９０】[1]ｑ未満の乱数r1を生成し、r1を一方向
性関数ｆに入力する。 t1＝gr1 mod ｐ (37) [2]電子文書Ｍとt1をハッシュ関数ｈに入力する。
【００９１】 h1＝ｈ(Ｍ,t1) (38) [3]署名作成用パラメータx1を用いて次式を計算する。
【００９２】 S1＝s1＝(h1×x1＋r1) mod ｑ (39) （２） 署名者Aj(j＝2〜N)は、それぞれ署名者Aj-1よ
り通知された署名(h1,h2,…,hj-1,Sj-1)が正しい署名で
あることを以下の手順により確認する。
【００９３】[1]次式よりTj-1'を求める。 Tj-1'＝ (ｇSj-1×y1-h1×y2-h2×…×yj-1-hj-1) mod ｐ (40) [2]このTj-1'と電子文書Ｍ、署名者Aj-1より通知された
hj-1に対してに対して次式が成り立つことを確認する。
【００９４】 hj-1＝ｈ(Ｍ,Tj-1') (41) ここで、(41)式が成り立てば署名者Aj-1(j＝2〜N)から
通知された署名(h1,h2,…,hj-1,Sj-1)が、署名者A1〜Aj
-1の署名の相違ないと認識する（この理由については後
述する）。
【００９５】次に、署名者Aj(j＝2〜N)は、以下の手順
で(hj,Sj) を作成し、(h1,h2,…,hj,Sj)を署名として次
の署名者（もしくは認証者）Aj+1(j＝2〜N)に通知す
る。
【００９６】[3]ｑ未満の乱数rjを生成し、rjを一方向
性関数ｆに入力する。 tj＝grj mod ｐ (42) [4]このtjおよび(28)式で求めたTj-1'よりTjを求める。
【００９７】 Tj＝tj×Tj-1' mod ｐ (43) [5]電子文書ＭとTjをハッシュ関数ｈに入力する。
【００９８】 hj＝ｈ(Ｍ,Tj) (44) [6]署名作成用パラメータxj（秘密）を用いて次式を計
算する。
【００９９】 sj＝(hj×xj＋rj) mod ｑ (45) [7]求めたsjと署名者Aj-1より受け取ったSj-1を用いて
次式を計算する。
【０１００】 Sj＝(sj＋Sj-1)＝(s1+s2+…sj-1) mod ｑ (46) ３）署名確認ステップ （１） 認証者AN+1は、それぞれ署名者ANより通知され
た署名(h1,h2,…,hN,SN)が正しい署名であることを以下
の手順により確認する。
【０１０１】[1]次式よりTN'を求める。 TN'＝ (ｇSN×y1-h1×y2-h2×…×yN-hN) mod ｐ (47) [2]このTN'と電子文書Ｍ、署名者ANより通知されたhNに
対して次式が成り立つことを確認する。
【０１０２】 hN＝ｈ(Ｍ,TN') (48) ここで(46)式が成り立てば署名(t1,t2,…,tN,SN)が署名
者Aj(j＝1〜N)の正しい署名であると認識し、電子文書
Ｍと署名(h1,h2,…,hN,SN)を保存する。ところで署名者
Aj(j=2〜N)が(41)式の成立を、また認証者AN+1が(48)式
の成立を確認することで、署名の正しさを確認できる。
なぜなら、 (47)式の左辺TN'＝(ｇSN×y1-h1×y2-h2×…×yN-hN) mod ｐ ＝ｇ(s1+s2+…+sN)×y1-h1×y2-h2×…×yN-hN) mod ｐ ((46)式より) ＝ｇs1×ｇs2×…ｇsN×y1-h1×y2-h2×…×yN-hN) mod ｐ ＝ｇ(h1*x1+r1)×ｇ(h2*x2+r2)…×ｇ(hN*xN+rN) ×y1-h1×y2-h2×…×yN-hN) mod ｐ ((45)式より) ＝(y1h1×ｇr1)×(y2h2×ｇr2)×…×(yNhN×ｇrN) ×y1-h1×y2-h2×…×yN-hN) mod ｐ ((12)式より) ＝ｇr1×ｇr2×…×ｇrN mod ｐ ＝(t1×t2×…×tN) mod ｐ ((19)式より) ＝TN ((16)式より) 故に、hN＝ｈ（Ｍ,TN）＝ｈ(Ｍ,TN')となるためであ
る。
【０１０３】次に、実施例３の処理量であるが、これに
ついては実施例１、２の処理量と同じである。また安全
性についても同様の議論が成り立つ。
【０１０４】次に、署名のデータ量は、以下のとおりと
なる。 (log2ｑ×(N+1)) ビット このように、実施例３は、実施例１、２と処理量的には
等しく、また安全性は同等であり、署名のデータ量は、
実施例１、２より減少できる。
【０１０５】なお、実施例３においては、ｐとして素数
を選んだが、ｐとして素数のべき乗に選んでも同様に構
成できる、だだしこの場合、乗算剰余演算（ａ×ｂmod
ｐ）を、ｐで規定される有限体上の乗算に置き換える。 〔実施例４〕図４は本発明の実施例４におけるディジタ
ル署名方式の構成を示すものである。実施例４も、実施
例１と同様に同図に示すように、システムパラメータを
決定するシステム管理者と、N 人の署名者Aj(j＝1〜N)
と認証者AN+1で構成される。そして、N 人の署名者Aj(j
＝1〜N)が、A1,A2,…,ANの順番に、ある文書Ｍに対する
署名を作成し、その署名を認証者AN+1が確認する。以下
同図を参照しながら実施例の動作をシステム初期設定ス
テップ、署名作成ステップ、署名確認ステップの順に詳
しく説明する。 １）システム初期設定ステップ （１） システムの管理者は、２素数ｐ、ｑと、その積
ｎを決定し、一方向性関数ｆとして ｆ(x)＝ｘe mod ｎ (49) と、ｅ以下の数値を生成するハッシュ関数ｈを決定し、
２素数ｐ，ｑを秘密に保持する一方、f(x)とｈを全ての
ユーザに通知する。 （２） システムの管理者は、上記一方向性関数ｆの逆
関数ｆ-1 ｆ-1(x)＝ｘd mod ｎ (50) を用いて、各ユーザAiの署名作成用のパラメータxiと署
名確認用のパラメータyiを作成する。
【０１０６】 xi＝ｆ-1(yi)＝yid mod ｎ (51) このようにして求めた署名作成用のパラメータxiはユー
ザAiに秘密に配布する。
【０１０７】ここで注意すべきことは、システム管理者
以外は、前記関数ｆの逆関数ｆ-1を計算できないという
ことである。つまり、ユーザにとってはｆは一方向性関
数といえる。一方システム管理者は、関数ｆの逆関数ｆ
-1を計算できるため、署名確認用パラメータyiをさきに
決めて、それに対応する署名作成用パラメータを求める
ことができる。このことを利用すれば、署名確認用パラ
メータyiとして、ユーザAiの識別情報（識別情報とは、
名前や住所といった他のユーザに広く知られた情報のこ
とである）を用いることが可能となる。すなわち、実施
例４は、実施例１、２、３と比較すると、いわゆる識別
情報に基づくディジタル署名法が構成できるため、署名
確認用パラメータyiの正当性の確認や管理が容易とな
る。 ２）署名作成ステップ ここでは、ユーザA1,A2,…,ANが、それぞれ署名者とし
て、ある数値データ化された電子文書Ｍに対して署名
し、ユーザAN+1が、認証者として、その署名を確認する
場合について説明する。なお署名者A1,A2,…,ANの署名
順は署名者A1→署名者A2→…→署名者ANの順とする。ま
た署名者A2以降は、先に署名を施した署名者の署名を確
認した後署名を行なう。 （１） 署名者A1は、署名作成用の秘密パラメータX1を
用いて、電子文書Ｍに対して、以下の手順で署名(t1,S
1) を作成し、その署名を署名者A2に通知する。
【０１０８】[1]乱数r1を生成し、r1を一方向性関数ｆ
に入力する。 t1＝r1e mod ｎ (52) [2]電子文書Ｍとt1をハッシュ関数ｈに入力する。
【０１０９】 h1＝ｈ(Ｍ,t1) (53) [3]署名作成用秘密パラメータx1を用いて次式を計算す
る。
【０１１０】 S1＝(x1h1×r1) mod ｎ (54) （２） 署名者Aj(j＝2,3,…,N)は、A2,A3,…,ANの順番
で、それぞれ署名者Aj-1より通知された署名(Sj-1,tk(k
＝1,2,…,j-1))が正しい署名であることを以下の手順に
より確認する。
【０１１１】[1]署名tkに対して次式を求める。 Tj-1＝(t1×t2×…×tj-1) mod ｎ (55) [2]tkと電子文書Ｍに対して次式を求める。
【０１１２】 hk＝ｈ(Ｍ,tk) (k＝1,2,…,j-1) (56) [3]次式が成り立つことを確認する。
【０１１３】 Tj-1'＝(Sj-1e×y1-h1×y2-h2×…×yj-1-hj-1) mod ｎ ＝ Tj-1 (57) ここで、(57)式が成り立てば署名者Aj-1(j＝2〜N)から
通知された署名(h1,h2,…,hj-1,Sj-1)が、署名者A1〜Aj
-1の署名の相違ないと認識する（この理由については後
述する）。
【０１１４】次に、署名者Aj(j＝2〜N)は、以下の手順
で(hj,Sj) を作成し、(h1,h2,…,hj,Sj)を署名として次
の署名者（もしくは認証者）Aj+1(j＝2〜N)に通知す
る。
【０１１５】[4]乱数rjを生成し、rjを一方向性関数ｆ
に入力する。 tj＝rje mod ｎ (58) [5]電子文書Ｍとtjをハッシュ関数ｈに入力する。
【０１１６】 hj＝ｈ(Ｍ,tj) (59) [6]署名作成用秘密パラメータxjを用いて次式を計算す
る。
【０１１７】 sj＝(xjhj×rj) mod ｎ (60) [7]sj,Sj-1を用いて次式を計算する。
【０１１８】 Sj＝(sj×Sj-1) mod ｎ (61) （３） 署名認証者AN+1は、署名者ANより通知された署
名(t1,t2,…,tN,SN)が正しい署名であることを以下の手
順により確認する。
【０１１９】[1]署名tkに対して次式を求める。 TN＝(t1×t2×…×tN) mod ｎ (62) [2]tkと電子文書Ｍに対して次式を求める。
【０１２０】 hk＝ｈ(Ｍ,tk) (k＝1〜N) (63) [3]次の確認式が成り立つことを確認する。
【０１２１】 TN'＝(SNe×y1-h1×y2-h2×…×yN-hN) mod ｎ ＝TN (64) ここで(64)式が成り立てば署名(t1,t2,…,tN,SN)が署名
者Aj(j＝1〜N)の正しい署名であると認識し、電子文書
Ｍと署名(t1,t2,…,tN,SN)を保存する。ところで署名者
Aj(j=2〜N)が(57)式の成立を、また認証者AN+1が(64)式
の成立を確認することで、署名の正しさを確認できる。
なぜなら、 (64)式の左辺TN'＝(SNe×y1-h1×y2-h2×…×yN-hN) mod ｎ ＝((S1×S2×…×SN)e×y1-h1×y2-h2×…×yN-hN) mod ｎ （(61)式より) ＝(x1h1×r1)e×(x2h2×r2)e×…×(xNhN×rN)e ×y1-h1×y2-h2×…×yN-hN) mod ｎ （(60)式より) ＝(y1h1×t1)×(y2h2×t2)×…×(yNhN×tN) ×y1-h1×y2-h2×…×yN-hN) mod ｎ ＝(t1×t2×…×tN) mod ｎ ((58)式より) ＝TN ((55)式より) となるためである。
【０１２２】以上が実施例４の構成と動作である。次
に、実施例４における処理量を示す。ここでは、処理量
を従来例の場合と同様に、ｎの桁数(log2ｎビット)程度
の数値に対する乗算剰余演算の回数で表わすことにす
る。これはlog2ｎビット幅の乗算剰余演算の処理が、署
名作成処理および署名確認処理の大部分を占めるためで
ある。また、各計算回数は、従来例のところで述べた高
次の高速指数演算法を用いて計るものとする。また実施
例１と同様に、条件(H2)を満たすために、高々10次以下
の高速指数演算法を用いるものとする。そして、10次以
上のべき乗剰余演算が必要な場合には、10次以下の高速
指数演算法を、繰り返し利用するものとする。なお(52)
式〜(61)式における各べき数hi(i＝1〜N)は、ｅと同程
度の桁数(log2ｅビット)の数値である。
【０１２３】このとき、署名者数N が、 10×(L-1)＜N≦10×L の場合、まず署名作成者Ai(ｉ＝１〜N）の各処理量は、
以下のとおりとなる。
【０１２４】 署名の作成：平均 〔2×{2−(1/2) }×log2ｅ〕 回 署名の確認：平均 〔{2×log2ｅ×J〕 回 （ただし、10×(J-1)＜j≦10×Jとする） 同様に、認証者AN+1の処理は、以下のとおりとなる。
【０１２５】署名の確認：平均 〔{2×log2ｅ×L〕回 例えば、認証者の署名確認に、ｅを500ビットに選ぶと
き高々1000×L回程度の乗算剰余演算が必要となり、ｅ
を150ビット程度に選ぶ場合、高々300 ×L回程度の乗算
剰余演算が必要となる。このことから、ｅを従来例１の
ｑと同程度の桁数（500ビット)とするとき、第４の実施
例の署名確認の処理量は、実施例１と同様に、従来例１
より最大約1/10に削減できる。
【０１２６】ところで実施例１における署名のデータ量
は、 (log2ｎ×(N＋1)) ビット となる。
【０１２７】次に実施例４の安全性について説明する。
安全性については (1)署名作成用のパラメータを解読する攻撃に対する安
全性。
【０１２８】(2)偽の署名を偽造する攻撃に対する安全
性。 の２つの点について調べる必要がある。
【０１２９】(1)について、まずyiから直接xi求めるこ
とは、ＲＳＡ暗号を解読ことに帰着される。すなわち、
このためには合成数ｎを素因数分解する必要があり、ｎ
を250 ビット程度の２つの素数の積とすれば事実上困難
とされている。またxiを悉皆的に探索する攻撃に対して
も、ｎを500 ビット程度とすれば事実上困難である。
【０１３０】一方、偽の文書M'に対する偽造署名を作成
する攻撃については、まずtk'を適当に与えて確認式を
満たすSk<を求める攻撃に対しては、やはりＲＳＡ暗号
を解読する問題に帰着される。次にSk'を適当に与えて
確認式を満たすtk'を求める攻撃に対しては、yh(t,M')
＝ｔmod ｎを満たすｔを求めることに帰着される。こ
れについては、やはりｎを500ビット、hの出力を150ビ
ット程度とすれば、事実上困難であると予想される。
【０１３１】なお実施例４では、実施例１と同様の構成
で、(t1,t2,…,tN,SN)を署名とする構成について説明し
たが、実施例２と同様に(T1,T2,…,TN,SN)を署名として
も構成でき、また実施例３と同様に(h1,h2,…,hN,SN)を
署名としても構成できる。 〔実施例５〕図５は本発明の実施例５におけるディジタ
ル署名方式の構成を示すものである。実施例５も、実施
例１と同様に同図に示すように、システムパラメータを
決定するシステム管理者と、N 人の署名者Aj(j＝1〜N)
と認証者AN+1で構成される。そして、N 人の署名者Aj(j
＝1〜N)が、A1,A2,…,ANの順番に、ある文書Ｍに対する
署名を作成し、その署名を認証者AN+1が確認する。以下
同図を参照しながら実施例の動作をシステム初期設定ス
テップ、署名作成ステップ、署名確認ステップの順に詳
しく説明する。 １）システム初期設定ステップ （１） システムの管理者は、素数ｐとｐを法とする剰
余体上で定義される楕円曲線Ｅを決定する。そしてこの
楕円曲線Ｅ上の点で構成される加法群に属する元で、あ
る数値ｑでスカラー倍倍すると初めて点∞（ここで点∞
は楕円曲線Ｅ上で定義される加法に関する単位元であ
る）に一致する点Ｇを基本点として決定する。そして一
方向性関数ｆとして、入力ｘに対して基本点Ｇのｘ倍点
を求める関数とする。
【０１３２】 ｆ(ｘ)＝ｘ×Ｇ (on Ｅ) (65) また、いくつかの入力データに対して、それらの入力デ
ータに依存し、かつ、ここでは前述のｑ以下の数値を生
成するハッシュ関数ｈを決定し、全てのユーザに通知す
る。 （２） 各ユーザAiは、それぞれｑ未満の署名作成用の
パラメータxi(秘密)を生成し、これを秘密の保持する一
方、その秘密パラメータxiをシステム管理者より通知さ
れている一方向性関数ｆ(x)に入力して、署名確認用の
パラメータＹi Ｙi＝xi×Ｇ (on Ｅ) (66) を生成し、このＹiを、他のユーザに通知する。このと
き署名確認用のパラメータＹiは、楕円曲線上のある点
となる。 ２）署名作成ステップ ここでは、ユーザA1,A2,…,ANが、それぞれ署名者とし
て、ある数値データ化された電子文書Ｍに対して署名
し、ユーザAN+1が、認証者として、その署名を確認する
場合について説明する。なお署名者A1,A2,…,ANの署名
順は署名者A1→署名者A2→…→署名者ANの順とする。ま
た署名者A2以降は、先に署名を施した署名者の署名を確
認した後署名を行なう。 （１） 署名者A1は、署名作成用の秘密パラメータx1を
用いて、電子文書Ｍに対して、以下の手順で署名(S1,h
1) を作成し、その署名を署名者A2に通知する。
【０１３３】[1]ｑ未満の乱数r1を生成し、r1を一方向
性関数ｆに入力する。 Ｔ1＝r1×Ｇ (on Ｅ) (67) ここで、Ｔ1は楕円曲線上の点である。
【０１３４】[2]電子文書Ｍと楕円曲線上の点Ｔ1をハッ
シュ関数ｈに入力する。 h1＝ｈ(Ｍ,Ｔ1) (68) [3]署名作成用秘密パラメータx1を用いて次式を計算す
る。
【０１３５】 S1＝(h1×x1＋r1) mod ｑ (69) （２） 署名者Aj(j＝2〜N)は、A2,A3,…,ANの順番で、
それぞれ署名者Aj-1(j＝2〜N)より通知された署名(h1,h
2,…,hj-1,Sj-1)が正しい署名であることを以下の手順
により確認する。
【０１３６】[1]次式よりＶj-1'を求める。 Ｖj-1'＝(Sj-1×Ｇ−h1×Ｙ1−h2×Ｙ2×…−hj-1×Ｙj-1) (on Ｅ) (70) [2]Ｖj-1'と電子文書Ｍおよびhj-1に対して次式が成り
立つことを確認 する。
【０１３７】 hj-1＝ｈ(Ｍ,Ｖj-1') (71) ここで、(71)式が成り立てば署名者Aj-1(j＝2〜N)から
通知された署名(h1,h2,…,hj-1,Sj-1)が、署名者A1〜Aj
-1の署名の相違ないと認識する（この理由については後
述する）。
【０１３８】次に、署名者Aj(j＝2〜N)は、以下の手順
で(hj,Sj) を作成し、(h1,h2,…,hj,Sj)を署名として次
の署名者（もしくは認証者）Aj+1(j＝2〜N)に通知す
る。
【０１３９】[3]ｑ以下の乱数rjを生成し、rjを一方向
性関数ｆに入力する。 Ｔj＝rj×Ｇ (on Ｅ) (72) [4]Ｖjを求める。
【０１４０】 Ｖj＝(Ｔj＋Ｖj-1) (on Ｅ) (73) [5]電子文書ＭとＴjをハッシュ関数ｈに入力する。
【０１４１】 hj＝ｈ(Ｍ,Ｔj) (74) [6]署名作成用秘密パラメータxjを用いて次式を計算す
る。
【０１４２】 sj＝(hj×xj＋rj) mod ｑ (75) [7]次式を計算する。
【０１４３】 Sj＝(sj＋Sj-1) mod ｑ (76) （３） 署名認証者AN+1は、署名者ANより通知された署
名(h1,h2,…,hN,SN)が正しい署名であることを以下の手
順により確認する。
【０１４４】[1]次式よりＶN'を求める。 ＶN'＝(SN×Ｇ−h1×Ｙ1−h2×Ｙ2×…−hN×ＹN) (on Ｅ) (77) [2]ＶN'と電子文書ＭおよびhNに対して次式が成り立つ
ことを確認する。
【０１４５】 hN＝ｈ(Ｍ,ＶN') (78) ここで(78)式が成り立てば署名(h1,h2,…,hN,SN)が署名
者Aj(j＝1〜N)の正しい署名であると認識し、電子文書
Ｍと署名(h1,h2,…,hN,SN)を保存する。ところで署名者
Aj(j=2〜N)が(71)式の成立を、また認証者AN+1が(78)式
の成立を確認することで、署名の正しさを確認できる。
なぜなら、 (77)式の左辺ＶN'＝(SN×Ｇ−h1×Ｙ1−h2×Ｙ2×…−hN×ＹN) (on Ｅ) ＝((s1＋s2＋…＋sN)×Ｇ −h1×Ｙ1−h2×Ｙ2 ×…−hN×ＹN) (on Ｅ) （(76)式より ） ＝((h1×x1＋r1)Ｇ＋(h2×x2＋r2)Ｇ＋…＋(hN×xN＋rN)Ｇ −h1×Ｙ1−h2×Ｙ2×…−hN×ＹN) (on Ｅ) （(75)式より ） ＝((h1×Ｙ1＋Ｔ1)＋(h2×Ｙ2＋Ｔ2)＋…＋(hN×ＹN＋ＴN) −h1×Ｙ1−h2×Ｙ2×…−hN×ＹN) (on Ｅ) （(66),(72)式よ り） ＝(Ｔ1＋Ｔ2＋…＋ＴN) (on Ｅ) ＝ＶN （(73)式より） 故に、hN＝ｈ(Ｍ,ＶN)＝ｈ(Ｍ,ＶN')となるためであ
る。
【０１４６】以上が実施例５の構成と動作である。次
に、実施例５における処理量について述べる。実施例５
では、楕円曲線上の点に対するスカラー倍演算が、その
処理の大半を占める。ところで、楕円曲線上の点に対す
るスカラー倍演算に対しても、高速指数演算法と同様の
アルゴリズムが利用できる。ただしこの場合、べき乗剰
余演算を、楕円曲線上の点に対するスカラー倍演算とみ
なし、乗算剰余演算を楕円曲線上の点に対する加算とみ
なす。つまり、高速指数演算法と同様の方法で、楕円曲
線におけるある点のスカラー倍演算を、楕円曲線上の点
に対する加算を実行できる。これは高速指数演算をいわ
ばその対数領域で行なうことに相当する。以下、この方
法を楕円曲線に関する高速加算演算法と呼ぶことにす
る。そして、高次の高速指数演算法の場合と同様に、楕
円曲線に関する高次の高速加算演算法を定義するものと
する。
【０１４７】上述の事柄を踏まえると、実施例５におい
ては、楕円曲線上の点の加算演算が基本となる。従って
ここでは、楕円曲線上の点の加算演算の回数で各処理量
を計ることができる。なお、他の演算に必要な処理は、
楕円曲線上の点の加算演算の処理量に比べると、無視で
きるほど小さいと仮定できる。
【０１４８】また各処理における楕円曲線上のスカラー
倍演算には、上述の高次の高速加算演算法を用いる場合
を想定する。
【０１４９】ただし、ｋ次の高速加算演算法が有効とな
る(H2)の条件〔2k+1/k＜3×log2ｙ〕（kは被加数の個
数、log2ｙはスカラー倍数の桁数（ビット数）を満たす
ために、10次以下の高速加算演算法を利用するものとす
る（なぜならいま乗数の桁数log2ｑは150以上としてい
るためである）。従って実施例１と同様に、10次以上の
スカラー倍演算が必要な場合には、その演算をいくつか
の10次以下のスカラー倍演算に分割し、それに対して10
以下の高速加算演算法を用いるものとする。
【０１５０】なお(65)式〜(78)式における数値ri,Si,hi
((i＝1〜N) は、ｑと同程度の桁数(log2ｑビット)の数
値であるとしている。
【０１５１】このとき、署名者数Nが 10×(L-1)＜N ≦10×L とするとき、署名作成者Ai(ｉ＝１〜N）の各処理量は、
以下のとおりとなる。
【０１５２】 署名の作成：平均 〔2×{2−(1/2) }×log
2ｑ〕 回 署名の確認：平均（高々) 〔2×log2ｑ×J〕 回 (但し、Jは、10×(J-1)＜j ≦10×J を満たす数とす
る) 同様に、認証者AN+1の処理は、以下のとおりとなる。
【０１５３】 署名の確認：平均（高々) 〔2×log2ｑ×L〕回 なお、楕円曲線上の加算１回に必要な処理量は、従来例
や他の実施例における乗算剰余演算１回とほぼ等しいと
すると、実施例５における署名確認の処理量は、従来例
１に比較して最大1/10に削減できる。
【０１５４】次に実施例５における署名のデータ量は、 (log2ｑ×(N＋1)) ビット となる。
【０１５５】実施例５の安全性についても、実施例１と
同様の議論が成り立つ。ただし実施例５の安全性は、楕
円曲線上で定義される離散対数問題すなわち ｆ(ｘ)＝ｘ×Ｇ (on Ｅ) において、f(x)、Ｇ、Ｅが与えられたときにｘを求める
問題の困難性に帰着する。
【０１５６】なお実施例５では、実施例３と同様に(h1,
h2,…,hN,SN)を署名とする構成について説明したが、実
施例１と同様にして、(Ｔ1,Ｔ2,…,ＴN,SN)を署名とし
て構成することも、また、実施例２と同様にして、(Ｔ
1,Ｔ2,…,ＴN,SN)を署名として構成することもできる。
【０１５７】
【発明の効果】以上の説明から明らかなように本発明
は、上述の構成により、複数の署名者Ai（i＝1〜N）が
生成した、数値データ化された電子文書Ｍに対する署名
(t1,t2,…,tN,SN）に対して、認証者AN+1 が、署名者Ai
（i＝1〜N）の真の署名であるかどうかの確認を一括し
て行える。このとき、高速指数演算法を利用すること
で、処理量を削減できる。また、署名者A1を除く各署名
者Ai（i＝2〜N）は、各自の署名を生成する前に、署名
順序が先の署名者Ai-1（i＝2〜N）より通知された署名
(t1,t2,…,ti-1,Si-1)に対して、署名者Ai-1（i＝2〜
N）の真の署名かどうかの確認を一括して実行できる。
このとき、高速指数演算法を利用することで、処理量を
削減できる。
【０１５８】また署名としてハッシュ関数の出力hiを用
いることで署名のデータ量を小さくすることができる。
【図面の簡単な説明】
【図１】本発明の第１の実施例におけるディジタル署名
方式の構成図である。
【図２】本発明の第２の実施例におけるディジタル署名
方式の構成図である。
【図３】本発明の第３の実施例におけるディジタル署名
方式の構成図である。
【図４】本発明の第４の実施例におけるディジタル署名
方式の構成図である。
【図５】本発明の第５の実施例におけるディジタル署名
方式の構成図である。
【図６】従来例１の構成によるディジタル署名方式の構
成図である。
【符号の説明】
１０ システム管理者 ２０ 署名者Ai(ｉ＝1〜Ｎ) ３０ 認証者AN

Claims (6)

    【特許請求の範囲】
  1. 【請求項１】コンピュータや通信ネットワークを利用し
    て送受信される、あるいは蓄積される数値データたる電
    子文書Ｍの正当性を、複数の署名者の作成した数値デー
    タたるディジタル署名によって確認するディジタル署名
    方式において、 複数の署名者Ai(ｉ＝1〜N)が、前記電子文書Ｍに対する
    ディジタル署名を作成する署名作成ステップと、認証者
    AN+1が、前記各署名者Ai(ｉ＝1〜N)が作成した署名の正
    しさを確認する署名確認ステップとを有し、 前記各署名者Ai(ｉ＝1〜N)および認証者AN+1は、それぞ
    れ、共通の一方向性関数ｆと、共通のハッシュ関数ｈ
    と、前記各署名者Ai(ｉ＝1〜N)の署名確認用パラメータ
    yi(ｉ＝1,2,…,N)を保持しており、また、前記各署名者
    Aiは、それぞれ署名作成用パラメータxiを秘密に保持し
    ており、 前記一方向性関数ｆは、２つのデータd1、d2に対する第
    １の演算op1 の結果op1〔d1,d2〕を、その入力値とする
    ときの出力値ｆ(op1〔d1,d2〕)が、前記データd1をその
    入力値とするときの出力値ｆ(d1)と前記データd2に対す
    る第２の演算op2 の結果op2{ｆ(d1),d2}に等しくなり、
    かつ２つ以上のデータd1,d2,…,dn (n≧2)に対する第３
    の演算op3 の結果op3〔d1,d2,…,dn〕を、その入力値と
    するときの出力値ｆ(op3〔d1,d2,…,dn〕)が、前記各デ
    ータd1,d2,…,dn のそれぞれをその入力値とするときの
    各出力値ｆ(d1),ｆ(d2),…,ｆ(dn)に対する第４の演算o
    p4の結果op4〔ｆ(d1),ｆ(d2),…,ｆ(dn)〕に等しくなる
    関数とし、特に、この第４の演算op4の結果op4〔ｆ(d
    1),ｆ(d2),…,ｆ(dn)〕 を求めるのに、高速指数演算法
    を拡張した高次の高速指数演算法を用いるものとし、 また、前記ハッシュ関数ｈは、一つ以上の入力データ{d
    i(i≧１)}に対して、その各入力値に依存し、かつある
    定められた数値以下の出力データｈ(d1,h2,…,hi)を出
    力する関数とし、 前記署名確認用パラメータyiと前記署名作成用パラメー
    タxiは、前記署名確認用パラメータyiが前記署名作成用
    パラメータxiを前記一方向性関数ｆに入力したときの出
    力ｆ(xi)に等しくなるように署名者自身もしくは第３の
    信頼のおける機関によって生成されるものとし、 前記署名作成ステップは、前記署名者A1が、秘密に乱数
    r1を生成し、前記乱数r1を前記一方向性関数ｆに入力し
    てt1＝ｆ(r1)を求め、このt1と前記電子文書Ｍを前記ハ
    ッシュ関数ｈに入力してh1＝ｈ(Ｍ,t1) を求め、このh1
    と前記署名作成用パラメータx1に対する前記第１の演算
    op1 の結果op1〔h1,x1〕と、前記乱数r1に対する前記第
    ３の演算op3 の結果s1＝op3〔op1〔h1,x1〕,r1〕を求
    め、前記{t1,S1} を署名者A1の署名として前記電子文書
    Ｍとともに署名者A2に通知するステップと、 各署名者Aj(j＝2〜N)が、A2,A3,…,ANの順番に、それぞ
    れ署名順が一つ前の署名者Aj-1(j＝2〜N)より通知され
    た署名{t1,t2,…,tj-1,Sj-1} に対して、まず、前記署
    名{t1,t2,…,tj-1}に対する前記第４の演算op4 の演算
    結果Tj-1＝op4〔t1,t2,…,tj-1〕を求め、次に前記電子
    文書Ｍと前記署名{tk} (k＝1〜j-1) をそれぞれ前記ハ
    ッシュ関数ｈに入力してhk＝ｈ(Ｍ,tk) (k＝1〜j-1) を
    求め、このhk(k＝1〜j-1)と前記署名確認用パラメータy
    k(k＝1〜j-1) に対する前記第２の演算op2の演算結果op
    2〔yk,hk〕(k＝1,2,…,j-1) の、前記第４の演算op4 に
    関する逆数op2〔yk,hk〕-1 (k＝1〜j-1)と、前記署名Sj
    -1を前記一方向性関数ｆに入力して得られる出力値ｆ(S
    j-1)とに対する前記第４の演算op4の演算結果Tj-1'＝op
    4〔ｆ(Sj-1),op2〔y1,h1〕-1,op2〔y2,h2〕-1,…,op2
    〔yj-1,hj-1〕-1〕 を求め、この演算結果Tj-1'が前記T
    j-1に一致すれば前記署名{t1,t2,…,tj-1,Sj-1}が前記
    電子文書Ｍに対する署名者Aj-1(j＝2〜N)の署名である
    と認識するステップと、 前記署名者Aj(j＝2〜N) が乱数rjを生成し、この乱数rj
    を前記一方向性関数ｆに入力してtj＝ｆ(rj)を求め、前
    記電子文書Ｍと前記tjを前記ハッシュ関数ｈに入力して
    得られる出力値hj＝ｈ(Ｍ,tj) と前記署名作成用パラメ
    ータxjに対する前記第１の演算op1 の演算結果op1〔hj,
    xj〕と、前記乱数rjに対する前記第３の演算op3 の演算
    結果sj＝op3〔op1〔hj,xj〕,rj〕を求め、この結果sjと
    前記署名Sj-1に対する前記第３の演算op3 の演算結果Sj
    ＝op3〔Sj-1,sj〕を求め、前記{t1,t2,…,tj,Sj}を前記
    署名者Ajの署名として、前記電子文書Ｍとともに次の署
    名者または認証者であるAj+1(j＝2〜N) に通知するステ
    ップとから構成され、 前記署名確認ステップは、前記認証者AN+1が、前記署名
    者ANより通知された署名{t1,t2,…,tN,SN}と電子文書Ｍ
    より、まず、署名{tk}(k＝1〜N) に対する前記第４の演
    算op4 の演算結果TN＝op4〔t1,t2,…,tN〕を求め、次
    に、前記電子文書Ｍと前記署名{tk} (k＝1〜N)をそれぞ
    れ前記ハッシュ関数ｈに入力したときの出力hk＝ｈ(Ｍ,
    tk)(k＝1〜N)と前記署名確認用パラメータyk(k＝1〜N)
    に対する前記第２の演算op2 の演算結果op2〔yk,hk〕(k
    ＝1〜N) の、前記第４の演算op4に関する逆数op2〔yk,h
    k〕-1 (k＝1〜N)と、前記署名SNを前記一方向性関数ｆ
    に入力して得られる出力値ｆ(SN)とに対する、前記第４
    の演算op4 の演算結果TN'＝op4〔ｆ(SN),op2〔y1,h1〕
    -1,op2〔y2,h2〕-1,…,op2〔yN,hN〕-1〕 を求め、この
    演算結果TN'が前記TNに一致すれば前記署名{t1,t2,…,t
    N,SN}が前記電子文書Ｍに対する署名者Ak(k＝1〜N) の
    署名であると認識するステップから構成されるディジタ
    ル署名方式。
  2. 【請求項２】 署名作成ステップは、署名者A1が、秘密
    に乱数r1を生成し、前記乱数r1を一方向性関数ｆに入力
    してT1＝t1＝ｆ(r1)を求め、このT1と電子文書Ｍをハッ
    シュ関数ｈに入力してh1＝ｈ(Ｍ,T1) を求め、このh1と
    前記署名作成用パラメータx1に対する前記第１の演算op
    1 の結果op1〔h1,x1〕と、前記乱数r1に対する前記第３
    の演算op3 の結果s1＝op3〔op1〔h1,x1〕,r1〕を求め、
    前記{T1,S1} を署名者A1の署名として前記電子文書Ｍと
    ともに署名者A2に通知するステップと、 各署名者Aj(j＝2〜N)が、A2,A3,…,ANの順番に、それぞ
    れ署名順が一つ前の署名者Aj-1(j＝2〜N)より通知され
    た署名{T1,T2,…,Tj-1,Sj-1} に対して、まず、前記電
    子文書Ｍと前記署名{Tk} (k＝1〜j-1)をそれぞれ前記ハ
    ッシュ関数ｈに入力してhk＝ｈ(Ｍ,Tk) (k＝1〜j-1) を
    求め、このhk(k＝1〜j-1)と前記署名確認用パラメータy
    k(k＝1〜j-1) に対する前記第２の演算op2の演算結果op
    2〔yk,hk〕(k＝1,2,…,j-1) の、前記第４の演算op4 に
    関する逆数op2〔yk,hk〕-1 (k＝1〜j-1)と、前記署名Sj
    -1を前記一方向性関数ｆに入力して得られる出力値ｆ(S
    j-1)とに対する前記第４の演算op4 の演算結果Tj-1'＝o
    p4〔ｆ(Sj-1),op2〔y1,h1〕-1,op2〔y2,h2〕-1,…,op2
    〔yj-1,hj-1〕-1〕 を求め、この演算結果Tj-1'が前記T
    j-1に一致すれば前記署名{T1,T2,…,Tj-1,Sj-1}が前記
    電子文書Ｍに対する署名者Aj-1(j＝2〜N)の署名である
    と認識するステップと前記署名者Aj(j＝2〜N) が乱数rj
    を生成し、この乱数rjを前記一方向性関数ｆに入力して
    tj＝ｆ(rj)を求め、このtjと前記署名Tj-1に対する前記
    第４の演算op4 の演算結果Tj＝op4〔tj,Tj-1〕を求め、
    前記電子文書Ｍと前記Tjを前記ハッシュ関数ｈに入力し
    て得られる出力値hj＝ｈ(Ｍ,Tj) と前記署名作成用パラ
    メータxjに対する前記第１の演算op1 の演算結果op1〔h
    j,xj〕と、前記乱数rjに対する前記第３の演算op3 の演
    算結果sj＝op3〔op1〔hj,xj〕,rj〕を求め、この結果sj
    と前記署名Sj-1に対する前記第３の演算op3 の演算結果
    Sj＝op3〔Sj-1,sj〕を求め、前記{T1,T2,…,Tj,Sj}を前
    記署名者Ajの署名として、前記電子文書Ｍとともに次の
    署名者または認証者であるAj+1(j＝2〜N) に通知するス
    テップとから構成され、 前記署名確認ステップは、前記認証者AN+1が、前記署名
    者ANより通知された署名{T1,T2,…,TN,SN}と電子文書Ｍ
    より、まず、前記電子文書Ｍと前記署名{Tk} (k＝1〜N)
    をそれぞれ前記ハッシュ関数ｈに入力したときの出力hk
    ＝ｈ(Ｍ,Tk)(k＝1〜N)と前記署名確認用パラメータyk(k
    ＝1〜N) に対する前記第２の演算op2の演算結果op2〔y
    k,hk〕(k＝1〜N) の、前記第４の演算op4 に関する逆数
    op2〔yk,hk〕-1 (k＝1〜N)と、前記署名SNを前記一方向
    性関数ｆに入力して得られる出力値ｆ(SN)とに対する、
    前記第４の演算op4 の演算結果TN'＝op4〔ｆ(SN),op2
    〔y1,h1〕-1,op2〔y2,h2〕-1,…,op2〔yN,hN〕-1〕 を
    求め、この演算結果TN'が前記TNに一致すれば前記署名
    {T1,T2,…,TN,SN}が前記電子文書Ｍに対する署名者Ak(k
    ＝1〜N) の署名であると認識するステップから構成され
    る請求項１記載のディジタル署名方式。
  3. 【請求項３】 署名作成ステップが、署名者A1が、秘密
    に生成した乱数r1を前記一方向性関数ｆに入力したとき
    の出力t1＝ｆ(r1)を求め、また、前記電子文書Ｍと前記
    t1を前記ハッシュ関数ｈに入力したときの出力h1＝ｈ
    (Ｍ,t1) を求め、この出力h1と前記署名作成用パラメー
    タx1に対する前記第１の演算op1 の演算結果op1〔h1,x
    1〕と、前記乱数r1に対する前記第３の演算op3 の演算
    結果S1＝op3〔op1〔h1,x1〕,r1〕を求め、前記{h1,S1}
    を前記署名者A1の署名として、前記電子文書Ｍとともに
    署名者A2に通知するステップと、 署名者Aj(j＝2〜N)が、A2,A3,…,ANの順に、署名順が一
    つ前の署名者Aj-1(j-1＝2〜N) より通知された前記署名
    {h1,h2,…,hj-1,Sj-1}と電子文書Ｍより、まず、前記署
    名hkと前記署名確認用パラメータyk(k＝1〜j-1) に対す
    る前記第２の演算op2 の演算結果op2〔yk,hk〕(k＝1〜j
    -1) の、前記第４の演算op4 に関する逆数op2〔yk,hk〕
    -1 (k＝1〜j-1)と、前記署名Sj-1を前記一方向性関数ｆ
    に入力して得られる出力値ｆ(Sj-1)とに対する前記第４
    の演算op4 の演算結果Tj-1'＝op4〔ｆ(Sj-1),op2〔y1,h
    1〕-1,op2〔y2,h2〕-1,…,op2〔yj-1,hj-1〕-1〕を求
    め、この演算結果Tj-1' と前記電子文書Ｍを前記ハッシ
    ュ関数ｈに入力したときの出力hj-1'＝h(Ｍ,Tj-1') が
    前記hj-1に一致すれば前記署名{h1,h2,…,hj-1,Sj-1}が
    前記電子文書Ｍに対する署名者Ak(k＝1〜j-1) の署名で
    あると認識するステップと、 前記署名者Aj(j＝2〜N) が、乱数rjを生成し、この乱数
    rjを前記一方向性関数ｆに入力してtj＝ｆ(rj)を求め、
    このtjと前記Tj-1'(＝Tj-1)に対する前記第４の演算op4
    の演算結果Tj＝op4〔tj,Tj-1'〕を求め、前記電子文書
    Ｍと前記Tjを前記ハッシュ関数ｈに入力して得られる出
    力値hj＝ｈ(Ｍ,Tj) と前記署名作成用パラメータxjに対
    する前記第１の演算op1 の演算結果op1〔hj,xj〕と、前
    記乱数rjに対する前記第３の演算op3 の演算結果sj＝op
    3〔op1〔hj,xj〕,rj〕を求め、この結果sjと前記署名Sj
    -1に対する前記第３の演算op3 の演算結果Sj＝op3〔Sj-
    1,sj〕を求め、前記{h1,h2,…,hj,Sj}を署名者Ajの署名
    として、前記電子文書Ｍとともに次の署名者または認証
    者であるAj+1(j＝2〜N) に通知するステップとから構成
    され、 署名確認ステップは、認証者AN+1が、署名者ANより通知
    された前記署名{h1,h2,…,hN),SN}と電子文書Ｍより、
    まず、前記署名hk(k＝1〜N) と前記署名確認用パラメー
    タyk(k＝1〜N) に対する前記第２の演算op2 の演算結果
    op2 〔yk,hk〕(k＝1〜N) の、前記第４の演算op4 に関
    する逆数op2〔yk,hk〕-1(k＝1〜N)と、前記署名SNを前
    記一方向性関数ｆに入力して得られる出力値ｆ(SN)とに
    対する、前記第４の演算op4 の演算結果TN'＝op4〔ｆ(S
    N),op2〔y1,h1〕-1,op2〔y2,h2〕 -1,…,op2〔yN,h
    N〕-1〕を求め、この演算結果TN' と前記電子文書Ｍを
    前記ハッシュ関数ｈに入力したときの出力hN'＝h(Ｍ,T
    N') が前記hNに一致すれば前記署名{h1,h2,…,hN,SN}が
    前記電子文書Ｍに対する署名者Ak(k＝1〜N) の署名であ
    ると認識するステップから構成される請求項１記載のデ
    ィジタル署名方式。
  4. 【請求項４】 一方向性関数ｆが、素数もしくは素数の
    べき乗値である数値ｐを用いて構成される有限体上で定
    義される関数で、(ｐ−１)の約数である数値ｑでべき乗
    したときこの有限体上で定義される乗法に関する単位元
    １に等しくなり、かつ(q-1)以下のいかなる数値でべき
    乗しても決して前記単位元１に等しくならないこの有限
    体の元ｇに対して、この有限体上である数値ａでべき乗
    する関数ｆ(ａ)＝ｇa であり、 第１の演算が、前記数値ｑを法とする乗算演算であり、
    第２の演算が前記有限体上で定義されるべき乗演算であ
    り、第３の演算が前記数値ｑを法とする加算であり、第
    ４の演算が前記有限体上で定義される乗算であることを
    特徴とする請求項１もしくは請求項２記載のディジタル
    署名方式。
  5. 【請求項５】 一方向性関数ｆが、ある合成数ｎを法と
    する剰余環で定義される関数で、前記記ｎを法として、
    前合成数ｎのオイラー関数値φ（ｎ）に互いに素なある
    数値ｅでべき乗する関数ｆ(ａ)＝ａe mod ｎであり、 第１の演算と第２の演算が前記剰余環上で定義されるべ
    き乗演算であり、第３の演算と第４の演算が前記剰余環
    上で定義される乗算演算であることを特徴とする請求項
    １もしくは請求項２記載のディジタル署名方式。
  6. 【請求項６】 一方向性関数ｆが、ある素数もしくは素
    数のべき乗値である数値ｐを用いて構成される有限体の
    上で構成される楕円曲線上で定義される関数で、ある数
    値ｑで前記楕円曲線上定義されるスカラー倍演算を行う
    と前記楕円曲線上で定義される加法に関する単位元∞に
    等しくなり、かつ(q-1)以下の数値でスカラー倍演算を
    行っても決して前記単位元∞に等しくならない前記楕円
    曲線上の点Ｇに対して、ある数値ａでスカラー倍する関
    数ｆ(ａ)＝ａ×Ｇであり、 第１の演算が前記数値ｑを法とする乗算演算であり、第
    ２の演算が前記楕円曲線上で定義されるスカラー倍演算
    であり、第３の演算が前記数値ｑを法とする加算演算で
    あり、第４の演算が前記楕円曲線上で定義されるの加算
    であることを特徴とする請求項１もしくは請求項２記載
    のディジタル署名方式。
JP3287505A 1991-11-01 1991-11-01 デイジタル署名方式 Pending JPH05128132A (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP3287505A JPH05128132A (ja) 1991-11-01 1991-11-01 デイジタル署名方式

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP3287505A JPH05128132A (ja) 1991-11-01 1991-11-01 デイジタル署名方式

Publications (1)

Publication Number Publication Date
JPH05128132A true JPH05128132A (ja) 1993-05-25

Family

ID=17718211

Family Applications (1)

Application Number Title Priority Date Filing Date
JP3287505A Pending JPH05128132A (ja) 1991-11-01 1991-11-01 デイジタル署名方式

Country Status (1)

Country Link
JP (1) JPH05128132A (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9895240B2 (en) 2012-03-29 2018-02-20 Ösur hf Powered prosthetic hip joint
US12245955B2 (en) 2011-11-11 2025-03-11 Össur Iceland Ehf Prosthetic device and method with compliant linking member and actuating linking member
US12575950B2 (en) 2019-09-18 2026-03-17 Össur Iceland Ehf Methods and systems for controlling a prosthetic or orthotic device

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12245955B2 (en) 2011-11-11 2025-03-11 Össur Iceland Ehf Prosthetic device and method with compliant linking member and actuating linking member
US9895240B2 (en) 2012-03-29 2018-02-20 Ösur hf Powered prosthetic hip joint
US12575950B2 (en) 2019-09-18 2026-03-17 Össur Iceland Ehf Methods and systems for controlling a prosthetic or orthotic device

Similar Documents

Publication Publication Date Title
US7093133B2 (en) Group signature generation system using multiple primes
EP0503119B1 (en) Public key cryptographic system using elliptic curves over rings
US7653817B2 (en) Signature schemes using bilinear mappings
Ge et al. A direct anonymous attestation scheme for embedded devices
US20020090085A1 (en) Method of public key generation
US9882890B2 (en) Reissue of cryptographic credentials
US7730319B2 (en) Provisional signature schemes
JP2007510336A (ja) 公開鍵を検証可能に生成する方法及び装置
US7000110B1 (en) One-way function generation method, one-way function value generation device, proving device, authentication method, and authentication device
US6480606B1 (en) Elliptic curve encryption method and system
Lim et al. A study on the proposed Korean digital signature algorithm
KR100971038B1 (ko) 다수의 엔티티와 그에 따른 장치에 부하를 분배하는암호화 방법
JP4494965B2 (ja) 処理中の計算を容易にするための暗号化方法、及び装置
Michels et al. GOST 34.10—a brief overview of Russia's DSA
JPH05128132A (ja) デイジタル署名方式
KR100899020B1 (ko) 공개키를 이용하여 암호화 작업을 수행하는 방법
Prajwal Digital signature algorithm: A hybrid approach
Zahhafi et al. A DSA-like digital signature protocol
JP3331328B2 (ja) 多重デジタル署名方法、そのシステム、その装置及びそのプログラム記録媒体
JP3331321B2 (ja) 複数のデジタル署名を一括して検証する方法及びそのための装置とその方法を記録した記録媒体
Lim et al. The Korean certificate-based digital signature algorithm
Lv et al. Ring authenticated encryption: a new type of authenticated encryption
US20090138718A1 (en) Method of generating a signature with &#34;tight&#34; security proof, associated verification method and signature scheme based on the diffie-hellman model
JP3292312B2 (ja) ディジタル署名方法
JP3435472B2 (ja) 秘密保持認証方法及びシステム