Cryptology

因为密钥空间比较小，只有 26，可以使用暴力破解来破译这种密码.

使用频率分析的密码破译方法可以破解简单替换密码

将现实世界中的东西映射为比特序列的操作称为编码。例如，常见的字符编码有 ASCII UTF8 等编码

全称为 exclusive or,译作异或运算。
XOR 运算规则如下:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

将 0 理解为偶数，将 1 理解为奇数，就可以将 XOR 和一般的加法运算等同起来。
偶数 0 + 偶数 0 = 偶数 0
偶数 0 + 奇数 1 = 奇数 1
奇数 1 + 偶数 0 = 奇数 1
奇数 1 + 奇数 1 = 偶数 0

将一个棋子保持原状（不翻转）看做 0，将一个棋子翻转到另一面看做 1，那么 XOR 运算就相当于将黑白棋的一个棋子进行翻转的操作进行连接
不翻转 0 + 不翻转 0 = 不翻转 0
不翻转 0 + 翻转 1 = 翻转 0
翻转 1 + 不翻转 0 = 翻转 0
翻转 1 + 翻转 1 = 不翻转 0

DES 全称 Data Encryption Standard,1999 年 DES ChallengeIII 中用了 22 小时 15 分破解了 DES 加密的密文。目前已经不再使用该加密算法.
DES 是以 64 比特的明文为一个单位来进行加密的，这个 64 比特的单位称为分组。以分组为单位进行处理的密码算法称为分组密码。
DES 每次只能加密 64 比特的数据，如果要加密的明文比较长，就需要对 DES 加密进行迭代，而迭代的具体方式就称为模式。

在 Feistel 网络中，加密的各个步骤称为轮，整个加密过程就是进行若干次轮的循环。DES 是一种 16 轮循环的 Feistel 网络。

三重 DES 是为了增加 DES 的强度，将 DES 重复 3 次所得到的一种密码算法。

3DES 之所以设计为 加密->解密->加密 的过程是为了兼容普通的 DES。

3DES 目前还被银行等机构使用，但其处理速度不高。

AES (Advanced Encrytion Standard)是取代其前任标准 DES 而成为新标准的一种对称密码算法。

Rijndael 算法在 2000 年被选为新一代标准密码算法——AES。Rijndael 的分组长度为 128 比特，密钥长度可以以 32 比特为单位在 128 比特到 256 比特的范围内进行选择（在 AES 的规格中，密钥长度只有 128,193,256 比特三种）。
它也是由多个轮构成的，其使用了 SPN 结构。

相同的明文分组会被转换为相同的密文分组。

明文在加密之前回合前一个密文分组进行 XOR 运算，所以相同的明文分组对应的密文也不一样。
有一个密文分组损坏会影响该密文分组以及下一个密文分组的明文，但是下下的密文分组不会受到影响。

如果能够对初始化向量中的任意比特进行反转，则第一个明文分组中相应的比特也会被反转。

CBC 模式也可以被重放攻击

CFB 模式中，密码算法的输出相当于一次性密码本中的随机比特序列。密码算法就相当于用来生成密钥流的伪随机生成器，而初始化向量就相当于伪随机数生成器的种子。
CFB 模式可以被重放攻击

OFB 模式中，XOR 所需要的比特序列（密钥流）可以事先通过密码算法生成，和明文分组无关。
OFB 模式中，如果对密钥流的一个分组进行加密后其结果碰巧和加密前是相同的，那么这一分组之后的密钥流就会变成同一值的不断反复。

CTR 模式中可以以任意顺序对分组进行加密和解密，因此在加密和解密时需要用到的“计数器”的值可以由 nonce 和分组序号直接计算出来。
CTR 模式的密文分组中由一个比特被反转了，则解密后明文分组中仅由与之对应的比特会被翻转，这一错误不会放大。但是，攻击者也可以利用该特性来反转密文分组的某些比特，来引起明文中相应比特的反转。
CTR 模式避免了 OFB 中加密前后一致导致的问题。

需要用一种安全的方式将密钥交给对方。例如，直接将密钥保存在 U 盘中，然后亲手将 U 盘交给对方。

密钥中心为每次会话生成会话密钥，然后，用参与会话的人的密钥加密会话密钥，将加密后的会话密钥发给参与会话的人。

根据所交换的信息，双方可以各自生成相同的密钥，而窃听者却无法生成相同的密钥。

