实现数字签名的RSA算法的设计与实现

课程实践报告书课程实践报告书 课程名称 密码学与网络安全课程实践 题 目 实现数字签名的 RSA 算法的设计与实现 学生姓名 专 业 班 别 学 号 指导老师 日 期 2016 年 6 月 18 日 第 1 页 实现数字签名的实现数字签名的 RSA 算法的设计与实现算法的设计与实现 摘摘 要要 随着计算机网络和信息技术的发展 信息安全在各领域发挥着越来越重要 的作用 其中密码学已成为信息安全技术的核心 本文主要介绍了信息加密技 术的应用 RSA算法是目前公认的在理论和实际应用中最为成熟和完善的一种公钥密码 体制 它是第一个既能用于数据加密也能用于数字签名的算法 是公钥密码体 制的代表 数字签名是起到身份认证 核准数据完整性的一种信息安全技术 它通过认证技术来辨认真伪 RSA数字签名体制使用的是RSA公开密钥密码算法 进行数字签名 本文主要内容包括 第一 对RSA算法进行系统的介绍 第二 介绍RSA数字 签名的一些基本概念和数字签名的理论实现过程 第三详述RSA数字签名的设计 与实现 主要实现的模块包括RSA密钥的产生 一对公钥和私钥 RSA加密算法 和解密算法的实现 第四 对该系统进行了整体的测试和分析改进 关键字 关键字 RSA算法 加密 解密 RSA数字签名 第 2 页 目目 录录 1 引言 3 1 1 课题的研究背景 3 1 2 课题的研究意义 3 2 RSA 算法和 RSA 数字签名算法的概念设计 3 2 1 RSA 算法的概念和原理 3 2 1 1 RSA 算法介绍 3 2 1 2 RSA 算法的实现原理 3 2 2 RSA 数字签名基本概念和 RSA 数字签名算法的实现原理 4 2 2 1 RSA 数字签名基本概念 4 2 2 2 RSA 数字签名算法的实现原理 5 3 RSA 数字签名的逻辑设计与实现 6 第 3 页 3 1 RSA 数字签名的总体设计 6 3 1 1 RSA 数字签名所需实现的功能 6 3 1 2 总体要求和设计 6 3 2 各部分的设计实现 7 3 2 1 密钥产生的实现 7 3 2 2 产生消息摘要的设计实现 10 3 2 3 数字签名的设计实现 12 3 2 4 验证数字签名的设计与实现 15 3 2 5 RSA 数字签名的运行结果 18 4 软件的整体测试和分析改进 18 4 1 软件的整体测试 18 4 2 性能分析与改进设想 19 开发体会 19 参考文献 20 第 4 页 1 1 引言引言 1 11 1 课题的研究背景课题的研究背景 随着电子信息技术的迅速发展 人类已步入信息社会 但是由于整个社会 形成了一个巨大的计算机网络 任何一个计算机网络出现的安全问题 都会影 响整个国家的网络安全 所以信息安全 计算机网络安全问题已引起了人类的 高度重视 网络的安全措施应是能全方位地针对各种不同的威胁和脆弱性 这 样才能确保网络信息的保密性 完整性和可用性 现代密码学已成为信息安全技术的核心 密码学是以研究通信安全保密的 学科 即研究对传输信息采用何种秘密的变换以防止第三者对信息的窃取 RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法 它 易于理解和操作 也十分流行 随着越来越多的商业应用和标准化工作 RSA已 经成为最具代表性的公钥加密技术 现今 网上交易加密连接 网上银行身份 验证 各种信用卡使用的数字证书 智能移动电话和存储卡的验证功能芯片等 大多数使用RSA技术 1 21 2 课题的研究意义课题的研究意义 随着电子商务的发展 网络上资金的电子交换日益频繁 如何防止信息的 伪造和欺骗成为非常重要的问题 目前关于数字签名的研究主要集中点是基于 公钥密码体制的数字签名 手写签名的每一项业务都是数字签名的潜在用场 数字签名可以提供数据完整性 真实性和不可否认性 数字签名技术在身份识 别和认证 数据完整性 抵赖等方面具有其它技术无法替代的作用 它在军事 电子商务和电子政务等领域有着极广泛的应用 而在公钥体制中 RSA是一个较 为完善的公钥密码算法 不仅能够同时用于加密和数字签名 而且易于理解和 操作 是被广泛研究的公钥密码算法 因此 基于RSA的数字签名具有较强的研 究性和实际应用意义 2 2 RSARSA 算法和算法和 RSARSA 数字签名算法的概念数字签名算法的概念设计设计 2 12 1 RSARSA 算法的概念和原理算法的概念和原理 2 1 12 1 1 RSARSA 算法介绍算法介绍 RSA算法是一种公钥密码算法 实现RSA算法包括生成RSA密钥 加密和解密 数据 RSA算法是第一个能同时用于加密和数字签名的算法 也易于理解和操作 RSA是被研究得最广泛的公钥算法 RSA的缺点主要有 A 产生密钥很麻烦 受到素数产生技术的限制 因而难 第 5 页 以做到一次一密 B 分组长度太大 为保证安全性 n 至少也要 600 bits 2 1 22 1 2 RSARSA 算法的实现原理算法的实现原理 1 随机选择两个不同的素数p和q 它们的宽度是密钥宽度的二分之一 2 计算出p和q的乘积n 3 在2和 n 之间随机选择一个数e e 必须和 n 互素 整数e用做加 密密钥 其中 n p 1 q 1 4 从公式ed 1 mod n 中求出解密密钥d 5 得公钥 e n 私钥 d n 6 公开公钥 但不公开私钥 7 将明文P 假设P是一个小于n的整数 加密为密文C 计算方法为 C P e mod n 8 将密文C解密为明文P 计算方法为 P C d mod n 然而只根据n和e 不是p和q 要计算出d是不可能的 因此 任何人都可对 明文进行加密 但只有授权用户 知道d 才可对密文解密 2 22 2 RSARSA 数字签名基本概念和数字签名基本概念和 RSARSA 数字签名算法的实现原理数字签名算法的实现原理 2 2 12 2 1 RSARSA 数字签名基本概念数字签名基本概念 RSA数字签名体制使用了RSA公开密钥密码算法进行数字签名 鉴于RSA算法 在实践中已经被证明了的安全性 RSA数字签名体制在许多安全标准中得以广泛 应用 ISO IEC 9796和ANSI X9 30 199X 以及美国联邦信息处理标准FIPS 186 2已经将RSA作为推荐的数字签名标准算法之一 RSA数字签名算法 包括签名算法和验证签名算法 它是利用的RSA算法的 加密和解密算法的原理进行的一种数字签名 实际上是通过一个哈希函数来实 现的 本设计是通过的MD5算法 产生消息摘要MD来实现的所需加密的对象 数字签名的特点是它代表了消息的特征 消息如果发生改变 数字签名的 值也将发生改变 不同的消息将得到不同的数字签名 安全的数字签名使接收 方可以得到保证 消息确实来自发送方 因为签名的私钥只有发送方自己保存 第 6 页 他人无法做一样的数字签名 如果第三方冒充发送方发出一个消息 而接收方 在对数字签名进行解密时使用的是发送方的公开密钥 只要第三方不知道发送 方的私有密钥 加密出来的数字签名和经过计算的数字签名必然是不相同的 这就提供了一个安全的确认发送方身份的方法 即数字签名的真实性得到了保 证 数字签名类似手书签名 它具有以下的性质 1 能够验证签名产生者的身份 以及产生签名的日期和时间 2 能用于证实被签消息内容 3 数字签名可由第三方验证 从而能够解决通信双方的争议 为了满足数字签名的这些要求 例如 通信双方在发送消息时 既要防止 接收方或其他第三方伪造 又要防止发送方因对自己的不利而否认 也就是说 为了保证数字签名的真实性 数字签名的原理是 发送方和接收方根据要求各自产生自己的一对公钥 和私钥 1 被发送文件采用某种算法对原始消息进行运算 得到一个固定长度的数 字串 称为消息摘要 MD 不同的消息得到的消息摘要各异 但是对相同的 消息它的消息摘要却是唯一的 2 发送方生成消息的消息摘要 用自己的私钥对摘要进行加密来形成发送 方的数字签名 3 这个数字签名将作为消息的附件和消息一同用接收方的公钥进行加密 将加密后的密文一起发送给接收方 4 接收方首先把接收到的密文用自己的私钥解密 得到原始消息和数字签 名 再用发送方的公钥解密数字签名 随后用同样的算法计算出消息摘要 5 如果计算出来的消息摘要和发送方发送给他的消息摘要 通过解密数字 签名得到的 是相同的 这样接收方就能确认数字签名确实是发送方的 否则 就认为收到的消息是伪造的或是中途被篡改的 数字签名的原理图如2 1所示 A B 第 7 页 用A的私钥加密 用B的公钥 用B的私钥 用A的公钥解密 数字签名 加密 解密 核实签名 图2 1 数字签名的原理 2 2 22 2 2 RSARSA 数字签名算法的实现原理数字签名算法的实现原理 RSA数字签名算法分为以下两个步骤 1 签名算法 包括两步 消息摘要计算 RSA加密 1 消息摘要MD的计算 消息在签名前首先通过MD5计算 生成128位的消 息摘要 MD5函数是一种单向散列函数 它将任意长度的消息压缩成128位的消 息摘要 应用MD5的单向性 即给定散列值 计算消息很难 和抗碰撞性 即给定 消息M 要找到另一消息M 并满足两者的散列值很难 可以实现信息的完整性 检验 另外该函数的设计不基于任何假设和密码体制而直接构造 执行的速度 快 是一种被广泛认可的单向散列算法 2 对MD作RSA加密算法 采用签名者的私钥加密消息摘要 得到加密后的 字符串即数字签名 2 验证签名算法 RSA解密 对消息摘要计算和比较 验证签名算法包括两步 RSA解密得签名者的消息摘要 验证者对原消息计 算摘要 比较两个消息摘要 验证签名的过程输入为消息 签名者的公钥 签 名 输出为验证的结果 即是否是正确的签名 1 RSA解密 签名实际是加密的消息摘要 用以上所述的RSA解密方法采 用签名者的公钥对这个加密的消息摘要解密 解密的结果应为128位的消息摘要 2 消息摘要计算和比较 验证者对消息用MD5算法重新计算 得到验证者 自己的消息摘要 验证者比较解密得到的消息摘要和自己的消息摘要 如果两 者相同 则验证成功 可以确认消息的完整性及签名确实为签名者的 否则 验证失败 确认签名被冒充或是被篡改 D EDE 第 8 页 3 3 RSARSA 数字签名的逻辑设计与实现数字签名的逻辑设计与实现 3 13 1 RSARSA 数字签名的总体设计数字签名的总体设计 3 1 13 1 1 RSARSA 数字签名所需实现的功能数字签名所需实现的功能 在本软件中需要实现的功能有以下几个 1 生成RSA密钥 公钥ke e n 私钥kd d n 2 利用MD5算法计算出消息摘要MD 3 数字签名的实现 用私钥d对消息摘要进行加密计算 RSA算法中的加 密方法 4 验证数字签名 用公钥e对数字签名进行解密计算 RSA算法中的解密 方法 得到的解密结果与 2 步计算出的消息摘要比较 如果两个消息摘要一 样则签名成功 3 1 23 1 2 总体要求和设计总体要求和设计 本软件的总体要求有 1 按要求生成非对称密钥 公钥和私钥 2 按任意写入的的消息字符串 明文信息 生成所需要的消息摘要MD 3 在本设计中用产生的私钥d根据RSA算法的加密原理对所生成的消息摘要 进行加密运算 得到数字签名 4 在本设计中用产生的公钥e根据RSA算法的解密原理对所加密的消息摘要 即数字签名进行解密运算 得到对应的消息摘要 在本设计中标示的为解密信 息 比较两个消息摘要 验证数字签名者的身份的真实与否 5 提示信息完整 操作舒适 图形界面雅观 本软件的总体设计都是基于C 的开发环境 采用的是Microsoft Visual c 6 0的运行环境 3 23 2 各部分的设计实现各部分的设计实现 3 2 13 2 1 密钥产生的实现密钥产生的实现 在密钥的产生部分中起决定性作用的是素数的选择 对随机数作素性检测 若通过则为素数 否则增加一个步长后再做素性检测 直到找出素数 素性检 测采用Fermat测试 这个算法的理论依据是费尔马小定理 如果m是一个素数 第 9 页 且a不是m的倍数 那么根据费尔马小定理有 a m 1 1 mod m 实际应用时 a m 1 1 mod m a m a mod m a a m mod m 因此对于整数m 只需计算a m mod m 再将结果与a比较 如果两者相同 则m为素数 选取a 2 则a一定不 会是任何素数的倍数 根据所选的素数的不同产生不同的密钥 密钥的理论产生模块流程图如图3 1所示 图3 1 密钥产生 密钥产生的部分代码实现 CString str 第一步 产生任意素数 GeneratePrimeNumbers 第二步 计算 n p q m n m Prime1 m Prime2 第三步 0 p 1 q 1 m Undef m Prime1 1 m Prime2 1 第四步 选择 e SelectE 第五步 计算D CalculateD 显示公钥和私钥 1 公钥 KU e n str Format d d m e m n m public key SetWindowText str 2 私钥KU d n 第 10 页 str Format d d m d m n m private key SetWindowText str 选择一个 e 使 e 与 m Undef互素 选择e的函数的实现 SelectE CString str for float i 2 i 100000 i if IsRelativePrime float m Undef float i m e long i return 互为素数的函数的实现 IsRelativePrime float X float Y float R 输入 X Y if X Y 如果X较小则交换两个值 X X Y Y X Y 第 11 页 X X Y 在这时X总是比Y大 for if Y 0 break R fmod X Y X Y Y R if X 1 return false else return true 互素 计算D的函数的实现 CalculateD float d long d dash CString str for float k 1 k 100000 k 第 12 页 d m Undef k 1 m e d dash long m Undef k 1 m e if d d dash m d d return 产生素数的函数的实现 GeneratePrimeNumbers CString str UpdateData TRUE 通过以下两个函数可获得两个大素数 但增加了计算复杂性 为了方便 直接给定素数 m Prime1 FindPrime 1 m Prime2 FindPrime m Prime1 m Prime1 47 m Prime2 71 3 2 23 2 2 产生消息摘要的设计实现产生消息摘要的设计实现 计算消息摘要的理论实现流程图如图3 2所示 第 13 页 图3 2 消息摘要计算流程 在以上流程图中其中循环处理块是最重要的一步 也是MD5的核心算法 在 这一步中包括了 1 把四个连接变量复制到了四个变量a b c d中 使a A b B c C d D 其中a b c d组合成128位的寄存器 且在实际算法运算中保存中间结 果和最终结果 2 将当前的512位块分解为16个子块 每个子块为32位 3 要循环四轮 每一轮处理一个块中的16个子块 四轮的第一步进行不 同的处理 其他的相同 每一轮有16个输入子块M 0 M 1 M 15 或表示为M i 其中i为0 15 t是常量数组 包含64个元素 每个元素为32位 数组t表示为t 1 t 2 t 64 或t k k为1 64 MD5的循环四轮操作过程用下式表示 a b a proccessP b c d M i T k s s表示循环左移s位 产生消息摘要的主要代码如下 int i int Index 初始化MD5所需常量 Init 计算追加长度 Append WriteMessage length 对原始信息进行补位 得到消息摘要 第 14 页 for i 0 i m AppendByte i if i 0 WriteMessage unsigned char 0 x80 else WriteMessage unsigned char 0 x0 将原始信息长度附加在补位后 的数据后面 for i 0 i 8 i WriteMessage m MsgLen i 位块数组 unsigned char x 64 0 循环 将原始信息以64字节为一组拆分进行处理 for i 0 Index 1 i WriteMessage length i x Index WriteMessage i if Index 63 Index 1 将64字节位转换为16个字节 Transform x 将寄存器ABCD的最终值转换为16进制返回给用户 return ToHex UpperCase 第 15 页 3 2 33 2 3 数字签名的设计实现数字签名的设计实现 数字签名的理论实现流程图如图3 3所示 数字签名 就是通过在数据单 元上附加数据 或对数据单元进行加密变换 从而使接收者可以确认数据来源 和完整性 数字签名是防止他人对传输的文件进行破坏 以及确定发信人的身 份的手段 数字签名中的加密算法就是应用的RSA加密原理 而它的验证算法则 是应用的RSA解密原理 图3 3 数字签名的实现流程 RSA 的加密 解密过程都为求一个整数的整数次幂 再取模 如果按其含 义直接计算 则中间结果非常大 有可能超出计算机所允许的整数取值范围 为了减小中间结果和提高加 解密运算中指数运算的有效性 本设计采用了快 速指数算法 它的运算过程为 假如要算 a m mod n 1 将 m 表示为二进制的形式 2 初始化 c 0 d 1 c 在这里表示指数的部分结果 它的终值即为指数 m d 是中间结果 它的终值即为所求结果 3 从二进制数的最高位到最低位开始对每一位都用公式 1 进行运算 得到 的 d 为该步的结果 公式 1 c 2 c d fmod d d n 4 若二进制数是 1 则在上面的运算后继续以下运算 c c 1 d fmod d a n 得到的结果 d 才为该步的最终结果 数字签名主要实现过程的代码如下 消息摘要 8 位为一组 一个字符一组 char message 200 从文本框中得到消息摘要 结束 第 16 页 m message GetWindowText message 200 len strlen message char showstr 1000 int NO BITS 32 double c 0 d 1 char bits 100 double n double m n unsigned char ch double data 19 long i k NO BITS int sizeof d sizeof double 将十进制数私钥 d 转换为二进制 D to B m d 32 bits 得到合适的字节 GetOnlyProperBits bits k NO BITS strlen bits 1 for int ii 0 ii 0 i c 2 c d fmod d d n if bits NO BITS i 1 c c 1 d fmod data d n 从 d 中读取字符放入 result 中 result ii d 把字符串变为十六进制数后连接字符串 strcat showstr longtohex d 结束循环 显示结果 m result SetWindowText showstr 字符串变为 16 进制数的函数的实现 longtohex long x char str 8 int i 0 第 18 页 商 int a 余数 int b long tt x while tt 16 a tt 16 b tt 16 switch b case 0 str i 0 break case 1 str i 1 break case 2 str i 2 break case 3 str i 3 break case 4 str i 4 break case 5 str i 5 break case 6 str i 6 break case 7 str i 7 break case 8 str i 8 break case 9 str i 9 break case 10 str i A break case 11 str i B break 第 19 页 case 12 str i C break case 13 str i D break case 14 str i E break case 15 str i F break i tt a str i 0 strrev str return str 3 2 43 2 4 验证数字签名的设计与实现验证数字签名的设计与实现 图 3 4 验证数字签名流程 验证数字签名的正确与成功性 主要是比较得到的两次消息摘要是否一样 如果验证方用签名方的公钥解密得到消息摘要 即是本设计中得到的解密信息 和他自己计算得到的消息摘要 在本系统中为第一次计算得到的消息摘要 是 一样的 则证明签名是正确的 没有被篡改或是冒充 验证签名的原理则是根 据RSA的解密算法 具体的理论流程图如图3 4所示 在本设计中签名和验证 签名都在同一界面实现 不进行文件的双方传输 验证数字签名的过程时应用的解密算法是RSA的解密原理 而RSA的解密过 程也应用了求一个整数的整数次幂 再取模的运算 在此也采用了快速指数算 法 具体的算法过程同RSA的加密过程中应用的快速指数算法是一样的 验证数字签名主要实现过程的代码如下 第 20 页 int NO BITS double c 0 d 1 char bits 100 double n double m n double data 19 long i k int sizeof d sizeof double 用于存储解密信息 char message 200 将十进制数公钥 e 转换为二进制 D to B m e 32 bits GetOnlyProperBits bits k NO BITS strlen bits 1 for int j 0 j 0 i c 2 c d fmod d d n 第 21 页 if bits NO BITS i 1 c c 1 d fmod data d n 结束循环 从 d 中读取字符放入 message 中 message j d 显示结果 m mingwen SetWindowText message 3 2 53 2 5 RSARSA 数字签名的运行结果数字签名的运行结果 图 3 5 RSA 数字签名的运行结果 第 22 页 在本软件中得到二个消息摘要 根据写入的消息 明文信息 计算出来的 消息摘要 解密数字签名得到的消息摘要 即是本设计中的解密信息 如果 两个消息摘要是一样的则证明RSA数字签名者的身份的真实性 从而实现了RSA 数字签名 该系统的运行结果如图3 5所示 产生的消息摘要和解密得到的消息 摘要 在此处是解密信息 是完全一样的 则证明了数字签名的真实性 4 4 软件的整体测试和分析改进软件的整体测试和分析改进 4 14 1 软件的整体测试软件的整体测试 1 测试密钥的生成 产生密钥的前提是要有两个素数的生成 密钥的产 生依赖于素数的生成 素数生成不一样则密钥也会不相同 在本设计中素数是 47 和 71 则相对应的的密钥是公钥 3 3337 和私钥 2147 3337 2 测试消息摘要 MD 的生成 写入的消息 明文信息 不一样得到消息 摘要就有所区别 但是在产生消息摘要时所使用的计算方法是一样的即 MD5 算 法 该算法的核心是其中的四轮循环 如果四轮循环中的一个细节出了问题则 所产生的 MD 便是相差极远 如若明文信息是 dfgfhfhgjk 则得到的消息摘要 A4127B4881D24B01A85696477A07C17C 若明文信息是 cvnjj 则得到的消息摘 要是 A1E2C15FF4C9F4D407EF33D1AC56C632 3 测试数字签名的生成 根据 RSA 算法的加密原理对不同的消息摘要 MD 进行加密运算 得到的便是不同的数字签名 DS 若消息摘要 MD 是 A1E2C15FF4C9F4D407EF33D1AC56C632 则得到的 DS 是 DD6865036D64198985366C98523593F286980023D6D36411F361F050 若消息摘要 MD 是 66F753A8408C91EC0B16D91A1100902A 则得到的 DS 是 1F1F98F2410D1F5931F366CD686369371D61F236CD6DD6D693936C9350D 4 测试数字签名的真实与否 验证数字签名 根据 RSA 算法的解密原 理对