PKCS #1 v2.1 RSA 算法标准
常见公钥加密算法有哪些
常见公钥加密算法有哪些 什么是公钥加密公钥加密，也叫非对称（密钥）加密（public key encrypTIon），属于通信科技下的网络安全二级学科，指的是由对应的一对唯一性密钥（即公开密钥和私有密钥）组成的加密方法。它解决了密钥的发布和管理问题，是目前商业密码的核心。在公钥加密体制中，没有公开的是私钥，公开的是公钥。 常见算法RSA、ElGamal、背包算法、Rabin（Rabin的加密法可以说是RSA方法的特例）、Diffie-Hellman （D-H）密钥交换协议中的公钥加密算法、EllipTIc Curve Cryptography （ECC，椭圆曲线加密算法）。使用最广泛的是RSA算法（由发明者Rivest、Shmir和Adleman 姓氏首字母缩写而来）是著名的公开金钥加密算法，ElGamal是另一种常用的非对称加密算法。 非对称是指一对加密密钥与解密密钥，这两个密钥是数学相关，用某用户密钥加密后所得的信息，只能用该用户的解密密钥才能解密。如果知道了其中一个，并不能计算出另外一个。因此如果公开了一对密钥中的一个，并不会危害到另外一个的秘密性质。称公开的密钥为公钥；不公开的密钥为私钥。 如果加密密钥是公开的，这用于客户给私钥所有者上传加密的数据，这被称作为公开密钥加密（狭义）。例如，网络银行的客户发给银行网站的账户操作的加密数据。 如果解密密钥是公开的，用私钥加密的信息，可以用公钥对其解密，用于客户验证持有私钥一方发布的数据或文件是完整准确的，接收者由此可知这条信息确实来自于拥有私钥的某人，这被称作数字签名，公钥的形式就是数字证书。例如，从网上下载的安装程序，一般都带有程序制作者的数字签名，可以证明该程序的确是该作者（公司）发布的而不是第三方伪造的且未被篡改过（身份认证/验证）。 对称密钥密码体制 所谓对称密钥密码体制，即加密密钥与解密密钥是相同的密码体制。 数据加密标准DES属于对称密钥密码体制。它是由IBM公司研制出，于1977年被美国
公钥加密算法
公钥加密算法 一．简介 公钥加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。 图1 非对称加密的简化模型 非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。另一方面，甲方可以使用乙方的公钥对机密信息进行签名后再发送给乙方；乙方再用自己的私匙对数据进行验签。 甲方只能用其专用密钥解密由其公用密钥加密后的任何信息。非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要。 非对称密码体制的特点：密钥管理简单，算法强度复杂、安全性依赖于算法与密钥；但是由于其算法复杂，而使得加密解密速度没有对称加密解密的速度快。 二．起源 W.Diffie和M.Hellman 1976年在IEEE Trans.on Information刊物上发表了“ New Direction in Cryptography”文章，提出了“非对称密码体制即公开密钥密码体制”的概念，开创了密码学研究的新方向。 三．基本原理 1.A要向B发送信息，A和B都要产生一对用于加密和解密的公钥和私钥。 2.A的私钥保密，A的公钥告诉B；B的私钥保密，B的公钥告诉A。 3.A要给B发送信息时，A用B的公钥加密信息，因为A知道B的公钥。
RSA公钥加密算法及其安全性讨论
RSA公钥加密算法及其安全性讨论 RSA algorithm for public-key encryption and its security 摘要：RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。但是，RSA的安全性依赖于大数的因子分解，却并没有从理论上证明破译RSA的难度与大数分解难度等价，即RSA的重大缺陷是无法从理论上把握它的保密性能到底如何。随着计算能力的不断进步和各种攻击方法的出现，RSA算法是否真的安全。 关键词：RSA，公钥，加密，大数分解，攻击，安全性 1 RSA加密算法 1.1公钥简介 密码体制按密钥类型分为对称密钥和不对称密钥。对称密钥即加密、解密用的是同一个密钥，又称为私钥。不对称密钥即公钥加密，加密、解密用的是不同的密钥，一个密钥“公开”，即公钥，另一个自己秘密持有，即私钥，加密方用公钥加密，只有用私钥才能解密——史称公钥加密体系：PKI。 1.2 RSA算法简介 RSA加密算法是一种非对称加密算法。RSA加密算法是Ron Rivest、Adi Shamirh和Len Adleman于1977年在美国麻省理工学院开发出来的，次年首次对外公开宣布，是第一个既能用于数据加密也能用于数字签名的算法。RSA就是他们三人姓氏开头字母拼在一起组成的。RSA是建立在“大整数的素因子分解是困难问题”基础上的，其安全性取决于大数分解，也就是大数分解质因数的困难性。换言之，对一极大整数做因式分解愈困难，RSA演算法愈可靠。假如有人找到一种快速因式分解的演算法的话，那么用RSA加密的信息的可靠性肯定会急剧下降，但找到这样的演算法的可能性是非常小的，今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。 1.3 RSA算法 1.3.1公钥和私钥的产生 假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥： （1）选两个保密的足够大的素数p和q。同时对p, q严加保密，不让任何人知道。 （2）计算N=p×q。 （3）计算f(n)=(p-1)(q-1)。 （4）找一个与f(n)互质的数e，且1 公钥密码算法 学号：0900250114 姓名：李荣亮 摘要：古往今来，通信中的安全保密问题一直受到广泛关注。历史上，交战双方在通信安全、保密和密码破译方面的优势均被认为是取得战争胜利的关键因素之一。今天，随着互联网的发展，人类进入信息化时代，现代通信涉及各个行业，信息安全已成为人人都关心的问题，敏感信息的安全传输越来越受到人们的关注，这就促使密码学揭去了神秘的面纱，为更广泛的领域和大众服务。 一、公钥密码学概述。 公开密钥密码算法的提出是整个密码学历史上最大的而且也许是最唯一真 正的变革。从最初一直到现代，几乎所有密码系统都建立在基本的替代和置换工具的基础上。在用了数千年的本质上可以手算完成的算法之后，常规的密码学随着转轮加密/解密机的发展才出现了一个重大进步。机电式变码旋转软件使得极其复杂的密码系统被研制出来。有了计算机后，更加复杂的系统被设计出来。但是不管是转轮机还是后来的DES（数据加密标准），虽然代表了重要的进展，却仍然依赖于替代和置换这样的基本工具。 公钥密码学则与以前的所有方法都截然不同。一方面公开密钥算法基于数学函数而不是替代和置换，更重要的是，公开密钥密码学是非对称的，它用到两个不同的密钥，而对称的常规加密则只使用一个密钥。使用两个密钥对于保密通信，密钥分配和鉴别等领域都有着深远的影响。 公钥密码算法中的密钥依性质划分，可分为公钥和私钥两种。 用户或系统产生一对密钥，将其中的一个公开，称为公钥；另一个自己保留，称为私钥。 任何获悉用户公钥的人都可用用户的公钥对信息进行加密与用户实现安全信息交互。 由于公钥与私钥之间存在的依存关系，只有用户本身才能解密该信息，任何未受授权用户甚至信息的发送者都无法将此信息解密。 在近代公钥密码系统的研究中, 其安全性都是基于难解的可计算问题的。 如: (1)大数分解问题； (2)计算有限域的离散对数问题； 实验报告 实验八、RSA公钥密码 实验目的： 熟练掌握RSA公钥密码算法原理及实现。 实验内容： 1、写出RSA公钥密码算法及其实现。 2、当取两素数分别为17、23，加密密钥为35时，写出其明文空间，并求出下列明文的密 文：1、15、17、23、48、235。 3、当取两素数分别为17、23，加密密钥为35时，求相应的解密密钥。 实验结果： 1.算法： Step1：选取两个大素数p和q，p和q保密 Step2：计算n=pq，f（n）=（p-1）（q-1），n公开，f（n）保密 Step3：随机选取正整数1 n=p*q; t=(p-1)*(q-1); cout<<"请输入加密密钥e:"; cin>>e; cout<<"输入明文M:"; cin>>M; C=1; for(i=0;i 实验五公钥加密算法—RSA 一、实验目的 通过使用RSA算法对实验数据进行加密和解密，掌握公钥加密算法的基本原理，熟练掌握RSA算法各功能模块的工作原理和具体运算过程。 二、实验原理 RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。 1. RSA的密钥生成 RSA的算法涉及三个参数，n、e、d。 其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。鉴于现代对于大整数分解的水平不断增强，一般P、Q的取值都要求在1024位以上。 e和d是一对相关的值，e可以任意取，但要求e与(p-1)*(q-1)互质；再选择d，要求： (e*d)mod((p-1)*(q-1))=1。 RSA加密算法的基本原理 1978年RSA加密算法是最常用的非对称加密算法，CFCA 在证书服务中离不了它。但是有不少新来的同事对它不太了解，恰好看到一本书中作者用实例对它进行了简化而生动的描述，使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读，希望能够对时间紧张但是又想了解它的同事有所帮助。 RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。RSA以它的三个发明者Ron Rivest,Adi Shamir,Leonard Adleman的名字首字母命名，这个算法经受住了多年深入的密码分析，虽然密码分析者既不能证明也不能否定RSA的安全性，但这恰恰说明该算法有一定的可信性，目前它已经成为最流行的公开密钥算法。 RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积（这是公认的数学难题）。 RSA的公钥、私钥的组成，以及加密、解密的公式可见于下表： 可能各位同事好久没有接触数学了，看了这些公式不免一头雾水。别急，在没有正式讲解RSA加密算法以前，让我们先复习一下数学上的几个基本概念，它们在后面的介绍中要用到： 一、什么是“素数”？ 素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”（或“互素数”）？ 小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种（不限于此）： （1）两个质数一定是互质数。例如，2与7、13与19。 （2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与26。（3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。（4）相邻的两个自然数是互质数。如15与16。 （5）相邻的两个奇数是互质数。如49与51。 （6）大数是质数的两个数是互质数。如97与88。 （7）小数是质数，大数不是小数的倍数的两个数是互质数。如7和16。 （8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数， 1、常见的几种加密算法： DES（Data Encryption Standard）：数据加密标准，速度较快，适用于加密大量数据的场合； 3DES（Triple DES）：是基于DES，对一块数据用三个不同的密钥进行三次加密，强度更高； RC2和RC4：用变长密钥对大量数据进行加密，比DES 快；IDEA（International Data Encryption Algorithm）国际数据加密算法，使用128 位密钥提供非常强的安全性； RSA：由RSA 公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件块的长度也是可变的； DSA（Digital Signature Algorithm）：数字签名算法，是一种标准的DSS（数字签名标准）； AES（Advanced Encryption Standard）：高级加密标准，是下一代的加密算法标准，速度快，安全级别高，目前AES 标准的一个实现是Rijndael 算法； BLOWFISH，它使用变长的密钥，长度可达448位，运行速度很快； 其它算法，如ElGamal钥、Deffie-Hellman、新型椭圆曲线算法ECC等。 2、公钥和私钥： 私钥加密又称为对称加密，因为同一密钥既用于加密又用于解密。私钥加密算法非常快（与公钥算法相比），特别适用于对较大的数据流执行加密转换。 公钥加密使用一个必须对未经授权的用户保密的私钥和一个可以对任何人公开的公钥。用公钥加密的数据只能用私钥解密，而用私钥签名的数据只能用公钥验证。公钥可以被任何人使用；该密钥用于加密要发送到私钥持有者的数据。两个密钥对于通信会话都是唯一的。公钥加密算法也称为不对称算法，原因是需要用一个密钥加密数据而需要用另一个密钥来解密数据。 可能各位同事好久没有接触数学了，看了这些公式不免一头雾水。别急，在没有正式讲解RSA加密算法以前，让我们先复习一下数学上的几个基本概念，它们在后面的介绍中要用到： 一、什么是“素数”？ 素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”（或“互素数”）？ 小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种（不限于此）： （1）两个质数一定是互质数。例如，2与7、13与19。 （2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与26。（3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。（4）相邻的两个自然数是互质数。如15与16。 （5）相邻的两个奇数是互质数。如49与51。 （6）大数是质数的两个数是互质数。如97与88。 （7）小数是质数，大数不是小数的倍数的两个数是互质数。如7和16。 （8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，这两个数为互质数。等等。 三、什么是模指数运算？ 指数运算谁都懂，不必说了，先说说模运算。模运算是整数运算，有一个整数m，以n 为模做模运算，即m mod n。怎样做呢？让m去被n整除，只取所得的余数作为结果，就 公钥密码技术讲义 1.问题的引入 1.1攻击类型 根据攻击的不同方式，攻击被分为被动攻击和主动攻击。 图表1消息的正常传送 被动攻击 获得正在传送的信息。其特点是：偷听或监视传送。攻击的手段是：泄露消息内容和通信量分析。（绘图说明） 主动攻击 主动攻击主要涉及到数据流的修改或创建错误流。攻击手段是：伪装、重放、修改消息和拒绝服务。 1.2安全服务 (简要说明) A.XX性 B.验证（鉴别） C.完整性 D.不可抵赖性（不可否认性） E.访问控制 F.可用性 1.3常规加密的缺陷 尽管对称密码技术有一些很好的特性，但它也存在着明显的缺陷，主要在于其密钥的管理： A.进行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情况下是可行的， 但在某些情况下会非常困难，甚至无法实现。 B.密钥规模复杂。举例来说，A与B两人之间的密钥必须不同于A和C两人之间的密钥， 否则给B的消息的安全性就会受到威胁。在有1000个用户的团体中，A需要保持至少999个密钥（更确切的说是1000个，如果她需要留一个密钥给他自己加密数据）。对于该团体中的其它用户，此种情况同样存在。这样，这个团体一共需要将近50万个不同的密钥！推而广之，n个用户的团体需要n2/2个不同的密钥。 2.公钥密码技术 2.1基本概念 应用两个不同的密钥：一个是公开的，一个是秘密的。从公开密钥(以下简称为公钥)很难推断出私人密钥(以下简称为私钥)。持有公钥的任何人都可以加密消息，但却无法解密。只有持有私钥的人才能够解密。 2.2加密/解密基本步骤 图表2加密/解密基本步骤 一般的情况下，网络中的用户约定一个共同的公开密钥密码系统，每个用户都有自己的公钥和私钥，并且所有的公钥都保存在某个公开的数据库中，任何用户都可以访问此数据库。这样加密协议如下： A.Alice从公开数据库中取出Bob的公开密钥。 B.Alice用Bob的公开密钥加密她的消息，然后传送给Bob。 C.Bob用他的私钥解密Alice的消息。 RSA1978年，MIT的Rivest、Shamir、Adleman提出RSA算法 非对称加密（公开密钥加密）密码学的一次革命，定义：KA≠KB ，KA、E和D公开 特点： 基于数论原理(大数分解难题) 是目前应用最广泛的公钥加密算法 属于块加密算法 在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 RSA算法原理 l 定义：RSA加密算法 确定密钥： 1. 找到两个大质数，p,q 2. Let n=pq 3. let m=(p-1)(q-1);Choose e and d such that de=1(%m). 4. Publish n and e as public key. Keep d and n as secret key. 加密： C=M^e(%n) 解密： M=(C^d)%n 其中C=M^e(%n) 为C%n=(M^e)%n 存在的主要问题是大数计算和大数存储的问题。 什么是RSA RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。 RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。 RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n 至少也要600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。 这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。 RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。 RSA的算法涉及三个参数，n、e1、e2。 其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。 e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。 (n及e1),(n及e2)就是密钥对。 RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n； e1和e2可以互换使用，即： A=B^e2 mod n；B=A^e1 mod n； 一、RSA 的安全性 RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA 的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。 二、RSA的速度 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。 三、RSA的选择密文攻击 RSA在选择密文攻击面前很脆弱。一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： 公钥密码系统及RSA公钥算法 摘要： 本文简单介绍了公开密钥密码系统的思想和特点，并具体介绍了RSA算法的理论基础，工作原理和具体实现过程，并通过一个简单例子说明了该算法是如何实现。在本文的最后，概括说明了RSA算法目前存在的一些缺点和解决方法。 关键词：公钥密码体制，公钥，私钥， RSA 中图分类号：TP309.7 §1引言 随着计算机联网的逐步实现，Internet前景越来越美好，全球经济发展正在进入信息经济时代，知识经济初见端倪。计算机信息的保密问题显得越来越重要，无论是个人信息通信还是电子商务发展，都迫切需要保证Internet网上信息传输的安全，需要保证信息安全。信息安全技术是一门综合学科，它涉及信息论、计算机科学和密码学等多方面知识，它的主要任务是研究计算机系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和完整。其中，信息安全的核心是密码技术。密码技术是集数学、计算机科学、电子与通信等诸多学科于一身的交叉学科。它不仅能够保证机密性信息的加密，而且能够实现数字签名、身份验证、系统安全等功能。是现代化发展的重要科学之一。本文将对公钥密码系统及该系统中目前最广泛流行的RSA 算法做一些简单介绍。 §2公钥密码系统 要说明公钥密码系统，首先来了解一下不同的加密算法：目前的加密算法按密钥方式可分为单钥密码算法和公钥密码算法。 2.1. 单钥密码 又称对称式密码，是一种比较传统的加密方式，其加密运算、解密运算使用的是同样的密钥，信息的发送者和信息的接收者在进行信息的传输与处理时，必须共同持有该密码（称为对称密码）。因此，通信双方都必须获得这把钥匙，并保持钥匙的秘密。 单钥密码系统的安全性依赖于以下两个因素：第一，加密算法必须是足够强的，仅仅基于密文本身去解密信息在实践上是不可能的；第二，加密方法的安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确保算法的秘密性（事实上，现实中使用的很多单钥密码系统的算法都是公开的），但是我们一定要保证密钥的秘密性。 从单钥密码的这些特点我们容易看出它的主要问题有两点：第一，密钥量问题。在单钥密码系统中，每一对通信者就需要一对密钥，当用户增加时，必然会带来密钥量的成倍增长，因此在网络通信中，大量密钥的产生﹑存放和分配将是一个难以解决的问题。第二，密钥分发问题。单钥密码系统中，加密的安全性完 数学文化课程报告题目：RSA公钥加密算法及实现 RSA公钥加密算法及实现 摘要 公钥密码是密码学界的一项重要发明，现代计算机与互联网中所使用的密码技术都得益于公钥密码。公钥密码是基于数学的上的困难问题来保证其性。其中RSA加密算法是一项重要的密码算法，RSA利用大整数的质数分解的困难性，从而保证了其相对安全性。但如果发现了一种快速进行质数分解的算法，则RSA算法便会失效。本文利用C 语言编程技术进行了RSA算法的演示[1]。 关键词：C语言编程、RSA算法、应用数学。 RSA public key encryption algorithm Abstract Public key cryptography is an important invention in cryptography, thanks to public key cryptography, and it is used in modern computer and Internet password technology. Public key cryptography is based on the mathematics difficult problem to ensure its confidentiality. The RSA public key encryption algorithm is an important cryptographic algorithm, RSA using the difficulty that large integer is hard to be factorized into prime Numbers to ensure it safety. But if you can find a kind of fast algorithm to do the factorization, RSA algorithm will be failure. In this paper we used C language programming technology to demonstrate the RSA algorithm. Keywords：C language programming、RSA algorithm、Applied mathematics 226 Kerberos采用对称密钥体制对信息进行加密。其基本思想是：能正确对信息进行解密的用户就是合法用户。用户在对应用服务器进行访问之前，必须先从第三方（Kerberos服务器）获取该应用服务器的访问许可证（ticket）。 Kerberos密钥分配中心KDC（即Kerberos服务器）由认证服务器AS和许可证颁发服务器TGS构成。Kerberos认证过程具体如下。 ①用户想要获取访问某一应用服务器的许可证时，先以明文方式向认证服务器AS发出请求，要求获得访问TGS的许可证。 ②AS以证书（credential）作为响应，证书包括访问TGS的许可证和用户与TGS间的会话密钥。会话密钥以用户的密钥加密后传输。 ③用户解密得到TGS的响应，然后利用TGS的许可证向TGS申请应用服务器的许可证，该申请包括TGS的许可证和一个带有时间戳的认证符（authenticator）。认证符以用户与TGS间的会话密钥加密。 ④TGS从许可证中取出会话密钥、解密认证符，验证认证符中时间戳的有效性，从而确定用户的请求是否合法。TGS确认用户的合法性后，生成所要求的应用服务器的许可证，许可证中含有新产生的用户与应用服务器之间的会话密钥。TGS将应用服务器的许可证和会话密钥传回到用户。 ⑤用户向应用服务器提交应用服务器的许可证和用户新产生的带时间戳的认证符（认证符以用户与应用服务器之间的会话密钥加密）。 ⑥应用服务器从许可证中取出会话密钥、解密认证符，取出时间戳并检验有效性；然后向用户返回一个带时间戳的认证符，该认证符以用户与应用服务器之间的会话密钥进行加密。据此，用户可以验证应用服务器的合法性。 至此，双方完成了身份认证，并且拥有了会话密钥。其后进行的数据传递将以此会话密钥进行加密。 Kerberos将认证从不安全的工作站移到了集中的认证服务器上，为开放网络中的两个主体提供身份认证，并通过会话密钥对通信进行加密。对于大型的系统可以采用层次化的区域（realm）进行管理。 Kerberos也存在一些问题：Kerberos服务器的损坏将使整个安全系统无法工作；AS在传输用户与TGS间的会话密钥时是以用户密钥加密的，而用户密钥是由用户口令生成的，因此可能受到口令猜测的攻击；Kerberos使用了时间戳，因此存在时间同步问题；要将Kerberos用于某一应用系统，则该系统的客户端和服务器端软件都要做一定的修改。 2．公钥加密算法与RSA （1）公钥加密算法。在私钥加密算法（对称加密算法）DES中，加密和解密所使用的密钥是相同的，其保密性主要取决于对密钥的保密程度。加密者必须用非常安全的方法将密钥传给接收者。如果通过计算机网络传送密钥，则必须先对密钥本身予以加密后再传送。 1976年，美国的Diffe和Hallman提出了一个新的非对称密码体系（公钥加密算法）。其主要特点是在对数据进行加密和解密时使用不同的密钥。每个用户都保存着一对密钥，每个人的公开密钥都对外开放。假如某用户要与另一用户通信，可用公开密钥对数据进行加密，而收信者则用自己的私有密钥进行解密，这样就可以保证信息不会外泄。 公钥加密算法的特点可总结为以下几点。 ①加密和解密分别用加密密钥和解密密钥两个不同的密钥实现，并且不可能由加密密钥推导出解密密钥（或者不可能由解密密钥推导出加密密钥）。其加/解密过程如图12-9所示。 RSA加密算法是最常用的非对称加密算法，CFCA在证书服务中离不了它。但是有不少新来的同事对它不太了解，恰好看到一本书中作者用实例对它进行了简化而生动的描述，使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读，希望能够对时间紧张但是又想了解它的同事有所帮助。 RSA是第一个比较完善的公开密钥算法，它既能用于加密，也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名，这个算法经受住了多年深入的密码分析，虽然密码分析者既不能证明也不能否定RSA的安全性，但这恰恰说明该算法有一定的可信性，目前它已经成为最流行的公开密钥算法。 RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数（100到200位十进制数或更大）的函数。从一个公钥和密文恢复出明文的难度，等价于分解两个大素数之积（这是公认的数学难题）。 RSA的公钥、私钥的组成，以及加密、解密的公式可见于下表： 可能各位同事好久没有接触数学了，看了这些公式不免一头雾水。别急，在没有正式讲解RSA加密算法以前，让我们先复习一下数学上的几个基本概念，它们在后面的介绍中要用到： 一、什么是“素数”？ 素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；又如，12＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。素数也称为“质数”。 二、什么是“互质数”（或“互素数”）？ 小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”这里所说的“两个数”是指自然数。 判别方法主要有以下几种（不限于此）： （1）两个质数一定是互质数。例如，2与7、13与19。 （2）一个质数如果不能整除另一个合数，这两个数为互质数。例如，3与10、5与26。 （3）1不是质数也不是合数，它和任何一个自然数在一起都是互质数。如1和9908。 （4）相邻的两个自然数是互质数。如15与16。 （5）相邻的两个奇数是互质数。如49与51。 （6）大数是质数的两个数是互质数。如97与88。 （7）小数是质数，大数不是小数的倍数的两个数是互质数。如7和16。 （8）两个数都是合数（二数差又较大），小数所有的质因数，都不是大数的约数，这两个数是互质数。如357与715，357=3×7×17，而3、7和17都不是715的约数，这两个数为互质数。等等。 三、什么是模指数运算？ 指数运算谁都懂，不必说了，先说说模运算。模运算是整数运算，有一个整数m，以n为模做模运算，即m mod n。怎样做呢？让m去被n整除，只取所得的余数作为结果，就叫做模运算。例如，10 mod 3=1； 26 mod 6=2；28 mod 2 =0等等。 数据加密方法及原理介绍 一、加密术语 ■加密 ◇透过数学公式运算，使文件或数据模糊化，将容易识别的明文变成不可识别的密文 ◇用于秘密通讯或安全存放文件及数据 ■解密 ◇为加密的反运算 ◇将已模糊化的文件或数据还原，由密文还原出明文 ■密钥 ◇是加密/解密运算过程中的一个参数，实际上就是一组随机的字符串 二、加密方法 1、对称式加密 ◆使用同一把密钥对数据进行加密和解密，又称对称密钥（Symmetric Key）或（Secret Key） ◆进行加密通信前需要将密钥先传送给对方，或者双方通过某种密钥交换方法得到一个对称密钥 ◆缺点：破解相对较容易 ◆优点：加密/解密运算相对简单，耗用运算较少，加密/解密效率高 ◆常见算法：40Bits～128Bits ●DES、3DES、AES、RC2、RC4等 2、非对称式加密（也称为公钥/私钥加密） ◆I公钥加密主要用于身份认证和密钥交换。公钥加密，也被称为"不对称加密法"，即加解密过程需要两把不同的密钥，一把用来产生数字签名和加密数据，另一把用来验证数字签名和对数据进行解密。 ◆使用公钥加密法，每个用户拥有一个密钥对，其中私钥仅为其个人所知，公钥则可分发给任意需要与之进行加密通信的人。例如：A想要发送加密信息给 B，则A需要用B的公钥加密信息，之后只有B才能用他的私钥对该加密信息进行解密。虽然密钥对中两把钥匙彼此相关，但要想从其中一把来推导出另一把，以目前计算机的运算能力来看，这种做法几乎完全不现实。因此，在这种加密法中，公钥可以广为分发，而私钥则需要仔细地妥善保管。 ◆双方使用“不同密钥”执行加密/解密工作 ◆又称为不对称密钥（Asymmetric Key），由一对公钥（Public Key）和私钥（Private Key）构成一个密钥对 ◆密钥对具有单向性（One Way Function）以及不可推导性。公钥可以对外公开或传给通讯过程的另一方，私钥不可泄露必须由自己妥善保管，采用公钥加密的数据只能通过私钥解密，采用私钥加密的数据也只能通过公钥来解密。所谓有不可推导性是指通过公钥几乎是不可能推导出对方的私钥的，一般情况下都是采用公钥来加密，私钥用来解密及数字签名等 ◆密钥的保管 ●公钥可传送给需要进行安全通信的计算机或用户 ●私钥必须由自己好好保管，不可泄露 ◆缺点：加密/解密复杂，耗用较多运算，速度慢，效率相对较低 ◆优点：破解困难，安全性高，目前还没有发现公钥算法被破解的情况 ◆常见算法：512 bits～4096 bits ●DH算法（Diffie-Hellman）：非常典型的一种公钥算法，IPSec中普通使用DH算法 ●RSA（Rivest-Shamir-Aldeman由这三个人共同发明的一种安全性极高的公钥算法）现在的SSL安全通信中普通采用RSA算法来进行生成通信双方最终用于数据加密和解密的对称密钥、数字签名等方面 ◆非对称（公钥）加密算法原理介绍 本节以DH算法为例对非对称（公钥）加密算法的原理进行一个通俗、简单的简述，目的在于帮助大家了解非对称加密算法的基本工作原理，以及如何通过该算法巧妙的得出一个通信双方最终用来对数据进行加密/解密的共享密钥（对称密钥）。 背包密码体制之背包算法 姓名：张全英 学号：20143967 专业：信息与计算科学1班 学院：数学与信息科学 摘要：网络和信息安全正在成为一个国家政治、军事、经济以及社会生活正常运行的基础,它将是一个国家综合实力的重要体现。而密码学是信息安全的核心。公钥密码又是将加密、解密密钥甚至加密、解密函数分开,用户只保留解密密钥,而将加密密钥和加密函数一起公之于众,是密码学的重要组成部分。背包公钥和RSA一样是著名的公钥体制之一,特别是背包公钥的安全基础是背包问题,这是一个NP难问题。虽然在提出不久就遭到破解,但是在提出的背包公钥系统的改进方案中依然有几个被证明是安全的。背包公钥是首个把NP问题用于公钥密码的密码体制,而其他现阶段应用的公钥密码体制都是基于因式分解或离散对数问题的,他们都不是NP问题构造的,因此背包公钥体制的研究是十分有意义的。本文从背包体制的常用攻击方法入手,寻找被破解的原因,并针对这些原因提出了新的构造思路,利用非超递增序列构造背包体制。利用非超递增序列构造背包公钥有2个必须解决的问题是加密结果的不唯一性和解密的困难性。本文对一种同余多模背包序列进行分析,并利用得出的性质构造一种新的L序列,并证明了L序列能解决以上2个问题,并提出了利用L序列构造背包公钥体制的方案。为了加快加解密速度,还提出了模M和W-1的逆向构造算法。然后给出了非超递增背包公钥体制的模拟实现。 关键字：模逆，欧几里德算法，同余式，超递增序列 目录： 1.公钥密码的原理 2.公钥密码的数学基础： 一个公开密钥密码系统必须满足的条件是： A.通讯双方A和B容易通过计算产生出一对密钥（公开密钥K1，私钥密钥K2）。 B.在知道公开密钥K1和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文： C.C = Ek1（M） D.接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文： E.M = Dk2（C）= Dk2[Ek1（M）] F.除A和B以外的其他人即使知道公钥k1，要确定私钥K2在计算上也是不可行的。 G.除A和B以外的其他人即使知道公钥k1和密文C，要想恢复原来的明文C在计算上也是不可行的。 3.数论基础知识： 这些要求最终可以归结到设计一个单向陷门函数。 4.单向函数：单项陷门函数： 一个单向函数是满足下列条件的函数：它将一个定义域映射到值域，使得每个函数值有一个唯一的原像，同时还要满足下列条件：函数值计算很容易，而逆计算是不可行的。 所谓单向陷门函数是这样的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在另外的方向上要计算是不可行的。有了附加的信息，函数的逆就可以在多项式时间内计算出来。 一个实用的公开密钥密码系统的建立和发展依赖于找到一个单向陷门函数。 密码学中两种常见的密码算法为对称密码算法（单钥密码算法）和非对称密码算法（公钥密码算法）。 对称密码算法有时又叫传统密码算法，就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加密解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加密解密。只要通信需要保密，密钥就必须保密。对称算法的加密和解密表示为： Ek(M)=C Dk(C)=M 对称算法可分为两类。一次只对明文中的单个位（有时对字节）运算的算法称为序列算法或序列密码。另一类算法是对明文的一组位进行运算，这些位组称为分组，相应的算法称为分组算法或分组密码。现代计算机密码算法的典型分组长度为64位――这个长度大到足以防止分析破译，但又小到足以方便作用。 这种算法具有如下的特性： Dk(Ek(M))=M 常用的采用对称密码术的加密方案有5个组成部分（如图所示） l）明文：原始信息。 2)加密算法：以密钥为参数，对明文进行多种置换和转换的规则和步骤，变换结果为密文。 3)密钥：加密与解密算法的参数，直接影响对明文进行变换的结果。 4)密文：对明文进行变换的结果。 5)解密算法：加密算法的逆变换，以密文为输入、密钥为参数，变换结果为明文。 对称密码术的优点在于效率高（加／解密速度能达到数十兆／秒或更多），算法简单，系统开销小，适合加密大量数据。 尽管对称密码术有一些很好的特性，但它也存在着明显的缺陷，包括： l）进行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情况下是可行的，但在某些情况下会非常困难，甚至无法实现。 2)规模复杂。举例来说，A与B两人之间的密钥必须不同于A和C两人之间的公钥密码算法
密码学实验-RSA公钥密码
公钥加密算法
RSA加密算法的基本原理
常见的几种加密算法
用实例讲解RSA加密算法(精)
公钥密码技术讲义
RSA算法公钥加密算法
公钥密码系统及RSA公钥算法
RSA加密算法及实现
2.公钥加密算法与RSA[共2页]
用实例给新手讲解RSA加密算法
数据加密方法及原理介绍
浅谈背包公钥密码体制全解
公钥密码和对称密码