（通信与信息系统专业论文）数字签名与密码学中的布尔函数的研究.pdf

西安电子科技大学硕士研究生学位论文 中文摘要 信息系统安全的中心内容是保证信息在系统中的保密性、认证性和 完整性。数字签名技术是实现信息安全的重要组成部分。随着信息化的 发展，信息安全与现代密码理论、技术变得越来越密切相关。作为表示 逻辑关系的函数，布尔函数是实现密码体制的一个重要工具。无论在流 密码还是分组密码中、在私钥还是公钥中，布尔函数都有着重要的应 用。 本文中，作者在介绍了数字签名和布尔函数的一些基本概念、理论 以及相关知识的基础上，对数字签名以及布尔函数中的某些领域进行了 深入的研究，取得的主要研究结果有： 1 提出了一个基于离散对数的环签名方案和一个可验证的环签名方案； 2 改进了k i m 等提出的可转化群签名方案； 3 提出了一个基于几何的门限签名方案； 4 设计了四种新的一阶相关免疫布尔函数的构造方法； 5 给出了个截止目前最好的一阶相关免疫布尔函数的计数下界。 关键词：数字签名相关免疫布尔函数计数认证 堕窒皇量型垫查堂堡主堕塑兰兰垡堕苎 a b s t r a c t t h em a i nc o n t e n to fi n f o r m a t i o n s e c u r 时i s t o g u a r a n t e e t h e c o n f i d e n t i a l i t y ，a u t h e n t i c a t i o na n di n t e g r a t i o no f t h ei n f o r m a t i o ni ns y s t e m s d i g i t a ls i g n a t u r et e c h n o l o g yi s a ni m p o r t a n tp a r tt oa c h i e v et h ei n f o r m a t i o n s e c u r i t y w i t ht h ed e v e l o p m e n to f t h ei n f o r m a t i o nt e c h n o l o g y ，i n f o r m a t i o n s e c u r i t yb e c o m e sm o r ea n dm o r er e l a t e dt om o d e mc r y p t o g r a p h y b e i n ga f u n c t i o nd e n o t i n gl o g i c ，b o o l e a nf u n c t i o ni sa ni m p o r t a n tt o o lt oi m p l e m e n t t h em o d e m c r y p t o g r a p h y n om a t t e ri nt h es t r e a mc i p h e ro rb l o c kc i p h e r ， s y m m e t r i cc r y p t o g r a p h y o r a s y m m e t r i cc r y p t o g r a p h y ，b o o l e a n f u n c t i o nh a sa g o o di m p l e m e n t a t i o n t h ed i s s e r t a t i o nm a k e sa d e e ps t u d y o ns o m ei s s u e so f d i g i t a ls i g n a t u r e s a n db o o l e a nf u n c t i o n sa f t e ri n t r o d u c i n gs o m eb a s i cn o t i o n s ，t h e o r i e sa n d o t h e rr e l a t e dk n o w l e d g e t h em a i nr e s u l t sg o t t e nf r o mt h ed i s s e r t a t i o na r ea s f o l l o w i n g ： 1 p r o p o s e ad l - b a s e d r i n gs i g n a t u r es c h e m e a n dav e r i f i a b l er i n gs i g n a t u r e 2 i m p r o v e t h ec o n v e r t i b l eg r o u p s i g n a t u r es c h e m ep r o p o s e db y k i me t c 3 p r e s e n ta g e o m e t r y - b a s e d t h r e s h o l ds i g n a t u r es c h e m e 4 d e s i g nf o u rn e wm e t h o d st o c o n s t r u c tt h e1s t - o r d e rc o r r e l a t i o n - i m m u n e b o o l e a nf u n c t i o n s 5 g i v et h eb e s tl o w e rb o u n do ft h en u m b e rls t o r d e rc o r r e l a t i o n i m m u n e b o o l e a nf u n c t i o n ss of a r k e y w o r d s ：d i g i t a ls i g n a t u r ec o r r e l a t i o n - i m m u n e f u n c t i o n se n u m e r a t i o n a u t h e n t i c a t i o n 西安电子科技大学硕士研究生学位论文 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含 其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确地说明并表示了谢意。 本人签名：生差盔日期垒亟：主 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离 校后，发表论文或使用论文工作成果时署名单位仍为西安电子科技大学。学校有权 保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的沦文在解密后遵 守此规定) 本人签名 导师签名 日期2 照：主 日期趔= 丛 j 燃穆 第一章绪论 第一章绪论 本幸芍岛俞宿了秸喜名金中堑孝签名p 分在现代社金| 申的重重任，羼波夼语 了与传喜瘩全鸯鸯和筅酌弦代密五易学审蓐糸函盘韵意义，最后夼诏了本话土主岳 研宓钓固题、取得钓主暮研宓嵌果掰盈鲁幸内客盍辫。 奉幸募键询：谨垂瘩全；数雩谷名；席皋函盐 1 1 引言 计算机和网络技术的快速发展已经使人类社会步入了信息时代：因特网的迅 速普及和其技术的飞速进步无可置疑为生产力的发展起到了极大的推动作用。现 在，因特网已经成为人们进行通信、商贸以及获取各种信息的不可或缺的工具。 在网络给社会和人们的日常生活带来巨大的经济效益和便利的同时由于信 息网络的国际化、社会化和开放化等特点，当它在给人们提供“信息共享”、 “技术共享”的同时，也给人类社会带来了不安全的阴影。机密信息在网上被泄 露、篡改和假冒，网络黑客的猖獗、计算机犯罪、计算机病毒和垃圾文化的肆意 传播正在对社会的安定和青少年的成长带来了严重的威胁。 信息是一种重要的战略资源，各个国家和地区都给予了高度的重视。国际上 围绕信息的获取、使用和控制的斗争愈演愈烈。信息时代的到来也对人类战争的 模式带来了时刻的变化。在当今信息时代，信息安全也是直接关系到国家安全、 社会稳定和经济持续健康发展的重要问题正日益受到世界各国和地区的重视。 随着全球信息高速公路建设的兴起和通信的网络化、数字化、个人化、智能 化、宽带化进程的不断加快，用户对信息的安全存储、安全处理和安全传输的要 求愈益迫切。特别地，随着个人通信、多媒体通信、电子邮件、电子商务以及电 子政务等系统的发展，信息系统的安全保护问题就更加显著。 1 1 1 数字签名的重要性 信息系统安全的中心内容是保证信息在系统中的保密性、认证性和完整性。 传统的密码体制的主要功能是信息保密，而现代密码体制还应保证信息在系统中 的可认证性和完整性，这样可以保证在公开信道上安全地传输信息。为了防止消 2 西安电子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 息被窜改、删除、重放和伪造，一种有效的方法是使发送的消息具有被验证的能 力，使接收者能够识别和确认消息的真伪，实现这功能的密码系统称为认证系 统。消息的认证性和消息的保密性不同，保密性是使截获者在不知密钥的情况下 不能解读密文的内容，而认证性是使任何不知密钥的人不可构造出一个密文，使 意定的接收者解密成一个可理解的消息。 认证理论和技术是最近二十年来随着网络的普遍应用而发展起来的，它已经 成为通信安全学的一个重要的领域。认证系统主要包括以下几个方面的内容： 1 ) 消息认证；2 ) 身份认证；3 ) 数字签名。消息认证是解决在通信双方利害一 致的条件下，如何防止第三方伪造和破坏的问题；身份认证技术是用于提供通信 方身份认证性的安全机制，它通过检测证明方拥有什么或者知道什么来确认证明 方的身份是否合法。在实际通信系统中，通信双方很难进行面对面交流，甚至通 信一方或双方是机器而不是人。人一机身份认证系统仍然可以采用“检测证明方 拥有什么”的方法，例如检查人的个人特征一指纹、声纹、视网膜等，因为每个 人的这些特征各不相同，因而可以利用它们来唯一地鉴别人的身份。另一种身份 认证方法是通过检测证明方知道什么来确认证明方的身份是否合法；例如，在计 算机网络中，用户访问网络时必须输入用户名和口令，网络通过检查口令是否正 确来确认用户身份的合法性。这种认证方法与上述方法不同的是，它不依赖于证 明方的任何物理特征因而适用范围更广泛，甚至可以实现机器一机器之间的身 份认证。密码学中的身份认证方案主要是基于这种方法，验证方通过密码技术验 证证明方是否知道某个秘密，如证明方与验证方之间共享的秘密密钥，或证明方 自己的私有密钥等。而数字签名刚解决当通信双方是竞争对象时，如何远距离迅 速地利用电子签名代替传统的书写签名和印签的问题。 1 1 2 密码学中的布尔函数的意义 1 9 4 9 年，s h a n n o n 发表了一篇具有划时代意义的文章，“保密通信的信息理 论”，首次用概率统计的观点对信息源、密钥源、接受和截获的密文进行了数 学描述和定量分析，标志着密码学真正成为了一门科学。1 9 7 6 年d i f f i e 和 h c l l m a n 发表了“密码学中的新方向”1 2 ，提出了一种崭新的密码体制，导致了密 码学发展史上的一场革命，产生了新的双钥体制公钥体制，使得收发双方无 需事先交换密钥就可建立保密通信。二十多年来，密码学无论在理论上还是应用 上都得到了飞速发展，大量的敏感信息如法庭已录、资金转移和私人财产等，常 常通过公共通信设施或计算机网络来进行交换，而这些信息的秘密性和真实性是 人们迫切需要的。因此在当今的信息社会里，信息安全越来越受到重视，随着信 息化的发展，信息保密与现代密码理论与技术密切相关，这不仅给密码学的研究 以巨大的推动力，也为密码理论与技术的应用提供了广阔的前景。 第一章绪论 如今，密码理论与技术的应用已经覆盖了国防、军事、政府、金融、商业和 文教等领域。 流密码和分组密码是密码体制实现的两种基本方式，而作为表示逻辑关系的 函数，布尔函数又是实现密码体制的一个重要工具。无论在流密码还是分组密码 中，无论在私钥还是公钥中，布尔函数都有着重要的应用；特别是在流密码中 布尔函数更具有特殊的地位。因而，伴随着密码学的发展，研究布尔函数具有非 常重要的意义。 1 2 论文主要研究的问题及研究成果 由于作者在近一年半的科研阶段中，几乎同时进行着关于数字签名和密码学 中的布尔函数的研究，所以本论文大致可以分为三部分： 论文第一部分在介绍了环签名、群签名、门限签名等几种应用在不同环境下 的数字签名方案的基础上，提出了一个新的基于离散对数的环签名方案和一个可 验证的环签名方案，改进了k i m 等提出的可转化群签名方案，使其能够抗击目前 已知攻击，提出了一种基于几何的门限签名方案；最后认真总结几种常见的数字 签名方案的攻击方法。 论文第二部分在介绍了密码学中的布尔函数的基本性质如非线性性、相关 免疫性以及平衡性的基础上，设计了四种新的一阶相关免疫布尔函数的构造方 法，通过这四种新的构造方法，从而得到了截止目前最好的一阶相关免疫布尔函 数的计数下界，这个新的下界好远远好于m i t c h e l l 提出的下界以及其它现有的 下界。 论文第三部分总结了主要成果，给出了作者正在研究的数字签名、认证和布 尔函数等领域中的一些问题。 1 3 论文内容安排 第二章简要介绍了密码学的一些初步知识，包括对称密码、非对称密码、 杂凑函数、数字证书、零知识证明、r s a 加、解密算法、e 1 g a m a l 加、解密算 法、r s a 签名方案、e 1 g a m a l 签名方案、s c h n o r r 签名方案、n y b c r g r u e p p e l 签名 方案、数字签名标准( d s s ) 以及d i f f i e h e l l m a n 密钥交换。 第三章介绍了环签名、群签名、门限签名等数字签名方案，提出了几种新的 应用不同数学原理或基于不同数学难题的数字签名方案，同时改进了某些存有缺 陷的方案；最后，给出了几种常见的数字签名方案的攻击方法。 4 西安电子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 第四章主要介绍了密码学中的布尔函数的几种常用的表示方法，它的基本性 质线性性、非线性性、相关免疫陛、对称性、平衡性、严格雪崩准则以及扩 散准则。 第五章设计了四种新的一阶相关免疫布尔函数的构造方法，通过这四种新的 构造方法，给出了目前最好的一阶相关免疫布尔函数的计数下界。 第六章给出了本论文的主要成果、作者正在或下一步待研究的数字签名、认 证和布尔函数领域中一些问题。 第二章密码学简介 第二章密码学简介 本幸苔羌萄单命宿了窟玛学弱古大国威要素i 寸辫窟码、雌j 寸赫窟码、 矗凄函盘、盘享各名、数字证书科盟霉知识证卯，舆次简墓夼匈了r s a 加窟体 耕、e i g o m a i 加密体翻硝压d i f r l e - h e l l m a n 窟锏立耱，最后夼国了几个常见的 数字署名方案。 本幸差锺词：对赫窟码；肄i 寸称窟；暑；磐凄函盘；窟钥立籀 2 1 密码学组成 密码学是研究与隐蔽性、数据完整性、实体认证、数据认证等信息安全领 域相关的数学技术【8 。这些性质也是几乎所有的密码协议所要达到的效果。 过去，密码系统是为了保护军事中的保密通信而设计的；自从进入二十世 纪，特别是上世纪六十年代以后，计算机通信网的迅速发展使得密码学越来越为 人们所熟悉、利用。电子商务、电子政务等应用使得先进的密码学技术成为必需 之物。 本节中主要介绍了与数字签名相关的一些基本的密码理论，包括：对称密 码、非对称密码、杂凑函数、数字签名、数字证书和零知识证明。 2 1 1 对称密码 古典密码学主要包含两大密码系统对称密码和非对称密码。对称密码 也被称为私钥密码。 对称密码的加密密钥和解密密钥是相同的，通信双方应保证这个密钥的保 密性。 设待加密的消息为m ，加密密钥为t ，。o 为加密算法，d 。o 为加密算 法。 则加密密文c = e 。( m ) ，解密明文为m = d 。( c ) = d 。( e 。( 盯) ) 。 6 西安电子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 d e s i g l 和i d e a l 0 1 是比较出名的两个对称密码系统。 2 1 2 非对称密码 在非对称密码系统中，有两个不同的密钥加密密钥是公开的，所以非对 称密码也被称为公钥密码：解密密钥也称为私钥，是保密的，只有收信人知道。 但要通过公开的加密密钥获得解密密钥是不可能的，这种不可能或者是实际上 的，或者是计算上的，也就是说，利用攻击者现有的财力、物力是不可能计算出 来的。 设待加密的消息为m ，e k o 为加密算法，d , o 为加密算法，私钥为t ，公 钥为儿。 则加密密文 c = e 。( m ) ，解密明文为m = d 。( c ) 。 与对称密码系统相比，非对称密码的速度比较慢，一般不用在大量数据加 密，只用于加密小的消息，如对称密钥交换中。 r s a l i l 】是一比较出名的非对称密码系统。 2 1 3 杂凑函数 杂凑函数的另一个名字叫消息压缩。从这个名字可见，杂凑函数的输出与 输入的消息是相关的，但是大小比输入的消息要小。 一个杂凑函数被用来产生消息的数字指纹。通常在密码中使用的是单向 杂凑函数。“单向”意味着它容易把消息转换到它的摘要，但相反的过程却比较 困难。 一个单向杂凑函数h ( x ) 应具有以下性质： 1 ( x 1 可以用于任何数据大小的分组； 2 不管输入数据多大，h ( x ) 应产生固定大小的输出； 3 给定输入x ，h ( x ) 应易于计算； 4 日( z ) 应是单向函数。即给定输a x 对应的h ( x ) ，计算出x 是计算上 不可行的； 5 ( x ) 应是不碰撞的。即，要找到另一个不同于x 的y ，使得 h ( y ) = h ( x ) 是计算上不可行的。 第二章密码学简介 7 杂凑函数主要是用于数字签名产生阶段。两个较有名的杂凑函数是s h a - 1 【。2 1 和m d 一5 1 1 3 。 2 1 4 数字签名 随着计算机通信网的发展，人们希望通过电子设备实现快速、远距离的交 易，数字签名法应运而生，并开始应用于商业通信系统，如电子邮件、电子转帐 和办公自动化等系统。 数字签名是用于提供服务不可否认性的安全机制，类似于手书签字，数字 签字也应满足以下要求：1 ) 收方能够确认或证实发方的签字，但不能伪造；2 ) 发方发出的签字的消息给收方后，就不能再否认他所签发的消息：3 ) 收方对已 收到的签字消息不能否认，即有收报认证；4 ) 第三者可以确认收发双方的消息 传送，但不能伪造这一过程。其功能也与传统的手写签名一样，代表签名者对一 份合同内容或一项服务业务的承认，因而它可以在签名者违反合同或否认其使用 过某种服务业务时被用来作为证据，防止抵赖。 然而，数字签名与手写签名在形式上有很大不同：( 1 ) 数字签名是采用电子 形式，容易在网络中传输；( 2 ) 只有知道秘密密钥的人才能生成数字签名，因而 数字签名很难伪造，而手写签名则相对比较容易被伪造：( 3 ) 数字签名可以对整 个消息进行签名，签名后消息不可以更改，而手写签名后的文件可以改动：数 字签名与手书签字的区别在于：手书签字是模拟的，且困人而异；数字签名是0 和1 的数字串，因消息而异。数字签名与消息认证的区别在于：消息认证使收方 能验证消息发送者及所发送消息内容是否被窜改过；当收发双方之间没有利害冲 突时，这对防止第三者的破坏来说是足够了，但当收发双方之间有利害冲突时， 单纯用消息认证技术就无法解决他们之间的纠纷，必须借助满足前述要求的数字 签名技术【4 j 。 2 1 5 数字证书 数字证书是一个包含有用户个人信息、个人私、公钥，最为重要的是证书机 构( c a ) 的签字。证书机构是颁发数字证书的第三方，通常是一个大的、著名 的、值得信赖的第三方。 数字证书可用在一方的身份认证。例如，当你想给你朋友发送一条消息时， 你所需要做的全部就是获得你朋友的数字证书，用里面包含的公钥加密消息，然 后发给朋友。通过数字证书，你就可以确信消息所发给的接收者就是你想发给的 接收者。 8 西安电子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 在许多电子商务应用中传输的数据首先要加密。在用公钥密码加密的数据 之前，必须获得接收方的公钥。所以证书机构必须是一个值得信赖的第三方。数 字证书是p k i 中的核心内容。 2 1 6 零知识证明 零知识证明【1 4 】是包括证明方和验证方的双方协议，协议中证明方要使验证 方确信他知道某种秘密，而不能泄露秘密的内容。 零知识证明可以分为两类：交互式【1 5 i 的和非交互式的【1 6 】。 1 9 8 9 年，q u i s q u a t e r 等给出了一个解释零知识证明的通俗例子【l ”。有一个 图，如图2 - 1 型2 - 1 设p 知道秘密，可打开c 和d 之间的秘密门，不知道的人都会陷入死胡同。 下面说明p 如何使q 确信他知道这个秘密，但又让q 获不得这个秘密。 1 ) q 站在a 处： 2 ) p 进入洞中任一点c 或d ： 3 ) 当p 进洞之后，q 走到b 点； 4 ) q 让p 从左边或右边走出来： 5 ) p 实现q 的要求； 6 ) p 和q 重复以上协议多次。 这样的话，0 就相信p 知道这个秘密，而又获取不到这个秘密。 2 2 基于因式分解的密码系统 基于因式分解的密码系统的安全性主要依赖于大因式分解的困难性。比较出 名的基于因式分解的密码系统是r i v e s t , r l ，a s h a m i r 和l a d l e m a n 提出的 r s a 密码系统【1 ”。 公、私密钥产生阶段 s t e p1 选择两个大素数，p 和q 。为了保证安全性，p 和g 要有相同长 度： 第二章密码学简介 s t e p2 计算乘积：n = p q ： s t e p3 计算欧拉常数：( ) = ( p 1 ) ( g 一1 ) s t e p4 随机选择加密密钥p ，p 满足g c d ( e ，妒( ) ) = 1 ，1 e 庐( ) s t e p5 用欧几里德算法计算解密密钥d = e 1m o d ( 0 。由扩展的欧几里 德算法可知：解密密钥d 是唯一确定的。 加密算法对消息m 的加密密文为c ；m m o dn ； 解密算法解密明文为m ：c m o dn 。 r s a 密码系统是一种确定性加密系统，即对同一明文，加密后的密文也相 同。 2 3 基于离散对数的密码系统 基于离散对数的密码系统的安全性主要依赖于离散对数求逆的困难性，即 d l p 问题。比较出名的基于离散对数的密码系统是t e i g a m a l 提出的e 1 g a r n a l 密 码系统 1 8 。 令乙是一个有p 个元素的有限域，p 是一素数。明文集m 为z ，密文集为 z ，x z 。，。公钥：令g 是z ，( 4 中除去0 元素) 中的一个本原元，计算公钥 ，5 9 。r o o dp ，私钥口p 。 加密算法选择随机数k z ，且( ，一1 ) = i ，计算 y i = g m o dp ， y l = 邶r o o dp 密文由以上两部分级连构成，即密文c = y f l y ：。 解密算法收到密文c 后，计算 村专= 攀= 攀m o d pg。gy i 一 e 1 g a m a l 密码系统是一种非确定性加密系统，即对同一明文，加密后的密文 也可能不相同。 0 西安电子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 2 4d i f f i e h e l l m a n 密钥交换 d i i f e 和h e l l m a n 提出的密钥交换1 2 】_ 是一个公钥算法，能够保密地产生通信 双方的会话密钥。设g 是z ，中的一个本原元，n 是两个强素数的乘积。 算法如下： s t e p1 a l i c e 和b o b 是通信双方，每人分别任选个一随机数口和b ： s t e p2 a l i c e 计算 x = g 。m o d h ， b o b 计算 y = g m o dn ： s t e p3 a l i c e 计算 k = y 。= g “m m h ， b o b 计算 k = x = g 。r o o d 。 于是，一个会话密钥k 就产生了。对任何攻击者，要想攻击这个算法，都 面临着d l p 问题。 2 5 数字签名 为了实现签字目的，发方必须向收方提供足够的非保密信息，以便使其验 证消息签字：但又不能泄露用于产生签字的机密信息，以防止他人伪造签字。因 此，签字者和证实者可公用的信息不能太多。任何一种产生签字的算法或函数都 应提供这两种信息，而且从公开的信息中很难推测出用于产生签字的机密信息。 实现数字签名的方法很多其中大多数基于公钥密码技术。在公钥密码系统中， 用户将其公开密钥向所有人公布，而只有用户自己知道其秘密密钥。用户的数字 签名过程与公钥加密系统的工作过程相反：用户利用其秘密密钥将一个消息或该 消息的杂凑值进行签名，然后将消息和签名一起传给验证方，验证方利用签名者 公开的密钥就可以鉴别签名的真伪。因为只有签名者才知道其秘密密钥，因此只 有他才能生成数字签名，所以签名者一旦对一个消息进行了签名就无法抵赖；另 外，验证方只需要知道签名者的公开密钥就可以验证数字签名的真伪因此任何 人都可虬验证数字签名。 第二章密码学简介 数字签字有两种：一种是对整体消息的签字，它是消息经过密码变换的被签 消息整体：一种是对压缩消息的签字，它是附加在被签消息之后或某一特定位置 的一段签字图样。 一个签字体制一般含有两个组成部分，即签字算法和验证算法。签字算法或 签字密钥是秘密的，只有签字人掌握；证实算法应当公开，以便他人进行验证。 体制的安全性在于，从明文和签字难以推出签字密钥或伪造一个明文和签字可被 证实为真一j 。 2 5 1 r s a 签名方案 基于因式分解的数字签名的安全性主要是建立在因式分解的困难性。最出名 的基于因式分解的数字签名是r s a 数字签名】。 r s a 广泛应用在电子商务中，它有三个基本的算法构成，即公、私密钥产生 阶段、加密算法和解密算法。 公、私密钥产生阶段 s t e p1 选择两个大素数，p 和口a 为了保证安全性，p 和g 要有基本相同 的长度； s t e p2 计算乘积：n = p - q ； s t e p3 计算欧拉常数：矿( ) = ( p 一1 ) ( q 一1 ) ； s t e p4 ，随机选择加密密钥g ，。满g c d ( e ，( ) ) = 1 ，1 e s ( ) ； s t e p5 用欧几里德算法计算解密密钥d = e 1m o d ( ) 。由扩展的欧几里 德算法可知：解密密钥d 是唯一确定的。 签名算法对消息m 的签字为o = 阴“m o d n ； 验证签名算法对给定的m 和c ，可按下式验证： v e r k ( 研，c ) = 真m = c 4m o dn 。 2 5 2e 1 g a m a l 签名方案 基于离散对数的数字签名的安全性主要是建立在d l p 的计算上的困难性。 最出名的基于离散对数的数字签名是e 1 g a m a l “哺】。 1 2 西安电子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 令z 是一个有p 个元素的有限域，p 是一素数。明文集m 为z ，密文集为 z ，x z ，。公钥：令g 是z ，( z ，中除去0 元素) 中的一个本原元或其生成元，计 算公钥卢；旷m o dp ，私钥a c ，。 签名算法 s t e p1 选择随机数k ez r “且( 女，p 1 ) = i ； s t e p2 计算 r = g m o dp ， s = ( h ) - - a - r ) k “m o dp l ； s t e p3 将( r l is ) 作为对消息m 的签名发送给对方。 验证签名算法接收者收到m 和( r | | s ) 后，先计算h ( m ) ，再按下式验证 v e r k ( h ( m ) ，r ，j ) = 真营卢7 r 5 = g ”1m o dp 。 2 5 3s c h n o r r 签名方案 1 9 8 9 年，s c h n o r r 提出了一种签名体制s c h n o r r 签名方案1 9 1 。 公、私密钥产生阶段 p ，g：是大素数，g ip 一1 ，q 是大于等于1 6 0 b i t 的整数： g ：z ，中元素，且g ”s i m o dp ，：用户密钥1 ( j q ； ，：用户公钥y ；矿r o o dp 。 签名算法对消息m 的签名为s = s i g 。) = ( e ，其中 ，5g m o dp ， s i k - - x - em o dp e = h ( r0 m ) 。 验证签名算法验证者收到和s = ( e 后，计算 第二章密码学简介 而后计算h ( r - 0 肼) ，验证 h ( r 1 1 m ) = 8 如果( e 是肼的合法签字则等号成立。 2 5 4n y b e r g r u e p p e l 签名方案 1 9 9 3 年，n y b e r g 和r u p p e l 提出了具有消息恢复功能的基于离散对数的签 名方梨2 m 。签名者私钥为x ，公钥y = g 。r o o dp 。 签名算法：s t e p 1 签名者任选一随机数k s t e p2 签名者计算 ，= mg r o o dp ， s = j ，+ k r o o dg ： 则消息m 的签名为p ，s ) 。 验证签名算法：s t e p 1 验证者收到m 和( ) 后，计算 m 5 9 y 7r r o o dp ： s t e p 2 如果等式成立，则接受签名；否则，不接受。 2 5 5 数字签名标准 1 9 9 4 年，n i s t 公布了一个产生数字签名的具体的数字签名算法伫”，用于 侦察对文件内容未授权的改动以及对签名者的认证；此外，产生的数字签名满足 不可否认性，也就是说，签名者不能否认他实际已经签过的名。算法如下： 密钥产生阶段 s t e p 1 选择一素数g ，满足2 g ( 2 ”； s t e p 2 选择一素数，满足0 - t 8 ，选择素数p ，满足 2 “。 p 2 “，且满足q i ( p 一1 ) ； s t e p3 选择z ：域中一个阶为q 的生成元g ： 1 4 西安电子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 s t e p4 选择一个随机数z 。满足l s x q 一1 ，私钥为，； s t e p5 公钥y ：y = ( p ，q ，g ，g r o o d p ) 。 签名算法 s t e p 1 签名者任选一数t ，满足i i q ，将t 保密： s t e p2 签名者计算，= ( g r o o dp ) m o dq ； s t e p3 签名者计算j = - 砷( 盯) + ，) m o dg ； s t e p4 消息村的签名为p ，s ) 。 验证签名算法 s t e p 1 验证者验证是否1 s 5 9 ，否则，拒绝此签名 s t e p2 验证者计算 w = s 一1r o o d 口： s t e p3 验证者计算 h = w - ( m ) ，“：= r 1 4 r o o dg ： s t e p4 验证者计算v = ( g y t r o o dp ) m o dg ； s t e p5 验证者验证 v ：，。 如果等式成立接受签名；否则，拒绝签名。 2 6 本章总结 本章首先简单介绍了对称密码、非对称密码、杂凑函数、数字签名、数字证 书以及零知识证明等密码学组成要素，其次介绍了比较经典的r s a 加密体制、 e 1 g a m a l 加密体制以及o i f f i e h e l l m a n 密钥交换，最后介绍了r s a 签名方案、 e i g a m a l 签名方案、s c h n o r r 签名方案、n y b e r g r u e p p e l 签名方案以及数字签名 标准等数字签名方案。 第三章数字签名体制的研究与设计 1 5 第三章数字签名体制的研究与设计 本幸首先骨语了盘字缮名方案韵荽本祝含，舆次值针了一种垂于高傲卅数的 环各名方李，臣笆了k 1 m 孑提出钎可站似群各名方案，握出了一种墨于凡何的f i ) 雕可麓证罄名最后话出了几种常见韵政击方 去。 奉幸关键询：可看缸签名；群签名；n 限善拿髂证；伪( 童睦击 3 1 环签名 2 0 0 1 年，r i v e s t 等人提出了一种新的签名概念环签名方案1 ，它有以下 性质： 1 环签名方案无需群管理中心来生成签名，无需其他成员合作； 2 验证签名者不能分辨出环成员中哪一位代表成员签名，但确信是群成员中一位 签名： 3 签名者可以在未经其他成员同意下代表他所属的任意群签名。 此外，r i v e s t 提出的环签名方案可以使每一环成员在签名时可以使用不同的 算法。 3 1 1r i v e s t 等提出的环签名方案 r i v e s t 等提出的环签名方案中的陷门单向函数采用r s a 加密函数。 带密钥的联合函数 给定一密钥k ，一初始化值v 和 0 ，l r 上的，个任意数y 。，：，y ，定义 o 。( m ，y ：，y ，) 为带密钥的联合函数，它有如下性质： 1 每一个联合函数中都用一公用加密算法毛加密输出为 0 ，l r 上的一数值 ： 2 对每一s ，1 s ，给定除儿外的所有y 。值q ，( n ，y 2 ，y ，) 是从y ；到输出： 的一一映射； 1 6 西安电子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 3 对每一j ，l s5 s ，给定一b b i t 数：和除儿外的所有y ，值，能从 g ( y 1 y 2 ，y ，) = ：中有效地计算出儿： 4 给定女，v 和z ，如不能对陷门单向函数g l , g ：，g ，中任一求逆，则从 c k ，( g i ( 而) ，g z ( x 2 ) ，g ，( 斗) ) = ：求解龟，j 2 ，b 是不可能的。 r i v e s t 在文中指出，有些联合函数是不安全的，具有线性性质，他给出了一 个可用的联合函数：c 。( _ y 。，y ，y ，) = e ，o 疋( 一o e ( 1 0 t p ，o v ) ) ) ) = v 。 环签名过程： s t e p1 签名者选择一个键值：k = ( 吖) 。作为对称加密的密钥； s t e p2 。签名者选择一随机的模糊值v ； s t e p3 签名者为其他环成员随机独立地选择h ( 1 i r ，i 5 ) 并计算 s t e p4 签名者从q ，0 1 ，2 ，弗) = v 中求解只 s t e p5 签名者利用其私钥墨求解t = 邑“( 儿) ， s t e p6 。消息m 的签名为把，只，只弼x 。，x ：，x ，) 。 验证环签名过程： s t e p1 验证者收到签名忆，只，只x ，屯，t ) 后，对每一个f = 1 , 2 ，r ， 计算y ，= 品托) ； s t e p2 验证者得到密钥k ：k = 何盯) 。 s t e p3 验证者检验所有的y ，是否满足下式：c k ，( y i ，2 ， ) = v 。 如果上式成立，就接受签名：否则，拒绝签名。 方案的安全性在很大程度上依赖于上述联合函数的健壮性。从这个联合函数 可以看出，首先加密整数v ，最后经r 次加密后仍得到v ，所以称之为环签名。 3 1 2 一个基于离散对数的环签名方案 作者在文献 2 3 中提出了一种基于离散对数的环签名方案，该方案具有上述 签名方案的性质：签名时，无需群管理中心来生成签名，无需其他成员合作，可 第三章数字签名体制的研究与设计 1 7 以在未经其他成员同意下代表签名者所属的任意群签名；验证签名者分辨不出群 成员中哪一位代表群签名，但确信群成员中一位签名。为简便，本文都使用了类 似的签名方案，但也可以使用不同的方案。 我们假设已经存在一公开单向杂凑函数 o 和一公用对称加密函数算法e 。对 任一，- b i t 长的密钥 ，函数巨是作用在6 - b i t 长的字符串的一个置换。本文 中，带密钥的联合函数可选上述签名方案中的联合函数。 基于离散对数的陷门单向函数 p ，吼：大素数，q i f p 一1 ，q 。是大于等于1 6 0b i t 的整数，p 是大于等于5 1 2b i t 的整数，保证g f ( p 。) 中求解离散对数困难； g 。：g f ( p j ) 中元素，且岛mz l r o o dp 岛：用户私钥s e q 。； 只：用户公钥只= g i sm o d p ，。 陷门单向函数g f ( a ，卢) = g 。4 只，口r o o d p 。，其反函数为毋一3 ( ，) = ( a ，卢) ，其中 。和口按下式计算： 口5 y g 2r o o dp 口。2 口m o dq ， ( 1 ) ( 2 ) t ；口+ p sr o o dq ， ( 3 ) k 是小于吼的一整数。 - 基于离散对数的环签名过程： s t e p1 签名者计算消息m 的杂凑函数值，作为对称密钥女= 似) ： s t e p2 签名者从 o ，l r 中选择一初始化值v ； s t e p3 签名者为其他环成员随机独立地选择0 ，只) ，( 1s i s ，i s ) 并计算 y = g j ( 8 ，属) ： s t e p4 签名者从o 。( y 【，y 2 ，y ，) = v 中求解y 。： ! 堕塞史子科技大学硕士研究生学位论文数字签名与密码学中的布尔函数的研究 s t e p5 签名者利用其私钥足求解心，成) = g s - ! ( ) 首先任选一整数女( c g ) ，按等式1 求解： 其次，按等式2 求解。，； 最后，按等式3 求解以 s t e p6 消息 的签名为嘏，岛，只；v ；融i ，崩) ，( 口2 ，岛) ，( 吃，反) ) 。 基于离散对数的验证环签名过程： s t e p1 验证者收到签名后，对每一个i = l 2 ， 计算 y ，= g j ( 口，最) s t e p2 验证者计算消息m 的杂凑函数值，作为对称密钥k ： k = ( 村) 。 s t e p3 验证者检验所有的y 是否满足下式： 巴。( m ，y 2 ，y r ) = v 。 如果q ，( y l ，n ，) = v ，验证者就接受亿，p 2 ，耳；v ；( 口i ，岛) ，( 口2 ，应) ，( q ，肛) ) 是 消息村的合法环签名。 方案的安全性分析 给定仁。，a ) ，易于求解对应的y ，。如果攻击者在不知任何一位群成员私钥s j ，那 么从y ，计算出满足条件的缸，成) 是非常困难的；他可以任意猜测一对0 ，成) 但满 足条件的概率为_ ! l ：上，由于p j 是一大素数，所以成功概率是非常小的。由于攻 p l q 【po 击者总可以获得一和h ，属) ，但他想计算出群成员私钥置，必须首先从g “中计算出 t ，而这是一离散对数难题。 环签名方案在现实中有着广泛的应用环境，比如用匿名方式透露权威信息 等。 3 1 3 一个可验证的环签名方案 作者在文献 2 4 中提出了一个可验证的环签名方案，它除了具有以上介绍 的所有环签名的特征外，还具有如下特征：当签名者想向验证者证明他是签名者 第三章数字签名体制的研究与设计 1 9 时，验证者能够根据他提供的信息确认他是真正的签名者；此外，没有签名者的 参入，没有人可以确定是谁签的名。 我们仍然假设已经存在一公开单向杂凑函数 o 和一公用对称加密函数算法 e 。对任一1 一b i t 长的密钥，函数最是作用在b b i t 长的字符串的一个置换。 本文中，带密钥的联合函数仍选3 1 _ 3 节签名方案中的联合函数。 每一个环成员，比如a ，按如下计算他的参数， 选择一个大素数p 。，使得在g f ( p 。) 计算离散对数非常困难，q ，是p ，一1 的一 个素数因子。，是q 一1 的一个大素数因子，g ，是g f ( p ，) 一个阶为吼的生成元；成 员a 的两个私钥为和氏，满足。矿x 。c 锈，两个公钥为y = 昌“r n o d p 和 y = g ，m o dp 。 基于离散对数的陷门单向函数 定义陷门单向函数喜( 口，圆为g 似，声) = 咒，4 t 4 d m 。d e ，它的反函数g , - t 劬为 g ，。( y ) = ( a ，卢) ，其中 a - = y g 一：n o dp ， ( 4 ) 口+ = a r o o d q ，( 5 ) g j ；x a , 口。+ _ 卢m o dq ， ( 6 ) k 是一满足k o 的整数。 可验证环签名过程如3 1 2 节的基于离散对数的环签名方案的签名过程一 样，如下： 可验证环签名过程： s t e p1 签名者首先计算消息m 的杂凑函数值作为对称密钥k ，k = ( m ) ； s t e p2 签名者从如，l r 随机选择一初始值v ； s t e p3 签名者为其他环成员从如，1 尹中随机独立地选择如。鼢，( 1 s f - r ，