Question

传送秘密

秘密：一件事情，只有我知，外人不知。

如何在众目睽睽下传送秘密呢？

这裡提供两个策略：掩、饰。

第一个策略是遮掩资料、包装资料，导致外人看不见。比如寄信，我们使用信封，让外人无法偷看资料。要验证外人是否偷看资料，可以使用易碎胶带；要阻止外人偷看资料，可以使用保险箱。

第一个策略在电脑世界行不通。资料在网路线中、空气中传送，包装薄弱。只需接线、接收，有心人皆可直接取得资料。

第二个策略是修饰资料、加工资料，导致外人看不懂。比如行话，我们去到夜店说要冰块和盐，只有熟人才能理解话中有话。

第二个策略在电脑世界行得通。资料套用四则运算，就变得完全令人看不懂。套用反运算，就看得懂了。比如说字母从零开始编号，每个字母乘三加三模二十六，然后字串头尾对调。

想要实行第二个策略，当事人必须先有共识，你知我知、外人不知；否则外人也能看懂你我传送的秘密了。比如“从零开始编号……头尾对调”就是共识。又比如我和你当众说“老地方见”，外人听了不知道是哪裡，但是你我早知道老地方是哪裡。外人一旦知道老地方是指什麽，外人就知道你我的行踪了。

也就是说：你我必须先有共同秘密，才能传送秘密！鸡生蛋蛋生鸡，总得起个头。两种解法：一、你我事先私下见面，约定第一个共同祕密。二、你我当众揣摩彼此、塑造共识，形成第一个共同秘密。

你我拥有第一个共同秘密之后，即可利用递推法，传送更多秘密。比如过几天我又和你说“上次隔壁那一家，东西也很棒，待会一起去。”你我分享了更多秘密，但是外人仍旧雾裡看花。

一件事情通常有各式各样的解读方式，理论上外人永远无法正确解读秘密。但是当传送秘密越来越多，则解读方式就越来越少。安全起见，三不五时就要更换第一个共同秘密。

A1 与 A2 事先见面。
A1: 我跟你说，当我说“跑”，我们就逃跑。
A2: 好。

B1 与 B2 事先见面。
B1: 我跟你说，当我说“跑”，我们就往前衝。
B2: 好。

后来 A1A2B1B2 通通上战场，
C 听到他们说跑，但是不知道他们打算逃跑还是往前衝。

Encrypt / Decrypt

“加密”是改变资料外观。“解密”是回复原本外观。

资料加密之前叫做“明文 plaintext”，加密之后叫做“密文 ciphertext”。“加密”是明文变密文，“解密”是密文变明文。

encrypt
Thank you! --------> 3Q!
           <-------- decrypt="" encrypt="" fibonacci="" sequence="" --------=""> 13-3-2-31-1-1-8-5
                   <-------- decrypt="" <="" pre="">

UVa 425 11220 11385

Attack（Crack）（Cryptanalysis）

“攻击”、“破解”、“密文分析”就是给定密文，找出明文，在不知道加密解密方式的情况下。

[ciphertext]
O, Draconian devil! Oh, lame saint. P.S. Find Robert Langdon.

please find plaintext.

即便外人不知道加密解密方式，外人还是可以用试误法，穷举各种加密解密可能性，一一尝试解密，总有一种会成功。即便密文有很多种解读方式，外人仍然可以大概猜出个端倪。

UVa 795 828 11697

加密解密基本原理：Substitution 与 Transposition

现今的加密演算法，通通都是换字面（Substitution）、换位置（Transposition）。这是最符合电脑运作特性的方式。

你我事先见面约定换字面、换位置的表格，不让外人知道；如此一来，只有你我可以加密解密。

设计表格时，要注意密文是否可以正确还原成明文。用数学的术语来说就是：表格必须是一对一函数、必须拥有反函数。

DES Encryption

Caesar Cipher

罗马帝国时期的演算法。原理是换字面。

加密：明文每个字元加三成为密文。解密：密文每个字元减三成为明文。三是事先约定的秘密，可以改成任意数。

引入密钥的观念，事先约定的秘密只需要一个数字，不需要加密解密方式。加密解密方式可以公诸于世；只要密钥没有公诸于世，外人就无法解密。

