署名生成装置及署名验证装置

摘要

提供一种能够防止对署名数据的抄本攻击(Transcript attack)的署名生成装置。使用署名密钥进行署名的署名生成装置存储上述署名密钥，使用上述署名密钥对署名对象数据实施署名，生成署名数据，在上述署名数据的生成时，对使用上述署名密钥进行了署名的累积次数进行计数，判断计数的累积次数是否达到了规定次数，在判断为计数的累积次数达到了上述规定次数的情况下，以后禁止使用上述署名密钥进行的署名。

权利要求

1.一种署名生成装置，使用署名密钥进行署名，其特征在于，具备：密钥存储单元，存储着上述署名密钥；

署名生成单元，使用上述署名密钥对署名对象数据实施署名，生成署名数据；

计数单元，在生成上述署名数据时，对使用上述署名密钥进行了署名的累积次数进行计数；

判断单元，判断由上述计数单元计数的累积次数是否达到了规定次数；以及署名禁止单元，在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，以后禁止使用上述署名密钥进行的署名，在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，上述署名禁止单元通过生成上述署名密钥之外的另外的署名密钥、并用生成的上述另外的署名密钥对由上述密钥存储单元存储的上述署名密钥进行覆盖，来禁止使用上述署名密钥进行的署名。

2.如权利要求1所述的署名生成装置，其特征在于，上述署名生成装置还具备：

验证密钥证书存储单元，存储有验证密钥证书，该验证密钥证书包含对应于上述署名密钥的验证密钥和表示上述验证密钥的正当性且由第1秘密密钥生成的验证密钥署名数据；

公开密钥证书存储单元，存储有公开密钥证书，该公开密钥证书包含对应于上述第1秘密密钥的公开密钥和表示上述公开密钥的正当性且由外部机构所具有的第2秘密密钥生成的公开密钥署名数据；以及发送单元，将上述署名对象数据、由上述署名生成单元生成的上 述署名数据、上述验证密钥证书和上述公开密钥证书发送给进行上述署名数据的验证的署名验证装置。

3.如权利要求2所述的署名生成装置，其特征在于，在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，上述署名禁止单元还对应上述另外的署名密钥而生成上述验证密钥之外的另外的验证密钥，对于生成的上述另外的验证密钥，使用上述第1秘密密钥生成上述验证密钥署名数据之外的另外的验证密钥署名数据，生成包含上述另外的验证密钥和上述另外的验证密钥署名数据的、上述验证密钥证书之外的另外的验证密钥证书，用生成的上述另外的验证密钥证书对存储在上述公开密钥证书存储单元中的上述验证密钥证书进行覆盖。

4.如权利要求1所述的署名生成装置，其特征在于，上述署名生成装置还具备存储有表示上述署名密钥的第1密钥信息的信息存储单元；

上述署名生成单元根据存储在上述存储单元中的第1密钥信息，从上述密钥存储单元取得上述署名密钥，使用取得的上述署名密钥生成上述署名数据；

上述密钥存储单元还存储上述署名密钥之外的另外的署名密钥；

在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，上述署名禁止单元通过将由上述信息存储单元存储的上述第1密钥信息改写为表示上述另外的署名密钥的第2密钥信息，来禁止使用上述署名密钥进行的署名。

5.如权利要求1所述的署名生成装置，其特征在于，上述署名生成单元取得由上述计数单元计数的累积次数；

上述署名对象数据包含消息数据和取得的累积次数。

6.如权利要求1所述的署名生成装置，其特征在于，上述署名生成装置还具备对时刻进行计时的时钟单元； 上述署名生成单元利用上述时钟单元取得作为署名数据的有效期限判断基准的时刻信息；

上述署名对象数据包含消息数据和取得的上述时刻信息。

7.如权利要求1所述的署名生成装置，其特征在于，上述判断单元具有存储了上述规定次数的次数存储部；

上述署名生成装置还具备更新单元，该更新单元将由上述次数存储部存储的上述规定次数更新为另外的规定次数。

8.一种署名验证装置，验证由使用署名密钥进行署名的署名生成装置生成的署名数据，其特征在于，具备：接收单元，从上述署名生成装置接收署名对象数据和对于上述署名对象数据的署名数据，上述署名对象数据包含消息数据与上述署名生成装置使用上述署名密钥进行了署名的累积次数；

次数判断单元，判断包含在接收到的上述署名对象数据中的上述累积次数是否达到了规定次数；以及验证禁止单元，在判断为上述累积次数达到了上述规定次数的情况下，禁止上述署名数据的验证。

9.如权利要求8所述的署名验证装置，其特征在于，上述署名对象数据还包含作为上述署名数据的有效期限判断基准的第1时刻信息；

上述署名验证装置还具备：

时钟单元，对时刻进行计时；

期限判断单元，在判断为上述累积次数没有达到上述规定次数的情况下，使用上述时钟单元取得表示当前时刻的第2时刻信息，利用上述第1时刻信息和取得的第2时刻信息，判断是否已超过上述署名数据的有效期限；

验证单元，在判断为没有超过上述署名数据的有效期限的情况下，验证上述署名数据；

以及

上述验证禁止单元还在判断为已超过上述署名数据的有效期限的情况下，禁止上述署名数据的验证。

10.如权利要求9所述的署名验证装置，其特征在于，上述署名数据是使用上述署名生成装置所生成的署名密钥生成的；

上述接收单元还接收验证密钥证书以及公开密钥证书，所述验证密钥证书包含对应于上述署名密钥的验证密钥和表示上述验证密钥的正当性且包括利用第1秘密密钥生成的验证密钥署名数据，所述公开密钥证书包含对应于上述第1秘密密钥的第1公开密钥和表示上述第1公开密钥的正当性且包括利用外部机构所具有的第2秘密密钥生成的公开密钥署名数据；

上述验证单元具备：

密钥存储部，存储有对应于上述第2秘密密钥的第2公开密钥；

第1验证部，在判断为没有超过上述署名数据的有效期限的情况下，使用上述第2公开密钥来验证上述公开密钥证书是否是正当的；

第2验证部，在判断为上述公开密钥证书是正当的情况下，使用上述第1公开密钥来验证上述验证密钥证书是否是正当的；以及第3验证部，在判断为上述验证密钥证书是正当的情况下，验证上述署名数据是否是正当的。

11.如权利要求10所述的署名验证装置，其特征在于，上述署名验证装置还具备发送单元，在判断为上述累积次数达到了上述规定次数的情况下，该发送单元将确定生成了上述署名数据的上述署名生成装置的确定信息发送给外部装置。

12.如权利要求8所述的署名验证装置，其特征在于，上述次数判断单元具有存储上述规定次数的次数存储区域；

上述署名验证装置还具备更新单元，上述更新单元从上述署名生成装置接收上述规定次数之外的另外的规定次数，将由上述次数存储 区域存储的上述规定次数更新为接收到的上述另外的规定次数。

13.一种署名系统，包括使用署名密钥进行署名的署名生成装置和验证由上述署名生成装置生成的署名数据的署名验证装置，其特征在于，上述署名生成装置具备：

密钥存储单元，存储着上述署名密钥；

署名生成单元，使用上述署名密钥对包含消息数据和使用上述署名密钥进行了署名的累积次数的署名对象数据实施署名，生成上述署名数据；

计数单元，在生成上述署名数据时，对上述累积次数进行计数；

判断单元，判断由上述计数单元计数的累积次数是否达到了规定次数；

署名禁止单元，在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，以后禁止使用上述署名密钥进行的署名；以及发送单元，向上述署名验证装置发送包含上述署名对象数据与上述署名数据的数据组；

上述署名验证装置具备：

接收单元，从上述署名生成装置接收上述数据组；

次数判断单元，判断包含在接收到的上述数据组的上述署名对象数据中的上述累积次数是否达到了规定次数；以及验证禁止单元，在通过上述次数判断单元判断为上述累积次数达到了上述规定次数的情况下，禁止上述署名数据的验证。

14.如权利要求13所述的署名系统，其特征在于，上述署名系统还具备监视从上述署名生成装置向上述署名验证装置发送的上述数据组的监视装置；

上述监视装置具备：

取得单元，从连接上述署名生成装置与上述署名验证装置的传输通道取得上述数据组；

日志存储单元，在取得上述数据组之前，存储已经取得的1个以上的已取得数据组；

数据判断单元，使用上述1个以上的已取得数据组，判断所取得的上述数据组是否是正当的；以及信息发送单元，在判断为上述数据组是不正当的情况下，向外部装置发送对生成了包含在所取得的上述数据组中的上述署名数据的上述署名生成装置进行确定的确定信息。

15.如权利要求14所述的署名系统，其特征在于，上述数据组还包含对应于上述署名密钥的验证密钥；

上述1个以上的已取得数据组分别包括已取得验证密钥和包含已取得累积次数的已取得署名对象数据；

上述数据判断单元检索在日志存储单元中是否存在包含与上述验证密钥及上述累积次数一致的已取得验证密钥及已取得累积次数的已取得数据组，在存在的情况下，判断为所取得的上述数据组是不正当的。

16.一种署名生成方法，在使用署名密钥进行署名的署名生成装置中使用，其特征在于，上述署名生成装置具备存储着上述署名密钥的密钥存储单元；

上述署名生成方法包括：

署名生成步骤，使用上述署名密钥对署名对象数据实施署名，生成署名数据；

计数步骤，在生成上述署名数据时，对使用上述署名密钥进行了署名的累积次数进行计数；

判断步骤，判断由上述计数步骤计数的累积次数是否达到了规定次数；以及 署名禁止步骤，在判断为由上述计数步骤计数的累积次数达到了上述规定次数的情况下，以后禁止使用上述署名密钥进行的署名，在判断为由上述计数步骤计数的累积次数达到了上述规定次数的情况下，上述署名禁止步骤通过生成上述署名密钥之外的另外的署名密钥、并用生成的上述另外的署名密钥对由上述密钥存储单元存储的上述署名密钥进行覆盖，来禁止使用上述署名密钥进行的署名。

17.一种署名验证方法，在署名验证装置中使用，该署名验证装置对使用署名密钥进行署名的署名生成装置所生成的署名数据进行验证，其特征在于，该署名验证方法包括：接收步骤，从上述署名生成装置接收署名对象数据和对于上述署名对象数据的署名数据，上述署名对象数据包含消息数据和上述署名生成装置使用上述署名密钥进行了署名的累积次数；

次数判断步骤，判断包含在接收到的上述署名对象数据中的上述累积次数是否达到了规定次数；以及验证禁止步骤，在判断为上述累积次数达到了上述规定次数的情况下，禁止上述署名数据的验证。

18.一种集成电路，是使用署名密钥进行署名的署名生成装置的集成电路，其特征在于，具备：密钥存储单元，存储着上述署名密钥；

署名生成单元，使用上述署名密钥对署名对象数据实施署名，生成署名数据；

计数单元，在生成上述署名数据时，对使用上述署名密钥进行了署名的累积次数进行计数；

判断单元，判断由上述计数单元计数的累积次数是否达到了规定次数；以及署名禁止单元，在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，以后禁止使用上述署名密钥进行的署名， 在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，上述署名禁止单元通过生成上述署名密钥之外的另外的署名密钥、并用生成的上述另外的署名密钥对由上述密钥存储单元存储的上述署名密钥进行覆盖，来禁止使用上述署名密钥进行的署名。

19.一种集成电路，是署名验证装置的集成电路，该署名验证装置对使用署名密钥进行署名的署名生成装置所生成的署名数据进行验证，该集成电路的特征在于，具备：接收单元，从上述署名生成装置接收署名对象数据和对于上述署名对象数据的署名数据，上述署名对象数据包含消息数据和上述署名生成装置使用上述署名密钥进行了署名的累积次数；

次数判断单元，判断包含在接收到的上述署名对象数据中的上述累积次数是否达到了规定次数；以及验证禁止单元，在判断为上述累积次数达到了上述规定次数的情况下，禁止上述署名数据的验证。

说明书

署名生成装置及署名验证装置

技术领域

[0001] 本发明涉及作为信息安全技术的加密技术，特别涉及数字署名的技术。 背景技术

[0002] 作为用来进行从接收装置向发送装置发送数据时的发送者的确定及防止数据的窜改的技术，有作为公开密钥加密的一种的数字署名方式。如果简单地说明，则是如下方法：发送装置使用发送装置的秘密密钥对想要发送的数据制作署名数据，与想要发送的数据一起将署名数据发送给发送装置，接收装置使用与发送装置的秘密密钥对应的公开密钥来验证署名数据，判断是否被窜改(例如参照非专利文献1)。这里，由公开密钥很难计算秘密密钥的值。

[0003] 最近，作为能够进行高速处理的公开密钥加密，提出了NTRU加密(例如参照非专利文献2)。该NTRU加密同在某个模下进行幂乘余数运算的RSA加密或进行椭圆曲线上的点的数乘(scalar倍)运算的椭圆曲线加密相比，由于利用可高速运算的多项式运算进行加密与解密，所以比以往的公开密钥加密更能高速地处理，在软件的处理中也能够以实用的时间进行处理。

[0004] 因而，在公开密钥加密中使用了NTRU加密的加密通信系统中，与以往的使用了公开密钥加密的加密通信系统相比，具有能够高速地进行发送装置及接收装置的处理的优点。

[0005] 在上述记载中提出的方式是将数据加密的保密加密方式，但此后提出了NTRU加密的数字署名方式(参照非专利文献3)。关于数字 署名方式，因解读法的出现等而其方式被变更了数次。以下，对称作NTRUSign的数字署名方式简单地进行说明(对于详细情况，参照专利文献2及非专利文献4)。

