[密码学复习]Cryptography

最新推荐文章于 2025-03-24 11:19:31 发布

Azhang_

最新推荐文章于 2025-03-24 11:19:31 发布

阅读量4.6k

点赞数 4

分类专栏：密码学

本文链接：https://blog.csdn.net/Azhang_/article/details/110384731

版权

整合

Week 2对称加密

Two requirements:

A strong encryption algorithm
A secret key known only to participants.

1. 有三部分构成：

1.加密算法

2.可能使用的密钥数量：数量越大越安全

3.text文本的处理：分为stream ciphers整段传输和block ciphers, 将文本切成固定块大小传输

2. 密码攻击有以下几种：

Ciphertext only, Known plaintext, Chosen plaintext, Chosen ciphertext, Chosen text:

已知明文攻击指的是攻击者获取到的明密文对。

而选择明文攻击指的是攻击者可以通过某种手段往其中加入指定明文并由此获取指定密文。

选择密文和选择文本很少见，所以书上没有过多介绍

3. Two important definitions are interesting on which much of the cryptologic research of modern times are based. 两个现代密码学研究的基础

也就是说密码学必须建立在这两个其中之一条件之上：

• Unconditional Security (Shannon): The security of the cipher is independent of the computing resource available to the adversaries. 不管对手拥有的计算资源有多强大都无法破解

• Computational Security (Turing): Adversaries are provided with constrained computing resources and the security of the cipher determined by the size of the computations required to break the cipher.为对手提供了受限制的计算资源，并且密码的安全性由破解密码所需的计算大小确定。

4. Classical Ciphers

4.1 Substitution Ciphers 代替技术

Here plaintext symbols are substituted or replaced with other symbols
using an unknown key. The substitutions can be performed as sequence of symbols or symbol by symbol. 简单来说就是把当前的字符固定的换成另一个字符

4.1.1 Caser Cipher

最简单的加密技术，给定一个k，把当前字符（所在位置为i）变成i+k个位置的字符。比如k=3，a的i=1，那么i+k=4，所以a就变成d。

这里其实E(k, p) => (c = p + k) mod 26

所以直接变换(p = c - k) mod 26 => D(k, p)

key space（密钥取值范围）为1~25，因为0就是明文自己，所以不算

Affine Cipher

Caser Cipher的升级版
Encryption: E(k,p) = c = ap + b mod m

Decryption: D(k,p) = a^-1(c – b) mod m

⚠️这里的要点是a和m需要互为质数，b的取值范围为[0, m-1]或[1, m]，因为取0和取m模出来都是0

举两个例子，如果m=26，也就是说对应的表为26字母表，那么a的取值范围为[1, 25]，b为[0, 25]，所以key space = 25 * 26

如果m=36，也就是说对应的表为26字母表，那么a的取值范围为{1,5,7,11,13,17,19,23,25,29,31,35}，因为需要互质，b为[0, 35]，所以key space = 12 * 36

这里引入一个概念叫trival。如果说trival的话就是p不管取什么，c恒等于p。所以如果a=1, b=0那么c=p。non-trivial就是总数-trival

Monalphabetic Cipher

更简单暴力，直接把每一个字母随机对应到不同的字母(可以是自身)。
所以possible keys = 26!

虽然看起来很安全，因为brute-force很难破解，但是其实Language statistics可以作为一种分析方式。分析每个字符的使用频率来计算

4.2 Transposition Ciphers 置换技术

Here plaintexts are organized as a sequence of plaintext blocks and symbol positions in each block are permuted or transposed using a key. The same permutation is used for every block. 在这里，纯文本被组织为一系列的纯文本块，并且每个块中的符号位置使用键进行置换或转置。每个块使用相同的排列。更通俗一点说，它区别于代替技术，它是直接将明文打散，通过复杂排列进行重新组合

一个例子：Row transposition cipher
plaintext: attackpostponeduntiltwoamxyz
简单来说它就是先把明文一行一行地写成矩阵块，然后打乱列的序号，根据序号从1开始，按列从上到下的顺序依次读取字符拼成新的密文。且可以多次加密。

4.3 Complex Ciphers - Polyalphabetic Cipher

Vigenère Cipher

假设plaintext P的长度是n，他会先随机定义一个d，然后对应每一个index i（i属于n）获得K_i = i mod d。然后使用Caser Cipher获得
Encryption:E(K,P) = C, where c_i = p_i + k_i mod 26

Decrypton: D(K,C) = P, where p_i = c_i - k_i mod 26

d越大越安全。以下是一个例子：

Week 3

Modern Symmetric Ciphers
主要分成两种，流加密和块加密

1. One Time Pad

首先我们回顾一下Vigenère Cipher

假设plaintext P的长度是n，他会先随机定义一个d，然后对应每一个index i（i属于n）获得K_i = i mod d。然后使用Caser Cipher获得
Encryption:E(K,P) = C, where c_i = p_i + k_i mod 26

Decrypton: D(K,C) = P, where p_i = c_i - k_i mod 26

d越大越安全。以下是一个例子：

One time pad其实就是这种cipher的特殊例子，就是当n=d的时候就是one time pad，也叫Vernam。（n是plaintext长度，d是key的长度）

在这里其实就是用XOR来加密解密。

Plaintext ⊕ Key = CipherText

CipherText ⊕ Key = Plaintext

Perfect Secrecy

• An encryption scheme has the property of unconditional security if the cipher text generated by the algorithm does not reveal sufficient information to break the scheme, even with access to an unlimited amount of computational power.

• In other words, the adversary cannot not obtain any knowledge to reverse the encryption by watching any amount of cipher text without access to the key.

It implies: Pr[M = x|C = y] = Pr[M = x]
也可以写成P_X|Y(x|y) = P_X(x) 大致意思就是，哪怕给定了另一个条件Y，也不会改变/影响原来X的概率

One time pad其实不太practical，因为要保证key的绝对安全。但是two time pad就不够安全，因为

• C1=M1 ⊕ K; C2= M2 ⊕ K; then

• C1 ⊕ C2=M1 ⊕ M2 ⊕ K ⊕ K= M1 ⊕ M2.

Even though M1 ⊕ M2 may not direct meaning, it still leaks information about both M1 and M2.

Block Cipher

Fiestel Block Cipher

首先要了解这是一种密码结构，很多算法都在用这种结构，包括DES

首先会传入一个长度为2w的明文（2的倍数）和一个密钥Key。接下来会决定产生轮次round，图中轮次为16（DES一般就是16）。然后根据传入的key用特殊或者自制算法计算出子key{key₁, key₂, …, key₁₆}。这些子key和原key没啥直接关系。接下来就是如图，每一轮，让右边part R完全不做处理，直接放在下一轮的L。然后输入key_i和右边部分进函数F获得result，让左边part L和result XOR得到下一轮的R。

所以说Fiestel主要强度来自于：1.F函数强度，2.轮数，3.生成子key的算法的强度

DES

DES算法的相关参数如下：　

明文分组长度：64 bits，左右各32 bits

密钥长度：64 bits

轮数：16轮

3DES

首先先说一下2DES在本质上并没有比DES安全多少，所以能破解DES大概率也能破解2DES。但是3DES如果在三个过程中使用的key都不一样的话，那么密钥长度可以被认为是192(64*3)位。同时为什么采用加密-解密-加密的模式是因为首先如果3个key都不相同，那么这种方式其实和加密-加密-加密的模式得出来的加密效果是一样的。但是如果3个key一样，又可以向下兼容，变成DES模式。