1、中华人民共和国国家标准信息技术安全技术带消息恢复的数字签名方案发布实施国家技术监督局发布前言本标准等同采用国际标准信息技术安全技术带消息恢复的数字签名方案该国际标准规定的对有限长消息进行数字签名的方案适合于我国使用本标准的附录附录附录和附录都是提示的附录本标准由中华人民共和国电子工业部提出本标准由电子工业部标准化研究所归口本标准起草单位电子工业部第三十研究所本标准主要起草人龚奇敏黄月江方关宝雷利民李桂茹前言国际标准化组织和国际电工委员会形成了世界范围内的标准化专门体系或的成员国通过由处理特殊技术活动领域的各个组织所建立的技术委员会来参与国际标准的开发和的技术委员会在共同感兴趣的领域内合作其他与
2、和有联络的官方和非官方国际性组织也参与这项工作在信息技术领域内和已建立了一个联合技术委员会被联合技术委员会接受的国际标准草案送给各成员国表决一个国际标准的发布需要至少的成员国投赞成票国际标准是由信息技术联合技术委员会制定的附录和只作为参考引言电子信息交换中的数字签名和传统邮件中的手写签名十分相似大多数数字签名方案都基于某种公开密钥体制所有公开密钥体制均包含三种基本操作产生密钥对的进程该密钥对由一个秘密密钥和一个公开密钥组成使用秘密密钥的进程使用公开密钥的进程在所有公开密钥数字签名方案中秘密密钥用于消息的签名进程公开密钥用于签名的验证进程因而数字签名方案的密钥对由一个秘密签名密钥和一个公开验证密
3、钥组成明显地有两类数字签名方案当验证进程需要消息作为输入的一部分时该方案称作带附录的签名方案在计算附录中将使用散列函数当验证进程同时揭示消息及其冗余有时称作消息影子时该方案称作带消息恢复的签名方案本标准规定了有限长消息的数字签名方案该数字签名方案的验证进程只需要尽量少的资源它不涉及到使用散列函数从而避免了对这种一般算法的已知攻击消息不一定要用自然语言写可以是任意一种有限长的比特串此类消息的例子有保密密钥材料以及对更长消息进行散列运算后的结果又称为消息印鉴由保密软硬件所产生的几个比特串组成的结构化组便是一个特例其中一个比特串是对该硬件内产生的控制信息编码的结果注本标准的使用可能涉及到某些专利条款
4、中华人民共和国国家标准信息技术安全技术带消息恢复的数字签名方案国家技术监督局批准实施范围本标准规定了对有限长消息使用公开密钥体制的带消息恢复的数字签名方案这种数字签名方案包含下列两个进程签名进程它使用秘密签名密钥和签名函数来对消息签名验证进程它使用公开验证密钥和验证函数来验证签名同时恢复出消息签名进程中必要时欲签名的消息需填充和扩展然后加上与消息本身有关的人为的冗余对消息中是否存在自然的冗余不作假定这人为的冗余将由验证进程揭示出来把这人为的冗余去掉便恢复出消息本标准不规定密钥产生进程签名函数和验证函数附录提示的附录给出了一个公开密钥体制的例子包含密钥产生签名函数和验证函数附录提示的附录通过例子
5、来说明这些操作的各步这个方案中的若干参数与安全性有关本标准不规定为要达到给定的安全性水平而对这些参数应取什么值然而以这样一种方式规定即在本标准使用中如果这些参数中有的必须要改变时使所作的改变最小定义本标准采用下列定义消息有限长的比特串签名由签名进程最后得到的比特串符号和缩略语填充后的消息扩展后的消息带冗余的扩展后的消息中间整数签名签名的比特数恢复后的中间整数恢复后的带冗余的消息恢复后的填充了的消息秘密签名密钥控制下的签名函数公开验证密钥控制下的验证函数模的算术计算半字节半字节置换字节字节的影子的两个比特串的级联和两个比特串的异或注所有整数比特串或字节串其最高有效数字位或字节在左边表和附录提示的
6、附录中采用了到和到的十六进制记法概述下面两章规定第章中的签名进程第章中的验证进程每个签名实体应使用其自己的对应于公开验证密钥的签名密钥并将其保密如有必要欲签名的消息应当填充和扩展然后按照第章规定的规则加上冗余对此带冗余的扩展消息如第章规定的那样用秘密签名密钥计算其签名每个验证实体都会知道并使用该签名实体特定的公开验证密钥当且仅当第章规定的验证进程获得成功签名才是可接受的注密钥的产生与分配已超出本标准的范围签名进程图概括了这种签名进程图签名进程注这种签名进程较好的实现方法应当对这些操作加以物理保护使得无法对秘密签名密钥控制下的签名函数进行直接访问填充消息是一个比特串在其左边添上到个以便获得一个字
7、节的串指数后面将用到是填充的数目加因此的值为到从而在填充后的消息中个最低有效位是信息位个填充的个信息位乘上后的数应小于或等于因此待签名消息的比特数最多应是小于或等于的最大整数的倍扩展数后面要用到是满足字节串至少包含个比特的最小整数扩展后的消息的获得是通过依次在左边不断重复的字节直到形成字节串为止对于从到等于加上所以从到的第字节等于的第字节字节注数小于或等于只有当模同余于或时两者才可能相等冗余通过交替地将的字节放在奇数位置上将字节冗余放在偶数位置上便得到带冗余的扩展后的消息的第字节的低半字节经指数对其修改后便由其值和位置对消息长度进行了编码对从到的第字节等于的第字节的第字节等于的第字节按表规定的
8、影子的像但第字节例外它等于的第字节的影子与指数异或的结果字节注从到的个字节计算到的个字节是通过对从到连续地应用下列三个公式完成的最后第字节再经指数修改截取和强置中间整数是用比特串来编码的其最高有效位为个最低有效位便是的个最低有效位但最低有效字节被替代了如果是的最低有效字节则的最低有效字节是签名产生在秘密签名密钥的控制下对应用签名函数就得到比特串的签名表置换和影子如果由四比特组成在置换下的像用表示则为如果字节由两个半字节组成在影子下的像用表示则为验证进程图概括了验证进程图验证进程签名开启在公开验证密钥的控制下通过对签名应用验证函数将其变换成恢复后的中间整数如果不是一个最高有效位为和最低有效半字节
9、为的比特串则该签名将被拒绝消息恢复恢复后的带冗余的消息是一个字节串其个最高有效位为而个最低有效位便是的个最低有效位但最低有效字节需被替代按照表中规定的置换如果是的最低有效四个半字节则的最低有效字节应是注和这两串可能不等是由的个最低有效位且在其最高有效位填充了到个后组成的从的个字节计算出个和按照表中规定的影子第个和等于第个字节与第个字节的影子的异或如果个和都是则签名将被拒绝恢复成第个非零和的位置恢复后的填充了的消息便是中奇数位置上个最低有效字节组成的串指数恢复成第个非零和的最低有效半字节的值如果指数不取到之间的值或的个最高有效位不全为则签名将被拒绝个填充的个信息位消息被恢复成的个最低有效位组成的
10、串冗余校验当且仅当的个最低有效位等于由恢复后的填充了的消息按照和计算出的带冗余的扩展后的消息的个最低有效位时签名才被接受附录提示的附录用于数字签名的公开密钥体制例子定义模数两个素数的乘积构成的整数公开验证密钥模数和验证指数秘密签名密钥签名指数符号和缩略语代表元素合成整数模数模数的比特长度模数的素因子验证指数签名指数整数和的最小公倍数关于的雅可比符号注设是奇素数并设是一个正整数则整数关于素数的勒让德符号用下列式子定义当不是的倍数时则整数关于素数的勒让德符号取值为或它取决于整数是或不是模的平方的倍数关于素数的勒让得符号为设为奇正整数并设是一个正整数整数关于整数的雅可比符号等于整数关于的素因子的勒让
11、得符号之乘积所以如果则任何整数关于任何整数的雅可比符号可以有效地计算而无需知道的素因子密钥产生公开验证指数每个签名实体都应选择一个正整数作为其公开验证指数在特定的应用中公开验证指数可以标准化注公开验证指数取为和会有一些特别的优点秘密的素因子和公开的模数每个签名实体应当秘密地且随机地选取两个不同的奇素数和它们满足下列条件如果是奇数则和都应当与互素如果是偶数则和都应当与互素且和不应当模同余公开模数就是秘密素因子和的乘积模数的长度为应当等于注关于素数选取的若干别的条件也应当很好地考虑以便防止对模数的因子分解有些形式的模数有简单的模约简运算且只需少量的存储表这些形式是其长度比特其长度比特其中且在负形式
12、中个最高有效字节的所有位均是其数目可达到模数长度的四分之一在正形式中在取值为的最高有效位之后个最高有效字节的所有位均是其数目可达模数长度的四分之一秘密签名指数秘密签名指数是使得为下列数的倍数的最小正整数若是奇数若是偶数签名函数中间整数是按所述计算出的比特串关于的代表元素记为如果是奇数则就是如果是偶数且则是如果是偶数且则是注如果是偶数则关于的雅可比符号强置为对计算其模的次幂签名便是此计算结果或者是其关于的补取其中较小者这就定义了签名函数验证函数签名是小于的正整数对其进行模的次幂以得到合成整数于是恢复后的中间整数用下列译码确定如果是模同余则就是如果是模同余则是而且当是偶数时如果是模同余则是如果是模
13、同余则是所有其他情况签名都应被拒绝而且如果不落在到范围内签名也应被拒绝这便定义了验证函数附录提示的附录关于附录提示的附录的说明实例使用十六进制记法公开指数为的例子密钥产生公开验证指数为所以秘密素因子都是模余比特的公开模数具有形式其中形式其秘密签名指数为变量的长度是小于或等于的正整数是小于或等于的最大整数因而当为时取值从到待签名的消息为到比特的串填充后的消息和为到字节的串为扩展后的消息为字节的串带冗余的消息和为字节的串而且中间整数和及签名都是比特个比特的串例本例说明了对比特消息签名的填充扩展和截取过程该消息为签名进程在左边填充了四个以后填充后的消息便是字节的串所以通过将的个相连字节不断重复依次排
14、在左边直至达到个字节的串便构成扩展后的消息带冗余的扩展后的消息是一个字节的串它是通过将的个字节和冗余的个字节交替排列而得到的第个字节的修改给出了消息边界的编码中间整数是从通过下列方法得到的截取个比特左边填充一个最低有效字节予以替代即代之以因为是奇数所以代表元素便是对计算其模的次幂此处签名便是该计算结果关于的补验证进程签名小于通过对计算其模的次幂得到合成整数中间整数是比特的串其中最高有效位是且最低有效半字节的值为因为在这里是模余且是模余所以恢复后的中间整数是恢复后的带冗余的消息在这里便是字节的串其中在一个填充的后接着便是的个最低有效位但最低有效字节例外按照置换中的说明用表示的将代之以其值为第个非
15、零和是第个和值为这样而恢复后的填充了的消息就是的最低有效奇数位置中个字节的串的四个最高有效位为因此消息本身就恢复为的个最低有效位的串这个签名是可被接受的这是因为恢复后的带冗余的消息的个最低有效位和由计算出的带冗余的扩展后的消息中的一样而这种计算方法和由计算出的完全一样例本例说明了一种更简单的情况比特的消息对于比特的模数既不需要填充也不需要扩展签名进程消息为比特恰恰编成字节所以而该消息就是填充后的消息也是扩展后的消息扩展后的带冗余的消息是字节的串通过对截取比特左边填充一个以及替代最低有效字节便得到中间整数因为是奇数代表元素为对计算其模的次幂签名在这里便是该计算结果验证进程签名小于通过对计算其模的
16、次幂便得到合成整数因为此处是模余因此恢复后的中间整数就是恢复后的带冗余的消息便是字节的串其中在一个填充的后接着是的个最低有效位但最低有效字节例外按照置换中的说明由表示的代之以其值为第个非零和是第个和其值为这样且恢复后的填充了的消息是中奇数位置上的字节的串恢复后的消息为比特的串这个签名是可接受的因为恢复后的带冗余的消息的个最低有效位和由计算出的带冗余的扩展后的消息中的一样这种计算方法和由计算出的完全一样公开指数为的另一个例子密钥产生公开验证指数为所以秘密素因子都是模余比特的公开模数具有形式其中形式其秘密签名指数为变量的长度因为为所以取值为到待签名消息为到比特的串填充后的消息和是到字节的串为扩展后
17、的消息为字节的串带冗余的消息和是字节的串而且中间整数和以及签名均为比特比特的串例本例说明了对比特消息签名的填充扩展和截取过程该消息为签名进程在左边填充四个以后填充后的消息为一个字节的串所以通过将的连续个字节不断重复依次排在左边直至得到字节的串扩展后的带冗余的消息是一个字节的串它是通过交替地排列的个字节和冗余的个字节得到的第字节的修改给消息边界进行编码中间整数是通过下列方法从得到的先截取其比特再在左边填充一个最后替代最低有效字节代之以因为是奇数所以代表元素为对计算其模的次幂此处便是该结果关于的补验证进程签名小于对计算其模的次幂就得到合成整数中间整数是比特的串其中最高有效位为最低有效半字节的值为因
18、为此处是模余是模余所以恢复后的中间整数为恢复后的带冗余的消息便是字节的串其中在两个填充的后接着是的个最低有效位但最低有效字节例外按照置换中的说明由表示的被代替其值为第个非零和是第个和其值为这样恢复后的填充了的消息便是的最低有效奇数位置上个字节的串的四个最高有效位为消息本身便恢复为的个最低有效位的串这签名是可接受的因为恢复后的带冗余的消息的个最低有效位和由计算出的带冗余的扩展后的消息中的一样这种计算方法和由计算出的完全相同公开指数为的例子密钥产生公开验证指数为所以一个素因子为模余另一个为模余位公开模数具有形式其中形式其秘密签名指数为变量的长度因为为所以取值为到待签名消息为到比特的串填充后消息和都
19、为到字节的串为扩展后消息为字节的串带冗余的消息和均为字节的串而且中间整数和以及签名均为比特比特的串例本例说明了带强置雅可比符号的比特消息的签名签名进程消息为比特的串恰好编码成字节所以填充后消息扩展后消息和该消息相同带冗余的扩展后的消息为字节的串通过截取的比特左边填充一个替代最低有效字节便得到中间整数因为关于的雅可比符号为所以代表元素为对计算其模的次幂此处签名就是该计算结果验证进程签名小于对计算模平方得到合成整数因为此处是模余所以恢复后的中间整数为恢复后的带冗余的消息除了最高有效位强置成以及最低有效字节被替代外与的相同第个非零和是第个和其值为这样恢复后的填充了的消息是奇数位置上的字节串恢复后的消
20、息就是比特的串这个签名是可接受的因为恢复后的带冗余的消息的个最低有效位和由计算出的带冗余的扩展后的消息中的一样这种计算方法和由计算出的完全相同例最后这个例子说明了不需要强置雅可比符号的比特消息的签名情况签名进程消息是比特的串恰好编成字节所以填充后的消息和扩展后的消息都是该消息带冗余的扩展后的消息是字节的串通过截取的比特左边填充一个替代最低有效字节就得到中间整数由于关于的雅可比符号为所以此处就是代表元素对计算其模的次幂结果便是签名验证进程签名小于通过对计算模平方得到合成整数由于是模余所以此处就是恢复后的中间整数恢复后的带冗余的消息是字节的串它和相同但最高有效位需强置成最低有效字节被替代掉第个非零
21、和是第个和其值为这样恢复后的填充了的消息就是的奇数位置上个字节的串恢复后的消息便是比特的串这个签名是可接受的因为恢复后的带冗余的消息的个最低有效位和由计算出的带冗余的扩展后的消息中的一样这种计算方法和由计算出的完全相同附录提示的附录为抵抗对附录提示的附录各种潜在攻击所采取的若干预防措施秘密函数的合法自变量函数模的次幂的唯一的合法自变量就是代表元素如果是奇数所有代表元素都是比特的串其中最高有效位的值为最低有效半字节的值为如果是偶数则代表元素关于模数的雅可比符号强置为且所有的代表元素都是下列情况之一若则代表元素为比特串其中最高有效位的值为最低有效半字节的值为若则代表元素为比特串其中最高有效位的值是三个最低有效位组成的串的值为四种运算的排除由于代表元素的这种结构特性下面四种运算可以不予考虑注这些材料取自的一篇通信见附录提示的附录该研讨会于年月日至日在丹麦的举行平移代表元素的比特串编码不可能平移成另一个代表元素求补代表元素的比特串编码不可能经求补后变成另一个代表元素普通乘法代表元素与常数的普通乘积即不进行模约简不可能是另一个代表元素普通方幂任何常数的普通次幂即不进行模约简不可能是一个代表元素事实上模余的整数不可能是某一数的幂模余的数也不可能是某一数的偶次幂附录提示的附录参考文献
