目录

一、凯撒密码的实现及破解

（一）凯撒密码简要介绍    

（三）破解过程关键代码实现

二、维吉尼亚密码的实现及破解

（一）维吉尼亚密码简要介绍    

（三）破解过程关键代码实现

三、一次一密密码的实现及破解 

（一）一次一密加密法简要介绍    

（二）实现过程关键代码实现

（三）维吉尼亚密码的破解实现 

四、RSA加密法的实现及破解 

（一）RSA加密法简要介绍    

五、参考资料

本项目是对最为经典的几种密码学算法作介绍与python编程实现，对于其中几种较为简单的加密算法，加入了破解程序。本人是该领域初学者，所以本篇文章也仅仅是浅尝辄止。本人并不奢望读者可以通过本文学到非常多的相关知识，意图在于用尽可能简单的流程引导跟我类似的初学者了解密码学的经典算法并激发学习欲望。

本文的绝大部分参考程序来自于作者Al Sweigart的书籍《Python密码学编程》，想深入学习了解的读者可以购买查阅此书，对本文中的代码感兴趣的读者也可查阅此书或私信我~

      凯撒密码是最早的代换密码，使用单表代换。其基本思想是：通过把字母移动一定的位数来实现加密和解密。明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。其作为最早的置换密码之一，原理已被广泛理解，且常作为教学的入门密码学案例。在现代，凯撒密码主要用于教育目的，很少用于实际安全应用，因为其易于通过暴力破解、频率分析等方法被破解。

（二）实现过程关键代码实现

在Python中，可以通过字符在26字母表中的索引进行转换，加上偏移量后再将其转换回字符，实现简单的凯撒密码加密和解密。

破解脚本则通过尝试所有可能的密钥和检测结果的方法，尝试找到正确的密钥来解密信息。如果输出结果有可读的英文明文，则说明可能找到了正确的密钥。

维吉尼亚密码是一种使用一串密钥词进行加密的方法。每个字母的偏移量由密钥词中相对应位置的字母决定。这种密码相较于单一偏移的凯撒密码提供了更高的安全性。见下图， 如果我们使用“PIZZA”作为维吉尼亚密钥，那么第1个子密钥是P，第2个子密钥是I，第3和4个子密钥都是Z，第5个子密钥是A。我们将使用第1个来加密明文的第1个字母，使用第2个密钥来加密第2个字母，如此类推。当我们到达明文的第6个字母时，我们将回过头来使用第1个子密钥。

示例：用维吉尼亚加密法加密“HAPPY”

（二）实现过程关键代码实现

通过对每个字母根据密钥字母（子密钥）相应位置的偏移量进行加密，实现加密过程。解密过程相反，根据密钥字母的偏移量进行反向操作。

 针对每个子密钥，尝试26个可能的字母进行解密，按以下思路进行代码编写：（1）量化解密后文本的字母频率与常规频率的接近程度；（2）结果越接近常规频率的，就越可能是正确的子密钥；（3）排列组合所有可能子密钥，形成可能的完整密钥；（4）利用英文检验来验证密钥。

卡西斯基试验：

这是一种判断维吉尼亚密钥可能长度的方法，它的步骤如下： 找出密文中的重复序列——算出重复序列的间距算出重复序列的间距——获取间距的因数——次数最高的因数很可能就是 维吉尼亚密钥的长度。

    密钥遍历：

英文识别：

      函数默认要求至少有20%的单词存在于字典中，并且至少有85%的字符是字母或空格。 如果这两个条件都满足，函数返回True，表示文本是英文；否则返回False。利用该函数，我们就可以在检测到可能都英文明文时，停止遍历，返回密钥和输出结果。

一次一密加密法(one-time pad cipher)是牢不可破的加密法。它是在维吉尼亚加密法的基础上增加以下条件：（1） 密钥和要加密的消息同样长。（2）密钥由真正随机符号组成。（3）密钥只用一次，永不对其他消息复用。所以其实现即把维吉尼亚加密法的密钥长度改为消息长度一样长的字符串即可。（以下仅展示修改部分）

仅展示相对于维吉尼亚密码的修改部分

既然在简介中都说了“一次一密加密法(one-time pad cipher)是牢不可破的加密法”，本部分自然就没有对应的破解密码。接下来阐释它为什么无法破解：（1）暴力破解？ 需要尝试的次数：

26的n次方！ n = len(message)

一旦密钥的长度达到12个字母或者更多，大多数消费级别的笔记本计算机就不可能在合理的时间内破译了。

（2）与维吉尼亚破解相同的“频率分析”

每个明文字符都是通过各自的密钥进行加密的，所以频率分析也失去意义。

（3）即使存在算力无限的计算机，该加密法也是无法破解的。

可以看以上例子，相同的密文经过不同的密钥破解后，可能形成不同的可能英文明文。事实上，任何相同长度的可读英语明文消息都可能是原来的明文。 不能因为某个密钥可以把密文解密成可读英文就说它是原来的加密密钥。

RSA加密法是一种基于非对称加密的算法，它依赖于一对密钥：一个公钥用于加密数据，一个私钥用于解密数据。 RSA的核心安全性基于大数分解问题的计算难度：给定两个大质数的乘积，恢复原来的质数是非常困难的。

（二）实现过程关键代码实现 

(1)Rabin-Miller素性检验

Rabin-Miller素性测试是一个有效的算法，可以快速判断大数是否为素数，尽管它是一个概率性算法，但通过足够多的测试可以使错误的概率非常小。

（2）主函数及加密函数：

由于本加密方法的代码过长，此处不做展示啦，实际上就是对简介部分的算法描述做拆解并分别实现，如果各位感兴趣可以查阅书籍、资料或与我联系。

（三）RSA算法的破解

RSA的核心安全性基于大数分解问题的计算难度：给定两个大质数的乘积，恢复原来的质数是非常困难的。所以它的破解十分困难，至少在我的计算机上应该是无法完成的，此处就自然也没有破解的实现啦。但是需要说明的是，在量子计算机相关领域快速发展的当下，RSA加密法也面临着被破解的风险。此外，本文中的加密法并不是完全不存在漏洞的，比如本代码生成的随机数实际上是“伪随机数”，攻击者可以利用这一点很方便地知道生成的大质数p和q，所以本文的算法代码只是RSA简单实现。再者说，每个密码学相关学习者都不应该认为自己所编写的加密算法是坚不可摧的~

书目： Hacking Secret Ciphers with Python https://inventwithpython.com/hacking/ 

【乐正垂星】恺撒密码，完美加密，与现代密码学初探https://www.bilibili.com/video/BV1ce4y1q778/?spm_id_from=333.337.search-card.all.click&vd_source=d98aad613320e6f9f29e11acfbbe7a61

详解维吉尼亚密码（附四种攻击策略）https://blog.csdn.net/forest_LL/article/details/135300302

感谢您能读到这里！再次声明，如果你对密码学领域初学并找不到渠道的话，强烈推荐您参考本文文首提到的书籍！下回见W~