Crypto Lab 1：数学基础和古典密码 ¶

本节 Lab 由以下三个部分组成：

• Task 1：维吉尼亚密码破解
• Task 2：希尔密码破解
• Bonus：gcccd

Task 1 (40%)¶

课上介绍了维吉尼亚（Vigenere）密码，其作为多表加密的替换密码，加密强度相对于单表替换已经增强了许多，但是仍然会因语言学特性被轻松破解。

维吉尼亚密码的破解方法在课上有一定介绍，也做了一些展示，密钥的破解基本分为以下两步：

1. 爆破猜测密钥长度
   • 第一种方法是寻找多次重复的密文，然后计算密文间隔的最大公因数，即为最有可能的密钥长度，这个在课上已作展示
   • 此外，也可以爆破密钥长度，计算密文中相隔该长度的字符重合了几次，整体重合次数最多的长度可能就是密钥长度
2. 逐位爆破密钥
   • 确定了密钥长度后，可以通过字母频率或者单词频率猜测密钥的其中几位
   • 随后根据已解密的部分猜测单词，继续进行密钥的破解

本 Task 需要完成 ZJU School-Bus 上的 vigenere-encrypt 一题，在实验报告中简单描述这道题的做法。如果没法完整做出，也可以叙述自己的思路和解题过程，会根据完成情况给分。本题分值 40 分。

Task 2 (60%)¶

希尔密码是古典密码学与线性代数的结合，通过希尔密码的破解，也可以初步感受现代密码学的特点：以数学为基础的算法构建和破解。

本 Task 需要完成 ZJU School-Bus 上的 HSC 一题，在实验报告中简单描述这道题的做法。

这里首先先让同学们复现一下 sagemath 的使用方法，对完成本题或者之后专题的学习有较大的帮助。

• 对题目中的 MT 矩阵进行随机赋值，使其可逆，使用 sage 求出它的逆矩阵，分值 10 分
• 随机设置 flag 生成 FT，计算 RT，再通过 RT 和 MT 求出 FT 的值，与原 FT 进行比对，分值 10 分

如果后续没有选择密码学专题的打算，上述复现可以使用在线环境。

HSC 题目分值 40 分，加上 sage 复现部分本 Task 共 60 分，同样，如果没法完整做出，也可以叙述自己的思路和解题过程，会根据完成情况给分。

Bonus (+15%)¶

gcccd 是一道比较特别的密码学题目，题目附件已放在学在浙大，有兴趣的同学可以写出自己的做题思路，本题不需要写出完整的解题代码，会按照思路的可行与否进行给分，bonus 分值 15 分。

你可能需要用到的：

• 简单了解离散对数
• 了解一些 python 的小特性