[0006] 在NTRUSign署名方式的密钥生成中，以多项式X^N-1为模，通过使用属于具有整数系数的多项式的环R的多个元、和环R的理想子环，生成秘密密钥及公开密钥。这里，“X^a”是指X的a次幂。在NTRUSign署名方式中的对于消息的署名中，使用生成的秘密密钥、和作为消息的哈希(Hash)值的2·N维的矢量。在NTRUSign署名方式的署名验证中，使用公开密钥、对于消息的署名、和作为消息的哈希值的2·N维的矢量。另外，在非专利文献4及非专利文献5中，记载了NTRUSign署名方式中使用的环及环的理想子环，所以省略这里的说明。

[0007]

[0008] (1)NTRUSign署名方式的参数

[0009] NTRUSign署名方式使用作为非负整数的参数N、q、df、dg、Normbound。以下说明这些参数的意义。

[0010] (1-1)参数N

[0011] NTRUSign署名方式是通过多项式的运算进行署名生成及署名验证的数字署名方式。在NTRUSign署名方式中处理的多项式的次数由上述参数N决定。

[0012] NTRUSign署名方式中处理的多项式是相对于上述参数N的N-1次以下的整数系数多项式，例如在N＝5时，是X^4+X^3+1等的多项式。另外，对于多项式实施(mod X^N-1)运算，计算出始终由N-1次以下构成的整数系数多项式。这是因为，通过实施(modX^N-1)运算，X^N＝1的关系式成立，所以对于N次以上的变量，能够始终变换为N-1次以下的变量。这里可知，通过对多项式实施(mod X^N-1)运算而得到的整数系数多项式为多项式环R的元。

[0013] 此外，公开密钥h、署名s都表现为N-1次以下的多项式。此外，秘密密钥是4个N-1次以下的多项式对(f，g，F，G)。即，f、g、F、G都是N-1次以下的多项式，是多项式环R的元。另外，以下有时也将4个组(f，g，F，G)分为两个对(f，g)，(F、G)的进一步的对，而标记为{(f，g)，(F、G)}。

[0014] 并且，多项式运算是，利用X^N＝1的关系式对上述参数N进行运算，以使运算结果总为N-1次以下的多项式。例如，在N＝5的情况下，多项式X^4+X^2+1与多项式X^3+X的积，如果设多项式与多项式的积为×、整数与多项式的积(或者整数与整数的积)为·，则根据X^5＝1的关系，如

[0015] (X^4+X^2+1)×(X^3+X)

[0016] ＝X^7+2·X^5+2·X^3+X

[0017] ＝X^2·1+2·1+2·X^3+X

[0018] ＝2·X^3+X^2+X+2

[0019] 所示地进行运算，以使其始终成为N-1次以下的多项式。

[0020] 另外，在NTRUSign署名方式中，N-1次的多项式a＝a_0+a_1·X+a_2·X^2+……+a_(N-1)·X^(N-1)看作与矢量(a_0，a_1，a_2，……，a_(N-1))相同。a_0，a_1，a_2，……，a_(N-1)是多项式a的系数，是整数。

[0021] (1-2)参数q

[0022] 在NTRUSign署名方式中，使用作为2以上整数的、作为多项式环R的理想子环的参数q。在NTRUSign署名方式中出现的多项式的系数，取以q为模的余数。

[0023] (1-3)参数df、dg

[0024] 在生成作为NTRUSign署名方式中处理的秘密密钥的一部分的多项式f及作为公开密钥的多项式h时与多项式f一起使用的多项式g的选择方法，分别由参数df、dg决定。 [0025] 首先，多项式f选择是，使df个系数为1，并且其他系数为0。即，多项式f是N-1次以下的多项式，从0次(常数项)到N-1次有N个系数，但进行使该N个系数中的df个系数是1、并且(N-df)个系数为0的选择。

[0026] 并且，多项式g选择是，使dg个的系数为1、其他系数为0。

[0027] (1-4)参数Normbound

[0028] 在NTRUSign署名方式中，如后面叙述，计算由署名s制作的2·N维的矢量与作为消息的哈希值的2·N维的矢量的距离，根据该距离判断是否是正确的署名。Normbound是在该判断时使用的阈值。即，如果上述距离小于Normbound，则作为正确的署名受理，如果是Normbound以上，则作为不正确的署名拒绝。

[0029] 在非专利文献4中，作为NTRUSign署名方式的参数的例子，可以举出(N，q，df，dg，Normbound)＝(251，128，73，71，310)的例子。

[0030] (2)消息的哈希值、范数及矢量间的距离

[0031] 在NTRUSign署名方式中，制作对于消息m的哈希值的署名。消息m的哈希值是N次多项式的对(m1，m2)，视为与2·N维的矢量相同。对于由消息求哈希值的哈希函数，非专利文献1中有详细记载。

[0032] 在NTRUSign署名方式中，在署名验证中使用矢量的距离。以下表示其定义。 [0033] 将多项式a＝a_0+a_1·X+a_2·X^2+……+a_(N-1)·X^(N-1)的范数‖a‖定义为如下。

[0034] ‖a‖＝sqrt((a_0-μ)^2+(a_1-μ)^2+……+(a_(N-1)-μ)^2)

[0035] μ＝(1/N)·(a_0+a_1+a_2+……+a_(N-1))

[0036] 这里，sqrt(x)表示x的平方根。

[0037] 多项式a、b的对(a，b)的范数‖(a，b)‖定义为如下。

[0038] ‖(a，b)‖＝sqrt(‖a‖^2+‖b‖^2)

[0039] 多项式a、b的对(a，b)与c、d的对(c，d)的距离，由‖(c-a，d-b)‖定义。 [0040] 由此，通过实施(mod X^N-1)运算得到的N-1次以下的整数系数多项式，可以看作定义了加法、减法、乘法、以及表示元的大小的范数的N维数组，多项式环R可以看作N维数组的集合。

[0041] (3)NTRUSign署名方式的密钥生成

[0042] 在NTRUSign署名方式中，如上所述，利用参数df、dg随机地生成多项式f、多项式g。并且，如非专利文献4所述，利用Fq×f＝1(mod q)的多项式Fq，通过

[0043] h＝Fq×g(mod q)

[0044] 生成多项式h。这里，多项式Fq称作多项式f的逆元。进而，求出满足下式的范数较小的多项式F、G。

[0045] f×G-g×F＝q

[0046] 设秘密密钥为{(f，g)，(F，G)}，公开密钥为h。秘密密钥是用来生成署名的密钥，也称作署名生成密钥。此外，公开密钥是用来验证署名的密钥，也称作署名验证密钥。 [0047] 这里，x＝y(mod q)是将多项式y的第i次的系数用模q除使余数包含在0到q-1的范围内时，使余数成为多项式x的第i次系数的运算(0≤i≤N-1)。即，是将对多项式y的各系数进行mod q运算以使其包含在0到q-1的范围内的多项式，作为多项式x的运算。

[0048] (4)NTRUSign署名方式的署名生成

[0049] 在NTRUSign署名方式的署名生成中，计算作为署名对象的消息m的署名s。首先，计算对消息m的哈希值即2·N维的矢量(m1，m2)(m1及m2是N次多项式)。

[0050] 利用该2·N维的矢量(m1，m2)与秘密密钥{(f，g)，(F，G)}，计算满足以下式的多项式a、b、A、B。

[0051] G×m1-F×m2＝A+q×B-g×m1+f×m2＝a+q×b

[0052] 这里，A、a的系数取为除以模q时的余数限制在从<-q/2>+1至的范围的余数。即，在用模q除时的余数为从(q/2)到q-1的情况下，减去q，调整成使其包含在上述范围内。这里，表示在x以下的数中最大的数。例如<-1/2>＝-1。

[0053] 接着，通过以下式计算s、t，将s作为署名输出。

[0054] s＝f×B+F×b(mod q)

[0055] t＝g×B+G×b(mod q)

[0056] (5)NTRUSign署名方式的署名验证

[0057] 在NTRUSign署名方式的署名生成中，验证署名s是否是作为署名对象的消息m的正确的署名。首先，计算作为对消息m的哈希值的2·N维矢量(m1，m2)。

[0058] 使用公开密钥h，通过以下的式计算多项式t。

[0059] t＝s×h(mod q)

[0060] 求出2·N维矢量(s，t)与(m1，m2)的距离，检查是否小于Normbound。如果小于Normbound，则判断署名s是正确的而接受署名s。如果是Normbound以上，则判断为署名s是不正确的而拒绝署名s。

[0061] 专利文献1：日本特表2000-516733号公报

[0062] 专利文献2：国际公开号WO2003/050998号

[0063] 非专利文献1：岡本龍明、山本博資，《現代暗号》，産業図書(1997年) [0064] 非专利文献2：J.Hoffstein，J.Pipher，and J.H.Silverman，“NTRU：Aring based public key cryptosystem”，Lecture Notes in Computer Science，1423，pp.267-288，Springer-Verlag，1998.

[0065] 非 专 利 文 献 3：J.Hoffstein，J.Pipher，and J.Silverman，“NSS：AnNTRU Lattice-Based Signature Scheme”，Advances inCryptoplogy-Eurocrypt’01，LNCS，Vol.2045，pp.123-137，Springer-Verlag，2001

[0066] 非专利文献4：J.Hoffstein，N.Graham，J.Pipher，J.Silverman andW.Whyte，“NTRUSign：Digital Signatures Using the NTRU Lattice”，CT-RSA’03，LNCS，Vol.2612，pp.122-140，Springer-Verlag，2003

[0067] 在上述的NTRUSign署名方式中，有称作抄本攻击(Transcriptattack)的攻击。抄本攻击是从多个署名文(消息与署名的对)求出秘密密钥的攻击。抄本攻击的详细情况记载在非专利文献4中，所以这里在以下简单地说明。

[0068] 抄本攻击利用多个署名s与消息的哈希值(m1，m2)的一部分m1的差分m1-s为 [0069] m1-s＝e1×f+e2×F

[0070] e1、e2是系数在-1/2到1/2的范围内的多项式，来取差分m1-s的2次矩及4次矩的平均值，求出作为秘密密钥的一部分的f，F。这里，多项式a的2次矩a～2是指，a＝a_0+a_1·X+a_2·X^2+……+a(N-2)·X^(N-2)+a_(N-1)·X^(N-1)和a的相反a*＝a_0+a_(N-1)·X+a_(N-2)·X^2+…+a_2·X^(N-2)+a_1·X^(N-1)的积a～＝a×a*。此外，4次矩a～4是a～2的平方、即a～4＝a～2×a～2。

[0071] (m1-s的2次矩)＝(e1×f+e2×F)×(e1*×f*+e2*×F*)

[0072] ＝e1～×f～+e2～×F～+e1×f×e2*×F*+e2×F×e1*×f*

[0073] 如果署名文件的个数增大，则包含在m1-s的2次矩的平均中的e1～、e2～收敛于某一定值k1、k2，上述式的e1×f×e2*×F*和e2×F×e1*×f*接近于0。因而，在署名文件的个数较大的情况下，m1-s的2次矩的平均大致等于k1×f～+k2×F～。进而，在4次矩的 平均中，也同样能得到与f及F关联的信息，能够根据两者的信息求出f。根据非专利文献4，为了从2次矩及4次矩的平均求出有关秘密密钥的信息所需的署名文的个数分别为10^4、10^8。因而，为了使NTRUSign署名方式的抄本攻击成功，认为需要10^8个以上的署名文。

发明内容

[0074] 本发明的目的是提供一种能够防止对署名数据的抄本攻击(Transcript attack)的署名生成装置、署名验证装置、署名系统、署名生成方法、署名验证程序、署名验证方法、署名验证程序、署名生成用的集成电路及署名验证用的集成电路。

[0075] 为了达到上述目的，本发明是一种使用署名密钥进行署名的署名生成装置，其具备：密钥存储单元，存储着上述署名密钥；署名生成单元，使用上述署名密钥对署名对象数据实施署名，生成署名数据；计数单元，在生成上述署名数据时，对使用上述署名密钥进行了署名的累积次数进行计数；判断单元，判断由上述计数单元计数的累积次数是否达到了规定次数；署名禁止单元，在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，以后禁止使用上述署名密钥进行的署名。

[0076] 这里，所谓的署名禁止单元的署名禁止，包括禁止使用由密钥存储单元存储的署名密钥的概念，以及将存储在密钥存储单元中的署名密钥删除、将另外的署名密钥写入密钥存储单元的覆盖的概念两者。

[0077] 根据上述所示的结构，署名生成装置对使用署名密钥进行了署名的累积次数进行计数，在累积次数达到了规定次数时，以后禁止使用上述署名密钥进行的署名，所以能够防止对于使用了上述署名密钥的署名的抄本攻击。

[0078] 这里，也可以是，在判断为由上述计数单元计数的累积次数达到 了上述规定次数的情况下，上述署名禁止单元通过生成上述署名密钥之外的另外的署名密钥、并用生成的上述另外的署名密钥对由上述密钥存储单元存储的上述署名密钥进行覆盖，来禁止使用上述署名密钥进行的署名。

[0079] 根据该结构，署名生成装置在累积次数达到了规定次数的情况下生成上述署名密钥之外的另外的署名密钥，用生成的上述另外的署名密钥对由上述密钥存储单元存储的上述署名密钥进行覆盖，所以能够可靠地禁止使用了上述署名密钥的署名。

[0080] 这里，也可以是，上述署名生成装置还具备：验证密钥证书存储单元，存储有验证密钥证书，该验证密钥证书包含对应于上述署名密钥的验证密钥、和表示上述验证密钥的正当性且由第1秘密密钥生成的验证密钥署名数据；公开密钥证书存储单元，存储有公开密钥证书，该公开密钥证书包含对应于上述第1秘密密钥的公开密钥、和表示上述公开密钥的正当性且由外部机构所具有的第2秘密密钥生成的公开密钥署名数据；发送单元，将上述署名对象数据、由上述署名生成单元生成的上述署名数据、上述验证密钥证书、和上述公开密钥证书发送给进行上述署名数据的验证的署名验证装置。

