多段签名验证系统、电子签名给与装置、数据追加装置及电子签名验证装置

摘要

本发明提供在向原数据追加数据时，能够缩短签名所需要的处理时间的多段签名验证系统、电子签名给与装置、数据追加装置和电子签名验证装置。多段签名验证系统具备：电子签名给与装置，对预先生成的原数据、取得的陷门散列值、和识别生成了该陷门散列值的数据追加装置的识别信息，给予签名；数据追加装置，将新的生成数据以及识别信息作为追加数据给与原数据，并利用秘密信息，计算与追加数据以及陷门散列值一同输入陷门散列函数时的输出与陷门散列值相等的确定值；和，电子签名验证装置，其根据陷门散列值来验证追加数据的正当性。

说明书

技术领域

本发明涉及多段签名验证系统、电子签名给与装置、数据追加装置及电子签名验证装置。

背景技术

以往，在作为初期节点的数据的输出者与作为最终节点的数据的输入者之间存在1个或1个以上的中间节点，并有进行数据的追加或传送的多跳式通信。例如考虑，对用户向内容提供者的申请，给予符合作为中间节点的计费信息生成者为申请对象的内容或申请目的地的计费信息的情况。这时，内容提供者或计费代行服务器根据所给与的计费信息向用户进行计费。在此，如果计费者可以信赖用户，则计费不拖欠进行，但是，如果不能信赖用户时，作为计费的根据，必须明确申请确实由用户所生成的信息来源。

在明确信息来源时，考虑到通过在各终端间使用IPSec或SSL等技术确立保密的信道来进行相互认证、或将生成者的电子签名给与信息的方法。前者在进行认证时，各终端必须同时在线，与此相反，后者因为向内容给与签名的时刻和信息的输入者验证签名的时刻可以不同，所以可以在任意的时刻进行验证处理，具有例如可以分散负荷进行处理的优点。

当在上述的例子中使用电子签名时，通过用户对生成的申请给与签名，同样计费信息生成者向生成的计费信息给予签名，计费一侧可以不管那些终端的信赖性进行计费，对此用户不能进行申请的事后否认。对像这样多段追加的数据进行签名·验证的技术已提出几个。

例如，公开了在第1个签名者给与签名并输出的原数据上，第2个签名者再追加数据，并对追加数据给与签名，同样，由第i-1个签名者输入了数据的第i个签名者追加数据，在给与追加数据签名之后，输出给第i+1个签名者的多段签名方式(例如，参照特开2002-40935号公报(以下称文献1))。这样，验证者可以验证对多段追加的数据的签名。下面，说明第i个签名者的该签名方式。

当第i个签名者在输入数据上追加数据时，取得追加后的数据与追加前的数据的差分数据m_i。签名通过对结合该m_i的散列值与签名者的ID_i的结合数据和第i-1个的确定值进行可以逆运算的运算，并用密钥加密所得到的数据来生成。到第i个的差分数据、ID、第i个的确定值被输出给第i+1个签名者。由第n个签名者输入数据的验证者，使用公开密钥解码第n个的确定值，通过在所得到的值上施行逆运算f-1，导出第n-1个的确定值，通过重复此动作，得到第1个签名者追加的数据m₁与ID₁的结合数据。该结合数据如果与最初输入数据具有的m₁与ID₁的结合数据相等，则可以保证输入数据的正当性。

另外，作为其他的多段签名方式，公开了对于数据M，第1个签名者对生成的数据M₁，生成签名δ₁，将δ＝δ₁作为给与M₁的签名的方式(例如，参照D.Boneh，C.Gentry，B.Lynn，and H.Shacham，“Aggregate and verifiablyencrypted signatures from bilinear map”in Proc.of Eurocrypt 2003，volume 2656ofLNCS，pages 416-432.Springer-Verlag 2003.(以下称文献2))。取得(M₁、δ)的第2个签名者，生成生成的数据M₂之后，对M₂生成签名δ₂。之后，设δ＝δ₁·δ₂，将该δ作为关于M₁、M₂的签名。同样，取得(M₁、M₂、M₃、…M_n-1、δ)的第n个的签名者，生成生成的数据M_n之后，对M_n生成签名δ_n。之后，设

