签名生成装置、签名生成方法

摘要

本发明提供一种能够使解析签名生成处理中使用的值变得困难的签名生成装置。签名生成装置通过随机数生成模块生成由len比特构成的随机数u，由选择模块将生成的随机数u转换成比特表现，从表存储部取得与各比特值对应的元对。签名生成装置通过随机元生成模块对取得的所有元对实施第一群G和第二群的基本运算，计算第一群G上的元Pk和第二群Ga上的元Pak。签名生成装置使用消息m的散列值h、第一群G上的元Pk和第二群Ga上的元Pak、转换模块、主要运算模块、逆转换模块、乘法运算模块、除法运算模块以及签名数据生成模块，生成对消息m的签名数据S。

主权项

一种签名生成装置，以群G和群Ga上的离散对数问题为安全性依据，对群G上的基本元P以及群Ga上的基本元Pa实施幂运算，从而生成对消息的数字签名，上述幂运算是指求出进行了整数次群的基本运算后的结果，其特征在于，预先将分解组与多个数分别对应，各分解组包括多个分解对，各分解对包括第一分解值和第二分解值，各第一分解值是对基本元P实施将任意正整数作为幂的幂运算而计算出的群G上的元，各第二分解值是对基本元Pa实施将与该第二分解值对应的第一分解值中使用的正整数作为幂的幂运算而计算出的群Ga上的元，上述签名生成装置具有：分解值存储单元，存储多个上述分解组；选择单元，从上述多个数中随机选择数u，从上述分解值存储单元中选择与选择出的数u对应的分解组；生成单元，对选择出的分解组中包含的2个以上的第一分解值实施上述群G的基本运算，生成第一幂元，对选择出的分解组中包含的、且与上述2个以上的第一分解值分别对应的第二分解值实施上述群Ga的基本运算，生成第二幂元；以及签名单元，将生成的上述第一幂元和消息分别转换成群Ga上的元，对转换后的第一幂元、转换后的消息以及上述第二幂元实施上述群Ga上的运算，计算第一离散对数和第二离散对数，使用计算出的第一离散对数和第二离散对数，生成对消息的数字签名。