[0081] 根据该结构，由于署名生成装置将署名数据的验证所需的验证密钥多阶层化后发送给署名验证装置，所以能够提高验证密钥的正当性。

[0082] 这里，也可以是，在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，上述署名禁止单元还对应上述另外的署名密钥而生成上述验证密钥之外的另外的验证密钥，对于生成的上述另外的验证密钥，使用上述第1秘密密钥生成上述验证密钥署名数据之外的另外的验证密钥署名数据，生成包含上述另外的验证密钥和上述另外的验证密钥署名数据的、上述验证密钥证书之外的另外的验证密钥证书，用生成的上述另外的验证密钥证书对存储在上述公开密钥证 书存储单元中的上述验证密钥证书进行覆盖。 [0083] 根据该结构，在累积次数达到了规定次数的情况下，署名生成装置生成上述验证密钥证书之外的另外的验证密钥证书，用生成的上述另外的验证密钥证书对由上述验证密钥证书存储单元存储的上述验证密钥证书进行覆盖。由此，能够取得另外的署名密钥与另外的验证密钥证书的同步，署名生成装置能够将生成的另外的署名密钥用于署名。 [0084] 这里，也可以是，上述署名生成装置还具备存储有表示上述署名密钥的第1密钥信息的信息存储单元；上述署名生成单元根据存储在上述存储单元中的第1密钥信息，从上述密钥存储单元取得上述署名密钥，使用取得的上述署名密钥生成上述署名数据；上述密钥存储单元还存储上述署名密钥之外的另外的署名密钥；在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，上述署名禁止单元通过将由上述信息存储单元存储的上述第1密钥信息改写为表示上述另外的署名密钥的第2密钥信息，来禁止使用上述署名密钥进行的署名。

[0085] 根据该结构，在累积次数达到了规定次数的情况下，署名生成装置将由信息存储单元存储的第1密钥信息改写为第2密钥信息，所以能够可靠地禁止使用了上述署名密钥的署名。

[0086] 这里，也可以是，上述署名生成单元取得由上述计数单元计数的累积次数；上述署名对象数据包含消息数据和取得的累积次数。

[0087] 根据该结构，由于署名生成装置在署名对象数据中包含有消息数据和累积次数，所以能够提高生成的署名数据的正当性。

[0088] 这里，也可以是，上述署名生成装置还具备对时刻进行计时的时钟单元；上述署名生成单元利用上述时钟单元取得作为署名数据的有效期限判断基准的时刻信息；上述署名对象数据包含消息数据和取得的上述时刻信息。

[0089] 根据该结构，由于署名生成装置在署名对象数据中包含有消息数据和时刻信息，所以能够提高生成的署名数据的正当性。

[0090] 这里，也可以是，上述判断单元具有存储了上述规定次数的次数存储部；上述署名生成装置还具备将由上述次数存储部存储的上述规定次数更新为另外的规定次数的更新单元。

[0091] 根据该结构，即使在抄本攻击所需的署名数据的数量被变更的情况下，署名生成装置也能够更新规定次数，所以能够防止抄本攻击。

[0092] 此外，本发明是一种验证由使用署名密钥进行署名的署名生成装置生成的署名数据的署名验证装置，其具备：接收单元，从上述署名生成装置接收包含消息数据与上述署名生成装置使用上述署名密钥进行了署名的累积次数的署名对象数据、和对于上述署名对象数据的署名数据；次数判断单元，判断包含在接收到的上述署名对象数据中的上述累积次数是否达到了规定次数；验证禁止单元，在判断为上述累积次数达到了上述规定次数的情况下，禁止上述署名数据的验证。

[0093] 根据该结构，在接收到的署名对象数据中包含的累积次数达到了规定次数的情况下，署名验证装置禁止接收到的署名数据的验证。由此，若接收到累积次数达到规定次数的署名数据，则能够不验证接收到的署名数据就将其视为不正当的。

[0094] 这里，也可以是，上述署名对象数据还包含作为上述署名数据的有效期限判断基准的第1时刻信息；上述署名验证装置还具备：时钟单元，对时刻进行计时；期限判断单元，在判断为上述累积次数没有达到上述规定次数的情况下，使用上述时钟单元取得表示当前时刻的第2时刻信息，利用上述第1时刻信息和取得的第2时刻信息，判断是否已超过上述署名数据的有效期限；验证单元，在判断为没有超过上述署名数据的有效期限的情况下，验证上述署名数据；上述验证禁止单元还在判断为已超过上述署名数据的有效期限的情况下，禁止上述署名数据的验证。

[0095] 根据该结构，在已超过接收到的署名数据的有效期限的情况下，署名验证装置禁止接收到的署名数据的验证。由此，若接收到有效期限已过的署名数据，则能够不验证接收到的署名数据就将其视为不正当的。

[0096] 这里，也可以是，上述署名数据是使用上述署名生成装置所生成的署名密钥生成的；上述接收单元还接收包含对应于上述署名密钥的验证密钥、和表示上述验证密钥的正当性且包括利用第1秘密密钥生成的验证密钥署名数据的验证密钥证书，以及包含对应于上述第1秘密密钥的第1公开密钥、和表示上述第1公开密钥的正当性且包括利用外部机构所具有的第2秘密密钥生成的公开密钥署名数据的公开密钥证书；上述验证单元具备：密钥存储部，存储有对应于上述第2秘密密钥的第2公开密钥；第1验证部，在判断为没有超过上述署名数据的有效期限的情况下，使用上述第2公开密钥来验证上述公开密钥证书是否是正当的；第2验证部，在判断为上述公开密钥证书是正当的情况下，使用上述第1公开密钥来验证上述验证密钥证书是否是正当的；第3验证部，在判断为上述验证密钥证书是正当的情况下，验证上述署名数据是否是正当的。

[0097] 根据该结构，由于署名验证装置接收被多阶层化的验证密钥，从阶层化的上层开始依次进行署名验证，所以能够进行可靠性较高的验证。

[0098] 这里，也可以是，上述署名验证装置还具备发送单元，在判断为上述累积次数达到了上述规定次数的情况下，该发送单元将确定生成了上述署名数据的上述署名生成装置的确定信息发送给外部装置。

[0099] 根据该结构，在接收到的署名对象数据中包含的累积次数达到了规定次数的情况下，署名验证装置将确定生成接收到的署名数据的上述署名生成装置的确定信息发送给外部装置，所以能够使外部装置进行生成了不正当署名数据的署名生成装置的管理。 [0100] 这里，也可以是，上述次数判断单元具有存储上述规定次数的次数存储区域；上述署名验证装置还具备从上述署名生成装置接收上述规定次数之外的另外的规定次数、将由上述次数存储区域存储的上述规定次数更新为接收到的上述另外的规定次数的更新单元。 [0101] 根据该结构，署名验证装置能够在与署名生成装置之间取得规定次数的同步。 [0102] 此外，本发明是一种包括使用署名密钥进行署名的署名生成装置和验证由上述署名生成装置生成的署名数据的署名验证装置的署名系统，上述署名生成装置具备：密钥存储单元，存储着上述署名密钥；署名生成单元，使用上述署名密钥对包含消息数据和使用上述署名密钥进行了署名的累积次数的署名对象数据实施署名，生成上述署名数据；计数单元，在生成上述署名数据时，对上述累积次数进行计数；判断单元，判断由上述计数单元计数的累积次数是否达到了规定次数；署名禁止单元，在判断为由上述计数单元计数的累积次数达到了上述规定次数的情况下，以后禁止使用上述署名密钥进行的署名；发送单元，向上述署名验证装置发送包含上述署名对象数据与上述署名数据的数据组；上述署名验证装置具备：接收单元，从上述署名生成装置接收上述数据组；次数判断单元，判断包含在接收到的上述数据组的上述署名对象数据中的上述累积次数是否达到了规定次数；验证禁止单元，在通过上述次数判断单元判断为上述累积次数达到了上述规定次数的情况下，禁止上述署名数据的验证。

[0103] 根据该结构，署名系统在署名生成装置中对使用秘密密钥进行了署名的累积次数进行计数，在累积次数达到了规定次数的情况下，以后禁止使用上述秘密密钥进行的署名，所以能够防止对使用了上述秘密密钥的署名的抄本攻击。此外，署名系统中，在署名验证装置中接收到的署名对象数据中包含的累积次数达到了规定次数的情况下，禁止接收到的署名数据的验证，所以若接收到累积次数达到了规定次数 的署名数据，则能够不验证接收到的署名数据就将其视为不正当的。

[0104] 这里，也可以是，上述署名系统还具备监视从上述署名生成装置向上述署名验证装置发送的上述数据组的监视装置；上述监视装置具备：取得单元，从连接上述署名生成装置与上述署名验证装置的传输通道取得上述数据组；日志存储单元，在取得上述数据组之前，存储已经取得的1个以上的已取得数据组；数据判断单元，使用上述1个以上的已取得数据组，判断所取得的上述数据组是否是正当的；信息发送单元，在判断为上述数据组是不正当的情况下，向外部装置发送对生成了包含在所取得的上述数据组中的上述署名数据的上述署名生成装置进行确定的确定信息。

[0105] 根据该结构，署名系统在监视装置中监视传输通道中流过的数据组是否正当，在是不正当的数据组的情况下，向外部装置发送对生成了包含在该数据组中的署名数据的署名生成装置进行确定的确定信息。由此，署名系统能够使外部装置进行生成了包含在不正当的数据组中的署名数据的署名生成装置的管理。

[0106] 这里，也可以是，上述数据组还包含对应于上述署名密钥的验证密钥；上述1个以上的已取得数据组分别包括：包含已取得累积次数的已取得署名对象数据，和已取得验证密钥；上述数据判断单元检索在日志存储单元中是否存在包含与上述验证密钥及上述累积次数一致的已取得验证密钥及已取得累积次数的已取得数据组，在存在的情况下，判断所取得的上述数据组是不正当的。

[0107] 根据该结构，署名系统在监视装置中能够使用包含在数据组中的验证密钥及累积次数，来判断数据组是否是正当的。

附图说明

[0108] 图1是表示数字署名系统1的结构的框图。

[0109] 图2是表示由署名生成装置10进行的初始设定处理动作的流程 图。 [0110] 图3是表示由署名生成装置10进行的署名生成处理动作的流程图。

[0111] 图4是表示由署名生成装置10进行的计数值检查处理动作的流程图。 [0112] 图5是表示由署名验证装置20进行的署名验证处理动作的流程图。

[0113] 图6是表示数字署名系统1000的结构的框图。

[0114] 图7是表示由署名生成装置1010进行的署名生成处理动作的流程图。 [0115] 图8是表示由署名验证装置1020进行的署名验证处理动作的流程图。 [0116] 图9是表示由署名监视服务器1030进行的监视处理动作的流程图。

[0117] 附图标记说明

[0118] 1 数字署名系统

[0119] 10 署名生成装置

[0120] 20 署名验证装置

[0121] 50 通信通道

[0122] 101 用户署名生成密钥保存部

[0123] 102 用户证书保存部

[0124] 103 个数限定署名生成密钥保存部

[0125] 104 个数限定证书保存部

[0126] 105 署名生成部

[0127] 106 署名数据组生成部

[0128] 107 计数部

[0129] 108 计数判断部

[0130] 109 个数限定密钥生成部

[0131] 110 发送部

[0132] 150 初始设定部

[0133] 151 署名禁止部

[0134] 201 CA公开密钥保存部

[0135] 202 署名数据组保存部

[0136] 203 署名验证部

[0137] 204 接收部

[0138] 205 显示部

[0139] 1000 数字署名系统

[0140] 1010 署名生成装置

[0141] 1020 署名验证装置

[0142] 1030 署名监视服务器

[0143] 1040 中心

[0144] 1050 通信通道

[0145] 1101 用户署名生成密钥保存部

[0146] 1102 用户证书保存部

[0147] 1103 个数限定署名生成密钥保存部

[0148] 1104 个数限定证书保存部

[0149] 1105 署名生成部

[0150] 1106 署名数据组生成部

[0151] 1107 计数部

[0152] 1108 计数判断部

[0153] 1109 个数限定密钥生成部

[0154] 1110 发送部

[0155] 1111 时钟部

[0156] 1201 CA公开密钥保存部

[0157] 1202 署名数据组保存部

[0158] 1203 署名验证部

[0159] 1204 接收部

[0160] 1205 显示部

[0161] 1206 计数判断部

[0162] 1207 时刻判断部

[0163] 1208 时钟部

[0164] 1301 日志保存部

[0165] 1302 通信监视部

[0166] 1303 署名数据组取得部

[0167] 1304 署名数据组判断部

[0168] 1305 收发部

具体实施方式

[0169] 1、第一实施方式

[0170] 下面，参照附图说明作为本发明涉及的第一实施方式的数字署名系统1。 [0171] 1.1数字署名系统1的概要

[0172] 数字署名系统1如图1所示，包括署名生成装置10、署名验证装置20、和通信通道50。

[0173] 署名生成装置10生成对消息数据m的署名数据组SS，经由通信通道50向署名验证装置20发送署名数据组SS。另外，关于署名数据组SS，在后面叙述。

[0174] 署名验证装置20接收该署名数据组SS，验证接收到的署名数据组SS是否是消息数据m的正确的署名。署名验证装置20判断为署名数据组SS是正确的情况下，接受署名数据组SS，在判断为署名数据组SS不正确的情况下，拒绝署名数据组SS。

[0175] 1.2署名生成装置10的结构

