署名生成装置、署名验证装置、它们的方法及程序

摘要

将x设为署名生成装置的秘密密钥，将m

说明书

技术领域

本发明涉及信息安全性技术的应用技术，特别涉及能够从署名复原消息的消息复原署名。

背景技术

作为消息复原署名的以往技术，有在非专利文献1中示出的技术。该方式是在随机预言模型(random Oracle model)中证明了安全性的方式。以下，示出该方式的概要。

在该方式中，设为

消息m∈{0，1}^k2

函数F₁：{0，1}^k2→{0，1}^k1

函数F₂：{0，1}^k1→{0，1}^k2

函数H：{0，1}^k1+k2→{0，1}^k

E：在有限域F_q上定义的椭圆曲线

P：对椭圆曲线E上的点R满足p·R＝O(O是无限远点)的质数

G1：椭圆曲线E上的位数p的部分集合的点

w∈Z/pZ

秘密密钥：x∈Z/pZ

公开密钥：(F_q，E，G1，Y)(Y＝-x·G1(∈E))。

另外，{0，1}^δ表示2进δ位的比特数据，{0，1}^δ→{0，1}^ε表示从2进δ位的比特数据到2进ε位的比特数据的映射的函数。

<署名生成(signature generation)>

如下进行署名生成。其中，R_x表示点R∈E的x坐标，(+)表示异或运算符。

m’＝F₁(m)|(F₂(F₁(m))(+)m)......(1)

R_x＝(w·G1)_x

r＝R(+)m’......(2)

c＝H(r)

z＝w+c·x mod p

署名σ＝(r，z)。

<署名验证>

如下进行署名验证。其中，[m’]^k1表示m’的开头k1比特，[m’]^k2表示m’的余数的k2比特。

m’＝r(+)(z·G1+H(r)·Y)_x

m＝[m’]^k2(+)F₂([m’]^k1)

若[m’]^k1＝F₁(m)，则验证合格。

非专利文献1：Masayuki Abe，Tatsuaki Okamoto，“A Signature Schemewith Message Recovery as Secure as Discrete Logarithm，”ASIACRYPT 1999，pp.378-389

发明内容

发明要解决的课题