$>\delta >=>\Pi >i>=>1>n>\mathrm{\delta i}>$>

将该δ作为关于M₁、M₂、…M_n的签名。在签名一侧，通过全部乘以从各签名对象和各签名者的公开密钥所得到的值，并与确定值比较来进行验证。

在文献1中，采用了签名者使用被给与输入数据的确定值来给与追加数据签名的方法。通过这样，如果当某追加数据和给与其的确定值被删除时，通过在验证者一侧进行验证，可以检测出追加数据被删除。

另外，在文献2中，通过将给与数据的签名给合为1个，可以缩短签名长度。

但是，众所周知，电子签名的给与一般情况下要花费计算时间，这些多段签名方式，通过多段进行电子签名的给与，存在开销增大的可能性。

发明内容

因此，本发明的目的在于：鉴于上述问题，提供当在原数据上追加数据时，可以缩短签名所需要的处理时间的多段签名验证系统、电子签名给与装置、数据追加装置及电子签名验证装置。

为了达到上述目的，本发明的第一个特征是：提供一种多段签名验证系统，对已给予签名的原数据给予追加数据，并验证所述原数据和所述追加数据的正当性，其包括：电子签名给与装置，具有电子签名给予部，该电子签名给予部对预先生成的原数据、取得的陷门散列值、和识别生成了该陷门散列值的数据追加装置的识别信息，给予签名；数据追加装置，具有数据追加部和确定值计算部，所述数据追加部将新的生成数据以及所述识别信息作为追加数据给与所述原数据，所述确定值计算部利用秘密信息，计算与所述追加数据以及所述陷门散列值一同输入陷门散列函数时的输出与所述陷门散列值相等的确定值；和，电子签名验证装置，具有陷门散列值计算部和验证部，所述陷门散列值计算部根据所述追加数据和所述确定值来计算所述陷门散列值，所述验证部根据由该陷门散列值计算部所计算的陷门散列值来验证所述追加数据的正当性。

本发明的第二个特征是：提供一种电子签名给与装置，用来给与电子签名，其包括：取得部，用于取得陷门散列值、和识别生成该陷门散列值的数据追加装置的识别信息；电子签名给与部，用于对预先所生成的原数据、所述陷门散列值、和所述识别信息给予电子签名；和，输出部，用于将给与所述电子签名的所述原数据以及所述识别信息输出给所述数据追加装置。

本发明的第三个特征是：提供一种数据追加装置，将新的数据给与在电子签名给与装置所生成的原数据，其包括：陷门散列值生成部，用于生成陷门散列值；第1输出部，用于输出所述陷门散列值、和识别生成所述陷门散列值的数据追加装置的识别信息；数据追加部，用于将新的生成数据以及所述识别信息作为追加数据给与所述原数据；确定值计算部，用于利用秘密信息，计算与所述追加数据以及所述陷门散列值一同输入陷门散列函数时的输出与所述陷门散列值相等的确定值；和，第2输出部，用于输出所述追加数据和所述确定值。

本发明的第四个特征是：提供一种电子签名验证装置，验证被给与电子签名的原数据和被追加给与该原数据的追加数据的正当性，其包括：数据取得部，用于从数据追加装置取得所述追加数据和与所述追加数据以及陷门散列值一同输入陷门散列函数时的输出与所述陷门散列值相等的确定值；陷门散列值计算部，用于根据所述追加数据和所述确定值来计算所述陷门散列值；和，验证部，用于根据由该陷门散列值计算部所计算的陷门散列值来验证所述追加数据的正当性。

附图说明

图1是涉及第1实施方式的多段签名验证系统的构成框图。

图2是表示涉及第1实施方式的多段签名验证方法的流程图。

图3是涉及第1实施方式的电子签名验证装置取得的数据例。

图4是涉及第2实施方式的多段签名验证系统的构成框图。

图5是涉及第2实施方式的数据追加装置间的数据流动的说明图。

图6是涉及第2实施方式的电子签名验证装置取得的数据例。

图7是涉及第2实施方式的包含占位符的SMIL文件的例子。

图8是在图7中在占位符插入数据的例子。