[0176] 署名生成装置10如图1所示，包括用户署名生成密钥保存部101、用户证书保存部102、个数限定署名生成密钥保存部103、个数限定证书保存部104、署名生成部105、署名数据组生成部106、计数部107、计数判断部108、个数限定密钥生成部109、和发送部110。 [0177] 署名生成装置10保存在NTRUSign署名方式中使用的秘密密钥即个数限定署名生成密钥、和与对应于上述秘密密钥的公开密钥相对应的公开密钥证书即个数限定证书，使用个数限定署名生成密钥，生成对于作为输入的消息数据m的署名数据S。此外，署名生成装置10对生成的署名数据的个数进行计数，在计数的值超过规定的阈值tc的情况下，生成新的个数限定署名生成密钥及个数限定证书。

[0178] 另外，阈值tc是NTRUSign署名方式的抄本攻击不成功的署名个数，例如是10^7。此外，个数限定证书的详细情况在后面叙述。

[0179] (1)用户署名生成密钥保存部101

[0180] 用户署名生成密钥保存部101保存着为了生成个数限定证书CL而使用的用户署名生成密钥KUG。假设用户署名生成密钥KUG是预先提供的。

[0181] 这里，个数限定证书CL包括对应于个数限定署名生成密钥的个数限定署名验证密钥KLV(公开密钥)、和使用用户署名生成密钥KUG对个数限定署名验证密钥KLV实施了署名的署名数据SKLV。

[0182] 另外，在个数限定证书中，除了个数限定署名验证密钥KLV及署名数据SKLV以外，也可以包含有其他数据。例如，也可以包含用来识别个数限定证书的识别符。署名数据SKLV是基于NTRUSign署名方式生成的。关于NTRUSign署名方式，在非专利文献4中详细地记述，由于是公知的技术，所以省略这里的说明。

[0183] (2)用户证书保存部102

[0184] 用户证书保存部102保存着对应于用户署名生成密钥KUG的用 户证书CU。用户证书CU包括对应于用户署名生成密钥的用户署名验证密钥KUV、使用证书生成服务器CA(未图示)的秘密密钥对用户署名验证密钥KUV实施了署名的署名数据SKUV。署名数据SKUV也是基于NTRUSign署名方式生成的。此外，用户证书CU也与用户署名生成密钥KUG同样，假设是预先提供的。另外，在用户证书CU中，除了用户署名验证密钥KUV及署名数据SKUV以外，也可以包含有其他数据。例如，也可以包含用户的识别符及证书的期限等。 [0185] 这里，证书生成服务器CA是在称作认证局(Certificate Authority)的机构中具备的装置，发布表示用户署名验证密钥KUV是正确的公开密钥的(作为对公开密钥的“盖官印”的)“用户证书”。即，用户证书保存部102预先保存有由证书生成服务器CA发布的用户证书CU。此外，认证局生成对每个署名生成装置不同的用户署名生成密钥及用户署名验证密钥，还利用证书生成服务器CA生成对所生成的用户署名验证密钥的用户证书。认证局将生成的用户署名生成密钥及用户证书密钥分发给署名生成装置。由此，署名生成装置能够预先保存用户署名生成密钥和用户证书密钥。

[0186] (3)个数限定署名生成密钥保存部103

[0187] 个数限定署名生成密钥保存部103具有为了生成对消息数据的署名数据而使用的个数限定署名生成密钥KLG的区域。

[0188] 署名生成装置10生成个数限定署名生成密钥，将生成的个数限定署名生成密钥保存到个数限定署名生成密钥保存部103。

[0189] (4)个数限定证书保存部104

[0190] 个数限定证书保存部104具有用于保存对应于个数限定署名生成密钥KLG的个数限定证书CL的区域。

[0191] 署名生成装置10生成个数限定证书，将生成的个数限定证书保存到个数限定证书保存部104。

[0192] (5)署名生成部105

[0193] 署名生成部105进行消息数据m的署名数据S的生成、以及个数限定署名验证密钥KLV的署名数据SKLV的生成。

[0194] <生成署名数据S的情况>

[0195] 如果署名生成部105从署名数据组生成部106接受了表示指示生成消息数据m的署名数据的第1署名生成指示，则读取保存在个数限定署名生成密钥保存部103中的个数限定署名生成密钥KLG，利用读取的个数限定署名生成密钥KLG，生成对消息数据m的署名数据S，即对消息数据m实施署名而生成署名数据S。

[0196] 如果署名数据S的生成结束，则署名生成部105将表示该消息的第1结束通知向署名数据组生成部106输出。

[0197] 署名生成部105在将第1结束通知向署名数据组生成部106输出后，将指示判断计数的值是否超过了规定值tc的计数判断指示向计数判断部108输出。

[0198] 另外，署名数据S是基于NTRUSign署名方式生成的。

[0199] <生成署名数据SKLV的情况>

[0200] 如果署名生成部105从个数限定密钥生成部109接受了表示指示生成用户署名验证密钥KLV的署名数据SKLV的第2署名生成指示，则读取保存在用户署名生成密钥保存部101中的用户署名验证密钥KUG，使用读取的用户署名生成密钥KUG，生成对由个数限定密钥生成部109生成的个数限定署名验证密钥KLV的署名数据SKLV，即对个数限定署名验证密钥KLV实施署名而生成署名数据SKLV。另外，关于个数限定密钥生成部109的动作，在后面叙述。

[0201] 如果署名数据SKLV的生成结束，则署名生成部105将表示该消息的第2结束通知向个数限定密钥生成部109输出。

[0202] 另外，署名数据SKLV是基于NTRUSign署名方式而生成的。

[0203] 此外，在密钥更新时，在由个数限定密钥生成部109生成了个数限定署名验证密钥KLVN的情况下，通过与上述同样的动作，署名 生成部105生成署名数据SKLVN。此时，署名生成部105将由个数限定密钥生成部109生成的个数限定署名验证密钥KLVN作为新的个数限定署名验证密钥KLV，生成署名数据SKLVN。

[0204] (6)署名数据组生成部106

[0205] 如果署名数据组生成部106通过用户的操作接受了消息数据m，则从个数限定证书保存部104读取个数限定证书CL、从用户证书保存部102读取用户证书CU。 [0206] 署名数据组生成部106将第1署名生成指示向署名生成部105输出，然后，如果从署名生成部105接受了第1结束通知，则生成由消息数据m、在署名生成部105生成的消息数据m的署名数据S、读取的个数限定证书CL、和读取的用户证书CU构成的署名数据组SS。

[0207] 署名数据组生成部106经由发送部110将生成的署名数据组SS向署名验证装置20发送。

[0208] (7)计数部107

[0209] 计数部107具备对生成了署名数据S的次数进行计数、并保持当前的署名数据生成次数的计数器。

[0210] 如果计数部107从个数限定密钥生成部109接受了将计数值c设定为初始值0的初始值设定指示，则使计数值c＝0。

[0211] 如果由署名生成部105生成了署名数据S，计数部107则对计数值c加1，将加法运算后的结果再次作为计数值c保持。

[0212] 由此，计数部107能够对利用保存在个数限定署名生成密钥保存部103中的个数限定署名生成密钥KLG生成的署名数据个数进行计数。此外，换言之，计数部107能够对保存在个数限定署名生成密钥保存部103中的个数限定署名生成密钥KLG的使用次数进行计数。

[0213] (8)计数判断部108

[0214] 计数判断部108预先保存着阈值tc。

[0215] 如果计数判断部108从署名生成部105接受了计数判断指示，则 判断计数部107的计数值c是否是阈值tc以上。

[0216] 在判断为是阈值tc以上的情况下，计数判断部108向个数限定密钥生成部109输出指示个数限定署名生成密钥及个数限定署名验证密钥的更新的密钥更新指示。 [0217] (9)个数限定密钥生成部109

[0218] 个数限定密钥生成部109生成个数限定署名生成密钥及个数限定证书。 [0219] 个数限定密钥生成部109如图1所示，具有初始设定部150和署名禁止部151。 [0220] <初始设定部150>

[0221] 将个数限定署名生成密钥及个数限定证书作为初始设定保存到个数限定署名生成密钥保存部103及个数限定证书保存部104中的情况下，初始设定部150生成个数限定署名生成密钥及个数限定证书。

[0222] 以下对其动作进行说明。

[0223] 如果个数限定密钥生成部109的初始设定部150通过用户的操作而接受了进行初始设定的初始设定指示，则生成NTRUSign署名方式的秘密密钥及公开密钥。 [0224] 初始设定部150将生成的秘密密钥作为个数限定署名生成密钥KLG、将生成的公开密钥作为个数限定署名验证密钥KLV，将个数限定署名生成密钥KLG保存到个数限定署名生成密钥保存部103中。

[0225] 初始设定部150向署名生成部105输出第2署名生成指示。然后，若初始设定部150从署名生成部105接受了第2结束通知，则生成由个数限定署名验证密钥KLV和由署名生成部105生成的署名数据SKLV构成的个数限定证书CL。

[0226] 初始设定部150将生成的个数限定证书CL保存到个数限定证书保存部104中。 [0227] 初始设定部150向计数部107输出初始值设定指示。

[0228] <署名禁止部151>

[0229] 署名禁止部151对应于在上述的“发名内容”中记述的署名禁止单元，在计数值c超过了阈值tc的情况下，在该时刻禁止使用了保存在个数限定署名生成密钥保存部103中的秘密密钥的署名。

[0230] 这里，作为署名禁止的一例，使用覆盖的概念。

[0231] 以下，对署名禁止部151的动作进行说明。

[0232] 若署名禁止部151从计数判断部108接受了密钥更新指示，则通过NTRUSign署名方式的密钥生成，生成新的个数限定署名生成密钥KLGN作为秘密密钥、生成新的个数限定署名验证密钥KLVN作为公开密钥。

[0233] 署名禁止部151首先将保存在个数限定署名生成密钥保存部103中的个数限定署名生成密钥KLG删除，然后，将个数限定署名生成密钥KLGN作为新的个数限定署名生成密钥KLG，写入到个数限定署名生成密钥保存部103中。即，署名禁止部151通过用个数限定署名生成密钥KLGN覆盖并更新保存在个数限定署名生成密钥保存部103中的个数限定署名生成密钥KLG，成为个数限定署名生成密钥KLG。

[0234] 署名禁止部151将第2署名生成指示向署名生成部105输出。然后，若署名禁止部151从署名生成部105接受了第2结束通知，则生成由个数限定署名验证密钥KLVN和在署名生成部105生成的署名数据SKLVN构成的个数限定证书CLN。此时，署名禁止部151将个数限定署名验证密钥KLVN作为新的个数限定署名验证密钥KLV、将署名数据SKLVN作为新的署名数据SKLV，生成个数限定证书CLN。

[0235] 署名禁止部151将保存在个数限定证书保存部104中的个数限定证书CL删除，然后，将生成的个数限定证书CLN作为新的个数限定证书CL，写入到个数限定证书保存部104中。即，署名禁止部151 通过用生成的个数限定证书CLN覆盖并更新保存于个数限定证书保存部104中的个数限定证书CL，成为新的个数限定证书CL。

[0236] 署名禁止部151向计数部107输出初始值设定指示。

[0237] (10)发送部110

[0238] 发送部110经由通信通道50向署名验证装置20发送署名数据组SS。

[0239] 1.3署名验证装置20的结构

[0240] 署名验证装置20如图1所示，包括CA公开密钥保存部201、署名数据组保存部202、署名验证部203、接收部204和显示部205。

[0241] (1)CA公开密钥保存部201

[0242] CA公开密钥保存部201保存着与用于验证用户证书CU的证书生成服务器CA(未图示)所具有的秘密密钥相对应的公开密钥(署名验证密钥)KPC。

[0243] (2)署名数据组保存部202

[0244] 署名数据组保存部202具有用来保存署名数据组SS的区域。

[0245] (3)署名验证部203

[0246] 署名验证部203验证包含在署名数据组SS中的署名数据S、包含在个数限定证书CL中的署名数据SKLV、包含在用户证书CU中的署名数据SKUV。

[0247] 以下，示出验证的动作。

[0248] 署名验证部203从接收部204接受表示开始验证的验证开始指示。

[0249] 署名验证部203使用保存在CA公开密钥保存部中的CA公开密钥KPC，验证署名数据SKUV是否是用户署名验证密钥KUV的正确的署名。

[0250] 在判断为署名数据SKUV是正确的署名的情况下，署名验证部203使用用户署名验证密钥KUV验证署名数据SKLV是否是个数限 定署名验证密钥KLV的正确的署名。 [0251] 在判断为署名数据SKLV是正确的署名的情况下，署名验证部203使用个数限定署名验证密钥KLV验证署名数据S是否是消息数据m的正确的署名。

[0252] 在判断为署名数据S是正确的署名的情况下，署名验证部203向显示部205输出表示受理接受到的署名数据组SS的消息“OK”。

[0253] 在各署名验证中的任一个署名验证中，在判断为署名数据是不正确的署名的情况下，署名验证部203向显示部205输出表示拒绝接收到的署名数据组SS的消息“NG”。 [0254] (4)接收部204

[0255] 接收部204经由通信通道50接收从署名生成装置10发送的署名数据组SS。 [0256] 接收部204将接收到的署名数据组SS存储到署名数据组保存部202，然后，向署名验证部203输出验证开始指示。

[0257] (5)显示部205

[0258] 若显示部205从署名验证部203接受了与署名验证的验证结果有关的消息，则显示接受的消息。

[0259] 1.4署名生成装置10的动作

[0260] 署名生成装置10的动作包括对个数限定署名生成密钥及个数限定证书进行初始设定的“初始设定处理”、进行署名生成的“署名生成处理”、和检查计数值并生成个数限定署名生成密钥及个数限定证书的“计数值检查处理”的动作。下面，说明各个动作。 [0261] (1)初始设定处理

[0262] 利用图2表示的流程图，对初始设定处理的动作进行说明。

