信息技术安全技术带消息恢复的数字签名方案

《信息技术安全技术带消息恢复的数字签名方案》由会员分享，可在线阅读，更多相关《信息技术安全技术带消息恢复的数字签名方案（25页珍藏版）》请在装配图网上搜索。

1、信息技术安全技术带消息恢复的数字签名方案 一 范围 本标准规定了对有限长消息使用公开密钥体制的带消息恢复的数学签名方案。 这种数学签名方案包含下列两个进程： ――签名进程，它使用秘密签名密钥和签名函数来对消息签名； ――验证进程，它使用公开验证密钥和验证函数来验证签名，同时恢复出消息。 签名进程中，必要时，欲签名的消息需填充和扩展，然后加上与消息本身有关的人为的冗余，对消息中是否存在自然的冗余不作假定。这人为的冗余将由验证进程揭示出来，把这人为的冗余去掉便恢复出消息。 本标准不规定密钥产生进程、签名函数和验证函数。附录A（提示的附录）给出了

2、一个公开密钥体制的例子，包含密钥产生、签名函数和验证函数。附录B（提示的附录）通过例子来说明这些操作的各步。 这个方案中的若干参数与安全性有关：本标准不规定为要达到给定的安全性水平而对这些参数应取什么值。然而以这样一种方式规定，即在本标准使用中，如果这些参数中有的必须要改变时，使所作的改变最小。 二 定义 本标准采用下列定义 2.1消息 message 有限长的比特串。 2.2签名 signature 由签名进程最后得到的比特串。 三 符号和缩略语 MP 填充后的消息 ME 扩展后的消息 MR 带冗余的扩展

3、后的消息 IR 中间整数 ∑ 签名 Ks 签名的比特数 IR’ 恢复后的中间整数 MR’ 恢复后的带冗余的消息 MP’ 恢复后的填充了的消息 Sign 秘密签名密钥控制下的签名函数 Verif 公开验证密钥控制下的验证函数 mod z 模z的算术计算 μ 半字节 П 半字节置换 m 字节 S 字节的影子 X‖Y X和Y两个比特串的级联 X⊕Y X和Y两个比特串的异或 注： 1所有整数（比特串或字节串）其最高有效数字（位或字节）在左边。 2表1和附录B（

4、提示的附录）中采用了0到9和A到F的十六进制记法。 四 概述 下面两章规定： ――第5章中的签名进程； ――第6章中的验证进程 每个签名实体应使用其自己的对应于公开验证密钥的签名密钥并将其保密。 如有必要，欲签名的消息应当填充和扩展，然后按照第5章规定的规则加上冗余，对此带冗余的扩展消息，如第5章规定的那样，用秘密签名密钥计算其签名。 每个验证实体都会知道并使用该签名实体特定的公开验证密钥，当且仅当第6章规定的验证进程获得成功，签名才是可接受的。 注：密钥的产生与分配已超出本标准的范围。 五 签名进程 图1概括了这

5、种签名进程。 图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的最大

6、整数的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的

7、第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

8、 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

9、 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签名开启 在公开验证密钥的控制下，通过对签名Σ应用验证函数将其

10、变换成恢复后的中间整数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的

11、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，则签名Σ将被拒

12、绝。 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 模数和验证指数。 秘密签名

13、密钥 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或－

14、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秘密的素因子和公开的模数 每个签名实

15、体应当秘密地且随机地选取两个不同的奇素数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＋

16、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

17、的代表元素记为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。 于是

18、，恢复后的中间整数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（提示的附录）的说明实例

19、 （使用十六进制记法） 一 公开指数为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)。

20、 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 72

21、D7CC3F 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

22、比特消息签名的填充、扩展和截取过程。该消息为： 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 带冗余

23、的扩展后的消息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代

24、之以μ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 F1

25、38D56A 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

26、 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后

27、，接着便是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，恢复后的

28、填充了的消息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

29、比特的模数既不需要填充也不需要扩展。 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＝1

30、DFEA7DC 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 85323E

31、10 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 　 验证进程 签名Σ

32、小于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

33、 （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

34、’＝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密钥

35、产生 公开验证指数为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 412D

36、2BDF 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 C8E24C

37、93 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以后

38、，填充后的消息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

39、 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 2F67F

40、078 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 　 验

41、证进程 签名? 小于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＝70

42、780D89 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’＝3

43、0780D89 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’

44、的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

45、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

46、 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

47、，扩展后消息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

48、 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 C3

49、E15823 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 A1A8AC1

50、1 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 497

51、8AC11 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

52、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个和，

53、其值为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’计算出的带冗余的扩展后的消息中的

54、一样，这种计算方法和由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 FE

55、DCBA98 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 6B

56、BAD098 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 E

57、8A10CB0 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’

58、是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’＝ FEDC

59、BA98 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 （提示的附录） 为抵抗对

60、附录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。 二 四种

61、运算的排除 由于代表元素的这种结构特性，下面四种运算可以不予考虑。 注：这些材料取自Eurocrypt90的一篇通信（见附录D（提示的附录）），该研讨会于1990年5月21日至24日在丹麦的Arhus举行。 　 平移 代表元素的比特串编码不可能平移成另一个代表元素。 　 求补 代表元素的比特串编码不可能经求补后变成另一个代表元素。 　 普通乘法 代表元素与常数的变通乘积（即不进行模约简）不可能是另一个代表元素。 　 普通方幂 任何常数的普通v次幂（即不进行模约简）不可能是一个代表元素

62、。 事实上，模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.