图9是涉及第2实施方式的占位符在多段形成时的数据构造的例子。

图10是涉及第3实施方式的多段签名验证系统的构成框图。

图11是涉及第4实施方式的电子签名验证装置取得的数据例。

图12是涉及第5实施方式的多段签名验证系统的构成框图。

具体实施方式

首先，对在本实施方式中使用的陷门散列函数、陷门散列值进行说明。下面，将y作为散列密钥，将x作为密钥，前者为公开信息，后者为秘密信息。另外，表1表示关于陷门散列函数的值。

                           表1

    值    说明    q    适当选择的充分大的素数    k    适当的自然数    p    满足kp+1的素数    m’    从q的不可约剩余群选择为随机    r’    从1的不可约剩余群选择为随机    g    g^q＝1(mod p)的数    x    从q的不可约剩余群选择为随机的密钥    y    用y＝g^x(mod p)导出的公开密钥    h_y    与公开密钥y对应的陷门散列值h_y(m’，r’)    将m’，r’作为输入的陷门散列值    m    属于q的不可约剩余群的任意值    r    通过与m一同输入h_y变为h_y(m’，r’)相等的值

陷门散列值，通过伴随y的陷门散列函数h_y的2数的输入，表示为h_y(m、r)，满足以下性质。

1)只给出y和h_y(m’，r’)时，导出使h_y(m，r)＝h_y(m’，r’)的m，r组非常困难。

2)已知x，使用x，m’，r’对随机数m导出使h_y(m’，r’)＝h_y(m，r)的r很容易。

这样，总称通过使用某秘密信息(在此为密钥)可以有意制造冲突的函数为陷门散列函数。陷门散列函数伴随最低2数的输入。

下面，将关于陷门散列函数的过程分为以下3个过程进行说明。

1)陷门散列值的导出

(ァ)如表1所示，选择q、k、p、m’、r’、x，导出g、y。

(ィ)设h_y＝h_y(m’，r’)＝g_m’y_r’(mod p)，将此作为陷门散列值。

2)冲突的检测(已知h_y、m’、r’、q、x)

(ァ)选择随机数m。

(ィ)导出使m+x_r＝m’+x_r’(mod p)的r。该r满足h_y(m’，r’)＝h_y(m，r)。

3)陷门散列值的验证(已知g、p、y、m、r、h_y(m’，r’))。

(ァ)检测是否满足h_y(m，r)＝g_my_r(mod p)h_y(m’，r’)。

下面，使用上述举例的陷门散列函数，对本发明的实施方式进行说明。另外，本发明不局限于上述举例的陷门散列函数，使用具有陷门散列函数性质的任意函数都可以实现。

第1实施方式

如图1所示，涉及第1实施方式的多段签名认证系统，具有电子签名给与装置10、1个数据追加装置20以及电子签名验证装置30。在电子签名给与装置10、数据追加装置20、电子签名验证装置30之间进行数据的输入/输出时，可以分别在装置间直接进行输入/输出，也可以通过通信网络进行输入/输出。在此，所说通信网络，包括因特网、移动电话网、公用电话网等通信网。

电子签名验证装置10取得数据追加装置20生成的陷门散列值和导出陷门散列值所必须的参数，向这些和在电子签名给与装置10预先所生成的原数据给与签名，并输出给数据追加装置20。

数据追加装置20取得具有陷门散列值、参数的数据，将生成数据作为追加数据，并将此追加到取得数据上。另外，通过使用秘密信息与追加数据一同输入陷门散列函数，来计算与陷门散列值相等的确定值，并与取得数据一同输出给电子签名验证装置30。

电子签名验证装置30取得给与电子签名的数据，根据取得数据具有的参数和确定值导出陷门散列值，通过与输入数据具有的陷门散列值进行比较验证，来验证追加数据的正当性。另外，验证陷门散列值、参数以及给与电子签名给与装置的原数据的签名，并验证陷门散列值、原数据的正当性。

下以对电子签名给与装置10、数据追加装置20、电子签名验证装置30的更详细的构成进行说明。

电子签名给与装置10具有电子签名给与部11和数据输入/输出部12。