[0263] 若个数限定密钥生成部109的初始设定部150通过用户的操作接受了初始设定指示，则通过NTRUSign署名方式的密钥生成，生成秘密密钥及公开密钥(步骤S5)，将生成的秘密密钥作为个数限定署名 生成密钥KLG、将公开密钥作为个数限定署名验证密钥KLV，将个数限定署名生成密钥KLG保存到个数限定署名生成密钥保存部103中(步骤S10)。 [0264] 个数限定密钥生成部109的初始设定部150向署名生成部105输出第2署名生成指示。若署名生成部105从个数限定密钥生成部109接受了第2署名生成指示，则使用保存在用户署名生成密钥保存部101中的用户署名生成密钥KUG，生成个数限定署名验证密钥KLV的署名数据SKLV(步骤S15)。

[0265] 署名生成部105向个数限定密钥生成部109的初始设定部150输出第2结束通知。若个数限定密钥生成部109的初始设定部150从署名生成部105接受了第2结束通知，则生成由个数限定署名验证密钥KLV和在署名生成部105生成的署名数据SKLV构成的个数限定证书CL(步骤S20)，将生成的个数限定证书CL保存到个数限定证书保存部104中(步骤S25)。

[0266] 个数限定密钥生成部109的初始设定部150将初始值设定指示向计数部107输出。若计数部107从个数限定密钥生成部109接受到初始值设定指示，则保存计数值c＝0(步骤S30)。

[0267] (2)署名生成处理

[0268] 利用图3所示的流程图，对署名生成处理的动作进行说明。

[0269] 署名数据组生成部106通过用户的操作接受消息数据m(步骤S100)。 [0270] 署名数据组生成部106分别从个数限定证书保存部104读取个数限定证书CL、从用户证书保存部102读取用户证书CU，向署名生成部105输出第1署名生成指示。若署名生成部105从署名数据组生成部106接受到第1署名生成指示，则读取保存在个数限定署名生成密钥保存部103中的个数限定署名生成密钥KLG，使用读取的个数限定署名生成密钥KLG，生成对消息数据m的署名数据S(步骤 S105)。计数部107对计数值c加1，将相加结果作为新的计数值c(步骤S110)。

[0271] 若署名数据S的生成结束，则署名生成部105将表示该消息的第1结束通知向署名数据组生成部106输出。若署名数据组生成部106从署名生成部105接受到第1结束通知，则生成由消息数据m、在署名生成部105生成的消息数据m的署名数据S、读取的个数限定证书CL、和读取的用户证书CU构成的署名数据组SS(步骤S115)。

[0272] 发送部110经由通信通道50将在署名数据组生成部106生成的署名数据组SS向署名验证装置20发送(步骤S120)。

[0273] (3)计数值检查处理

[0274] 利用图4所示的流程图，对计数值检查处理的动作进行说明。另外，假设署名生成部105在执行署名生成处理的步骤S105之后，将计数器判断指示向计数判断部108输出。 [0275] 若计数判断部108从署名生成部105接受了计数判断指示，则判断计数部107的计数值c是否是阈值tc以上(步骤S200)。

[0276] 在判断为不是阈值tc以上的情况下(步骤S200中的“否”)，计数值检查处理结束。

[0277] 在判断为是阈值tc以上的情况下(步骤S200中的“是”)，计数判断部108向个数限定密钥生成部109的署名禁止部151输出指示个数限定署名生成密钥及个数限定署名验证密钥的更新的密钥更新指示。若个数限定密钥生成部109的署名禁止部151从计数判断部108接受了密钥更新指示，则分别生成NTRUSign署名方式的秘密密钥及公开密钥作为个数限定署名生成密钥KLGN，生成公开密钥作为个数限定署名验证密钥KLVN。 [0278] 个数限定密钥生成部109的署名禁止部151用生成的个数限定署名生成密钥KLGN覆盖保存于个数限定署名生成密钥保存部103中的个数限定署名生成密钥KLG，成为新的个数限定署名生成密钥 KLG(步骤S210)。即，署名禁止部151首先将保存在个数限定署名生成密钥保存部103中的个数限定署名生成密钥KLG删除，然后将个数限定署名生成密钥KLGN作为新的个数限定署名生成密钥KLG，写入到个数限定署名生成密钥保存部103中。 [0279] 个数限定密钥生成部109的署名禁止部151将第2署名生成指示向署名生成部105输出。若署名生成部105从署名禁止部151接受了第2署名生成指示，则利用保存在用户署名生成密钥保存部101中的用户署名生成密钥KUG，生成个数限定署名验证密钥KLVG的署名数据SKLVN(步骤S215)。

[0280] 署名生成部105将第2结束通知向个数限定密钥生成部109的署名禁止部151输出。若个数限定密钥生成部109的署名禁止部151从署名生成部105接受了第2结束通知，则生成由个数限定署名验证密钥KLVN和在署名生成部105生成的署名数据SKLVN构成的个数限定证书CLN(步骤S220)。此时，署名禁止部151将个数限定署名验证密钥KLVN作为新的个数限定署名验证密钥KLV、将署名数据SKLVN作为新的署名数据SKLV，生成个数限定证书CLN。

[0281] 个数限定密钥生成部109的署名禁止部151用生成的个数限定证书CLN覆盖保存于个数限定证书保存部104中的个数限定证书CL，成为新的个数限定证书CL(步骤S225)。即，署名禁止部151将保存于个数限定证书保存部104中的个数限定证书CL删除，然后将生成的个数限定证书CLN作为新的个数限定证书CL，写入到个数限定证书保存部104中。 [0282] 个数限定密钥生成部109的署名禁止部151将初始值设定指示向计数部107输出。若计数部107从署名禁止部151接受了初始值设定指示，则保存计数值c＝0(步骤S230)。

[0283] 1.5署名验证装置20的动作

[0284] 署名验证装置20经由通信通道50从署名生成装置10接收署名 数据组SS，验证该署名数据组SS。以下，利用图5所示的流程图说明由署名验证装置20进行的署名验证处理。

[0285] 接收部204经由通信通道50接收从署名生成装置10发送的署名数据组SS(步骤S300)。

[0286] 接收部204将接收到的署名数据组SS保存到署名数据组保存部202中(步骤S305)。

[0287] 接收部204将验证开始指示向署名验证部203输出。署名验证部203从接收部204接受验证开始指示。署名验证部203对于在署名数据组SS中的用户证书CU中包含的用户署名验证密钥KUV和其署名数据SKUV，使用保存在CA公开密钥保存部中的CA公开密钥KPC验证署名数据SKUV是否是用户署名验证密钥KUV的正确的署名(步骤S310)。 [0288] 在判断为署名数据SKUV是正确的署名的情况下(步骤S310中的“是”)，署名验证部203对于在署名数据组SS中的个数限定证书CL中包含的个数限定署名验证密钥KLV和其署名数据SKLV，使用用户署名验证密钥KUV来验证署名数据SKLV是否是个数限定署名验证密钥KLV的正确的署名(步骤S315)。

[0289] 在判断为署名数据SKLV是正确的署名的情况下(步骤S315中的“是”)，署名验证部203对于署名数据组SS中的消息数据m和其署名数据S，使用个数限定署名验证密钥KLV来验证署名数据S是否是消息数据m的正确的署名(步骤S320)。

[0290] 在判断为署名数据S是正确的署名的情况下(步骤S320中的“是”)，署名验证部203通过显示部205显示消息“OK”(步骤S325)。

[0291] 在判断为署名数据SKUV不正确的情况下(步骤S310中的“否”)、判断为署名数据SKLV不正确的情况下(步骤S315中的“否”)、以及判断为署名数据S不正确的情况下(步骤S320中的“否”)，署名验证部203通过显示部205显示消息“NG”(步骤S330)。 [0292] 1.6第一实施方式的整体动作

[0293] 下面，表示第一实施方式的数字署名系统1的整体动作。

[0294] 数字署名系统1的署名生成装置10在“署名生成及验证时”对于作为输入的消息数据m生成署名数据组SS，向署名验证装置20发送。署名验证装置20验证署名数据组SS，根据其验证结果，决定受理或者拒绝署名数据组。此外，在“初始设定时”，署名生成装置10将个数限定署名生成密钥及个数限定证书初始化，在“计数值检查时”检查计数值，根据其结果，更新个数限定署名生成密钥及个数限定证书。

[0295] 1.7第一实施方式的效果

[0296] 在第一实施方式的数字署名系统1中，由计数部107对用一个个数限定署名生成密钥生成的署名数据的个数进行计数，如果在计数判断部108中计数值c超过了阈值tc，则更新个数限定署名生成密钥。因此，能够将用一个个数限定署名生成密钥生成的署名数据的总数抑制在tc以内。由于tc是作为NTRUSign署名方式的攻击方法的抄本攻击不成功的署名个数，所以，对于数字署名系统1的抄本攻击不会成功，是安全的。

[0297] 个数限定署名验证密钥的证书是使用用户署名生成密钥生成的。通过这样，在更新了个数限定署名生成密钥及个数限定署名验证密钥的情况下，用户能够通过自己拥有的署名生成装置生成个数限定证书。在证书生成服务器CA生成个数限定署名验证密钥的证书的情况下，在署名生成装置中不需要用户证明生成密钥及用户证书，但用户需要将个数限定署名验证密钥的证书委托给证书生成服务器CA，每当更新个数限定署名生成密钥及个数限定署名验证密钥时，需要进行向证书生成服务器CA的通信。与此相比，如第一实施方式那样，通过使用用户署名生成密钥来生成个数限定署名验证密钥的证书，不需要向这些证书生成服务器CA的通信。

[0298] 2、第二实施方式

[0299] 以下，参照附图说明作为本发明涉及的第二实施方式的数字署名系统1000。 [0300] 2.1数字署名系统1000的概要

[0301] 数字署名系统1000如图6所示，包括署名生成装置1010、署名验证装置1020、署名监视服务器1030、中心1040和通信通道1050。

[0302] 署名生成装置1010生成对消息数据m的署名数据组SS，将生成的署名数据组SS经由通信通道1050向署名验证装置1020发送。

[0303] 署名验证装置1020经由通信通道1050从署名生成装置1010接收署名数据组SS，验证接收到的署名数据组SS。

[0304] 署名监视服务器1030监视在通信通道1050中流过的署名数据组SS，如果检测出不正确的署名数据组SS，则将该消息经由通信通道1050向中心1040发送。

[0305] 中心1040接收表示检测出不正确的署名数据组SS的消息。

[0306] 2.2署名生成装置1010的结构

[0307] 署名生成装置1010如图6所示，包括用户署名生成密钥保存部1101、用户证书保存部1102、个数限定署名生成密钥保存部1103、个数限定证书保存部1104、署名生成部1105、署名数据组生成部1106、计数部1107、计数判断部1108、个数限定密钥生成部1109、发送部1110和时钟部1111。

[0308] 署名生成装置1010保存着在NTRUSign署名方式中使用的秘密密钥即个数限定署名生成密钥、和与对应于上述秘密密钥的公开密钥相对应的公开密钥证书即个数限定证书，使用个数限定署名生成密钥，生成对作为输入的消息数据m的署名数据S。此外，署名生成装置1010对生成的署名数据的个数进行计数，在计数值超过了规定的阈值tc的情况下，生成新的个数限定署名生成密钥及个数限定证书。

[0309] 另外，阈值tc是NTRUSign署名方式的抄本攻击不成功的署名 的个数，例如是10^7个。此外，关于个数限定证书的详细情况在后面叙述。

[0310] 另外，构成署名生成装置1010的用户署名生成密钥保存部1101、用户证书保存部1102、个数限定署名生成密钥保存部1103、个数限定证书保存部1104、计数部1107、计数判断部1108、个数限定密钥生成部1109及发送部1110，分别进行与第一实施方式所示的用户署名生成密钥保存部101、用户证书保存部102、个数限定署名生成密钥保存部103、个数限定证书保存部104、计数部107、计数判断部108、个数限定密钥生成部109及发送部110同样的动作，所以省略这里的说明。

[0311] (1)时钟部1111

[0312] 时钟部1111具有对日期时刻进行计时并表示当前时刻的时刻信息TG。时钟部1111例如以秒单位进行计时，时刻信息是从1970年1月1日0时0分0秒到当前时刻的秒数。

[0313] (2)署名数据组生成部1106

[0314] 若署名数据组生成部1106通过用户的操作接受了消息数据m，则将指示生成由消息数据m、计数值c和时刻信息TG构成的署名对象数据D的署名数据的第1署名生成指示，向署名生成部1105输出。

[0315] 然后，若署名数据组生成部1106从署名生成部1105接受了第1结束通知，则分别从个数限定证书保存部1104读取个数限定证书CL、从用户证书保存部1102读取用户证书CU。署名数据组生成部1106生成由在署名生成部1105生成的署名对象数据D及署名对象数据D的署名数据S、和读取的个数限定证书CL及用户证书CU构成的署名数据组SS。 [0316] 署名数据组生成部1106经由发送部1110将生成的署名数据组SS向署名验证装置1020发送。

[0317] (3)署名生成部1105

[0318] 署名生成部1105进行署名对象数据D的署名数据S的生成、以及个数限定署名验证密钥KLV的署名数据SKLV的生成。

[0319] <生成署名数据S的情况>

[0320] 若署名生成部1105从署名数据组生成部1106接受到第1署名生成指示，则分别从计数部1107取得保持的计数值c、从时钟部1111取得表示当前时刻的时刻信息TG。 [0321] 署名数据组生成部1106生成由消息数据m、计数值c和时刻信息TG构成的署名对象数据D。

[0322] 署名数据组生成部1106读取保存于个数限定署名生成密钥保存部1103中的个数限定署名生成密钥KLG，使用读取的个数限定署名生成密钥KLG，生成对于生成的署名对象数据D的署名数据S，即对署名对象数据D实施署名而生成署名数据S。

