一 范围

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

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

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

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

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

本标准不规定密钥产生进程、签名函数和验证函数。附录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.