数据输入/输出部12进行数据追加装置20输出的陷门散列值、参数的取得。取得方法是通过通信由数据追加装置20直接输入，或取得网络上预先所登录的。具体地讲，陷门散列值是h_y(m’，r’)，参数是g、p、y。

电子签名给与部11根据以往的电子签名技术给与预先所生成的原数据、参数、陷门散列值签名。

数据输入/输出部12将原数据、参数、陷门散列值以及给与这些的签名输出给追加装置20。

另外，电子签名给与装置具有图未示的数据保持部，保持从数据追加装置所输入的陷门散列值、参数、原数据等。数据保持部是RAM、ROM、硬盘、软磁盘、微型光盘、IC芯片、盒式磁带等存储媒体。

数据追加装置20具有陷门散列值生成部21、数据输入/输出部22、数据追加部23和确定值计算部24。

陷门散列值生成部21从表1记载的各值之中生成m、r以外的值，并将陷门散列值、参数交给数据输入/输出部22，将密钥以及计算确定值必须的值交给确定值计算部24。具体地讲，密钥是x，确定值计算必须的值是m’、r’、p。数据输入/输出部22输出陷门散列值、参数。输出方法是通过通信直接输出给电子签名给与装置、或登录到网络上。

数据追加部23将生成数据作为追加数据，并将此追加到数据输入/输出部22从电子签名给与装置10取得的数据上。具体地讲，追加数据是m。

确定值计算部24根据x、m、m’、r’、q生成确定值r，数据输入/输出部22将追加了追加数据的取得数据和确定值r一同输出给电子签名验证装置30。

另外，数据追加装置20具有图未示的数据保持部，保持陷门散列值、密钥、确定值r等表1举出的值或追加数据。数据保持部是RAM、ROM、硬盘、软磁盘、微型光盘、IC芯片、盒式磁带等存储媒体。

电子签名验证装置30具有数据取得部31、电子签名验证部32、陷门散列值计算部33。

数据取得部31取得数据追加装置20输出的数据以及确定值。

电子签名验证部32根据取得数据具有的电子签名给与装置10给与的电子签名，来验证原数据、陷门散列值以及参数的正当性。

陷门散列值计算部33根据取得数据具有的追加数据、参数以及确定值计算陷门散列值h_y(m，r)。将该值与取得数据具有的陷门散列值进行比较验证。在此，如果两者相等，当通过电子签名验证部32可以验证陷门散列值、参数的正当性时，可以说是比追加数据正当的数据。通过上述2级验证，可以保障电子签名给与装置10的原数据以及数据追加装置20的追加数据的正当性。

另外，电子签名验证装置30具有图未示的数据保持部，保持从数据追加装置所输入的取得数据等。数据保持部是RAM、ROM、硬盘、软磁盘、微型光盘、IC芯片、盒式磁带等存储媒体。

在上述的例子中，虽然电子签名给与装置10或数据追加装置20输出参数或陷门散列值，但是，如从验证方法得知，这些值只是在验证时必须。因此，如果有像专门能够识别陷门散列值和参数那样的识别符，使用其识别符，电子签名验证装置30可以取得陷门散列值以及参数，则电子签名给与装置或各数据追加装置可以取代陷门散列值、参数输出识别符。

下面，使用图2对涉及第1实施方式的多段签名认证方法进行说明。

(a)首先，在步骤S101，数据追加装置20生成表1所示的各值。之后，在步骤S102，将陷门散列值以及参数输出给电子签名装置。

(b)接着，在步骤S103，电子签名给与装置10给与预先在电子签名给与装置所生成的原数据、陷门散列值、参数的签名。之后，在步骤S104，将这些数据以及签名输出给数据追加装置20。

(c)接着，在步骤S105，数据追加装置20将生成数据作为追加数据，并将此追加到由电子签名给与装置10取得的数据上。之后，在步骤S106，通过使用秘密信息与追加数据一同输出到陷门散列函数，来计算与陷门散列值相等的确定值。之后，在步骤S107，将给与确定值的追加数据与给与电子签名的原数据、参数、陷门散列值一同输出给电子签名验证装置30。

