中华人民共和国国家标准
信息技术安全技术idt
带消息恢复的数字签名方案
GB15851-1995ISO/IEC9796:1991

Informationtechnology-Securitytechniques
Digitalsignatureschemegivingmessagerecovery

(国家技术监督局1995年12月13日发布1996年8月1日实施)


一范围

本标准规定了对有限长消息使用公开密钥体制的带消息恢复的数学签名方案。

这种数学签名方案包含下列两个进程：

――签名进程，它使用秘密签名密钥和签名函数来对消息签名；

――验证进程，它使用公开验证密钥和验证函数来验证签名，同时恢复出消息。

签名进程中，必要时，欲签名的消息需填充和扩展，然后加上与消息本身有关的人为的冗余，对消息中是否存在自然的冗余不作假定。这人为的冗余将由验证进程揭示出来，把这人为的冗余去掉便恢复出消息。

本标准不规定密钥产生进程、签名函数和验证函数。附录A（提示的附录）给出了一个公开密钥体制的例子，包含密钥产生、签名函数和验证函数。附录B（提示的附录）通过例子来说明这些操作的各步。

这个方案中的若干参数与安全性有关：本标准不规定为要达到给定的安全性水平而对这些参数应取什么值。然而以这样一种方式规定，即在本标准使用中，如果这些参数中有的必须要改变时，使所作的改变最小。

二定义

本标准采用下列定义

2.1消息message

有限长的比特串。

2.2签名signature

由签名进程最后得到的比特串。

三符号和缩略语

MP填充后的消息

ME扩展后的消息

MR带冗余的扩展后的消息

IR中间整数

∑签名

Ks签名的比特数

IR’恢复后的中间整数

MR’恢复后的带冗余的消息

MP’恢复后的填充了的消息

Sign秘密签名密钥控制下的签名函数

Verif公开验证密钥控制下的验证函数 modz模z的算术计算

μ半字节

П半字节置换

m字节

S字节的影子

X‖YX和Y两个比特串的级联

X⊕YX和Y两个比特串的异或

注：

1所有整数（比特串或字节串）其最高有效数字（位或字节）在左边。

2表1和附录B（提示的附录）中采用了0到9和A到F的十六进制记法。

四概述

下面两章规定：

――第5章中的签名进程；

――第6章中的验证进程

每个签名实体应使用其自己的对应于公开验证密钥的签名密钥并将其保密。

如有必要，欲签名的消息应当填充和扩展，然后按照第5章规定的规则加上冗余，对此带冗余的扩展消息，如第5章规定的那样，用秘密签名密钥计算其签名。

每个验证实体都会知道并使用该签名实体特定的公开验证密钥，当且仅当第6章规定的验证进程获得成功，签名才是可接受的。

注：密钥的产生与分配已超出本标准的范围。

五签名进程

图1概括了这种签名进程。

图1签名进程

注：这种签名进程较好的实现方法应当对这些操作加以物理保护，使得无法对秘密签名密钥控制下的签名函数进行直接访问。

5.1填充

消息是一个比特串，在其左边添上0到7个0以便获得一个z字节的串。指数r（后面将用到）是填充0的数目加1，因此r的值为1到8。从而，在填充后的消息MP中，8z＋1－r个最低有效位是信息位。

MP＝mz‖mz-1‖…m2‖m1

Mz=(r-1个填充的0)‖(9-r个信息位)

z乘上16后的数应小于或等于ks＋3。因此待签名消息的比特数最多应是小于或等于（ks＋3）/16的最大整数的8倍。

5.2扩展

数t(后面要用到)是满足2t字节串至少包含ks–1个比特的最小整数。

扩展后的消息ME的获得是通过依次在左边不断重复MP的z字节，直到形成t字节串为止。对于i从1到t，j等于（i-1）modz加上1（所以j从1到z），ME的第i字节等于MP的第j字节。

ME＝…mz‖…mz‖m1‖
T字节

注：数z小于或等于t，只有当ks模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的第z字节的影子与指数r异或的结果。