大小写、空白键、标点符号等细节，请自行制定规则。

Diffie-Hellman Key Exchange

Diffie-Hellman Key Exchange

本单元的先备知识是“ Residue ”！

先前介绍的演算法，你我必须事先私下见面约定秘密数值。然而在电脑世界当中，你我无法事先私下见面。于是有人想出在公开场合建立秘密数值的演算法。因为非常简洁好用，似乎也没人去设计其他演算法了。

(g^a)^b ≡ (g^b)^a (mod p)

一、甲乙公开协议一个质数 p。p 做为模数。
　　甲乙公开协议一个数字 g。
二、甲心中随便想一个数字 a。
　　乙心中随便想一个数字 b。
三、甲计算 g^a，传送给乙，乙获得 g^a。
　　乙计算 g^b，传送给甲，甲获得 g^b。
四、甲计算(g^b)^a，乙计算(g^a)^b，
　　两人求得共同秘密(g^a)^b。

外人只知道 g、g^a、g^b、p，外人无法快速计算(g^a)^b。
想破解，必须求得 a，必须计算 log(g^a) 求得 a。（或者是 b）
然而 log 得花很多时间！

遗珠之憾是不能控制共同秘密为何。

当数字很小，馀数次方的时间複杂度为 O(logN)，建立速度极快；馀数对数的时间複杂度为 O(sqrtN)，破解速度也极快。

当数字够大，馀数对数演算法的记忆体便不敷使用，必须改用试误法，时间大幅成长为 O(N)！利用馀数次方与馀数对数的时间差，让外人一时无法破解；当外人破解时，秘密早就传送完毕了！

然而外人只要肯花时间，总有一天还是能破解秘密。实务上的应对方式是资料分段加密、资料分流传送，让外人永远无法追上最新进度，让外人无法获得资料全貌。

馀数系统改成 Finite Field、改成 Elliptic Curve

此处的馀数系统，基本单元是整数。我们可以进一步把整数改成馀数多项式、改成椭圆曲线格点，让对数更难计算、计算更久。

以 Diffie-Hellman Key Exchange 得到的共同秘密来加密解密

所有的加密演算法，例如 Caesar Cipher、ENIGMA、Feistel Cipher、DES，全部都可以透过 Diffie-Hellman Key Exchange 获得共同秘密。

壹、Diffie-Hellman Key Exchange：
　一、甲乙公开协议一个质数 p。p 做为模数。
　　　甲乙公开协议一个数字 g。
　二、甲心中随便想一个数字 a。
　　　乙心中随便想一个数字 b。
　三、甲计算 g^a，传送给乙，乙获得 g^a。
　　　乙计算 g^b，传送给甲，甲获得 g^b。
　四、甲计算(g^b)^a，求得共同秘密(g^a)^b = s。
　　　乙计算(g^a)^b，求得共同秘密(g^a)^b = s。
贰、任意一个加密演算法：
　一、甲利用 s 加密。
　二、乙利用 s 解密。

接收窗口

进一步仔细调整步骤顺序，引入接收窗口的观念。

壹、乙建立接收窗口：
　一、甲乙公开协议一个质数 p。p 做为模数。 （乙公佈一个质数 p）
　　　甲乙公开协议一个数字 g。　　　　　　（乙公佈一个数字 g）
　二、乙心中随便想一个数字 b。　　　　　　（乙心中随便想一个数字 b）
　　　乙计算 g^b，传送给甲，甲获得 g^b。　 （乙公佈 g^b）
贰、甲加密：
　一、甲心中随便想一个数字 a。
　　　甲计算 g^a，传送给乙，乙获得 g^a。
　二、甲计算(g^b)^a，求得共同秘密(g^b)^a = s。
　三、甲利用 s 加密。
参、乙解密：
　一、乙计算(g^a)^b，求得共同秘密(g^a)^b = s。
　二、乙利用 s 解密。

甲每次加密都可以重新想一个数字 a，密文更不容易破解；乙每次解密都可以用同一个数字 b，密文更容易接收。

人人都知道 g^b，人人都可以利用 g^b 传送秘密给乙，人人都无法窥伺彼此秘密！