(d)电子签名验证装置30取得的数据是如图3所示的数据构造。即，取得原数据、参数、陷门散列值和给与确定值的追加数据。之后，在步骤S108，电子签名验证装置30根据电子签名给与装置10给与的电子签名，来验证原数据、陷门散列值以及参数的正当性。

(e)接着，在步骤109，电子签名验证装置30根据取得数据具有的追加数据、参数以及确定值计算陷门散列值h_y(m，r)。之后，在步骤S110，将计算所得到的值与取得数据具有的陷门散列值进行比较。在此，当两者相等，在步骤S108能够验证陷门散列值、参数的正当性时，可以说是比追加数据正当数据。通过步骤S108以及步骤S110两级验证，可以保障电子签名给与装置10的原数据以及数据追加装置20的追加数据的正当性。

根据涉及第1实施方式的多段签名认证系统，当数据追加装置向已给与签名的原数据追加数据时，可以不必给与追加数据电子签名，缩短签名所需要的计算时间。另外，在涉及第1实施方式的多段签名认证系统，识别信息是在生成陷门散列值时所生成的参数。因此，电子签名验证装置可以使用参数来计算陷门散列值。

另外，根据涉及第1实施方式的电子签名给与装置，可以给与原数据、识别信息(参数)以及陷门散列值电子签名。另外，根据涉及第1实施方式的电子签名给与装置，可以通过通信网络输入识别信息(参数)以及陷门散列值。另外，根据涉及第1实施方式的数据追加装置，通过代替给与电子签名而给与确定值，可以缩短签名时间，保障根据确定值生成数据的正当性。另外，根据涉及第1实施方式的数据追加装置，可以通过通信网络输出识别信息(参数)以及陷门散列值。

另外，根据涉及第1实施方式的电子签名验证装置，根据电子签名、陷门散列值可以验证原数据以及追加数据的正当性。更详细地讲，根据涉及第1实施方式的电子签名验证装置，通过根据电子签名来验证原数据的正当性，并比较取得数据所包含的陷门散列值与所计算的陷门散列值，可以验证追加数据的正当性。另外，可以有专门识别陷门散列值和参数那样的识别符，涉及第1实施方式的电子签名验证装置使用其识别符来取得陷门散列值以及参数。这时候，取得的数据即使不包含陷门散列值或参数等，也可以通过使用识别符取得陷门散列值和参数，可以计算陷门散列值。

第2实施方式

如图4所示，涉及第2实施方式的多段签名认证系统，具有电子签名给与装置10、n个(n是自然数)数据追加装置20、和电子签名验证装置30。在下面的说明中，在第i位追加数据的数据追加装置或在该数据追加装置预先所生成的生成数据、其数据追加装置追加的追加数据、生成的陷门散列值、识别信息以及确定值的后面记述(i)。另外，涉及数据追加装置20(i)生成的陷门散列值的各值，如x_i、y_i添加下标来描述。

电子签名给与装置10的动作因为与第1实施方式相同，所以在此省略说明。

数据追加装置20(i)，当i是1或1以上n-1或n-1以下时，输出生成的陷门散列值(i)和参数(i)，取包含这些的数据。另外，将从数据追加装置20(i+1)取得的陷门散列值(i+1)、参数(i+1)以及数据追加装置20(i)预先生成的生成数据(i)作为追加数据，追加到取得数据上。进而，通过使用秘密信息，与追加数据(i)一同输入陷门散列函数，来导出与陷门散列值(i)相等那样的确定值(i)，并与取得数据一同输出。数据追加装置20(n)除了追加数据(n)只是生成数据(n)这一点，与上述数据追加装置20(i)的动作相同。

电子签名验证装置30的陷门散列值计算部33根据取得数据具有的参数(i)、追加数据(i)以及确定值(i)导出陷门散列值(i)，从i＝1到i＝n施行与取得数据具有的陷门散列值(i)进行比较验证的操作。电子签名验证部32的动作与第1实施方式相同。

下面，对数据追加装置20(i)、电子签名验证装置30的陷门散列值计算部33进行详细说明。

