公钥密码学与RSA

对称密码体制的缺陷

公钥密码学 是密码学一次伟大的革命 使用两个密钥：公密钥、私密钥 加解密的非对称性 公钥加密算法是基于数学函数而不是对位的形式的简单操作。 1976年，Diffie和Hellman 在“密码学新方向”一文中提出 使用两个密钥：公密钥、私密钥 加解密的非对称性 公钥加密算法是基于数学函数而不是对位的形式的简单操作。 是对对称密码的重要补充 公钥加密一般用于消息认证和密钥分配。

公钥密码学解决的基本问题 密钥交换 对称密码进行密钥交换的要求： 已经共享一个密钥 利用密钥分配中心 数字签名 与传统的签名比较

公钥密码体制 重要特点 六个组成部分： 仅根据密码算法和加密密钥来推导解密密钥在计算上不可行 两个密钥中的任何一个都可用来加密，另一个用来解密。 六个组成部分： 明文、密文；公钥、私钥； 加密、解密算法

公钥密码体制

公钥密码体制的加密功能 A向B发消息X， B的公钥为KUb,私钥为KRb 加密 Y = EKUb(X) 解密 X = DKRb(Y)

公钥密码体制的加密

公钥密码体制的认证 A向B发送消息X A的公钥为KUa，私钥为KRa “加密”： Y = EKRa(X) （数字签名） “解密”： X = DKUa(Y) 注意：不能保证消息的保密性

具有保密与认证的公钥体制

对称密码 公钥密码 一般要求： 1、加密解密用相同的密钥 2、收发双方必须共享密钥 安全性要求： 1、密钥必须保密 2、没有密钥，解密不可行 对称密码 公钥密码 一般要求： 1、加密解密用相同的密钥 2、收发双方必须共享密钥 安全性要求： 1、密钥必须保密 2、没有密钥，解密不可行 3、知道算法和若干密文不足以确定密钥 1、加密解密算法相同，但使用不同的密钥 2、发送方拥有加密或解密密钥，而接收方拥有另一个密钥 1、两个密钥之一必须保密 2、无解密密钥，解密不可行 3、知道算法和其中一个密钥以及若干密文不能确定另一个密钥

关于公钥密码的几种误解 公钥密码比传统密码安全？ 任何加密方案的安全性都依赖于密钥的长度和破解密码的计算工作。所以公钥加密不必常规加密更安全。用户只要保护他的私钥，接收的通信就是安全的 公钥密码是通用方法，所以传统密码已经过时？ 传统密码用来加密大批量数据，公钥密钥用来进行密钥分配。

RSA算法 由MIT的 Rivest, Shamir & Adleman 在 1977 提出 最著名的且被广泛应用的公钥加密体制 明文、密文是0到n-1之间的整数，通常n的大小为1024位或309位十进制数 RSA is the best known, and by far the most widely used general public key encryption algorithm.

RSA算法描述 加密： C=Me mod N, where 0≤M<N 解密： M=Cd mod N 公钥为（e，N）， 私钥为（d，N） 必须满足以下条件： 计算Me和Cd是比较容易的 由e和n确定d是不可行的

RSA 密钥产生过程 随机选择两个大素数 p, q 计算 N=p.q 选择 e使得1<e<ø(N),且gcd(e,ø(N))=1 e.d=1 mod ø(N) 且 0≤d≤N 公布公钥: KU={e,N} 保存私钥: KR={d,p,q} This key setup is done once (rarely) when a user establishes (or replaces) their public key. The exponent e is usually fairly small, just must be relatively prime to ø(N). Need to compute its inverse to find d. It is critically important that the private key KR={d,p,q} is kept secret, since if any part becomes known, the system can be broken. Note that different users will have different moduli N.

RSA 的使用 发送方要加密明文M: 接收方解密密文C: 注意：M必须比N小 获得接收方的公钥 KU={e,N} 计算: C=Me mod N, where 0≤M<N 接收方解密密文C: 使用自己的私钥 KR={d,N} 计算: M=Cd mod N 注意：M必须比N小

为什么RSA 可以加解密 因为 Euler 定理的一个推论: Mkø(n)＋1 = M mod N RSA 中: N=p.q 选择 e & d 使得ed＝1 mod ø(N) 因此 存在k使得e.d=1+k.ø(N) 因此 Cd = (Me)d = M1+k.ø(N) = M mod N Can show that RSA works as a direct consequence of Euler’s Theorem.

RSA Example Select primes: p=17 & q=11 Compute n = pq =17×11=187 Select e : gcd(e,160)=1; choose e=7 Determine d: de=1 mod 160 and d < 160 Value is d=23 since 23×7=161= 1×160+1 Publish public key KU={7,187} Keep secret private key KR={23,17,11} Here walk through example using “trivial” sized numbers. Selecting primes requires the use of primality tests. Finding d as inverse of e mod ø(n) requires use of Inverse algorithm (see Ch4)

RSA Example cont sample RSA encryption/decryption is: given message M = 88 (nb. 88<187) encryption: C = 887 mod 187 = 11 decryption: M = 1123 mod 187 = 88 Rather than having to laborious repeatedly multiply, can use the "square and multiply" algorithm with modulo reductions to implement all exponentiations quickly and efficiently (see next).

RSA 密钥生成 必须做 素数测试是重要的算法 由e求d要使用到扩展Euclid算法 确定两个大素数： p, q 选择e或者d，并计算d或者e 素数测试是重要的算法 由e求d要使用到扩展Euclid算法 Both the prime generation and the derivation of a suitable pair of inverse exponents may involve trying a number of alternatives, but theory shows the number is not large.

RSA 的安全性 三种攻击 RSA的方法: 强力穷举密钥:尝试所有可能的密钥。因此，e 和d 的位数越大，算法就越安全。然而，在密钥产生和加密解密中使用的计算都非常复杂，所以密钥越大，系统运行越慢。 时间攻击：依赖解密算法的运行时间

RSA 的安全性 数学攻击 ：实质上是对两个素数乘积的分解. RSA的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。现在，人们已能分解多个十进制位的大素数。因此，模数n 必须选大一些，因具体适用情况而定。目前，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢。

RSA 的安全性 例如：1977年RSA的三个发明者邀请《Scientific American》的读者参加比赛，去解密他们在Martin Gardner 的Mathematical Games 专栏中列出的一段密码，并提供奖励。他们认为在1015 年内都不会发生的事。在1994年4月，一个工作组使用1600多台计算机，只经过8个月的工作，就破解了这段密码。该比赛使用的公钥的长度（n的大小）是129位十进制数字。这样的结果并没有使RSA失效，他只是意味必须使用更大的密钥。 当前小于1024位的N已经被证明是不安全的，自己使用中不要使用小于1024位的RSA，最好使用2048位的。

RSA算法 RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。 RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法

RSA算法 此外还正在积极寻找攻击RSA的方法，如选择密文攻击，一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。 对付以上攻击，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash Function对文档作HASH处理，或同时使用不同的签名算法。

RSA算法的优缺点 优点是密钥空间大 缺点 1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。 2)速度太慢。由于进行的都是大数计算，使得RSA最快的情况也比DES慢上倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。由于RSA 的分组长度太大，为保证安全性，n 至少也要 600 bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。为了速度问题,目前人们广泛使用单,公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA来给文件密钥加密,极好的解决了单钥密码的密钥分发问题。