公钥密码中，密钥分为加密密钥和解密密钥，它们是不同的。发送者用加密密钥对消息进行加密，接收者用解密密钥对密文进行解密。只要拥有加密密钥，任何人都可以进行加密，但是没有解密密钥是无法解密的。

公钥密码带来了公钥认证问题，需要判断得到的公钥是否正确合法。
公钥密码的处理速度比对称密码要慢很多.

准备两个很大的质数：p 和 q
N = p * q

L 是 p-1 和 q-1 的最小公倍数
L = lcm(p-1, q-1)

E 和 L 之间存在下列关系：
1< E <L
gcd(E,L) = 1 (E 和 L 的最大公约数为 1 E 和 L 互质,该条件保证一定存在解密时需要使用的数 D)

D、E、L 之间必须具备下列关系：
1<D<L
E*D mod L = 1

密文 = 明文^E mode N
目前还没有发现求离散对数的高效算法，所以通过明文求密文非常困难。

RSA 中所使用的 p 和 q 的长度都是 512 比特以上，N 的长度为 1024 比特以上。由于 E 和 D 的长度可以和 N 差不多，因此要找出 D，就需要进行 1024 比特以上的暴力破解，这也非常困难。

D 和 E 的关系如下：
E x D mod L = 1
L = lcm(p-1, q-1)
N = p * q

EIGamal 方式利用了 mod N 下求离散对数的困难度。
EIGamal 方式的一个缺点是，经过加密的密文长度会变为明文的两倍。

Rabin 方式利用了 mod N 下求平方根的困难度。

椭圆曲线密码的特点是所需密钥长度比 RSA 短。
椭圆曲线密码是通过将椭圆曲线上的特定点进行特殊的乘法运算来实现的，它利用了这种乘法运算的逆运算非常困难这一特性。

两个不同的消息产生同一个散列值的情况称为碰撞.
难以发现碰撞的性质称为抗碰撞性。
弱抗碰撞性：当给定某条消息的散列值时，单向散列函数必须确保要找到和该条消息具备相同散列值的另外一条消息是非常困难的。
强抗碰撞性：要找到散列值相同的两条不同的消息时非常困难的，这里的散列值可以是任意值。

无法通过散列值反算出消息的内容。

用户下载到软件后，可以自行计算散列值，然后与官方网站上公布的散列值进行对比。

基于口令的加密（PBE password based encrytion）的原理是将口令和盐（salt，通过伪随机数生成器产生的随机值）混合后计算其散列值，然后，将这个散列值作为加密的密钥。通过这样的方法能够预防针对口令的字典攻击。

使用单向散列函数可以构造消息认证码。消息认证码是将“发送者和接收者之间的共享密钥”和“信息”进行混合后计算出的散列值。

数字签名的处理过程非常耗时，因此一般不会对整个消息内容直接施加数字签名，而是先通过单向散列函数计算出消息的散列值，然后再对这个散列值施加数字签名。

密码技术中所使用的随机数需要具备“事实上不可能根据过去的随机数列预测未来的随机数列”这样的性质。为了保证不可预测性，可以利用单向散列函数的单向性。

一次性口令经常被用于服务器对客户端的合法性认证。在这种方式中，通过使用单向散列函数可以保证口令只在通信链路上传送一次，因此即使窃听者窃取了口令，也无法使用。

MD 是消息摘要（Message Digest）的缩写。MD4 和 MD5 目前都已经不安全了。

SHA-1 的强抗碰撞性已于 2005 年被攻破。

RIPEMD-160 是 RIPEMD 的修订版。RIPEMD 的强抗碰撞性已经于 2004 年被攻破。

SHA-3 用于取代 SHA-1。SHA-3 和 AES 一样采用公开竞赛的方式进行标准化。
2012 年 10 月 2 日，期盼已久的 SHA-3 获胜算法终于揭开了她的面纱，她就是 Keccak 算法！Keccak 算法由意法半导体的 Guido Bertoni、Joan Daemen（AES 算法合作者）和 Gilles Van Assche，以及恩智浦半导体的 Michaël Peeters 联合开发。NIST 计算机安全专家 Tim Polk 说，Keccak 的优势在于它与 SHA-2 设计上存在极大差别，适用于 SHA-2 的攻击方法将不能作用于 Keccak。

对消息进行填充处理，使其长度为 512 比特的整数倍。这里 512 比特称为一个输入分组。
输入 SHA-1 的消息长度应大于 0 比特小于 2^64 比特。
SHA-1 的填充过程如下：