图5表示数据追加装置20(i-1)、数据追加装置20(i)、数据追加装置20(i+1)间的信息的流程。数据追加装置20(i)的陷门散列值生成部21生成表1记载的各值，陷门散列值(i)、参数(i)交给数据输入/输出部22，将密钥以及计算作为确定r_i所必须的值交给确定值计算部24。具体地讲，密钥是x_i，确定值计算所必须的值是m_i’、r_i’、q_i。数据输入/输出部22输出陷门散列值(i)、参数(i)。具体地讲，陷门散列值(i)是h_yi(m_i’，r_i’)，参数(i)是g_i、p_i、y_i。数据追加部23将生成数据(i)、数据输入/输出部22从数据追加装置(i+1)取得的陷门散列值(i+1)、参数(i+1)加在起作为追加数据(i)，追加到数据输入/输出部22从数据追加装置(i-1)取得的数据上。具体地讲，陷门散列值(i+1)是h_yi+1(m_i+1’，r_i+1’)，参数(i+1)是g_i+1、p_i+1、y_i+1，追加数据(i)是m_i。确定值计算部24根据x_i、m_i、m_i’、r_i’、q_i生成作为确定值(i)的r_i，数据输入/输出部22将追加了追加数据(i)的取得数据和确定值(i)一同输出给数据追加装置(i+1)。在此，将i、j作为n或n以下不同的自然数，数据追加装置20(i)和数据追加装置20(j)可以是相同的数据追加装置。这时候，分别对追加数据(i)、追加数据(j)进行上述操作。

图6表示电子签名验证装置的取得数据。在该取得数据中，包含电子签名给与装置10以及各数据追加装置20(i)输出的数据。电子签名验证装置30的陷门散列值计算部33根据数据取得部31取得的数据具有的参数(i)、确定值(i)追加数据(i)来计算陷门散列值(i)。具体地讲为h_yi(m_i，r_i)。与第1实施方式一样，将该值与取得数据具有的陷门散列值(i)进行比较验证，如果两相等，追加数据(i-1)的正当性补充验证，则追加数据(i-1)所包含的陷门散列值(i)、参数(i)的正当性也被验证，可以说追加数据(i)也是正当的。陷门散列值计算部33通过从i＝1到n依次进行上述验证，来验证全部追加数据的正当性。

另外，在第2实施方式中，电子签名给与装置10的电子签名给与部11生成数据追加装置20指定追加数据的场所的占位符，数据追加装置20(i)的数据追加部23，给与识别信息的数据具有占位符时，在占位符内插入追加数据。占位符是用于数据插入的模板等，可以指定数据追加装置20追加数据的场所。例如，当数据是SMIL文件时，当使用模板时，电子签名给与装置10或数据追加装置20(i)，在如图7所示的SMIL文件中，生成具有指定数据追加装置20的ID的“video”要素，将src属性置于空。取得该SMIL文件的数据追加装置20(i+1)，在取得的带占位符SMIL文件内的有自己的ID的要素src属性上，追加作为生成数据的URL。例如，生成数据追加后的SMIL文件如图8所示。假如当多个数据追加装置20(i)向多段输入占位符时，追加嵌套状进行，结果是成为如图9所示的构造。

另外，在第1实施方式中，电子签名给与装置10或数据追加装置20可以输出用于指定插入追加数据的场所的占位符。

根据涉及第2实施方式的多段签名认证系统，当多个数据追加装置向已给与签名的原数据追加数据时，可以不必给与各追加数据电子签名，缩短签名所需要的计算时间。根据涉及第2实施方式的电子签名给与装置，可以指定插入追加数据的场所。

另外，根据涉及第2实施方式的数据追加装置，取代对多个数据追加装置分别给与电子签名，通过分别给与确定值，可以缩短签名时间，根据确定值来保障生成数据的正当性。另外，根据涉及第2实施方式的数据装置，可以指定插入追加数据的场所。

另外，根据涉及第2实施方式的电子签名认证装置，当追加数据包含陷门散列值时，可以验证各追加数据的正当性。另外，通过从第1陷门散列值顺序地进行验证，当对追加数据进行篡改时，可以检测篡改由哪个追加数据进行，对哪个数据追加装置输出的数据进行。

第3实施方式

如图10所示，涉及第3实施方式的多段签名认证系统，具有

