现代密码学初步

硬币掷出之后，正逆的转换从未停止。

Coin Flip Algorithm

密码学，是一个死板且迷惑的学问，密码学家大多不受人理解，超脱俗世之外。研究生活中大家都理解的事物，质疑现实里大家都公认的条理。

，生活中最为常见的随机决定性质事件（~~虽然感觉现在没多少人会甩硬币了~~），这个随机系统快捷，方便，最重要的是，大家都公认了其公正性，没有人会质疑这个硬币的概率生成，的概率生成。

但显然，有人会质疑，这就是密码学家的工作。

博弈与悖论

打比你和朋友一起吃饭，现在决定谁请客，那么你拿出了这枚硬币，然后抛出，大家都会认为这枚硬币是的概率。但显然，如果这个时候你的朋友运气并不是很好，那么他可能会感性用事，于是就出现了的第一条悖理。

若双方互不信任，无法制备被两人公认的随机数生成器

显然，作为一个聪明的或者数学家，你能够用理科思维打败他，比如说，我们先抛个次，然后近似证明这枚硬币是的（~~虽然这个好像是生物学的统计方法~~），或者我们用三维建模模拟硬币的抛出下落，然后循环往复个次，用数学归纳法再证一证。

这个时候你的朋友可能就哑口无言了，那如果他还想反驳，他也许会提出：那如果这个硬币富有魔法，在一切实验性场合时表现正常，但是在正式性场合时则会受到抛出人思维控制，这个结论又该如何证明呢？

~~证明你个头啊，~~显然这个问题是无解的，在当今人类的科技树上并不存在魔法这一选项，所以显然，在这种情况下，已经失效了，这个博弈不会再作为此次赌注的一环。

但你怎么能服输呢，于是你选择了一种可能会比麻烦一点，但是满足上述要求的博弈。

现在我手中有一张白纸，我会在这张白纸上写下一个整数（保证一定是整数），现在我将白纸倒扣在桌子上，你没有任何机会看到这张白纸，但你可以监督我不会对这张白纸再做任意修改。
现在你猜测这个数是奇数还是偶数，如果猜错了，那么你就买单。

这个看样子也太正确了，直接规避掉了有关随机的性质，去除了随机数的生成。并且使用信息论的证明，你的朋友不存在比随机猜测更好的策略（~~我们假设你的朋友没有透视眼或者读心术之类的超能力，也就是他不具备任何信息~~）。

那这就是我们寻找的完美的吗？怎么可能！你连硬币都优化掉了还能叫？引入了第三种介质，这里我们姑且称之为「白纸」，这是一个稳定介质，能够存储我们需要的信息（写下的数字）且为只读模式（不可被修改）。

不不不，你的朋友又开始耍花招了，他提出了新的要求：

双方互不信任，且不存在一个双方都信任的第三方

这怎么行呢，~~这种时候多半就直接甩手走人了。~~现实中当然不存在这么让人讨厌的情况存在，而密码学就是为了摆脱烦恼而存在的。

密码学建立在「质疑」的基础之上，不吝以最大的恶意去揣度每一个人。这就能达到密码学的最初目的，让最坏且最聪明的人都无机可乘，乖乖就范，没有捣乱的空间，这样才能让每一场游戏都安心。

所以我们的研究，就是一步一步将所有有利的条件全部禁止，然后找到最原初最本质的解决方案。

所以，上面引入介质（第三方）的方法显得太过于简单了，就比如我们直接找到某一方的家长，然后让他来操作整个游戏流程，因为家长是大家都信任的第三方。

尝试与解决

然后你发现这是一个死局。

不能用硬币，因为没有办法满足「方案中不能含有公认随机部分」；不能用纸条，因为不能满足「只有公开的信息才能被公认」；不能使用介质。

事实上，根据博弈论（）的引理，任何一种方案都可以被抽象为一种组合游戏，所以必定存在先后手的必胜策略。所以不存在公平法则。

所以，从理论数学的角度来看，已经被判定了死刑。但显然，那只是理论数学。

从密码学的角度上看，我们只需要解决一个问题，如果必须存在必胜策略，但那要求两个波特面对面交互上万年的话，这个必胜策略是不是可以近似于没有呢？所以，当我们制定的必胜策略超出了博弈双方的计算能力，那这就是公平的。

单向双射

定义一个函数，其定义域为，保证如果，那么一定。所以实际上，是一组映射，而也是一组映射。

这里，我们额外添加一个条件：已知求是一个极为简单的部分，但通过计算是极其困难的（这里我们近似认为不可能）。

于是，我们设计出了基于单向双射的：

约定一种单向双射函数，此时的计算方式双方已知且信任；
在中选择一个数（并不知道的具体数值），并计算，公开展示（此时仅知道）
将猜测的值（判断奇偶性，的公平概率）。
将公开并得到游戏结果。（此时可以通过验证数值是否被偷换）

这里我们尽可能将设计得更加复杂，以至于最天才的数学家也无法在一个极短的时间内通过计算出。那么这个游戏对于而言，她（这里用代替）无法预知的猜测，因为无法通过任何情况得知有关的任何信息，所以对于他（这里的代替）而言，他的最优策略就是随便猜。

