毕业设计（论文）非对称密码学加密算法的研究与设计――RSA算法的程序设计、

1、目目 录录 设计总说明.3 introduction .5 前 言.8 1 密码学的概述.9 1.1 密码学的基本术语.9 1.1.1 密码学.9 1.1.2 密钥.9 1.1.3 加密与解密.10 1.1.4 密码体制.10 1.1.5 鉴别、完整性和抗抵赖.10 1.2 密码学的应用.11 1.3 密码算法的概念及其分类.11 1.3.1 对称密码算法.11 1.3.2 公开密钥算法.12 1.3.3 hash 算法.12 1.4 密码编码学的基本概念.13 1.5 密码分析学的基本概念.13 1.6 密码学的信息论基础.14 1.7 密码学的起源和发展.14 1.8 密码算法的安全性.1

2、5 2 公钥密码体制基础.16 2.1 整数算法.16 2.1.1 二进制运算.16 2.1.2 整数除法.16 2.1.3 整除性.16 2.2 模运算.18 2.2.1 模算符.18 2.2.2 余集：zn.18 2.2.3 同余.19 2.2.4 在集合 zn 当中的运算.19 2.2.5 逆.20 2.2.6 加法集和乘法集的不同.21 2.2.7 另外两个集合.21 2.3 素数.22 2.3.1 定义.22 2.3.2 素数的基数.22 2.3.3 素性检验.22 2.3.4 euler phi-(欧拉(n)函数.23 2.3.5 fermat(费尔马)小定理.23 2.3.6 生

3、成素数.25 2.4 素性测试.25 2.4.1 确定性算法.25 2.4.2 概率算法.26 2.4.3 推荐的素性检验.28 2.5 因数分解.29 2.5.1 算术基本定理.29 2.5.2 因数分解方法.29 2.5.3 fermat 方法.30 2.6 中国剩余定理.30 2.7 指数与对数.30 2.7.1 指数.31 2.7.2 对数.31 2.8 分治法基本思想.31 3 rsa 密码系统.33 3.1 rsa 简介 .33 3.2 单向函数.33 3.3 rsa 的加解密过程及算法分析 .34 3.4 rsa 的安全性分析 .37 3.4.1 针对 rsa 的攻击.37 3.

4、4.2 因数分解攻击.37 3.4.3 选择密文攻击.38 3.4.4 对加密指数的攻击.38 3.4.5 对解密指数的攻击.39 3.4.6 明文攻击.39 3.4.7 对模的攻击.40 3.4.8 执行攻击.41 3.5 使用 rsa 的意义.42 4 rsa 的 c 程序实现.43 4.1 rsa 编程设计 .43 4.2rsa 源程序.49 4.3 结束语.59 参考文献.60 致谢.61 设计总说明设计总说明 密码学是信息安全的重要技术，是用于保护国家机密及决策的一个重要工具， 也是保护个人信息以及其他重要资料的重要方法。可以有效保障信息的机密性、完 整性和鉴别。密码学的研究涉及到很

5、多技术的学习，主要包括怎样把数据加密，怎 样传送加密数据，怎样解密加密的数据，使需要数据的合法者得到自己要的数据。 密码学是研究编制密码和破译密码的技术科学。密码学一般包括两个对立统一的 分支学科：密码编码学和密码分析学。密码编码学与密码分析学相辅相成，共处于密 码学的统一体中。现代密码学除了包括密码编码学和密码分析学两个主要的学科外， 还包括一个新产生的分支密码密钥学。它是以密码体系最核心部分的密钥作为研 究对象的学科。密钥管理是一种规程，它包括密钥的产生、分配、存储、保护、销毁 等环节。上述三个分支学科构成了现代密码学的主要科学体系。 公开密钥密码体制是现代密码学的最重要的发明和进展。对信

6、息发送与接收人 的真实身份的验证、对所发出 /接收信息在事后的不可抵赖以及保障数据的完整性 是现代密码学主题的另一方面。 公钥密码算法最主要的特点是加密和解密使用不同 的密钥（公钥和私钥） ，且加密密钥能公开，而仅需保守解密密钥的机密的密码算法。 公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有 密钥才能解密；如 果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能 解密。在这种加密算法中，从公开的加密密钥无法推导出保密的解密密钥，也无法从 加密密钥和密文恢复出相应的明文。最有影响的公钥密码算法是 rsa，它能抵抗到目 前为止己知的所有密码攻击。在公钥体制中，加密密

7、钥不同于解密密钥。人们将加 密密钥公之于众，谁都可以使用；而解密密钥只有解密人自己知道。迄今为止的所 有公钥密码体系中， rsa 系统是最著名、使用最广泛的一种。 非对称密码体制的特点：算法强度复杂、安全性依赖于算法与密钥但是由于其 算法复杂，而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有 一种密钥，并且是非公开的，如果要解密就得让对方知道密钥。所以保证其安全性 就是保证密钥的安全，而非对称密钥体制有两种密钥，其中一个是公开的，这样就 可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。 本课题主要研究加密算法中的非对称密码加密算法 rsa。对密码学做了简单的介 绍

8、，着重介绍了公钥密码体制的基本知识：如二进制运算、整数除法、模运算、欧拉 函数、费尔马小定理、欧几里德算法、概率算法、推荐的素性检验；算术基本定理、 中国剩余定理、分治法基本思想。并分析 rsa 加解密过程及算法实现；针对 rsa 的 攻击做简要分析，如因数分解攻击、选择密文攻击、对加密指数的攻击、对解密指数 的攻击、明文攻击、对模的攻击、执行攻击；rsa 加密算法的优缺点分析。根据理论 基础设计 rsa 算法的程序，并在 vc6.0 软件平台下实现 rsa 算法的加密解密。 rsa 算法是第一个既能用于数据加密也能用于数字签名的算法，算法的名字以发 明者的名字命名。算法中使用的公钥和私钥都是

9、两个大素数（大于 100 个十进制位） 的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 先选择两个大素数 p 和 q（） ，且。计算：n=p*q 然后随机 16 2265536pq、pq 选择加密密钥 e，要求 e 和(p-1)*(q-1)互质。最后，利用 euclid 算法计算解密密钥 d,满 足 e*d=1(mod(p-1)*(q-1)其中 n 和 d 也要互质。数 e 和 n 是公钥，d 是私钥。两个素数 p 和 q 不再需要，应该丢弃，不要让任何人知道。加密信息 m 时，首先把 m 分成等长 数据块 m1，m2，mi，块长 s，其中 2s=n，s 尽可能的大

10、。对应的密文是： (a)；解密时作如下计算：(b)。这就是 rsa 的加解密过mod e ii cmnmod d ii mcn 程。 rsa 可用于数字签名，用(a)式签名，(b)式验证。具体操作时考虑到安全性和 m 信 息量较大等因素，一般是先作 hash 运算。rsa 的安全性依赖于大数分解，但是否等 同于大数分解一直未能得到理论上的证明。目前，rsa 的一些变种算法已被证明等价 于大数分解。不管怎样，分解 n 是最显然的攻击方法。现在，人们已能分解 140 多个 十进制位的大素数。因此，模数 n 必须选大一些，因具体适用情况而定。由于进行的 都是大数计算,使得 rsa 最快的情况也比 d

11、es 慢上 100 倍,无论是软件还是硬件实现。 速度一直是 rsa 的缺陷。一般来说只用于少量数据加密。 关键词：rsa；rsa 算法；加密；解密；非对称密钥；密码学；公钥；私钥。 introduction cryptography is an important information security technologies for protection of state secrets and an important tool for decision-making is also important to protect personal information and othe

12、r information important way. information can effectively protect the confidentiality, integrity and differentiation. cryptography research involves many technical learning, including how to data encryption and how to send encrypted data, how to decrypt the encrypted data, so that the legitimate need

13、s of those who have their own data to the data cryptography is the preparation of the password and decrypt the password of the technical sciences. cryptography usually consists of two branches of the unity of opposites: cryptography and cryptanalysis. cryptography and cryptanalysis complementary stu

14、dy were in the unity of cryptography. in addition to including modern cryptography and cryptanalysis cryptography study two main subjects, but also includes a new branch of production - the password key learning. it is based password system, the core part of the key as the study subjects. key manage

15、ment is a point of order, which includes key generation, distribution, storage, protection, destruction and other links. constitute the three branches of the major modern scientific system of cryptography. public key cryptosystem is the most important of modern cryptography invention and progress. s

16、end and receive information of the real identity verification, on the issue / receive information after the fact of non-repudiation and data integrity protection is the subject of modern cryptography, on the other hand. the main features of public key cryptography algorithm is the encryption and dec

17、ryption use different keys (public key and private key), and the encryption key can open, but only conservative in the confidential decryption key cryptographic algorithm. public key and private key are a pair, if the public key used to encrypt the data, only using the corresponding private key can

18、decrypt; if the private key used to encrypt the data, then only the corresponding public key can be used decryption. in this encryption algorithm, encryption key from the public can not derive the secret decryption key, can not ciphertext from the encryption key and the corresponding plaintext recov

19、ery. the most influential public key cryptography algorithm is rsa, it can resist all the passwords so far known attacks. in the public key system, the encryption key is different from the decryption key. it will be made public encryption key, anyone can use; the decryption key only to decrypt thems

20、elves know. so far all the public key system, rsa system is the best known and most widely used one. asymmetric cryptography features: intensity of complex algorithms, security depends on the algorithm and key, but because of its computational complexity, and makes encryption and decryption speed is

21、 not fast symmetric encryption and decryption. symmetric encryption system is only one key, and non-public, if you want to have to let each other know the decryption key. therefore, to ensure their safety is to ensure security of the keys rather than symmetric key system, there are two keys, one of

22、which is open, so that you can transfer without the other party as symmetric encryption key as a. this security on large lot. this research project mainly in the non-symmetric encryption algorithm encryption algorithm code rsa. on cryptography is briefly introduced, highlighting the basics of public

23、 key cryptography: as binary operations, integer division, modular arithmetic, euler function, fermats little theorem, euclidean algorithm, probabilistic algorithms, recommendation primality test; the fundamental theorem of arithmetic, chinese remainder theorem, divide and conquer the basic idea. an

24、d analyze the rsa encryption and decryption process and the algorithm; for a brief analysis of rsa attack, such as factoring attack, chosen ciphertext attack on the encryption exponent attack, the attack on the decryption exponent, plaintext attack, on the mode of attack, an attack ; rsa encryption

25、algorithm analyzes the advantages and disadvantages. rsa algorithm is based on theoretical foundation design procedures and software platform to achieve in vc6.0 rsa algorithm encryption and decryption. rsa algorithm is the first not only for data encryption can be used for digital signature algorit

26、hm, the algorithms name to the inventors name. algorithm using the public key and private key are two large prime numbers (greater than 100 decimal places) of the function. it is assumed that key and ciphertext from a plaintext of the difficulty to infer equivalent decomposition of the product of tw

27、o large prime numbers. first select two large prime numbers p and q (), and. calculation: n = p * q and then randomly selected encryption key e, e and requirements (p-1) * (q-1) are coprime. finally, euclid algorithm decryption key d, to satisfy e * d = 1 (mod (p-1) * (q-1) where n and d have coprim

28、e. e and n is the number of public key, d is the private key. two primes p and q are no longer needed, it should be discarded, do not let anyone know. encrypted message m, first of all the m divided into equal length blocks of data m1, m2, . . mi, block size s, where 2 s = n, s as large as possible.

29、 corresponding ciphertext is: - (a); decryption calculated as follows: - (b). this is the rsa encryption and decryption process. rsa can be used for digital signatures, using (a) type signature, (b) authentication. specific operation, take into account the large amount of information security and m

30、factors, generally the first operations for hash. rsas security depends on the integer factorization, but is equivalent to factoring has not been proved theoretically. currently, rsa algorithm for some variants have been proven equivalent to factoring. in any case, decomposition of n is the most obv

31、ious attack method. now, more than 140 people have been able to decompose a large prime number decimal places. therefore, the modulus n must be selected larger, because of the specific application conditions. as a result of large numbers are calculated, making the fastest rsa situation 100 times slo

32、wer than des, either software or hardware. rsa has been the defect rate. generally used only for a small amount of data encryption. keywords: rsa; rsa algorithm; encryption; decryption; non-symmetric key; cryptography; public key; private key. 前前 言言 信息社会中，每天都有大量的信息在传输、交换、存储和处理，而这些处理过程 几乎都要以来强大的计算机系统

33、来完成，一旦计算机系统发生安全问题，就可能造成 信息的丢失、篡改、伪造、假冒，以及系统遭受坏等严重后果，因此，如何保证计算 机系统的安全，是当前一个需要立即解决的十分严峻的问题。 通常保障信息安全的方法有两大类：一是以防火墙技术为代表的被动防卫型，二 是建立在数据加密，用户授权确认机制上的开放型网络安全保障技术。第二种就要采 用密码学的知识来解决。 密码学是一门既古老又年轻的科学，它最早的应用可以追溯到几千年前的古罗马， 但成为一门独立的学科则是从近几十年才开始的。1949 年 shannon 发表的保密系统的 信息理论和 1976 年 diffie 和 hellman 的密码学的新方向首次提

34、出的公钥密码思想 奠定了现在密码学的理论基础。1977 年美国加密数据加密标准 des 的正式发布和 1977 年 r.l.rivest，shamir，l.adleman 三人共同提出的第一个公钥密码思想的密码体制- rsa 公钥密码成为现在密码学研究迅速发展的两个里程碑。 根据加密密钥和解密密钥是否相同或者本质上等同，即从其中一个容易推出另一 个，可将现有的加密体制分为两种。一种是单钥加密体制，其典型代表是美国的数据 加密标准 des（dataencryptionstandard）；另一种是公钥密码体制，其典型代表是 rsa 密码体制。我这次的论文主要就是研究 rsa 的算法和算法的程序实现

35、。 自 19 世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截 收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战 线。1917 年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942 年， 美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能 以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦三岛和其他 许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，这些事例也从反 面说明了密码保密的重要地位和意义。 1 1 密码学的概述密码学的概述 1.11.1 密码学的基本术语密码学的基本术语 1.1.

36、1 密码学密码学 密码学（cryptography） ，它是一门研究秘密书写的科学，是以认识密码变换的本 质、研究密码保密与破译的基本规律为对象的学科。密码的另一种定义是一门与信息 安全密切相关的数学科学，是信息安全的核心。密码提供的最基础的服务是使合法通 信者进行信息的交换，而其他人员难以获得通信内容。 密码学一般包括两个对立统一的分支学科：密码编码学和密码分析学。研究密码 变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码 以获取通信情报的，称为破译学，总称密码学。密码编码学与密码分析学相辅相成， 共处于密码学的统一体中。 现代密码学除了包括密码编码学和密码分析学两

37、个主要的学科外，还包括一个新 产生的分支密码密钥学。它是以密码体系最核心部分的密钥作为研究对象的学科。 密钥管理是一种规程，它包括密钥的产生、分配、存储、保护、销毁等环节，因而在 密码管理体系中密钥管理至关重要。上述三个分支学科构成了现代密码学的主要科学 体系。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、 图像、数据等都可实施加、解密变换。 1.1.2 密钥密钥 明文到密文的转换往往由一些特殊的函数完成，控制这些函数的参数称为密钥， 用 k 表示。所谓密钥，是指由用户事先选定的较短的字符或数字序列，其作用近似于 打开保险箱的钥匙。所有密钥的集合构成密钥空间，用 sk

38、表示。密钥空间中不相同密 钥的个数称为密钥体制的密钥量，它是衡量密码体制安全性的一个重要指标。 密钥是一个数值，它和加密算法一起生成特别的密文。密钥本质上是非常非常大 的数。密钥的长度尺寸用比特来衡量。在公开密钥加密方法中，密钥的长度越大，密 文就越安全。在同种加密算法中，密钥越大越安全。但是传统方法和公开密钥方法所 用的加密算法不一样，因此它们的密钥尺寸不能直接比较。 公钥和私钥是算术相关的，仅凭公钥推算出私钥是困难的。然而如果有足够的时 间和计算能力，总是可能导出私钥的。这使得选择合适尺寸的密钥变得非常重要。为 了安全需要足够大的密钥，而为了速度则要用小的密钥 1.1.3 加密与解密加密与

39、解密 加密是在密钥 k 的作用下，把明文 p 从明文信息空间 sp 对应到密文信息空间 sc 的一种变换，明文和密文的关系可表示为 cek（p）。 密文传送到接收者，合法用户利用密钥对密文 c 进行与加密变换相反的逆变换， 称为解密变换，用 dk 表示。解密变换是把密文 c 从密文信息空间 sc 对应到明文信息 空间 sp 的变换。 逆变换的过程称为解密或译密。解密变换的目的是恢复出明文 p：p=dk（c） dkek（p）。 上式中的 ek 和 dk 为可逆变换对。k 不同，ek 和 dk 也不同。可见，信息的保密性 完全依赖于密钥 k 的保密性。 1.1.4 密码体制密码体制 一个完整的密码

40、体制（cryptosystem）由 5 部分组成：明文信息空间 sp、密文信 息空间 sc、密钥空间 sk、加密变换族 ek、解密变换族 dk。 密码体制应满足以下 3 个一般性要求：加解密变换对所有密钥都一致有效；体制 必须是简单易行的，应易于找到密钥用于逆变换；体制的安全性仅依赖于密钥的保密 性而不能依赖于加、解密算法的强度。 一个好的密码体制则应至少满足以下两个条件： 在已知明文 p 和密钥 k 时，计算 cek（p）容易；在已知密文 c 和密钥 k 时， 计算 pdk（c）容易。 在不知密钥 k 时，不可能由密文 c 推知明文 p。 对于一个密码体制，如果能够根据密文确定明文或密钥，或

41、者能够根据明文及其 生成的密文确定密钥，这个密码体制就是可以破译的，反之则为不可破译的。 1.1.5 鉴别、完整性和抗抵赖鉴别、完整性和抗抵赖 鉴别是解决身份冒充问题。消息的接受者应该能够确认消息的来源，发送者不可 能伪装成他人。同样，发送者也要能够确认接受者是否是自称的，接受者不可能伪装 成他人。 完整性事解决篡改问题，消息的接受者应该能够验证在传送过程中消息没有被修 改。 抗抵赖性是指发送者或接受者事后不可能虚假地否认他发送或接收的消息。 这些功能使通过计算机进行的信息交流，就像面对面交流一样安全可靠。某人是 否就是他说的人，某人的身份证明文件是否有效，声称从某人那里来的文件是否确实 是从

42、那个人那里来的，这些事情通过鉴别、完整性检验和抗抵赖来实现。 1.2 密码学的应用密码学的应用 在很长的时间内，密码仅限于军事、政治和外交的用途，其知识和经验也仅掌握 在与军事、政治和外交有关的密码机关手中，再加上通信手段比较落后，故不论密码 理论还是密码技术发展都很缓慢。 随着科学技术的进步，信息交换的手段越来越先进，信息交换的速度越来越快， 信息交换的内容越来越广泛，信息交换的形式越来越多样化，信息交换的规模也越来 越大。到了 20 世纪 70 年代，随着信息的激增，对信息保密的需求也从军事、政治和 外交等领域，逐步扩展到民用和商用领域，从而导致了密码学知识的广泛传播。计算 机技术和微电子

43、技术的发展，为密码学理论的研究和实现提供了强有力的手段和工具。 进入 20 世纪 80 年代以后，随着网络的兴起，对密码理论和技术的研究更是呈爆炸性 增长的趋势，密码学在雷达、导航、遥控、遥测等领域占有重要地位。除此之外，密 码学正渗透到通信、电力、金融、医疗、卫生、交通等各行业的管理信息系统，甚至 到个人和家庭等领域，而且保密的作用也已不再仅仅是保密，还有认证、完整性检验 和抗抵赖等新的功能。对普通的家庭来说，生活中许多地方需要保密，如各种银行密 码、信用卡密码、网络账号和密码等。 1.3 密码算法的概念及其分类密码算法的概念及其分类 密码算法也叫密码，是用于加密和解密的数学函数。通常情况下

44、，有两个相关的 函数，一个用作加密，另一个用作解密。 如果算法的保密性是依赖于保持密钥的秘密，这种算法称为非受限制的算法，也 称基于密钥的算法。在非受限密码算法中，根据密钥的特点，加密算法分为两类：秘 密密钥算法和公开密钥算法。现在的密码学算法一般基本上都是，非限制算法！ 1.3.1 对称密码算法对称密码算法 秘密密钥算法通常称之为对称密码算法或传统密码算法，也称单密钥算法。对称 密码算法要求发送者和接收者在安全通信之前，商定一个密钥。其算法的安全性依赖 于密钥，密钥一旦泄露，整个安全系统都要崩溃。换句话说，在使用对称密码加密算 法时，只要通信需要保密，密钥就必须保密。 对称算法可分为两类。一

45、类只对明文中的单个比特（有时对字节）运算的算法称 为序列算法或序列密码。另一类算法是对明文的一组比特运行运算，这些比特组称为 分组，相应的算法称为分组算法或分组密码。 1.3.2 公开密钥算法公开密钥算法 公开密钥算法也叫非对称密码算法或双密钥算法。公开密钥加密法可以解决密钥 发布的问题，公开密钥的概念由 whitfield diffie 和 martin hellman 在 1975 年提出。 现在也有证据表明英国情报机关先于 diffie 和 hellman 几年发明了这种方法，但是却 作为军事秘密不为人知，并且没有什么有价值的成果。 公开密钥算法不要求通信双方共享一个密钥，其用作加密的密

46、钥不同于用作解密 的密钥，而且解密密钥不能根据解密密钥计算出来。用于加密的密钥可向所有使用者 公开，使用加密密钥加密后的信息只有用相对应的解密密钥才可解密。 公钥加密法的主要优势在于可以让事先没有安全通道的人安全地交换信息。收发 双方通过安全通道共享密钥的前提条件不存在了，所有的通信中只包含了公钥，私钥 是不会传输或共享的。公钥加密法是加密技术的革命，它可以为普通人提供较强的加 密手段，因而可以说公钥加密法是密码学发展史上的一个里程碑。 1.3.3 hash 算法算法 hash 算法也称为消息摘要或单向函数，是密码学中的一种重要的算法。它是许多 安全认证协议的重要组成部分，是实现有效、安全可靠

47、的数字签名和认证的重要工具。 hash 算法是一种将任意长度的输入消息计算产生出一个固定长度的输出的数学变 换，即消息 m 的 hash 为 h（m）。这类算法具有以下特点： 对于任何消息，计算 h（m）相对来说较为容易，这意味着要使用该函数，并不 需要占用太多的计算时间。 给定 h（m），寻找一个消息使得其 hash 值为 h（m）的难度与穷举所有可能的 m 并计算 h（m）的难度相比，不会有明显的差别。 虽然理论上存在很多不同数值，其 hash 值都是 h（m），但是要找到两个 hash 结果相同的数值，从计算的角度来说是很困难的。 要从密码学的角度认为一个 hash 函数是安全的，其必备

48、条件如下：找到一个消息， 使其消息摘要为一预先给定的消息摘要值，在计算上是不可行的；以现有的计算能力， 不可能找到两个具有相同消息摘要的消息；给定一个消息，不可能找到另一个消息与 其具有相同的消息摘要。 1.4 密码编码学的基本概念密码编码学的基本概念 密码编码学的主要目的是确保明文、密钥等秘密信息不被窃听者及攻击者窃听或 破译。密码编码学希望能够解决在下述环境下即信息的存储（可能为非授权者接触）、 信息的交换（可能被冒用或抵赖）以及信息的传输（可能被截获）过程中，信息的安 全保护问题。 密码编码系统应具有以下独立的特征： （1）转换明文为密文的运算类型 有的算法的保密性可能依赖于保护算法本身

49、，称为受限制的密码算法；也有的算 法仅依赖于使用算法时所采用的密钥，称为基于密钥的密码算法。 （2）所用的密钥类型 如果发送方和接收方使用相同的密钥，这种密码称为对称密码、单密钥密码或传 统密码。如果发、收双方使用不同的密钥，这种密码就称为非对称密码、双钥密码或 公钥密码。 （3）处理明文的方法 分组密码每次处理一个输入分组，相应地输出一个输出分组。而序列（流）密码 是连续地处理输入元素，每次输出一个元素。 1.5 密码分析学的基本概念密码分析学的基本概念 密码分析学，是一门研究在不知道通常解密所需要的秘密信息的情况下对加密 的信息进行解密的学问。通常，这需要寻找一个秘密的钥匙。 密码分析的目

50、标在密码学的历史上从古至今都一样，实际使用的方法和技巧 却随着密码学变得越来越复杂而日新月异。密码学算法和协议从古代只利用纸笔等 工具，发展到第二次世界大战时的恩尼格玛密码机，直到目前的基于电子计算机的 方案。而密码分析也随之改变了。无限制地成功 破解密码已经不再可能。 在上个 世纪 70 年代中期，公钥密码学作为一个新兴的密码学分支发展起来了。而用来破 解这些公钥系统的方法则和以 往完全不同，通常需要解决精心构造出来的纯数学问 题。其中最著名的就是大数的质因数分解。 1.6 密码学的信息论基础密码学的信息论基础 1949 年，shannon 以其在信息论方面的基本著作为依据，为密码学提供了理

51、论基 础。依据已经收到的密文来得到的明文的不确定性，来度量密码在理论上的保密度。 如果不论截取了多少密文，对明文仍然一无所知，则此密码达到完全保密。 所有现用密码都会在密文中留下一些有关明文的信息（唯一例外是一次一密）。 随着密文长度的增加，明文的不确定性通常会下降，最后到零，此时意味着，有足够 的信息来唯一地确定明文，这样，此密码至少在理论上是可破译的。 只要有数百比特长的明文，大多数密码在理论上是可破译的。但这并不意味着这 些密码不安全，因为要确定明文在计算上的耗费，可能会超过可利用的资源。因此， 重要的问题不在于密码是否绝对安全，而是计算上是否安全。 1.7 密码学的起源和发展密码学的起

52、源和发展 密码学在公元前 400 多年就早已产生了，密码学的起源的确要追溯到人类刚刚出 现，并且尝试去学习如何通信的时候。为了确保通信的机密，最先是有意识地使用一 些简单的方法来加密信息，通过一些（密码）象形文字相互传达信息。接着由于表音 和表意文字的出现和使用，确保通信的机密性就成为一种艺术，古代发明了不少加密 信息和传达信息的方法。 密码学真正成为科学是在 19 世纪末和 20 世纪初期，特别是两次世界大战中对军 事信息保密传递和破获敌方信息的需求，密码学得到了空前的发展，并广泛用于军事 情报部门的决策。 20 世纪初，随着技术的进步，产生了最初的可以实用的机械式和电动式密码机， 同时出现

53、了商业密码机公司和市场。这一阶段又称为机械密码时代。 在计算机出现以前，密码算法主要是通过字符之间代替或易位实现的，我们统称 这些密码体制为古典密码。这些密码算法的使用和分析破译，为今天电子时代尤其是 网络时代的密码算法提供了坚实有力的理论基础。20 世纪 60 年代后，电子技术的发展， 使得基于复杂计算的密码成为可能。这一阶段电子密码机得到较快的发展和广泛的应 用，使密码学的发展进入了一个新的阶段。同时充分利用了古典密码留下来的经验， 对于算法的设计有了更科学的思路。 密码破译是随着密码的使用而逐步产生和发展的。1412 年，波斯人卡勒卡尚迪所 编的百科全书中载有破译简单代替密码的方法。到

54、16 世纪末期，欧洲一些国家设有专 职的破译人员，以破译截获的密信。密码破译技术有了一定的发展。1949 年美国人香 农发表了秘密体制的通信理论一文，应用信息论的原理分析了密码学中的一些基 本问题。 1.8 密码算法的安全性密码算法的安全性 密码系统的安全性是至关重要的问题，主要由保密性和可靠性来衡量。 对算法的保密性的要求主要有： 在已知与密文相对应的明文的情况下，密码分析者要从截取的密文中系统地确 定解密变换，在计算上是不可行的。 密码分析者要从截获的密文中确定明文，在计算上是不可行的。 对算法的可靠性要求有： 在已知与密文相对应的明文的情况下，密码分析者要有规律地确定加密变换， 在计算上

55、是不可行的。 密码分析者若想有规律地求出密文 c，使得 dk（c）是 m 集合中的有效明文，在 计算上是不可行的。 根据被破译的难易程度，不同的密码算法也具有不同的安全等级。有多种衡量安 全性的方法。按照价值大小来衡量，如果破译算法的代价大于加密数据的价值，那么 算法可能是安全的；按照数据有效时间来衡量，如果破译算法所需的时间比加密数据 保密的时间更长，那么算法可能是安全的；按照实际破译所需数据量来衡量，如果用 单密钥加密的数据量比破译算法需要的数据量少得多，那么算法可能是安全的。 如果不论密码分析者有多少密文，都没有足够的信息恢复出明文，那么这个算法 就是无条件保密的。事实上，只有一次一密乱

56、码本，才是不可破译的（给出无限多的 资源仍然不可破）。所有其他的密码系统在唯密文攻击中都是可破译的，只要简单地 一个接一个地去试每种可能的密钥，并且检查所得明文是否有意义，这种方法叫做强 力攻击或穷举攻击。密码学更关心在计算上不可破译的密码系统。如果一个算法用 （现在或将来）可得到的资源都不能破译，这个算法被认为在计算上是安全的。 2 2 公钥密码体制基础公钥密码体制基础 2.12.1 整数算法整数算法 2.1.1 二进制运算二进制运算 在密码学中，我们感兴趣的主要是三种应用于整数集的二进制运算。二进制运算 用两个输入创建一个输出。三种普通的二进制运算分别是：加法、减法和乘法。每种 运算都是利

57、用两个输入(a 和 b)并创建一个输出(c)。两个输入来自整数集，输出也进 入整数集。在该范畴内除法是不适用的，因为正像我们了解到的那样，除法产生两个 输出而不是一个。 2.1.2 整数除法整数除法 在整数计算中，如果我们用 n 除 a，就会得到 q 和 r。这 4 个整数之间的关系表示 如下：。在这种关系中，a 是被除数，q 是商，n 是除数，r 是余数。这不aqnr 是运算，因为 a 除以 n 的结果是两个整数 q 和 r，我们只能称其为除法关系。在密码学 中，当我们运用以上的除法关系时，要有两种限制。首先，要求除数是正数；其次， 要求余数是非负数。 我们使用计算机或计算器的时候，如果 a

58、 是负数，r 和 q 就是负数。那我们如何去 满足 r 必须是正数这个限制要求呢？解决的方法很简单，q 的值减 1 然后再把 n 的值和 r 相加，就可以使其变为正值。如：。用 23 去减 1 就得出24，把 11 和2 相加得 9。上述关系依然是正确的。 2.1.3 整除性整除性 我们简单讨论一下整除性，这是一个在密码学中经常要遇到的问题。如果 a 不等 于零，在除法关系中假设 r=0，我们得出这时我们就可以说 n 可以整除 a。我aqn 们也可以说 a 可以被 n 整除。如果我们不考虑 q 的值，就可以把上面的关系表示为 n|a。如果余数不为零，即 n 不能整除 a，这时我们可以把这种关系

59、表达为 n a。 性质 以下是整除性的几种性质。 性质 1：如果 a1，那么 a=1。 性质 2：如果 ab 且 ba，那么 a=b。 性质 3：如果 ab 且 bc，那么 ac。 性质 4：如果 ab 且 ac，那么 a(mbnc，这里 m 和 n 是任意整数。 euclidean 算法 当两个整数都是正数时，要靠列举出所有公约数来求最大公约数(gcd)就没有实际 意义了。所幸 2000 多年以前数学家 euclid 发现的一种算法，可以用来求出两个正整 数的最大公约数。 euclidean 算法基于以下事实。 事实 1：gcd(a，0)=a。 事实 2：gcd(a，b)=gcd(b，r)，

60、这里 r 是 a 除以 b 所得的余数。 第一个事实告诉我们，对两个整数，如果第二个整数是 0，那么第一个数就是这两 个数的最大公约数。第二个事实告诉我们如何去改变 a 和 b 的值，直到使 b 为 0 的方 法，当 b 变为 0 时，我们就能够直接看出最大公约数了。例如，为了计算 gcd(36，10)， 我们可以多次使用第二个事实，一直到 b 变为 0，然后再使用第一个事实的结论，这样 我们就得到 gcd(36，10)了。换句话说，gcd(36，10)=2，gcd(10，6)=2 等。 我们用两个变量 r1 和 r2 来表示减小过程中的变化值。它们的初始值是 a 和 b。在 每一步中我们都要