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

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

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

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

3、钥控制下的签名函数 Verif 公开验证密钥控制下的验证函数 mod z 模z的算术计算 半字节 半字节置换 m 字节 S 字节的影子 XY X和Y两个比特串的级联 XY X和Y两个比特串的异或 注： 1所有整数（比特串或字节串）其最高有效数字（位或字节）在左边。 2表1和附录B（提示的附录）中采用了0到9和A到F的十六进制记法。 四 概述 下面两章规定： 第5章中的签名进程； 第6章中的验证进程 每个签名实体应使用其自己的对应于公开验证密钥的签名密钥并将其保密。 如有必要，欲签名的消息应当填充和扩展，然后按照第5章规定的规则加上冗余，对此带冗余的扩展消息，如第5章规定的那样，用秘密签名密钥计

4、算其签名。 每个验证实体都会知道并使用该签名实体特定的公开验证密钥，当且仅当第6章规定的验证进程获得成功，签名才是可接受的。 注：密钥的产生与分配已超出本标准的范围。 五 签名进程 图1概括了这种签名进程。 图1签名进程 注：这种签名进程较好的实现方法应当对这些操作加以物理保护，使得无法对秘密签名密钥控制下的签名函数进行直接访问。 5.1填充 消息是一个比特串，在其左边添上0到7个0以便获得一个z字节的串。指数r（后面将用到）是填充0的数目加1，因此r的值为1到8。 从而，在填充后的消息MP中，8z1r个最低有效位是信息位。 MPmzmz-1m2m1 Mz= (r-1个填充的0 )(9-r个信

5、息位) z乘上16后的数应小于或等于ks3。因此待签名消息的比特数最多应是小于或等于（ks3）/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字节。 MEmzmzm1 T字节 注：数z小于或等于t，只有当ks模16同余于13、14、15、0或1时，两者才可能相等。 5.3冗余 通过交替地将ME的t字节放在奇数位置上，将t字节冗余放在偶数位置上便得到带冗余的

6、扩展后的消息MR。MR的第2z 字节的低半字节经指数r对其修改后，便由其值和位置对消息长度进行了编码。 对i从1到t, MR的第（2i-1）字节等于ME的第i字节； MR的第2i字节等于ME的第i字节按表1规定的影子S的像，但第2z字节例外，它等于ME的第z字节的影子与指数r异或的结果。 MRS（mz）rmzS（m2）m2S（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修改

7、。mr2z :rmr2z。 5.4截取和强置 中间整数IR是用ks比特串来编码的，其最高有效位为1，ks 1个最低有效位便是MR的ks 1个最低有效位，但最低有效字节被替代了，如果21是MR的最低有效字节，则IR的最低有效字节是16。 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四比特组成，在置换下的像用（）表示，则为a4a2a11；a4a3a11；a4a3a21；a3a

8、2a1 。 如果字节m由两个半字节21组成，在影子S下的像用S(m)表示，则为(2)(1) 六 验证进程 图2验证进程 图2概括了验证进程。 6.1签名开启 在公开验证密钥的控制下，通过对签名应用验证函数将其变换成恢复后的中间整数IR。 IR=Verif() 如果IR不是一个最高有效位为1和最低有效半字节为6的ks比特串，则该签名将被拒绝。 6.2消息恢复 恢复后的带冗余的消息MR是一个2t字节串，其（1ks）(mo16)个最高有效位为0，而ks1个最低有效位便是IR的ks1人最低有效位，但最低有效字节需被替代。按照表1中规定的置换，如果1236是IR 的最低有效四个半字节，则MR的最低有效字

9、节应是1(4)2 。 MRm2tm2t-1m2m1 注：MR和MR这两串可能不等，MR是由MR的ks1个最低有效位且在其最高有效位填充了0到15个0后组成的。 从MR的2t个字节，计算出t个和，按照表1中规定的影子S，第i个和等于第2i个字节与第（2i1）个字节的影子的异或。 m2iS(m2i-1) 如果t个和都是0，则签名将被拒绝。 Z恢复成第1个非零和的位置，恢复后的填充了的消息MP便是MR中奇数位置上z个最低有效字节组成的串。 MP=m2z-1m2z-3m2i-1m3m1 指数r恢复成第1个非零和的最低有效半字节的值。 如果指数r不取1到8之间的值，或MP的r-1个最高有效位不全为0，则