而此时起到了「签名」作用，保证了不存在作假的情况（当然如果足够蠢使得这个本身并不单向双射那不做考虑）。所以，这就是一个完全公平的。

所以，上述过程是在计算数学的领域下得到的结果，如果有人想要在理论数学中计算那纯属扯皮，这也是理论可行（一份完全无损的方案）与计算可行（一份在平常情况下能够实施的方案）的区别。

那么让计算可行无限接近于理论可行的方法，就是把这个趋近到很大，使得足够大。并让复杂到通过求仅有的方法是枚举。这样下来，显然只有当是波特的时候才会出现作弊。

这里给出两个例子：

基于离散对数

选择一个质数以及其原根，公开展示；
在中任意指定数，公开展示；
在中选择数，公开展示。
将判断的大小关系，然后公开展示，并得到游戏结果。

基于质因数分解

选择质数满足，并公开展示；
选择任意整数，公开展示或者。
将猜测公示的是还是；
公开，并得到游戏结果。

经过数学界证明，如果真的靠后者得到了前者，那他可以大吃一顿之后去领图灵奖。

加密通信 Encrypted Communication

加密通信属于通信问题的一种，一般而言，用于互相信任的双方在保证不会对被怀疑的第三方获取任何正确信息的通信方式。是间谍工作最简单的一环。

举一个例子，希望知晓一个数，那么她在公开是进行一系列加密，使得所有得到公开信息的人中，得到的是，而其他人得到的是，其中。

这个情况在现实中基本得到完全解决，在谍报工作中，传递信息的双方会在事先约定一套完整的加密与解密方案，所以这样使得所有公开的信息都是已加密信息，而接受信息的一方可以轻松通过解密方案实现正确信息的获取。而任何不知道解密方案的第三方都无法实现解密，也就无法获取正确信息。

于是我们要提高难度，设想下面的场景：此时三人具有共同初始认知（即不存在任何信息使得某些人知道而另一些人不知道）。与 互相信任且想要交换一些信息，他们需要保证不能知道这些信息。

这就是加密通信的假设。

Diffie-Hellman Algorithm

从信息论的角度而言，此时与不具有额外共识，简单来说，对于这场信息交换，处于同一条起跑线。而加密通信的解决，正是共识的无中生有，目标就是在间产生一个新的共识。

从信息论角度上，这个角度无解，因为初始共识相同，地位等价。

然后你发现基本上密码学都基于一些数学界中无解或难解的问题。于是和在基于离散对数提出了加密通信的解决方案。

由或公开一个质数和其原根。（此时对于是已知的）
想一个数，不公开；想一个数，不公开。
公开，公开（这里我们假设不是，无法推算）
推算，推算，二人得到共识。
通过对通信进行加密与解密，此时获得的是没有的错误信息。

感觉很熟悉？因为有一道的题目背景就来源与协议：破解协议。所以别指望你那 long long 或者 __int128_t 能够做到多么安全的加密系统，别人的破解说不定就是一杯茶的时间。

加密系统的建立

设为加密函数（其中为正确信息），为解密函数，保证。此时接收方已经知晓的计算方式，那么公开。就可以通过计算出，而其他人不行。

那么，在上述情况下，我们设，那么，这就是一套合法的加密系统，其中被称为密钥。但显然看起来过于简陋了，所以并不安全。

RSA Algorithm

全称，由，，三人在年提出的防御明文攻击的算法。

明文攻击

对于交换信息的双方而言，他们正在进行加密通信，但第三方通过一系列手段获取了通信中一部分明文（破译之后的正确信息），在加密方式简单的情况下，可以通过部分明文破译出加密方案从而通过所有公开信息计算出所有正确信息。

此上为明文攻击。是密码学中一种牵一发而动全身的手段，一旦出现则损失巨大。

而就是用来防御明文攻击的算法。

防御明文攻击

依然基于质因数分解和离散对数的难解性，我们提出了以下方案：

首先指定两个不同的质数，计算，公开；
计算。
选择一个数，并满足，公开；
计算，即模的逆元。

此时获得公钥，以及私钥。

你说可以通过计算出？异想天开。如果上百位，那么质因数分解是级别的。算到太阳爆炸都算不完。

那么此时双方拥有私钥，而所有人都知道公钥。那么信息交换形式就会变成下面的样子，我们这里假设需要交换的信息是一个整数：

计算，公开展示。
接受，并通过欧拉定理计算出。

当然，想要通过计算基本也是不可能的，我想可能也不行。

需要注意的是，这里的必须是的整数，但显然在日常中足够大也不会存在超越限制的情况。但如果有的情况，第一可以分割信息传递，第二可以通过等对称性加密算法的密钥加密信息，再用的公钥加密的密钥。

Secure Multi-party Computation

（）指的是多方安全计算，一般而言是双方，简称为。

2PC：Millionaires’ Problem

设有元钱，有元钱，保证，他们想知道谁更有钱，但又不想告诉对方具体钱数。