签名与检验方法以及签名与检验装置的制作方法
专利名称：签名与检验方法以及签名与检验装置的制作方法
技术领域：
本发明涉及一种签名与检验方法以及签名与检验装置，特别是一种在多个签名装置进行签名的状况下的、签名长度不依赖于签名装置数目的、签名与检验方法以及签名与检验装置。
背景技术：
伴随着计算机与互联网环境的普及，电子发送接收消息的机会也在增加。这种情况下，为了防止在发送消息的过程中消息被篡改，希望在消息中添加电子签名。
但是在使用称作RSA或DSA的公知的签名方式，由多个签名装置进行了签名的情况下，为了表示全体都已进行了签名，需要由全签名装置分别生成签名句，并将这些签名句都保存起来。因此，签名句的数据长度的合计值与签名装置的台数成比例，在签名装置数目较多的情况下，效率不高。
作为解决这样的问题的签名方式之一，提出了非专利文献1中所述的签名方式。图11中示出了该以往的签名方式的顺序。
另外，本说明书中所使用的签名的意义，这里进行了定义。“‖”表示位列彼此的连接。“○”表示每一位的“异或”。“^”表示以右边的被算符为指数计算出左边的被算符的幂的算数算符。例如，f^{-1}为f-1。「_{x}」表示x为脚标。例如，u_{i}为ui。
参照图11，一旦输入了成为签名对象的签名文字u_{i_{m-1}}(S3F100)，便在进行了所具有的密钥的合法性检验(S3F101)与签名句u_{i_{m-1}}的合法性的检验(S3F102)之后，计算出将本签名装置的公开密钥与已经签名了的签名装置的公开密钥连接起来的T_{m}(S3F103)。接下来，计算出T_{m}的散列值与签名句u_{i_{m-1}}的异或U(S3F104)，设U的位列中第一个安全参数k位为a，剩下的为s(S3F105)。接下来，比较a与本签名装置的RSA模量n_{i_{m}}(S3F106)，在a小于RSA模量n_{i_{m}}时，通过秘密密钥d_{i_{m}}对a计算出以RSA方式为准据的签名句u_{i_{m}}(S3F107)，并输出(S3F109)。此时给s添加1位的信息0作为控制信息。另外，在a大于RSA模量n_{i_{m}}时，对于大于模量的数，由于无法计算RSA签名，因此对将a减去了n_{i_{m}}之后的值计算出签名句u_{i_{m}}(S3F108)并输出(S3F109))。此时给s添加1位的信息1作为控制信息。
这样，在RSA的情况下，对于大于签名装置的RSA模量n_{i_{m}}的数，由于无法计算签名，因此基于非专利文献1的以往技术中，在较大的情况下，减去模量n_{i_{m}}之后再添加签名。此时，为了之后的检验能够进行，在其后添加1bit的控制信息(超过了模量的情况下添加1，此外添加0)。签名句u_{i_{m}}的检验时，使用与签顺序与相反的顺序对签名装置的公开密钥反复进行检验，最终追溯到得到预定的初始值，通过这样，判断是正确的签名。
非专利文献1Anna Lysyanskaya，Silvio Micali，Leonid Reyzin，HovavShacham.Sequential Aggregate Signatures from Trapdoor Permutations.InAdvances in Cryptology--EUROCRYPT 2004，vol.3027 of LNCS，pp.74-90.Springer-Verlag，2004.
根据非专利文献1中所述的以前的签名方式，由于即使多个签名装置顺次进行签名，签名句的数据长度的合计值也不与签名装置的台数成比例，因此在存储签名句的情况下，能够削减存储量，在进行通信的情况下，能够削减通信量。但是，存在如下问题即签名长为固定值+签名次数，存在如果签名次数增加，签名长度也稍有延长。
发明内容
本发明的目的在于，改善所述以前的签名方式所具有的问题点，使得签名长度与签名装置的数目无关，为一定值。
本发明第1项涉及一种签名方法，是一种将初始值或其他多个签名装置顺次进行签名操作所生成的签名句、消息、以及本签名装置的秘密密钥作为输入，输出与输入相同长度的签名句的签名装置的签名方法，其特征在于所述所输出的签名句，表示该所述所输出的签名句的生成所述涉及的签名装置，在输入到了各个签名装置的所述消息中，已经进行了签名。
本发明第2项所涉及的签名方法的特征在于，在本发明第1项所记载的签名方法中，计算签名句的操作具有第1与第2这两个步骤，所述第1步骤(f^{-1}部分的操作)的计算中，使用带陷阱门的单向性置换的反函数，所述第2步骤(h^{-1}部分的操作)的计算中，使用与所述第1步骤相比相同或不同的带陷阱门的单向性置换的反函数，如果所述第1步骤结束，便将计算结果存储到存储介质中，在所述第2步骤开始时，从所述存储介质读出必要的数据，如果所述第2步骤结束，便将计算结果存储到所述存储介质中。
本发明第3项所涉及的签名方法的特征在于，在本发明第2项所记载的签名方法中，在所述第1步骤中，如果针对所述第1步骤的输入是所述带陷阱门的单向性置换的值域的元素，便通过该所述带陷阱门的单向性置换的反函数对所述输入进行映射，如果不是则不进行任何操作，如果针对所述第2步骤的输入是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的反函数对所述输入进行映射，如果不是则不进行任何操作。
本发明第4项所涉及的签名方法的特征在于，在本发明第3项所记载的签名方法中，所述第2步骤中所使用的所述带陷阱门的单向性置换的计算进一步由第1与第2子步骤构成，所述第1子步骤(φ^{-1}部分的操作)中，计算签名句全体的空间上的双向单射，该双向单射能够通过多项式时间来计算，并且所述双向单射的反函数也能够通过多项式时间来计算，在所述第2子步骤(g^{-1}部分的操作)中使用带陷阱门的单向性置换的反函数，如果是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的反函数对所述输入映射，如果不是则不进行任何操作，所述第1子步骤与所述第2子步骤的开始时，从所述存储介质读入必要的数据，所述第1子步骤与所述第2子步骤的结束时，将计算结果写入到所述存储介质中。
本发明第5项所涉及的签名方法的特征在于，在本发明第4项所记载的签名方法中，所述第1步骤中所使用的所述带陷阱门的单向性置换，与所述第2步骤的所述第2子步骤中所使用的所述带陷阱门的单向性置换，是RSA函数。
本发明第6项所涉及的签名方法的特征在于，在本发明第5项所记载的签名方法中，所述第2步骤的所述第1子步骤中所使用的所述双向单射，采用φ(x)＝x-n_{i_{m}}mod2^{κ}，所述n_{i_{m}}是作为签名装置i_{m}的公开密钥的一部分的RSA模量，所述κ是安全参数。
本发明第7项所涉及的签名方法的特征在于，在本发明第6项所记载的签名方法中，所述第1步骤之前有T_{m}计算步骤，所述T_{m}计算步骤中，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，对于各个j，所述M_{1}，…，M_{j}是输入给了第j个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥。
本发明第8项所涉及的签名方法的特征在于，在本发明第7项所记载的签名方法中，所述第1步骤之前有异或计算步骤，在所述异或计算步骤中，计算出U＝H(T_{m})○u_{i_{m-1}}，所述H为散列函数，所述u_{i_{m-1}}是所述所输入的签名句，○为异或。
本发明第9项所涉及的签名方法的特征在于，在本发明第8项所记载的签名方法中，所述第1步骤之前，具有密钥合法性检验步骤，在所述密钥合法性检验步骤中，确认pk_{i_{1}}，…，pk_{i_{m-1}}是否完全不同，但在m＝1的情况下，不进行任何确认。
本发明第10项所涉及的签名方法的特征在于，在本发明第9项所记载的签名方法中，所述第1步骤之前，有对所输入的签名句进行检验的签名句检验步骤。
本发明第11项所涉及的签名方法的特征在于，在本发明第2项所记载的签名方法中，所述第1步骤之前，具有对pk_{i_{1}}，…，pk_{i_{m-1}}是否完全不同进行确认的密钥合法性检验步骤，以及对所输入的签名句进行检验的签名句检验步骤。
本发明第12项所涉及的签名方法的特征在于，在本发明第1～11的任一项所记载的签名方法中，具有将所输入的初始值或签名句或他们的散列值作为辅助信息而生成并写入到所述存储介质中的步骤，并将所述辅助信息与签名句作为组输出。
本发明第13项涉及一种签名方法，其特征在于，包括输入单元将初始值或其他多个签名装置顺次进行签名操作而生成的签名句u_{i_{m-1}}、以及输入给这些签名装置的消息M_{1}，…，M_{m-1}输入并保存到存储介质中的步骤；T_{m}计算单元从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，且将‖设为位列彼此的连接时，计算出T_{m}＝M_{1}‖…‖M_{m}‖pK_{i_{1}}‖…‖pk_{i_k_{i_{m}}，并将计算结果保存到所述存储介质中的步骤；异或计算单元在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算出U＝H(T_{m})○u_{i_{m-1}}，将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，并在设n{i{m}}为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出v＝U，并将计算结果保存到所述存储介质中的步骤；双向单射变换单元从所述存储介质读入必要的数据，在设κ为安全参数时，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第2变换单元从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，便计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中的步骤；以及输出单元从所述存储介质读入u_{i_{m}}并作为签名句而输出的步骤。
本发明第14项所涉及的签名方法的特征在于，在本发明第13项所记载的签名方法中，具有由w设置单元在w_{i_{m}}＝u_{i_{m-1}}或设h为散列函数时，计算w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中的步骤，将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
本发明第15项涉及一种检验方法，是一种检验多个签名装置顺次进行签名操作而生成的签名句u是否合法的检验装置的检验方法，其特征在于当且仅当签名句u为，所述所输出的签名句表示，所述所输出的签名句的生成所涉及的签名装置已经在输入在各个签名装置中的所述消息中进行了签名时，通过检验；所述签名句u的位长，是不依赖于为了计算所述签名句u而涉及的所述签名句装置的数目的常数。
本发明第16项涉及一种检验方法，是一种检验多个签名装置顺次进行签名操作而生成的签名句u是否合法的检验装置中的检验方法，其特征在于当且仅当生成签名句u的签名装置通过合法的方法生成了签名句u时通过检验，所述签名句u的位长，是不依赖于为了计算所述签名句u而涉及的所述签名句装置的数目的常数，且所述签名句u的检验，使用作为所述多个签名装置中最后1台执行签名操作之前的数据的辅助信息w来进行。
本发明第17项所涉及的检验方法的特征在于，在本发明第15或16项所记载的签名方法中，检验签名句的操作具有第1与第2这两个步骤，所述第1步骤(h部分的操作)的计算中，使用带陷阱门的单向性置换，所述第2步骤(f部分的操作)的计算中，使用与所述第1步骤相比相同或不同的带陷阱门的单向性置换，在开始所述第1步骤与第2步骤时，从存储介质读出必要的数据，在所述第1步骤与第2步骤结束结束时，将计算结果写入到所述存储介质中。
本发明第18项所涉及的检验方法的特征在于，在本发明第17项所记载的签名方法中，所述第1步骤中，如果针对所述第1步骤的输入是所述带陷阱门的单向性置换的定义域的元素，便通过所述带陷阱门的单向性置换对所述输入进行映射，如果不是则不进行任何操作，如果针对所述第2步骤的输入是所述带陷阱门的单向性置换的定义域的元素，便通过所述带陷阱门的单向性置换对所述输入进行映射，如果不是则不进行任何操作。
本发明第19项所涉及的检验方法的特征在于，在本发明第18项所记载的签名方法中，所述第1步骤中所使用的所述带陷阱门的单向性置换的计算进一步由第1与第2子步骤构成，所述第1子步骤(g部分的操作)中，使用带陷阱门的单向性置换的函数，如果是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的函数对所述输入进行映射，如果不是则不进行任何操作，所述第2子步骤(φ部分的操作)中，计算签名句全体的空间上的双向单射，该双向单射能够通过多项式时间来计算，并且所述双向单射的反函数也能够通过多项式时间来计算，所述第1子步骤与所述第2子步骤的开始时，从所述存储介质读入必要的数据，所述第1子步骤与所述第2子步骤的结束时，将计算结果写入到所述存储介质中。
本发明第20项所涉及的检验方法的特征在于，在本发明第19项所记载的签名方法中，所述第1步骤的所述第1子步骤中所使用的所述带陷阱门的单向性置换，与所述第2步骤中所使用的所述带陷阱门的单向性置换，是RSA函数。
本发明第21项所涉及的检验方法的特征在于，在本发明第20项所记载的签名方法中，所述第1步骤的所述第2子步骤中所使用的所述双向单射，采用φ(x)＝x+n_i_{m}mod 2^{κ}，所述n_{i_{m}}是作为签名装置i_{m}的公开密钥的一部分的RSA模量，所述κ是安全参数。
本发明第22项所涉及的检验方法的特征在于，在本发明第21项所记载的签名方法中，所述第2步骤之后有T_{j}计算步骤，所述T_{j}计算步骤中，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，这里，对各个j，所述M_{1}，…，M_{j}是输入在第j个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥。
本发明第23项所涉及的检验方法的特征在于，在本发明第22项所记载的签名方法中，所述T_{j}计算步骤之后，具有如下那样的u计算步骤即将H设为散列函数，将U设为第2步骤的计算结果时，从所述存储介质读入必要的数据，而计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果存储到所述存储介质中。
本发明第24项所涉及的检验方法的特征在于，在本发明第23项所记载的签名方法中，对j＝m-1，…，1，反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤。
本发明第25项所涉及的检验方法的特征在于，在本发明第24项所记载的签名方法中，在对j＝m-1，…，1反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤之前，有密钥合法性检验步骤，所述密钥合法性检验步骤中，对pk_{i_{1}}，…，pk_{i_{m-1}}全部都不同进行确认，但在m＝1的情况下，不进行任何确认。
本发明第26项所涉及的检验方法的特征在于，在本发明第25项所记载的签名方法中，在对j＝m-1，…，1反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤之后，存在u判断步骤，其中对作为检验结果是否得到了初始值进行判断。
本发明第27项所涉及的检验方法的特征在于，在本发明第2项所记载的签名方法中，所述第1步骤之前有T_{m-1}计算步骤以及v″计算步骤，所述T_{m-1}计算步骤中，计算出T_{m-1}＝M_{1}|…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，这里，M_{1}，…，M_{m-1}是输入在第1，…，m-1个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥；所述v″计算步骤中，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并且所述第1步骤将所述v”作为输入，在所述第2步骤之后，存在判断所述第2步骤的计算结果是否与所述辅助信息相一致的u判断步骤。
本发明第28项涉及一种检验方法，其特征在于，包括输入单元将由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、输入给这些签名装置的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}输入，并保存到存储介质中的步骤；J初始化单元将m-1设为变数j的步骤；第2变换单元，从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，便计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中的步骤；双向单射计算单元从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，如果v＜n_{i_{j}}便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中的步骤；每当将所述变量j减1时重复基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤直到所述变量j变为0的步骤；T{j}计算单元从所述存储介质读入必要的数据，计算出T_{j}＝M{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}并将计算结果保存到所述存储介质中的步骤；u计算单元从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U并将计算结果保存到所述存储介质中的步骤；u判断单元从所述存储介质读入必要的数据，并判断u是否等于预先设定的初始值的步骤；以及输出单元在u等于预先设定的初始值的情况下输出表示检验成功的通知，否则便输出表示检验失败的通知的步骤。
本发明第29项涉及一种检验方法，其特征在于，包括输入单元对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、前一个签名装置所输入的签名句或其散列值即辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中的步骤；T_{m-1}计算单元从所述存储介质读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中的步骤；v″计算单元从所述存储介质读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中的步骤；第2变换单元从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，便计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出v′＝v″，并将计算结果保存到所述存储介质中的步骤；双向单射计算单元从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，便计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中的步骤；u判断单元从所述存储介质读入必要的数据，并判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致的步骤；以及输出单元在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则，输出表示检验失败的通知的步骤。
本发明第30项涉及一种签名装置，其特征在于，包括可读写的存储介质；输入单元，其对初始值或其他多个签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、以及输入在这些签名装置中的消息M_{1}，…，M_{m-1}进行输入，并保存到存储介质中；T_{m}计算单元，其从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，将‖设为位列彼此的连接时，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中；异或计算单元，其在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算出U＝H(T_{m})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，在将n_{i_{m}}设为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算v＝U，并将计算结果保存到所述存储介质中；双向单射变换单元，其从所述存储介质读入必要的数据，在将κ设为安全参数时，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，则计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中；以及输出单元，其从所述存储介质读入u_{i_{m}}，并作为签名句输出。
本发明第31项所涉及的签名装置的特征在于，在本发明第30项所记载的签名方法中，具有w设置单元，其在w_{i_{m}}＝u_{i_{m-1}}，或者将h设为散列函数时，计算w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中；将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
本发明第32项涉及一种检验装置，其特征在于，包括可读写的存储介质；输入单元，其对由其他的1个以上的签名装置顺次进行了签名操作而生成的签名句u_{i_{m-1}}、输入在些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；J初始化单元，其将m-1设置为变量j；第2变换单元，其从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{j}}，便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中；T{j}计算单元，其每当将所述变量j减1时，重复执行了基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤之后，从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，并将计算结果保存到所述存储介质中；u计算单元，其从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，并判断u是否等于预先设定的初始值；以及输出单元，其在u等于预先设定的初始值情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
本发明第33项涉及一种检验装置，其特征在于，包括可读写的存储介质；输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、作为前一个签名装置所输入的签名句或其散列值的辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}进行输入，并保存到存储介质中；T_{m-1}计算单元，其从所述存储介质读入必要的数据，计算T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中；v″计算单元，其从所述存储介质读入必要的数据，计算v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，则计算v′＝v″^{e_{i_{m-1}}}modn_{i_{m-1}}，否则计算出v′＝v″，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，则计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致；以及输出单元，其在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
本发明第34项涉及一种程序，让具有可读写的存储介质的计算机起到作为以下单元而发挥功能输入单元，其对初始值或其他多个签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、以及输入在这些签名装置中的消息M_{1}，…，M_{m-1}进行输入，并保存到存储介质中；T_{m}计算单元，其从所述存储介质以及公开密钥存储装置读入必要的数据，在将pK_{i_{j}}设为签名装置i_{j}的公开密钥，将‖设为位列彼此的连接时，计算T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中；异或计算单元，其在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算U＝H(T_{m})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，在将n_{i_{m}}设为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出v＝U，并将计算结果保存到所述存储介质中；双向单射变换单元，其从所述存储介质读入必要的数据，在将κ设为安全参数时，计算v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，便计算u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中；以及输出单元，其从所述存储介质读入u_{i_{m}}，并作为签名句输出。
本发明第35项所涉及的程序的特征在于，在本发明第34项所记载的签名方法中，让所述计算机进一步起到作为w设置单元而发挥功能，所述w设置单元在w_{i_{m}}＝u_{i_{m-1}}，或将h设为散列函数时，计算出w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中，并且将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
本发明第36项涉及一种程序，让具有可写入的存储介质的计算机作为以下单元而发挥功能输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、输入给这些签名装置的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；J初始化单元，其将m-1设为变量j；第2变换单元，其从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，便计算出v′＝u_{i_{j}}^{e_{i_{j}}}modn_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{j}}，便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中；T_{j}计算单元，其在每当将所述变量j减1时，重复执行了基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤之后，从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，并将计算结果保存到所述存储介质中；u计算单元，其从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u是否等于预先设定的初始值；以及输出单元，其在u＝预先设定的初始值的情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
本发明第37项涉及一种程序，让具有可读写的存储介质的计算机起到作为以下单元的功能输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、作为前一个签名装置所输入的签名句或其散列值的辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；T_{m-1}计算单元，其从所述存储介质读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中；v″计算单元，其从所述存储介质读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，则计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出v′＝v″，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，便计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}modn_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致；以及输出单元，其在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则，便输出表示检验失败的通知。
本发明中，在签名装置i_{m}中进行在所输入的签名句u_{i_{m-1}}超过了模量n_{i_{m}}的情况下，不进行任何操作，在没有超过的情况下，进行以RSA签名为准据的签名的第1操作；对第1操作的结果，作用向大至模量n_{i_{m}}的方向映射的函数的第2操作；以及在该第2操作的结果超过了模量n_{i_{m}}的情况下，不进行任何操作，在没有超过的情况下，进行以RSA签名为准据的签名的第3操作。这里，如果设各个签名装置的RSA模量的位长与安全参数κ相等，签名句u_{i_{m-1}}以及签名装置i_{m}的模量n_{i_{m}}就变为小于2^{κ}的数。第1操作中，对取0～n_{i_{m}}的值的签名句u_{i_{m-1}}，进行以RSA签名为准据的签名，因此第1操作之后的值变为0～n_{i_{m}}，另外，对于取n_{i_{m}}～2^{κ}的值的签名句u_{i_{m-1}}，不进行任何操作，因此第1操作之后的值变为n_{i_{m}}～2^{κ}。另外，第2操作中，进行从第1操作之后的值向以2^{κ}为模量的n_{i_{m}}的加法，因此第2操作之后的值也变为小于2^{κ}的数，但第1操作之后的值为n_{i_{m}}～2^{κ}者，在第2操作之后变为0～n_{i_{m}}。因此，第3操作中，对第2操作之后的值变为0～n_{i_{m}}者进行以RSA签名为准据的签名，由此对任意值的签名句u_{i_{m-1}}，至少都进行1次RSA签名。另外，第3操作之后的值，也即签名值u_{i_{m}}的值与所输入的签名句u_{i_{m-1}}的值一一对应，因此根据签名值u_{i_{m}}的值，能够唯一决定所实施的签名操作，从而不需要添加非专利文献1中那样的控制位。
第1效果是，签名长度不依赖于签名装置的数目。其原因是，签名前的数据与签名后所生成的数据位数不变。
第2效果是，能够在每次签名时变更签名装置的顺序。其原因与第1效果的情况下相同，签名前的数据与签名后所生成的数据位数不变。因此，对各个签名装置的输入是一定的，跟该签名装置是第几个进行签名的无关，因此不管是第几个，都能够通过相同的操作来签名。
第3效果是，与签名装置勾结的攻击者，无法伪造出从线路中的“诚实honest”的签名装置中通过的签名句。其原因在于，不管对签名装置的输入u是什么，签名时最多进行两次的RSA计算中的至少一方的u不变。
第4效果是，在系统使用的开始阶段，不需要知道签名装置的数目m，即使签名装置的数目m在使用中动态变化，也能够正常使用。其原因是，签名装置的数目为m+1台时的签名顺序，是在进行了签名装置的数目为m台时的签名顺序之后再进行一次同样的签名操作，签名的操作方法不依赖于签名装置的数目m。
图1为本发明的第1实施方式的方框图。
图2为表示本发明的第1实施方式中的签名装置之构成的方框图。
图3为表示本发明的第1实施方式中的签名装置之动作的流程图。
图4为表示本发明的第1实施方式中的检验装置之构成的方框图。
图5为表示本发明的第1实施方式中的检验装置之动作的流程图。
图6为本发明的第2实施方式的方框图。
图7为表示本发明的第2实施方式中的签名装置之构成的方框图。
图8为表示本发明的第2实施方式中的签名装置之动作的流程图。
图9为表示本发明的第2实施方式中的检验装置之构成的方框图。
图10为表示本发明的第2实施方式中的检验装置之动作的流程图。
图11为表示以前的签名装置之动作的流程图。
图中i_{1}，…，i_{m-1}-签名装置，i_{1}-2，…，i_{m-1}-2-检验装置，i_{1}-3，…，i_{m-1}-3-密钥存储装置，i_{1}-4，…，i_{m-1}-4-密钥合法性检验装置，i_{1}-5，…，i_{m-1}-5-密钥生成装置，M_{1}，…，M_{m}-消息，
u_{i_{0}}，…，u_{i_{m-1}}-签名句，w_{i_{0}}，…，w_{i_{m-1}}-辅助信息。
具体实施例方式
<第1实施方式>
对照图1，本发明的第1实施方式，由签名装置i_{1}，…，i_{m}、检验装置i_{1}-2，…，i_{m-1}-2、公开密钥存储装置i_{1}-3，…，i_{m-1}-3、密钥合法性检验装置i_{1}-4，…，i_{m}-4、以及秘密密钥存储装置i_{1}-5，…，i_{m-1}-5构成。
参照图2，签名装置i_{m}由输入单元S1B100、T_{m}计算单元S1B103、异或计算单元S1B104、第一变换单元S1B105、双向单射变换单元S1B106、第二变换单元S1B107、存储介质S1B108、以及输出单元S1B109构成，其他的签名装置也具有与签名装置i_{m}相同的构成。
参照图4，检验装置i_{m}-2由输入单元V1B100、j初始化单元V1B102、j判断单元V1B103、第二变换单元V1B104、双向单射变换单元V1B105、第一变换单元V1B106、T_{j}计算单元V1B107、u计算单元V1B108、j减少单元V1B109、存储介质V1B1010、u判断单元V1B1011、accept输出单元V1B1012、以及reject输出单元V1B1013构成。其他检验装置也具有与检验装置i_{m}-2相同的构成。
对本实施方式进行概述。首先，给签名装置i_{1}输入签名装置i_{1}的公开密钥秘密密钥对、初始值u_{i_{0}}、以及消息M_{1}。签名装置i_{1}使用u_{i_{0}}生成对消息M_{1}的签名句u_{i_{1}}。之后，顺次给签名装置i_{j}输入签名装置i_{j}的公开密钥秘密密钥对、前一个签名装置所输出的签名句u_{i_{j-1}}、以及消息M_{j}，签名装置i_{j}使用这些生成签名句u_{i_{j}}。签名句u_{i_{j}}是表示签名装置i_{1}在消息M_{1}中进行了签名，签名装置i_{2}在消息M_{2}中进行了签名，…、签名装置i_{j}在消息M_{j}中进行了签名的数据。
对各个j，给检验装置i_{j}输入签名装置i_{1}，…，i_{j}的公开密钥与消息M_{1}，…，M_{j-1}，以及签名句u_{i_{j-1}}。于是，检验装置i_{j}对签名句u_{i_{j-1}}是否是使用签名装置i_{1}，…，i_{j-1}的秘密密钥，且针对消息M_{1}，…，M_{j-1}所生成的签名句进行检验。
本实施方式的系统目标是，生成签名句u_{i_{m}}即对签名装置i_{1}在消息M_{1}中进行了签名，签名装置i_{2}在消息M_{2}中进行了签名，…，签名装置i_{m}在消息M_{m}中进行了签名进行表示的数据。
另外，本实施方式系统的应用开始阶段，不需要知道签名装置的数目m。签名装置的数目m可以在应用中动态变化。另外，签名装置i{1}，…，i_{m}的动作完全相同。检验装置、公开密钥存储装置、密钥合法性检验装置、秘密密钥存储装置也基本都进行相同的动作。
接下来对本实施方式进行详细说明。
签名装置i_{j}的公开密钥pk_{i}、秘密密钥sk_{i}分别为(n_{i}，e_{i})、(p_{i_{j}}，q_{i_{j}}，d_{i_{j}})，满足下面的5个性质。
1.p_{i_{j}}，q_{i_{j}}为质数。
2.n_{i_{j}}＝p_{i_{j}}q_{i_{j}}3.n_{i_{j}}的位长等于安全参数κ。
4.p_{i_{j}}，q_{i_{j}}的位长为相同程度。
5.e_{i_{j}}与Φ(n_{i})互为质数。
6.d_{i_{j}}＝e_{i_{j}}-1 mod Φ(n_{i})其中，这里Φ(n_{i})为1以上不满n_{i}且与n_{i}互为质数的整数的个数。生成满足该性质(pk_{i}，(sk_{i})的方法，例如记载在非专利文献2「Alfred J.Menezes Paul C.van Oorschot，and Scott A.Vanstone.Handbookof Applied Cryptography.CRC Press.」(http//www.cacr.math.uwaterloo.ca/hac/)中。
从安全性的观点来说，最好能够均对e_{i_{j}}是否与Φ(n_{i})互为质数进行确认。作为能够进行该确认的方法，有使e_{i_{j}}为比n_{i}大的质数的方法。但e_{i}}不一定必须满足该性质。
对各个j＝1，…，m，秘密密钥存储装置i_{j}-5存储秘密密钥sk_{i_{j}}，公开密钥存储装置i_{j}-3存储公开密钥pk_{1}，…，pk_{m}。
对密钥合法性检验装置i_{m}-4的动作进行说明。密钥合法性检验装置i_{m}-4是确认公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}的合法性的装置。为了确认合法性，首先，从密钥存储装置i_{m}-3读入pk_{i_{1}}，…，pk_{i_{m-1}}，确认pk_{i_{1}}，…，pk_{i_{m-1}}全部都不同。但在m＝1的情况下，不进行确认。
从安全性的观点出发，希望也对e_{i_{j}}与Φ(n_{i})互为质数进行确认，但也可以省略该确认。
对签名装置i_{m}的动作进行说明。对照图2、图3，对如下方法进行说明将消息M_{1}，…，M_{m}以及由签名装置i_{1}，…，i_{m-1}使用公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}所生成的针对消息M_{1}，…，M_{m-1}的签名句u_{i_{m-1}}，输入给了签名装置i_{m}时，签名装置i_{m}在消息M_{m}中进行签名。
签名装置i_{m}首先通过输入单元S1B101，读入M_{1}，…，M_{m}、pk_{i_{1}}，…，pk_{i_{m}}、sk_{i_{m}}、u_{i_{m-1}}，并存储到存储介质S1B108中(S1F100)。其中，在m＝1的情况下，满足u_{i_{0}}＝0。
接下来，签名装置i_{m}将u_{i_{m-1}}、M_{1}，…，M_{m-1}、pk_{i_{1}}，…，pk_{i_{m-1}}发送给检验装置i_{m}-2。检验装置i_{m}-2检验签名句u_{i{m-1}}的合法性(S1B101，S1F102)。此时，检验装置i_{m}-2将pk_{i_{1}}，…，pk_{i_{m-1}}发送给密钥合法性检验装置i_{m}-4。密钥合法性检验装置i_{m}-4对密钥的合法性进行检验(S1B102，S1F101)。设在m＝1的情况下，只确认出u_{i_{0}}＝0。
从安全性的观点来说，希望进行所述u_{i_{m-1}}的检验与密钥合法性检验，但为了实现高效化，可以省略其中一方或双方的操作。
接下来，签名装置i_{m}通过T_{m}计算单元S1B103，从存储介质S1B108读入必要的数据，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}(S1F103)。一旦计算结束，T_{m}计算单元S1B103便在存储介质S1B108中写入T_{m}。
接下来，签名装置i_{m}通过异或单元S1B104，从存储介质S1B108读入必要的数据，计算U＝H_(T_{m})○u_{i_{m-1}}，并将计算结果存储到存储介质S1B108中(S1F104)。这里，H为输出与所输入的位数相同的散列(hash)值的散列函数。
接下来，签名装置i_{m}通过第一变换单元S1B105，从存储介质S1B108读入输入给签名装置i_{m}的数据，首先判断U是否小于n_{i_{m}}(S1F105)。如果U＜n_{i_{m}}，签名装置i_{m}便通过第一变换单元S1B105计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，并将计算结果写入到存储介质S1B108中(S1F106)。反之，如果U≥n_{i_{m}}，签名装置i_{m}便通过第一变换单元S1B105，设为v＝u，将计算结果写入到存储介质S1B108中(S1F107)。
接下来，签名装置i_{m}通过双向单射变换单元S1B106，从存储介质S1B108读入必要的数据，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果写入到存储介质S1B108中(S1F108)。
接下来，签名装置i_{m}通过第二变换单元S1B107，从存储介质S1B108读入必要的数据，判断v′是否小于n_{i_{m}}(S1F109)。如果v′＜n_{i_{m}}，签名装置i_{m}便通过第二变换单元S1B107，计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，并将计算结果写入到存储介质S1B108中(S1F1010)。反之，如果v′≥n_{i_{m}}，签名装置i_{m}便通过第二变换单元S1B107计算出u_{i_{m}}＝v′，将计算结果写入到存储介质S1B108中(S1F1011)。
最后，签名装置i_{m}通过输出单元S1B109，从存储介质S1B108读入u_{i_{m}}并输出(S1F1012)。
这样，签名装置i_{m}判断所输入的签名句u_{i_{m-1}}是否超过了模量n_{i_{m}}，在超过了的情况下，不进行操作，在没有超过的情况下，执行进行以RSA方式为准据的签名的第1操作，对该第1操作的结果执行对其作用向大至模量n_{i_{m}}的方向映射的函数的第2操作，判断该第2操作的结果是否超过了模量n_{i_{m}}，在超过了的情况下，不进行操作，在没有超过的情况下，执行进行以RSA方式为准据的签名的第3操作。根据签名句u_{i_{m-1}}的值，存在RSA签名被实施两次的的冗长，但是也能够根据签名值u_{i_{m}}的值来唯一决定所实施的签名操作，因此不需要附加非专利文献1中那样的控制位。
接下来，参照图4、图5，对检验装置i_{m}-2检验签名句u_{m-1}的方法进行说明。
检验装置i_{m}-2，首先通过输入单元V1B100从公开密钥存储装置i_{m}-3读入pk_{i_{1}}，…，pk_{i_{m-1}}，进而读入消息M_{1}，…，M_{m-1}(V1F100)。所读入的数据由输入单元V1B100写入到存储介质V1B1010中。
接下来，检验装置i_{m}-2通过输入单元V1B100将pk_{i_{1}}，…，pk_{i_{m-1}}发送给密钥检验装置i_{m}-4，请求其检验公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}的合法性(V1B101，V1F101)。
接下来，检验装置i_{m}-2为了从前一个签名装置追溯到第一个签名装置而顺次进行检验处理，首先，通过j初始化单元V1B102，将m-1设置为对正在检验哪个签名装置的签名进行管理的变量j(V1F102)。
接下来，检验装置i_{m}-2通过j判断单元V1B103，判断是否为j＞0(V1F103)。
下面，对j＞0的情况下的检验装置i_{m}-2的动作进行说明。关于不是j＞0的情况下的动作，将在后面说明。
接下来，检验装置i_{m}-2通过第二变换单元V1B104，首先从存储介质V1B1010读入必要的数据，判断是否为u_{i_{j}}＜n_{i_{j}}(V1F104)。
之后，如果是u_{i_{j}}＜n_{i_{j}}，检验装置i_{m}-2便通过第二变换单元V1B104，计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，并将计算结果写入到存储介质V1B1010中(V1F105)。
反之，如果不是u_{i_{j}}＜n_{i_{j}}，检验装置i_{m}-2便通过第二变换单元V1B104，将v′＝u_{i_{j}作为计算结果，写入到存储介质V1B1010中(V1F106)。
接下来，检验装置i_{m}-2通过双向单射计算单元V1B105，从存储介质V1B1010读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，将计算结果写入到存储介质V1B1010中(V1F107)。
接下来，检验装置i_{m}-2通过第一变换单元V1B106，从存储介质V1B1010读入必要的数据，首先判断是否为v＜n_{i_{j}}(V1F108)。
于是，如果是v＜n_{i_{j}}，检验装置i_{m}-2便通过第一变换单元V1B106计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，并将计算结果写入到存储介质V1B1010中(V1F109)。
另一方面，如果v＜n_{i_{j}}，检验装置i_{m}-2便通过第一变换单元V1B106，将U＝v作为计算结果写入到存储介质V1B1010中(V1F1010)。
接下来，检验装置i_{m}-2通过T_{j}计算单元V1B107，从存储介质V1B1010读入必要的数据，并计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，将计算结果写入到存储介质V1B1010中(V1F1011)。
检验装置i_{m}-2接着通过u计算单元V1B108，从存储介质V1B1010读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果写入到存储介质V1B1010中(V1F1012)。
接下来，检验装置i_{m}-2通过j減少单元V1B 109，使得j＝j-1(V1F1013)。
之后，检验装置i_{m}-2再次通过j判断单元V1B103，判断是否为j＞0(V1F103)。
如果j＞0，检验装置i_{m}-2便进行步骤V1F104之后的处理。
如果j＝0，检验装置i_{m}-2便通过u判断单元V1B1011，从存储介质V1B1010读入必要的数据，调查是否为u＝0(V1F1014)。
之后，如果u＝0，检验装置i_{m}-2便通过accept输出单元V1B1012，输出表示检验成功的accept(V1F1015)，如果不是这样，便通过reject输出单元V1B1013，输出表示检验失败的reject(V1F1016)。
另外，设图5的虚线所包围的部分的操作为f(x)，g(x)，h(x)，φ(x)。
也即f(x)＝x^{e_{i_{j}}}mod n_{i_{j}} ifx＜n_{i_{j}}＝x otherwise.
g(x)＝x^{e_{i_{j}}}mod n_{i_{j}} ifx＜n_{i_{j}}＝x otherwise.
φ(x)＝x+n_{i_{j}}mod 2^{κ}h(x)＝g(φ(x))。
于是，图3的虚线所包围的部分的操作f^{-1}(x)，g^{-1}(x)，h^{-1}(x)，φ^{-1}(x)，分别是f(x)，g(x)，h(x)，φ(x)的反函数。
因此，本实施方式中的签名装置i_{m}，通过计算公式u_{i_{m}}＝(g_{m}^{-1}(φ^{-1}(f_{m}^{-1}(H(T_{m})○u_{i_{m-1}}))))，生成签名句。另外，本实施方式中的检验装置i_{m}-2，通过计算公式u_{i_{m-2}}＝H(T_{m-1})○(f_{m-1}(φ(g_{m-1}(u_{i_{m-1}}))))，求出成为前一个签名装置的输入的签名句，之后重复进行同样的处理，直到达到最初的签名装置，求出输入的初始值，并调查所求出的初始值是否与预先设定的初始值(本实施方式的情况下为值0)相一致。
接下来，对本实施方式的效果进行说明。
第1效果是，签名长度不依赖于签名装置的数目。其原因是，签名前的数据与签名后所生成的数据位数不变。
第2效果是，能够在每次签名时变更签名装置的顺序。其原因与第1效果的情况下相同，签名前的数据与签名后所生成的数据位数不变。因此，对各个签名装置的输入是一定的，跟该签名装置是第几个进行签名的无关，因此不管是第几个，都能够通过相同的操作来签名。但需要通过某种形式，将按照什么样的顺序进行了签名通知给检验装置。
第3效果是与签名装置勾结的攻击者，无法伪造出从线路中途的“诚实(honest)”的签名装置中通过的签名句。其原因在于，不管对签名装置的输入u是什么，签名时进行两次的RSA计算中的至少一方的u变化。
第4效果是，在开始系统的使用的阶段，不需要知道签名装置的数目m，这是由于，即使签名装置的数目m在使用中动态变化，也能够正常使用。其原因是，签名装置的数目为m+1台时的签名顺序，是在进行了签名装置的数目为m台时的签名顺序之后再进行一次同样的签名操作，签名的操作方法不依赖于签名装置的数目m。
另外，以上的第1实施方式中，使用很典型的例子即RSA函数进行了说明，但更普通的是，只要有存在于{0，1}^{κ}中的部分集合X，并且满足以下条件(1)、(2)，就跟第1实施方式一样，能够实现一种签名长度不依赖于签名者的人数且安全的签名方式。
(1)f，g是带陷阱门的单向性置换，且X既包括在f的定义区中又包括在g的定义区中。
(2)φ、φ、φ^{-1}都是在多项式时间中能够计算的{0，1}^{κ}上的双向单射，将{0，1}^{κ}\X映射到X中。
这里，带陷阱门的单向性置换，是满足以下4个性质的函数。
1)计算f较为容易。
2)对于不知道陷阱门(也称作秘密密钥)的人来说，很难计算出f^{-1}。
3)对于知道陷阱门的人来说，计算f^{-1}很容易。
4)是双向单射(全单射)。
进而，一般来说存在位于{0，1}^{κ}中的部分集合X，如果满足以下条件(1)、(2)，就与第1实施方式一样，能够实现签名长度不依赖于签名者的人数且安全的签名方式。
(1)f是带陷阱门的单向性置换，且X包括在f的定义区中。
(2)h是带陷阱门的单向性置换，且{0，1}^{κ}\X包括在h的定义区中。
第2实施方式参照图6，本发明的第2实施方式，由签名装置i_{1}，…，i_{m}、检验装置i_{1}-2，…，i_{m}-2、公开密钥存储装置i_{1}-3，…，i_{m}-3、密钥合法性检验装置i_{1}-4，…，i_{m}-4、以及秘密密钥存储装置i_{1}-5，…，i_{m}-5构成。
参照图7，签名装置i_{m}由输入单元S1B100、T_{m}计算单元S1B103、异或计算单元S1B104、第一变换单元S1B105、双向单射变换单元S1B106、第二变换单元S1B107、存储介质S1B108、输出单元S1B109以及w设置单元S2B100构成。其他的签名装置也具有与签名装置i_{m}相同的构成。
参照图9，检验装置i_{m}-2由输入单元V2B200、T_{m-1}计算单元V2B202、v″计算单元V2B203、第二变换单元V2B204、双向单射变换单元V2B205、第一变换单元V2B206、u判断单元V2B207、accept输出单元V2B208、reject输出单元V2B209以及存储介质V2B2010构成。其他的检验装置也具有与检验装置i_{m}-2相同的构成。
对本实施方式进行概述。首先，给签名装置i_{1}输入签名装置i_{1}的公开密钥秘密密钥对、初始值u_{i_{0}}、以及消息M_{1}。签名装置i_{1}使用u_{i_{0}}生成针对消息M_{1}的签名句u_{i_{1}}。并且将初始值u_{i_{0}}作为辅助信息w_{i_{1}}而生成，输出u_{i_{1}}与w_{i_{1}}之组。接下来，给签名装置i_{2}输入签名装置i_{2}的公开密钥秘密密钥对、u_{i_{1}}与w_{i_{1}}之组、以及消息M_{2}。签名装置i_{2}使用u_{i_{1}}，生成针对消息M_{2}的签名句u_{i_{2}}，并且将u_{i_{1}}作为補助信息w_{i_{2}}而生成，输出u_{i_{2}}与w_{i_{2}}之组。之后，顺次给签名装置i_{j}输入签名装置i_{j}的公开密钥秘密密钥对、前一个签名装置所输出的签名句u_{i_{j-1}}、辅助信息w_{i_{j-1}}、以及消息M_{j}，签名装置i_{j}使用这些生成签名句u_{i_{j}}与辅助信息w_{i_{j}}之组。u_{i_{j}}是与第1实施方式相同的签名句，是表示签名装置i_{1}在消息M_{1}中进行了签名，签名装置i_{2}在消息M_{2}中进行了签名，…、签名装置i_{j}在消息M_{j}中进行了签名的数据。
另外，w_{i_{j}}是用来让签名句u_{i_{j}}的检验能够简单地进行的辅助信息，本实施方式的情况下，是成为签名装置i{j}的输入的签名句u_{i_{j-1}}本身。对各个j，若给检验装置i_{j}输入签名装置i_{1}，…，i_{j}的公开密钥与消息M_{1}，…，M_{j-1}，以及签名句u_{i_{j-1}}，w_{i_{j-1}}，则检验装置i_{j}运用辅助信息w_{i_{j-1}}，对u_{i_{j-1}}是否是使用签名装置i{1}，…，i{j-1}的公开密钥生成了针对消息M{1}，…，M_{j-1}的签名句进行检验。
本实施方式的系统目标与第1实施方式一样，是生成签名句u_{i_{m}}，也即表示签名装置i_{1}在消息M_{1}中进行了签名，签名装置i_{2}在消息M_{2}中进行了签名，…，签名装置i_{m}在消息M_{m}中进行了签名的数据。
另外，与第1实施方式一样，另外，本实施方式系统的应用开始阶段，也不需要知道签名装置的数目m。签名装置的数目m可以在应用中动态变化。另外，签名装置i_{1}，…，i_{m}的动作完全相同。检验装置、公开密钥存储装置、密钥合法性检验装置、秘密密钥存储装置也基本都进行相同的动作。
接下来以与第1实施方式的不同的为中心，对本实施方式进行详细说明。
签名装置i_{j}的公开密钥pk_{i}、秘密密钥sk_{i}，与第1实施方式一样被生成，对各个j＝1，…，m，秘密密钥存储装置i_{j}-5存储秘密密钥sk_{i_{j}}，且公开密钥存储装置i_{j}-3存储公开密钥pk_{1}，…，pk_{m}。
密钥合法性检验装置的动作与第1实施方式相同。
在将消息M_{1}，…，M_{m}、签名装置i_{1}，…，i_{m-1}使用公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}所生成的针对消息M_{1}，…，M_{m-1}的签名句u_{i_{m-1}}、以及辅助信息w_{i_{m-1}}输入给了签名装置i_{m}时的、签名装置i_{m}在消息M_{m}中进行签名的方法中，添加了生成辅助信息的顺序这一点，与第1实施方式不同，此外均与第1实施方式相同。对照图7、图8进行说明，本实施方式的情况下，签名装置i_{m}接着步骤S1F102的处理，通过w设置单元S2B100，计算出w_{i_{m}}＝u_{i_{m-1}}，并将计算结果写入到存储介质S1B108中(S2F100)。写入到了存储介质S1B108中的辅助信息w_{i_{m}}，与由输出单元S1B109通过与第1实施方式相同的顺序所生成并写入在存储介质S1B108中的签名句u_{i_{m}}一起被读出、输出(S1F1012′)。
接下来，对照图9、图10，对检验装置i_{m}-2检验签名句u_{m-1}的方法进行说明。
检验装置i_{m}-2，首先通过输入单元V1B200从公开密钥存储装置i_{m}-3读入pk_{i_{1}}，…，pk_{i_{m-1}}，进而读入消息M_{1}，…，M_{m-1}，并写入到存储介质V1B2010中。(V1F200)。
接下来，检验装置i_{m}-2通过输入单元V2B200，将pk_{i_{1}}，…，pk_{i_{m-1}}发送给密钥检验装置i_{m}-4，请求其检验公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}的合法性(V2F201)。
接下来，检验装置i_{m}-2通过T_{m-1}计算单元V2B202，从存储介质V2B2010读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果T_{m-1}保存到存储介质V2B2010中(V2F202)。
接下来，检验装置i_{m}-2通过v″计算单元V2B203，从存储介质V2B2010读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果v″保存到存储介质V2B2010中(V2F203)。
接下来，检验装置i_{m}-2通过第二变换单元V2B204，从存储介质V2B2010读入必要的数据，判断是否为v″＜n_{i_{m-1}}(V2F204)。如果是v″＜n_{i_{m-1}}，检验装置i_{m}-2便通过第二变换单元V2B204计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，并将计算结果v′保存到存储介质V2B2010中(V2F205)。另外，如果不是v″＜n_{i_{m-1}}，检验装置i_{m}-2便设为v′＝v″，并将计算结果v′保存到存储介质V2B2010中(V2F206)。
接下来，检验装置i_{m}-2通过双向单射变换单元V2B205，从存储介质V2B2010读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果v保存到存储介质V2B2010中(V2F207)。
接下来，检验装置i_{m}-2通过第一变换单元V2B206，从存储介质V2B2010读入必要的数据，判断是否是v＜n_{i_{m-1}}(V2F208)。如果v＜n_{i_{m-1}}，检验装置i_{m}-2便通过第一变换单元V2B206，计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}mod n_{i_{m-1}}}，并将计算结果u_{i_{m-2}}保存到存储介质V2B2010中(V2F209)。另外，如果不是u_{i_{m-2}}＜n_{i_{m-1}}，检验装置i_{m}-2便设u_{i_{m-1}})＝v，将计算结果u_{i_{m-2}}保存到存储介质V2B2010中(V2F2010)。
接下来，检验装置i_{m}-2通过u判断单元V2B2011，从存储介质V2B2010读入必要的数据，调查是否为u_{i_{m-2}}}＝w_{i_{m-1}}(V2F2011)。如果是u_{i_{m-2}}}＝w_{i_{m-1}}，检验装置i_{m}-2便通过accept输出单元V2B208输出accept(V2F2012)，如果不是，便通过reject输出单元V2B209输出reject(V2F2013)。
接下来，对本实施方式的效果进行说明。
第1效果是，签名长度不依赖于签名装置的数目。其原因是，签名前的数据与签名后所生成的数据位数不变。但与第1实施方式相比，数据长度增加了辅助信息的部分。
第2效果是，与第1实施方式相比，能够削减检验计算的计算量。其原因是，第1实施方式中，最终需要求出初始值，因此需要与已进行过签名签名的签名装置的数目成正比的检验计算，与此相对，本实施方式中，成为前一个签名装置的输入的签名句被作为辅助信息传送过来，因此只需要进行1签名装置份量的检验计算。但本实施方式需要以前一个签名装置能够信赖为前提，与不需要这样的前提就能够证明安全性的第1实施方式相比，安全性降低。
此外，还起到了与第1实施方式相同的效果。
另外，本实施方式中，作为与签名句u_{i_{j}}成组的辅助信息w_{i_{j}}，采用成为签名装置i_{j}的输入的签名句u_{i_{j-1}}本身，但也可以将h作为输出与输入位数相同的散列值的的给定的散列函数，并将u_{i_{j-1}}的散列值h(u_{i_{j-1}})作为辅助信息w_{i_{j}}。另外，对本实施方式也能够进行与第1实施方式相同的附加变更。
以上对本发明的实施方式进行了说明，但本发明并不仅限于以上实施方式，还可以进行其他各种附加变更。另外，本发明的签名装置与检验装置，其所具有的功能当然能够硬件实现，还可以通过计算机与程序来实现。程序在磁盘或半导体存储器等计算机可读存储介质中进行记录并被提供，在计算机的启动等时读入到计算机中，控制该计算机的动作，通由此使该计算机起到上述各个实施方式中的签名装置以及检验装置的功能。
权利要求
1.一种签名方法，是一种将初始值或其他多个签名装置顺次进行签名操作所生成的签名句、消息、以及本签名装置的秘密密钥作为输入，输出与输入相同长度的签名句的签名装置的签名方法，其特征在于所述所输出的签名句，表示该所述所输出的签名句的生成所述涉及的签名装置，在输入到了各个签名装置的所述消息中进行了签名。
2.如权利要求1所述的签名方法，其特征在于计算签名句的操作具有第1与第2这两个步骤，所述第1步骤(f^{-1}部分的操作)的计算中，使用带陷阱门的单向性置换的反函数，所述第2步骤(h^{-1}部分的操作)的计算中，使用与所述第1步骤相比相同或不同的带陷阱门的单向性置换的反函数，如果所述第1步骤结束，便将计算结果存储到存储介质中，在所述第2步骤开始时，从所述存储介质读出必要的数据，如果所述第2步骤结束，便将计算结果存储到所述存储介质中。
3.如权利要求2所述的签名方法，其特征在于在所述第1步骤中，如果针对所述第1步骤的输入是所述带陷阱门的单向性置换的值域的元素，便通过该所述带陷阱门的单向性置换的反函数对所述输入进行映射，如果不是则不进行任何操作，如果针对所述第2步骤的输入是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的反函数对所述输入进行映射，如果不是则不进行任何操作。
4.如权利要求3所述的签名方法，其特征在于所述第2步骤中所使用的所述带陷阱门的单向性置换的计算进一步由第1与第2子步骤构成，所述第1子步骤(φ^{-1}部分的操作)中，计算签名句全体的空间上的双向单射，该双向单射能够通过多项式时间来计算，并且所述双向单射的反函数也能够通过多项式时间来计算，在所述第2子步骤(g^{-1}部分的操作)中使用带陷阱门的单向性置换的反函数，如果是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的反函数对所述输入映射，如果不是则不进行任何操作，所述第1子步骤与所述第2子步骤的开始时，从所述存储介质读入必要的数据，所述第1子步骤与所述第2子步骤的结束时，将计算结果写入到所述存储介质中。
5.如权利要求4所述的签名方法，其特征在于所述第1步骤中所使用的所述带陷阱门的单向性置换，与所述第2步骤的所述第2子步骤中所使用的所述带陷阱门的单向性置换，是RSA函数。
6.如权利要求5所述的签名方法，其特征在于所述第2步骤的所述第1子步骤中所使用的所述双向单射，使用φ(x)＝x-n_{i_{m}}mod 2^{κ}，所述n_{i_{m}}是作为签名装置i_{m}的公开密钥的一部分的RSA模量，所述κ是安全参数。
7.如权利要求6所述的签名方法，其特征在于所述第1步骤之前有T_{m}计算步骤，所述T_{m}计算步骤中，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，对于各个j，所述M_{1}，…，M_{j}是输入给了第j个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥。
8.如权利要求7所述的签名方法，其特征在于所述第1步骤之前有异或计算步骤，所述异或计算步骤中，计算出U＝H(T_{m})○u_{i_{m-1}}，所述H为散列函数，所述u_{i_{m-1}}是所述所输入的签名句，○为异或。
9.如权利要求8所述的签名方法，其特征在于所述第1步骤之前，具有密钥合法性检验步骤，在所述密钥合法性检验步骤中，确认pk_{i_{1}}，…，pk_{i_{m-1}}是否完全不同，但在m＝1的情况下，不进行任何确认。
10.如权利要求9所述的签名方法，其特征在于所述第1步骤之前，有对所输入的签名句进行检验的签名句检验步骤。
11.如权利要求8所述的签名方法，其特征在于所述第1步骤之前，具有对pk_{i_{1}}，…，pk_{i_{m-1}}是否完全不同进行确认的密钥合法性检验步骤，以及对所输入的签名句进行检验的签名句检验步骤。
12.如权利要求1～11中任一项所述的签名方法，其特征在于具有将所输入的初始值或签名句或他们的散列值作为辅助信息而生成并写入到所述存储介质中的步骤，并将所述辅助信息与签名句作为组输出。
13.一种签名方法，其特征在于，包括输入单元将初始值或其他多个签名装置顺次进行签名操作而生成的签名句u_{i_{m-1}}、以及输入给这些签名装置的消息M_{1}，…，M_{m-1}输入并保存到存储介质中的步骤；T_{m}计算单元从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，且将‖设为位列彼此的连接时，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中的步骤；异或计算单元在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算出U＝H(T_{m})○u_{i_{m-1}}，将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，并在设n_{i_{m}}为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出v＝U，并将计算结果保存到所述存储介质中的步骤；双向单射变换单元从所述存储介质读入必要的数据，在设κ为安全参数时，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第2变换单元从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，便计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中的步骤；以及输出单元从所述存储介质读入u_{i_{m}}并作为签名句而输出的步骤。
14.如权利要求13所述的签名方法，其特征在于具有由w设置单元在w_{i_{m}}＝u_{i_{m-1}}或设h为散列函数时，计算w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中的步骤，将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
15.一种检验方法，是一种检验多个签名装置顺次进行签名操作而生成的签名句u是否合法的检验装置中的检验方法，其特征在于当且仅当签名句u是如下内容时通过检验即所述所输出的签名句为，所述所输出的签名句的生成所涉及的签名装置已经在输入于各个签名装置中的所述消息中进行了签名；所述签名句u的位长，是不依赖于为了计算所述签名句u而涉及的所述签名句装置的数目的常数。
16.一种检验方法，是一种检验多个签名装置顺次进行签名操作而生成的签名句u是否合法的检验装置中的检验方法，其特征在于当且仅当生成签名句u的签名装置通过合法的方法生成了签名句u时通过检验，所述签名句u的位长，是不依赖于为了计算所述签名句u而涉及的所述签名句装置的数目的常数，且所述签名句u的检验，使用作为所述多个签名装置中最后1台执行签名操作之前的数据的辅助信息w来进行。
17.如权利要求15或16所述的检验方法，其特征在于检验签名句的操作具有第1与第2这两个步骤，所述第1步骤(h部分的操作)的计算中，使用带陷阱门的单向性置换，所述第2步骤(f部分的操作)的计算中，使用与所述第1步骤相比相同或不同的带陷阱门的单向性置换，在开始所述第1步骤与第2步骤时，从存储介质读出必要的数据，在所述第1步骤与第2步骤结束结束时，将计算结果写入到所述存储介质中。
18.如权利要求17所述的检验方法，其特征在于所述第1步骤中，如果针对所述第1步骤的输入是所述带陷阱门的单向性置换的定义域的元素，便通过所述带陷阱门的单向性置换对所述输入进行映射，如果不是则不进行任何操作，如果针对所述第2步骤的输入是所述带陷阱门的单向性置换的定义域的元素，便通过所述带陷阱门的单向性置换对所述输入进行映射，如果不是则不进行任何操作。
19.如权利要求18所述的检验方法，其特征在于所述第1步骤中所使用的所述带陷阱门的单向性置换的计算进一步由第1与第2子步骤构成，所述第1子步骤(g部分的操作)中，使用带陷阱门的单向性置换的函数，如果是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的函数对所述输入进行映射，如果不是则不进行任何操作，所述第2子步骤(φ部分的操作)中，计算签名句全体的空间上的双向单射，该双向单射能够通过多项式时间来计算，并且所述双向单射的反函数也能够通过多项式时间来计算，所述第1子步骤与所述第2子步骤的开始时，从所述存储介质读入必要的数据，所述第1子步骤与所述第2子步骤的结束时，将计算结果写入到所述存储介质中。
20.如权利要求19所述的检验方法，其特征在于所述第1步骤的所述第1子步骤中所使用的所述带陷阱门的单向性置换，与所述第2步骤中所使用的所述带陷阱门的单向性置换，是RSA函数。
21.如权利要求20所述的检验方法，其特征在于所述第1步骤的所述第2子步骤中所使用的所述双向单射，采用φ(x)＝x+n_i_{m}mod 2^{κ}，所述n_{i_{m}}是作为签名装置i_{m}的公开密钥的一部分的RSA模量，所述κ是安全参数。
22.如权利要求21所述的检验方法，其特征在于所述第2步骤之后有T_{j}计算步骤，所述T_{j}计算步骤中，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，这里，对各个j，所述M_{1}，…，M_{j}是输入在第j个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥。
23.如权利要求22所述的检验方法，其特征在于所述T_{j}计算步骤之后，具有如下那样的u计算步骤即将H设为散列函数，将U设为第2步骤的计算结果时，从所述存储介质读入必要的数据，而计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果存储到所述存储介质中。
24.如权利要求23所述的检验方法，其特征在于对j＝m-1，…，1，反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤。
25.如权利要求24所述的检验方法，其特征在于在对j＝m-1，…，1反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤之前，有密钥合法性检验步骤，所述密钥合法性检验步骤中，对pk_{i_{1}}，…，pk_{i_{m-1}}全部都不同进行确认，但在m＝1的情况下，不进行任何确认。
26.如权利要求25所述的检验方法，其特征在于在对j＝m-1，…，1反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤之后，存在u判断步骤，其中对作为检验结果是否得到了初始值进行判断。
27.如权利要求21所述的检验方法，其特征在于所述第1步骤之前有T_{m-1}计算步骤以及v″计算步骤，所述T_{m-1}计算步骤中，计算出T_{m-1}＝M_{1}|…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，这里，M_{1}，…，M_{m-1}是输入在第1，…，m-1个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥；所述v″计算步骤中，计算出v″＝H(T_{m-1})○u{i_{m-1}}，并且所述第1步骤将所述v”作为输入，且在所述第2步骤之后，存在判断所述第2步骤的计算结果是否与所述辅助信息相一致的u判断步骤。
28.一种检验方法，其特征在于，包括输入单元将由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、输入给这些签名装置的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}输入，并保存到存储介质中的步骤；J初始化单元将m-1设为变数j的步骤；第2变换单元，从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，便计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中的步骤；双向单射计算单元从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，如果v＜n_{i_{j}}便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中的步骤；每当将所述变量j减1时重复基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤直到所述变量j变为0的步骤；T_{j}计算单元从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}并将计算结果保存到所述存储介质中的步骤；u计算单元从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U并将计算结果保存到所述存储介质中的步骤；u判断单元从所述存储介质读入必要的数据，并判断u是否等于预先设定的初始值的步骤；以及输出单元在u等于预先设定的初始值的情况下输出表示检验成功的通知，否则便输出表示检验失败的通知的步骤。
29.一种检验方法，其特征在于，包括输入单元对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、前一个签名装置所输入的签名句或其散列值即辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中的步骤；T_{m-1}计算单元从所述存储介质读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中的步骤；v″计算单元从所述存储介质读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中的步骤；第2变换单元从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，便计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出v′＝v″，并将计算结果保存到所述存储介质中的步骤；双向单射计算单元从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，便计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中的步骤；u判断单元从所述存储介质读入必要的数据，并判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致的步骤；以及输出单元在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则，输出表示检验失败的通知的步骤。
30.一种签名装置，其特征在于，包括可读写的存储介质；输入单元，其对初始值或其他多个签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、以及输入在这些签名装置中的消息M_{1}，…，M_{m-1}进行输入，并保存到存储介质中；T_{m}计算单元，其从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，将‖设为位列彼此的连接时，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中；异或计算单元，其在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算出U＝H(T_{m})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，在将n_{i_{m}}设为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算v＝U，并将计算结果保存到所述存储介质中；双向单射变换单元，其从所述存储介质读入必要的数据，在将κ设为安全参数时，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，则计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中；以及输出单元，其从所述存储介质读入u_{i_{m}}，并作为签名句输出。
31.如权利要求30所述的签名装置，其特征在于具有w设置单元，其在w_{i_{m}}＝u_{i_{m-1}}，或者将h设为散列函数时，计算w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中；将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
32.一种检验装置，其特征在于，包括可读写的存储介质；输入单元，其对由其他的1个以上的签名装置顺次进行了签名操作而生成的签名句u_{i_{m-1}}、输入在些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；J初始化单元，其将m-1设置为变量j；第2变换单元，其从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{j}}，便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中；T_{j}计算单元，其每当将所述变量j减1时，重复执行了基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤之后，从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，并将计算结果保存到所述存储介质中；u计算单元，其从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，并判断u是否等于预先设定的初始值；以及输出单元，其在u等于预先设定的初始值情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
33.一种检验装置，其特征在于，包括可读写的存储介质；输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、作为前一个签名装置所输入的签名句或其散列值的辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}进行输入，并保存到存储介质中；T_{m-1}计算单元，其从所述存储介质读入必要的数据，计算T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中；v″计算单元，其从所述存储介质读入必要的数据，计算v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，则计算v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，否则计算出v′＝v″，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，则计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}modn_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致；以及输出单元，其在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
34.一种程序，让具有可读写的存储介质的计算机起到作为以下单元而发挥功能输入单元，其对初始值或其他多个签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、以及输入在这些签名装置中的消息M_{1}，…，M_{m-1}进行输入，并保存到存储介质中；T_{m}计算单元，其从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，将‖设为位列彼此的连接时，计算T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中；异或计算单元，其在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算U＝H(T_{m})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，在将n_{i_{m}}设为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出v＝U，并将计算结果保存到所述存储介质中；双向单射变换单元，其从所述存储介质读入必要的数据，在将κ设为安全参数时，计算v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，便计算u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中；以及输出单元，其从所述存储介质读入u_{i_{m}}，并作为签名句输出。
35.如权利要求34所述的程序，其特征在于让所述计算机进一步起到作为w设置单元而发挥功能，所述w设置单元在w_{i_{m}}＝u_{i_{m-1}}，或将h设为散列函数时，计算出w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中，并且将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
36.一种程序，让具有可读写的存储介质的计算机作为以下单元而发挥功能输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、输入给这些签名装置的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；J初始化单元，其将m-1设为变量j；第2变换单元，其从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，便计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{j}，便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中；T_{j}计算单元，其在每当将所述变量j减1时，重复执行了基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤之后，从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，并将计算结果保存到所述存储介质中；u计算单元，其从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u是否等于预先设定的初始值；以及输出单元，其在u＝预先设定的初始值的情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
37.一种程序，让具有可读写的存储介质的计算机起到作为以下单元的功能输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、作为前一个签名装置所输入的签名句或其散列值的辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；T_{m-1}计算单元，其从所述存储介质读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中；v″计算单元，其从所述存储介质读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，则计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出v′＝v″，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，便计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}modn_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致；以及输出单元，其在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则，便输出表示检验失败的通知。
38.一种签名装置，至少包括如下那样的单元即在输入了初始值或其他多个签名装置顺次进行签名操作所生成的签名句、以及输入在所述签名装置的消息的情况下，计算出将所述消息与本装置的公开密钥以及已经签名过的签名装置的公开密钥连接起来的结果，并导出所述连接结果的散列值与所述签名句的异或值，其特征在于，还具有第1单元，其在所述异或值超过了所述签名装置的公开密钥的一部分即RSA模量的情况下，直接输出所述异或值，在没有超过的情况下，输出所述异或中进行了以RSA签名为准据的签名之后的结果；第2单元，其对所述第1单元的输出，作用向大至所述RSA模量的方向映射的函数；以及第3变换单元，其在所述第2单元中的运算结果超过了所述RSA模量的情况下，直接输出所述双向单射单元中的运算结果，在没有超过的情况下，输出在所述第2单元的运算结果中进行了以RSA签名为准据的签名之后的结果。
39.一种检验装置，是一种对多个权利要求38中所述的签名装置顺次进行签名操作而生成的签名句是否合法进行检验的检验装置，包括每当检验各个签名装置中的签名时在所述签名句超过了对应的签名装置的RSA模量的情况下，直接输出，在没有超过的情况下，输出进行了以RSA签名为准据之后的结果的第4单元；第5单元，其对所述第4单元的输出，作用向小至所述RSA模量的方向映射的函数；第6单元，其在所述第5单元的输出超过了所述RSA模量的情况下，直接输出所述第5单元的输出，在没有超过的情况下，输出在所述第5单元的输出中进行了以RSA签名为准据的签名之后的结果；以及第7单元，其对输入给所述签名装置的消息、连接本装置的公开密钥和已经签名过的签名装置的公开密钥的结果的散列值、以及所述第6单元的输出之间的异或值，进行求算；根据对各个所述签名装置的基于所述第7单元的输出结果，判断检验的成功、失败。
全文摘要
本发明提供一种在多个签名装置进行签名的情况下的签名长度不依赖于签名装置的数目的RSA签名方法。签名装置i_{m}，具有在所输入的签名句u_{i_{m－1}}超过了模量n_{i_{m}}的情况下，不进行任何操作，在超过了的情况下，进行以RSA方式为准据的签名的第1变换单元(SS1B105)；对该结果作用向大至模量n_{i_{m}}的方向进行映射的函数的双向单射变换单元(S1B106)；在该操作结果超过了模量n_{i_{m}}的情况下，不进行任何操作，在没有超过的情况下，进行以RSA方式为准据的签名的第2变换单元(S1B107)；以及将该操作结果作为签名句u_{i_{m}}输出的输出单元(S1B109)。
文档编号G09C1/00GK101069381SQ20058004097
公开日2007年11月7日 申请日期2005年11月11日 优先权日2004年11月29日
发明者寺西勇, 佐古和惠, 田口大悟, 野田润 申请人:日本电气株式会社
技术领域：
本发明涉及一种签名与检验方法以及签名与检验装置，特别是一种在多个签名装置进行签名的状况下的、签名长度不依赖于签名装置数目的、签名与检验方法以及签名与检验装置。
背景技术：
伴随着计算机与互联网环境的普及，电子发送接收消息的机会也在增加。这种情况下，为了防止在发送消息的过程中消息被篡改，希望在消息中添加电子签名。
但是在使用称作RSA或DSA的公知的签名方式，由多个签名装置进行了签名的情况下，为了表示全体都已进行了签名，需要由全签名装置分别生成签名句，并将这些签名句都保存起来。因此，签名句的数据长度的合计值与签名装置的台数成比例，在签名装置数目较多的情况下，效率不高。
作为解决这样的问题的签名方式之一，提出了非专利文献1中所述的签名方式。图11中示出了该以往的签名方式的顺序。
另外，本说明书中所使用的签名的意义，这里进行了定义。“‖”表示位列彼此的连接。“○”表示每一位的“异或”。“^”表示以右边的被算符为指数计算出左边的被算符的幂的算数算符。例如，f^{-1}为f-1。「_{x}」表示x为脚标。例如，u_{i}为ui。
参照图11，一旦输入了成为签名对象的签名文字u_{i_{m-1}}(S3F100)，便在进行了所具有的密钥的合法性检验(S3F101)与签名句u_{i_{m-1}}的合法性的检验(S3F102)之后，计算出将本签名装置的公开密钥与已经签名了的签名装置的公开密钥连接起来的T_{m}(S3F103)。接下来，计算出T_{m}的散列值与签名句u_{i_{m-1}}的异或U(S3F104)，设U的位列中第一个安全参数k位为a，剩下的为s(S3F105)。接下来，比较a与本签名装置的RSA模量n_{i_{m}}(S3F106)，在a小于RSA模量n_{i_{m}}时，通过秘密密钥d_{i_{m}}对a计算出以RSA方式为准据的签名句u_{i_{m}}(S3F107)，并输出(S3F109)。此时给s添加1位的信息0作为控制信息。另外，在a大于RSA模量n_{i_{m}}时，对于大于模量的数，由于无法计算RSA签名，因此对将a减去了n_{i_{m}}之后的值计算出签名句u_{i_{m}}(S3F108)并输出(S3F109))。此时给s添加1位的信息1作为控制信息。
这样，在RSA的情况下，对于大于签名装置的RSA模量n_{i_{m}}的数，由于无法计算签名，因此基于非专利文献1的以往技术中，在较大的情况下，减去模量n_{i_{m}}之后再添加签名。此时，为了之后的检验能够进行，在其后添加1bit的控制信息(超过了模量的情况下添加1，此外添加0)。签名句u_{i_{m}}的检验时，使用与签顺序与相反的顺序对签名装置的公开密钥反复进行检验，最终追溯到得到预定的初始值，通过这样，判断是正确的签名。
非专利文献1Anna Lysyanskaya，Silvio Micali，Leonid Reyzin，HovavShacham.Sequential Aggregate Signatures from Trapdoor Permutations.InAdvances in Cryptology--EUROCRYPT 2004，vol.3027 of LNCS，pp.74-90.Springer-Verlag，2004.
根据非专利文献1中所述的以前的签名方式，由于即使多个签名装置顺次进行签名，签名句的数据长度的合计值也不与签名装置的台数成比例，因此在存储签名句的情况下，能够削减存储量，在进行通信的情况下，能够削减通信量。但是，存在如下问题即签名长为固定值+签名次数，存在如果签名次数增加，签名长度也稍有延长。
发明内容
本发明的目的在于，改善所述以前的签名方式所具有的问题点，使得签名长度与签名装置的数目无关，为一定值。
本发明第1项涉及一种签名方法，是一种将初始值或其他多个签名装置顺次进行签名操作所生成的签名句、消息、以及本签名装置的秘密密钥作为输入，输出与输入相同长度的签名句的签名装置的签名方法，其特征在于所述所输出的签名句，表示该所述所输出的签名句的生成所述涉及的签名装置，在输入到了各个签名装置的所述消息中，已经进行了签名。
本发明第2项所涉及的签名方法的特征在于，在本发明第1项所记载的签名方法中，计算签名句的操作具有第1与第2这两个步骤，所述第1步骤(f^{-1}部分的操作)的计算中，使用带陷阱门的单向性置换的反函数，所述第2步骤(h^{-1}部分的操作)的计算中，使用与所述第1步骤相比相同或不同的带陷阱门的单向性置换的反函数，如果所述第1步骤结束，便将计算结果存储到存储介质中，在所述第2步骤开始时，从所述存储介质读出必要的数据，如果所述第2步骤结束，便将计算结果存储到所述存储介质中。
本发明第3项所涉及的签名方法的特征在于，在本发明第2项所记载的签名方法中，在所述第1步骤中，如果针对所述第1步骤的输入是所述带陷阱门的单向性置换的值域的元素，便通过该所述带陷阱门的单向性置换的反函数对所述输入进行映射，如果不是则不进行任何操作，如果针对所述第2步骤的输入是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的反函数对所述输入进行映射，如果不是则不进行任何操作。
本发明第4项所涉及的签名方法的特征在于，在本发明第3项所记载的签名方法中，所述第2步骤中所使用的所述带陷阱门的单向性置换的计算进一步由第1与第2子步骤构成，所述第1子步骤(φ^{-1}部分的操作)中，计算签名句全体的空间上的双向单射，该双向单射能够通过多项式时间来计算，并且所述双向单射的反函数也能够通过多项式时间来计算，在所述第2子步骤(g^{-1}部分的操作)中使用带陷阱门的单向性置换的反函数，如果是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的反函数对所述输入映射，如果不是则不进行任何操作，所述第1子步骤与所述第2子步骤的开始时，从所述存储介质读入必要的数据，所述第1子步骤与所述第2子步骤的结束时，将计算结果写入到所述存储介质中。
本发明第5项所涉及的签名方法的特征在于，在本发明第4项所记载的签名方法中，所述第1步骤中所使用的所述带陷阱门的单向性置换，与所述第2步骤的所述第2子步骤中所使用的所述带陷阱门的单向性置换，是RSA函数。
本发明第6项所涉及的签名方法的特征在于，在本发明第5项所记载的签名方法中，所述第2步骤的所述第1子步骤中所使用的所述双向单射，采用φ(x)＝x-n_{i_{m}}mod2^{κ}，所述n_{i_{m}}是作为签名装置i_{m}的公开密钥的一部分的RSA模量，所述κ是安全参数。
本发明第7项所涉及的签名方法的特征在于，在本发明第6项所记载的签名方法中，所述第1步骤之前有T_{m}计算步骤，所述T_{m}计算步骤中，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，对于各个j，所述M_{1}，…，M_{j}是输入给了第j个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥。
本发明第8项所涉及的签名方法的特征在于，在本发明第7项所记载的签名方法中，所述第1步骤之前有异或计算步骤，在所述异或计算步骤中，计算出U＝H(T_{m})○u_{i_{m-1}}，所述H为散列函数，所述u_{i_{m-1}}是所述所输入的签名句，○为异或。
本发明第9项所涉及的签名方法的特征在于，在本发明第8项所记载的签名方法中，所述第1步骤之前，具有密钥合法性检验步骤，在所述密钥合法性检验步骤中，确认pk_{i_{1}}，…，pk_{i_{m-1}}是否完全不同，但在m＝1的情况下，不进行任何确认。
本发明第10项所涉及的签名方法的特征在于，在本发明第9项所记载的签名方法中，所述第1步骤之前，有对所输入的签名句进行检验的签名句检验步骤。
本发明第11项所涉及的签名方法的特征在于，在本发明第2项所记载的签名方法中，所述第1步骤之前，具有对pk_{i_{1}}，…，pk_{i_{m-1}}是否完全不同进行确认的密钥合法性检验步骤，以及对所输入的签名句进行检验的签名句检验步骤。
本发明第12项所涉及的签名方法的特征在于，在本发明第1～11的任一项所记载的签名方法中，具有将所输入的初始值或签名句或他们的散列值作为辅助信息而生成并写入到所述存储介质中的步骤，并将所述辅助信息与签名句作为组输出。
本发明第13项涉及一种签名方法，其特征在于，包括输入单元将初始值或其他多个签名装置顺次进行签名操作而生成的签名句u_{i_{m-1}}、以及输入给这些签名装置的消息M_{1}，…，M_{m-1}输入并保存到存储介质中的步骤；T_{m}计算单元从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，且将‖设为位列彼此的连接时，计算出T_{m}＝M_{1}‖…‖M_{m}‖pK_{i_{1}}‖…‖pk_{i_k_{i_{m}}，并将计算结果保存到所述存储介质中的步骤；异或计算单元在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算出U＝H(T_{m})○u_{i_{m-1}}，将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，并在设n{i{m}}为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出v＝U，并将计算结果保存到所述存储介质中的步骤；双向单射变换单元从所述存储介质读入必要的数据，在设κ为安全参数时，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第2变换单元从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，便计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中的步骤；以及输出单元从所述存储介质读入u_{i_{m}}并作为签名句而输出的步骤。
本发明第14项所涉及的签名方法的特征在于，在本发明第13项所记载的签名方法中，具有由w设置单元在w_{i_{m}}＝u_{i_{m-1}}或设h为散列函数时，计算w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中的步骤，将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
本发明第15项涉及一种检验方法，是一种检验多个签名装置顺次进行签名操作而生成的签名句u是否合法的检验装置的检验方法，其特征在于当且仅当签名句u为，所述所输出的签名句表示，所述所输出的签名句的生成所涉及的签名装置已经在输入在各个签名装置中的所述消息中进行了签名时，通过检验；所述签名句u的位长，是不依赖于为了计算所述签名句u而涉及的所述签名句装置的数目的常数。
本发明第16项涉及一种检验方法，是一种检验多个签名装置顺次进行签名操作而生成的签名句u是否合法的检验装置中的检验方法，其特征在于当且仅当生成签名句u的签名装置通过合法的方法生成了签名句u时通过检验，所述签名句u的位长，是不依赖于为了计算所述签名句u而涉及的所述签名句装置的数目的常数，且所述签名句u的检验，使用作为所述多个签名装置中最后1台执行签名操作之前的数据的辅助信息w来进行。
本发明第17项所涉及的检验方法的特征在于，在本发明第15或16项所记载的签名方法中，检验签名句的操作具有第1与第2这两个步骤，所述第1步骤(h部分的操作)的计算中，使用带陷阱门的单向性置换，所述第2步骤(f部分的操作)的计算中，使用与所述第1步骤相比相同或不同的带陷阱门的单向性置换，在开始所述第1步骤与第2步骤时，从存储介质读出必要的数据，在所述第1步骤与第2步骤结束结束时，将计算结果写入到所述存储介质中。
本发明第18项所涉及的检验方法的特征在于，在本发明第17项所记载的签名方法中，所述第1步骤中，如果针对所述第1步骤的输入是所述带陷阱门的单向性置换的定义域的元素，便通过所述带陷阱门的单向性置换对所述输入进行映射，如果不是则不进行任何操作，如果针对所述第2步骤的输入是所述带陷阱门的单向性置换的定义域的元素，便通过所述带陷阱门的单向性置换对所述输入进行映射，如果不是则不进行任何操作。
本发明第19项所涉及的检验方法的特征在于，在本发明第18项所记载的签名方法中，所述第1步骤中所使用的所述带陷阱门的单向性置换的计算进一步由第1与第2子步骤构成，所述第1子步骤(g部分的操作)中，使用带陷阱门的单向性置换的函数，如果是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的函数对所述输入进行映射，如果不是则不进行任何操作，所述第2子步骤(φ部分的操作)中，计算签名句全体的空间上的双向单射，该双向单射能够通过多项式时间来计算，并且所述双向单射的反函数也能够通过多项式时间来计算，所述第1子步骤与所述第2子步骤的开始时，从所述存储介质读入必要的数据，所述第1子步骤与所述第2子步骤的结束时，将计算结果写入到所述存储介质中。
本发明第20项所涉及的检验方法的特征在于，在本发明第19项所记载的签名方法中，所述第1步骤的所述第1子步骤中所使用的所述带陷阱门的单向性置换，与所述第2步骤中所使用的所述带陷阱门的单向性置换，是RSA函数。
本发明第21项所涉及的检验方法的特征在于，在本发明第20项所记载的签名方法中，所述第1步骤的所述第2子步骤中所使用的所述双向单射，采用φ(x)＝x+n_i_{m}mod 2^{κ}，所述n_{i_{m}}是作为签名装置i_{m}的公开密钥的一部分的RSA模量，所述κ是安全参数。
本发明第22项所涉及的检验方法的特征在于，在本发明第21项所记载的签名方法中，所述第2步骤之后有T_{j}计算步骤，所述T_{j}计算步骤中，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，这里，对各个j，所述M_{1}，…，M_{j}是输入在第j个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥。
本发明第23项所涉及的检验方法的特征在于，在本发明第22项所记载的签名方法中，所述T_{j}计算步骤之后，具有如下那样的u计算步骤即将H设为散列函数，将U设为第2步骤的计算结果时，从所述存储介质读入必要的数据，而计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果存储到所述存储介质中。
本发明第24项所涉及的检验方法的特征在于，在本发明第23项所记载的签名方法中，对j＝m-1，…，1，反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤。
本发明第25项所涉及的检验方法的特征在于，在本发明第24项所记载的签名方法中，在对j＝m-1，…，1反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤之前，有密钥合法性检验步骤，所述密钥合法性检验步骤中，对pk_{i_{1}}，…，pk_{i_{m-1}}全部都不同进行确认，但在m＝1的情况下，不进行任何确认。
本发明第26项所涉及的检验方法的特征在于，在本发明第25项所记载的签名方法中，在对j＝m-1，…，1反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤之后，存在u判断步骤，其中对作为检验结果是否得到了初始值进行判断。
本发明第27项所涉及的检验方法的特征在于，在本发明第2项所记载的签名方法中，所述第1步骤之前有T_{m-1}计算步骤以及v″计算步骤，所述T_{m-1}计算步骤中，计算出T_{m-1}＝M_{1}|…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，这里，M_{1}，…，M_{m-1}是输入在第1，…，m-1个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥；所述v″计算步骤中，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并且所述第1步骤将所述v”作为输入，在所述第2步骤之后，存在判断所述第2步骤的计算结果是否与所述辅助信息相一致的u判断步骤。
本发明第28项涉及一种检验方法，其特征在于，包括输入单元将由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、输入给这些签名装置的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}输入，并保存到存储介质中的步骤；J初始化单元将m-1设为变数j的步骤；第2变换单元，从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，便计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中的步骤；双向单射计算单元从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，如果v＜n_{i_{j}}便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中的步骤；每当将所述变量j减1时重复基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤直到所述变量j变为0的步骤；T{j}计算单元从所述存储介质读入必要的数据，计算出T_{j}＝M{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}并将计算结果保存到所述存储介质中的步骤；u计算单元从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U并将计算结果保存到所述存储介质中的步骤；u判断单元从所述存储介质读入必要的数据，并判断u是否等于预先设定的初始值的步骤；以及输出单元在u等于预先设定的初始值的情况下输出表示检验成功的通知，否则便输出表示检验失败的通知的步骤。
本发明第29项涉及一种检验方法，其特征在于，包括输入单元对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、前一个签名装置所输入的签名句或其散列值即辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中的步骤；T_{m-1}计算单元从所述存储介质读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中的步骤；v″计算单元从所述存储介质读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中的步骤；第2变换单元从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，便计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出v′＝v″，并将计算结果保存到所述存储介质中的步骤；双向单射计算单元从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，便计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中的步骤；u判断单元从所述存储介质读入必要的数据，并判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致的步骤；以及输出单元在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则，输出表示检验失败的通知的步骤。
本发明第30项涉及一种签名装置，其特征在于，包括可读写的存储介质；输入单元，其对初始值或其他多个签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、以及输入在这些签名装置中的消息M_{1}，…，M_{m-1}进行输入，并保存到存储介质中；T_{m}计算单元，其从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，将‖设为位列彼此的连接时，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中；异或计算单元，其在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算出U＝H(T_{m})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，在将n_{i_{m}}设为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算v＝U，并将计算结果保存到所述存储介质中；双向单射变换单元，其从所述存储介质读入必要的数据，在将κ设为安全参数时，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，则计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中；以及输出单元，其从所述存储介质读入u_{i_{m}}，并作为签名句输出。
本发明第31项所涉及的签名装置的特征在于，在本发明第30项所记载的签名方法中，具有w设置单元，其在w_{i_{m}}＝u_{i_{m-1}}，或者将h设为散列函数时，计算w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中；将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
本发明第32项涉及一种检验装置，其特征在于，包括可读写的存储介质；输入单元，其对由其他的1个以上的签名装置顺次进行了签名操作而生成的签名句u_{i_{m-1}}、输入在些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；J初始化单元，其将m-1设置为变量j；第2变换单元，其从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{j}}，便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中；T{j}计算单元，其每当将所述变量j减1时，重复执行了基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤之后，从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，并将计算结果保存到所述存储介质中；u计算单元，其从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，并判断u是否等于预先设定的初始值；以及输出单元，其在u等于预先设定的初始值情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
本发明第33项涉及一种检验装置，其特征在于，包括可读写的存储介质；输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、作为前一个签名装置所输入的签名句或其散列值的辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}进行输入，并保存到存储介质中；T_{m-1}计算单元，其从所述存储介质读入必要的数据，计算T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中；v″计算单元，其从所述存储介质读入必要的数据，计算v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，则计算v′＝v″^{e_{i_{m-1}}}modn_{i_{m-1}}，否则计算出v′＝v″，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，则计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致；以及输出单元，其在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
本发明第34项涉及一种程序，让具有可读写的存储介质的计算机起到作为以下单元而发挥功能输入单元，其对初始值或其他多个签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、以及输入在这些签名装置中的消息M_{1}，…，M_{m-1}进行输入，并保存到存储介质中；T_{m}计算单元，其从所述存储介质以及公开密钥存储装置读入必要的数据，在将pK_{i_{j}}设为签名装置i_{j}的公开密钥，将‖设为位列彼此的连接时，计算T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中；异或计算单元，其在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算U＝H(T_{m})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，在将n_{i_{m}}设为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出v＝U，并将计算结果保存到所述存储介质中；双向单射变换单元，其从所述存储介质读入必要的数据，在将κ设为安全参数时，计算v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，便计算u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中；以及输出单元，其从所述存储介质读入u_{i_{m}}，并作为签名句输出。
本发明第35项所涉及的程序的特征在于，在本发明第34项所记载的签名方法中，让所述计算机进一步起到作为w设置单元而发挥功能，所述w设置单元在w_{i_{m}}＝u_{i_{m-1}}，或将h设为散列函数时，计算出w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中，并且将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
本发明第36项涉及一种程序，让具有可写入的存储介质的计算机作为以下单元而发挥功能输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、输入给这些签名装置的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；J初始化单元，其将m-1设为变量j；第2变换单元，其从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，便计算出v′＝u_{i_{j}}^{e_{i_{j}}}modn_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{j}}，便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中；T_{j}计算单元，其在每当将所述变量j减1时，重复执行了基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤之后，从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，并将计算结果保存到所述存储介质中；u计算单元，其从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u是否等于预先设定的初始值；以及输出单元，其在u＝预先设定的初始值的情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
本发明第37项涉及一种程序，让具有可读写的存储介质的计算机起到作为以下单元的功能输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、作为前一个签名装置所输入的签名句或其散列值的辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；T_{m-1}计算单元，其从所述存储介质读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中；v″计算单元，其从所述存储介质读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，则计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出v′＝v″，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，便计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}modn_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致；以及输出单元，其在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则，便输出表示检验失败的通知。
本发明中，在签名装置i_{m}中进行在所输入的签名句u_{i_{m-1}}超过了模量n_{i_{m}}的情况下，不进行任何操作，在没有超过的情况下，进行以RSA签名为准据的签名的第1操作；对第1操作的结果，作用向大至模量n_{i_{m}}的方向映射的函数的第2操作；以及在该第2操作的结果超过了模量n_{i_{m}}的情况下，不进行任何操作，在没有超过的情况下，进行以RSA签名为准据的签名的第3操作。这里，如果设各个签名装置的RSA模量的位长与安全参数κ相等，签名句u_{i_{m-1}}以及签名装置i_{m}的模量n_{i_{m}}就变为小于2^{κ}的数。第1操作中，对取0～n_{i_{m}}的值的签名句u_{i_{m-1}}，进行以RSA签名为准据的签名，因此第1操作之后的值变为0～n_{i_{m}}，另外，对于取n_{i_{m}}～2^{κ}的值的签名句u_{i_{m-1}}，不进行任何操作，因此第1操作之后的值变为n_{i_{m}}～2^{κ}。另外，第2操作中，进行从第1操作之后的值向以2^{κ}为模量的n_{i_{m}}的加法，因此第2操作之后的值也变为小于2^{κ}的数，但第1操作之后的值为n_{i_{m}}～2^{κ}者，在第2操作之后变为0～n_{i_{m}}。因此，第3操作中，对第2操作之后的值变为0～n_{i_{m}}者进行以RSA签名为准据的签名，由此对任意值的签名句u_{i_{m-1}}，至少都进行1次RSA签名。另外，第3操作之后的值，也即签名值u_{i_{m}}的值与所输入的签名句u_{i_{m-1}}的值一一对应，因此根据签名值u_{i_{m}}的值，能够唯一决定所实施的签名操作，从而不需要添加非专利文献1中那样的控制位。
第1效果是，签名长度不依赖于签名装置的数目。其原因是，签名前的数据与签名后所生成的数据位数不变。
第2效果是，能够在每次签名时变更签名装置的顺序。其原因与第1效果的情况下相同，签名前的数据与签名后所生成的数据位数不变。因此，对各个签名装置的输入是一定的，跟该签名装置是第几个进行签名的无关，因此不管是第几个，都能够通过相同的操作来签名。
第3效果是，与签名装置勾结的攻击者，无法伪造出从线路中的“诚实honest”的签名装置中通过的签名句。其原因在于，不管对签名装置的输入u是什么，签名时最多进行两次的RSA计算中的至少一方的u不变。
第4效果是，在系统使用的开始阶段，不需要知道签名装置的数目m，即使签名装置的数目m在使用中动态变化，也能够正常使用。其原因是，签名装置的数目为m+1台时的签名顺序，是在进行了签名装置的数目为m台时的签名顺序之后再进行一次同样的签名操作，签名的操作方法不依赖于签名装置的数目m。
图1为本发明的第1实施方式的方框图。
图2为表示本发明的第1实施方式中的签名装置之构成的方框图。
图3为表示本发明的第1实施方式中的签名装置之动作的流程图。
图4为表示本发明的第1实施方式中的检验装置之构成的方框图。
图5为表示本发明的第1实施方式中的检验装置之动作的流程图。
图6为本发明的第2实施方式的方框图。
图7为表示本发明的第2实施方式中的签名装置之构成的方框图。
图8为表示本发明的第2实施方式中的签名装置之动作的流程图。
图9为表示本发明的第2实施方式中的检验装置之构成的方框图。
图10为表示本发明的第2实施方式中的检验装置之动作的流程图。
图11为表示以前的签名装置之动作的流程图。
图中i_{1}，…，i_{m-1}-签名装置，i_{1}-2，…，i_{m-1}-2-检验装置，i_{1}-3，…，i_{m-1}-3-密钥存储装置，i_{1}-4，…，i_{m-1}-4-密钥合法性检验装置，i_{1}-5，…，i_{m-1}-5-密钥生成装置，M_{1}，…，M_{m}-消息，
u_{i_{0}}，…，u_{i_{m-1}}-签名句，w_{i_{0}}，…，w_{i_{m-1}}-辅助信息。
具体实施例方式
<第1实施方式>
对照图1，本发明的第1实施方式，由签名装置i_{1}，…，i_{m}、检验装置i_{1}-2，…，i_{m-1}-2、公开密钥存储装置i_{1}-3，…，i_{m-1}-3、密钥合法性检验装置i_{1}-4，…，i_{m}-4、以及秘密密钥存储装置i_{1}-5，…，i_{m-1}-5构成。
参照图2，签名装置i_{m}由输入单元S1B100、T_{m}计算单元S1B103、异或计算单元S1B104、第一变换单元S1B105、双向单射变换单元S1B106、第二变换单元S1B107、存储介质S1B108、以及输出单元S1B109构成，其他的签名装置也具有与签名装置i_{m}相同的构成。
参照图4，检验装置i_{m}-2由输入单元V1B100、j初始化单元V1B102、j判断单元V1B103、第二变换单元V1B104、双向单射变换单元V1B105、第一变换单元V1B106、T_{j}计算单元V1B107、u计算单元V1B108、j减少单元V1B109、存储介质V1B1010、u判断单元V1B1011、accept输出单元V1B1012、以及reject输出单元V1B1013构成。其他检验装置也具有与检验装置i_{m}-2相同的构成。
对本实施方式进行概述。首先，给签名装置i_{1}输入签名装置i_{1}的公开密钥秘密密钥对、初始值u_{i_{0}}、以及消息M_{1}。签名装置i_{1}使用u_{i_{0}}生成对消息M_{1}的签名句u_{i_{1}}。之后，顺次给签名装置i_{j}输入签名装置i_{j}的公开密钥秘密密钥对、前一个签名装置所输出的签名句u_{i_{j-1}}、以及消息M_{j}，签名装置i_{j}使用这些生成签名句u_{i_{j}}。签名句u_{i_{j}}是表示签名装置i_{1}在消息M_{1}中进行了签名，签名装置i_{2}在消息M_{2}中进行了签名，…、签名装置i_{j}在消息M_{j}中进行了签名的数据。
对各个j，给检验装置i_{j}输入签名装置i_{1}，…，i_{j}的公开密钥与消息M_{1}，…，M_{j-1}，以及签名句u_{i_{j-1}}。于是，检验装置i_{j}对签名句u_{i_{j-1}}是否是使用签名装置i_{1}，…，i_{j-1}的秘密密钥，且针对消息M_{1}，…，M_{j-1}所生成的签名句进行检验。
本实施方式的系统目标是，生成签名句u_{i_{m}}即对签名装置i_{1}在消息M_{1}中进行了签名，签名装置i_{2}在消息M_{2}中进行了签名，…，签名装置i_{m}在消息M_{m}中进行了签名进行表示的数据。
另外，本实施方式系统的应用开始阶段，不需要知道签名装置的数目m。签名装置的数目m可以在应用中动态变化。另外，签名装置i{1}，…，i_{m}的动作完全相同。检验装置、公开密钥存储装置、密钥合法性检验装置、秘密密钥存储装置也基本都进行相同的动作。
接下来对本实施方式进行详细说明。
签名装置i_{j}的公开密钥pk_{i}、秘密密钥sk_{i}分别为(n_{i}，e_{i})、(p_{i_{j}}，q_{i_{j}}，d_{i_{j}})，满足下面的5个性质。
1.p_{i_{j}}，q_{i_{j}}为质数。
2.n_{i_{j}}＝p_{i_{j}}q_{i_{j}}3.n_{i_{j}}的位长等于安全参数κ。
4.p_{i_{j}}，q_{i_{j}}的位长为相同程度。
5.e_{i_{j}}与Φ(n_{i})互为质数。
6.d_{i_{j}}＝e_{i_{j}}-1 mod Φ(n_{i})其中，这里Φ(n_{i})为1以上不满n_{i}且与n_{i}互为质数的整数的个数。生成满足该性质(pk_{i}，(sk_{i})的方法，例如记载在非专利文献2「Alfred J.Menezes Paul C.van Oorschot，and Scott A.Vanstone.Handbookof Applied Cryptography.CRC Press.」(http//www.cacr.math.uwaterloo.ca/hac/)中。
从安全性的观点来说，最好能够均对e_{i_{j}}是否与Φ(n_{i})互为质数进行确认。作为能够进行该确认的方法，有使e_{i_{j}}为比n_{i}大的质数的方法。但e_{i}}不一定必须满足该性质。
对各个j＝1，…，m，秘密密钥存储装置i_{j}-5存储秘密密钥sk_{i_{j}}，公开密钥存储装置i_{j}-3存储公开密钥pk_{1}，…，pk_{m}。
对密钥合法性检验装置i_{m}-4的动作进行说明。密钥合法性检验装置i_{m}-4是确认公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}的合法性的装置。为了确认合法性，首先，从密钥存储装置i_{m}-3读入pk_{i_{1}}，…，pk_{i_{m-1}}，确认pk_{i_{1}}，…，pk_{i_{m-1}}全部都不同。但在m＝1的情况下，不进行确认。
从安全性的观点出发，希望也对e_{i_{j}}与Φ(n_{i})互为质数进行确认，但也可以省略该确认。
对签名装置i_{m}的动作进行说明。对照图2、图3，对如下方法进行说明将消息M_{1}，…，M_{m}以及由签名装置i_{1}，…，i_{m-1}使用公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}所生成的针对消息M_{1}，…，M_{m-1}的签名句u_{i_{m-1}}，输入给了签名装置i_{m}时，签名装置i_{m}在消息M_{m}中进行签名。
签名装置i_{m}首先通过输入单元S1B101，读入M_{1}，…，M_{m}、pk_{i_{1}}，…，pk_{i_{m}}、sk_{i_{m}}、u_{i_{m-1}}，并存储到存储介质S1B108中(S1F100)。其中，在m＝1的情况下，满足u_{i_{0}}＝0。
接下来，签名装置i_{m}将u_{i_{m-1}}、M_{1}，…，M_{m-1}、pk_{i_{1}}，…，pk_{i_{m-1}}发送给检验装置i_{m}-2。检验装置i_{m}-2检验签名句u_{i{m-1}}的合法性(S1B101，S1F102)。此时，检验装置i_{m}-2将pk_{i_{1}}，…，pk_{i_{m-1}}发送给密钥合法性检验装置i_{m}-4。密钥合法性检验装置i_{m}-4对密钥的合法性进行检验(S1B102，S1F101)。设在m＝1的情况下，只确认出u_{i_{0}}＝0。
从安全性的观点来说，希望进行所述u_{i_{m-1}}的检验与密钥合法性检验，但为了实现高效化，可以省略其中一方或双方的操作。
接下来，签名装置i_{m}通过T_{m}计算单元S1B103，从存储介质S1B108读入必要的数据，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}(S1F103)。一旦计算结束，T_{m}计算单元S1B103便在存储介质S1B108中写入T_{m}。
接下来，签名装置i_{m}通过异或单元S1B104，从存储介质S1B108读入必要的数据，计算U＝H_(T_{m})○u_{i_{m-1}}，并将计算结果存储到存储介质S1B108中(S1F104)。这里，H为输出与所输入的位数相同的散列(hash)值的散列函数。
接下来，签名装置i_{m}通过第一变换单元S1B105，从存储介质S1B108读入输入给签名装置i_{m}的数据，首先判断U是否小于n_{i_{m}}(S1F105)。如果U＜n_{i_{m}}，签名装置i_{m}便通过第一变换单元S1B105计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，并将计算结果写入到存储介质S1B108中(S1F106)。反之，如果U≥n_{i_{m}}，签名装置i_{m}便通过第一变换单元S1B105，设为v＝u，将计算结果写入到存储介质S1B108中(S1F107)。
接下来，签名装置i_{m}通过双向单射变换单元S1B106，从存储介质S1B108读入必要的数据，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果写入到存储介质S1B108中(S1F108)。
接下来，签名装置i_{m}通过第二变换单元S1B107，从存储介质S1B108读入必要的数据，判断v′是否小于n_{i_{m}}(S1F109)。如果v′＜n_{i_{m}}，签名装置i_{m}便通过第二变换单元S1B107，计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，并将计算结果写入到存储介质S1B108中(S1F1010)。反之，如果v′≥n_{i_{m}}，签名装置i_{m}便通过第二变换单元S1B107计算出u_{i_{m}}＝v′，将计算结果写入到存储介质S1B108中(S1F1011)。
最后，签名装置i_{m}通过输出单元S1B109，从存储介质S1B108读入u_{i_{m}}并输出(S1F1012)。
这样，签名装置i_{m}判断所输入的签名句u_{i_{m-1}}是否超过了模量n_{i_{m}}，在超过了的情况下，不进行操作，在没有超过的情况下，执行进行以RSA方式为准据的签名的第1操作，对该第1操作的结果执行对其作用向大至模量n_{i_{m}}的方向映射的函数的第2操作，判断该第2操作的结果是否超过了模量n_{i_{m}}，在超过了的情况下，不进行操作，在没有超过的情况下，执行进行以RSA方式为准据的签名的第3操作。根据签名句u_{i_{m-1}}的值，存在RSA签名被实施两次的的冗长，但是也能够根据签名值u_{i_{m}}的值来唯一决定所实施的签名操作，因此不需要附加非专利文献1中那样的控制位。
接下来，参照图4、图5，对检验装置i_{m}-2检验签名句u_{m-1}的方法进行说明。
检验装置i_{m}-2，首先通过输入单元V1B100从公开密钥存储装置i_{m}-3读入pk_{i_{1}}，…，pk_{i_{m-1}}，进而读入消息M_{1}，…，M_{m-1}(V1F100)。所读入的数据由输入单元V1B100写入到存储介质V1B1010中。
接下来，检验装置i_{m}-2通过输入单元V1B100将pk_{i_{1}}，…，pk_{i_{m-1}}发送给密钥检验装置i_{m}-4，请求其检验公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}的合法性(V1B101，V1F101)。
接下来，检验装置i_{m}-2为了从前一个签名装置追溯到第一个签名装置而顺次进行检验处理，首先，通过j初始化单元V1B102，将m-1设置为对正在检验哪个签名装置的签名进行管理的变量j(V1F102)。
接下来，检验装置i_{m}-2通过j判断单元V1B103，判断是否为j＞0(V1F103)。
下面，对j＞0的情况下的检验装置i_{m}-2的动作进行说明。关于不是j＞0的情况下的动作，将在后面说明。
接下来，检验装置i_{m}-2通过第二变换单元V1B104，首先从存储介质V1B1010读入必要的数据，判断是否为u_{i_{j}}＜n_{i_{j}}(V1F104)。
之后，如果是u_{i_{j}}＜n_{i_{j}}，检验装置i_{m}-2便通过第二变换单元V1B104，计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，并将计算结果写入到存储介质V1B1010中(V1F105)。
反之，如果不是u_{i_{j}}＜n_{i_{j}}，检验装置i_{m}-2便通过第二变换单元V1B104，将v′＝u_{i_{j}作为计算结果，写入到存储介质V1B1010中(V1F106)。
接下来，检验装置i_{m}-2通过双向单射计算单元V1B105，从存储介质V1B1010读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，将计算结果写入到存储介质V1B1010中(V1F107)。
接下来，检验装置i_{m}-2通过第一变换单元V1B106，从存储介质V1B1010读入必要的数据，首先判断是否为v＜n_{i_{j}}(V1F108)。
于是，如果是v＜n_{i_{j}}，检验装置i_{m}-2便通过第一变换单元V1B106计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，并将计算结果写入到存储介质V1B1010中(V1F109)。
另一方面，如果v＜n_{i_{j}}，检验装置i_{m}-2便通过第一变换单元V1B106，将U＝v作为计算结果写入到存储介质V1B1010中(V1F1010)。
接下来，检验装置i_{m}-2通过T_{j}计算单元V1B107，从存储介质V1B1010读入必要的数据，并计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，将计算结果写入到存储介质V1B1010中(V1F1011)。
检验装置i_{m}-2接着通过u计算单元V1B108，从存储介质V1B1010读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果写入到存储介质V1B1010中(V1F1012)。
接下来，检验装置i_{m}-2通过j減少单元V1B 109，使得j＝j-1(V1F1013)。
之后，检验装置i_{m}-2再次通过j判断单元V1B103，判断是否为j＞0(V1F103)。
如果j＞0，检验装置i_{m}-2便进行步骤V1F104之后的处理。
如果j＝0，检验装置i_{m}-2便通过u判断单元V1B1011，从存储介质V1B1010读入必要的数据，调查是否为u＝0(V1F1014)。
之后，如果u＝0，检验装置i_{m}-2便通过accept输出单元V1B1012，输出表示检验成功的accept(V1F1015)，如果不是这样，便通过reject输出单元V1B1013，输出表示检验失败的reject(V1F1016)。
另外，设图5的虚线所包围的部分的操作为f(x)，g(x)，h(x)，φ(x)。
也即f(x)＝x^{e_{i_{j}}}mod n_{i_{j}} ifx＜n_{i_{j}}＝x otherwise.
g(x)＝x^{e_{i_{j}}}mod n_{i_{j}} ifx＜n_{i_{j}}＝x otherwise.
φ(x)＝x+n_{i_{j}}mod 2^{κ}h(x)＝g(φ(x))。
于是，图3的虚线所包围的部分的操作f^{-1}(x)，g^{-1}(x)，h^{-1}(x)，φ^{-1}(x)，分别是f(x)，g(x)，h(x)，φ(x)的反函数。
因此，本实施方式中的签名装置i_{m}，通过计算公式u_{i_{m}}＝(g_{m}^{-1}(φ^{-1}(f_{m}^{-1}(H(T_{m})○u_{i_{m-1}}))))，生成签名句。另外，本实施方式中的检验装置i_{m}-2，通过计算公式u_{i_{m-2}}＝H(T_{m-1})○(f_{m-1}(φ(g_{m-1}(u_{i_{m-1}}))))，求出成为前一个签名装置的输入的签名句，之后重复进行同样的处理，直到达到最初的签名装置，求出输入的初始值，并调查所求出的初始值是否与预先设定的初始值(本实施方式的情况下为值0)相一致。
接下来，对本实施方式的效果进行说明。
第1效果是，签名长度不依赖于签名装置的数目。其原因是，签名前的数据与签名后所生成的数据位数不变。
第2效果是，能够在每次签名时变更签名装置的顺序。其原因与第1效果的情况下相同，签名前的数据与签名后所生成的数据位数不变。因此，对各个签名装置的输入是一定的，跟该签名装置是第几个进行签名的无关，因此不管是第几个，都能够通过相同的操作来签名。但需要通过某种形式，将按照什么样的顺序进行了签名通知给检验装置。
第3效果是与签名装置勾结的攻击者，无法伪造出从线路中途的“诚实(honest)”的签名装置中通过的签名句。其原因在于，不管对签名装置的输入u是什么，签名时进行两次的RSA计算中的至少一方的u变化。
第4效果是，在开始系统的使用的阶段，不需要知道签名装置的数目m，这是由于，即使签名装置的数目m在使用中动态变化，也能够正常使用。其原因是，签名装置的数目为m+1台时的签名顺序，是在进行了签名装置的数目为m台时的签名顺序之后再进行一次同样的签名操作，签名的操作方法不依赖于签名装置的数目m。
另外，以上的第1实施方式中，使用很典型的例子即RSA函数进行了说明，但更普通的是，只要有存在于{0，1}^{κ}中的部分集合X，并且满足以下条件(1)、(2)，就跟第1实施方式一样，能够实现一种签名长度不依赖于签名者的人数且安全的签名方式。
(1)f，g是带陷阱门的单向性置换，且X既包括在f的定义区中又包括在g的定义区中。
(2)φ、φ、φ^{-1}都是在多项式时间中能够计算的{0，1}^{κ}上的双向单射，将{0，1}^{κ}\X映射到X中。
这里，带陷阱门的单向性置换，是满足以下4个性质的函数。
1)计算f较为容易。
2)对于不知道陷阱门(也称作秘密密钥)的人来说，很难计算出f^{-1}。
3)对于知道陷阱门的人来说，计算f^{-1}很容易。
4)是双向单射(全单射)。
进而，一般来说存在位于{0，1}^{κ}中的部分集合X，如果满足以下条件(1)、(2)，就与第1实施方式一样，能够实现签名长度不依赖于签名者的人数且安全的签名方式。
(1)f是带陷阱门的单向性置换，且X包括在f的定义区中。
(2)h是带陷阱门的单向性置换，且{0，1}^{κ}\X包括在h的定义区中。
第2实施方式参照图6，本发明的第2实施方式，由签名装置i_{1}，…，i_{m}、检验装置i_{1}-2，…，i_{m}-2、公开密钥存储装置i_{1}-3，…，i_{m}-3、密钥合法性检验装置i_{1}-4，…，i_{m}-4、以及秘密密钥存储装置i_{1}-5，…，i_{m}-5构成。
参照图7，签名装置i_{m}由输入单元S1B100、T_{m}计算单元S1B103、异或计算单元S1B104、第一变换单元S1B105、双向单射变换单元S1B106、第二变换单元S1B107、存储介质S1B108、输出单元S1B109以及w设置单元S2B100构成。其他的签名装置也具有与签名装置i_{m}相同的构成。
参照图9，检验装置i_{m}-2由输入单元V2B200、T_{m-1}计算单元V2B202、v″计算单元V2B203、第二变换单元V2B204、双向单射变换单元V2B205、第一变换单元V2B206、u判断单元V2B207、accept输出单元V2B208、reject输出单元V2B209以及存储介质V2B2010构成。其他的检验装置也具有与检验装置i_{m}-2相同的构成。
对本实施方式进行概述。首先，给签名装置i_{1}输入签名装置i_{1}的公开密钥秘密密钥对、初始值u_{i_{0}}、以及消息M_{1}。签名装置i_{1}使用u_{i_{0}}生成针对消息M_{1}的签名句u_{i_{1}}。并且将初始值u_{i_{0}}作为辅助信息w_{i_{1}}而生成，输出u_{i_{1}}与w_{i_{1}}之组。接下来，给签名装置i_{2}输入签名装置i_{2}的公开密钥秘密密钥对、u_{i_{1}}与w_{i_{1}}之组、以及消息M_{2}。签名装置i_{2}使用u_{i_{1}}，生成针对消息M_{2}的签名句u_{i_{2}}，并且将u_{i_{1}}作为補助信息w_{i_{2}}而生成，输出u_{i_{2}}与w_{i_{2}}之组。之后，顺次给签名装置i_{j}输入签名装置i_{j}的公开密钥秘密密钥对、前一个签名装置所输出的签名句u_{i_{j-1}}、辅助信息w_{i_{j-1}}、以及消息M_{j}，签名装置i_{j}使用这些生成签名句u_{i_{j}}与辅助信息w_{i_{j}}之组。u_{i_{j}}是与第1实施方式相同的签名句，是表示签名装置i_{1}在消息M_{1}中进行了签名，签名装置i_{2}在消息M_{2}中进行了签名，…、签名装置i_{j}在消息M_{j}中进行了签名的数据。
另外，w_{i_{j}}是用来让签名句u_{i_{j}}的检验能够简单地进行的辅助信息，本实施方式的情况下，是成为签名装置i{j}的输入的签名句u_{i_{j-1}}本身。对各个j，若给检验装置i_{j}输入签名装置i_{1}，…，i_{j}的公开密钥与消息M_{1}，…，M_{j-1}，以及签名句u_{i_{j-1}}，w_{i_{j-1}}，则检验装置i_{j}运用辅助信息w_{i_{j-1}}，对u_{i_{j-1}}是否是使用签名装置i{1}，…，i{j-1}的公开密钥生成了针对消息M{1}，…，M_{j-1}的签名句进行检验。
本实施方式的系统目标与第1实施方式一样，是生成签名句u_{i_{m}}，也即表示签名装置i_{1}在消息M_{1}中进行了签名，签名装置i_{2}在消息M_{2}中进行了签名，…，签名装置i_{m}在消息M_{m}中进行了签名的数据。
另外，与第1实施方式一样，另外，本实施方式系统的应用开始阶段，也不需要知道签名装置的数目m。签名装置的数目m可以在应用中动态变化。另外，签名装置i_{1}，…，i_{m}的动作完全相同。检验装置、公开密钥存储装置、密钥合法性检验装置、秘密密钥存储装置也基本都进行相同的动作。
接下来以与第1实施方式的不同的为中心，对本实施方式进行详细说明。
签名装置i_{j}的公开密钥pk_{i}、秘密密钥sk_{i}，与第1实施方式一样被生成，对各个j＝1，…，m，秘密密钥存储装置i_{j}-5存储秘密密钥sk_{i_{j}}，且公开密钥存储装置i_{j}-3存储公开密钥pk_{1}，…，pk_{m}。
密钥合法性检验装置的动作与第1实施方式相同。
在将消息M_{1}，…，M_{m}、签名装置i_{1}，…，i_{m-1}使用公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}所生成的针对消息M_{1}，…，M_{m-1}的签名句u_{i_{m-1}}、以及辅助信息w_{i_{m-1}}输入给了签名装置i_{m}时的、签名装置i_{m}在消息M_{m}中进行签名的方法中，添加了生成辅助信息的顺序这一点，与第1实施方式不同，此外均与第1实施方式相同。对照图7、图8进行说明，本实施方式的情况下，签名装置i_{m}接着步骤S1F102的处理，通过w设置单元S2B100，计算出w_{i_{m}}＝u_{i_{m-1}}，并将计算结果写入到存储介质S1B108中(S2F100)。写入到了存储介质S1B108中的辅助信息w_{i_{m}}，与由输出单元S1B109通过与第1实施方式相同的顺序所生成并写入在存储介质S1B108中的签名句u_{i_{m}}一起被读出、输出(S1F1012′)。
接下来，对照图9、图10，对检验装置i_{m}-2检验签名句u_{m-1}的方法进行说明。
检验装置i_{m}-2，首先通过输入单元V1B200从公开密钥存储装置i_{m}-3读入pk_{i_{1}}，…，pk_{i_{m-1}}，进而读入消息M_{1}，…，M_{m-1}，并写入到存储介质V1B2010中。(V1F200)。
接下来，检验装置i_{m}-2通过输入单元V2B200，将pk_{i_{1}}，…，pk_{i_{m-1}}发送给密钥检验装置i_{m}-4，请求其检验公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}的合法性(V2F201)。
接下来，检验装置i_{m}-2通过T_{m-1}计算单元V2B202，从存储介质V2B2010读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果T_{m-1}保存到存储介质V2B2010中(V2F202)。
接下来，检验装置i_{m}-2通过v″计算单元V2B203，从存储介质V2B2010读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果v″保存到存储介质V2B2010中(V2F203)。
接下来，检验装置i_{m}-2通过第二变换单元V2B204，从存储介质V2B2010读入必要的数据，判断是否为v″＜n_{i_{m-1}}(V2F204)。如果是v″＜n_{i_{m-1}}，检验装置i_{m}-2便通过第二变换单元V2B204计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，并将计算结果v′保存到存储介质V2B2010中(V2F205)。另外，如果不是v″＜n_{i_{m-1}}，检验装置i_{m}-2便设为v′＝v″，并将计算结果v′保存到存储介质V2B2010中(V2F206)。
接下来，检验装置i_{m}-2通过双向单射变换单元V2B205，从存储介质V2B2010读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果v保存到存储介质V2B2010中(V2F207)。
接下来，检验装置i_{m}-2通过第一变换单元V2B206，从存储介质V2B2010读入必要的数据，判断是否是v＜n_{i_{m-1}}(V2F208)。如果v＜n_{i_{m-1}}，检验装置i_{m}-2便通过第一变换单元V2B206，计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}mod n_{i_{m-1}}}，并将计算结果u_{i_{m-2}}保存到存储介质V2B2010中(V2F209)。另外，如果不是u_{i_{m-2}}＜n_{i_{m-1}}，检验装置i_{m}-2便设u_{i_{m-1}})＝v，将计算结果u_{i_{m-2}}保存到存储介质V2B2010中(V2F2010)。
接下来，检验装置i_{m}-2通过u判断单元V2B2011，从存储介质V2B2010读入必要的数据，调查是否为u_{i_{m-2}}}＝w_{i_{m-1}}(V2F2011)。如果是u_{i_{m-2}}}＝w_{i_{m-1}}，检验装置i_{m}-2便通过accept输出单元V2B208输出accept(V2F2012)，如果不是，便通过reject输出单元V2B209输出reject(V2F2013)。
接下来，对本实施方式的效果进行说明。
第1效果是，签名长度不依赖于签名装置的数目。其原因是，签名前的数据与签名后所生成的数据位数不变。但与第1实施方式相比，数据长度增加了辅助信息的部分。
第2效果是，与第1实施方式相比，能够削减检验计算的计算量。其原因是，第1实施方式中，最终需要求出初始值，因此需要与已进行过签名签名的签名装置的数目成正比的检验计算，与此相对，本实施方式中，成为前一个签名装置的输入的签名句被作为辅助信息传送过来，因此只需要进行1签名装置份量的检验计算。但本实施方式需要以前一个签名装置能够信赖为前提，与不需要这样的前提就能够证明安全性的第1实施方式相比，安全性降低。
此外，还起到了与第1实施方式相同的效果。
另外，本实施方式中，作为与签名句u_{i_{j}}成组的辅助信息w_{i_{j}}，采用成为签名装置i_{j}的输入的签名句u_{i_{j-1}}本身，但也可以将h作为输出与输入位数相同的散列值的的给定的散列函数，并将u_{i_{j-1}}的散列值h(u_{i_{j-1}})作为辅助信息w_{i_{j}}。另外，对本实施方式也能够进行与第1实施方式相同的附加变更。
以上对本发明的实施方式进行了说明，但本发明并不仅限于以上实施方式，还可以进行其他各种附加变更。另外，本发明的签名装置与检验装置，其所具有的功能当然能够硬件实现，还可以通过计算机与程序来实现。程序在磁盘或半导体存储器等计算机可读存储介质中进行记录并被提供，在计算机的启动等时读入到计算机中，控制该计算机的动作，通由此使该计算机起到上述各个实施方式中的签名装置以及检验装置的功能。
权利要求
1.一种签名方法，是一种将初始值或其他多个签名装置顺次进行签名操作所生成的签名句、消息、以及本签名装置的秘密密钥作为输入，输出与输入相同长度的签名句的签名装置的签名方法，其特征在于所述所输出的签名句，表示该所述所输出的签名句的生成所述涉及的签名装置，在输入到了各个签名装置的所述消息中进行了签名。
2.如权利要求1所述的签名方法，其特征在于计算签名句的操作具有第1与第2这两个步骤，所述第1步骤(f^{-1}部分的操作)的计算中，使用带陷阱门的单向性置换的反函数，所述第2步骤(h^{-1}部分的操作)的计算中，使用与所述第1步骤相比相同或不同的带陷阱门的单向性置换的反函数，如果所述第1步骤结束，便将计算结果存储到存储介质中，在所述第2步骤开始时，从所述存储介质读出必要的数据，如果所述第2步骤结束，便将计算结果存储到所述存储介质中。
3.如权利要求2所述的签名方法，其特征在于在所述第1步骤中，如果针对所述第1步骤的输入是所述带陷阱门的单向性置换的值域的元素，便通过该所述带陷阱门的单向性置换的反函数对所述输入进行映射，如果不是则不进行任何操作，如果针对所述第2步骤的输入是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的反函数对所述输入进行映射，如果不是则不进行任何操作。
4.如权利要求3所述的签名方法，其特征在于所述第2步骤中所使用的所述带陷阱门的单向性置换的计算进一步由第1与第2子步骤构成，所述第1子步骤(φ^{-1}部分的操作)中，计算签名句全体的空间上的双向单射，该双向单射能够通过多项式时间来计算，并且所述双向单射的反函数也能够通过多项式时间来计算，在所述第2子步骤(g^{-1}部分的操作)中使用带陷阱门的单向性置换的反函数，如果是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的反函数对所述输入映射，如果不是则不进行任何操作，所述第1子步骤与所述第2子步骤的开始时，从所述存储介质读入必要的数据，所述第1子步骤与所述第2子步骤的结束时，将计算结果写入到所述存储介质中。
5.如权利要求4所述的签名方法，其特征在于所述第1步骤中所使用的所述带陷阱门的单向性置换，与所述第2步骤的所述第2子步骤中所使用的所述带陷阱门的单向性置换，是RSA函数。
6.如权利要求5所述的签名方法，其特征在于所述第2步骤的所述第1子步骤中所使用的所述双向单射，使用φ(x)＝x-n_{i_{m}}mod 2^{κ}，所述n_{i_{m}}是作为签名装置i_{m}的公开密钥的一部分的RSA模量，所述κ是安全参数。
7.如权利要求6所述的签名方法，其特征在于所述第1步骤之前有T_{m}计算步骤，所述T_{m}计算步骤中，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，对于各个j，所述M_{1}，…，M_{j}是输入给了第j个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥。
8.如权利要求7所述的签名方法，其特征在于所述第1步骤之前有异或计算步骤，所述异或计算步骤中，计算出U＝H(T_{m})○u_{i_{m-1}}，所述H为散列函数，所述u_{i_{m-1}}是所述所输入的签名句，○为异或。
9.如权利要求8所述的签名方法，其特征在于所述第1步骤之前，具有密钥合法性检验步骤，在所述密钥合法性检验步骤中，确认pk_{i_{1}}，…，pk_{i_{m-1}}是否完全不同，但在m＝1的情况下，不进行任何确认。
10.如权利要求9所述的签名方法，其特征在于所述第1步骤之前，有对所输入的签名句进行检验的签名句检验步骤。
11.如权利要求8所述的签名方法，其特征在于所述第1步骤之前，具有对pk_{i_{1}}，…，pk_{i_{m-1}}是否完全不同进行确认的密钥合法性检验步骤，以及对所输入的签名句进行检验的签名句检验步骤。
12.如权利要求1～11中任一项所述的签名方法，其特征在于具有将所输入的初始值或签名句或他们的散列值作为辅助信息而生成并写入到所述存储介质中的步骤，并将所述辅助信息与签名句作为组输出。
13.一种签名方法，其特征在于，包括输入单元将初始值或其他多个签名装置顺次进行签名操作而生成的签名句u_{i_{m-1}}、以及输入给这些签名装置的消息M_{1}，…，M_{m-1}输入并保存到存储介质中的步骤；T_{m}计算单元从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，且将‖设为位列彼此的连接时，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中的步骤；异或计算单元在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算出U＝H(T_{m})○u_{i_{m-1}}，将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，并在设n_{i_{m}}为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出v＝U，并将计算结果保存到所述存储介质中的步骤；双向单射变换单元从所述存储介质读入必要的数据，在设κ为安全参数时，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第2变换单元从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，便计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中的步骤；以及输出单元从所述存储介质读入u_{i_{m}}并作为签名句而输出的步骤。
14.如权利要求13所述的签名方法，其特征在于具有由w设置单元在w_{i_{m}}＝u_{i_{m-1}}或设h为散列函数时，计算w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中的步骤，将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
15.一种检验方法，是一种检验多个签名装置顺次进行签名操作而生成的签名句u是否合法的检验装置中的检验方法，其特征在于当且仅当签名句u是如下内容时通过检验即所述所输出的签名句为，所述所输出的签名句的生成所涉及的签名装置已经在输入于各个签名装置中的所述消息中进行了签名；所述签名句u的位长，是不依赖于为了计算所述签名句u而涉及的所述签名句装置的数目的常数。
16.一种检验方法，是一种检验多个签名装置顺次进行签名操作而生成的签名句u是否合法的检验装置中的检验方法，其特征在于当且仅当生成签名句u的签名装置通过合法的方法生成了签名句u时通过检验，所述签名句u的位长，是不依赖于为了计算所述签名句u而涉及的所述签名句装置的数目的常数，且所述签名句u的检验，使用作为所述多个签名装置中最后1台执行签名操作之前的数据的辅助信息w来进行。
17.如权利要求15或16所述的检验方法，其特征在于检验签名句的操作具有第1与第2这两个步骤，所述第1步骤(h部分的操作)的计算中，使用带陷阱门的单向性置换，所述第2步骤(f部分的操作)的计算中，使用与所述第1步骤相比相同或不同的带陷阱门的单向性置换，在开始所述第1步骤与第2步骤时，从存储介质读出必要的数据，在所述第1步骤与第2步骤结束结束时，将计算结果写入到所述存储介质中。
18.如权利要求17所述的检验方法，其特征在于所述第1步骤中，如果针对所述第1步骤的输入是所述带陷阱门的单向性置换的定义域的元素，便通过所述带陷阱门的单向性置换对所述输入进行映射，如果不是则不进行任何操作，如果针对所述第2步骤的输入是所述带陷阱门的单向性置换的定义域的元素，便通过所述带陷阱门的单向性置换对所述输入进行映射，如果不是则不进行任何操作。
19.如权利要求18所述的检验方法，其特征在于所述第1步骤中所使用的所述带陷阱门的单向性置换的计算进一步由第1与第2子步骤构成，所述第1子步骤(g部分的操作)中，使用带陷阱门的单向性置换的函数，如果是所述带陷阱门的单向性置换的值域的元素，便通过所述带陷阱门的单向性置换的函数对所述输入进行映射，如果不是则不进行任何操作，所述第2子步骤(φ部分的操作)中，计算签名句全体的空间上的双向单射，该双向单射能够通过多项式时间来计算，并且所述双向单射的反函数也能够通过多项式时间来计算，所述第1子步骤与所述第2子步骤的开始时，从所述存储介质读入必要的数据，所述第1子步骤与所述第2子步骤的结束时，将计算结果写入到所述存储介质中。
20.如权利要求19所述的检验方法，其特征在于所述第1步骤的所述第1子步骤中所使用的所述带陷阱门的单向性置换，与所述第2步骤中所使用的所述带陷阱门的单向性置换，是RSA函数。
21.如权利要求20所述的检验方法，其特征在于所述第1步骤的所述第2子步骤中所使用的所述双向单射，采用φ(x)＝x+n_i_{m}mod 2^{κ}，所述n_{i_{m}}是作为签名装置i_{m}的公开密钥的一部分的RSA模量，所述κ是安全参数。
22.如权利要求21所述的检验方法，其特征在于所述第2步骤之后有T_{j}计算步骤，所述T_{j}计算步骤中，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，这里，对各个j，所述M_{1}，…，M_{j}是输入在第j个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥。
23.如权利要求22所述的检验方法，其特征在于所述T_{j}计算步骤之后，具有如下那样的u计算步骤即将H设为散列函数，将U设为第2步骤的计算结果时，从所述存储介质读入必要的数据，而计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果存储到所述存储介质中。
24.如权利要求23所述的检验方法，其特征在于对j＝m-1，…，1，反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤。
25.如权利要求24所述的检验方法，其特征在于在对j＝m-1，…，1反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤之前，有密钥合法性检验步骤，所述密钥合法性检验步骤中，对pk_{i_{1}}，…，pk_{i_{m-1}}全部都不同进行确认，但在m＝1的情况下，不进行任何确认。
26.如权利要求25所述的检验方法，其特征在于在对j＝m-1，…，1反复执行所述第1步骤、所述第2步骤、所述T_{j}计算步骤，以及所述u计算步骤之后，存在u判断步骤，其中对作为检验结果是否得到了初始值进行判断。
27.如权利要求21所述的检验方法，其特征在于所述第1步骤之前有T_{m-1}计算步骤以及v″计算步骤，所述T_{m-1}计算步骤中，计算出T_{m-1}＝M_{1}|…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，这里，M_{1}，…，M_{m-1}是输入在第1，…，m-1个签名装置的消息，所述pk_{i_{j}}是签名装置i_{j}的公开密钥；所述v″计算步骤中，计算出v″＝H(T_{m-1})○u{i_{m-1}}，并且所述第1步骤将所述v”作为输入，且在所述第2步骤之后，存在判断所述第2步骤的计算结果是否与所述辅助信息相一致的u判断步骤。
28.一种检验方法，其特征在于，包括输入单元将由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、输入给这些签名装置的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}输入，并保存到存储介质中的步骤；J初始化单元将m-1设为变数j的步骤；第2变换单元，从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，便计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中的步骤；双向单射计算单元从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，如果v＜n_{i_{j}}便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中的步骤；每当将所述变量j减1时重复基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤直到所述变量j变为0的步骤；T_{j}计算单元从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}并将计算结果保存到所述存储介质中的步骤；u计算单元从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U并将计算结果保存到所述存储介质中的步骤；u判断单元从所述存储介质读入必要的数据，并判断u是否等于预先设定的初始值的步骤；以及输出单元在u等于预先设定的初始值的情况下输出表示检验成功的通知，否则便输出表示检验失败的通知的步骤。
29.一种检验方法，其特征在于，包括输入单元对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、前一个签名装置所输入的签名句或其散列值即辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中的步骤；T_{m-1}计算单元从所述存储介质读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中的步骤；v″计算单元从所述存储介质读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中的步骤；第2变换单元从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，便计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出v′＝v″，并将计算结果保存到所述存储介质中的步骤；双向单射计算单元从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中的步骤；第1变换单元从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，便计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中的步骤；u判断单元从所述存储介质读入必要的数据，并判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致的步骤；以及输出单元在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则，输出表示检验失败的通知的步骤。
30.一种签名装置，其特征在于，包括可读写的存储介质；输入单元，其对初始值或其他多个签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、以及输入在这些签名装置中的消息M_{1}，…，M_{m-1}进行输入，并保存到存储介质中；T_{m}计算单元，其从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，将‖设为位列彼此的连接时，计算出T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中；异或计算单元，其在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算出U＝H(T_{m})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，在将n_{i_{m}}设为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算v＝U，并将计算结果保存到所述存储介质中；双向单射变换单元，其从所述存储介质读入必要的数据，在将κ设为安全参数时，计算出v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，则计算出u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中；以及输出单元，其从所述存储介质读入u_{i_{m}}，并作为签名句输出。
31.如权利要求30所述的签名装置，其特征在于具有w设置单元，其在w_{i_{m}}＝u_{i_{m-1}}，或者将h设为散列函数时，计算w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中；将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
32.一种检验装置，其特征在于，包括可读写的存储介质；输入单元，其对由其他的1个以上的签名装置顺次进行了签名操作而生成的签名句u_{i_{m-1}}、输入在些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；J初始化单元，其将m-1设置为变量j；第2变换单元，其从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{j}}，便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中；T_{j}计算单元，其每当将所述变量j减1时，重复执行了基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤之后，从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，并将计算结果保存到所述存储介质中；u计算单元，其从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，并判断u是否等于预先设定的初始值；以及输出单元，其在u等于预先设定的初始值情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
33.一种检验装置，其特征在于，包括可读写的存储介质；输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、作为前一个签名装置所输入的签名句或其散列值的辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}进行输入，并保存到存储介质中；T_{m-1}计算单元，其从所述存储介质读入必要的数据，计算T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中；v″计算单元，其从所述存储介质读入必要的数据，计算v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，则计算v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，否则计算出v′＝v″，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，则计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}modn_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致；以及输出单元，其在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
34.一种程序，让具有可读写的存储介质的计算机起到作为以下单元而发挥功能输入单元，其对初始值或其他多个签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、以及输入在这些签名装置中的消息M_{1}，…，M_{m-1}进行输入，并保存到存储介质中；T_{m}计算单元，其从所述存储介质以及公开密钥存储装置读入必要的数据，在将pk_{i_{j}}设为签名装置i_{j}的公开密钥，将‖设为位列彼此的连接时，计算T_{m}＝M_{1}‖…‖M_{m}‖pk_{i_{1}}‖…‖pk_{i_{m}}，并将计算结果保存到所述存储介质中；异或计算单元，其在将H设为散列函数，将○设为异或时，从所述存储介质读入必要的数据，并计算U＝H(T_{m})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，在将n_{i_{m}}设为本签名装置的RSA模量时，如果U＜n_{i_{m}}，便计算出v＝u^{d_{i_{m}}}mod n_{i_{m}}，此外则计算出v＝U，并将计算结果保存到所述存储介质中；双向单射变换单元，其从所述存储介质读入必要的数据，在将κ设为安全参数时，计算v′＝v+n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v′＜n_{i_{m}}，便计算u_{i_{m}}＝v′^{d_{i_{m}}}mod n_{i_{m}}，此外则计算u_{i_{m}}＝v′，并将计算结果保存到所述存储介质中；以及输出单元，其从所述存储介质读入u_{i_{m}}，并作为签名句输出。
35.如权利要求34所述的程序，其特征在于让所述计算机进一步起到作为w设置单元而发挥功能，所述w设置单元在w_{i_{m}}＝u_{i_{m-1}}，或将h设为散列函数时，计算出w_{i_{m}}＝h(u_{i_{m-1}})，并将计算结果保存到所述存储介质中，并且将所述所计算出的w_{i_{m}}作为辅助信息，与所述所生成的签名句u_{i_{m}}作为组而输出。
36.一种程序，让具有可读写的存储介质的计算机作为以下单元而发挥功能输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、输入给这些签名装置的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；J初始化单元，其将m-1设为变量j；第2变换单元，其从所述存储介质读入必要的数据，如果u_{i_{j}}＜n_{i_{j}}，便计算出v′＝u_{i_{j}}^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出v′＝u_{i_{j}，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{j}，便计算出U＝v^{e_{i_{j}}}mod n_{i_{j}}，此外则计算出U＝v，并将计算结果保存到所述存储介质中；T_{j}计算单元，其在每当将所述变量j减1时，重复执行了基于所述第2变换单元、所述双向单射计算单元、以及所述第1变换单元的所述步骤之后，从所述存储介质读入必要的数据，计算出T_{j}＝M_{1}‖…‖M_{j}‖pk_{i_{1}}‖…‖pk_{i_{j}}，并将计算结果保存到所述存储介质中；u计算单元，其从所述存储介质读入必要的数据，计算出u_{i_{j-1}}＝H(T_{j})○U，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u是否等于预先设定的初始值；以及输出单元，其在u＝预先设定的初始值的情况下，输出表示检验成功的通知，否则输出表示检验失败的通知。
37.一种程序，让具有可读写的存储介质的计算机起到作为以下单元的功能输入单元，其对由其他的1个以上的签名装置顺次进行签名操作所生成的签名句u_{i_{m-1}}、作为前一个签名装置所输入的签名句或其散列值的辅助信息v_{i_{m-1}}、输入在这些签名装置中的消息M_{1}，…，M_{m-1}、以及这些签名装置的公开密钥pk_{i_{1}}，…，pk_{i_{m-1}}进行输入，并保存到存储介质中；T_{m-1}计算单元，其从所述存储介质读入必要的数据，计算出T_{m-1}＝M_{1}‖…‖M_{m-1}‖pk_{i_{1}}‖…‖pk_{i_{m-1}}，并将计算结果保存到所述存储介质中；v″计算单元，其从所述存储介质读入必要的数据，计算出v″＝H(T_{m-1})○u_{i_{m-1}}，并将计算结果保存到所述存储介质中；第2变换单元，其从所述存储介质读入必要的数据，如果v″＜n_{i_{m-1}}，则计算出v′＝v″^{e_{i_{m-1}}}mod n_{i_{m-1}}，此外则计算出v′＝v″，并将计算结果保存到所述存储介质中；双向单射计算单元，其从所述存储介质读入必要的数据，计算出v＝v′-n_{i_{m-1}}mod 2^{κ}，并将计算结果保存到所述存储介质中；第1变换单元，其从所述存储介质读入必要的数据，如果v＜n_{i_{m-1}}，便计算出u_{i_{m-2}}＝v^{e_{i_{m-1}}}modn_{i_{m-1}}，此外则计算出u_{i_{m-2}}＝v，并将计算结果保存到所述存储介质中；u判断单元，其从所述存储介质读入必要的数据，判断u_{i_{m-2}}或其散列值是否与所述辅助信息v_{i_{m-1}}相一致；以及输出单元，其在u_{i_{m-2}}或其散列值与所述辅助信息v_{i_{m-1}}相一致的情况下，输出表示检验成功的通知，否则，便输出表示检验失败的通知。
38.一种签名装置，至少包括如下那样的单元即在输入了初始值或其他多个签名装置顺次进行签名操作所生成的签名句、以及输入在所述签名装置的消息的情况下，计算出将所述消息与本装置的公开密钥以及已经签名过的签名装置的公开密钥连接起来的结果，并导出所述连接结果的散列值与所述签名句的异或值，其特征在于，还具有第1单元，其在所述异或值超过了所述签名装置的公开密钥的一部分即RSA模量的情况下，直接输出所述异或值，在没有超过的情况下，输出所述异或中进行了以RSA签名为准据的签名之后的结果；第2单元，其对所述第1单元的输出，作用向大至所述RSA模量的方向映射的函数；以及第3变换单元，其在所述第2单元中的运算结果超过了所述RSA模量的情况下，直接输出所述双向单射单元中的运算结果，在没有超过的情况下，输出在所述第2单元的运算结果中进行了以RSA签名为准据的签名之后的结果。
39.一种检验装置，是一种对多个权利要求38中所述的签名装置顺次进行签名操作而生成的签名句是否合法进行检验的检验装置，包括每当检验各个签名装置中的签名时在所述签名句超过了对应的签名装置的RSA模量的情况下，直接输出，在没有超过的情况下，输出进行了以RSA签名为准据之后的结果的第4单元；第5单元，其对所述第4单元的输出，作用向小至所述RSA模量的方向映射的函数；第6单元，其在所述第5单元的输出超过了所述RSA模量的情况下，直接输出所述第5单元的输出，在没有超过的情况下，输出在所述第5单元的输出中进行了以RSA签名为准据的签名之后的结果；以及第7单元，其对输入给所述签名装置的消息、连接本装置的公开密钥和已经签名过的签名装置的公开密钥的结果的散列值、以及所述第6单元的输出之间的异或值，进行求算；根据对各个所述签名装置的基于所述第7单元的输出结果，判断检验的成功、失败。
全文摘要
本发明提供一种在多个签名装置进行签名的情况下的签名长度不依赖于签名装置的数目的RSA签名方法。签名装置i_{m}，具有在所输入的签名句u_{i_{m－1}}超过了模量n_{i_{m}}的情况下，不进行任何操作，在超过了的情况下，进行以RSA方式为准据的签名的第1变换单元(SS1B105)；对该结果作用向大至模量n_{i_{m}}的方向进行映射的函数的双向单射变换单元(S1B106)；在该操作结果超过了模量n_{i_{m}}的情况下，不进行任何操作，在没有超过的情况下，进行以RSA方式为准据的签名的第2变换单元(S1B107)；以及将该操作结果作为签名句u_{i_{m}}输出的输出单元(S1B109)。
文档编号G09C1/00GK101069381SQ20058004097
公开日2007年11月7日 申请日期2005年11月11日 优先权日2004年11月29日
发明者寺西勇, 佐古和惠, 田口大悟, 野田润 申请人:日本电气株式会社
最新回复(0)