Crypto 基础¶
约 935 个字 3 行代码 预计阅读时间 5 分钟
RSA算法¶
Quote
RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
- 对称密码：加密和解密使用同一种密钥的方式
- 公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。
算法描述¶
- 密钥计算方法
- 任意选取两个大素数p和q
- 计算 \(n=p\times q\) 和 \(z=(p-1)\times (q-1)\) // \(n\) 表示欧拉函数
- 找到一个 \(e\) 满足 \(gcd(e,z)=1\) (注意：e的选取是很容易的，例如，所有大于p和q的素数都可用)
- 确定解密钥 \(d\) ，满足 \((de)\mod z =1\)
- 则公开密钥为 \((e,n)\) ，私有密钥为 \((d,n)\)
- 加密方法
- \(密文=明文^e\mod n\)
- 解密方法
- \(明文=密文^d\mod n\)
Info
只根据公开密钥e,n计算出d是不可能的，因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密
Vigenere 维吉尼亚密码¶
维吉尼亚密码是多表密码的一种简单形式，加密强度相对于单表替换已经增强了许多，但是仍然会因语言学特性被轻松破解。
加密表
下面给出一个例子
明文：come greatwall 密钥：crypto
首先，对密钥进行填充使其长度与明文长度一样。
| 明文 | c | o | m | e | g | r | e | a | t | w | a | l | l |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 密钥 | c | r | y | p | t | o | c | r | y | p | t | o | c |
其次，查表得密文
明文：come greatwall 密钥：crypto 密文：efkt zferrltzn
破解¶
对包括维吉尼亚密码在内的所有多表密码的破译都是以字母频率为基础的，但直接的频率分析却并不适用，这是因为在维吉尼亚密码中，一个字母可以被加密成不同的密文，因而简单的频率分析在这里并没有用。
破译维吉尼亚密码的关键在于它的密钥是循环重复的。 如果我们知道了密钥的长度，那密文就可以被看作是交织在一起的凯撒密码，而其中每一个都可以单独破解。关于密码的长度，我们可以 使用卡西斯基试验和弗里德曼试验来获取。
卡西斯基试验是基于类似 the 这样的常用单词有可能被同样的密钥字母进行加密，从而在密文中重复出现。例如，明文中不同的 CRYPTO 可能被密钥 ABCDEF 加密成不同的密文：
此时明文中重复的元素在密文中并不重复。然而，如果密钥相同的话，结果可能便为（使用密钥 ABCD）：
此时卡西斯基试验就能产生效果。对于更长的段落此方法更为有效，因为通常密文中重复的片段会更多。如通过下面的密文就能破译出密钥的长度：
其中，两个 DYDUXRMH 的出现相隔了 18 个字母。因此，可以假定密钥的长度是 18 的约数，即长度为 18、9、6、3 或 2。而两个 NQD 则相距 20 个字母，意味着密钥长度应为 20、10、5、4 或 2。取两者的交集，则可以基本确定密钥长度为 2。确定了密钥长度后，可以通过字母频率或者单词频率猜测密钥的其中几位，随后根据已解密的部分猜测单词，继续进行密钥的破解