10、签名将被拒绝。 m2z-1=（r1个填充的0）（9r个信息位） 消息被恢复成MP的8z+1-r个最低有效位组成的串。 6.3冗余校验 当且仅当MR的ks1个最低有效位等于由恢复后的填充了的消息MP，按照5.2和5.3计算出的带冗余的扩展后的消息的ks1个最低有效位时，签名才被接受。 附录A （提示的附录） 用于数字签名的公开密钥体制例子 一 定义 模数 modulus 两个素数的乘积构成的整数。 公开验证密钥 public verification key 模数和验证指数。 秘密签名密钥 secret signature key 签名指数 二 符号和缩略语 RR 代表元素 IS 合成整数 n

11、模数 k 模数的比特长度 p,q 模数的素因子 v 验证指数 s 签名指数 lcm(a,b) 整数a和b的最小公倍数 （an） a关于n的雅可比（Jacobi）符号 注：设p是奇素数,并设a是一个正整数，则整数a关于素数p的勒让德（Legendre）符号用下列式子定义: （ap）=a(p-1)/2modp 当a不是p的倍数时，则整数a关于素数p的勒让德符号取值为1或1，它取决于整数a是或不是模p的平方。P的倍数关于素数p的勒让德符号为0。 设n为奇正整数,并设a是一个正整数,整数a关于整数n的雅可比符号等于整数a关于n的素因子的勒让德符号之乘积。所以,如果n=pq,则（an）（ap）（aq）

12、任何整数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。 注 关于素数

13、选取的若干别的条件也应当很好地考虑，以便防止对模数的因子分解。 有些形式的模数有简单的模约简运算且只需少量的存储表。这些形式是 Fx,y:n=264xc其长度:k=64x比特， Fx,y:n=264xc其长度:k=64x1比特， 其中：1y2x且c264x-8y2384c(形式Fx,y,其x=8,y=16)。 n=pq=1 00000000 00000000 00000000 00000000 BBA2D15D BB303C8A 21C5EBBC BAE52B71 25087920 DD7CDF35 8EA119FD 66FB0640 12EC8CE6 92F0A0B8 E8321B04 1A

14、CD40B7 秘密签名指数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是小于或等于（k2）/16的正整数，t是小于或等于（k+13）/16的最大整数。 因而，当k为513时， z取值从1到32，待签名的消息为1到256比特的串,填充后的消息MP和MP为1到32字节的串； t为32，扩展后的消息ME

15、为32字节的串，带冗余的消息MR和MR为64字节的串。 而且，中间整数IR和IR及签名都是512比特（k1个比特）的串。 B1.3例1 本例说明了对100比特消息签名的填充、扩展和截取过程。该消息为： CBBAA 9988 7766 5544 3322 1100 签名进程 在左边填充了四个0以后，填充后的消息MP便是13字节的串，所以z13，r5。 MPOC BBAA9988 77665544 33221100 通过将MP的13个相连字节不断重复，依次排在左边，直至达到32个字节的串，便构成扩展后的消息ME。 ME55443322 11000CBB AA998877 66554433 2211

16、000C BBAA9988 77665544 33221100 带冗余的扩展后的消息MR是一个64字节的串，它是通过将ME的32个字节和冗余的32个字节交替排列而得到的，第26个字节的修改（E2）给出了消息边界的编码。 MR44559944 88335522 3311EE00 E70C66BB BBAADD99 0088FF77 22664455 99448833 55223311 EE00E20C 66BBBBAA DD990088 FF772266 44559944 88335522 3311EE00 中间整数IR是从MR通过下列方法得到的：截取511个比特，左边填充一个1，最低有效字节予

17、以替代，即2100代之以1606。因为v是奇数，所以代表元素RR便是IR。 RRIRC4559944 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 A

18、65DABAB 920A8101 3A85D092 E04D3E42 1CAAB717 C90D89EA 45A8D23A 验证进程 签名小于n/2，通过对计算其模n的3次幂得到合成整数IS。 IS3BAA66BB 77CCAADD CCEE11FF 18F39944 FFF7F3C4 BAA73D12 FF5FA767 21A0A33D CFE6460E EF7BFD29 27E55E52 896205B7 13756A80 4E9B0774 5FFEC5E1 E7BB52B1 中间整数是512比特的串，其中最高有效位是1且最低有效半字节的值为6，因为n在这里是模16余7且IS是模16余1，

19、所以恢复后的中间整数IR是nIS。 1Rn-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的说明，用4426表示的EE06将代之以m 4m 3? 1（m 4）m 2，其值为EE00。 MR=44559