但是，在非专利文献1的方式中，式(1)的(F₂(F₁(m))和式(2)的R_x的比特长度为固定长度，消息m的比特长度也必须是固定长度。

因此，即使在消息m的长度比固定长度短的情况下，也不能相应地缩短署名σ的一部分r的比特长度，没有效率。此外，在消息m的比特长度比固定长度长的情况下，只能将消息m的一部分代入到式(1)中，不能构成将消息m的全部比特设为对象的消息复原署名。

用于解决课题的手段

本发明的署名生成装置如下进行署名生成。

首先，在署名生成装置的存储单元中存储整数的秘密密钥x，进而存储M比特的恢复消息m_rec∈{0，1}^M。其中，恢复消息m_rec成为署名对象的至少一部分。并且，署名生成装置生成整数的任意值k，并计算将位数q的循环群设为G，将该循环群G的生成源(generator)设为g的情况下的R＝g^k∈G，并输出该运算结果R。另外，“g^k∈G”意味着对g执行k次构成循环群G的运算(详细的在后面叙述)。接着，署名生成装置将对输入值输出L比特的散列值的散列函数H₁：{0，1}^*→{0，1}^L作用于依赖运算结果R和恢复消息m_rec的值α，并输出作为其运算结果的L比特的散列值h＝H₁(α)∈{0，1}^L。另外，L是与署名验证装置共享的正整数。此外，“将函数ε作用于δ”是指“将δ或用于确定δ的值代入函数ε”。接着，署名生成装置将输出比特长度根据恢复消息m_rec的比特长度M而决定为M比特的散列函数H₂：{0，1}^*→{0，1}^M作用于依赖运算结果R和散列值h的值β，并输出作为其运算结果的M比特的散列值u＝H₂(β)∈{0，1}^M。此外，署名生成装置计算恢复消息m_rec和散列值u的异或w＝m_rec(+)u∈{0，1}^M((+)是异或运算符)，并输出该异或值w。此外，署名生成装置计算依赖将散列值h∈{0，1}^L配置在第1比特位置上，将异或值w∈{0，1}^M配置在第2比特位置上的L+M比特的比特结合值h|w∈{0，1}^L+M的值r，该值r可复原散列值h和异或值w，并输出该值r。另外，第1比特位置不一定需要连续的L比特的位置，也可以是离散地配置的共L比特的位置。同样地，第2比特位置不一定需要是连续的M比特的位置，也可以是离散地配置的共M比特的位置。其中，在署名生成装置和署名验证装置中预先统一关于“第1比特位置”和“第2比特位置”是哪个比特位置。接着，署名生成装置将对输入值输出整数的散列函数H₃：{0，1}^*→Z(整数)作用于依赖值r的值γ，并输出作为其运算结果的散列值t＝H₃(γ)∈Z。之后，署名生成装置计算s＝k-t·x∈Z，并输出署名σ＝(r，s)。

本发明的署名验证装置如下进行署名验证。另外，将署名验证装置获取的署名表现为σ’＝(r’，s’)。此外，在署名验证装置的存储单元中存储有署名生成装置的公开密钥(public key)y＝g^x∈G。

首先，在署名验证装置中输入署名σ’＝(r’，s’)，该署名σ’＝(r’，s’)存储在存储单元中。此外，对应于署名σ’的恢复消息m_rec’的比特长度M’存储在存储单元中。另外，关于署名验证装置获取比特长度M’的值的方法在后面叙述。然后，署名验证装置将对输入值输出整数的散列函数H₃：{0，1}^*→Z(整数)，作用于依赖署名σ’具有的r’的值γ’，并输出作为其运算结果的散列值t’＝H₃(γ’)∈Z。此外，署名验证装置进行R’＝g^s’·y^t’∈G的运算，并输出该运算结果R’。另外，“g^s’·y^t’∈G”意味着，对g进行s’次构成循环群G的运算，对y进行t’次该运算，并对它们的各个运算结果进行该运算的运算(详细的在后面叙述)。接着，署名验证装置将输出比特长度根据恢复消息m_rec’的比特长度M’而决定的散列函数H₂：{0，1}^*→{0，1}^M’作用于值β，该值β依赖运算结果R’和r’的第1比特位置的L比特的值h’∈{0，1}^L，并输出作为其运算结果的M’比特的散列值u’＝H₂(β’)∈{0，1}^M’。此外，署名验证装置计算依赖值r’的第2比特位置的M’比特的值的值w’∈{0，1}^M’和散列值u’的异或w’(+)u’，并将其运算结果作为m_rec’∈{0，1}^M’而输出。此外，署名验证装置将对输入值输出L比特的散列值的散列函数H₁：{0，1}^*→{0，1}^L，作用于依赖运算结果R’和算出的恢复消息m_rec’的值α’，并输出作为其运算结果的L比特的散列值H₁(α’)∈{0，1}^L。然后，署名验证装置比较L比特的值h’和散列值H₁(α’)，并以h’＝H₁(α’)作为条件，输出验证成功的信息。另外，在“依赖ε和δ的值”中，除了包括该值仅依赖ε和δ的情况，还包括依赖ε和δ以及其他信息的情况。此外，在“依赖ε的值”中，除了包括该值仅依赖ε的情况，还包括依赖ε和其他信息的情况。其中，需要在署名生成装置中使用的值α、β、γ的构成方法与在署名验证装置中使用的值α’、β’、γ’的构成方法分别相同(详细的在后面叙述)。

这里，在本发明中，使用输出比特长度根据恢复消息的比特长度而变化的散列函数，并对处理方法下工夫，从而即使恢复消息的比特长度变化，也能够使成为各个异或运算的对象的两个被运算符的比特长度始终相同。由此，在恢复消息的比特长度短的情况下，能够相应地缩短在各个运算过程中的运算比特数和署名σ的比特数。此外，即使恢复消息的比特长度变长，也能够生成将恢复消息m_rec的全部比特设为对象的消息复原署名。

此外，在本发明中，若在署名生成装置中算出的散列值h、u与在署名生成装置中算出的散列值h’、u’不分别具有匹配性，则署名验证不能成功，所以与仅通过散列值h与散列值h’的匹配性来进行署名验证的情况相比，能够保证高的安全性。

另外，在本发明中，与以往不同，可以将消息的全部比特设为消息复原署名的对象(m＝m_rec)。

此外，也可以不将消息m的全部比特设为消息复原署名的对象。在不将消息m的全部比特设为消息复原署名的对象的情况下，M比特的恢复消息m_rec成为消息复原署名的对象，N比特的清零消息m_clr成为不是消息复原署名的普通的署名对象。此时，优选地，署名生成装置还将N比特的清零消息m_clr∈{0，1}^N存储在存储单元中，将散列函数H₃：{0，1}^*→Z作用于依赖值r和清零消息m_clr的值γ来计算t＝H₃(γ)∈Z，计算s＝k-t∈Z之后输出署名σ＝(r，s)和清零消息m_clr。在署名验证装置中，输入署名σ’和清零消息m_clr’。署名验证装置将散列函数H₃：{0，1}^*→Z作用于依赖署名σ’具有的r’和清零消息m_clr’的值γ’，并输出作为其运算结果的散列值t’＝H₃(γ’)∈Z。

这样，能够避免直到不需要将消息的全部比特设为消息复原署名的对象的情况为止，将消息的全部比特设为消息复原署名的对象，在各个运算过程中的运算比特数变长的情况。即，能够实现可灵活地应对各种比特长度的消息和各种用途的消息复原署名。

发明效果

在本发明中，能够实现可灵活地应对各种比特长度的消息的消息复原署名。

附图说明

图1是表示了第1实施方式的署名系统的整体结构的概念图。

图2是例示了第1实施方式中的署名生成装置的硬件结构的方框图。

图3是例示了第1实施方式中的署名生成装置的功能结构的方框图。

图4A是表示了散列运算单元的功能结构的细节的图，图4B是表示了散列运算单元的功能结构的细节的图。

图5是例示了第1实施方式的署名验证装置的功能结构的方框图。

图6是用于说明第1实施方式的署名生成处理的流程图。

图7A是用于说明步骤S15的处理的例子的流程图，图7B是用于说明步骤S17的处理的例子的流程图。

图8是用于说明第1实施方式的署名验证处理的流程图。

图9A是表示了“第1比特位置”和“第2比特位置”的设定例子的图，图9B是表示了“第1比特位置”和“第2比特位置”的设定例子的图，图9C是表示了“第1比特位置”和“第2比特位置”的设定例子的图。

图10是例示了第2实施方式中的署名生成装置的功能结构的方框图。

图11是例示了第2实施方式的署名验证装置的功能结构的方框图。

图12是用于说明第2实施方式的署名生成处理的流程图。

图13是用于说明第2实施方式的署名验证处理的流程图。

图14是例示了第3实施方式中的署名生成装置的功能结构的方框图。

图15是例示了第3实施方式的署名验证装置的功能结构的方框图。

图16是用于说明第3实施方式的署名生成处理的流程图。

图17是用于说明第3实施方式的署名验证处理的流程图。

图18是例示了第4实施方式中的署名生成装置的功能结构的方框图。

图19是例示了第4实施方式的署名验证装置的功能结构的方框图。

图20是用于说明第4实施方式的署名生成处理的流程图。

图21是用于说明第4实施方式的署名验证处理的流程图。

标号说明

1署名系统

10、110、210、310署名生成装置

20、120、220、320署名验证装置

具体实施方式

以下，参照附图说明用于实施本发明的优选方式。

【第1实施方式】

首先，说明本发明的第1实施方式。

<整体结构>

图1是表示了第1实施方式的署名系统1的整体结构的概念图。

如图1所示那样，本方式的署名系统1包括：进行署名生成的署名生成装置10、进行署名验证的署名验证装置20及公开署名生成装置10的效果密钥的公开密钥服务器装置30，且相互通过网络40而可通信地连接。另外，署名生成装置10、署名验证装置20及公开密钥服务器装置30是分别在公知的计算机中读入规定的程序而构成的装置。

<署名生成装置10的结构>

接着，说明署名生成装置10的结构。

【硬件结构】

图2是例示了第1实施方式中的署名生成装置10的硬件结构的方框图。

如图2所例示那样，该例子中的署名生成装置10包括：CPU(CentralProcessing Unit，中央处理器)11、输入单元12、输出单元13、辅助存储装置14、ROM(Read Only Memory，只读存储器)15、RAM(Random AccessMemory，随机存取存储器)16、总线17以及通信单元18。

该例子中的CPU11包括控制单元11a、运算单元11b以及寄存器11c，根据读入到寄存器11c中的各种程序来执行各种运算处理。此外，在该例子中的输入单元12是输入数据的输入端口、键盘、鼠标等，输出单元13是输出数据的输出端口、至外部记录介质的数据存储装置、印刷装置、显示器等。辅助存储装置14例如是硬盘、MO(Magneto-Optical disc，磁光盘)、半导体存储器等，其包括：存储了各种程序的程序区域14a和存储有各种数据的数据区域14b。此外，RAM16例如是SRAM(Static Random Access Memory，静态随机存取存储器)、DRAM(Dynamic Random Access Memory，动态随机存取存储器)灯，其包括：写入上述的程序的程序区域16a和写入各种数据的数据区域16b。此外，通信单元18是网卡等。此外，在该例子的总线17连接CPU11、输入单元12、输出单元13、辅助存储装置14、ROM15、PAM16以及通信单元18，使得可进行数据的交换。

【硬件和程序的协作】

CPU11(图2)根据读入的OS(Operating System，操作系统)程序，将存储在辅助存储装置14的程序区域14a中的程序写入RAM16的程序区域16a中。同样地，CPU11将存储在辅助存储装置14的数据区域14b中的各种数据写入RAM16的数据区域16b中。并且，写入了该程序和数据的RAM16上的地址被存储在CPU11的寄存器11c中。CPU11的控制单元11a依次读出存储在寄存器11c中的这些地址，并从读出的地址所示的RAM16上的区域中读出程序和数据，并使运算单元11b依次执行该程序所示的运算，并将其运算结果存储在寄存器11c中。另外，各程序可以作为单一的程序串来记载，此外，至少一部分程序也可以作为单独的模块而存储在库(library)中。

图3是例示了通过在CPU11中读入程序而构成的第1实施方式中的署名生成装置10的功能结构的方框图。另外，在图3中的箭头表示数据的流向，且省略了输入输出到暂时存储器10t和控制单元10s的数据的流向。

如图3所示那样，本方式的署名生成装置10包括：存储单元10a、秘密密钥生成单元10b、公开密钥生成单元10c、输入单元10d、消息分割单元10e、任意值生成单元10f、群运算单元10g、散列运算单元10h、10i、10j、10p、异或运算单元10h、10n、比特结合单元10m、整数运算单元10q、通信单元10r、控制单元10s、暂时存储器10t。另外，比特结合单元10m和异或运算单元10n构成r值运算单元10z。

此外，图4A是表示了散列运算单元10h的功能结构的细节的图，图4B是表示了散列运算单元10j的功能结构的细节的图。如图4所示那样，散列运算单元10h包括：散列次数运算单元10ha、部分散列运算单元10hb、比特结合单元10hc、比特删除单元10hd。此外，散列运算单元10j包括：散列次数运算单元10ja、部分散列运算单元10jb、比特结合单元10jc、比特删除单元10jd。

另外，存储单元10a和暂时存储器10t例如相当于在图2中记载的寄存器11c、辅助存储装置14、RAM16、或者结合了它们的存储器区域。此外，秘密密钥生成单元10b、公开密钥生成单元10c、消息分割单元10e、任意值生成单元10f、群运算单元10g、散列运算单元10h、10i、10j、10p、异或运算单元10h、10n、比特结合单元10m、整数运算单元10q、控制单元10s是用于实现各自的处理的程序被读入到CPU11而构成的单元。此外，输入单元10d是在读入规定的程序的CPU11的控制之下驱动的输入单元12，通信单元10r是读入规定的程序的CPU11的控制之下驱动的通信单元18。此外，署名生成装置10在控制单元10s的控制之下执行各种处理。此外，只要没有特别明示，运算过程的各个数据逐一地读写到暂时存储器10t中。

此外，上述的程序可以是单独实现其功能的程序，也可以是该程序进一步读出其他的库(没有记载)而实现各种功能的程序。即，各个程序的至少一部分相当于用于使计算机执行署名生成装置10的功能的程序。

<署名验证装置20的结构>

接着，说明署名验证装置20的结构。

【硬件结构】

与图2所示的署名生成装置10的硬件结构相同。

【硬件和程序的协作】

署名验证装置20也通过在图2所示那样的计算机中读入规定的程序而构成。图5是例示了这样构成的第1实施方式的署名验证装置20的功能结构的方框图。另外，在图5中的箭头表示数据的流向，且省略了输入输出到暂时存储器20n和控制单元20p的数据的流向。

如图5所示那样，本方式的署名验证装置20包括：存储单元20a、通信单元20b、比特长度提取单元20c、散列运算单元20d、20f、20i、20k、群运算单元20e、异或运算单元20g、比特提取单元20h、异或运算单元20j、比较单元20l、输出单元20m、控制单元20n、暂时存储器20p。

另外，存储单元20a和暂时存储器20p例如相当于计算机具有的寄存器、辅助存储装置、RAM、或者结合了它们的存储器区域。此外，比特长度提取单元20c、散列运算单元20d、20f、20i、20k、群运算单元20e、异或运算单元20g、比特提取单元20h、异或运算单元20j、比较单元20l、控制单元20n是用于实现各自的处理的程序被读入到CPU而构成的单元。此外，输出单元20m和通信单元20b是读入规定的程序的CPU的控制之下驱动的单元。此外，署名验证装置20在控制单元20n的控制之下执行各种处理。此外，只要没有特别明示，运算过程的各个数据逐一地读写到暂时存储器20p中。

此外，上述的程序可以是单独实现其功能的程序，也可以是该程序进一步读出其他的库(没有记载)而实现各种功能的程序。即，各个程序的至少一部分相当于用于使计算机执行署名验证装置20的功能的程序。

<处理>

接着，说明本方式的处理。

【前处理】

首先，决定难以对在署名系统1中使用的位数q的离散对数问题进行求解的循环群G与其生成源g∈G。作为这样的循环群G，例如可使用由在椭圆曲线上的有理点而成的群或有限域的乘法群等。另外，在使用由在椭圆曲线上的有理点而成的群的情况下，生成源g为椭圆曲线上的点g＝(g₁，g₂)，在使用有限域的乘法群的情况下，生成源g为2以上的整数。此外，用于在计算机上实现由在椭圆曲线上的有理点而成的群的具体方法中，存在各种方法(例如，“N.Koblitz.Elliptic Curve Crypto systems.Math.Comp.，Vol.48，No.17，pp.203-209，1987.”“Victor S.Miller.Use of Elliptic Curves in Cryptography.InAdvances in Cryptology-CRYPTO’85，Vol.218 of Lecture Notes in ComputerScience，pp.417-426.Springer，1986.”)，实际上，存在由椭圆曲线上的有理点而成的群所构成，且可安装在计算机上的各种加密方式。此外，从安全性方面考虑，期望位数q是质数，但若难以进行q的质数分解，则q不是质数也没有关系。此外，决定在署名系统1中使用的比特长度参数L∈Z_＞0(大于0的整数)。

此外，决定输出比特长度根据后述的恢复消息m_rec的比特长度M而决定为L+M比特的输出为可变长度的散列函数H₀：{0，1}^*→{0，1}^L+M，并决定输出比特长度根据恢复消息m_rec的比特长度M而决定为M比特的输出为可变长度的散列函数H₂：{0，1}^*→{0，1}^M。另外，关于这些散列函数的处理方法在后面叙述。

此外，决定对输入值输出L比特的散列值的散列函数H₁：{0，1}^*→{0，1}^L及对输入值输出Z_q(以q为模的完全余数系统(a complete system ofresidues modulo q))的元素(element)的散列函数H₃：{0，1}^*→Z_q。散列函数H₁可与散列函数H₀和散列函数H₂同样地构成，散列函数H₃可通过对SHA-1等的散列值进行以q为模的余数运算而构成。

用于确定如上决定的循环群G和各个散列函数H₀～H₃的信息，例如写入到构成署名生成装置10和署名验证装置20的各个程序中，署名生成装置10和署名验证装置20可进行通过决定的循环群G的运算、各个散列函数H₀～H₃的运算。此外，比特长度参数L∈Z_＞0、位数q、生成源g∈G存储在署名生成装置10的存储单元10a和署名验证装置20的存储单元20a中。

【密钥生成处理】

接着，说明署名生成装置10进行的密钥生成处理。

首先，署名生成装置10的秘密密钥生成单元10b生成任意的秘密密钥X∈Z_q。另外，该秘密密钥x的生成可以将拟随机数映射到Z_q而进行，也可以由署名生成者任意决定的值为基础而进行。生成的秘密密钥x安全地存储在署名生成装置10的存储单元10a中。即，署名生成装置10的外部的装置不能从存储单元10a取得秘密密钥x。

接着，署名生成装置10的公开密钥生成单元10c从存储单元10a读入秘密密钥x和循环群G的生成源g∈G，并进行由循环群G所定义的运算

y＝g^x∈G......(3)

而生成对应于秘密密钥x的公开密钥y∈G，并存储在存储单元10a中。另外，例如，在循环群G为由椭圆曲线E上的有理点而成的群的情况下，式(3)的右边意味着将作为椭圆曲线E上的点的生成源g＝(g₁，g₂)在椭圆曲线E上进行x倍的运算(x·g∈E)，公开密钥y成为椭圆曲线E上的点。另外，作为在计算机上执行椭圆曲线上的标量倍数运算的具体方法，例如可例示由仿射(affine)坐标或投影坐标来表示椭圆曲线上的点，使用二进展开法或移动窗法等的运算方法(例如，参照参考文献1“イアン·F·ブラケ、ガデイエル·セロツシ、ナイジエル·P·スマ一ト＝著「楕円曲腺暗号」、出版＝ピアソンエデユケ一シヨン、ISBN4-89471-431-0”等)。此外，例如在循环群G为有限域的乘法群的情况下，式(3)的右边意味着g^x mod p(其中，g是2以上的整数且p＝2q+1)的运算，公开密钥y成为标量值。生成的公开密钥y通过网络40，从通信单元10r发送到公开密钥服务器装置30，公开密钥服务器装置30将发送的公开密钥y例如与公开密钥证明书一同公开。另外，公开密钥y等的公开意味着，公开密钥y等存储在公开密钥服务器装置30的存储单元中，且处于可连接到网络40的任意装置可取得在公开密钥服务器装置30的存储单元中存储的公开密钥y等的状态。署名验证装置20通过通信单元20b而从公开密钥服务器装置30接收这样的公开密钥y，并存储在存储单元20a中。

【署名生成处理】

接着，说明第1实施方式的署名生成处理。

图6是用于说明第1实施方式的署名生成处理的流程图。以下，根据图6说明本方式的署名生成处理。

首先，在署名生成装置10(图3)的输入单元10d中，输入消息m∈{0，1}^L+M和恢复消息的比特长度M≥1(步骤S11)。输入的这些信息分别存储在存储单元10a中。

接着，消息分割单元10e从存储单元10a读取消息m∈{0，1}^L+M和恢复消息的比特长度M≥1。消息分割单元10e使用这些信息，将消息m∈{0，1}^L+M分割为比特长度M的恢复消息m_rec∈{0，1}^M和比特长度N(N≥0)的清零消息m_clr∈{0，1}^N(步骤S12)。例如，将消息m∈{0，1}^L+M的上位M比特设为恢复消息m_rec∈{0，1}^M，将下位N比特设为清零消息m_clr∈{0，1}^N。另外，分割法并不限定于此，可任意地设定将消息m∈{0，1}^L+M的哪个比特设定为恢复消息m_rec，将哪个比特设为清零消息m_clr。这样分割的比特长度M的恢复消息m_rec∈{0，1}^M和比特长度N的清零消息m_clr{0，1}^N分别存储在存储单元10a中。

接着，任意值生成单元10f生成任意值k∈Z_q，并将生成的任意值k存储在存储单元10a中(步骤S13)。另外，任意值k的生成，例如通过将拟随机数映射到Z_q而进行。

接着，群运算单元10g从存储单元10a读入生成源g∈G和任意值k∈Z_q，计算

R＝g^k∈G......(4)，

并将该运算结果g∈G输出到存储单元10a而存储(步骤S14)。另外，例如，在循环群G为由椭圆曲线E上的有理点而成的群的情况下，式(4)的右边意味着将作为椭圆曲线E上的点的生成源g＝(g₁，g₂)在椭圆曲线E上进行k倍的运算(k·g∈E)，运算结果R成为椭圆曲线E上的点。另外，作为在计算机上执行椭圆曲线上的标量倍数运算的具体方法，例如可例示由仿射(affine)坐标或投影坐标来表示椭圆曲线上的点，使用二进展开法或移动窗法等的运算方法。此外，例如在循环群G为有限域的乘法群的情况下，式(4)的右边意味着g^k mod p的运算，运算结果R成为标量值。

接着，散列运算单元10h从存储单元10a读取运算结果R∈G和恢复消息的比特长度M和比特长度参数L。散列运算单元10h将输出比特长度根据恢复消息m_rec的比特长度M而决定为L+M比特的散列函数H₀：{0，1}^*→{0，1}^L+M作用于运算结果R，输出并存储作为其运算结果的L+M比特的散列值

∏＝H₀(R)∈{0，1}^L+M......(5)

(步骤S15)。另外，例如，在循环群G为由椭圆曲线E上的有理点而成的群的情况下，式(5)的右边意味着将散列函数H₀作用于可唯一或限定性地确定作为在椭圆曲线E上的点的运算结果R的值(例如，点R的x坐标和y坐标的码的组合值，点R的x坐标或者y坐标，或者点R的x坐标和y坐标的比特结合值)的运算。即，此时的“将散列函数H₀作用于运算结果R”意味着，将散列函数H₀作用于可唯一地确定或者限定地确定作为在椭圆曲线E上的点的运算结果R的值的情况。此外，例如，在循环群G为有限域的乘法群的情况下，式(5)的右边意味着将散列函数H₀作用于作为标量值的运算结果R的运算。

【步骤S15的处理例子】

图7A是用于说明步骤S15的处理的例子的流程图。

首先，恢复消息的比特长度M和比特长度参数L读取到散列运算次数计算单元10ha。散列运算次数计算单元10ha进行

e_max＝rounddown{(L+M)/length(H)}......(5-1)

的运算，并将e_max存储在暂时存储器10t中(步骤S15a中)。另外，rounddown{*}意味着舍去*的小数点以下的运算，length(*)意味着*的比特长度，H意味着公知的散列函数。另外，作为散列函数H的具体例子，可例示SHA-1(比特长度160比特)或MD5(比特长度128比特)等。例如，L+M＝500，若散列函数H为SHA-1[length(H)＝160]，则e_max＝3。

接着，控制单元10s对变数e代入0，并将变数e存储在暂时存储器10t中(步骤S15b)。

接着，部分散列运算单元10hb从暂时存储器10t读取变数e，并从存储单元10a中读取运算结果R，计算散列值

H(e，R)......(5-2)

之后，存储在暂时存储器10t中(步骤S15c)。另外，例如，在循环群G为由椭圆曲线E上的有理点而成的群的情况下，式(5-2)意味着，将散列函数H作用于可唯一或者限定性地确定作为椭圆曲线E上的点的运算结果R的值(例如，将点R的x坐标和y坐标的符号组合的值，点R的x坐标或者y坐标，或者点R的x坐标和y坐标的比特结合值)和变数e的比特结合值的运算。此外，例如在循环群G为有限域的乘法群的情况下，式(5-2)意味着，将散列函数H作用于作为标量值的运算结果R和变数e的比特结合值的运算。

接着，控制单元10s从暂时存储器10t读取e_max和变数e，并判断是否满足

e＝e_max......(5-3)

(步骤S15d)。这里，若不满足式(5-3)，则控制单元10s将e+1设为新的e，并将新的e存储在暂时存储器10t之后(步骤S15e)，将处理返回到步骤S15c。另一方面，若满足式(5-3)，则控制单元10s对比特结合单元10hc给予指示，比特结合单元10hc从暂时存储器10t读取各个散列值H(0，R)、H(1，R)、H(2，R)、......、H(e_max，R)，并计算它们的比特结合值

HC(R)＝H(0，R)|......|H(e_max，R)......(5-4)

之后，存储在暂时存储器10t中(步骤S15f)。

接着，比特删除单元10hd从暂时存储器10t读取比特结合值HC(R)和恢复消息的比特长度M及比特长度参数L，

∏＝H₀(R)＝delete{length(HC(R))-(L+M)，HC(R)}......(5-5)

之后，输出到存储单元10a(步骤S15g)。另外，delete{δ，ε}意味着，将ε的比特从开头起删除δ比特的处理。即，式(5-5)意味着，将HC(R)的开头比特删除而将整体的比特长度为L+M的式设为∏＝H₀(R)的运算。

另外，步骤S15的处理方法并不限定于此。例如，也可以是不使用e，而通过散列链(hash chain)来扩展散列值的比特长度的方法。此时，式(5-4)的HC(R)，例如成为

HC(R)＝H(R)|H(H(R))||H(H(H(R)))|......|H(H(H......(R)......)|

(结束“步骤S15的处理的例子”的说明)。

在步骤S15之后，散列运算单元10i从存储单元10a读取散列值∏和恢复消息m_rec及比特长度参数L。散列运算单元10i将对输入值输出L比特的散列值的散列函数H₁：{0，1}^*→{0，1}^L，作用于依赖散列值∏和恢复消息m_rec的值α，并将作为其运算结果的L比特的散列值

h＝H₁(α)∈{0，1}^L......(6)

输出到存储单元10a而存储(步骤S16)。另外，在第1实施方式中，α是仅依赖散列值∏和恢复消息m_rec的值α＝(∏，m_rec)。另外，本方式的α的构成方法并没有限定，但设为α的构成方法与在后述的署名验证装置20中的α’(后述)的构成方法相同。作为α的构成例子，有如下所示的例子。

[α-1]将∏设为上位L+M比特、m_rec设为下位M比特而结合的L+2M比特的值设为α。

[α-2]将∏设为下位L+M比特、m_rec设为上位M比特而结合的L+2M比特的值设为α。

[α-3]将m_rec设为从上位起第奇数个比特(共计M比特)、∏设为其他的L+M比特而结合的L+2M比特的值设为α。

接着，散列运算单元10j从存储单元10a读取散列值∏和散列值h及恢复消息的比特长度M。散列运算单元10j将输出比特长度根据恢复消息m_rec的比特长度M而决定为M比特的散列函数H₂：{0，1}^*→{0，1}^M，作用于依赖散列值∏和散列值h的值β，并将作为其运算结果的M比特的散列值

u＝H₂(β)∈{0，1}^M......(7)

输出到存储单元10a而存储(步骤S17)。另外，在第1实施方式中，β是仅依赖散列值∏和散列值h的值β＝(∏，h)。另外，本方式的β的构成方法并没有限定，但设为β的构成方法与在后述的署名验证装置20中的β’(后述)的构成方法相同。作为β的构成例子，有如下所示的例子。

[β-1]将∏设为上位L+M比特、h设为下位L比特而结合的2L+M比特的值设为β。

[β-2]将∏设为下位L+M比特、h设为上位L比特而结合的2L+M比特的值设为β。

[β-3]将h设为从上位起第奇数个比特(共计L比特)、∏设为其他的L+M比特而结合的2L+M比特的值设为β。

【步骤S17的处理例子】

图7B是用于说明步骤S17的处理的例子的流程图。

首先，恢复消息的比特长度M读取到散列运算次数计算单元10ja。散列运算次数计算单元10ja进行

e_max＝rounddown{M/length(H)}......(7-1)

的运算，并将e_max存储在暂时存储器10t中(步骤S17a中)。

接着，控制单元10s对变数e代入0，并将变数e存储在暂时存储器10t中(步骤S17b)。

接着，部分散列运算单元10jb从暂时存储器10t读取变数e，并从存储单元10a中读取散列值∏、h，计算散列值

H(e，β)，β＝(∏，h)......(7-2)

之后，存储在暂时存储器10t中(步骤S17c)。

接着，控制单元10s从暂时存储器10t读取e_max和变数e，并判断是否满足

e＝e_max......(7-3)

(步骤S17d)。这里，若不满足式(7-3)，则控制单元10s将e+1设为新的e，并将新的e存储在暂时存储器10t之后(步骤S17e)，将处理返回到步骤S17c。另一方面，若满足式(7-3)，则控制单元10s对比特结合单元10jc给予指示，比特结合单元10jc从暂时存储器10t读取各个散列值H(0，β)、H(1，β)、H(2，β)、......、H(e_max，β)，并计算它们的比特结合值

HC(β)＝H(0，β)|......|H(e_max，β)......(7-4)

之后，存储在暂时存储器10t中(步骤S17f)。

接着，比特删除单元10id从暂时存储器10t读取比特结合值HC(β)和恢复消息的比特长度M，并计算

u＝H₂(β)＝delete{length(HC(β))-M，HC(β)}......(7-5)

之后，输出到存储单元10a(步骤S17g)。

另外，步骤S17的处理方法并不限定于此。例如，也可以是不使用e，而通过散列链(hash chain)来扩展散列值的比特长度的方法(结束“步骤S17的详细处理的例子”的说明)。

在步骤S17之后，异或运算单元10k从存储单元10a读取恢复消息m_rec和散列值u。异或运算单元10k计算恢复消息m_rec和散列值u的异或

w＝m_rec(+)u∈{0，1}^M......(8)

((+)是异或运算符)，并将该异或值w输出到存储单元10a中存储(步骤S18)。

接着，比特结合单元10m从存储单元10a读取散列值h∈{0，1}^L和异或值w∈{0，1}^M。比特结合单元10m计算将散列值h∈{0，1}^L配置在第1比特位置上，将异或值w∈{0，1}^M配置在第2比特位置上的L+M比特的比特结合值

d＝h|w∈{0，1}^L+M......(9)，

并将该比特结合值d输出到存储单元10a而存储(步骤S19)。另外，并没有特别限定将“第1比特位置”和“第2比特位置”设为哪个比特位置。但是，必须在署名生成装置10和署名验证装置20之间，将“第1比特位置”和“第2比特位置”设为哪个比特位置的基准统一。图9中示出“第1比特位置”和“第2比特位置”的设定例子。

图9A的例子是将连续的上位L比特设为“第1比特位置”，将连续的下位M比特设为“第2比特位置”的例子。图9B的例子是将连续的上位M比特设为“第2比特位置”，将连续的下位L比特设为“第1比特位置”的例子。此外，图9c的例子是L≥M的情况下的例子，是将从上位起第奇数个比特(共计M比特)的位置设为“第2比特位置”，将其他的比特位置设为“第1比特位置”的例子。

接着，异或运算单元10n从存储单元10a读取散列值∏和比特结合值d。异或运算单元10n计算散列值∏和比特结合值d的异或

r＝∏(+)d∈{0，1}^L+M......(10)，

并将该异或值r输出到存储单元10a中存储(步骤S20)。

接着，散列运算单元10p从存储单元10a读取异或值r和清零消息m_clr。散列运算单元10p将对输入值输出整数的散列函数H₃：{0，1}^*→Z_q，作用于依赖异或值r和清零消息m_clr的值γ，并将作为其运算结果的散列值

t＝H₃(γ)∈Z_q......(11)

输出到存储单元10a中而存储(步骤S21)。另外，在第1实施方式中，γ是仅依赖异或值r和清零消息m_clr的值γ＝(r，m_clr)。本方式的γ的构成方法并没有限定，但设为γ的构成方法与在署名验证装置20中的γ’(后述)的构成方法相同。作为γ的构成例子，有如下所示的例子。

[γ-1]将r设为上位L+M比特、m_clr设为下位N比特而结合的L+M+N比特的值设为γ。

[γ-2]将r设为下位L+M比特、m_clr设为上位N比特而结合的L+M+N比特的值设为γ。

[γ-3]将m_clr设为从上位起第奇数个比特(共计N比特)、r设为其他的L+M比特而结合的L+M+N比特的值设为γ。

接着，整数运算单元10q从存储单元10a读取任意值k和散列值t及秘密密钥x和q。整数运算单元10q计算

s＝k-t·x∈Z_q......(12)，

并将该运算结果s输出到存储单元10a而存储(步骤S22)。

接着，在通信单元10r中读取异或值r和运算结果s及清零消息m_clr，通信单元10r通过网络40，将署名σ＝(r，s)和清零消息m_clr发送到署名验证装置20(步骤S23)。

【署名验证处理】

接着，说明第1实施方式的署名验证处理。

图8是用于说明第1实施方式的署名验证处理的流程图。以下，根据图8说明本方式的署名验证处理。

首先，署名验证装置20(图5)的通信单元20b接收署名σ’＝(r’，s’)和清零消息m_clr’(相当于“接受输入”)，并将它们存储在存储单元20a中(步骤S41)。另外，若署名和清零消息是正规(authorized ones)的署名，则σ’＝(r’，s’)＝σ＝(r，s)，m_clr’＝m_clr，但在这里，将验证对象的署名表现为σ’＝(r’，s’)，将验证对象的清零消息表现为m_clr’。

接着，比特长度提取单元20c从存储单元20a读取比特长度参数L和署名σ’＝(r’，s’)的r’。比特长度提取单元20c根据

M’＝length(r’)-L......(13)

计算对应于署名σ’的恢复消息m_rec’的比特长度M’，并存储在存储单元20a中(步骤S42)。

接着，散列运算单元20d从存储单元20a读取r’和清零消息m_clr’及q。散列运算单元20d将与署名生成装置10相同的散列函数H₃：{0，1}^*→Z_q，作用于依赖r’和m_clr’的值γ’，并将作为其运算结果的散列值

t’＝H₃(γ’)......(14)

输出到存储单元20a中而存储(步骤S43)。另外，γ’的构成方法与在上述的署名生成装置10中的γ的构成方法相同(与将r＝r’，m_clr＝m_clr’的情况相同)。

接着，群运算单元20e从存储单元20a读取生成源g∈G和署名生成装置10的公开密钥y∈G和署名σ’的s’和散列值t’，并进行

R’＝g^s’·y^t’∈G......(15)

的运算，并将其运算结果R’输出到存储单元20a而存储(步骤S44)。另外，例如，在循环群G为由椭圆曲线E上的有理点(rational point)而成的群的情况下，式(15)的右边意味着将作为椭圆曲线E上的点的生成源g＝(g₁，g₂)在椭圆曲线E上进行s’倍，将公开密钥y＝(y₁，y₂)在椭圆曲线E上进行t’倍，并将这些运算结果在椭圆曲线E上相加的运算(s’·g+t’·y∈E)，运算结果R’成为椭圆曲线E上的点。另外，作为在CPU上执行椭圆曲线上的标量倍数运算的具体方法，例如可例示由仿射(affine)坐标或投影坐标来表示椭圆曲线上的点，使用二进展开法(dyadic expansion)或移动窗法(slidingwindow)等的运算方法。此外，例如在循环群G为有限域的乘法群(multiplicative group)的情况下，式(15)的右边意味着g^s’·y^t’mod p的运算，运算结果R’成为标量值。

接着，散列运算单元20f从存储单元20a读取运算结果R’∈G和恢复消息m_clr ’的比特长度M’及比特长度参数L。散列运算单元20f将与署名生成装置10相同的散列函数H₀：{0，1}^*→{0，1}^L+M作用于运算结果R’，并将作为其运算结果的L+M’比特的散列值

∏’＝H₀(R’)∈{0，1}^L+M’......(16)

输出到存储单元20a而存储(步骤S45)。另外，设为H₀(R’)的运算与署名生成装置10的情况相同(与R＝R’的情况相同)。

接着，异或运算单元20g从存储单元20a读取散列值∏’和署名σ’具有的r’，并计算它们的异或

d’＝∏’(+)r’∈{0，1}^L+M’......(17)，

并将该异或值d’输出到存储单元20a而存储(步骤S46)。

接着，比特提取单元20h从存储单元20a读取异或值d’和恢复消息m_rec’的比特长度M’。比特提取单元20h提取异或值d’的第1比特位置的L比特的值h’∈{0，1}^L和异或值d’的第2比特位置的M’比特的值w’∈{0，1}^M’，并将它们存储在存储单元20a中(步骤S47)。另外，“第1比特位置”和“第2比特位置”与在署名生成装置10的处理中的“第1比特位置”和“第2比特位置”相同(与将d＝d’的情况相同)。

接着，散列运算单元20i从存储单元20a读取散列值∏’和h’及恢复消息m_rec’的比特长度M’。散列运算单元20i将与署名生成装置10相同的散列函数H₂：{0，1}^*→{0，1}^M，作用于依赖散列值∏’和值h’的值β’，并将作为其运算结果的M’比特的散列值

u’＝H₂(β’)∈{0，1}^M’......(18)

输出到存储单元20a而存储(步骤S48)。另外，β’的构成方法与在上述的署名生成装置10中的β的构成方法相同(与将∏＝∏’、h＝h’的情况相同)。

异或运算单元20j从存储单元20a中读取值w’∈{0，1}^M’和散列值u’。异或运算单元20j计算值w’和散列值u’的异或

m_rec’＝w’(+)u’∈{0，1}^M’......(19)，

并将其运算结果作为恢复消息m_rec’∈{0，1}^M’，输出到存储单元20a而存储(步骤S49)。

接着，散列运算单元20k从存储单元20a读取散列值∏’和恢复消息m_rec’。散列运算单元20k将与署名生成装置10相同的散列函数H₁：{0，1}^*→{0，1}^L，作用于依赖散列值∏’和恢复消息m_rec’的值α’，并将作为其运算结果的L比特的散列值

H₁(α’)∈{0，1}^L......(20)

输出到存储单元20a而存储(步骤S50)。另外，α’的构成方法与在上述的署名生成装置10中的α的构成方法相同(与将∏＝∏’、m_rec＝m_rec’的情况相同)。

接着，比较单元20l从存储单元20a读取散列值H₁(α’)和值h’，并判断是否满足

h’＝H₁(α’)......(21)

(步骤S51)。

这里，在不满足式(21)的情况下，比较单元20l将0(验证失败)输出到存储单元20a而存储，输出单元20m输出从存储单元20a送出的0(验证失败)(步骤S52)。另一方面，在满足式(21)的情况下，比较单元20l将1(验证成功)输出到存储单元20a而存储，输出单元20m输出从存储单元20a送出的1(验证成功)(步骤S53)，还输出恢复消息m_rec’(步骤S54)。

【第2实施方式】

接着，说明本发明的第2实施方式。在第2实施方式中，不使用清零消息。这一点是与第1实施方式的不同点。以下，以与第1实施方式的不同点为中心进行说明，省略与第1实施方式共同的事项的说明。

<整体结构>

是第1实施方式的署名系统1的署名生成装置10置换为署名生成装置110，署名验证装置20置换为署名验证装置120的结构。

<署名生成装置110的结构>

接着，说明署名生成装置110的结构。

【硬件结构】

与第1实施方式的署名生成装置10相同。

【硬件和程序的协作】

署名生成装置110也通过在计算机中读入规定的程序而构成。

图10是例示了这样构成的第2实施方式中的署名生成装置110的功能结构的方框图。另外，在署名生成装置110中，对于与署名生成装置10共同的部分赋予与图3相同的符号，并简略说明。

如图10所示那样，本方式的署名生成装置110包括：存储单元10a、秘密密钥生成单元10b、公开密钥生成单元10c、输入单元110d、比特长度提取单元110e、任意值生成单元10f、群运算单元10g、散列运算单元10h、10i、10j、110p、异或运算单元10k、10n、比特结合单元10m、整数运算单元10q、通信单元110r、控制单元10s及暂时存储器10t。

另外，比特长度提取单元110e和散列运算单元110p是用于实现各自的处理的程序被读入到CPU11而构成的单元。此外，输入单元110d在读入规定的程序的CPU的控制之下驱动，通信单元110r在读入规定的程序的CPU的控制之下驱动。

此外，上述的程序可以是单独实现其功能的程序，也可以是该程序进一步读出其他的库(没有记载)而实现各种功能的程序。即，各个程序的至少一部分相当于用于使计算机执行署名生成装置110的功能的程序。

<署名验证装置120的结构>

接着，说明署名验证装置120的结构。

【硬件结构】请求审查时

与第1实施方式的署名验证装置20相同。

【硬件和程序的协作】

署名验证装置120也通过在计算机中读入规定的程序而构成。图11是例示了这样构成的第2实施方式的署名验证装置120的功能结构的方框图。

如图11所示那样，本方式的署名验证装置120包括：存储单元20a、通信单元120b、比特长度提取单元20c、散列运算单元120d、20f、20i、20k、群运算单元20e、异或运算单元20g、比特提取单元20h、异或运算单元20j、比较单元20l、输出单元20m、控制单元20n、暂时存储器20p。

另外，散列运算单元120d是用于实现处理的程序被读入到CPU而构成的单元。此外，通信单元120b在读入规定的程序的CPU的控制之下驱动。此外，上述的程序可以是单独实现其功能的程序，也可以是该程序进一步读出其他的库(没有记载)而实现各种功能的程序。即，各个程序的至少一部分相当于用于使计算机执行署名验证装置120的功能的程序。

<处理>

接着，说明本方式的处理。

【前处理/密钥生成处理】

与第1实施方式相同。

【署名生成处理】

接着，说明第2实施方式的署名生成处理。

图12是用于说明第2实施方式的署名生成处理的流程图。以下，按照图12说明本方式的署名生成处理。

首先，在署名生成装置110(图10)的输入单元110d中，输入恢复消息m_rec∈{0，1}^M(步骤S111)。输入的恢复消息m_rec存储在存储单元10a中。另外，在第2实施方式中，m＝m_rec。

接着，比特长度提取单元110e从存储单元10a读取恢复消息m_rec∈{0，1}^M，并提取其比特长度M而存储在存储单元10a中(步骤S112)。

之后，在署名生成装置110中执行与第1实施方式的步骤S13～S20相同的处理(步骤S113～S120)之后，散列运算单元110p从存储单元10a读取异或值r。散列运算单元110p将与第1实施方式相同的散列函数H₃：{0，1}^*→Z_q作用于依赖异或值r的值γ，并将作为其运算结果的散列值

t＝H₃(γ)∈Z_q......(22)

输出到存储单元10a而存储(步骤S121)。另外，在第2实施方式中，γ是仅依赖异或值r的值γ＝r。本方式的γ的构成方法并没有限定，但设为γ的构成方法与在后述的署名验证装置120中的γ’(后述)的构成方法相同。

接着，整数运算单元10q从存储单元10a读取任意值k和散列值t及秘密密钥x和q，根据上述的式(12)来计算s，并将该运算结果s输出到存储单元10a而存储(步骤S122)。

接着，在通信单元110r中读取异或值r和运算结果s，通信单元10r通过网络40将署名σ＝(r，s)发送到署名验证装置120(步骤S123)。

【署名验证处理】

接着，说明第2实施方式的署名验证处理。

图13是用于说明第2实施方式的署名验证处理的流程图。以下，根据图13说明本方式的署名验证处理。

首先，署名验证装置120(图11)的通信单元120b接收署名σ’＝(r’，s’)(相当于“接受输入”)，并将这些存储在存储单元20a中(步骤S141)。

接着，比特长度提取单元20c从存储单元20a读取比特长度参数L和署名σ’＝(r’，s’)的r’，并根据上述式(13)来计算对应于署名σ’的恢复消息m_rec’的比特长度M’，并存储在存储单元20a中(步骤S142)。

接着，散列运算单元120d从存储单元20a读取r’和q。散列运算单元120d将与署名生成装置110相同的散列函数H₃：{0，1}^*→Z_q，作用于依赖r’的值γ’，并将作为其运算结果的散列值

t’＝H₃(γ’)......(23)

输出到存储单元20a中而存储(步骤S143)。另外，γ’的构成方法与在上述的署名生成装置110中的γ的构成方法相同(与将r＝r’的情况相同)。

之后，通过与第1实施方式的步骤S44～S54相同的处理进行署名验证(步骤S144～S154)。

【第3实施方式】

接着，说明本发明的第3实施方式。本方式是第1实施方式的变形例，是简化了构成署名σ＝(r，s)的r的例子。即，相对于在第1实施方式中，设为r＝H₀(R)(+)(H₁(H₀(R)，m_rec)|m_rec(+)H₂(H₀(R)，H₁(H₀(R)，m_rec)))，在第3实施方式中，设为r＝H₁(R，m_rec)|m_rec(+)H₂(R，H₁(R，m_rec))。这样，能够削减运算量。以下，以与第1实施方式的不同点为中心进行说明，省略对于与第1实施方式共同的事项的说明。

<整体结构>

是第1实施方式的署名系统1的署名生成装置10置换为署名生成装置210，署名验证装置20置换为署名验证装置220的结构。

<署名生成装置210的结构>

接着，说明署名生成装置210的结构。

【硬件结构】

与第1实施方式的署名生成装置10相同。

【硬件和程序的协作】

署名生成装置210也通过在计算机中读入规定的程序而构成。

图14是例示了这样构成的第3实施方式中的署名生成装置210的功能结构的方框图。另外，在署名生成装置210中，对于与署名生成装置10共同的部分赋予与图3相同的符号，并简略说明。

如图14所示那样，本方式的署名生成装置210包括：存储单元10a、秘密密钥生成单元10b、公开密钥生成单元10c、输入单元10d、消息分割单元10e、任意值生成单元10f、群运算单元10g、散列运算单元210i、210j、10p、异或运算单元10k、比特结合单元210m、整数运算单元10q、通信单元10r、控制单元10s及暂时存储器10t。

另外，散列运算单元210i、210j、10p和比特结合单元210m是用于实现各自的处理的程序被读入到CPU而构成的单元。

此外，上述的程序可以是单独实现其功能的程序，也可以是该程序进一步读出其他的库(没有记载)而实现各种功能的程序。即，各个程序的至少一部分相当于用于使计算机执行署名生成装置210的功能的程序。

<署名验证装置220的结构>

接着，说明署名验证装置220的结构。

【硬件结构】

与第1实施方式的署名验证装置20相同。

【硬件和程序的协作】

署名验证装置220也通过在计算机中读入规定的程序而构成。图11是例示了这样构成的第2实施方式的署名验证装置120的功能结构的方框图。

如图15所示那样，本方式的署名验证装置220包括：存储单元20a、通信单元20b、比特长度提取单元20c、散列运算单元20d、220i、220k、比特提取单元220h、异或运算单元20j、比较单元20l、输出单元20m、控制单元20n、暂时存储器20p。

另外，散列运算单元220i、220k和比较单元20l是用于实现处理的程序被读入到CPU而构成的单元。此外，上述的程序可以是单独实现其功能的程序，也可以是该程序进一步读出其他的库(没有记载)而实现各种功能的程序。即，各个程序的至少一部分相当于用于使计算机执行署名验证装置120的功能的程序。

<处理>

接着，说明本方式的处理。

【前处理】

与第1实施方式的不同点在于没有设定散列函数H₀。

【密钥生成处理】

与第1实施方式相同。

【署名生成处理】

接着，说明第3实施方式的署名生成处理。

图16是用于说明第3实施方式的署名生成处理的流程图。以下，以与第1实施方式的不同点作为中心进行说明。

首先，署名生成装置210执行与第1实施方式的步骤S11～S14相同的处理(步骤S211～S214)。接着，散列运算单元10i从存储单元10a读取步骤S114的运算结果R和恢复消息m_rec及比特长度参数L。散列运算单元10i将对输入值输出L比特的散列值的散列函数H₁：{0，1}^*→{0，1}^L，作用于依赖运算结果R和恢复消息m_rec的值α(式(6))，并输出作为其运算结果的L比特的散列值h而存储(步骤S215)。另外，在第3实施方式中，α是仅依赖运算结果R∈G和恢复消息m_rec的值α＝(R，m_rec)。另外，在循环群G为有限域的乘法群的情况下，本方式的α的结构除了∏被置换为R的点之外，与第1实施方式相同。此外，在循环群G为由椭圆曲线E上的有理点而成的群的情况下，本方式的α的结构除了∏被置换为可唯一或者限定性地确定作为椭圆曲线E上的点的运算结果R的值(例如，将点R的x坐标和y坐标的符号组合的值，点R的x坐标或者y坐标，或者点R的x坐标和y坐标的比特结合值)的点之外，与第1实施方式相同。

接着，散列运算单元210j从存储单元10a读取运算结果R和散列值h和恢复消息的比特长度M。散列运算单元210j将输出比特长度根据恢复消息m_rec的比特长度M而决定为M比特的散列函数H₂：{0，1}^*→{0，1}^M，作用于依赖运算结果R和散列值h的值β(式(7))，并输出作为其运算结果的M比特的散列值u而存储在存储单元10a(步骤S216)。另外，在第3实施方式中，β是仅依赖运算结果R和散列值h的值β＝(R，h)。另外，在循环群G为有限域的乘法群的情况下，本方式的β的结构除了∏被置换为R的点之外，与第1实施方式相同。此外，在循环群G为由椭圆曲线E上的有理点而成的群的情况下，本方式的β的结构除了∏被置换为可唯一或者限定性地确定作为椭圆曲线E上的点的运算结果R的值(例如，点R的x坐标或者y坐标，或者点R的x坐标和y坐标的比特结合值)的点之外，与第1实施方式相同。

接着，异或运算单元10k从存储单元10a读取恢复消息m_rec和散列值u。异或运算单元10k计算恢复消息m_rec和散列值u的异或w(式(8))，并将该异或值w输出到存储单元10a而存储(步骤S217)。

接着，比特结合单元210m从存储单元10a读取散列值h∈{0，1}^L和异或值w∈{0，1}^M。比特结合单元210m计算将散列值h∈{0，1}^L配置在第1比特位置上，将异或值w∈{0，1}^M配置在第2比特位置上的L+M比特的比特结合值

r＝h|w∈{0，1}^L+M......(24)，

并将该比特结合值r输出到存储单元10a而存储(步骤S218)。关于将“第1比特位置”和“第2比特位置”设为哪个比特位置，与第1实施方式相同。

之后，执行与第1实施方式的步骤S21～S23相同的处理(步骤S219～S221)。

【署名验证处理】

接着，说明第3实施方式的署名验证处理。

图17是用于说明第1实施方式的署名验证处理的流程图。以下，以与第1实施方式的不同点作为中心进行说明。

首先，署名验证装置220执行与第1实施方式的步骤S41～S44相同的处理(步骤S241～S244)。

接着，比特提取单元220h从存储单元20a读取署名σ’＝(r’，s’)的r’和恢复消息m_rec’的比特长度M’。比特提取单元220h提取r’的第1比特位置的L比特的值h’∈{0，1}^L和r’的第2比特位置的M比特的值w’∈{0，1}^M’，并将它们存储在存储单元20a中(步骤S245)。另外，“第1比特位置”和“第2比特位置”与在署名生成装置10的处理中的“第1比特位置”和“第2比特位置”相同(与将d＝d’的情况相同)。

接着，散列运算单元220i从存储单元20a读取在步骤S244中的运算结果R’和h’及恢复消息m_rec’的比特长度M’。散列运算单元20i将与署名生成装置210相同的散列函数H₂：{0，1}^*→{0，1}^M，作用于依赖运算结果R’和h’的值β’(式(18))，并将作为其运算结果的M’比特的散列值u’输出到存储单元20a而存储(步骤S246)。另外，β’的构成方法与在署名生成装置210中的β的构成方法相同(与将∏＝∏’、h＝h’的情况相同)。

接着，异或运算单元20j从存储单元20a中读取值w’∈{0，1}^M’和散列值u’。异或运算单元20j计算值w’和散列值u’的异或(式(10))，并将其运算结果作为恢复消息m_rec’∈{0，1}^M’，输出到存储单元20a而存储(步骤S247)。

接着，散列运算单元220k从存储单元20a读取运算结果R’和恢复消息m_rec’。散列运算单元220k将与署名生成装置210相同的散列函数H₁：{0，1}^*→{0，1}^L，作用于依赖运算结果R’和恢复消息m_rec’的值α’，并将作为其运算结果的L比特的散列值(式(20))输出到存储单元20a而存储(步骤S248)。另外，α’的构成方法与在署名生成装置210中的α的构成方法相同(与将∏＝∏’、m_rec＝m_rec’的情况相同)。

之后，执行与第1实施方式的步骤S51～S54相同的处理(步骤S249～S252)。

【第4实施方式】

接着，说明本发明的第4实施方式。本方式是第3实施方式的变形例。在第4实施方式中，不使用清零消息。这一点是与第3实施方式的不同点。以下，以与第1～3实施方式的不同点为中心进行说明，省略与第1～3实施方式共同的事项的说明。

<整体结构>

是第1实施方式的署名系统1的署名生成装置10置换为署名生成装置310，署名验证装置20置换为署名验证装置320的结构。

<署名生成装置310的结构>

接着，说明署名生成装置310的结构。

【硬件结构】

与第1实施方式的署名生成装置10相同。

【硬件和程序的协作】

署名生成装置310也通过在计算机中读入规定的程序而构成。

图18是例示了这样构成的第4实施方式中的署名生成装置310的功能结构的方框图。另外，在署名生成装置310中，对于与署名生成装置10、110、210共同的部分赋予与图3、图10、图14相同的符号，并简略说明。

如图18所示那样，本方式的署名生成装置310包括：存储单元10a、秘密密钥生成单元10b、公开密钥生成单元10c、输入单元110d、比特长度提取单元110e、任意值生成单元10f、群运算单元10g、散列运算单元210i、210j、110p、异或运算单元10k、比特结合单元210m、整数运算单元10q、通信单元110r、控制单元10s及暂时存储器10t。

<署名验证装置320的结构>

接着，说明署名验证装置320的结构。

【硬件结构】

与第1实施方式的署名验证装置20相同。

【硬件和程序的协作】

署名验证装置320也通过在计算机中读入规定的程序而构成。图19是例示了这样构成的第2实施方式的署名验证装置120的功能结构的方框图。另外，在署名验证装置320中，对于与署名验证装置20、120、220共同的部分赋予与图5、图11、图15相同的符号，并省略说明。

如图19所示那样，本方式的署名验证装置320包括：存储单元20a、通信单元120b、比特长度提取单元20c、散列运算单元120d、220i、220k、群运算单元20e、比特提取单元20h、异或运算单元20j、比较单元20l、输出单元20m、控制单元20n及暂时存储器20p。

<处理>

接着，说明本方式的处理。

【前处理/密钥生成处理】

与第1实施方式相同。

【署名生成处理】

接着，说明第4实施方式的署名生成处理。

图20是用于说明第4实施方式的署名生成处理的流程图。以下，按照图20说明本方式的署名生成处理。

首先，署名生成装置310执行与第2实施方式的步骤S111～S114相同的处理(步骤S311～S314)，接着，执行与第3实施方式的步骤S215～S218相同的处理(步骤S315～S318)。接着，署名生成装置310执行与第2实施方式的步骤S121～S123相同的处理(步骤S319～S321)。

【署名验证处理】

接着，说明第4实施方式的署名验证处理。

图21是用于说明第4实施方式的署名验证处理的流程图。以下，按照图21说明本方式的署名验证处理。

首先，署名验证装置320执行与第2实施方式的步骤S141～S144相同的处理(步骤S341～S344)，接着，执行与第3实施方式的步骤S245～252相同的处理(步骤S345～S352)。

【成为署名验证的理由】

接着，说明署名验证装置20、120、220、320的处理成为署名验证的理由。

<关于第1、2实施方式>

在署名验证装置20、120中，使用署名σ’＝(r’，s’)，对依赖r’的值γ’计算散列值t’＝H₃(γ’)(式(14)(23))，计算R’＝g^s’·y^t’∈G(式(15))，计算散列值∏’＝H₀(R’)(式(16))。若署名σ’是正规的署名，则由于满足r’＝r和s’＝s(s＝k-t·x∈Z)，会满足γ’＝γ，满足t’＝H₃(γ’)＝H₃(γ)＝t，所以满足R’＝g^s’·y^t’＝g^s·y^t＝g^k-t·x·y^t·x＝g^k∈G。因此，成为∏’＝H₀(R’)＝H₀(g^k)＝∏。

此外，在署名验证装置20、120中，求异或值d’＝∏’(+)r’(式(17))，但若署名σ’是正规的署名，则由于满足r’＝r，满足r＝∏(+)d，满足∏’＝∏，所以满足d’＝d。此外，在署名验证装置20、120中，求依赖散列值∏’和异或值d’的第1比特位置的L比特的值h’∈{0，1}^L的值β’的散列值u’＝H₂(β’)(式(18))，但若署名σ’是正规的署名，则由于满足d’＝d，所以满足h’＝h，进而由于满足∏’＝∏，所以满足β’＝β，满足u’＝u。

此外，在署名验证装置20、120中，计算异或值d’的第2比特位置的M’比特的值w’∈{0，1}^M’和散列值u’的异或w’(+)u’，并将其运算结果设为恢复消息m_rec’∈{0，1}^M’(式(19))，但若署名σ’是正规的署名，则满足u’＝u、M’＝M及d’＝d。此时，因还满足w’＝w，所以满足m_rec’＝w’(+)u’＝w(+)u＝m_rec(+)u(+)u＝m_rec。

之后，在署名验证装置20、120中，求出将散列值H₁作用于依赖散列值∏’和恢复消息m_rec’的值α’而得的散列值H₁(α’)∈{0，1}^L(式(20))。若署名σ’是正规的署名，则满足∏’＝∏、m_rec’＝m_rec、α’＝α、h’＝h，且在署名生成装置中设为h＝H₁(α)，所以还满足h’＝H₁(α’)。即，若署名σ’是正规的署名，可以说满足h’＝H₁(α’)。

另一方面，若假设难以对在循环群G中的离散对数问题进行求解，则不知道秘密密钥x的第三人不能根据公开密钥y＝g^x∈G得知秘密密钥x，不能生成在上述的检验合格的署名σ’＝(r’，s’)。因此，可以称为在上述的检验合格的署名σ’＝(r’，s’)是知道秘密密钥x的人正规生成的署名。

<关于第3、4实施方式>

在署名验证装置220、320中，使用署名σ’＝(r’，s’)，对依赖r’的值γ’计算散列值t’＝H₃(γ’)，计算R’＝g^s’·y^t’∈G。若署名σ’是正规的署名，则由于满足r’＝r和s’＝s(s＝k-t·x∈Z)，会满足γ’＝γ，满足t’＝H₃(γ’)＝H₃(γ)＝t，满足y＝g^x∈G，所以成为R’＝g^s’·y^t’＝g^s·y^t＝g^k-t·x·y^t·x＝g^k∈R。

此外，在署名验证装置220、320中，求依赖运算结果R’和署名σ’的r’的第1比特位置的L比特的值h’∈{0，1}^L的值β’的散列值u’＝H₂(β’)，但若署名σ’是正规的署名，则由于满足r’＝r，所以满足h’＝h，进而由于满足R’＝R，所以满足β’＝β，满足u’＝u。

此外，在署名验证装置220、320中，计算署名σ’的r’的第2比特位置的M’比特的值w’∈{0，1}^M’和散列值u’的异或w’(+)u’，并将其运算结果设为恢复消息m_rec’∈{0，1}^M’，但若署名σ’是正规的署名，则满足u’＝u、M’＝M及r’＝r。此时，因还满足w’＝w，所以满足m_rec’＝w’(+)u’＝w(+)u＝m_rec(+)u(+)u＝m_rec。

之后，在署名验证装置220、320中，求出将散列值H₁作用于依赖运算结果R’和恢复消息m_rec’的值α’而得的散列值H₁(α’)∈{0，1}^L。若署名σ’是正规的署名，则满足R’＝R、m_rec’＝m_rec、α’＝α、h’＝h，且在署名生成装置中设为h＝H₁(α)，所以还满足h’＝H₁(α’)。即，若署名σ’是正规的署名，可以说满足h’＝H₁(α’)。

另一方面，若假设难以对在循环群G中的离散对数问题进行求解，则不知道秘密密钥x的第三人不能根据公开密钥y＝g^x∈G得知秘密密钥x，不能生成在上述的检验合格的署名σ’＝(r’，s’)。因此，可以称为在上述的检验合格的署名σ’＝(r’，s’)是知道秘密密钥x的人正规生成的署名。

【变形例】

本发明并不限定于上述的各个实施方式。例如，在第1、2实施方式中，将α设为仅依赖∏和m_rec的值，将α’设为仅依赖∏’和m_rec’的值。但是，也可以将α设为依赖∏和m_rec及第三信息的值，将α’设为依赖∏’和m_rec’及第三信息的值。另外，作为第三信息，可例示用于确定清零消息m_clr、公开密钥y及群G的参数等。关于β和β’及γ和γ’也是相同的。这样，能够进一步提高署名验证精度。尤其是，在作为第三信息而使用用于确定群G的参数的情况下，能够防止使用不正规(unauthorized)的群(例如，容易进行离散对数问题且在群运算单元20e中的运算结果与在正规的循环群G中的运算结果相同的群)而生成的不正规的署名检验合格的情况。

同样地，在第3、4实施方式中，将α设为仅依赖R和m_rec的值，将α’设为仅依赖R’和m_rec’的值。但是，也可以将α设为依赖R和m_rec及第三信息的值，将α’设为依赖R’和m_rec’及第三信息的值。关于β和β’及γ和γ’也是相同的。

此外，在各个实施方式中，由署名生成装置10、110、210、310进行密钥生成，但也可以由其他装置进行密钥生成。此外，在各个实施方式中，公开密钥服务器装置30公开了公开密钥y，但也可以是署名生成装置10、110、210、310对署名验证装置20、120、220、320发送公开密钥y的结构。此外，也可以是将在各个处理中的Z_q(以q为模的完全余数系统)置换为Z(整数)的结构。

此外，在各个实施方式中，署名验证装置20、120、220、320根据署名σ’具有的r’的比特长度和比特长度参数来计算恢复消息的比特长度，但也可以是署名生成装置10、110、210、310对署名验证装置20、120、220、320发送恢复消息的比特长度的结构。

此外，在各个实施方式中，至少将恢复消息m_rec设为署名对象。即，将恢复消息m_rec、m_rec’的比特长度M、M’分别设为1以上。但是，在实施方式1、3中，也可以将恢复消息m_rec、m_rec’分别设为无效(null)值，仅将清零消息m_clr、m_clr’设为署名对象。这相当于将恢复消息m_rec、m_rec’的比特长度M、M’分别设为0的情况。此外，也可以是可在M≥0的范围内设定比特长度M、M’的结构。这样，可根据比特长度M、M’的设定，进行消息恢复署名和普通署名的切换。另外，可省略通过将恢复消息m_rec、m_rec’分别设为无效值，将各自的比特长度M、M’分别设为0而没必要进行的处理。此外，也可以停止用于执行该没必要进行的处理的各个功能单元的处理。

此外，在本发明中的“散列(hash)函数”意味着对某一数据计算代表该数据的值的函数。在本发明中，不仅可以使用SHA-1和MD5等，例如还可以将公共密钥代入DES和Camellia等的公共密钥加密函数而得的函数用作散列函数。

此外，上述的各种处理不仅可以按照记载而按时序执行，也可以根据执行处理的装置的处理能力或根据需要而并列或单独执行，除此之外，能够在不脱离本发明的意旨的范围内适当变更是理所当然的。

此外，在通过计算机实现上述结构的情况下，由程序描述各个装置应具有的功能的处理内容。并且，通过由计算机执行该程序，能够在计算机上实现上述处理功能。

描述了该处理内容的程序可预先记录在计算机可读取的记录介质上。作为计算机可读取的记录介质，例如可以是磁记录装置、光盘、光磁记录介质、半导体存储器等，但具体地说，例如，作为磁记录装置，可使用硬盘装置、软盘装置、磁带等，作为光盘，可使用DVD(Digital Versatile Disc)、DVD-RAM(Random Access Memory)、CD-ROM(Compact Disc Read Only Memory)、CD-R(Recordable)/RW(ReWritable)等，作为光磁记录介质，可使用MO(Magneto-Optical disc)，作为半导体存储器，可使用EEP-ROM(ElectricallyErasable and Programmable-Read Only Memory)等。

此外，该程序的流通，例如可通过对记录了该程序的DVD、CD-ROM等可移动记录介质进行销售、转让、出租等来进行。此外，也可以是将该程序存储在服务器计算机的存储装置中，并通过网络将该程序从服务器计算机传送到其他计算机，从而流通该程序的结构。

执行这样的程序的计算机，例如首先将记录在可移动记录介质中的程序或者从服务器计算机传送的计算机暂时存储在自己的存储装置中。然后，在执行处理时，该计算机读取在自己的记录介质中存储的程序，并根据读取的程序来执行处理。此外，作为该程序的其他的实施方式，也可以计算机从可移动记录介质中直接读取程序，并执行对应于该程序的处理，也可以是在每次从服务器计算机对该计算机传送程序时，执行对应于接受的程序的处理。此外，也可以是不进行从服务器计算机至该计算机的程序的传送，而是通过仅根据其执行指示和取得结果来实现处理功能的、所谓的ASP(ApplicationService Provider，应用服务提供者)型的服务来执行上述处理的结构。另外，设为在本方式中的程序中，包括提供用于电子计算机的处理的信息且基于程序的数据(虽不是对于计算机的直接的命令，但具有限制计算机的处理的性质的数据等)。

此外，在本方式中，设为通过在计算机上执行规定的程序来构成本装置，但也可以通过硬件方式实现这些处理内容的至少一部分。

产业上的可利用性

本发明可应用于使用电子署名的各种用途。