机制类似联络地址、联络电话。乙提供服务专线 0800-092-000，人人皆可拨打专线联络乙，人人皆无法获知其他人的电话内容！

根据上个段落、这个段落，传输秘密现在有了两种模式：一到一、多到一。

另外还可以引入分发窗口的概念。由于不实用，大家不讨论。

RSA Encryption

加密演算法：馀数加法

馀数加法有著换字面的功效。对象是小写英文字母，模数设定成 26。对象是位元组，模数设定成 2^8 = 256。

设定模数为 26

[+1 table]       [+2 table]       [+3 table]
0 1 2 3 ... 25   0 1 2 3 ... 25   0 1 2 3 ... 25
1 2 3 4 ...  0   2 3 4 5 ... 1    3 4 5 6 ...  2

Caesar Cipher

馀数加法。报告完毕。

加密演算法：馀数乘法

馀数乘法有著换字面的功效。乘法是加法来的。

模数最好设定为质数，让各种乘数的表格，都是一对一函数，比较好处理。模数不见得要刚好是 26、256，可以设定成更大的模数，尤其是质数；表格过大，仍可运作，密文比明文长罢了。

设定模数为 37

[×1 table]       [×2 table]       [×3 table]
0 1 2 3 ... 36   0 1 2 3 ... 36   0 1 2 3 ... 36
0 1 2 3 ... 36   0 2 4 6 ... 35   0 3 6 9 ... 34

我们可以利用馀数乘法、馀数乘法反运算（馀数除法），一乘一除相互抵销，设计一个超级简单的加密演算法：

加密：明文乘以 a 成为密文。解密：密文乘以 a 的倒数成为明文（密文除以 a 成为明文）。a 是事先约定的秘密。

一、甲乙事先私下约定一个质数 p。p 做为模数。p 也是区块长度。
　　甲乙事先私下约定一个数字 a。
二、甲加密：
　　甲有明文 m。甲计算 m×a，传送给乙，乙获得 m×a。
三、乙解密：
　　乙获得密文 m×a。
　　乙计算 a 的倒数a。
　　乙计算(m×a)×a，乙求得明文 m。
　（乙计算(m×a)÷a。）

ElGamal Encryption

传输模式是多到一、加密演算法是馀数乘法。

加密演算法：馀数次方

馀数次方有著换字面的功效。次方是乘法来的。

我们可以利用馀数次方、馀数次方反运算（馀数根号），次方根号相互抵消，设计一个超级简单的加密演算法。然而馀数次方反运算（馀数根号）要算很久。由于已经知道次方数值，所以可以直接求次方数值的倒数，避开馀数根号。

馀数乘法版本：
m×1 ≡ m (mod n)
m×(a×a) ≡ m (mod n)   // a×a ≡ 1 (mod n)
(m×a)×a ≡ m (mod n)

馀数次方版本：
m^1 ≡ m (mod n)
m^(a×a) ≡ m (mod n)   // a×a ≡ 1 (mod φ(n))
(m^a)^a ≡ m (mod n)

加密：明文的 a 次方成为密文。解密：密文的 a 的倒数次方成为明文。a 是事先约定的秘密。

一、甲乙事先私下约定一个数字 p。p 做为模数。
　　甲乙事先私下约定一个数字 a。
二、甲加密：
　　甲有明文 m。甲计算 m^a，传送给乙，乙获得 m^a。
三、乙解密：
　　乙获得密文 m^a。
　　乙计算次方的模数φ(p) = p-1。
　　乙计算 a 的倒数a，模数是φ(p)。
　　乙计算(m^a)^a，乙求得明文 m。

RSA Encryption

传输模式是多到一、加密演算法是馀数次方。

壹、乙建立接收窗口：
　一、乙公佈一个质数 p。p 做为模数。
　　　乙公佈一个数字 g。
　二、乙心中随便想一个数字 b。
　　　乙公佈 g^b。
贰、甲加密：
　一、甲心中随便想一个数字 a。
　　　甲计算 g^a，传送给乙，乙获得 g^a。
　二、甲计算(g^b)^a，求得共同秘密(g^a)^b = s。
　三、甲有明文 m，甲计算 m^s，传送给乙，乙获得 m^s。
参、乙解密：
　一、乙计算(g^a)^b，求得共同秘密(g^a)^b = s。
　二、乙获得密文 m^s。
　　　乙计算次方的模数φ(p) = p-1。
　　　乙计算 s 的倒数s，模数是φ(p)。
　　　乙计算(m^s)^s，乙求得明文 m。