[0323] 若署名数据S的生成结束，则署名生成部1105将表示该消息的第1结束通知向署名数据组生成部1106输出。

[0324] 另外，署名数据S是基于NTRUSign署名方式生成的。

[0325] <生成署名数据SKLV的情况>

[0326] 若署名生成部1105从个数限定密钥生成部1109接受了表示指示生成用户署名验证密钥KLV的署名数据SKLV的第2署名生成指示，则读取保存在用户署名生成密钥保存部1101中的用户署名生成密钥KUG，使用读取的用户署名生成密钥KUG，生成对在个数限定密钥生成部1109生成的个数限定署名验证密钥KLV的署名数据SKLV，即对个数限定署名验证密钥KLV实施署名而生成署名数据SKLV。

[0327] 如果署名数据SKLV的生成结束，则署名生成部1105将表示该消息的第2结束通知向个数限定密钥生成部1109输出。

[0328] 另外，署名数据SKLV是基于NTRUSign署名方式生成的。

[0329] 此外，在个数限定密钥生成部1109生成了个数限定署名验证密钥KLVN的情况下，也通过与上述同样的动作，生成署名数据 SKLVN。

[0330] 2.3署名验证装置1020的结构

[0331] 署名验证装置1020如图6所示，包括CA公开密钥保存部1201、署名数据组保存部1202、署名验证部1203、接收部1204、显示部1205、计数判断部1206、时刻判断部1207和时钟部1208。

[0332] 构成署名验证装置1020的CA公开密钥保存部1201、署名数据组保存部1202、接收部1204及显示部1205，分别进行与第一实施方式所示的CA公开密钥保存部201、署名数据组保存部202、接收部204及显示部205同样的动作，所以省略这里的说明。 [0333] (1)时钟部1208

[0334] 时钟部1208具有对日期时刻进行计时且表示当前时刻的时刻信息TG。时钟部1208例如以秒单位进行计时，时刻信息是从1970年1月1日0时0分0秒到当前时刻的秒数。

[0335] (2)计数判断部1206

[0336] 计数判断部1206预先保存有阈值tc。

[0337] 若计数判断部1206从署名验证部1203接受了表示进行计数值判断的计数判断指示，则取得包含在署名数据组SS中的计数值c，判断所取得的计数值c是否是阈值tc以上。

[0338] 在判断为是阈值tc以上的情况下，计数判断部1206将表示该消息的第1判断结果通知向署名验证部1203输出。

[0339] 在判断为不是阈值tc以上的情况下，计数判断部1206将表示该消息的第2判断结果通知向署名验证部1203输出。

[0340] (3)时刻判断部1207

[0341] 时刻判断部1207预先保存有差分阈值TT。

[0342] 若时刻判断部1207从署名验证部1203接受到表示进行时刻判断的时刻判断指示，则取得包含在署名数据组SS中的时刻信息TG、并从时钟部1208取得时刻信息TV，判断所取得的时刻信息TG及时 刻信息TV的差分TV-TG是否超过了差分阈值TT。

[0343] 在判断为差分TV-TG超过了差分阈值TT的情况下，时刻判断部1207将表示该消息的第3判断结果通知向署名验证部1203输出。

[0344] 在判断为差分TV-TG未超过阈值TT的情况下，时刻判断部1207将表示该消息的第4判断结果通知向署名验证部1203输出。

[0345] (4)署名验证部1203

[0346] 署名验证部1203验证包含在署名数据组SS中的署名数据S、包含在个数限定证书CL中的署名数据SKLV、包含在用户证书CU中的署名数据SKUV。

[0347] 以下，表示验证的动作。

[0348] 署名验证部1203从接收部1204接受表示开始验证的验证开始指示。 [0349] 署名验证部1203向计数判断部1206输出计数判断指示，然后从计数判断部1206接受判断结果。

[0350] 如果作为计数值c的判断结果而接受到第1判断结果，则署名验证部1203通过显示部1205显示表示拒绝接收到的署名数据组SS的消息“NG”。

[0351] 如果作为计数值c的判断结果而接受到第2判断结果，则署名验证部1203向时刻判断部1207输出时刻判断指示，然后从时刻判断部1207接受判断结果。

[0352] 如果作为时刻判断的结果而接受到第3判断结果，则署名验证部1203通过显示部1205显示拒绝接收到的署名数据组SS的消息“NG”。

[0353] 如果作为时刻判断的结果而接受到第4判断结果，则署名验证部1203使用保存在CA公开密钥保存部中的CA公开密钥KPC，验证署名数据SKUV是否是用户署名验证密钥KUV的正确的署名。

[0354] 在判断为署名数据SKUV是正确的署名的情况下，署名验证部 1203使用用户署名验证密钥KUV来验证署名数据SKLV是否是个数限定署名验证密钥KLV的正确的署名。 [0355] 在判断为署名数据SKLV是正确的署名的情况下，署名验证部1203使用个数限定署名验证密钥KLV来验证署名数据S是否是消息数据m的正确的署名。

[0356] 在判断为署名数据S是正确的署名的情况下，署名验证部1203通过显示部1205显示表示受理接收到的署名数据组SS的消息“OK”。

[0357] 在各署名验证中的任一个署名验证中，判断为署名数据是不正确的署名的情况下，署名验证部1203通过显示部1205显示表示拒绝接收到的署名数据组SS的消息“NG”。 [0358] 2.4署名监视服务器1030的结构

[0359] 署名监视服务器1030如图6所示，具备日志保存部1301、通信监视部1302、署名数据组取得部1303、署名数据组判断部1304、和收发部1305。

[0360] (1)日志保存部1301

[0361] 日志保存部1301具有用来保存1个以上署名数据组的区域。

[0362] (2)通信监视部1302

[0363] 通信监视部1302通过收发部1305监视在通信通道1050中流过的署名数据组SS。 [0364] (3)署名数据组取得部1303

[0365] 若署名数据组取得部1303通过通信监视部1302检测出署名数据组SS在通信通道1050中流过，则经由收发部1305及通信监视部1302取得在通信通道1050中流过的署名数据组。

[0366] 署名数据组取得部1303判断在日志保存部1301中是否已经保存有署名数据组。 [0367] 在判断为没有保存的情况下，署名数据组取得部1303将取得的署名数据组SS保存到日志保存部1301中。

[0368] 在判断为已保存的情况下，署名数据组取得部1303将表示判断包含在所取得的署名数据组中的计数值c的正当性的判断指示，向署名数据组判断部1304输出。署名数据组取得部1303从署名数据组判断部1304接受判断结果。

[0369] 如果作为判断结果接受了表示计数值是正当值的正当通知，则署名数据组取得部1303将取得的署名数据组SS保存到日志保存部1301中。

[0370] 如果作为判断结果接受了表示计数值是不正当值的不正当通知，则署名数据组取得部1303将包含在所取得的署名数据组SS中的用户证书、和表示检测出不正当的署名数据组的检测消息，经由收发部1305向中心发送。

[0371] (4)署名数据组判断部1304

[0372] 如果署名数据组判断部1304从署名数据组取得部1303接受了判断指示，则判断在日志保存部1301中是否存在包含与所取得的署名数据组SS中的个数限定署名验证密钥和计数值分别相同的值的署名数据组SSF。

[0373] 在判断为存在的情况下，署名数据组判断部1304将不正当通知向署名数据组取得部1303输出。

[0374] 在判断为不存在的情况下，署名数据组判断部1304将正当通知向署名数据组取得部1303输出。

[0375] (5)收发部1305

[0376] 收发部1305接收在通信通道1050中流过的署名数据组，将接收到的署名数据组经由通信监视部1302向署名数据组取得部1303输出。

[0377] 若收发部1305从署名数据组取得部1303接受了用户证书，则将接受到的用户证书经由通信通道1050向中心发送。

[0378] 2.5中心1040

[0379] 中心1040经由通信通道1050从署名监视服务器1030接收检测消息和用户证书。 [0380] 2.6署名生成装置1010的动作

[0381] 署名生成装置1010的动作包括：对个数限定署名生成密钥及个数限定证书进行初始设定的“初始设定处理”、进行署名生成的“署名生成处理”、和检查计数值并生成个数限定署名生成密钥及个数限定证书的“计数值检查处理”的动作。“初始设定处理”和“计数值检查处理”的动作与第一实施方式所示的同作相同，所以省略说明。

[0382] (1)署名生成处理

[0383] 利用图7所示的流程图，对署名生成处理的动作进行说明。

[0384] 署名数据组生成部1106通过用户的操作接受消息数据m(步骤S1000)。 [0385] 署名数据组生成部1106将指示生成署名对象数据D的署名数据的第1署名生成指示，向署名生成部1105输出。若署名生成部1105从署名数据组生成部1106接受到第1署名生成指示，则分别从计数部1107取得所保持的计数值c、从时钟部1111取得表示当前时刻的时刻TG。署名数据组生成部1106生成由消息数据m、计数值c、和时刻信息TG构成的署名对象数据D(步骤S1005)。

[0386] 署名生成部1105读取保存在个数限定署名生成密钥保存部1103中的个数限定署名生成密钥KLG，使用读取的个数限定署名生成密钥KLG，生成对于生成的署名对象数据D的署名数据S(步骤S1010)。计数部1107对计数值c加1，将相加的结果作为新的计数值c(步骤S1015)。

[0387] 如果署名数据S的生成结束，署名生成部1105将表示该消息的第1结束通知向署名数据组生成部1106输出。若署名数据组生成部1106从署名生成部1105接受到第1结束通知，则分别从个数限定证书保存部1104读取个数限定证书CL、从用户证书保存部1102读取 用户证书CU。署名数据组生成部1106生成由在署名生成部1105生成的署名对象数据D及署名对象数据D的署名数据S、和读取的个数限定证书CL及用户证书CU构成的署名数据组SS(步骤S1020)。

[0388] 发送部1110经由通信通道1050将在署名数据组生成部1106生成的署名数据组SS向署名验证装置1020发送(步骤S1025)。

[0389] 2.7署名验证装置1020的动作

[0390] 署名验证装置1020经由通信通道1050从署名生成装置1010接收署名数据组SS，并验证该署名数据组SS。以下，利用图8所示的流程图说明由署名验证装置1020进行的署名验证处理。

[0391] 接收部1204经由通信通道1050接收从署名生成装置1010发送的署名数据组SS(步骤S1100)。

[0392] 接收部1204将接收到的署名数据组SS保存到署名数据组保存部1202中(步骤S1105)。

[0393] 接收部1204向署名验证部1203输出验证开始指示。若署名验证部1203从接收部1204接受了验证开始指示，则向计数判断部1206输出计数判断指示。若计数判断部1206接受了计数判断指示，则取得包含在署名数据组SS中的计数值c，判断所取得的计数值c是否是阈值tc以上(步骤S1110)。

[0394] 在判断为是阈值tc以上的情况下(步骤S1110中的“是”)，计数判断部1206将表示该消息的第1判断结果通知向署名验证部1203输出。如果作为计数值c的判断结果接受了第1判断结果，则署名验证部1203通过显示部1205显示消息“NG”(步骤S1140)。 [0395] 在判断为不是阈值tc以上的情况下(步骤S1110中的“否”)，计数判断部1206将表示该消息的第2判断结果通知向署名验证部1203输出。如果作为计数值c的判断结果而接受了第2判断结果，则署名验证部1203向时刻判断部1207输出时刻判断指示。若时刻判断部1207从署名验证部1203接受了时刻判断指示，则取得包含在署名数 据组SS中的时刻信息TG，并从时钟部1208取得时刻信息TV，判断所取得的时刻信息TG和时刻信息TV的差分TV-TG是否超过了差分阈值TT(步骤S1115)。

[0396] 在判断为差分TV-TG超过了差分阈值TT的情况下(步骤S1115中的“是”)，时刻判断部1207向署名验证部1203输出表示该消息的第3判断结果通知。如果作为时刻判断的结果而接受了第3判断结果，则署名验证部1203通过显示部1205显示消息“NG”(步骤S1140)。

[0397] 在判断为差分TV-TG没有超过差分阈值TT的情况下(步骤S1115中的“否”)，时刻判断部1207向署名验证部1203输出表示该消息的第4判断结果通知。如果作为时刻判断的结果而接受了第4判断结果，则署名验证部1203使用保存在CA公开密钥保存部中的CA公开密钥KPC，验证署名数据SKUV是否是用户署名验证密钥KUV的正确的署名(步骤S1120)。

[0398] 在判断为署名数据SKUV是正确的署名的情况下(步骤S1120中的“是”)，署名验证部1203对于在署名数据组SS中的个数限定证书CL中包含的个数限定署名验证密钥KLV和其署名数据SKLV，使用用户署名验证密钥KUV来验证署名数据SKLV是否是个数限定署名验证密钥KLV的正确的署名(步骤S1125)。

[0399] 在判断为署名数据SKLV是正确的署名的情况下(步骤S1125中的“是”)，署名验证部1203对于署名数据组SS中的消息数据m和其署名数据S，使用个数限定署名验证密钥KLV来验证署名数据S是否是消息数据m的正确的署名(步骤S1130)。

[0400] 在判断为署名数据S是正确的署名的情况下(步骤S1130中的“是”)，署名验证部1203通过显示部1205显示消息“OK”(步骤S1135)。

[0401] 在判断为署名数据SKUV不正确的情况下(步骤S1120中的“否”)、判断为署名数据SKLV不正确的情况下(步骤S1125中的 “否”)、以及判断为署名数据S不正确的情况下(步骤S1130中的“否”)，署名验证部1203通过显示部1205显示消息“NG”(步骤S1140)。 [0402] 2.8署名监视服务器1030的动作

