【国家标准(GB)】 信息技术 安全技术 带消息恢复的数字签名方案

GB15851—1995
本标准等同采用国际标准ISO/IEC9796：1991《信息技术安全技术
带消息恢复的数字签名方
案》。
该国际标准规定的对有限长消息进行数字签名的方案，适合于我国使用。本标准的附录 A、附录 B、附录 C和附录 D都是提示的附录。本标准由中华人民共和国电子工业部提出本标准由电子工业部标准化研究所归口。本标准起草单位：电子工业部第三十研究所。本标准主要起草人：龚奇敏、黄月江、方关宝、雷利民、李桂茹。631
GE15851-1995
ISO/IEC前言
ISO(国际标准化组织)和IEC(国际电工委员会)形成了世界范围内的标准化专门体系。ISO或IEC的成员国，通过由处理特殊技术活动领域的各个组织所建立的技术委员会来参与国际标准的开发。ISO和IEC的技术委员会在共同感兴趣的领域内合作，其他与ISO和IEC有联络的官方和非官方国际性组也参与这项工作。
在信息技术领域内，ISO和IEC已建立了-·个联合技术委员会[SO/IECJTCI。被联合技术委员会接受的国际标准草案送给各成员国表决。…个国际标准的发布，需要至少了5为的成员国投费成票。围际标准ISO/IEC:9796超由信息技术联会技术委员会ISO/IECFTC1制定的.附录A、BC利)只作为参考。
GB 15851-1995
电子信息交换中的数字签名和传统邮件中的手写签名十分相似。大多数数字签名方案都基于某种公开密钥体制。所有公开密铜体制均包命三种基本操作：一产生密钥对的进程，该密钥对由一个秘密密钥和一个公开密钥组成：—-使用秘密密钥的进程；
使用公开密钥的进程。
在所有公开密钥数字签名方案中，秘密密钥用于消息的签名进程，公开密钥用于签名的验证进程，因而数字签名方案的密钥对由一个“秘密签名密钥\和一个“公开验证密钥\组成。明显地，有两类数字签名方案：一当验证进程需要消息作为输入的一部分时，该方案称作“带附录的签名方案”，在计算附录中将使用散列函数；
一—-当验证进程同时揭示消息及其几余（有时称作“消息影子”)时，该方案称作“带消息恢复的签名方案”。
本标准规定了有限长消息的数字签名方案。该数字签名方案的验证进程只需要尽量少的资源。它不涉及到使用散列函数，从而避免了对这种一般尊法的已知攻击
消息不一定要用自然语言写，可以是任意一种有限长的比特串。此类消息的例子有保密密销材料以及对更长消息进行散列运算后的结果，又称为“消息印鉴”。出保密软硬件所产生的几个比特串组成的结构化组便虐一个特例，其中一个比特串是对该硬件内产生的控制伴息编码的结果。注；本标准的使用可能涉及到某些专利条款。633
1范围
中华人民共和国国家标准
信息技术安全技术
带消息恢复的数字签名方案
Information technology-Security techniques--Digital signature scheme giving message recoveryGB 15851—1995
idt ISO/IEC 9796:1991
本标准规定了对有限长消息使用公开密钥体制的带消息恢复的数字签名方案。这种数字签名方案包含下列两个进程：签名进程，它使用秘密签名密钥和签名函数来对消息签名；—一验证进程，它使用公开验证密钥和验证函数来验证签名，同时恢复出消息。签名进程中，必要时，欲签名的消息需填充和扩展，然后加上与消息本身有关的人为的穴余，对消息中是否存在自然的九余不作假定。这人为的几余将由验证进程揭示出来，把这人为的穴余去掉便恢复出消息。
本标准不规定密钥产生进程、签名函数和验证函数。附录A（提示的附录)给出了一个公开密钥体制的例子，包含密钥产生、签名函数和验证函数。附录B(提示的附录)通过例子来说明这些操作的各步。这个方案中的若干参数与安全性有关：本标准不规定为要达到给定的安全性水平而对这些参数应取什么值。然而以这样一一种方式规定，即在本标准使用中，如果这些参数中有的必须要改变时，使所作的改变最小。
2定义
本标准采用下列定义。
2.1 消息 message
有限长的比特串。
2.2签名signature
由签名进程最后得到的比特串。3符号和缩路语
填充后的消息
扩展后的消息
带亢余的扩展后的消息
中间整数
签名的比特数
恢复后的中间整数
恢复后的带穴余的消息
国家技术监督局1995-12-13批准634
1996-08-01实施
恢复后的填充了的消息
GB15851—1995
秘密签名密钥控制下的签名函数公开验证密钥控制下的验证函数模的算术计算
半字节
半字节置换
字节的影子
X和Y两个比特串的级联
X和Y两个比特串的异或
1所有整数(比特串或字节串)其最高有效数字(位或字节)在左边。2表1和附录B(提示的附录)中采用了0到9和A到F的十六进制记法4概述
下面两章规定：
第5章中的签名进程；
第6章中的验证进程。
每个签名实体应使用其自已的对应于公开验证密钥的签名密钥并将其保密。如有必要，欲签名的消息应当填充和扩展，然后按照第5章规定的规则加上余，对此带穴余的扩展消息，如第5章规定的那样，用秘密签名密钥计算其签名。每个验证实体都会知道并使用该签名实体特定的公开验证密钥，当且仅当第6章规定的验证进程获得成功，签名才是可接受的。注：密钥的产生与分配已超出本标准的范围。5签名进程
图1概括了这种签名进程。
截取和强置
签名产生
图1签名进程
GB 15851--1995
注：这种签名进程较好的实现方法应当对这些操作加以物理保护，使得无法对秘密签名密钥控制下的签名函数进行直接访间。
5.1填充
消息是一个比特串，在其左边添上0到7个0以便获得个之字节的串。指数r（后面将用到)是填充0的数目加1,因此r的值为1到8。从而，在填充后的消息MP中，8z+1一r个最低有效位是信息位。MP=m ll m1 llmz i ml
mz=（r—1个填充的0）Ⅱ（9-r个信息位）z乘上16后的数应小于或等于k.十3。因此待签名消息的比特数最多应是小于或等于（k，十3)/16的最大整数的8倍。
5.2扩展
数t(后面要用到)是满足2t字节串至少包含ks一1个比特的最小整数扩展后的消息ME的获得是通过依次在左边不断重复MP的字节，直到形成t字节串为止。对于i从1到t，j等于（i一1)mod加上1(所以从1到z），ME的第i字节等于MP的第字节。ME=.m lmz Ilmi
t 字节 →
注：数≥小于或等于t，只有当k.模16同余于13、14、15、0或1时，两者才可能相等。5.3完余
通过交替地将ME的t字节放在奇数位置上，将t字节穴余放在偶数位置上便得到带兀余的扩展后的消息MR。MR的第2z字节的低半字节经指数r对其修改后，便由其值和位置对消息长度进行了编码。
对i从1到t，
MR的第（2i-1)字节等于 ME的第i字节；一MR的第2i字节等于ME的第i字节按表1规定的影子S的像，但第2z字节例外，它等于ME的第字节的影子与指数r异或的结果。MR =*..S(mz) r Il m, l ..S(m2) Il mz Il S(m) Il m— — 2t 学节—
注：从MP(mp，到mp）的之个字节计算MR(mr2到mri）的2t个字节是通过对i从1到t连续地应用下列三个公式完成的。j：=（(i一1)mod z）十1smr21-1：—mp;smr2：= S(mp,)。最后，第2z字节再经指数r修改。mr2：=r@mrz
5.4截取和强置
中间整数IR是用k，比特串来编码的，其最高有效位为1,k。一1个最低有效位便是MR的k，一1个最低有效位，但最低有效字节被替代了，如果μ2Ⅱμl是MR的最低有效字节，则IR的最低有效字节是μl6。
5.5签名产生
在秘密签名密钥的控制下，对IR应用签名函数就得到k。比特串的签名Z。636
GB 15851-1995
E =- Sign(IR)
表1置换Ⅱ和影子S
果μ由aaga四比特组成，在置换I下的像用()表示,则为αaiαar1甲a:?aOlaOaar
如果字节m由两个半字节μ组成，在影子S下的像用S(m）表示，则为I(μ)I(u）。验证进程
图2概括了验证进程。
签名开启
消息恢复
余校验
恢复后的消息
【签名被接受】
图2验证进程
6.1签名开启
在公开验证密钥的控制下，通过对签名三应用验证数将其变换成恢复后的中间整数IR。FRr = Veni(s)
如果IR不是-个最高有效位为1和最低有效半字节为6的比特串，则该签名三将被拒绝。6.2消息恢复
恢复后的带完余的消息MR是--个2t字节串，其（1一k）(mod16）个最高有效位为0,而～1个最低有效位便是IR\的，一1个最低有效位，但最低有效字节需被替代。按照表1中规定的置换Ⅱ，如果26是IR的最低有效四个半字节，则MR'的最低有效字节应是I（）2。MR'= mgell mzi-, l *m2 llm:
：MR和MR这两串可能不等，MR是由MR的一1个最低有效位且在其最高有效位填充了0到15个0后组637
威的。
GB 158511995
从MR'的2t个字节，计算出t个和，按照表1中规定的影子S，第i个和等于第2i个字节与第（2i1）个字节的影子的异或。
m2: S(m2i-1)
如果t个和都是0,则签名三将被拒绝。恢复成第1个非零和的位置，恢复后的填充了的消息MP'便是MR'中奇数位置上个最低有效字节组成的串。
MP = m2z- i mz- il -mzi- l -m ll m指数恢复成第1个非零和的最低有效半字节的值。如果指数不取1到8之间的值，或MP的r一1个最高有效位不全为0,则签名Z将被拒绝。m2-1 =（r一1个填充的0）Ⅱ（9r个信息位）消息被恢复成MP的8z+1一个最低有效位组成的串。6.3亢余校验
当且仅当MR'的k一1个最低有效位等于由恢复后的填充了的消息MP\，按照5.2和5.3计算出的带允余的扩展后的消息的。1个最低有效位时，签名2才被接受。638
A1定义　
模数modulus
两个素数的乘积构成的整数。
GB 15851-1995
附录A
（提示的附录）
用于数字签名的公开密钥体制例子公开验证密钥 public verification key模数和验证指数。
秘密签名密钥secret signature key签名指数。
A2符号和缩略语
Icm(a,b)
代表元素
合成整数
模数的比特长度
模数的素因子
验证指数
签名指数
整数a和b的最小公倍数
a关于n的雅可比(Jacobi)符号
注：设 p是奇素数,并设a是一个正整数,则整数a关于素数p的勒让德(Legendre)符号用下列式子定义：(alp) = a(p-v)/2modp
当a不是p的倍数时，则整数α关于素数p的勒让德符号取值为+1或一1,它取决于整数α是或不是模p的平方。p的倍数关于素数p的勒让得符号为0。设n为奇正整数，并设α是一个正整数，整数α关于整数n的雅可比符号等于整数α关于n的素因子的勒让得符号之乘积。所以，如果n=pq,则(an）=（alp)(alq）任何整数α关于任何整数n的雅可比符号可以有效地计算而无需知道n的素因子。A3密钥产生
A3.1公开验证指数
每个签名实体都应选择个正整数作为其公开验证指数。在特定的应用中，公开验证指数可以标准化。
注：公开验证指数取为2和3会有一些特别的优点。A3.2秘密的素因子和公开的模数每个签名实体应当秘密地且随机地选取两个不同的奇素数力和9，它们满足下列条件：-如果是奇数，则—1和1都应当与互素；如果是偶数，则（1)/2和(g1)/2都应当与互素，且和q不应当模8同余。公开模数n就是秘密素因子p和q的乘积。639
模数的长度为,应当等于+1。
GB15851-1995
1关于素数选取的若干别的条件也应当很好地考虑，以便防止对模数的因子分解。2有些形式的模数有简单的模约简运算且只需少量的存储表。这些形式是Fx.s. - : n = 264r c
Fry + in = 264 + c
其长度：表64x比特，
其长度：k=64α+1比特，
其中：1≤2x且264x-2。
在负形式中，个最高有效字节的所有位均是1,其数目可达到模数长度的四分之一在正形式中，在取值为1的最高有效位之后，3个最高有效字节的所有位均是0,其数目可达模数长度的四分之A3.3秘密签名指数
秘密签名指数是使得SV一1为下列数的倍数的最小正整数s：—lcm(p1,g—1),若是奇数;
1/2lcm（—1,q-1）,若是偶数。A4签名函数
中间整数IR是按5.4所述计算出的k～1比特串。IR关于n的代表元素记为RR。
如果是奇数，则RR就是IR；
如果是偶数且(IRn）=+1,则RR是IR；如果是偶数且（IR|n）=一1,则RR是IR/2。注；如果是偶数，则RR关于n的雅可比符号强置为+1。对RR计算其模n的s次幂，签名三便是此计算结果或者是其关于n的补,取其中较小者。Z - min(RR'mod n,n -- (RRmod n))这就定义了签名函数“Sign”。Z = Sign(IR)
A5验证函数
签名是小于n/2的正整数，对其进行模n的次幂以得到合成整数IS。于是，恢复后的中间整数IR'用下列译码确定：一如果IS是模16同余6，则IR就是IS；—茹果nIS是模16同余6,则IR'是n～IS。而且，当是偶数时，
一如果IS是模8同余3，则IR是2IS；—如果 n—IS是模8同余3,则IR是2(n一IS)。所有其他情况，签名Z都应被拒绝，而且，如果IR'不落在2k-2到22k-11范围内，签名也应被拒绝。
这便定义了验证函数“Verif”。GB 15851—1995
IR' - Verif(E)
附录B
（提示的附录）
关于附录A（提示的附录）的说明实例（使用十六进制记法）
公开指数为3的例子
B1.1密钥产生
公开验证指数√为3。
所以秘密素因子都是模3余2。
BA09106C
1B4CBB7A
q=16046EB39
CFF955B6
754EB6FE
7A782B15
E03BEAB6
4B4F48B7
BBC21479
7C1BC152
21D03C08
EE152A32
9FF 1B 8DE
90A1A3AB
B8AE6B66
6BF8CB25
513比特的公开模数n具有形式2512+c,其中2c>2384>c(形式F，+其α=8,y=16)。00000000
n=pq=1
00000000
BBA2D15D
25087920
12EC8CE6
BB303C8A
DD7CDF35
92F0A0B8
秘密签名指数s为(n—p-q+3)/6。 2 AAAAAAA
C9F0783A
81C96A3F
DBF1149E
B1.2变量的长度
AAAAAAAA
49DD5F6C
16AB5F95
4CDC3227wwW.bzxz.Net
00000000
21C5EBBC
8EA119FD
E8321B04
AAAAAAAA
5AF651F4
72D7CC3F
3FAADD3F
00000000
BAE52B71
66FB0640
1ACD 40B7
AAAAAAAA
C9DODC92
2D0F25A9
DA5DCDA7
是小于或等于(+2)/16的正整数，是小于或等于(十13)/16的最大整数。因而，当为513时，
取值从1到32，待签名的消息为1到256比特的串，填充后的消息MP和MP为1到32字节的串；
t为32,扩展后的消息ME为32字节的串，带几余的消息MR和MR2为64字节的串。而且，中间整数IR和IR及签名都是512比特（一1个比特）的串。B1.3例1
本例说明了对100比特消息签名的填充、扩展和截取过程。该消息为：CBBAA99887766554433221100
签名进程
在左边填充了四个0以后，填充后的消息MP便是13字节的串，所以z=13，r=5。MP=0CBBAA99887766554433221100通过将MP的13个相连字节不断重复，依次排在左边，直至达到32个字节的串，便构成扩展后的消息ME。
ME=55443322
2211000c
11000CBB
BBAA9988
带穴余的扩展后的消息MR是
GB15851-1995
AA998877
77665544
66554433
33221100
一个64字节的串，它是通过将ME的32个字节和穴余的32个字节交替排列而得到的，第26个字节的修改（E2)给出了消息边界的编码。MR44559944
88335522
BBAADD99
55223311
FF772266
0088FF77
EE00E20C
44559944
3311EE00
22664455
66BBBBAA
88335522
E70C66BB
99448833
DD990088
3311EED0
中间整数IR是从MR通过下列方法得到的：截取511个比特，左边填充一个1，最低有效字节予以替代，即lμ=00代之以μ6=06。因为V是奇数，所以代表元素RR便尼IR。RR--IR-C4559944
BBAADD99
55223311
FF772266
88335522
008BFF77
EE00E20C
44559944
3311EE00
22664455
66BBBBAA
88335522
E70C66BB
99448833
DD990088
3311EE06
对RR计算其模n的s次幂，此处，签名三便是该计算结果关于n的补。Z=309F873D
137D3EBF
6BDD022E
E04D3E42
验证进程
8DED8379
D8F25AB5
A65DABAB
1CAAB 717
490F6097
F138D56A
920A8101
C90D89EA
EAAFDABC
719CDC52
3A85D092
45A8D23A
签名Z小于n/2，通过对计算其模n的3次筹得到合成整数IS。I
3BAA66BB
FFF7F3C4
CFE6460E
13756A80
77CCAADD
BAA73D12
EF7BFD29
4E9B0774
CCEE 1 1 FF
FF5FA767
27E55E52
5FFEC5E1
18F39944
21AdA33D
89620587
E7BB52B1
中间整数是512比特的串，其中最高有效位是1且最低有效半字节的值为6，因为n在这里是模16余7且IS是模16余1，所以恢复后的中间整数IR是n一IS。怕=
C4559944
BBAADD99
55223311
FF772266
88335522
0088FF77
EE00E20C
44559944
3311EE00
22664455
66BBBBAA
88335522
E70C66BB
99448833
DD990088
3311EE06
恢复后的带穴余的消息MR'在这单便是64学节的串，其中，在一个填充的0后，接着便是IR的511个最低有效位，但最低有效字节例外，按照置换五中I(0）=E的说明，用216表示的EE06将代之以li！）+其值为EE00。MR44559944
BBAADD99
55223311
FF772266
88335522
0088FF77
EE00E20C
44559944
3311EE00
22664455
66BBBBAA
88335522
E70C668B
99448833
DD990088
3311EE00
第1个非零和是第13个和，值为5，这样=13而=5.恢复后的填充了的消息MP就是MR的最低有效奇数位置中13个字节的串。MP'-0CBBAA99887766554433221100MP的四个最高有效位（.-1=4）为0,因此消息本身就恢复为MP的100个最低有效位（82十1 - r = 100)的串。
小提示：此标准内容仅展示完整标准里的部分截取内容，若需要完整标准请到上方自行免费下载完整标准文档。