20、944 88335522 3311EE00 E70C66BB BBAADD99 0088FF77 22664455 99448833 55223311 EE00E20C 66BBBBAA DD990088 FF772266 44559944 88335522 3311EE00 第1个非零和是第13个和，值为5，这样z13而r5，恢复后的填充了的消息MP就是MR的最低有效奇数位置中13个字节的串。 MP0C BBAA9988 77665544 33221100 MP的四个最高有效位（r-1=4）为0，因此消息本身就恢复为MP的100个最低有效位（8z+1-r=100）的串。 C BBAA9988

21、 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字节，所以z32而r=1，该消息就是填充后的消息MP，也是扩展后的消息ME。 MEMPF

22、EDCBA98 76543210 FEDCBA98 76543210 FEDCBA98 76543210 FEDCBA98 76543210 扩展后的带冗余的消息MR是64字节的串。 MR1DFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 通过对MR截取511比特，左边填充一个1以及替代最低有效字节便得到中间整数IR。因为v是奇数，代表元素RR为IR。 RRIR

23、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 A

24、14E5CAB 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

25、（1）3的说明，由m 4m 3m 26表示的3E06代之以m 4m 3? 1（m 4）m 2，其值为3E10。 MR1DFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 第1个非零和是第32个和，其值为1，这样z=32且r1。恢复后的填充了的消息MP是MR中奇数位置上的32字节的串。 MPFEDCBA98 76543210 FEDCBA98 76543210 FE

26、DCBA98 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 56503

27、03D 5297A4BD 2F549A9D 37CFE027 q3 A6EC260F 3E2E0B2C 106C5164 6D471D9E 04783176 27010818 E54CC26F 7C0C892B 512比特的公开模数n具有形式2512c，其中，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

28、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以

29、及签名? 均为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字节的串。 ME78899AAB BCCD0112 23344556 6778899A ABBCCD01 12233445 56677889 9AABBCCD 扩展后的带冗余的消息MR是一

30、个64字节的串，它是通过交替地排列ME的32个字节和冗余的32个字节得到的，第26字节的修改给消息边界进行编码。 MRF0780D89 DB9AB6AB 67BC7ACD E3013512 58238934 94454256 2F67F078 0D89DB9A B6AB67BC 7ACDE601 35125823 89349445 42562F67 F0780D89 DB9AB6AB 67BC7ACD 中间整数IR是通过下列方法从MR得到的：先截取其510比特，再在左边填充一个1，最后替代最低有效字节：m 2m 1CD代之以m 16D6。因为v是奇数，所以代表元素RR为IR。 RRIR7078

31、0D89 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 32F

32、4B662 DC4E2454 验证进程 签名? 小于n/2，对? 计算其模n的3次幂就得到合成整数IS。 IS8F87F1F5 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。 IRNIS70780D89 DB9AB6AB 67

33、BC7ACD E3013512 58238934 94454256 2F67F078 0D89DB9A B6AB67BC 7ACDE601 35125823 89349445 42562F67 F0780D89 DB9AB6AB 67BC7AD6 恢复后的带冗余的消息MR，便是64字节的串，其中在两个填充的0后接着是IR的510个最低有效位，但最低有效字节例外，按照置换? 中? （c）7的说明，由m 4m 3m 26表示的7AD6被m 4m 3? 1（m 4）m 2代替，其值为7ACD。 MR30780D89 DB9AB6AB 67BC7ACD E3013512 58238934 944542

34、56 2F67F078 0D89DB9A B6AB67BC 7ACDE601 35125823 89349445 42562F67 F0780D89 DB9AB6AB 67BC7ACD 第1个非零和是第13个和，其值为5，这样，z=13,r=5,恢复后的填充了的消息MP便是MR的最低有效奇数位置上13个字节的串。 MP01 12233445 56677889 9AABBCCD MP的四个最高有效位（r-1=4）为0，消息本身便恢复为MP的100个最低有效位（8z1-r=100）的串。 1 1223 3445 5667 7889 9AAB BCCD 这签名是可接受的，因为恢复后的带冗余的消息 M