儘管可以运作，但是一堆次方，看了就烦，乾脆简化。

壹、乙建立接收窗口：
　　乙公佈一个质数 p。p 做为模数。
　　乙公佈一个数字 a。
贰、甲加密：
　　甲有明文 m。甲计算 m^a，传送给乙，乙获得 m^a。
参、乙解密：
　　乙获得密文 m^a。
　　乙计算次方的模数φ(p) = p-1。
　　乙计算 a 的倒数a，模数是φ(p)。
　　乙计算(m^a)^a，乙求得明文 m。

然而外人知道 m^a、a、n、p，
可以计算φ(p) = p-1，
然后计算a，
然后计算(m^a)^a，求得明文 m。

为了不让外人轻鬆计算 a 的倒数，把模数从一个质数改成两个质数相乘，而且不让外人知道是哪两个质数。

壹、乙建立接收窗口：
　一、乙心中随便想两个质数 p 与 q。
　　　乙计算 p×q = n，n 做为模数。
　二、乙公佈 n。
　三、乙公佈一个数字 a。
贰、甲加密：
　　甲有明文 m。甲计算 m^a，传送给乙，乙获得 m^a。
参、乙解密：
　　乙获得密文 m^a。
　　乙计算次方的模数φ(n) = φ(p×q) = (p-1)×(q-1)。
　　乙计算 a 的倒数a，模数是φ(n)。
　　乙计算(m^a)^a，乙求得明文 m。

外人只知道 m^a、a、n，外人无法快速计算(m^a)^a。
一、想破解，必须得到 m，必须计算a√m^a得到 m。
　　然而开 a 次根号得花很多时间！
二、想破解，另一种方式是求得a。
　　必须计算 a 的倒数才能求得a，所以必须求得模数φ(n)。
　　必须计算(p-1)×(q-1) 才能求得φ(n)，所以必须求得 p 与 q。
　　必须计算 n 是哪两个数相乘才能求得 p 与 q。
　　然而质因数分解得花很多时间！

馀数倒数、馀数次方，远小于馀数根号、整数分解的时间複杂度。原理如同 Diffie-Hellman Key Exchange，利用时间差，让外人一时无法破解。

最后，把计算倒数的步骤往前挪，预先计算，不必每次重算。

壹、乙建立接收窗口：
　一、乙心中随便想两个质数 p 与 q。
　　　乙计算 p×q = n，n 做为模数。
　二、乙公佈 n。
　三、乙公佈一个数字 a。
　四、乙计算次方的模数φ(n) = φ(p×q) = (p-1)×(q-1)。
　　　乙计算 a 的倒数a，模数是φ(n)。
贰、甲加密：
　　甲有明文 m。甲计算 m^a，传送给乙。
参、乙解密：
　　乙获得密文 m^a。乙计算(m^a)^a，乙求得明文 m。

读者可以想一想：

一、乙可以只记a与 n，不记 p q a φ(n)。为什麽可以呢？

二、如果 p 和 q 其中一个很小，有什麽问题呢？

三、如果由甲来公佈 n 与 a，再由甲传送秘密给乙，有什麽问题呢？

最后讲个八卦。这三位作者跑去申请专利；然后开了一间名叫 RSA 的公司，变成该领域的业界龙头；然后提倡大家都使用此演算法；然后藉势得了图灵奖；然后公司被美国政府买通，在演算法裡面藏后门，让美国政府可以破解秘密，监听全世界的秘密讯息。

ICPC 4353

RSA Signature Algorithm（RSA Asymmetric Encryption）

传输模式是一到多、加密演算法是馀数次方。

壹、甲建立分发窗口：
　一、甲心中随便想两个质数 p 与 q。
　　　甲计算 p×q = n，n 做为模数。
　二、甲公佈 n。
　三、甲心中随便想一个数字 a。
　　　甲计算 a 的倒数a，模数是φ(n)。
　四、甲公佈a。（亦得改为公佈 a）
贰、甲加密：
　　甲有明文 m。甲计算 m^a，传送给乙，乙获得 m^a。
参、乙解密：
　　乙获得密文 m^a。乙计算(m^a)^a，乙求得明文 m。

