信息安全复习六：公开密钥密码学

一、章节梗概

1.公开密钥密码模型的基本原理
2.两个算法：RSA&D-H算法

主要内容
1.对称密钥密码的密钥交换问题
2.公钥密码模型的提出
3.设计公钥密码的基本要求
4.数字签名
5.RSA算法
6.公钥密码的特征总结

二、对称密钥密码

对称加密算法中，数据发送方将明文和密钥一起经过特殊加密算法处理成密文后，将它发送出去。接收方收到密文后，若想解读原文，则需要使用加密用到的相同密钥及相同算法的逆算法对密文进行解密，才能使其恢复成原文。

常见的对称加密算法有 AES、DES、Blowfish 等等。
对称加密的核心是只有一把密钥。

对称密钥密码模型中，双方共享的秘密是密钥KEY，解决的问题是保密通道。

对称的、单密钥、秘密密钥、传统密钥：发送方加密和接收方解密使用的是同一个密钥。

该密钥需要事先由发送方和接收方实现共享，是发送方和接收方共同的秘密。

如果密钥泄露，则不安全（无法实现保密性服务）

对称：通信双方是对等的。

三、公开密钥密码模型

非对称加密算法中，有两个密钥：公钥和私钥。它们是一对，如果用公钥进行加密，只有用对应的私钥才能解密；如果用私钥进行加密，只有用对应的公钥才能解密。
    非对称加密算法实现机密信息的交换过程为：甲方生成一对密钥并将其中一个作为公钥向其他方公开；得到该公钥的乙方使用该密钥对机密信息进行加密后发送给甲方；甲方再用自己的另一个专用密钥对加密后的信息进行解密。
     最有名的非对称加密算法当属 RSA 了，本文将对 RSA 算法的加/解密过程进行详细剖析。
    非对称加密拥有两把密钥。

3.1 非对称的、双密钥：每个人都有两个密钥

公钥：公开
私钥：保密

3.2 根据使用的密钥数量区分的两种密码体制

对称的、单密钥、秘密密钥、传统密码技术：发送发和接收方使用同一个密钥。

非对称的、双密钥、公开密码技术：发送方和接收方使用不同的密钥。

加密密钥和解密密钥分割开来，且无法由一个推算出另一个，使得不仅能公开加密算法，公开密钥也可以公开(公告牌、个人主页、号码簿)。

3.3 公开密钥密码

两个密钥：公钥和私钥
非对称：通信双方的地位不平等

往往利用数论的一些函数精心构造
补充而非取代对称密钥密码技术

缺点：公开密钥密码的主要弱点是加解密速度慢。

3.4 公开密钥的历史

1976年Diffie 和 Hellman在论文密码学新方向( New Direction in Cryptography ) 中首次提出了公开密钥密码体制的问题。

Diffie和 Hellman提出了第一个基于公开密钥思想的密码算法，称为D-H算法，此算法可以用于实现密钥交换。

1977年Rivest Shamir和 Adleman三个人实现了公开密钥密码体制，现在称为RSA算法，它是第一个既能用于密钥交换，也能用于数据加密和数字签名的算法。

3.5 公开密钥加密系统

一个公开密钥加密系统由六要素组成：
明文
密文
加密算法
解密算法
公开密钥（PU/KU
私有密钥（PR/KR

3.6公开密钥密码原理总结

公钥：任何人可以知道，用于加密明文或验证签名
私钥：仅有接收者/拥有者知道，用于解密和构造签名。

非对称的含义
密钥的不对称：加/解密密钥不同
用于加密的不能解密，用于解密的不能加密。
双方地位不对等：通信双方知道的秘密不一样多，私钥只能自己知道。

四、数字签名

密钥对互相之间可以交换使用。

密钥对交换使用能提供什么功能：通信保密、数字签名。
什么是数字签名：所谓数字签名就是一种可以替代手写签名的一种签名技术。

手写签名的安全需求：可认证、抗抵赖。
所谓数字签名就是用私钥加密：可认证、抗抵赖。

对称密钥密码实现不了可认证和抗抵赖的安全需求。

五、RSA算法

5.1 RSA介绍

概念
是一个分组加密算法。
目前被最广泛采用。
基于数论中的Fermat（小）定理实现。
是一个既能用于密钥交换，也能用于数据加密和数字签名的算法。

算法原理
来源于数论的理论基础：要求得两个大素数得乘积很容易，但要分解一个合数为两个大素数得乘积，在计算上几乎不可能；采用得单向函数是大素数相乘，相乘很容易，但因子分解很难。

5.2 RSA密钥生成步骤

5.3 RSA加密和解密

RSA加密

RSA解密

5.4 RSA使用

1.公钥公开：PU={n,e}；私钥保密：PR={n,d}

2.加密报文：发送方获取接收方的公钥PU ={n,e}

3.计算密文：C = M^e mod n，0<=M<n

4.解密密文：接收方用自己的私钥PR={n,d}解密

5.计算M = C^d mod n

举例：
选择素数：p=17 & q=11
计算 n = pq = 19× 11 = 187
计算 m = （p-1)(q-1) = 18 × 10 =160
找到 e：gcd（160，e）=1 ，选择 e = 7
计算d：de mod m = 1，7d mod 160 = 1 得 d=23
生成密钥对：公钥PU={187,7}；私钥PR={187，23}

RSA加密：M = 88，C = 88^7 mod 187 =11
RSA解密：M = 11^23 mode 187 =88

5.5 RSA的安全性和速度

安全性：破解 RSA 的难点在于对 n 的因数分解，然而大整数的因数分解暂时没有高效的算法。

速度：RSA最快的情况也比DES慢许多倍，无论是软件还是硬件。因此一般只用于少量数据加密，一般做密钥交换。

RSA是最优秀的公钥方案之一。
RSA —— 经典的非对称加密算法

六、公开密钥密码的特征总结

公开密钥算法设计需要有以下基本要求:
加密与解密由不同的密钥完成
知道加密算法，从加密密钥得到解密密钥在计算上是不可行的
两个密钥中的任一个都可以作为加密，而另一个作为解密。

保密通信：公钥加密，私钥解密保密通信
数字签名：私钥加密(签名)，公钥解密(验证)

七、公开密钥密码算法的基础

1.单向函数
对于一个函数f(x)，如果对于其定义域上的任意x，f(x)都容易计算，同时对子其值域中几乎所有的取值y,计算其逆丽数f^-1(y)都是不可行的，则函数f(x)称为单向函数。

2.可以提供单向函数的三大数学难题
大整数分解问题
离散对数问题
椭圆曲线离散对数问题(简称ECDLP)

3.单向陷门函数
对于一个单向函数f(x)，如果其逆函数f^-1(x)在已知某些辅助信息的情况下，容易求解得出，则称该单向函数f(x)称为单向陷门函数。

构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的”陷门”。

4.其它
除RSA算法之外，建立在不同计算难题上的其他公开密钥密码算法有:
基于因子分解问题的Rabin算法；
椭圆曲线公钥算法；
基于有限域中离散对数难题的Elgamal公钥密码算法；
基于“子集和”难题的Merkel-HellmanKnapsack (背包）公钥密码算法;

八、Diffie-Hellman密钥交换算法

8.1 概念

是第一个公钥方案。
使用在一些常用安全协议或产品（例如sSH 、IPSEC)。

8.2 密钥交换方案

不能直接用于有大量数据传输的保密通信；
允许两个用户可以安全地建立一个共享的秘密信息，用于后续的通信过程；
该秘密信息仅为两个参与者知道；
算法的安全性依赖于有限域上计算离散对数的问题

8.3 算法流程

Diffie-Hellman算法简介