[0403] 署名监视服务器1030监视署名数据组是否在通信通道1050中流过，在流过的情况下得到该署名数据组SS，与已经保存的署名数据组比较。以下，利用图9所示的流程图说明由署名监视服务器1030进行的监视处理，

[0404] 通信监视部1302经由收发部1305监视署名数据组SS是否在通信通道1050中流过(步骤S1200)。

[0405] 在通信监视部1302没有检测出在通信通道1050中流过署名数据组SS的情况下(步骤S1200中的“否”)，结束监视处理。

[0406] 如果在通信监视部1302检测出在通信通道1050中流过署名数据组SS(步骤S1200中的“是”)，署名数据组取得部1303经由收发部1305及通信监视部1302，取得在通信通道1050中流过的署名数据组(步骤S1205)。

[0407] 署名数据组取得部1303判断在日志保存部1301中是否已经保存有署名数据组(步骤S1210)。

[0408] 在判断为没有保存的情况下(步骤S1210中的“否”)，署名数据组取得部1303将所取得的署名数据组SS保存到日志保存部1301中(步骤S1215)。

[0409] 在判断为已保存的情况下(步骤S1210中的“是”)，署名数据组取得部1303向署名数据组判断部1304输出表示判断包含在所取得的署名数据组中的计数值c的正当性的判断指示。若署名数据组判断部1304从署名数据组取得部1303接受了判断指示，则判断在日志保存部1301中是否存在包括有与包含在所取得的署名数据组SS中的个数限定署名验证密钥和计数值分别相同的值的署名数据组SSF(步骤 S1220)。

[0410] 在判断为存在的情况下(步骤S1220中的“是”)，署名数据组判断部1304向署名数据组取得部1303输出不正当通知。若署名数据组取得部1303从署名数据组判断部1304作为判断结果而接受到不正当通知，则将包含在所取得的署名数据组SS中的用户证书向收发部1305输出。收发部1305经由通信通道1050将用户证书向中心发送(步骤S1225)。 [0411] 在判断为不存在的情况下(步骤S1220中的“否”)，署名数据组判断部1304向署名数据组取得部1303输出正当通知。若署名数据组取得部1303从署名数据组判断部1304作为判断结果而接受了正当通知，则将所取得的署名数据组SS保存到日志保存部1301中(步骤S1215)。

[0412] 2.9第二实施方式的整体动作

[0413] 下面，示出第二实施方式的数字署名系统1000的整体动作。

[0414] 数字署名系统1000的署名生成装置1010在“署名生成、验证时”对于作为输入的消息数据m生成署名数据组SS，向署名验证装置1020发送。署名验证装置1020验证署名数据组SS，根据其验证结果，决定受理或者拒绝署名数据组SS。此外，在“初始设定时”，署名生成装置1010将个数限定署名生成密钥及个数限定证书初始化，在“计数值检查时”检查计数值，根据其结果更新个数限定署名生成密钥及个数限定证书。再者，署名监视服务器1030监视在通信通道1050中是否流过署名数据组SS，在流过署名数据组SS的情况下，与以前的署名数据组比较。

[0415] 2.10第二实施方式的效果

[0416] 第二实施方式的数字署名系统1000与第一实施方式同样，能够将用一个个数限定署名生成密钥生成的署名数据的总数抑制在tc以内。

[0417] 进而，在第二实施方式中，使计数值包含在署名对象数据中，用署名验证装置1020进行验证。因此，能够用署名验证装置1020确认署名生成装置1010超过计数值而生成了署名数据的情况。

[0418] 此外，由于通过署名监视服务器1030检查是否在以前存在包含有相同的计数值和相同的个数限定署名验证密钥的署名数据组，所以能够防止通过署名生成装置1010故意或者错误地使用相同的计数值以及相同的个数限定署名生成密钥两次生成署名数据而不能成功计数署名次数的情况。

[0419] 进而，通过在署名生成装置1010及署名验证装置1020中具有时钟、在署名对象数据中包含表示使用了计数值的时刻的时刻信息，能够防止因重复使用相同的计数值、利用相同的计数值及相同的个数限定署名生成密钥两次生成署名数据造成的不能成功计数署名次数的情况。

[0420] 因而，在数字署名系统1000中，作为NTRUSign署名方式的攻击法的抄本攻击不会成功，是安全的。

[0421] 3、变形例

[0422] 上述说明的第一实施方式及第二实施方式是本发明的实施一例，本发明并不受这些实施方式的任何限定，在不脱离其主旨的范围内能够以各种的形态实施。例如，以下这样的情况也包含在本发明中。

[0423] (1)在第二实施方式的署名验证装置中，在计数值为阈值tc以上的情况下显示(输出)NG，但并不限于此。署名验证装置也可以在计数值为阈值tc以上的情况下，对中心发送并通知用户证书。此外，也可以代替用户证书，而是将表示署名生成装置的用户的识别符发送给中心。

[0424] (2)在第二实施方式中，在署名生成装置中，将表示进行了署名生成的当前时刻的时刻信息TG包含在署名对象数据中，但也可以将表示在当前时刻上加上阈值TT后的署名验证期限的时刻信息TGT 包含在署名对象数据中。

[0425] 此时，署名验证装置将图8所示的步骤S1115变更为，判断从该装置的时钟部取得的时刻信息TV是否超过时刻信息TGT。在判断为超过的情况下，署名装置进行步骤1140，在判断为不超过的情况下，署名验证装置进行步骤S1120。

[0426] (3)在第一实施方式及第二实施方式中，在署名数据组中包含有用户证书，但也可以不包含用户证书，而署名验证装置预先保持有用户证书。

[0427] (4)在第一实施方式及第二实施方式中，如果计数值c超过tc，则署名生成装置更新个数限定署名生成密钥，即用新生成的个数限定署名生成密钥覆盖存储的个数限定署名生成密钥，但并不限于此。也可以是，如果计数值c超过tc则署名生成装置在其以后不生成署名数据、即不使用该署名生成装置。此时，用户证书及用户署名生成密钥没有也可以，在此情况下，个数限定证书也可以包含通过证书生成服务器CA的署名生成密钥生成的个数限定署名验证密钥的署名数据。

[0428] (5)在第一实施方式及第二实施方式中，如果计数值c超过tc，则署名生成装置的计数判断部更新个数限定署名生成密钥，用新生成的个数限定署名生成密钥覆盖存储的个数限定署名生成密钥，但并不限于此。署名生成装置也可以存储多个个数限定署名生成密钥，具备保存作为表示使用的个数限定署名生成密钥的信息的使用个数限定署名生成密钥信息的使用个数限定署名生成密钥信息保存部、和更新使用个数限定署名生成密钥信息的使用个数限定署名生成密钥信息更新部，如果计数值c超过tc，则署名生成装置更新使用个数限定署名生成密钥信息。

[0429] 另外，对应于各个数限定署名生成密钥的个数限定署名验证密钥相互不同，分别对应于各个数限定署名验证密钥的个数限定证书与对 应于包含在个数限定证书中的个数限定署名验证密钥的个数限定署名生成密钥建立了对应，被保存在个数限定证书保存部中。

[0430] 此时，署名生成装置使用由保存在使用个数限定署名生成密钥信息保存部中的使用个数限定署名生成密钥信息表示的个数限定署名生成密钥来生成署名数据，生成由所生成的署名数据、与在生成中使用的个数限定署名生成密钥对应的个数限定证书、和用户证书构成的署名数据组。署名生成装置向署名验证装置发送生成的署名数据组。 [0431] 或者，对应于各个数限定署名生成密钥的个数限定署名验证密钥也可以是1个。即，个数限定署名生成密钥也可以是对应于所有的个数限定署名生成密钥的密钥。 [0432] (6)在第一实施方式及第二实施方式中，作为署名方式而使用NTRUSign署名方式，但也可以使其为其他署名方式，例如RSA署名方式、RSA-PSS署名方式、及椭圆DSA署名方式。

[0433] (7)在第一实施方式中，如果生成了署名数据S，则署名生成装置的计数判断部进行计数值的检查，但并不限于此。

[0434] 署名生成装置的计数判断部也可以定期地进行计数值的检查。或者，也可以通过接受用户的指示，计数判断部108进行计数值的检查。

[0435] (8)在第二实施方式中，中心仅接收不正当消息与用户证书，但并不限于此。 [0436] 中心保存接收到的用户证书，生成由包含在被保存的1个以上用户证书中的用户署名验证密钥构成的无效化列表。中心将生成的无效化列表向署名验证装置发送。 [0437] 此时，若署名验证装置从中心接收到无效化列表，则保存接收到的无效化列表。若署名验证装置从署名生成装置接收了署名数据组，则取得包含在接收到的署名数据组中的用户证书，判断包含在所取得的用户证书中的用户署名验证密钥是否存在于所保存的无效化列表中。在判断为存在的情况下，署名验证装置显示消息“NG”。在判断 为不存在的情况下，进行图8所示的1105以后的动作。

[0438] (9)在第一实施方式中，署名生成装置的计数判断部预先保存的阈值为固定的，但并不限于此。阈值也可以是可变的。

[0439] 例如，如果署名生成装置进一步通过用户的操作接受阈值tc’，则可以通过将保存在该装置的计数判断部中的阈值tc覆盖并更新为接受的阈值tc’，来使阈值可变。 [0440] 或者，署名生成装置也可以通过定期地变更阈值，使阈值为可变。 [0441] (10)在第二实施方式中，署名生成装置的计数判断部预先保存的阈值为固定的，但并不限于此。阈值也可以是可变的。

[0442] 以下表示此时的动作的一例。若署名生成装置进一步通过用户的操作接受阈值tc’，则将保存在该署名生成装置的计数判断部中的阈值tc覆盖并更新为接受的阈值tc’。署名生成装置将接受的阈值tc’向署名验证装置发送。若署名验证装置从署名生成装置接收到阈值tc’，则将保存在该署名验证装置的计数判断部中的阈值覆盖并更新为接收到的阈值tc’。

[0443] 或者，也可以是以下这样的动作。署名生成装置定期地变更阈值，将变更后的阈值向署名验证装置发送。若署名验证装置接收到变更后的阈值，则将保存在该署名验证装置的计数判断部中的阈值覆盖并更新为接收到的阈值tc’。

[0444] (11)在上述第一实施方式中，署名生成装置在计数值中作为初始值而设定了0，但并不限于此。署名生成装置也可以设定1作为计数值的初始值。此时，署名生成装置判断计数值c是否超过了阈值tc，在判断为超过的情况下，更新个数限定署名生成密钥及个数限定证书。

[0445] 此外，在第二实施方式中也同样，署名生成装置也可以设定1作为计数值的初始值。此时，署名生成装置判断计数值c是否超过了阈值tc，在判断为超过的情况下，更新个数限定署名生成密钥及个数限 定证书。署名验证装置判断接收到的计数值c是否超过了阈值tc，在判断为超过的情况下，显示(输出)NG，在判断为不超过的情况下，进行利用时刻信息的判断。

[0446] (12)在第二实施方式中，署名生成装置在生成了署名数据后对计数值的值加1，但并不限于此。

[0447] 署名生成装置也可以在生成署名对象数据D之前对计数值的值加1。即，署名生成装置也可以在图7所示的署名生成处理中，在执行了步骤S1000后执行步骤S1015，然后按照步骤S1005、S1010、S1020及S1025的顺序执行。

[0448] 此外，此时，署名生成装置也可以在生成署名数据之前进行计数值的检查处理。在此情况下，在判断计数值为规定值以上的情况下，署名生成装置生成新的个数限定署名生成密钥及新的个数限定证书，利用生成的新的个数限定署名生成密钥来生成署名对象数据的署名数据。并且，署名生成装置生成由署名对象数据、生成的署名数据、生成的新的个数限定证书、和用户证书构成的署名数据组。

[0449] (13)在第一实施方式中，署名生成装置也可以在生成署名数据S之前对计数值的值加1。

[0450] 此外，此时，署名生成装置也可以在生成署名数据之前进行计数值的检查处理。在此情况下，在判断计数值为规定值以上的情况下，署名生成装置生成新的个数限定署名生成密钥及新的个数限定证书，利用生成的新的个数限定署名生成密钥来生成消息数据的署名数据。并且，署名生成装置生成由消息数据、生成的署名数据、生成的新的个数限定证书、和用户证书构成的署名数据组。

[0451] (14)在第二实施方式中，署名生成装置生成对于由消息数据m、计数值c和时刻信息TG构成的署名对象数据D的署名数据S，但并不限于此。

[0452] 署名生成装置也可以生成对消息数据m的署名数据S。此时，署 名生成装置向署名验证装置发送由消息数据m、计数值c和时刻信息TG构成的数据D，署名数据S，个数限定证书CL以及用户证书CU。

[0453] (15)在第二实施方式中，署名生成装置向署名验证装置发送由消息数据m、计数值c和时刻信息TG构成的署名对象数据D，对署名对象数据D的署名数据S，个数限定证书CL以及用户证书CU，但并不限于此。

[0454] 署名生成装置也可以向署名验证装置发送由消息数据m和计数值c构成的署名对象数据D，对署名对象数据D的署名数据S，个数限定证书CL以及用户证书CU。此时，在由署名验证装置进行的署名验证处理中，省略图8所示的步骤S1115。

[0455] 或者，署名生成装置也可以向署名验证装置发送由消息数据m和时刻信息TG构成的署名对象数据D，对署名对象数据D的署名数据S，个数限定证书CL以及用户证书CU。此时，在由署名验证装置进行的署名验证处理中，省略图8所示的步骤S1110。 [0456] (16)在第一实施方式中，署名生成装置通过用户的操作接受消息，但并不限于此。 [0457] 署名生成装置也可以从外部的装置接受消息数据。

[0458] 此外，在第二实施方式中也同样，署名生成装置也可以从外部的装置接受消息数据。