具有电子签名给与装置10、n个(n是自然数)数据追加装置20、和电子签名验证装置30。在第3实施方式中，电子签名给与装置10或数据追加装置20(i)从多个数据追加装置20取得陷门散列值以及参数。下面，对电子签名给与装置10或数据追加装置20(i)进行详细说明。

首先，对电子签名给与装置10从多个数据追加装置20取得陷门散列值以及参数的情形进行说明。电子签名给与装置10的构成与图1相同。

电子签名给与装置10的数据输入/输出部12，将k作为n或n以下的自然数，进行数据追加装置20(1)～数据追加装置20(k)分别输出的陷门散列值(1)～陷门散列值(k)、参数(1)～参数(k)的取得。电子签名给与部11电子签名给与装置10的原数据、陷门散列值(1)～陷门散列值(k)、参数(1)～参数(k)签名。数据输入/输出部12将原数据、参数(1)～参数(k)、陷门散列值(1)～陷门散列值(k)输出给数据追加装置20(1)。

这时，i为k或k以下的数据追加装置20(i)的数据输入/输出部22，将陷门散列值生成部21生成的陷门散列值(i)、参数(i)输出给电子签名给与装置10。另外，i为k-1或k-1以下的数据追加装置20(i)的数据输入/输出部22，因为当从电子签名给与装置10或数据追加装置20(i-1)取得具有陷门散列值(i)、参数(i)时，其数据已经具有陷门散列值(i+1)、参数(i+1)，所以将生成数据作为追加数据(i)。

接着，对数据追加装置20(i)从多个数据追加装置20取得陷门散列值以及参数的情形进行说明。将m作为n-i或n-i以下的自然数，数据追加装置20(i)的数据输入/输出部22取得数据追加装置20(i+1)～数据追加装置20(i+m)分别输出的陷门散列值(i+1)～陷门散列值(i+m)、参数(i+1)～参数(i+m)，并将生成数据(i)、陷门散列值(i+1)～陷门散列值(i+m)、参数(i+1)～参数(i+m)作为追加数据(i)。另外，将j作为m或m以下，数据追加装置20(i+j)将生成数据(i+j)作为追加数据(i+j)。

另外，关于电子签名验证装置，因为与第1实施方式相同，所以以此省略说明。

再者，在第3实施方式中，也可以如在第2实施方式中所说明的那样，电子签名给与装置10或数据追加装置20输出用于指定插入追加数据的场所的占位符。

根据涉及第3实施方式的多段签名认证系统，当多个数据追加装置向已给与签名的原数据追加数据时，可以不必给与各追加数据电子签名，缩短签名所需要的计算时间。另外，根据涉及第3实施方式的电子签名给与装置，可以给与多个数据追加装置的陷门散列值以及识别信息(参数)电子签名。

另外，根据涉及第3实施方式的数据追加装置，可以将多个数据追加装置的识别信息以及陷门散列值追加到取得的数据上，并根据同时给与的确定值来保障正当性。

第4实施方式

本发明的第4实施方式，对电子签名给与装置10不输出已取得的陷门散列值，另外，在各数据追加装置20的追加数据中不包含陷门散列值的情形进行说明。多段签名认证系统的构成如图1相同。下面，对电子签名给与装置10、数据追加装置20(i)、电子签名验证装置30进行详细说明。

电子签名给与装置10的电子签名给与部11给与原数据、陷门散列值(1)、参数(1)电子签名，数据输入/输出部输出原数据、参数(1)、电子签名。

数据追加装置(i)的数据追加部23将原数据和参数(i+1)作为追加数据(i)。另外，确定值计算部24将追加数据(i)、陷门散列值(i+1)加在一起作为m_i，计算确定值(i)。这时候，电子签名验证装置30取得的数据变为图11那样。陷门散列值(1)虽然通过陷门散列值计算部32计算，但是，陷门散列值(1)因为根据追加数据(1)、陷门散列值(2)、确定值(1)计算，所以必须陷门散列值(2)。同样，对于作为n-1或n-1以下的i，在导出陷门散列值(i)时必须陷门散列值(i+1)。在此，陷门散列值(n)因为根据数据追加装置20(n)的生成数据(n)和确定值(n)计算，所以可以导出。因此，陷门散列值(1)通过由陷门散列值计算部重新返回计算陷门散列值可以导出。电子签名验证部32进行给与以上求得的陷门散列值(1)的签名的验证，如果验证的结果，陷门散列值(1)是正当的，则可以保障直到陷门散列值(1)的导出所使用的追加数据(1)～追加数据(n)的全部追加数据的正当性。