MR＝…S（mz）⊕r‖mz‖…S（m2）‖m2‖S（m1）‖m1
2t字节

注：从MP（mpZ到mp1）的z个字节计算MR（mr2t到mr1）的2t个字节是通过对i从1到t连续地
应用下列三个公式完成的。j:=((i-1)modz)+1;mr2i-1:=mpj;mr2i:=s(mpj)。最后，第2z字节再经指数r修改。mr2z:＝r⊕mr2z。

5.4截取和强置

中间整数IR是用ks比特串来编码的，其最高有效位为1，ks–1个最低有效位便是MR的ks–
1个最低有效位，但最低有效字节被替代了，如果μ2‖μ1是MR的最低有效字节，则IR的最低有效字节是μ1‖6。

5.5签名产生

在秘密签名密钥的控制下，对IR应用签名函数就得到ks比特串的签名Σ。

Σ＝Sign(IR)

表1置换Ⅱ和影子S

μ
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F

∏μ
E
3
5
8
9
4
2
F
0
D
B
6
7
A
C
1

如果μ由a4a3a2a1四比特组成，在置换∏下的像用∏（μ）表示，则为a4⊕a2⊕a1⊕1；a4
⊕a3⊕a1⊕1；a4⊕a3⊕a2⊕1；a3⊕a2⊕a1。

如果字节m由两个半字节μ2μ1组成，在影子S下的像用S(m)表示，则为∏(μ2)∏(μ1)


六验证进程

图2验证进程

图2概括了验证进程。

6.1签名开启

在公开验证密钥的控制下，通过对签名Σ应用验证函数将其变换成恢复后的中间整数IR’。

IR’=Verif(Σ)

如果IR’不是一个最高有效位为1和最低有效半字节为6的ks比特串，则该签名Σ将被拒绝。

6.2消息恢复

恢复后的带冗余的消息MR’是一个2t字节串，其（1－ks）(mo16)个最高有效位为0，而
ks－1个最低有效位便是IR’的ks－1人最低有效位，但最低有效字节需被替代。按照表1中
规定的置换∏，如果μ1‖μ2‖μ3‖6是IR￠的最低有效四个半字节，则MR’的最低有效
字节应是Ⅱ－1(μ4)‖μ2。

MR’＝m2t‖m2t-1‖…m2‖m1

注：MR和MR’这两串可能不等，MR’是由MR的ks－1个最低有效位且在其最高有效位填充了0
到15个0后组成的。

从MR’的2t个字节，计算出t个和，按照表1中规定的影子S，第i个和等于第2i个字节与第
（2i－1）个字节的影子的异或。

m2iS(m2i-1)

如果t个和都是0，则签名Σ将被拒绝。

Z恢复成第1个非零和的位置，恢复后的填充了的消息MP’便是MR’中奇数位置上z个最低有
效字节组成的串。

MP’=m2z-1‖m2z-3‖…m2i-1‖…m3‖m1

指数r恢复成第1个非零和的最低有效半字节的值。

如果指数r不取1到8之间的值，或MP’的r-1个最高有效位不全为0，则签名Σ将被拒绝。

m2z-1=（r－1个填充的0）‖（9－r个信息位）

消息被恢复成MP’的8z+1-r个最低有效位组成的串。

6.3冗余校验

当且仅当MR’的ks－1个最低有效位等于由恢复后的填充了的消息MP’，按照5.2和5.3计算
出的带冗余的扩展后的消息的ks－1个最低有效位时，签名Σ才被接受。

附录A

（提示的附录）

用于数字签名的公开密钥体制例子

一定义

模数modulus

两个素数的乘积构成的整数。

公开验证密钥publicverificationkey

模数和验证指数。

秘密签名密钥secretsignaturekey

签名指数

二符号和缩略语

RR代表元素

IS合成整数

n模数

k模数的比特长度

p,q模数的素因子

v验证指数

s签名指数

lcm(a,b)整数a和b的最小公倍数

（a∣n）a关于n的雅可比（Jacobi）符号

注：设p是奇素数,并设a是一个正整数，则整数a关于素数p的勒让德（Legendre）符号用下
列式子定义:

（a∣p）=a(p-1)/2modp

当a不是p的倍数时，则整数a关于素数p的勒让德符号取值为＋1或－1，它取决于整数a是或
不是模p的平方。P的倍数关于素数p的勒让德符号为0。

设n为奇正整数,并设a是一个正整数,整数a关于整数n的雅可比符号等于整数a关于n的素因子
的勒让德符号之乘积。所以,如果n=pq,则（a∣n）＝（a∣p）（a∣q）

任何整数a关于任何整数n的雅可比符号可以有效地计算而无需知道n的素因子。

三密钥产生

A3.1公开验证指数

每个签名实体都应选择一个正整数v作为其公开验证指数。在特定的应用中，公开验证指数
可以标准化。

注：公开验证指数取为2和3会有一些特别的优点。

A3.2秘密的素因子和公开的模数

每个签名实体应当秘密地且随机地选取两个不同的奇素数p和q,它们满足下列条件：

――如果v是奇数，则p-1和q-1都应当与v互素；

――如果v是偶数,则(p-1)/2和(q-1)/2都应当与v互素,且p和q不应当模8同余。

公开模数n就是秘密素因子p和q的乘积。

n=pq

模数的长度为k,k应当等于ks+1。

注

关于素数选取的若干别的条件也应当很好地考虑，以便防止对模数的因子分解。

有些形式的模数有简单的模约简运算且只需少量的存储表。这些形式是

Fx,y－:n=264x－c其长度:k=64x比特，

Fx,y＋:n=264x＋c其长度:k=64x＋1比特，

其中：1≤y≤2x且c<264x-8y<2c。

在负形式中，y个最高有效字节的所有位均是1，其数目可达到模数长度的四分之一。

在正形式中，在取值为1的最高有效位之后，y个最高有效字节的所有位均是0，其数

目可达模数长度的四分之一。

A3.3秘密签名指数

秘密签名指数是使得sv-1为下列数的倍数的最小正整数s：

――1cm(p-1,q-1),若v是奇数；

――1/21cm(p-1,q-1),若v是偶数。

四签名函数

中间整数IR是按5.4所述计算出的k－1比特串。

IR关于n的代表元素记为RR。

――如果v是奇数，则RR就是IR；

――如果v是偶数且（IR∣n）＝＋1，则RR是IR；

――如果v是偶数且（IR∣n）＝－1，则RR是IR/2。

注：如果v是偶数，则RR关于n的雅可比符号强置为＋1。

对RR计算其模n的s次幂，签名∑便是此计算结果或者是其关于n的补，取其中较小者。

