[發明專利]簽名生成裝置、簽名生成方法以及簽名生成程序

有效

• 申請號: 200680049826.0
• 申請日: 2006-12-26
• 公開（公告）號: CN101351988A
• 公開（公告）日: 2009-01-21
• 發明（設計）人: 布田裕一;大森基司;滿保雅浩
• 申請（專利權）人: 松下電器產業株式會社
• 主分類號: H04L9/32
• 分類號: H04L9/32
• 代理公司: 永新專利商標代理有限公司
• 代理人: 楊謙;胡建新

1.一種簽名生成裝置，以群G和群Ga上的離散對數問題為安全性依據，對群G上的基本元P以及群Ga上的基本元Pa實施冪運算，從而生成對消息的數字簽名，上述冪運算是指求出進行了整數次群的基本運算后的結果，其特征在于，

預先將分解組與多個數分別對應，各分解組包括多個分解對，各分解對包括第一分解值和第二分解值，各第一分解值是對基本元P實施將任意正整數作為冪的冪運算而計算出的群G上的元，各第二分解值是對基本元Pa實施將與該第二分解值對應的第一分解值中使用的正整數作為冪的冪運算而計算出的群Ga上的元，

上述簽名生成裝置具有：

分解值存儲單元，存儲多個上述分解組；

選擇單元，從上述多個數中隨機選擇數u，從上述分解值存儲單元中選擇與選擇出的數u對應的分解組；

生成單元，對選擇出的分解組中包含的2個以上的第一分解值實施上述群G的基本運算，生成第一冪元，對選擇出的分解組中包含的、且與上述2個以上的第一分解值分別對應的第二分解值實施上述群Ga的基本運算，生成第二冪元；以及

簽名單元，將生成的上述第一冪元和消息分別轉換成群Ga上的元，對轉換后的第一冪元、轉換后的消息以及上述第二冪元實施上述群Ga上的運算，計算第一離散對數和第二離散對數，使用計算出的第一離散對數和第二離散對數，生成對消息的數字簽名。

2.根據權利要求1所述的簽名生成裝置，其特征在于，

上述多個數分別是由長度為2以上的預定長度構成的比特串所表現的數，

分解對按照由上述預定長度構成的比特串的各比特值對應，

上述選擇單元將選擇出的上述數u轉換成由上述預定長度的比特串構成的比特表現，從上述分解值存儲單元中選擇由與各個比特的值相對應的分解對構成的上述分解組。

3.根據權利要求2所述的簽名生成裝置，其特征在于，

上述生成單元，

對按照每個比特值選擇出的分解對所構成的上述分解組中包含的2個以上的第一分解值，實施上述群G中的基本運算，生成上述第一冪元，

對按照每個比特值選擇出的分解對所構成的上述分解組中包含的、且與上述2個以上的第一分解值分別對應的第二分解值，實施上述群Ga中的上述基本運算，生成上述第二冪元。

4.根據權利要求1所述的簽名生成裝置，其特征在于，

上述第一冪元包括2個以上的值，

上述簽名單元具有：

轉換部，將對上述消息的散列值作為冪，對上述基本元Pa實施群Ga中的上述冪運算，由此將上述散列值轉換成屬于上述群Ga的轉換后散列值；

第一運算部，使用上述第一冪元中包括的1個值計算第一數據；

第二運算部，對上述轉換后散列值實施上述群Ga上的基本運算，計算屬于上述群Ga的第三冪元；

逆轉換部，在上述群Ga或者上述群Ga中真實包含的子群Sa中，對上述第二冪元和上述第三冪元分別實施在上述轉換部中進行的轉換的冪運算的逆運算，由此求出第一離散對數和第二離散對數；

第三運算部，使用上述第一離散對數和上述第二離散對數計算第二數據；以及

數據生成部，生成由上述第一數據和上述第二數據的組構成的數字簽名。

5.根據權利要求4所述的簽名生成裝置，其特征在于，

上述簽名生成裝置還具有存儲有屬于上述群Ga的轉換后私鑰的轉換后私鑰存儲單元，上述轉換后私鑰是將私鑰作為冪而對上述基本元Pa實施由上述群Ga所示的點構成的橢圓曲線上的純量乘運算后得到的結果，

上述第二運算部對下述運算結果和上述轉換后散列值實施上述群Ga上的基本運算，來計算上述第三冪元，其中該運算結果是針對上述轉換后私鑰實施將上述第一數據作為冪的上述群Ga的冪運算而得到的上述群Ga上的元。

6.根據權利要求5所述的簽名生成裝置，其特征在于，

上述群G和上述群Ga是整數剩余環的乘法群，

上述群G和上述群Ga各自的基本運算是對各元實施乘法運算的乘法運算，

上述群G和上述群Ga各自的冪運算是將正整數作為冪數的冪乘運算。

7.根據權利要求6所述的簽名生成裝置，其特征在于，

上述群Ga相對于使用2個素數p、q和正整數m表現的n＝p^m×q，是Z/nZ的乘法群，^是表示冪乘運算的運算符，×是表示乘法運算的運算符，Z是整數環，Z/nZ是整數剩余環。