密码学社课

木棉絮123 · 2025-01-01 16:17:09 · 个人记录

50分钟速通现代密码学入门

推荐阅读：

计算机入门：现代密码学 Modern Cryptography，借鉴对象。

OIWIKI 数论部分，你可以阅读 Meissel–Lehmer 算法，欧拉定理，费马小定理，原根和离散对数部分。出于大家理解程度的考虑，社课删节了数学内容。(这个网站是国内的，不需要翻墙)

OIWIKI 复杂度简介，理解复杂度记号和复杂度分析方式，你就可以衡量算法的运行时间。同上，社课删节了计算机科学部分。

《数学之美》，吴军，第十七章。全书都推荐阅读。（书图书馆有，在新书推介栏）

*OIWIKI 抽象代数部分或洛谷博客群论入门，学有余力可以研究一下。这里摘录一句话：“群论是抽象代数的分支。它已经很抽象了，所以学习的时候要尽量直观理解，不然就只剩一堆符号了。本文尽量多举一些例子。”

Intro

一些约定：

如果我在 ppt 上放了数学柿子式子，但是我没讲，说明它与主题不重要，我会把它放在延伸阅读里，你可以等社课结束以后自行查阅，或者询问我。

我留了三道思考题，大家感兴趣的话可以任选若干个写一份简要的研究报告，视完成情况给予一些小礼品（所以一定要写班级姓名啊！），提交地址：社长微信即可，或邮箱：[email protected]，

密码学初印象：

提到密码学你们会想到什么：

凯撒密码？《福尔摩斯探案集》“跳舞的小人”？，谍战片或者侦探片？

现代密码学和你想的不一样！接下来：三个例子

PS：如果有高二同学记忆好的话，这是上个学期某次英文讲座讲的内容，所以我这是在炒冷饭。

Coin Flip Problem

Coin Flip 问题：

Alice 和 Bob 计划去售货机买卡士酸奶，他们决定以一种公平的方式选出其中一方请客，而且都想让对方买单。

形式化的描述：设计一种游戏，使得双方获胜的概率均等，且双方互不信任。

直接石头剪刀布不就好了吗。

双方都认为对方会晚出。

形式化的描述：双方互不信任，存在通信上的不确定性（即不能双方同时发出一条消息/同时进行决策）。

这多简单，Alice 扔硬币，Bob 猜正反即可。

Bob 认为 Alice 可以在硬币上做手脚。

形式化的描述：若双方互不信任，无法制备双方信任的随机数生成器。

因为你有一枚完美硬币对方也不承认。

这难不倒我们，Alice 可以从 0,1 中选一个数，写在小纸条上，Bob 猜小纸条上的数字即可。

Bob 认为 Alice 可以在小纸条上做手脚。

形式化的描述：不存在可靠第三方。

于是我们对问题做一个完整的描述：

设计一种游戏，使得双方获胜的概率均等，其中不存在可靠第三方，不存在随机因素。

博弈论：策梅洛定理 Zermelo’s theorem ：其表示在二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当中必有一方有必胜/必不败的策略。

简单证明：博弈树。

[证明过程]()如下，读者自证不难，故略过。（到时候会折叠起来下面一块）

为方便计，对游戏的所有可能状态（是指游戏进行到某一步时的局面，包括下一步轮到谁）染色，如果某一状态已经判定先手胜则该状态染黑，同理先手负则该状态染白。

如果某一状态是先手方行动且它的所有后继状态（即下一步的状态）都是白色，则这一状态染白。

——你的回合但当你所有可能的下一步都会走到必败情形时，你已经输了。

如果某一状态是先手方行动且存在它的某一个后继状态是黑色，则这一状态染黑。

——你的回合且当你有一种方法能走到必胜情形时，你已经赢了。

如果是后手方行动，同上。

当以上染色结束后，考虑哪些未被染色的状态。如果该状态是先手方行动，根据以上染色规则，因为该状态胜负未分，必存在后继状态，且不能有一个黑色，且不能都是白色。所以它的所有后继状态中必存在一个未染色的状态。先手为了不输，故会选择从一个未染色状态转移到另一个未染色状态。对于后手同理。

所以，初始状态要么染黑要么染白，若未染色，则先后手都会选择从一个未染色状态转移到另一个未染色状态，从而在未染色状态之间循环直到有限步内结束。

总结一下：

1. 没有平局，每个游戏局面要么是必胜态，要么是必败态；
2. 一个状态是必败态，当且仅当它的所有后继状态都是必胜态；
3. 一个状态是必胜态，当且仅当它的后继状态存在一个必败态。