甲公佈 n 与a，再由甲传送秘密给大家，大家都可以解密。基本上没有任何加密效果。非常蠢。

然而此演算法有一个非常重要的特色：只有甲能加密！

此特色称作“非对称式加密 asymmetric encryption”。资讯不对称，甲知道的比乙多，甲有独门绝技！这个特性可以运用于稍后提到的 Digest 和 Signature。

加密演算法：馀数乘法

顺带一提，馀数乘法其实也有著换位置的功效。一种乘数，就是一种重新排列。模数则是区块长度。

设定模数为 7

[×1 table]        [×2 table]        [×3 table]
0 1 2 3 4 5 6     0 1 2 3 4 5 6     0 1 2 3 4 5 6
0 1 2 3 4 5 6     0 2 4 6 1 3 5     0 3 6 2 5 1 4

[×4 table]        [×5 table]        [×6 table]
0 1 2 3 4 5 6     0 1 2 3 4 5 6     0 1 2 3 4 5 6
0 4 1 5 2 6 3     0 4 1 5 2 6 3     0 4 1 5 2 6 3

模数设定为质数，比较好处理。但是区块长度是质数，而不是 32、64，挺彆扭。馀数系统可改成 Finite Field、改成 Elliptic Curve。如此一来，模数不必是质数，可以改成 32、64。

Man-in-the-middle Attack

Man-in-the-middle Attack

“中间人攻击”。传送秘密时，他人佯装接收对象。得进一步推广为双向版本，他人两面讨好、居中斡旋。

劳保黄牛、信用卡客服诈骗、社交工程等等都是中间人攻击。

中间人攻击的精髓：接洽对象全是坏人。假的检察官、假的行员、假的电话号码、假的法规。极端案例是《楚门的世界》。

中间人攻击是必胜攻击手法，所有的加密演算法一律失效！

一种破解方式是确认对象身分。不幸的是，电脑世界当中，讯息在网路上传输，可以随时拦截；而且无法见到对方。

一种破解方式是测量沟通时间。不幸的是，电脑世界当中，讯息在电脑中处理，计算速度飞快，难以察觉差异。

最后大家只好依赖“认证”。

Certification

“认证”。传送秘密前，预先谘询他人，确认接收对象的身分；或者请对方出具他人颁发的良民证。得进一步推广为双向版本，他人列席旁听、居中调解。

见证人、律师、身分证、识别证、印鑑证明等等都是认证。

认证的精髓：接洽对象全是好人。由第三方公正人士亲自验明正身，颁发证书，昭告天下。极端案例是“好人好事代表”。

“中间人攻击”和“认证”皆运用了第三者的概念，本质相同、却又相对，正所谓阴阳相生相剋。第三者可以为善、可以为恶。

Digest

Integrity

一份资料，资料内容为真，未经他人窜改造假。

如何确认资料未经窜改？

Digest 私藏版本

“摘要”。增加检查项目，确认是否相符，避免窜改造假。

首先利用编码演算法制作摘要！

避免他人只窜改本文、只窜改摘要：相同本文得到相同摘要，不同本文得到不同摘要；从本文到摘要是一对一函数。

壹、制作摘要：
　一、甲心中随便想一个编码演算法。
　二、甲编码本文，得到摘要。
贰、检查摘要：
　一、甲编码本文，得到新摘要。
　二、甲比对旧摘要、新摘要。
　　　若一致，本文未窜改。
　　　若不一致，本文已窜改。

接著利用加密演算法掩饰摘要！

避免他人同时窜改本文和摘要：加密本文、或者加密摘要、或者两者皆加密。一般仅加密摘要，节省时间。

壹、制作摘要：
　一、甲心中随便想一个编码演算法。
　二、甲编码本文，得到摘要。
　三、甲心中随便想一个加密演算法。（以及密钥）
　四、甲加密摘要，得到摘要密文。
贰、检查摘要：
　一、甲编码本文，得到新摘要。
　二、甲加密新摘要，得到新摘要密文。
　三、甲比对旧摘要密文、新摘要密文。
　　　若一致，本文未窜改。
　　　若不一致，本文已窜改。