∑＝min{RRsmodn,n-(RRsmodn)

这就定义了签名函数“Sign”。

∑＝Sign(IR)

五验证函数

签名∑是小于n/2的正整数，对其进行模n的v次幂以得到合成整数IS。

于是，恢复后的中间整数IR’用下列译码确定：

――如果IS是模16同余6，则IR’就是IS；

――如果n-IS是模16同余6，则IR’是n－IS。

而且，当v是偶数时，

――如果IS是模8同余3，则IR’是2IS；

――如果n-IS是模8同余3，则IR’是2（n－IS）。

所有其他情况，签名∑都应被拒绝，而且，如果IR’不落在2k-2到22k-1－1范围内，

签名也应被拒绝。

这便定义了验证函数“Verif”。

IR’=Verif(∑)

附录B

（提示的附录）

关于附录A（提示的附录）的说明实例

（使用十六进制记法）

一公开指数为3的例子

B1.1密钥产生

公开验证指数v为3。

所以秘密素因子都是模3余2。

p=BA09106C754EB6FEBBC214799FF1B8DE

1B4CBB7A7A782B157C1BC15290A1A3AB

q=16046EB39E03BEAB621D03C08B8AE6B66

CFF955B64B4F48B7EE152A326BF8CB25

513比特的公开模数n具有形式2512＋c，其中2c>2384>c(形式Fx,y,＋其x=8,y=16)。

n=pq=100000000000000000000000000000000

BBA2D15DBB303C8A21C5EBBCBAE52B71

25087920DD7CDF358EA119FD66FB0640

12EC8CE692F0A0B8E8321B041ACD40B7

秘密签名指数s为（n-p-q+3）/6。

s=2AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

C9F0783A49DD5F6C5AF651F4C9D0DC92

81C96A3F16A85F9572D7CC3F2D0F25A9

CBF1149E4CDC32273FAADD3FDA5DCDA7

B1.2变量的长度

z是小于或等于（k＋2）/16的正整数，t是小于或等于（k+13）/16的最大整数。

因而，当k为513时，

――z取值从1到32，待签名的消息为1到256比特的串,填充后的消息MP和MP’为1到32字节的
串；

――t为32，扩展后的消息ME为32字节的串，带冗余的消息MR和MR’为64字节的串。

而且，中间整数IR和IR’及签名Σ都是512比特（k－1个比特）的串。

B1.3例1

本例说明了对100比特消息签名的填充、扩展和截取过程。该消息为：

CBBAA99887766554433221100

签名进程

在左边填充了四个0以后，填充后的消息MP便是13字节的串，所以z＝13，r＝5。

MP＝OCBBAA99887766554433221100

通过将MP的13个相连字节不断重复，依次排在左边，直至达到32个字节的串，便构成扩展后
的消息ME。

ME＝5544332211000CBBAA99887766554433

2211000CBBAA99887766554433221100

带冗余的扩展后的消息MR是一个64字节的串，它是通过将ME的32个字节和冗余的32个字节交
替排列而得到的，第26个字节的修改（E2）给出了消息边界的编码。

MR＝44559944883355223311EE00E70C66BB

BBAADD990088FF772266445599448833

55223311EE00E20C66BBBBAADD990088

FF77226644559944883355223311EE00

中间整数IR是从MR通过下列方法得到的：截取511个比特，左边填充一个1，最低有效字节予
以替代，即μ2‖μ1＝00代之以μ1‖6＝06。因为v是奇数，所以代表元素RR便是IR。

RR＝IR＝C4559944883355223311EE00E70C66BB

BBAADD990088FF772266445599448833

55223311EE00E20C66BBBBAADD990088

FF77226644559944883355223311EE06

对RR计算其模n的s次幂，此处，签名Σ便是该计算结果关于n的补。

Σ＝309F873D8DED8379490F6097EAAFDABC

137D3EBFD8F25AB5F138D56A719CDC52

6BDD022EA65DABAB920A81013A85D092

E04D3E421CAAB717C90D89EA45A8D23A

验证进程

签名Σ小于n/2，通过对Σ计算其模n的3次幂得到合成整数IS。

IS＝3BAA66BB77CCAADDCCEE11FF18F39944

FFF7F3C4BAA73D12FF5FA76721A0A33D

CFE6460EEF7BFD2927E55E52896205B7

13756A804E9B07745FFEC5E1E7BB52B1

中间整数是512比特的串，其中最高有效位是1且最低有效半字节的值为6，因为n在这里是模
16余7且IS是模16余1，所以恢复后的中间整数IR’是n－IS。

1R’＝n-IS=C4559944883355223311EE00E70C66BB

BBAADD990088FF772266445599448833

55223311EE00E20C66BBBBAADD990088

FF77226644559944883355223311EE06

恢复后的带冗余的消息MR’在这里便是64字节的串，其中，在一个填充的0后，接着便是
IR’的511个最低有效位，但最低有效字节例外，按照置换P中P（0）＝E的说明，用μ4
‖
μ4‖μ2‖6表示的EE06将代之以m4‖m3‖?－1（m4）‖m2，其值为EE00。

MR’=44559944883355223311EE00E70C66BB

BBAADD990088FF772266445599448833

55223311EE00E20C66BBBBAADD990088

FF77226644559944883355223311EE00

第1个非零和是第13个和，值为5，这样z＝13而r＝5，恢复后的填充了的消息MP’就是MR’
的最低有效奇数位置中13个字节的串。

MP’＝0CBBAA99887766554433221100

MP’的四个最高有效位（r-1=4）为0，因此消息本身就恢复为MP’的100个最低有效位
（8z+1-r=100）的串。

CBBAA99887766554433221100

这个签名是可被接受的，审因为恢复后的带冗余的消息MR’的511个最低有效位和由MP’计
算出的带冗余的扩展后的消息中的一样，而这种计算方法和由MP计算出MR的完全一样。

B1.4例2

本例说明了一种更简单的情况：256比特的消息对于513比特的模数既不需要填充也不需要扩
展。

FEDCBA9876543210FEDCBA9876543210

FEDCBA9876543210FEDCBA9876543210

签名进程

消息为256比特，恰恰编成32字节，所以z＝32而r=1，该消息就是填充后的消息MP，也是扩
展后的消息ME。

ME＝MP＝FEDCBA9876543210FEDCBA9876543210

FEDCBA9876543210FEDCBA9876543210

扩展后的带冗余的消息MR是64字节的串。

MR＝1DFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

通过对MR截取511比特，左边填充一个1以及替代最低有效字节便得到中间整数IR。因为v是
奇数，代表元素RR为IR。

RR＝IR＝9DFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E06

对RR计算其模n的s次幂，签名?在这里便是该计算结果。

Σ＝319BB9BECB49F3ED1BCA26D0FCF09B0B

0A508E4D0BD43B350F959B72CD25B3AF

47D608FDCD248EADA74FBE19990DBEB9

BF0DA4B4E1200243A14E5CAB3F7E610C

验证进程

签名Σ小于n/2,通过对Σ计算其模n的3次幂便得到合成整数IS。因为此处IS是模16余1，因
此恢复后的中间整数IR’就是IS。

IR’=IS=9DFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E06

恢复后的带冗余的消息MR’便是64字节的串，其中，在一个填充的0后接着是IR’的511个最
低有效位，但最低有效字节例外，按照置换P中P（1）＝3的说明，由m4‖m3‖m2
‖6表
示的3E06代之以m4‖m3‖?－1（m4）‖m2，其值为3E10。

MR’＝1DFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

第1个非零和是第32个和，其值为1，这样z=32且r＝1。恢复后的填充了的消息MP’是MR’中
奇数位置上的32字节的串。

MP’＝FEDCBA9876543210FEDCBA9876543210

FEDCBA9876543210FEDCBA9876543210

恢复后的消息为256比特的串。

FEDCBA9876543210FEDCBA9876543210

FEDCBA9876543210FEDCBA9876543210

这个签名是可接受的，因为恢复后的带冗余的消息MR’的511个最低有效位和由MP’计算出
的带冗余的扩展后的消息中的一样，这种计算方法和由MP计算出MR的完全一样。

B2公开指数为3的另一个例子

B2.1密钥产生

公开验证指数为3，所以秘密素因子都是模3余2。

p＝461908C5405B7952F69864C3B0683002

5650303D5297A4BD2F549A9D37CFE027

q＝3A6EC260F3E2E0B2C106C51646D471D9E

0478317627010818E54CC26F7C0C892B

512比特的公开模数n具有形式2512－c，其中，2c>2488>c（形式Fx,y，－其
x=8,y=3）。

n=pq=FFFFFF7FA27087C35EBEAD78412D2BDF

FE0301EDD494DF13458974EA89B36470

8F7D0F5A00A50779DDF9F7D4CB80B889

1324DA251A860C4EC9EF288104B3858D

秘密签名指数s为（n-p-q+3）/6。

s=2AAAAA9545BD6BF5E51FC7940ADCDCA5

550080524E18CFD88B96E8D1C19DE612

1B13FAC0EB0495D47928E047724D91D1

740F6968457CE53EC8E24C9362CE84B5

B2.2变量的长度

因为k为512，所以

――z取值为1到32，待签名消息为1到256比特的串，填充后的消息MP和MP’是1到32字节
的
串；

――t为32，扩展后的消息ME为32字节的串，带冗余的消息MR和MR’是64字节的串。

而且，中间整数IR和IR’以及签名?均为511比特（k-1比特）的串。

B2.3例3

本例说明了对100比特消息签名的填充，扩展和截取过程，该消息为：

112233445566778899AABBCCD

签名进程

在左边填充四个0以后，填充后的消息MP为一个13字节的串，所以z=13,r=5。

MP=0112233445566778899AABBCCD

通过将MP的连续13个字节不断重复，依次排在左边，直至得到32字节的串。

ME＝78899AABBCCD0112233445566778899A

ABBCCD0112233445566778899AABBCCD

扩展后的带冗余的消息MR是一个64字节的串，它是通过交替地排列ME的32个字节和冗余的32
个字节得到的，第26字节的修改给消息边界进行编码。

MR＝F0780D89DB9AB6AB67BC7ACDE3013512

58238934944542562F67F0780D89DB9A

B6AB67BC7ACDE6013512582389349445

42562F67F0780D89DB9AB6AB67BC7ACD

中间整数IR是通过下列方法从MR得到的：先截取其510比特，再在左边填充一个1，最后替代
最低有效字节：m2‖m1＝CD代之以m1‖6＝D6。因为v是奇数，所以代表元素RR为IR。

RR＝IR＝70780D89DB9AB6AB67BC7ACDE3013512

58238934944542562F67F0780D89DB9A

B6AB67BC7ACDE6013512582389349445

42562F67F0780D89DB9AB6AB67BC7AD6

对RR计算其模n的s次幂，此处?便是该结果关于n的补。

S＝58E59FFB4B1FB1BCDBF8D1FE9AFA3730

C78A318A1134F5791B7313D480FF07AC

319B068EDF8F212945CB09CF33DF30AC

E54F4A063FCCA0B732F4B662DC4E2454

验证进程

签名?小于n/2，对?计算其模n的3次幂就得到合成整数IS。

IS＝8F87F1F5C6D5D117F70232AA5E2BF6CD

A5DF78B9404F9CBD162184727C2988D5

D8D1A79D85D72178A8E79FB1424C2443

D0CEAABD2A0DFEC4EE5471D59CF70AB7

中间整数是511比特的串,其中最高有效位为1，最低有效半字节的值为6。因为此外n是模16
余13，IS是模16余7，所以恢复后的中间整数IR’为n-IS。

IR’＝N－IS＝70780D89DB9AB6AB67BC7ACDE3013512

58238934944542562F67F0780D89DB9A

B6AB67BC7ACDE6013512582389349445

42562F67F0780D89DB9AB6AB67BC7AD6

恢复后的带冗余的消息MR’，便是64字节的串，其中在两个填充的0后接着是IR’的510个最
低有效位，但最低有效字节例外，按照置换?中?（c）＝7的说明，由m4‖m3‖m
2‖6
表示的7AD6被m4‖m3‖?－1（m4）‖m2代替，其值为7ACD。

MR’＝30780D89DB9AB6AB67BC7ACDE3013512

58238934944542562F67F0780D89DB9A

B6AB67BC7ACDE6013512582389349445

42562F67F0780D89DB9AB6AB67BC7ACD

第1个非零和是第13个和，其值为5，这样，z=13,r=5,恢复后的填充了的消息MP’便是MR’
的最低有效奇数位置上13个字节的串。

MP’＝0112233445566778899AABBCCD

MP’的四个最高有效位（r-1=4）为0，消息本身便恢复为MP’的100个最低有效位（8z＋1-
r=100）的串。

112233445566778899AABBCCD

这签名是可接受的，因为恢复后的带冗余的消息MR’的510个最低有效位和由MP’

计算出的带冗余的扩展后的消息中的一样，这种计算方法和由MP计算出MR的完全相同。

三公开指数为2的例子

B3.1密钥产生

公开验证指数v为2，所以，一个素因子为模8余3，另一个为模8余7。

P=867EA672E46B2B0A35F2F2F2719A1F3C

7EA059472B9DAE51A1730A282CDDBBE3

q=1E7468E3C4869473F094E740660B04CB4

8E47FB50196544DCC81D44928301850F

513位公开模数n具有形式2512＋c,其中2c>2384>c(形式Fx,y,+其x=8,y=16)。

n=pq=100000000000000000000000000000000

97518F6AD742E4E3A1EDC7F6CB0F2226

F13439524E5466C2D596A9F9760FAD26

743E5D43D9AAA91EF0368F22B87DF14D

秘密签名指数s为（n-p-q+5）/8。

S=20000000000000000000000000000000

12EA31ED5AE85C9C743DB8FED961E444

906DE094642FFE8F32CAA8601478A826

ACEAC1159294F6BE10D4C80D0113D60C

B3.2变量的长度

因为k为513，所以

――z取值为1到32，待签名消息为1到256比特的串，填充后消息MP和MP’都为1到32字节的
串；

――t为32，扩展后消息ME为32字节的串，带冗余的消息MR和MR’均为64字节的串。而且，
中间整数IR和IR’以及签名?均为512比特（k－1比特）的串。

B3.3例4

本例说明了带强置雅可比符号的256比特消息的签名。

F123E123D123C123B123A12391238123

612351234123312321231123O123
签名进程

消息为256比特的串，恰好编码成32字节，所以z＝32，r=1，填充后消息MP，扩展后消息ME
和该消息相同。

ME＝MP＝F123E123D123C123B123A12391238123

7123612351234123312321231123O123

带冗余的扩展后的消息MR为64字节的串。

MR＝12F15823C3E15823A3D1582373C15823

63B15823B3A15823D391582303815823

F3715823236158234351582393415823

833158235321582333115823E3015823

通过截取MR的511比特，左边填充一个1，替代最低有效字节便得到中间整数IR。

1R＝92F15823C3E15823A3D1582373C15823

63B15823B3A15823D391582303815823

F3715823236158234351582393415823

833158235321582333115823E3015836

因为IR关于n的雅可比符号为－1，所以代表元素RR为IR’/2。

RR＝IR’/2=4978AC11E1F0AC11D1E8AC11B9E0AC11

B1D8AC11D9D0AC11E9C8AC1181C0AC11

F9B8AC1191B0AC11A1A8AC11C9A0AC11

C198AC11A990AC119988AC11F180AC1B

对RR计算其模n的s次幂,此处签名?就是该计算结果。

?＝6BA03660D7A9001D533B01A605CAFD2A

1352E0D78776623C926FF2043B93E12B

E7D097AE506248153024E3C17CFA565D

F4F76FF2EC19C5079D11C723F0CE5071

验证进程

签名?小于n/2，对?计算模n平方得到合成整数IS。

IS＝04978AC11E1F0AC11D1E8AC11B9E0AC11

B1D8AC11D9D0AC11E9C8AC1181C0AC11

F9B8AC1191B0AC11A1A8AC11C9A0AC11

C198AC11A990AC119988AC11F180AC1B

因为此处IS是模16余11，所以恢复后的中间整数IR’为2IS。

1R’＝2IS＝92F15823C3E15823A3D1582373C15823

63B15823B3A15823D391582303815823

F3715823236158234351582393415823

833158235321582333115823E3015836

恢复后的带冗余的消息MR’除了最高有效位强置成0以及最低有效字节被替代外（P－1
（5）＝2），与IR’的相同。

MR’＝12F15823C3E15823A3D1582373C15823

63B15823B3A15823D391582303815823

F3715823236158234351582393415823

833158235321582333115823E3015823

第1个非零和是第32个和，其值为1，这样，z=32,r=1,恢复后的填充了的消息MP’是MR’奇
数位置上的32字节串。

MP’＝F123E123D123C123B123A12391238123

71236123512341233123212311230123

恢复后的消息就是256比特的串。

F123E123D123C123B123A12391238123

71236123512341233123212311230123

这个签名是可接受的，因为恢复后的带冗余的消息MR’的511个最低有效位和由MP’计算出
的带冗余的扩展后的消息中的一样，这种计算方法和由MP计算出MR的完全相同。

B3.4例5

最后这个例子说明了不需要强置雅可比符号的256比特消息的签名情况。

FEDCBA9876543210FEDCBA9876543210

FEDCBA9876543210FEDCBA9876543210

签名进程

消息是256比特的串，恰好编成32字节，所以z=32,r=1,填充后的消息MP和扩展后的消息ME都
是该消息。

ME＝MP＝FEDCBA9876543210FEDCBA9876543210

FEDCBA9876543210FEDCBA9876543210

带冗余的扩展后的消息MR是64字节的串。

MR＝1DFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

通过截取MR的511比特，左边填充一个1替代最低有效字节就得到中间整数IR。由于IR关于n
的雅可比符号为＋1，所以此处IR就是代表元素RR。

RR＝1R＝9DFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E06

对RR计算其模n的s次幂，结果便是签名?。

?＝28910D1F0FC8332A63AFE10A37848404

84374DF9D0A92347DD1966E5976823EC

597A1AEC0D24FE710934D49B0CB0412F

E8A10CB0D39D1C06207B0000E9F33021

验证进程

签名?小于n/2，通过对?计算模n平方得到合成整数IS。

由于IS是模16余6，所以此处IS就是恢复后的中间整数IR’。

1R’＝IS’＝9DFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E06

恢复后的带冗余的消息MR’是64字节的串，它和IR’相同，但最高有效位需强置成0，最低
有效字节被替代掉（P－1（3）＝1）。

MR’＝1DFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

1CFEA7DC6BBAD098F276495485323E10

第1个非零和是第32个和，其值为1，这样，z=32,r=1。

恢复后的填充了的消息MP’就是MR’的奇数位置上32个字节的串。

MP’＝FEDCBA9876543210FEDCBA9876543210

FEDCBA9876543210FEDCBA9876543210

恢复后的消息便是256比特的串。

FEDCBA9876543210FEDCBA9876543210

FEDCBA9876543210FEDCBA9876543210

这个签名是可接受的，因为恢复后的带冗余的消息MR’的511个最低有效位和由MP’计算出
的带冗余的扩展后的消息中的一样，这种计算方法和由MP计算出MR的完全相同。

附录C

（提示的附录） 为抵抗对附录A（提示的附录）各种潜在攻击所采取的若干预防措施

一秘密函数的合法自变量

函数“模n的s次幂”’的唯一的合法自变量就是代表元素。

如果v是奇数，所有代表元素都是k-1比特的串，其中最高有效位的值为1，最低有效半字节
的值为6。

如果v是偶数，则代表元素关于模数n的雅可比符号强置为＋1且所有的代表元素都是下列情
况之一：

――若（IR∣n）=+1,则代表元素为k-1比特串，其中最高有效位的值为1，最低有效半字节
的值为6；

――若（IR∣n）=－1，则代表元素为k-2比特串，其中最高有效位的值是1，三个最低有效
位组成的串的值为3。

二四种运算的排除

由于代表元素的这种结构特性，下面四种运算可以不予考虑。

注：这些材料取自Eurocrypt90的一篇通信（见附录D（提示的附录）），该研讨会于1990年
5月21日至24日在丹麦的Arhus举行。

平移

代表元素的比特串编码不可能平移成另一个代表元素。

求补

代表元素的比特串编码不可能经求补后变成另一个代表元素。

普通乘法

代表元素与常数的变通乘积（即不进行模约简）不可能是另一个代表元素。

普通方幂

任何常数的普通v次幂（即不进行模约简）不可能是一个代表元素。

事实上，模16余6的整数不可能是某一数的幂；模8余3的数也不可能是某一数的偶次幂。

附灵D

（提示的附录）

参考文献

PrecautionstakenagainstvariouspotentialattacksinISO/IEC
9796,Digital
ignatureschemegivingmessagerecovery,LouisGUILLOU,Jean-Jacques
QUISQUATER,MikeWALKER,PeterLANDROCK,CarolineSHAER,Proceedingsof
Eurocrypt’
90,editedbylvanDAMGARDandpublishedbySpringer-Verlaginthe
series
“LectureNotesinComputerScience”,Vol473,pp465-473.