35、R的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具有形式2512c,其中2c 2384 c(形式Fx,

36、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 AC

37、EAC115 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比特（k1比特）的串。 B3.3例4 本例说明了带强置雅可比符号的256比特消息的签名。 F123 E123 D123 C123 B123 A123 9123 8123 6123 5123 4123 3123 2123 1123 O123 签名进程 消息为256比特的

38、串，恰好编码成32字节，所以z32，r=1，填充后消息MP，扩展后消息ME和该消息相同。 MEMPF123E123 D123C123 B123A123 91238123 71236123 51234123 31232123 1123O123 带冗余的扩展后的消息MR为64字节的串。 MR12F15823 C3E15823 A3D15823 73C15823 63B15823 B3A15823 D3915823 03815823 F3715823 23615823 43515823 93415823 83315823 53215823 33115823 E3015823 通过截取MR的511比特

39、，左边填充一个1，替代最低有效字节便得到中间整数IR。 1R92F15823 C3E15823 A3D15823 73C15823 63B15823 B3A15823 D3915823 03815823 F3715823 23615823 43515823 93415823 83315823 53215823 33115823 E3015836 因为IR关于n的雅可比符号为1，所以代表元素RR为IR/2。 RRIR/2=4978AC11 E1F0AC11 D1E8AC11 B9E0AC11 B1D8AC11 D9D0AC11 E9C8AC11 81C0AC11 F9B8AC11 91B0AC1

40、1 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。 IS0 4978AC11 E1F0AC11 D1E8AC11 B9E0A

41、C11 B1D8AC11 D9D0AC11 E9C8AC11 81C0AC11 F9B8AC11 91B0AC11 A1A8AC11 C9A0AC11 C198AC11 A990AC11 9988AC11 F180AC1B 因为此处IS是模16余11，所以恢复后的中间整数IR为2IS。 1R2IS92F15823 C3E15823 A3D15823 73C15823 63B15823 B3A15823 D3915823 03815823 F3715823 23615823 43515823 93415823 83315823 53215823 33115823 E3015836 恢复后的带冗余

42、的消息MR除了最高有效位强置成0以及最低有效字节被替代外（P 1（5）2），与IR的相同。 MR12F15823 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字节串。 MPF123E123 D123C123 B123A123 91238123 71236123 512

43、34123 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

44、 FEDC BA98 7654 3210 签名进程 消息是256比特的串，恰好编成32字节，所以z=32,r=1,填充后的消息MP和扩展后的消息ME都是该消息。 MEMPFEDCBA98 76543210 FEDCBA98 76543210 FEDCBA98 76543210 FEDCBA98 76543210 带冗余的扩展后的消息MR是64字节的串。 MR1DFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BB

45、AD098 F2764954 85323E10 通过截取MR的511比特，左边填充一个1替代最低有效字节就得到中间整数IR。由于IR关于n的雅可比符号为1，所以此处IR就是代表元素RR。 RR1R9DFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E06 对RR计算其模n的s次幂，结果便是签名? 。 ? 28910D1F 0FC8332A 63AFE10A 378484

46、04 84374DF9 D0A92347 DD1966E5 976823EC 597A1AEC 0D24FE71 0934D49B 0CB0412F E8A10CB0 D39D1C06 207B0000 E9F33021 验证进程 签名? 小于n/2，通过对? 计算模n平方得到合成整数IS。 由于IS是模16余6，所以此处IS就是恢复后的中间整数IR。 1RIS9DFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6BBAD098 F2764954 85323E10 1CFEA7DC 6

47、BBAD098 F2764954 85323E06 恢复后的带冗余的消息MR是64字节的串，它和IR相同，但最高有效位需强置成0，最低有效字节被替代掉（P 1（3）1）。 MR1DFEA7DC 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 FED

48、CBA98 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（提示的附录）各种潜在攻击所采取的若干预防措施 一 秘密函数的合法自变量

49、 函数“模n的s次幂”的唯一的合法自变量就是代表元素。 如果v是奇数，所有代表元素都是k-1比特的串，其中最高有效位的值为1，最低有效半字节的值为6。 如果v是偶数，则代表元素关于模数n的雅可比符号强置为1且所有的代表元素都是下列情况之一： 若（IRn）=+1,则代表元素为k-1比特串，其中最高有效位的值为1，最低有效半字节的值为6； 若（IRn）=1，则代表元素为k-2比特串，其中最高有效位的值是1，三个最低有效位组成的串的值为3。 二 四种运算的排除 由于代表元素的这种结构特性，下面四种运算可以不予考虑。 注：这些材料取自Eurocrypt90的一篇通信（见附录D（提示的附录），该研讨会于

50、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 Eurocrypt90,edited by lvan DAMGARD and published by Springer-Verlag in the series “Lecture Notes in Computer Science”,Vol 473,pp 465-473.