第二三步可以改成：甲解密旧摘要密文，然后改为比对旧摘要、新摘要。

此方式仅适用单人。一旦他人知道密钥，那麽他人就可以解密、窜改、重新加密，令伪本文、伪摘要两相符合。

Digest 公开版本

继续利用非对称式加密来制作摘要！

避免他人只窜改本文、只窜改摘要：只允许本人制作摘要！如此一来，他人擅自改动本文，也无法重制摘要；他人擅自改动摘要，也无法与本文的编码结果相符。

一种实践方式是非对称式加密：只有本人知道如何加密，他人不知道如何加密。经典演算法是 RSA Signature Algorithm、Digital Signature Algorithm，此处省略。

壹、制作摘要：
　一、甲公佈一个编码演算法。
　二、甲编码本文，得到摘要。
　三、甲公佈一个非对称式加密演算法。（只有甲知道如何加密，他人不知。）
　四、甲加密摘要，得到摘要密文。
　五、本文、摘要密文一併传送给他人。
贰、检查摘要：
　一、他人编码本文，得到摘要。
　二、他人解密摘要密文，得到摘要。
　三、他人比对两份摘要。
　　　若一致，本文未窜改。
　　　若不一致，本文已窜改。

接著利用公证人来担保摘要！

避免他人同时窜改本文和摘要：找公证人登记摘要密文，先登记先赢。再由公证人宣布解密方式。

壹、制作摘要：
　一、甲公佈一个编码演算法。
　二、甲编码本文，得到摘要。
　三、甲心想一个非对称式加密演算法。（只有甲知道如何加密，他人不知。）
　四、甲加密摘要，得到摘要密文。
　五、甲洽询公证人，登记㊣摘要密文、㊣解密方式。
　六、本文、摘要密文一併传送给他人。
贰、检查摘要：
　一、他人编码本文，得到摘要。
　二、他人洽询公证人，搜寻摘要密文，得到㊣解密方式。
　三、他人解密摘要密文，得到摘要。
　四、他人比对两份摘要。
　　　若一致，本文未窜改。
　　　若不一致，本文已窜改。

不幸的是，如果公证人变成海边的消波块、路上的沥青，就无法确认本文是否被窜改了。

因而又衍生许多攻防技术，例如台湾的白色恐怖时期、《进撃の巨人》的雷斯家族、《ONE PIECE》的历史本文。这已经超出加密演算法的范围，就此打住。

缩短摘要长度：One-way Hash Encryption

缩短摘要长度，可以节省时间与空间！

制作摘要理应使用一对一函数。摘要尽量短，又满足一对一函数，其极限是压缩演算法！如果摘要更短，便无法满足一对一函数，而形成多对一函数。有失有得。

制作摘要理应使用一对一函数，然而大家习惯採用多对一函数，例如 One-way Hash Encryption。

Signature

Authentication

一份资料，作者身分为真，未经他人冒名顶替。

如何确认资料是否为他人伪作？

Signature

“签名”。大家把签名与摘要混为一谈，沿用摘要的演算法。

Password

Confidentiality

一份资料，只给自己人知道，不给外人知道。

如何确认是自己人？

Password

“通行码”。中文习惯称作“密码”，翻译不太准确。

通行码的机制很简单。双方事先约定关键字，一方说出关键字，另一方验证关键字。例如《阿里巴巴和四十大盗》的芝麻开门、《魔戒》《指环王》的 mellon。

通行码通常不需要加密。大家习惯背记抄写明文、而非密文。

通行码通常需要保密。主要是为了避免他人冒用身分为非作歹。也可以不保密，与他人分享。

Password 保密版本

事先做最好的准备、最坏的打算。使用者必须防止外人得知通行码，管理者必须预设外人入侵伺服器、盗取通行码。

一、设计通行码。让通行码毫无规律、难以联想。例如不要使用生日。甚至以乱数演算法决定通行码。令外人难以猜中。

二、传送通行码。使用者加密通行码，传送密文，管理者解密通行码。令外人无法窥视。

