密码学简介

密码学一开始的功能是在有恶意攻击者存在的环境下，保护双方通信安全，现在是保护信息安全的核心技术。

现代信息安全的基本要求

• 信息保密性(加解密)
• 信息完整性(消息认证码、数字签名)
• 认证性(消息认证码、数字签名)
• 不可否认性(数字签名)

古典密码学

经典算法：

• 置换密码：加密过程中明文的字母保持相同，但是顺序被打乱。
• 代换密码：明文中的每一个字符被替换成密文中的另一个字符。

现代密码学

现代密码学主要有三个方向：对称密码、公钥密码和安全协议

对称密码

使用相同的密码进行加解密操作，只是加密算法和解密算法不同，但密钥的分发是要保密进行的。

例如DES算法和AES算法。

DH密钥交换协议

DH密钥交换协议使得发送接收双方在不安全信道上共享密钥，该密钥用于双方加解密密钥。容易受到中间人攻击。DH算法的安全性依赖于计算离散对数的困难程度，例如y=(g的x次方) mod p,p为素数。交换过程如下。

DH协议大致过程：

• 客户端和服务端先对p和g达成一致，并且公开出来。中间人C也知道。

• 客户端生成私钥整数a，然后使用A=g^a mod p 得到公钥A发给服务端。中间人C也知道。

• 服务端也生成私钥整数b，然后使用B=g^b mod p得到公钥B发给服务端。中间人也知道。

• 客户端使用S=B^a mod p=g^b^a mod p计算出S

• 服务端使用S=A^b mod p=g^a^b mod p计算出S

• 这样就得出了公用的密钥S，然后使用共享密钥S进行加解密操作。

  安全性：

  虽然客户端服务端传输的公钥A、B公开，由于客户端服务端双方生成的a、b密钥是私钥不进行传输，并由于离散对数的难解，破解出最终的对称密钥是及其困难的。

  但是容易受到中间人工攻击。即攻击者通过伪造服务端身份和客户端身份协商密钥，攻击者通过伪造客户端身份和服务端身份协商密钥，这样攻击者就分别获得和客户端和服务端的共享密钥。这样攻击者就可以通过中间人的身份修改被客户端和服务端之间的信息啦。

公钥密码

公钥密码不同于对称密码，其加解密密码不一样，也称非对称密码。发送方和接收方各自生成自己的密钥对，过程大致是发送方使用对方的公钥进行加密处理，只有接收方使用自己的私钥才能对其解密获取信息。

RSA算法

给出两个素数，很容易得到乘积，但想反推得到这两个素数就很困难。

密钥对生成

• 选取两位非常大的素数p和q
• 计算出大素数乘积n=qp，*m=(p-1) * (q-1)，这里m是n的欧拉函数
• 找到满足gcd(m,e) = 1的e(1<e<m)，即e和m互素
• 找到满足ed mod m = 1的d(e在模m域上的逆元d)
• **(n,e)为公钥，(n,d)**为私钥

RSA加密

对于明文x，使用公钥(n,e)对x加密的过程，就是将x转换为数字，然后通过幂取模计算得到y。
$$
y=x^e mod n
$$
RSA解密

对于密文y，使用私钥(n,d)对y进行解密的过程，就是将y转换为数字，然后通过幂取模计算得到x。
$$
x = y^d mod n
$$
由于n是大整数，大整数的因素分解暂时没有高效的算法。只要将n分解，则q和p就能计算出来。