另外，在第4实施方式中，也可以如在第2实施方式中说明的那样，电子签名给与装置10或数据追加装置20输出用于指定插入追加数据的场所的占位符。

根据涉及第4实施方式的多段签名认证系统，在电子签名给与装置以及数据追加装置，因为不输出陷门散列值，所以可以减少输出的数据量。

另外，根据涉及第4实施方式的电子签名给与装置，因为不输出陷门散列值，所以可以减少输出的数据量。

另外，根据涉及第4实施方式的数据追加装置，因为不将陷门散列值追加到已取得的数据上，所以可以减少输出的数据量。

另外，根据涉及第4实施方式的电子签名验证装置，根据数据追加装置20(n)的生成数据(n)和确定值(n)可以导出各数据追加装置中的陷门散列值(1)～陷门散列值(n)，通过验证所给与的电子签名，可以验证全部追加数据的正当性。

第5实施方式

如图12所示，本发明的第5实施方式对在第2实施方式中数据追加装置20(i)在第j个再追加数据的情形进行说明。作为再追加数据的方法，有生成每个追加数据用的陷门散列值的方法、和对多个追加数据只生成1个陷门散列值的方法。在此，当对每个追加数据生成陷门散列值时，在第2实施方式中，因为数据追加装置20(i)只有作为数据追加装置20(j)进行，所以在此省略。

下面，对使用1个陷门散列值的多次数据追加进行详细说明。具体地讲，对将j作为比i+1大的自然数，数据追加装置(i)从数据追加装置(i-1)取得数据，在第i个再追加数据的情形进行考虑。另外，虽然对以下数据追加装置(i)进行2次数据追加的情形进行说明，但是，实际上通过多次应用本实施方式，也可以进行2次或2次以上的数据追加。

数据追加装置20(i)，当从数据追加装置20(i-1)取得数据时，如在第2实施方式中说明的那样，输出追加数据(i)和确定值(i)。当数据追加装置20(j-i)取得这些的数据时，数据追加装置20(j-1)将数据追加装置20(i)输出的参数(i)、陷门散列值(i)、生成数据(j-1)作为追加数据(j-1)，与确定值一同输出。在第j个再次追加数据的数据追加装置20(i)，从数据追加装置20(j+1)取得参数(j+1)、陷门散列值(j+1)，将生成数据(j)、参数(j+1)、陷门散列值(j+1)作为追加数据(j)，追加到取得数据，与确定值(j)一同输出。

涉及第5实施方式的电子签名给与装置以及电子签名验证装置30的动作，因为与第2实施方式相同，所以在此省略说明。

另外，在第5实施方式中，也可以如在第2实施方式中说明的那样，电子签名给与装置10或数据追加装置20输出用于指定插入追加数据的场所的占位符。

根据涉及第5实施方式的多段签名认证系统，相同的数据追加装置可以2次或2次以上追加数据。

根据涉及第5实施方式的数据追加装置，对于1个数据，可以多次追加数据。

本发明虽然通过上述第1～第5实施例进行了描述，但是，不应理解为该发明局限于构成该内容的一部分的论述以及图示仅局限于该发明。根据该内容当业者可以明确各种各样的代替实施例、实施例以及运用技术。例如，在第1～第5实施例的实施方式中，虽然将电子签名给与装置、数据追加装置、电子签名验证装置作为不同的装置进行了说明，但是，可以将这些功能汇集到1个装置。

同样，电子签名给与装置、数据追加装置、电子签名验证装置虽然分别具有多个功能，但是，可以按各自的功能分开装置。例如，在数据追加装置，可以将陷门散列值生成部和确定值计算部配置为不同的装置。这时，用有线或无线连接每个功能部。