三、保存通行码。管理者加密通行码，储存密文。只有管理者知道密钥。即便外人盗取通行码密文，也不知道如何解密。

四、验证通行码。甲、收到的通行码实施加密、伺服器的通行码密文，比对两者；乙、收到的通行码、伺服器的通行码密文实施解密，比对两者。大家倾向採用甲，只需加密，不需解密。令外人无法盗取解密程式、无法解密通行码密文。

保护通行码：One-way Hash Encryption

管理者储存通行码密文，理应使用一对一函数，然而大家习惯採用多对一函数，例如 One-way Hash Encryption。

一对一函数，不同的通行码，对应不同的通行码密文。优点是避免外人乱敲乱打通行码，碰巧通行码密文一样，导致验证通过。

多对一函数，有些不同的通行码，碰巧通行码密文一样。优点是即使外人窃取通行码密文，也无法从反向推导通行码，可能性太多。

Password v.s. Signature

通行码、签名，两者都是验证身分的机制。

通行码，传输模式是多到一，採对称式加密。

签名，传输模式是一到多，採非对称式加密。

两者都使用单向式加密来制造通行码密文、签名。

延伸阅读：One-time Password

https://en.wikipedia.org/wiki/Time-based_One-time_Password_Algorithm

One-way Hash Encryption

背景知识：One-to-One Function / Many-to-One Function

f(x) = y，相同的 x 对应相同的 y，不同的 x 对应不同的 y，这样的 f 称做“一对一函数”。

f(x) = y，相同的 x 对应相同的 y，有些不同的 x 对应相同的 y，这样的 f 称做“多对一函数”。

多对一函数的知名范例是整数乘法、整数分解（质因数分解）。

f(a,b) = ab = c
ab = 1×12 2×6 3×4 4×3 6×2 12×1 都得到 c = 12

多对一函数让人无法以输出判断输入。

通行码是 a 和 b，
管理者储存通行码，存为 a*b。
即便外人盗取 a*b，外人也难以猜出通行码。

背景知识：Hash Function

f(x) = y，自订 y 的范围大小，这样的 f 称做“杂凑函数”。

学过资料结构“ Hash Table ”的读者应该不陌生才对。

背景知识：One-way Function

f(x) = y，已知 x 欲求 y 很简单、算得快，已知 y 欲求 x 很困难、算得久，这样的 f 称做“单向函数”。

知名范例是整数乘法、整数分解（质因数分解）。

f(a,b) = ab = c
已知整数 a b 欲求整数 c，整数相乘。时间複杂度为一次乘法的时间。
已知整数 c 欲求整数 a b，整数分解。採用试除法，时间複杂度为 c 次除法的时间。

知名范例是次方、开根号。

f(a) = a^k = b   k 是常数
已知 a 欲求 b，次方运算。时间複杂度约是 logk 次乘法的时间。
已知 b 欲求 a，开根号运算。採用二分法，时间複杂度约是 logb*logk 次乘法的时间。

Encryption

“加密”。明文变成密文。

从一个东西变成另一个东西，概念等同于数学术语“函数”。我们可以把加密看作是一种特殊的函数。

“加密”。明文变成密文。

什麽是优秀的加密、差劲的加密呢？加密的关键究竟是什麽呢？

加密是避免外人从密文猜出明文，有时候也要避免外人看穿明文如何变成密文。从这个想法出发，可以发现加密的原理：

一、明文与密文相差极大。
二、明文稍微改动，密文剧烈变动。
三、密文稍微改动，明文剧烈变动。

One-way Encryption

“单向式加密”。

四、只有加密，没有解密。或者难以解密、解密代价极大。

注意到“单向式加密”和“非对称式加密”不一样！“非对称式加密”是一方知道如何加密与解密、另一方只知道如何解密。

One-way Hash Encryption

“单向杂凑加密”。用于缩短、固定密文长度。

五、限制函数输出范围。（间接导致一对一函数变成多对一函数。）

我们习惯把密文缩得很短，间接导致一对一函数变成多对一函数。其衍生的副作用：一、不同的明文得到一样的密文；二、外人难以从密文猜中原文。有失有得。

经典演算法是 MD5、SHA-3。此处省略。