rsa算法的研究及其在数字签名技术中的应用

rsa算法的研究及其在数字签名技术中的应用内容摘要：

用的算法加上一个密钥加上密文的样本必须不足以确定另一个密钥 燕山大学本科生毕业设计 (论文 ) 7 (6)步骤 6 解密变换：对密文 c m=cd(modn) 如果第三者进行窃听时，他会得到几个数： m,e,n(=pq)， c… 他如果要解码的话，必须想办法得到 d。 所以，他必须先知道 p， q，即对 n作素因子分解，而分解 1024位的素数 n却是非常困难的。 RSA数字签名体制的研究 RSA数字签名体制使用了 RSA公开密钥密码算法进行数字签名，鉴于RSA算法在实践中已经被证明了的安全性， RSA数字签名体制在许多安全标准中得以广泛应用。 ISO/IEC 9796和 ANSI 理标准 FIPS 1862已经将 RSA作为推荐的数字签名标准算法之一 [5]。 RSA数字签名算法，包括签名算法和验证签名算法。 它是利用的 RSA算法的加密和解密算法的原理进行的一种数字签名，实际上是通过一个 Hash函数来实现的产生消息摘要 (MD)来实现的所需加密的对象。 数字签名的特点是它代表了消息的特征，消息如果发生改变，数字签名的值也将发生改变，不同的消息将得到不同的数字签名。 安全的数字签名使接收方可以得到保证：消息确实来自发送方。 因为签名的私钥只有发送方自己保存，他人无法做一样的数字签名，如果第三方冒充发送方 发出一个消息，而接收方在对数字签名进行解密时使用的是发送方的公开密钥，只要第三方不知道发送方的私有密钥，加密出来的数字签名和经过计算的数字签名必然是不相同的，这就提供了一个安全的确认发送方身份的方法，即数字签名的真实性得到了保证。 数字签名通过认证技术来辨认真伪。 认证技术主要包括数字签名认证、身份认证以及公开密钥证明等。 数字签名认证机制提供了一种对数字签名进行鉴别的方法；身份认证机制提供了辨别和确认通信双方真实身份的方法；公开密钥证明机制则对密钥进行验证。 网络时代中，人们验证数字签名来确定你正在和谁打交道， 验证你的文件是否已被黑客篡改。 数据的安全性和真实性已成为网络安全中至关重要的一部分。 数字签名类似手书签名，它具有以 下的性质： 能够验证签名产生者的身燕山大学本科生毕业设计 (论文 ) 8 份，以及产生签名的日期和时间；能用于证实被签消息内容；数字签名可由第三方验证，从而能够解决通信双方的争议 [10]。 为了实现数字签名的以上性质，它就应满足下列要求： (1)条件 1 签名是可信的：任何人都可以验证签名的有效性； (2)条件 2 签名是不可伪造的：除了合法的签名者外，任何人伪造其签名是困难的； (3)条件 3 签名是不可复制的：对一个消息的签名不 能通过复制变为另一个消息的签名。 如果一个消息的签名是从别处复制得到的，则任何人都可以发现消息与签名之间的不一致性，从而可以拒绝签名的消息； (4)条件 4 签名的消息是不可改变的：经签名的消息不能篡改，一旦签名的消息被篡改，任何人都可以发现消息与签名之间的不一致性； (5)条件 5 签名是不可抵赖的：签名者事后不能否认自己的签名。 可以由第三方或仲裁方来确认双方的信息，以做出仲裁。 为了满足数字签名的这些要求，例如，通信双方在发送消息时，既要防止接收方或其他第三方伪造，又要防止发送方因对自己的不利而否认，也就是说，为了保证数字签名的真实性。 数字签名的原理是： (发送方和接收方根据要求各自产生自己的一对公钥和私钥 ) (1)步骤 1 被发送文件采用某种算法对原始消息进行运算，得到一个固定长度的数字串，称为消息摘要 (MD)，不同的消息得到的消息摘要各异，但是对相同的消息它的消息摘要却是唯一的； (2)步骤 2 发送方生成消息的消息摘要，用自己的私钥对摘要进行加密来形成发送方的数字签名； (3)步骤 3 这个数字签名将作为消息的附件和消息一同用接收方的公钥进行加密，将加密后的密文一起发送给接收方； (4)步骤 4 接收 方首先把接收到的密文用自己的私钥解密，得到原始消息和数字签名，再用发送方的公钥解密数字签名，随后用同样的算法计算出消息摘要； (5)步骤 5如果计算出来的消息摘要和发送方发送给他的消息摘要 (通过燕山大学本科生毕业设计 (论文 ) 9 解密数字签名得到的 )是相同的，这样接收方就能确认数字签名确实是发送方的，否则就认为收到的消息是伪造的或是中途被篡改的。 Hash函数 的研究 Hash函数是一种将任意长度的消息压缩为某一固定长度的消息摘要函数。 Hash函数的输入为任意长度的消息，其输出为固定长度的消息。 一个Hash函数是一个多对一的映射。 Hash函数可以用于数字签名，将 Hash函数应用于数字签名有许多好处。 一方面加快签名的速度；另一方面是可以破坏被攻击者用于消息伪造的数学结构。 Hash函数除了应用于数字签名之外，还可以用于其他方面，比如消息的完整性检测。 为了保证消息的完整性，及时发现消息是否被非法篡改，可以在消息传输之前对消息做 Hash变换，然后对消息进行传输，对于接收到的消息也做 Hash变换，将传输前的消息的 Hash变换值与接收到的消息的 Hash变换值作比较，如果两者相同，则可以认为消息在传输过程中没有被篡改，否则消息一定被非法篡改。 常见的 Hash函数有 Hash函数 MD4， MD5和安全 Hash算法 SHA等 [13]。 首先对 MD5 的算法进行研究， MD5 消息摘要算法是由 Rivest(公开密钥密码 RSA 算法的设计者之一 )所设计的单向散列函数， MD5 不基于任何假设和密码体制，它采用了直接构造的办法，速度很快，非常实用。 MD5算法的 典型应用是对一段信息 (message)产生信息摘要 (MD),以防止被篡改。 MD5 将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的 MD5 信息摘要。 如果在以后传播这个文件的过程中，无论文件的内容发生了任 何形式的改变 (包括人为修改或者下载过程中线路不稳定引起的传输错误等 )，只要你对这个文件重新计算 MD5 时就会发现信息摘要不相同，由此可以确定你得到的只是一个不正确的文件。 如果再有一个第三方的认证机构，用 MD5 还可以防止文件作者的“抵赖”，这就是所谓的数字签名应用。 MD5 还广泛用于加密和解密技术上。 比如在 unix 系统中用户的密码就是以 MD5(或其它类似的算法 )经加密后存储在文件系统中。 当用户登录的时候，系统把用户输入的密码计算成 MD5 值，然后再去和保燕山大学本科生毕业设计 (论文 ) 10 存在文件系统中的 MD5 值进行比较，进而确定输入的密码是否正确。 通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。 这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。 MD5 算法以任意长度的消息作为输入，产生一个 128 比特消息散列值(或称消息摘要 )作为输出。 具体的算法步骤如下： (1)步骤 1 附加填充比特，对消息进行填充，使消息的长度 (比特数 )与448 模 512 同余，即恰好为一个比 512 比特的倍数仅小 64 位的数。 (2)步骤 2 附加消息长度值，将用 64 比特表示的初始消息 (填充前 )的长度 (比 特数 )附加在步骤 1 的结果后。 (3)步骤 3 初始化 MD 缓存， MD5 算法使用了一个 4 个字 (128 比特，MD4 中每个字 32 比特 )的缓存来计算消息摘要，它们主要用来存放 MD5 的中间及最终结果。 缓存可以看成是 4 个 32 比特的寄存器 (A， B， C， D)。 (4)步骤 4 以 512 比特 (16 个字 )分组处理消息，这一步是 MD5 算法的主循环，以 512 比特作为分组，在后面有详细的介绍。 本章小结 本章详细研究了公钥密码体制中应用最广泛的 RSA密码体制的基本原理， RSA数字签名体制的基本原理， Hash函数的基本原理 ,这些 是后面在 c++语言中实现的基础。 燕山大学本科生毕业设计 (论文 ) 11 第 3章 RSA算法的仿真 RSA算法的参数的选择 为保证算法的安全性，必须要认真的选择 RSA算法的参数。 参数 p， q的选择 (1)要求 1 p和 q必须为强素数，且通常 p和 q的位数相等。 只有 p和 q足够大， n=pq才能足够大，才能抵抗因子分解的攻击。 根据目前因子分解的能力，应当选择 n为 1024位或 2048位。 这样就要求 p和 q的选择应为 512位或 1024位左右。 (2)要求 2 p和 q差值必须较大，最好与 p、 q位数接近。 由 [(p+q)2/4]n=[(p+q)2/4]pq=(pq)2/4,如果 p和 q的差值较小，则 (pq)2/4也小，因此 (pq)2/4稍大于 n， (pq)/2稍大于 n。 可得 n的如下分解法：顺序检查大于 n 的每一个整数 x，直到找到一个 x使得 x2n是某一整数 (记为 y)的平方。 有 x2n=y2，得 n=(x+y)(xy)。 (3)要求 3 p1和 q1的最大公因数应该很小。 (4)要求 4 p和 q应大到使用因子分解 n为计算上的不可能。 参数 e的选择 (1)要求 1 e不能太小。 (2)要求 2 e应使其在模 Φ (n)下的阶为最大。 参数 d的选择 应使 d4n且越大越好，如 n为 1024位时， d的长度应大于 256位。 总体考虑，尽量降低 e的长度，不要降低 d的长度。 RSA算法 的 仿真 产生 消息摘要的 设计 在 MD5算法中，首先需要对信息进行填充，使其字节长度对 512求余的结果等于 448。 因此，信息的字节长度 (Bits Length)将被扩展至 N*512+448，燕山大学本科生毕业设计 (论文 ) 12 即 N*64+56个字节 (Bytes)， N为一个正整数。 填充的方法如下，在信息的后面填充一个 1和无数个 0，直到满足上面的条件时才停止用 0对信息的填充。 然后，在在这个结果后面附加一个以 64位二进制表示的填充前信息长度。 经过这两步的处理，现在的信息字节长度 =N*512+448+64=(N+1)*512，即长度恰好是 512的整数倍。 这样做的原因是为满足后面处理中对信息长度的要求。 MD5中有四个 32位被称作链接变量的整数参数，他们分别为：A=0x01234567， B=0x89abcdef， C=0xfedcba98， D=0x76543210。 当设置好这四个链接变量后，就开始进入算法的四轮循环运算。 循环的次数是信息中 512位信息分组的数目。 将上面四个链接变量复制到另外四个变量中： A到 a， B到 b， C到 c， D到 d。 主循环有四轮，每轮循环都很相似。 第一轮进行 16次操作。 每次操作对a、 b、 c和 d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。 再将所得结果向右环移一个不定的数，并加上 a、 b、 c或 d中之一。 最后用该结果取代 a、 b、 c或 d中之一。 以一下是每次操作中用到的四个非线性函数 (每轮一个 )。 第一轮 (操作 0至 15)： F(X， Y， Z)=(X∧ Y)∨ ((172。 X)Z) 第二轮 (操作 16至 31)： G(X， Y， Z)=(X∧ Z)∨ (Y∧ (172。 Z)) 第三轮 (操作 32至 47)： H(X， Y， Z)=X⊕ Y⊕ Z 第四轮 (操作 48至 63)： I(X， Y， Z)=Y⊕ (X∨ (172。 Z)) 其中，⊕使逐位异或，∧是按位与，∨是按位或， 172。 是按位取反。 这四个函数的说明：如果 X、 Y和 Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。 F是一个逐位运算的函数。 即，如果 X，那么 Y，否则 Z。 函数 H是逐位奇偶操作符。 假设 Mj表示消息的第 j个子分组 (从 0到 15)， FF(a,b,c,d,Mj,s,ti)表示 a=b+((a+(F(b,c,d)+Mj+ti) GG(a,b,c,d,Mj,s,ti)表示 a=b+((a+(G(b,c,d)+Mj+ti) HH(a,b,c,d,Mj,s,ti)表示 a=b+((a+(H(b,c,d)+Mj+ti) II(a,b,c,d,Mj,s,ti)表示 a=b+((a+(I(b,c,d)+Mj+ti) 燕山大学本科生毕业设计 (论文 ) 13 这四轮 (64步 )是： 第一轮 FF(a,b,c,d,M0,7,0xd76aa478) FF(d,a,b,c,M1,12,0xe8c7b756) FF(c,d,a,b,M2,17,0x242070db) FF(b,c,d,a,M3,22,0xc1bdceee) FF(a,b,c,d,M4,7,。