[0459] (17)在第一实施方式中，署名生成装置的计数部对保持着的计数值加1，但并不限于此。署名生成装置的计数部既可以加上其他的数值，也可以进行乘法。在进行乘法的情况下，计数值的初始值例如设为1。

[0460] 此外，在第二实施方式中也同样，署名生成装置的计数部既可以加上其他的数值，也可以进行乘法。在进行乘法的情况下，计数值的初始值例如设为1。

[0461] (18)也可以是这些实施方式及变形例的组合。

[0462] <其他的变形例>

[0463] 另外，基于上述的实施方式说明了本发明，但本发明当然并不限于上述的实施方式。以下这样的情况也包含在本发明中。

[0464] (1)上述的各装置具体而言是由微处理器、ROM、RAM、硬盘单元、显示器单元、密钥盘、鼠标等构成的计算机系统。在上述RAM或上述硬盘单元中存储有计算机程序。通过上述微处理器按照上述计算机程序动作，各装置实现其功能。这里，计算机程序是为了实现规定的功能而将表示对计算机的指令的命令代码组合多个而构成的。

[0465] (2)构成上述各装置的结构要素的一部分或全部也可以由1个系统LSI(Large Scale Integration：大规模集成电路)构成。系统LSI是将多个结构部集成在1个芯片上而制造的超多功能LSI，具体而言是包括微处理器、ROM、RAM等而构成的计算机系统。在上述RAM中存储有计算机程序。通过上述微处理器按照上述计算机程序动作，系统LSI实现其功能。

[0466] (3)构成上述各装置的结构要素的一部分或全部也可以由对各装置可拆装的IC卡或单体的模组构成。上述IC卡或上述模组是由微处理器、ROM、RAM等构成的计算机系统。上述IC卡或上述模组也可以包括上述超多功能LSI。通过微处理器按照计算机程序动作，上述IC卡或上述模组实现其功能。该IC卡或该模组也可以具有耐篡改性。

[0467] (4)本发明也可以是上述所示的方法。此外，也可以是通过计算机实现这些方法的计算机程序，也可以是由上述计算机程序构成的数字信号。

[0468] 此外，本发明也可以是将上述计算机程序或上述数字信号记录在计算机可读取的记录媒体、例如软盘、硬盘、CD-ROM、MO、DVD、DVD-ROM、DVD-RAM、BD(Blu-ray Disc)、半导体存储器等中而成的产品。此外，也可以是记录在这些记录媒体中的上述计算机程 序或上述数字信号。

[0469] 此外，本发明也可以是将上述计算机程序或上述数字信号经由电气通信线路、无线或有线通信线路、以因特网为代表的网络、数据广播等传送。

[0470] 此外，本发明也可以是具备微处理器和存储器的计算机系统、上述存储器存储有上述计算机程序、上述微处理器按照上述计算机程序动作。

[0471] 此外，也可以通过将上述程序或上述数字信号记录到上述记录媒体中移送、或者将上述程序或上述数字信号经由上述网络等移送，由独立的其他计算机系统实施。 [0472] (5)也可以将上述实施方式及上述变形例分别组合。

[0473] 4、总结

[0474] 本发明是生成对包括消息数据的署名对象数据的署名数据的署名生成装置，其特征在于，具备：个数限定署名生成密钥保存部，保存为了生成上述署名数据而使用的个数限定署名生成密钥；署名生成部，使用保存在上述个数限定署名生成密钥保存部中的上述个数限定署名生成密钥，生成对上述署名对象数据的上述署名数据；计数部，对在上述署名生成部中使用上述个数限定署名生成密钥而生成了上述署名数据的次数进行计数；第1计数判断部，判断上述计数部的计数值；上述第1计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制使得在上述署名生成部中不生成上述署名数据。

[0475] 这里，也可以是，上述署名生成装置还具备生成上述个数限定署名生成密钥的密钥生成部；上述第1计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制，以便利用上述密钥生成部来生成上述个数限定署名生成密钥，并保存到上述个数限定署名生成密钥保存部中。

[0476] 这里，也可以是，上述第1计数判断部在上述计数值比预先给出 的规定值大的情况下，进行控制，以便利用上述密钥生成部来生成上述个数限定署名生成密钥，覆盖并更新在保存于上述个数限定署名生成密钥保存部中的以前的上述个数限定署名生成密钥。 [0477] 这里，也可以是，存在多个上述个数限定署名生成密钥；上述署名生成装置还具备：使用个数限定署名生成密钥信息保存部，保存表示多个上述个数限定署名生成密钥中作为使用的上述个数限定署名生成密钥的使用个数限定署名生成密钥的信息、即使用个数限定署名生成密钥信息；使用个数限定署名生成密钥信息更新部，更新上述使用个数限定署名生成密钥保存部的上述使用个数限定署名生成密钥信息；上述第1计数判断部在上述计数值比预先给出的规定值大的情况下，利用上述密钥生成部，在上述使用个数限定署名生成密钥信息更新部中更新上述个数限定署名生成密钥信息。

[0478] 这里，也可以是，上述署名生成装置还具备：个数限定证书保存部，保存对应于上述个数限定署名生成密钥的、为了验证上述署名数据而使用的个数限定署名验证密钥的证书；用户署名生成密钥保存部，保存为了生成上述个数限定证书而使用的用户署名生成密钥；上述密钥生成部生成上述个数限定署名生成密钥和对应于上述个数限定署名生成密钥的上述个数限定证书，分别保存到上述个数限定署名生成密钥保存部与上述个数限定证书保存部中。

[0479] 这里，也可以是，上述第1计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制，以利用上述密钥生成部生成上述个数限定署名生成密钥和对应于上述个数限定署名生成密钥的上述个数限定证书，分别覆盖更新在保存于上述个数限定署名生成密钥保存部中的以前的上述个数限定署名生成密钥、和保存于上述个数限定证书保存部中的以前的上述个数限定署名生成密钥上。

[0480] 这里，也可以是，上述署名生成装置利用保存在上述署名生成密钥保存部中的上述署名生成密钥，生成包括上述消息数据和上述计数 部表示的计数值的上述署名对象数据的上述署名数据。

[0481] 这里，也可以是，上述署名生成装置还具备保持时刻信息的第1时钟，上述署名对象数据还包括上述第1时钟保持的上述时刻信息。

[0482] 此外，本发明是验证对包括消息数据和计数值的署名对象数据的署名数据的署名验证装置，其特征在于，具备：个数限定证书保存部，保存为了验证上述署名数据而使用的个数限定署名验证密钥、或者上述个数限定署名验证密钥的证书；署名验证部，利用保存在上述个数限定署名验证密钥保存部中的上述个数限定署名验证密钥，验证对上述署名对象数据的上述署名数据；第2计数判断部，判断包含在上述署名对象数据中的上述计数值；上述第2计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名验证部中不进行署名验证。

[0483] 这里，也可以是，上述署名验证装置还具备对中心通知信息的通知部；上述第2计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制，以在上述通知部中将上述署名验证密钥或上述署名验证密钥的识别码向中心通知。

[0484] 这里，也可以是，上述署名验证装置还具备保持第2时刻信息的第2时钟、和判断时刻信息的时刻判断部；上述署名对象数据还包括第1时刻信息；上述时刻判断部比较第1时刻信息与第2时刻信息，在从第2时刻信息减去第1时刻信息后的时刻差量比预先给出的规定值大的情况下，进行控制以使得在上述署名验证部中不进行署名验证。 [0485] 这里，也可以是，上述署名验证装置还具备保持第2时刻信息的第2时钟、和判断时刻信息的时刻判断部；上述署名对象数据还包括第1时刻信息；上述时刻判断部比较第1时刻信息与第2时刻信息，在从第2时刻信息减去第1时刻信息后的时刻差量比预先给出的规定值大的情况下，进行控制以将上述署名验证密钥、或者上述署名验证 密钥的识别码向中心通知。

[0486] 此外，本发明是由生成对包括消息数据和计数值的署名对象数据的署名数据的署名生成装置和验证上述署名数据的署名验证装置构成的数字署名系统，其特征在于，上述署名生成装置具备：个数限定署名生成密钥保存部，保存为了生成上述署名数据而使用的个数限定署名生成密钥；署名生成部，利用保存在上述个数限定署名生成密钥保存部中的上述个数限定署名生成密钥，生成对上述署名对象数据的上述署名数据；计数部，计数在上述署名生成部中利用上述个数限定署名生成密钥生成上述署名数据的次数；第1计数判断部，判断上述计数部的计数值；上述署名验证装置具备：个数限定证书保存部，保存为了验证上述署名数据而使用的个数限定署名验证密钥、或者上述个数限定署名验证密钥的证书；署名验证部，利用保存在上述个数限定署名验证密钥保存部中的上述个数限定署名验证密钥，验证对上述署名对象数据的上述署名数据；第2计数判断部，判断包含在上述署名对象数据中的上述计数值；上述第1计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名生成部中不生成上述署名数据；上述第2计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名验证部中不进行署名验证。

[0487] 这里，也可以是，上述数字署名系统还具备监视由上述署名对象数据和上述署名数据构成的署名数据组的署名监视服务器、和从上述署名监视服务器接受监视结果信息的通知的中心；上述署名监视服务器具备：署名数据组取得部，取得上述署名数据组；署名数据组日志保存部，保存由以前的上述署名数据组构成的署名数据组日志；署名数据组判断部，判断上述署名数据组；上述署名数据组判断部通过比较由上述署名数据组取得部取得的上述署名数据、和上述署名数据组日志进行判断，根据其判断结果生成上述监视结果信息，向上述中心 通知。

[0488] 这里，也可以是，上述署名数据组判断部将包含在上述署名数据组中的上述署名对象数据中的计数值、和包含在保存于上述署名数据组日志保存部中的以前的上述署名数据组中的上述署名对象数据中的计数值比较。

[0489] 此外，本发明是生成对包括消息数据的署名对象数据的署名数据的署名生成方法，其特征在于，具备：个数限定署名生成密钥保存步骤，保存为了生成上述署名数据而使用的个数限定署名生成密钥；署名生成步骤，利用在上述个数限定署名生成密钥保存步骤中保存的上述个数限定署名生成密钥，生成对上述署名对象数据的上述署名数据；计数步骤，计数在上述署名生成步骤中利用上述个数限定署名生成密钥生成上述署名数据的次数；第1计数器判断步骤，判断在上述计数步骤中计数的计数值；上述第1计数器判断步骤在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名生成步骤中不生成上述署名数据。

[0490] 此外，本发明是验证对包括消息数据和计数值的署名对象数据的署名数据的署名验证方法，其特征在于，具备：个数限定证书保存步骤，保存为了验证上述署名数据而使用的个数限定署名验证密钥、或者上述个数限定署名验证密钥的证书；署名验证步骤，利用在上述个数限定署名验证密钥保存步骤中保存的上述个数限定署名验证密钥，验证对上述署名对象数据的上述署名数据；第2计数器判断步骤，判断包含在上述署名对象数据中的上述计数值；上述第2计数器判断步骤在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名验证步骤中不进行署名验证。

[0491] 此外，本发明是使生成对包括消息数据的署名对象数据的署名数据的署名生成装置执行的程序，其特征在于，具备：个数限定署名生成密钥保存步骤，保存为了生成上述署名数据而使用的个数限定署名 生成密钥；署名生成步骤，利用在上述个数限定署名生成密钥保存步骤中保存的上述个数限定署名生成密钥，生成对上述署名对象数据的上述署名数据；计数步骤，计数在上述署名生成步骤中利用上述个数限定署名生成密钥生成上述署名数据的次数；第1计数器判断步骤，判断在上述计数步骤中计数的计数值；上述第1计数器判断步骤在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名生成步骤中不生成上述署名数据。

[0492] 此外，本发明是使验证对包括消息数据和计数值的署名对象数据的署名数据的署名验证装置执行的程序，其特征在于，具备：个数限定证书保存步骤，保存为了验证上述署名数据而使用的个数限定署名验证密钥、或者上述个数限定署名验证密钥的证书；署名验证步骤，利用在上述个数限定署名验证密钥保存步骤中保存的上述个数限定署名验证密钥，验证对上述署名对象数据的上述署名数据；第2计数器判断步骤，判断包含在上述署名对象数据中的上述计数值；上述第2计数器判断步骤在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名验证步骤中不进行署名验证。

[0493] 此外，本发明是生成对包括消息数据的署名对象数据的署名数据的署名生成装置的集成电路，其特征在于，具备：个数限定署名生成密钥保存部，保存为了生成上述署名数据而使用的个数限定署名生成密钥；署名生成部，利用保存在上述个数限定署名生成密钥保存部中的上述个数限定署名生成密钥，生成对上述署名对象数据的上述署名数据；计数部，计数在上述署名生成部中利用上述个数限定署名生成密钥生成上述署名数据的次数；第1计数判断部，判断上述计数部的计数值；上述第1计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名生成部中不生成上述署名数据。 [0494] 此外，本发明是验证对包括消息数据和计数值的署名对象数据的署名数据的署名验证装置的集成电路，其特征在于，具备：个数限定 证书保存部，保存为了验证上述署名数据而使用的个数限定署名验证密钥、或者上述个数限定署名验证密钥的证书；署名验证部，利用保存在上述个数限定署名验证密钥保存部中的上述个数限定署名验证密钥，验证对上述署名对象数据的上述署名数据；第2计数判断部，判断包含在上述署名对象数据中的上述计数值；上述第2计数判断部在上述计数值比预先给出的规定值大的情况下，进行控制以使得在上述署名验证部中不进行署名验证。

[0495] 根据上述所示的数字署名系统的结构，能够防止抄本攻击。

[0496] 此外，构成上述所示的数字署名系统的各装置，能够在电器设备制造产业中经营性地、并且持续地及反复地制造、销售。