密码学社课

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

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

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

Intro

一些约定：

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

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

密码学初印象：

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

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

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

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

Coin Flip Problem

Coin Flip 问题：

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

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

双方都认为对方会晚出。

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

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

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

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

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

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

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

简单证明：博弈树。

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

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

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

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

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

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

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

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

总结一下：

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

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

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

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

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

• 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$）

定义对整数的取模运算 $\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

形式化的，