根据输入分组的 512 比特计算出 80 个 32 比特的值（W0-W79）
首先，输入分组的 512 比特分成 32 比特*16 组，并将它们命名为 W0-W15.
然后，剩下的 W16-W79 的计算方法如下。
W16 = （W0 xor W2 xor W8 xor W13） 循环左移 1 比特
Wt = W(t-16) xor W(t-14) xor W(t-8) xor W(t-3) 循环左移 1 比特

对输入分组一次进行 80 个步骤的处理，计算 5 个 32 比特的值（A-E）作为 SHA-1 的内部状态。对所有的分组都要进行这一操作。
160 比特的内部状态是通过名为 ABCDE 的 5 个 32 比特的缓冲区来表示的，80 个步骤所完成的操作，就是将输入分组的 512 比特的数据，与 SHA-1 所保持的 160 比特的内部状态（5 个缓冲区）进行混合。通过上述 80 个步骤的反复执行，SHA-1 就能够将已经过填充的消息全部混入这 160 比特的内部状态中，而 SHA-1 所输出的散列值，就是所有处理结束之后最终的内部状态（160 比特）。

分组处理是由 80 个步骤的处理组成的，其中每个步骤都是基于 W0-W79 使内部状态进行复杂变化的处理。
在一个步骤完成后，缓冲区 ABCD 的内容会被分别复制到 BCDE 中（其中 B 要循环左移 30 比特之后再复制），而缓冲区 E 的内容则会与其他缓冲区的内容以及 Wt，Kt 相加之后再被复制到缓冲区 A 中。
由于上述处理要循环 80 个步骤，因此输入分组中 1 个比特的变化，就会影响到散列值中几乎所有的比特，通过这样的方式，我们就能够实现单向散列函数所应具备的性质。

寻找和特定消息具备相同散列值的另一条不同的消息。这是一种试图破解单向散列函数的“弱抗碰撞性”的攻击

寻找散列值相同的两条消息，散列值可以是任意值。这是一种试图破解单向散列函数的“强抗碰撞性”的攻击

使用 DES，AES 之类的分组密码可以实现消息认证码。具体做法为，将分组密码的密钥作为消息认证码的共享密钥来使用，并使用 CBC 模式将消息全部加密。由于消息认证码中不需要解密，因此将除最后一个分组以外的密文部分全部丢弃，而将最后一个分组作为 MAC 值。由于 CBC 模式的最后一个分组会受到整个消息以及密钥的双重影响，因此可以将它用作消息认证码。

使用流密码和公钥密码也可以实现消息认证码。

如果密钥比单向散列函数的分组长度要短，就需要在末尾填充 0，直到其长度达到单向散列函数的分组长度为止。
如果密钥比单向散列函数的分组要长，则要用单向散列函数求出密钥的散列值，然后将这个散列值用作 HMAC 的密钥。

将填充后的密钥与被称为 ipad 的比特序列进行 XOR 运算。ipad 是将 00110110 这一比特序列（即 16 进制的 36）不断循环反复直到达到分组长度所形成的比特序列，其中 ipad 的 i 是 inner（内部）的意思。
XOR 运算所得到的值，就是一个和单向散列函数的分组长度相同，且和密钥相关的比特序列。这里我们将这个比特序列称为 ipadkey

随后，将 ipadkey 与消息进行组合，也就是将密钥相关的比特序列（ipadkey）附加在消息的开头。

将第 3 步的结果输入单向散列函数，并计算初散列值。

将填充后的密钥与被称为 opad 的比特序列进行 XOR 运算。opad 是将 01011100 这一比特序列（即 16 进制的 5C）不断循环反复直到达到分组长度所形成的比特序列，其中 opad 的 o 是 outer（外部）的意思。
XOR 运算所得到的值，这里我们将其称为 opadkey

将第 6 步的结果输入单向散列函数，并计算出散列值。这个散列值就是最终的 MAC 值。

将正确的 MAC 值保持下来重复利用，这种攻击方式称为重放攻击。

对于消息认证码来说，应保证不能根据 MAC 值推测出通信双方所使用的密钥。HMAC 中就是利用单向散列函数的单向性和抗碰撞性来保证无法根据 MAC 值推测出密钥的。
此外，在生成消息认证码所使用的密钥时，必须使用密码学安全的、高强度的伪随机数生成器。如果密钥是人为选定的，则会增加密钥被推测的风险。