必胜策略的核心本质是：理清必胜态和必败态，并构造必胜态与必败态之间的状态转移。

博弈论宣判了 Coin Flip 的理论无解。但是我们可以试图找出一种折中的方法。

我们注意到，引入硬币(或者小纸条)主要是利用了以下的性质：

Bob 无法在 Alice 抛硬币前（或者打开纸条前）获取关于硬币朝向（或者纸条上数字）的任何信息。

同时，如果 Bob 能承认硬币朝向（或者纸条上数字）不受 Alice 的干扰，那么上两个算法就是有效的。

形式化的，如果能找到一个东西满足以下两个性质，那么问题就大功告成了。

防篡改性：Bob 可以通过 Alice 给出的信息判断 Alice 有没要造假。

低（零）信息性：Bob 几乎无法或不能通过 Alice 给出的信息判断 Alice 的决策。

隆重介绍，单向双射函数模型：

已知映射 f:D\rightarrow V 是一个双射（人话：\forall x \in D ,f^{-1}(f(x))=x ，即二者唯一对应）。其特点为 x \rightarrow f(x) 非常容易求得，而 f(x) \rightarrow x 则极难求得（但不是无法求得）。

如果存在这样一种单向双射 f，可以设计如下 Coin Flip 算法：

• Alice 和 Bob 约定一种单向双射 f。

• Alice 在 1∼n 中选择一个数 x，计算 y=f(x)，并公开展示 y。

• Alice 在 1∼n 中选择一个数 x_0，Bob 猜测 x 是否大于 x_0。（此时 Bob 知道 y，但他很难根据 y 来计算 x）

• Alice 公开展示 x，如果 Bob 猜错了，他买单。（Bob 可以根据 f(x)=y 来验证 Alice 没有偷换 x）

在此，Bob 无法通过 y 获得任何关于 x 的信息（或者说计算量不可承受），此时不存在比随机猜测更好的策略。

这么好的东西要怎么找呢？当然是从数论里面找！

接下来花一点时间引入一个单向双射函数模型：

定义对整数的取模运算 \bmod p 的含义是将其除以 p 以后的余数。在集合 \{0,1,2,\cdots,p-1\} 中，任意两个元素相加或相乘，其结果 \bmod p 仍然在集合中，这个叫封闭性，加法与乘法具有交换性，这样就具有非常良好的代数性质。

更通俗的，让我们以 p=7 举例子。想象一个摩天轮，位置分别编号为 0 到 6，那么做加法，就是在摩天轮上转圈圈，加几就转动了几个位置。例如 0+3=3,1+6=0，可以看个动画演示一下。做乘法，就是摩天轮一直以一个速度在转，转了几分钟后，第零号车厢所在的位置。例如摩天轮以5个位置每分钟的速度顺时针旋转，则 0 号位置六分钟以后所在的位置就是 2，5\times6=0+5\times 6=0+7*4+2=2，这也有个动画。

为了方便讨论，如果式子需要对 p 取模，我就会说是模 p 意义下的。

如果恰当选取一个极大的质数 p，并选取 p 一个原根 g（你不需要知道什么是原根）。

那么 f(x)=g^x (\bmod p),x \in \{1,2,\cdots,p−1\}是一个单向双射函数，证明从略，见延伸阅读。

已知 f(x) 和 g 求解 x 叫“离散对数问题”，与已知g,x求f(x)计算量相差几个数量级。

如果你听不懂也没关系，但你需要理解的：一种从 “1到p-1” 到 “1到p-1”的映射方法，并且正着算容易反着算难。

有同学想到了什么吗。

如果有同学对高考比较关注的话，就会知道这是去年九省联考的压轴题，其中第三问这货我们待会还会见到他。

回到原问题，我们可以设计如下算法：

• Alice 和 Bob 约定一个大素数 p，原根 g。

• Alice 在 1∼p-2中选择一个数 x，计算 y=f(x)，并公开展示 y。

• Alice 在 1∼p-2 中选择一个数 x_0，Bob 猜测 x 是否大于 x_0。（此时 Bob 知道 y，但他很难根据 y 来计算 x）

• Alice 公开展示 x，如果 Bob 猜错了，他买单。（Bob 可以根据 f(x)=y 来验证 Alice 没有偷换 x）

Encrypted Communication Problem

互动环节从略。

自习课，Bob 想向女神 Alice 传递一个自然数 520，但是二人相距若干个座位，只能通过传纸条的方式传数字，这样数字有可能被其他人看到，所以 Bob 向你求助如何设计一种方法使得传递的消息只可能让 Alice 知道。

注意 Alice 和 Bob 不能走到教室外面说悄悄话。

形式化的，