# 第一章 古典密码学

# 基础定义

一个密码体制满足以下条件的五元组(P,C,K,ε,D)P表示明文空间C表示密文空间K表示密钥空间加密规则eKε解密规则dKD并且加密、解密规则满足条件:对每一个明文xP,均有dK(eK(x))=x\begin{matrix} 一个密码体制满足以下条件的五元组(\mathcal{P},\mathcal{C},\mathcal{K},\varepsilon,\mathcal{D}) \\ \mathcal{P}表示明文空间 \\ \mathcal{C}表示密文空间 \\ \mathcal{K}表示密钥空间 \\ 加密规则e_\mathcal{K} \in \varepsilon \\ 解密规则d_\mathcal{K} \in \mathcal{D} \\ 并且加密、解密规则满足条件: 对每一个明文x\in \mathcal{P},均有d_\mathcal{\mathcal{K}}(e_\mathcal{K}(x))=x \end{matrix}

# 移位密码

P=C=K=Z26,0K25,任意x,yZ26ek(x)=(x+K)mod26dk(y)=(yK)mod26\begin{matrix} 令P=C=K=\mathbb{Z}_{26},对0\leq K \leq 25,任意x,y\in\mathbb{Z}_{26} \\ e_k(x) = (x+K)\mod26 \\ d_k(y) = (y - K)\mod26 \end{matrix}

凯撒密码即为K=3K=3 时的移位密码

# 代换密码

P=C=Z26K是由26个数字0,1...,25的所有可能的置换组成。对任意的置换πK,定义eπ(x)=π(x)dπ(y)=π1(y)其中π1表示π函数的逆变换\begin{matrix} 令P=C=\mathbb{Z}_{26}。K是由26个数字0,1...,25的所有可能的置换组成。 \\ 对任意的置换\pi\in K,定义 \\ e_\pi(x)=\pi(x) \\ d_\pi(y)=\pi^{-1}(y) \\ 其中\pi^{-1}表示\pi函数的逆变换 \end{matrix}

移位密码是代换密码其中的一种情况

# 密码分析初步

# Kerchhoff 原则

Kerchhoff 原则:密码系统的安全性不依赖于加密体制或算法的保密,而依赖于密钥的安全性。

遵循 Kerchhoff 原则的好处:

  • 保护密钥比保护算法更加容易
  • 更换密钥比更换算法要更加容易
  • 加密算法需要统一,便于用户应用
  • 加密算法公开有助于承受公开的钻研和分析,从而提高算法的防御力。同时使公开设计使标准的建立成为可能

# 典型攻击模型

  • 唯密文攻击:敌手只拥有(某些个)密文串yy
  • 已知明文攻击:敌手拥有(某些个)明文串xx 及其对应的密文串yy
  • 选择明文攻击:敌手可以自由选择(某些个)明文串xx 并获得对应的密文串yy
  • 选择密文攻击:敌手可以自由选择(某些个)密文串yy 并获得对应的明文串xx

通常古典密码的唯密文攻击常采用词频分析的方式

# 仿射密码

P=C=Z26,K=(a,b)Z26×Z26:gcd(a,26)=1对任意的K=(a,b)K,x,yZ26,定义eK(x)=(ax+b)mod26dK(y)=a1(yb)mod26其中a1表示a的逆元(aa1=1mod26\begin{matrix} 令P=C=\mathbb{Z}_{26},且 K = {(a,b)\in\mathbb{Z}_{26}\times\mathbb{Z}_{26}:gcd(a,26)=1} \\ 对任意的K=(a,b)\in K,{\,\,}x,y\in\mathbb{Z}_{26},定义 \\ e_K(x) = (ax+b)\mod26 \\ d_K(y) = a^{-1}(y-b)\mod26 \\ 其中a^{-1}表示a的逆元(aa^{-1}=1\mod26 \end{matrix}

仿射密码的数学基础:

  • 同余方程定理

aZa\in\mathbb{Z},则同余方程axbmodma \cdot x \equiv b \mod m 有唯一解xZx\in\mathbb{Z} 的充分必要条件是gcd(a,m)=1gcd(a,m)=1

  • 同余方程定理

Zm\mathbb{Z}_m 中与mm 互素的数的个数成为mm 的欧拉函数,记为ϕ(m)\phi(m)

  • 基本算术定理与欧拉函数计算

如果不计因子顺序,任意整数mm 的素因子分解是唯一的。
m=Πi=1npieim = \Pi^n_{i=1}p^{e_i}_{i} 这里pip_i 均为素数且互不相同,ei>0,1ine_i>0,{\,\,}1\leq i \leq n,则ϕ(m)=Πi=1n(pieipi1ei)\phi(m)=\Pi^n_{i=1}(p^{e_i}_i-p^{e_i}_{i-1})

# 维吉尼亚密码

m是一个正整数。定义P=C=K=(Z26)m对任意的密钥K=(k1,k2,...,km),定义eK(x1,x2,...,xm)=(x1+k1,x2+k2,...,xm+km)dK(y1,y2,...,ym)=(y1k1,y2k2,...,ymkm)\begin{matrix} 设m是一个正整数。定义P=C=K=(\mathbb{Z}_{26})^m。 \\ 对任意的密钥K=(k_1,k_2,...,k_m),定义 \\ e_K(x_1,x_2,...,x_m)=(x_1+k_1,x_2+k_2,...,x_m+k_m) \\ d_K(y_1,y_2,...,y_m)=(y_1-k_1,y_2-k_2,...,y_m-k_m) \end{matrix}

维吉尼亚密码的 python 实现:

115-181
# -*- coding:utf-8 -*-
# 读取明文
def readPlaintext():
    t = []
    with open("./plaintext.txt", "r", encoding="utf-8") as plaintext:
        text = plaintext.readline()
        text = text.strip()
        for chr in text:
            t.append(chr)
    return t
# 读取密钥
def readKey():
    key = ""
    with open("./key.txt", "r", encoding="utf-8") as f:
        key = f.read()
    return key
# 写入密文
def writeCphertext(text):
    with open("./cphertext.txt", "w", encoding="utf-8") as cphertext:
        cphertext.write(text)
# 维吉尼亚密码加密过程
def vigenereEnc(plaintext, key):
    cphertext = ""
    key_length = len(key)
    upper_key = key.upper()
    index = 0 # 密钥下标
    for iter in plaintext:
        if iter.isalpha():
            # 如果是大写字母
            if iter.isupper():
                diff = 'A'
            else:
                diff = 'a'
            cphertext += chr(ord(diff) + ((ord(iter) - ord(diff)) + ord(upper_key[index % key_length]) - ord('A')) % 26)
            index += 1
        else:
            cphertext += iter
    return cphertext
# 维吉尼亚密码解密过程
def vigenereDec(cphertext, key):
    plaintext = ""
    key_length = len(key)
    upper_key = key.upper()
    index = 0 # 密钥下标
    for iter in cphertext:
        if iter.isalpha():
            if iter.isupper():
                diff = 'A'
            else:
                diff = 'a'
            plaintext += chr(ord(diff) + ((ord(iter) - ord(diff)) - ord(upper_key[index % key_length]) - ord('A')) % 26)
            index += 1
        else:
            plaintext += iter
    return plaintext
if __name__ == "__main__":
    key = readKey()
    plaintext = readPlaintext()
    cphertext = vigenereEnc(plaintext, key)
    writeCphertext(cphertext)

维吉尼亚密码的唯密文破解

  • Kasiski 测试法
    原理:如果两个相同的明文段被加密成相同的密文段,则这两个密文段之间的间距以很大概率为密钥长度的整数倍。
    方式:搜索长度至少为 3 的相同密文段,确定其离起始密文段的距离,进而猜测长度 m 为这些距离的最大公因子的因子
  • 重合指数法

定义:设x=x1x2...xnx=x_1x_2...x_n 是一个长度为 n 的字母串,xx 的重合指数Ic(x)I_c(x) 定义为 xx 中两个随机元素相同的概率。

原理:如果 x 是单表代换加密的密文串,则其重合指数与完全随机串的重合指数将会有显著偏离!

方式:维吉尼亚密码为多表代换密码,如果 Kasiski 测试法得到的 m 为正确值,则密文可以按照步长 m 分割为多个单表代换密码的密文,分割后的密文串应该符合重合指数法原理,即重合指数接近计算出来的字母重合指数。

Ic(x)=Σi=025[fi2][n2]=Σi=025fi(fi1)n(n1)\begin{matrix} I_c(x)=\frac{\Sigma^{25}_{i=0} \begin{bmatrix} f_i \\ 2 \\ \end{bmatrix}} {\begin{bmatrix} n \\ 2 \\ \end{bmatrix} } = \frac {\Sigma^{25}_{i=0}f_i(f_i-1)} {n(n-1)} \end{matrix}

下面是一段有效的维吉尼亚密码唯密文破解的 python 代码

220-448
# -*- coding:utf-8 -*-
import math
import Vigenere
# 字母频数表
dic_freq = {'A': 8.167, 'B': 1.492, 'C': 2.782, 'D': 4.253,
            'E': 12.702, 'F': 2.228, 'G': 2.015, 'H': 6.094,
            'I': 6.966, 'J': 0.153, 'K': 0.772, 'L': 4.025,
            'M': 2.406, 'N': 6.749, 'O': 7.507, 'P': 1.929,
            'Q': 0.095, 'R': 5.987, 'S': 6.327, 'T': 9.056,
            'U': 2.758, 'V': 0.978, 'W': 2.360, 'X': 0.150,
            'Y': 1.974, 'Z': 0.074}
# Kasiski 测试法 =================================
# 预处理字符串,将所有字母变成大写字母,去掉空格和标点符号
def preModify(text):
    result = ""
    for iter in text:
        if iter.isalpha():
            result += iter
    result = result.upper()
    return result
# 找到长度为 3-6 的重复字符子串
def calculateDistance(text):
    pre_text = preModify(text)
    pre_text_length = len(pre_text)
    result = {}
    for str_length in range(3, 7):
        for index in range(0, pre_text_length - 2 * str_length + 1):
            temp_str = pre_text[index: index + str_length]
            temp_str_cnt = pre_text.count(temp_str)
            if temp_str_cnt > 1 and (temp_str not in result.keys()):
                # 获得第一次出现重复字符字串的下标
                first = pre_text.find(temp_str)
                temp_list = [first]
                # 获得所有重复字符字串的下标,temp_list 存储下标
                for count in range(1, temp_str_cnt):
                    second = pre_text.find(temp_str, first + str_length)
                    temp_list.append(second)
                    first = second
                temp_distance = []
                temp_list_length = len(temp_list)
                for index in range(0, temp_list_length - 1):
                    temp_distance.append(temp_list[index + 1] - temp_list[index])
                result[temp_str] = temp_distance
    
    return result
# 分解因数
def decompositionFactor(number):
    result = []
    max_limit = math.isqrt(number) + 1
    for i in range(2, max_limit):
        if number % i == 0:
            result.append(i)
            j = number // i
            if i != j:
                result.append(j)
    result.sort()
    return result
# 通过重复字符字串间距获得因数列表
def getFactorsList(str_dist):
    temp_flag = {}
    for iter in str_dist:
        for iter2 in str_dist[iter]:
            # 获取因数列表
            temp_list = decompositionFactor(iter2)
            for iter3 in temp_list:
                if iter3 not in temp_flag:
                    temp_flag[iter3] = 1
                else:
                    temp_flag[iter3] += 1
    
    fac_list = []
    # 按照因数重复次数从大到小排序,如果相同则按因数大小从小到大排序
    for iter in sorted(temp_flag.items(), key=lambda x:(-x[1], x[0])):
        fac_list.append(iter[0])
    
    return fac_list
# 根据 Kasiski 测试法分出 m 组移位密文
def getShiftCipher(text, shift_dist):
    result = []
    text = preModify(text)
    text_length = len(text)
    for i in range(0, shift_dist):
        temp_str = ""
        for index in range(i, text_length, shift_dist):
            temp_str += text[index]
        result.append(temp_str)
    return result
# 重合指数法 ===============================================
# 统计频数
def calculateFrequency(text):
    character_frequency = {}
    text = preModify(text)
    text_length = len(text)
    for iter in text:
        if iter not in character_frequency:
            character_frequency[iter] = 1
        else:
            character_frequency[iter] += 1
    for iter in character_frequency:
        character_frequency[iter] /= text_length
    return character_frequency
# CI 值
def calculateCI(text):
    result = []
    num = 0
    character_frequency = calculateFrequency(text)
    for k in range(0, 26):
        num = 0
        for index in range(0, 26):
            if chr(ord('A') + (index + k) % 26) not in character_frequency:
                num += 0
                continue
            num += character_frequency[chr(ord('A') + (index + k) % 26)] * dic_freq[chr(ord('A') + index)]
        result.append(num)
    return result
# 计算每组的偏移量得到密钥
def calculateShift(frequency_list):
    flag = 0
    index = 0
    shift_k = -999999.0
    for i in range(0, 26):
        if 0.06 <= frequency_list[i] and frequency_list[i] <= 0.07:
            index = i
            flag = 1
    if flag == 0:
        for i in range(0, 26):
            if frequency_list[i] >= shift_k:
                index = i
                shift_k = frequency_list[i]
    return index
# 根据字典筛选可能具有实际意义的文本
def filterText(plaintext):
    upper_plaintext = plaintext.upper()
    with open("./dictionary.txt", "r", encoding="utf-8") as f:
        word_list = f.readlines()
    word_list_length = len(word_list)
    for i in range(0, word_list_length):
        word_list[i] = word_list[i].rstrip('\n')
    plaintext_word_list = []
    plaintext_word = ""
    plaintext_word_total = 0
    for iter in upper_plaintext:
        if iter.isalpha():
            plaintext_word += iter
        else:
            plaintext_word_list.append(plaintext_word)
            plaintext_word_total += 1
            plaintext_word = ""
    word_percent = 0
    for iter in plaintext_word_list:
        if iter in word_list:
            word_percent += 1
    word_percent = word_percent / plaintext_word_total
    if word_percent >= 0.2:
        return True
    else:
        return False
# 得到密钥
def getKey(cphertext):
    # 预处理密文
    temp_cphertext = preModify(cphertext)
    # 获取重复子串
    repeat_sub_string = calculateDistance(temp_cphertext)
    # 获取最有可能的几个公因数
    factors_list = getFactorsList(repeat_sub_string)
    # 取前六个公因数计算密钥
    key_value = []
    for number in factors_list[:5]:
        # 获取根据公因数分组后的移位密文
        shift_cpher = getShiftCipher(temp_cphertext, number)
        # 对每组计算 CI 值
        temp_key_value = []
        for iter_1 in shift_cpher:
            CI_value = calculateCI(iter_1)
            shift_key = calculateShift(CI_value)
            temp_key_value.append(shift_key)
        key_value.append(temp_key_value)
    # 对每组密文进行重排列
    # fact_key = permutationKey(key_value)
    # 对每组密钥尝试解密密文
    plaintext = []
    key_group = []
    no_repeat_plaintext = []
    for iter in key_value:
        key = ""
        for iter_2 in iter:
            key += chr(ord('A') + iter_2)
        key_group.append(key)
        plaintext.append(Vigenere.vigenereDec(cphertext, key))
    print("根据Kasiski测试法和重合指数法获取的所有密钥:")
    with open("./cipher2plaintext_key.txt", "w", encoding="utf-8") as f:
        for iter in key_group:
            print(iter)
            f.write(iter + "\n")
    print("根据Kasiski测试法和重合指数法解密的所有明文:")
    with open("./cipher2plaintext_plaintext.txt", "w", encoding="utf-8") as f:
        for iter in plaintext:
            print(iter)
            f.write(iter + "\n")
    print("根据Kasiski测试法和重合指数法解密的所有具有实际意义的明文:")
    with open("./cipher2plaintext_fact_plaintext.txt", "w", encoding="utf-8") as f:
        for iter in plaintext:
            if filterText(iter) == True and (iter not in no_repeat_plaintext):
                print(iter)
                no_repeat_plaintext.append(iter)
                f.write(iter + "\n")
            
if __name__ == "__main__":
    temp = ""
    with open("./cphertext.txt", "r", encoding="utf-8") as f:
        temp = f.read()
    getKey(cphertext=temp)

# 希尔密码

m2为正整数,P=C=(Z26)m,且K=定义在Z26上的m×m可逆矩阵gcd(detK,26)=1对任意的密钥K,定义eK(x)=xKdK(y)=yK1\begin{matrix} 设m\geq2为正整数,P=C=(\mathbb{Z}_{26})^m,且 K={定义在\mathbb{Z}_{26}上的m\times m可逆矩阵}(gcd({\,}det{\,\,}K,26)=1) \\ 对任意的密钥K,定义 \\ e_K(x)=xK \\ d_K(y)=yK^{-1} \end{matrix}

# 置换密码

m为一正整数。P=C=(Z26)mK是由所有定义在集合1,2,...,m上的置换组成。对任意的密钥(即置换)π,定义eπ(x1,x2,...,xm)=(xπ(1),xπ(2),...,xπ(m))dπ(x1,x2,...,xm)=(xπ1(1),xπ1(2),...,xπ1(m))其中π1为置换π的逆置换\begin{matrix} 令m为一正整数。P=C=(\mathbb{Z}_{26})^m,K是由所有定义在集合{1,2,...,m}上的置换组成。 \\ 对任意的密钥(即置换)\pi,定义 \\ e_\pi(x_1,x_2,...,x_m)=(x_{\pi(1)},x_{\pi(2)},...,x_{\pi(m)}) \\ d_\pi(x_1,x_2,...,x_m)=(x_{\pi^{-1}(1)},x_{\pi^{-1}(2)},...,x_{\pi^{-1}(m)}) \\ 其中\pi^{-1}为置换\pi的逆置换 \end{matrix}

简单来说就是将明文按照长度分组后,在每组中按置换函数进行置换

# 第二章 加密方案的安全性

# 现代密码学的基本原则

现代密码学的三个主要原则

  • 对 “安全” 的定义必须是公式化的、表述严格且精确的。
  • 若密码学方案的安全性依赖于某个未被证明的假设,这种假设必须精确陈述,且假设需要尽可能少。
  • 密码学方案应该有严格的安全证明。

# 完善保密性

# 无条件安全(Perfect Secrecy)

# 定义

即使攻击者具有无限的计算机资源,也无法攻破密码体制,我们称这种密码体制是无条件安全的

加密方案的定义:

  • 密钥生成子算法(Gen)

算法输入:安全参数nn,算法输出:满足特定分布的密钥kk

  • 加密子算法(Enc)

算法输入:密钥kk 和明文mm,算法输出:密文ccc=Enc(k,m)c=Enc(k,m)

  • 解密子算法(Dec)

算法输入:密钥kk 和密文cc,算法输出:明文mmm=Dec(k,c)m=Dec(k,c)

正确性:Dec(k,Enc(k,m))=mDec(k,Enc(k,m))=m

# 完善保密加密方案

明文空间为M\mathcal{M} 的加密方案Π=(Gen,Enc,Dec)\Pi=(Gen,Enc,Dec) 是无条件安全的,当且仅当对于M\mathcal{M} 上任意的概率分布,mM,cC\forall m \in \mathcal{M},c \in \mathcal{C}Pr[C=c]>0Pr[C=c]>0,有

Pr[M=mC=c]=Pr[M=m]Pr[M=m | C=c] = Pr[M=m]

这个式子描述了 “后验概率等于先验概率”,另一种等价的解释是:当且仅当明文和密文的分布是独立的,方案才是完善保密加密。

同时Pr[C=cM=m]=Pr[C=c]Pr[C=c | M=m] = Pr[C=c] 也成立,这是完善保密的等价描述

证明过程:

由条件概率公式可知,Pr[xy]=Pr[xy]Pr[y]Pr[x\bigwedge y]=Pr[x|y]Pr[y]

Pr[M=mC=c]=Pr[M=m]Pr[M=mC=c]Pr[C=c]=Pr[M=m]Pr[C=cM=m]Pr[M=m]=Pr[C=c]Pr[C=cM=m]=Pr[C=c]\begin{matrix} Pr[M=m | C=c] = Pr[M=m] \\ \iff \frac{Pr[M=m\bigwedge C=c]}{Pr[C=c]}=Pr[M=m] \\ \iff \frac{Pr[C=c\bigwedge M=m]}{Pr[M=m]}=Pr[C=c] \\ \iff Pr[C=c|M=m]=Pr[C=c] \end{matrix}

# 完善保密加密另一种表述:完美不可区分性

明文空间为M\mathcal{M} 的加密方案Π=(Gen,Enc,Dec)\Pi=(Gen,Enc,Dec) 是完善保密加密,当且仅当对于任意M\mathcal{M} 的概率分布,每个m0,m1Mm_0,m_1\in\mathcal{M} 和每个cCc\in\mathcal{C},均有

Pr[C=cM=m0]=Pr[C=cM=m1]Pr[C=c|M=m_0]=Pr[C=c|M=m_1]

充分性:若方案是完善保密加密,那么它一定满足完美不可区分性

Pr[C=cM=m0]=Pr[C=c]=Pr[C=cM=m1]Pr[C=c|M=m_0]=Pr[C=c]=Pr[C=c|M=m_1]

必要性:利用贝叶斯公式

P(c)=P(cmi)P(mi)P(mi)=P(cmi)P(mi)=P(cmi)P(c)=\frac{\sum P(c|m_i)\cdot P(m_i)}{\sum P(m_i)}=\sum P(c|m_i)\cdot P(m_i)=P(c|m_i)

其中P(mi)=1\sum P(m_i)=1P(cmi)\sum P(c|m_i) 恒等,故上式等于P(cmi)P(c|m_i)

# 敌手不可区分性

考虑任意加密方案Π=(Gen,Enc,Dec)\Pi = (Gen, Enc, Dec),任意敌手为A\mathcal{A}.

PrivKeavPrivK^{eav} 表示一个给定的Π\PiA\mathcal{A} 的实验,实验定义如下:

窃听不可区分实验PrivkA,ΠeavPrivk^{eav}_{\mathcal{A},\Pi}:

1. 敌手A\mathcal{A} 输出一对信息m0,m1Mm_0,m_1 \in \mathcal{M}.

2. 由GenGen 产生一个随机密钥kk,并且从0,10,1 里面随机选择一个比特bb. 然后,计算密文cEnck(mb)c \leftarrow Enc_k(m_b) 交给A\mathcal{A}.

3.A\mathcal{A} 输出一个比特bb'

4. 若b=bb'=b,定义实验的输出为11;否则为00. 若输出为11,记为PrivkA,Πeav=1Privk^{eav}_{\mathcal{A},\Pi}=1,此时称A\mathcal{A} 成功.

显然,若敌手随机猜测有50%50\% 的概率成功。

完善保密加密的另一种定义是:若没有敌手能以大于50%50\% 的概率成功,那么这种加密方案就是完善保密加密。

方案(Gen,Enc,Dec)(Gen,Enc,Dec) 为完善保密加密,当且仅当对于所有敌手都满足

Pr[PrivkA,Πeav=1]=12Pr[Privk^{eav}_{\mathcal{A},\Pi}=1]=\frac12

# 一次一密

一次一密的定义如下:

令整数l>0l>0,设M,K,C={0,1}l\mathcal{M},\mathcal{K},\mathcal{C}=\left\{0,1\right\}^l

GenGenK={0,1}l\mathcal{K}=\left\{0,1\right\}^l 里面按均匀分布选取一个二进制串

Enck(m)Enc_k(m):输出c:=kmc:=k\oplus m

Deck(c)Dec_k(c):输出m:=kcm:=k\oplus c

缺点:

  • 密钥长度和明文长度一样长
  • 密钥只能使用一次
  • 密钥管理异常复杂

# 完善保密性小结

完善保密加密的局限性:所有的完善保密加密,密钥空间都不小于明文空间

# 计算安全性

定义:攻击者具有有限的计算资源,很难攻破密码体制,我们称这种密码体制是计算安全的

# 可忽略函数

计算安全性的定义并不要求完全没可能攻破密码,实际上只要满足攻破密码算法的概率可忽略条件即可

如何定义概率可忽略?

  • 渐进表示:当安全参数nn 足够长时,PPT(概率多项式时间)敌手攻破密码算法的概率快速趋近于 0
  • 形式化定义:可忽略函数

一个函数f:NRf:\mathbb{N} \rightarrow \mathbb{R} 是可忽略的,满足以下条件

多项式p(),N,s.t.n>N,f(n)<1p(n)\forall多项式p(·),\exists N,s.t.\forall n > N, f(n)<\frac{1}{p(n)}

例如:2^{-n},2^{-\sqrt{n}},n^

我们把一个可忽略函数表示为 negl

可忽略函数也有着闭包特性

两个 negl 的和也是 negl

多项式乘 negl,得到的也是 negl

# 一般渐进安全性表述

一个方案是安全的,如果任意 PPT 敌手攻击成功的概率不超过安全参数的可忽略函数。

从设计安全的密码方案的角度,提高安全参数,攻击者攻击成功的概率以超多项式的速 度下降,而诚实的用户运行时间只增长了(通常很小的)多项式时间。所以可以通过选择足够大的 安全参数 n 得到足够强的安全性。

# 窃听不可区分实验

为了描述计算安全,定义一个实验。这个实验相比起之前的实验,只考虑 PPT 敌手:要求敌手判断正确的概率大于50%50\% 的程度是 negl 的

窃听不可区分实验PrivkA,Πeav(n)Privk^{eav}_{\mathcal{A},\Pi}(n):

1. 给定输入1n1^n 给敌手A\mathcal{A}, A\mathcal{A} 输出一对长度相等的信息m0,m1m_0,m_1.
2. 运行Gen(1n)Gen(1^n) 生成一个密钥kk, 选择一个随机比特bb, 计算cEnck(mb)c\leftarrow Enc_k(m_b) 并交给A\mathcal{A}. 这里的cc 称为挑战密文
3.A\mathcal{A} 输出一个比特bb'
4. 若b=bb=b',则实验输出为11; 否则为00. 若PrivkA,Πeav(n)=1Privk^{eav}_{\mathcal{A},\Pi}(n)=1,则称A\mathcal{A} 成功

在上面的实验中,任何 PPT 敌手的成功概率高于50%50\% 的部分可忽略,则这个加密方案是安全的

如果对于所有 PPT 敌手A\mathcal{A}, 存在一个可忽略函数 negl 使得

Pr[PrivkA,Πeav(n)=1]12+negl(n)Pr[Privk^{eav}_{\mathcal{A},\Pi}(n)=1]\leq \frac{1}{2}+negl(n)

则称对称加密方案Π=(Gen,Enc,Dec)\Pi=(Gen,Enc,Dec)在窃听者存在的情况下不可区分的加密。

# 伪随机性

如果说一个长度为l\mathcal{l} 的字符串的分布D\mathcal{D} 是伪随机的,那么意味着D\mathcal{D} 与均匀分布是不可区分的。更准确地说:对于任何多项式时间算法,分辨出一个字符串是D\mathcal{D} 的样本还是均匀分布的样本,是不可行的。

关于伪随机性在密码学中的作用,有一个直观的例子:考虑一个加密方案,如果密文是伪随机的,则在任何 PPT 敌手的角度上看,这个密文与真正的随机串没有任何区别:从而不会携带关于明文的任何信息。

# 伪随机数发生器 (PRG)

一个伪随机发生器是一个确定性算法,接受一个较短的种子,将其扩展成为一个长的伪随机字符串。

l()\mathcal{l}(·) 为多项式,令GG 为确定多项式时间算法。这个算法满足:对于任何输入s{0,1}ns \in \left\{0,1\right\}^nGG 输出一个长度为l(n)\mathcal{l}(n) 的字符串。如果满足下面的两个条件,则称GG 是一个伪随机发生器:

1. 扩展性:对于每个nn,有l(n)>n\mathcal{l}(n)>n

2. 伪随机性:对于所有的 PPT 区分器D\mathcal{D} 来说:

Pr[D(r)=1]Pr[D(G(s))=1]negl(n)|\Pr[D(r) = 1] - \Pr [D(G(s)) =1]| \leq negl(n)

其中rr 是从{0,1}l(n)\left\{0,1\right\}^{\mathcal{l}(n)} 中均匀随机选择的;s 是从{0,1}n\left\{0,1\right\}^n 中均匀随机选择的。

l(n)\mathcal{l}(n) 称为扩展因子

伪随机数是真随机数在计算能力上的松弛。正因为敌手没有无限的计算能力,伪随机数才能骗过所有的 PPT 敌手。

显然,一个伪随机数发生器的种子,必须均匀选取,对区分器保密。另外,实践上,种子应该足够长,使得攻击者没办法在可行时间内暴力枚举所有种子。

目前,我们还不知道伪随机发生器是否真的存在。但我们倾向于认为存在,而且已经造出了许多在现实生活中可用的发生器。

# 用 PRG 构造定长加密方案

首先令GG 是一个扩展因子为l\mathcal{l} 的 PRG. 构造加密方案如下:

  • GenGen:随机选择k{0,1}nk \in \left\{0,1\right\}^n
  • EncEncc:=G(k)mc:=G(k)\oplus m
  • DecDecm:=G(k)cm:=G(k)\oplus c

下面证明它是窃听不可区分的。

考虑任意的 PPT 敌手A\mathcal{A},定义ε\varepsilon

ε(n)Pr[PrivKA,Πeav(n)=1]12\varepsilon(n) \triangleq \Pr[PrivK^{eav}_{\mathcal{A},\Pi}(n) = 1] - \frac12

显然,如果A\mathcal{A} 能攻破Π\Pi (可以判断出密文来源),那么ε(n)\varepsilon(n) 是不可忽略的。

我们构造一个针对GG 的区分器D\mathcal{D} 如下:

区分器D\mathcal{D} 获取到输入w{0,1}l(n)\mathcal{w} \in \left\{0,1\right\}^{\mathcal{l}(n)},然后D\mathcal{D} 进行如下操作:

1. 运行A(1n)\mathcal{A}(1^n)A\mathcal{A} 产生一对消息m0,m1m_0,m_1 交回给\mathcal

2.D\mathcal{D} 随机选择一个比特bb,令c:=wmbc:=\mathcal{w} \oplus m_b

3. 把cc 发给A\mathcal{A}A\mathcal{A} 猜测cc 是源于m0m_0 还是m1m_1,将猜测结果bb' 交给D\mathcal{D}. 如果b=bb'=b,则D\mathcal{D} 输出11;否则输出00.

如果w\mathcal{w} 是随机选择的,此时A\mathcal{A} 完全等同于做了一次一密,从而!swig0>Pr[D(w)=1]=Pr[PrivKA,<eav=1]=12\def\tPi\Pr[\mathcal{D}(w) = 1] = \Pr[PrivK ^ {eav} _ {\mathcal{A}, \tPi} = 1] = \frac12,其中\tPi 是长度为l(n)\mathcal{l}(n) 的一次一密方案。

如果w\mathcal{w} 是取自伪随机发生器的,则此时A\mathcal{A} 的行为完全与题设中的Π\Pi 一致,加密方案是异或上G(k)G(k),故A\mathcal{A} 的成功概率是12+ε(n)\frac12+\varepsilon(n). 此时

Pr[D(w)=1]=Pr[D(G(k))=1]=Pr[PrivKA,Πeav(n)=1]=12+ε(n)\Pr[D(w) = 1] = \Pr[D(G(k)) = 1] = \Pr[PrivK^{eav}_{\mathcal{A}, \Pi}(n) = 1] = \frac{1}{2} + \varepsilon(n)

综上,我们得到Pr[D(w)=1]Pr[D(G(k))=1]=ε(n)\Big | \Pr[D(w) = 1] - \Pr[D(G(k)) = 1] \Big |= \varepsilon(n),按照 PRG 的性质,ε(n)=negl\varepsilon(n) = negl,从而A\mathcal{A} 无法攻破Π\Pi,故Π\Pi 是窃听不可区分的。

# 第三章 分组密码

# 分组加密的构造方法

# 分组密码

分组密码(Block cipher)

  • 将明文分成等长的分组(64bit, 128bit)

  • 对每个分组采用相同的加密算法进行加密

  • 算法一般是交替使用混淆和扩散技术

# 实际构造方法

  • 代换 - 置换网络(SPN,Substitution Permutation Network)

  • Feistel 网络

  • 雪崩效应

# 代换 - 置换网络(SPN)

定义M=C=lm|\mathcal{M}|=|\mathcal{C}|=l\cdot m,一个lml\cdot m 长的二进制串x=(x1,x2,,xlm)x = (x_1,x_2,…,x_{lm})

可以看作mm 个长度为ll 的子串的并联,x=x<1>x<2>x<m>x = x_{<1>}||x_{<2>}||…||x_{<m>},其中x<i>=(x(i1)l+1,,xil)x_{<i>}=(x_{(i-1)l+1},…,x_{il})

  • 代换πS\pi_S{0,1}l{0,1}l\left\{0,1\right\}^l \rightarrow \left\{0,1\right\}^l
  • 置换πP\pi_P:\left\{1,…,lm\right\} \rightarrow \left\

  • 二进制明文串wi1\mathcal{w_{i-1}} 与密钥KiK_i 异或得到uiu_i
  • uiu_i 中每四位查询代换表 ——SS 盒进行代换得到viv_i
  • viv_i 每一位查询置换表 ——PP 盒进行置换得到wiw_i

# Feistel 密码结构

  • 明文分组分为L0L_0R0R_0,通过nn 次循环处理后,再结合起来生成密文分组。
  • 每第ii 次循环都以上一循环产生的Li1L_{i-1}Ri1R_{i-1}KK 产生的子密钥KiK_i 作为输入
  • 所有循环的结构都相同,其方法是先对数据的右半部分和子密钥应用函数FF,然后对函数输出结果和数据的左半部分取异或。
  • 在置换之后,执行由数据两部分互换构成的交换。
  • 解密过程与加密过程基本相同。规则如下:用密文作为算法的输入,但以相反顺序使用子密钥 KiK_i

# 数据加密标准(DES, Data Encryption Standard)

# 具体过程

具体看 DES 算法原理及实现

# 高级加密标准(AES, Advanced Encryption Standard)

# 概要

128 比特分组,128、192 和 256 位密钥。如果密钥长度是 128 比特,则轮数是 10,如果密钥长度是 192 比特,则轮数是 12,如果密钥长度是 256 比特,则轮数是 14.

AES 和 SPN 网络结构非常的相似。每一轮都是用了密钥混合、代换和置换。AES 在每一轮包括一个额外的线性变换 “MixColumn”

AES 的操作单元以字节为单位

AES 的SS 盒是有限域上的操作,也可以写为一个表

# 具体过程

  • 矩阵变换
  • 加轮密钥 (AddRoundKeys)
  • 字节变换 (SubBytes)
  • 行移位 (ShiftRows)
  • 列混淆 (MixColumns)
  • 加轮密钥 (AddroundKeys)

# 矩阵变换

将明文和密文变换成十六进制流放入 4x4 的矩阵中

# 加轮密钥

一轮变换明文M'_{i,j}=M_{i,j}\oplus K_

# 字节变换

通过查询SS 盒,Mi,jM'_{i,j} 中,高位为行,低位为列

19 中, 1 对应SS 盒的第二行, 9 对应SS 盒的第十列,查询SS 盒得到变换19d419 \rightarrow d4

剩下所有Mi,jM'_{i,j} 以此类推

# 行移位

如图所示,每行向左循环进行rowirow_i 单位的移位

# 列混淆

对于每一列用混淆矩阵来混淆,计算过程如图

用密钥解密的时候只需要用混淆矩阵的逆矩阵和密文计算即可

# 加轮密钥

与第一步相同,但此时的keykey 是经过一轮变换后的子密钥keyikey_i

子密钥计算过程

# 分组加密的工作模式

# ECB 模式

电子密码本(Electronic codebook,ECB 模式)是最简单的加密模式,需要加密的消息按照块密码的块大小被分为数个块,并对每个块进行独立加密,最后再直接拼接起来。

缺点:

  • 由于相同的块会被加密成同样的密文,所以并不能很好地隐藏数据模式
  • ECB 模式是确定性地加密方案,所以不是 CPA - 安全的
  • ECB 模式甚至不是 EAV - 安全的

# CBC 模式

密码分组链接模式(Cipher-block chaining,CBC 模式),在这个模式中,每个明文块先与前一个密文块进行异或后再进行加密。由于每个密文块都依赖于它前面的所有明文块,同时为了保证每条消息的唯一性,在第一块中需要使用初始化向量。

加密过程(若第一块下标为 1):

C_i=E_k(P_i)\oplus C_

C0=IVC_0 = IV

解密过程:

P_i = D_K(C_i)\oplus C_

C0=IVC_0 = IV

缺点:

  • 加密过程是串行的,无法并行化
  • 消息必须被填充到块大小的整数倍

加密时,明文中的微小改变都会导致后面的全部密文块发生改变,而在解密时,从两个邻接的密文块中即可得到一个明文块。因此,解密过程可以被并行化,而解密时,密文中一位的改变只会导致其对应的明文块完全改变和下一个明文块中对应位发生改变,不会影响到其它明文的内容。

# CFB 模式

密文反馈模式(Cipher feedback,CFB 模式)类似于 CBC 模式,可以将块密码变为自同步的流密码。它不用 DES 加密明文,而是把 DES 作为伪随机数生成器,把IVIV 作为种子。这样就可以从IVIV 和指定的 key 生成字节流,然后把明文与这个字节流异或。

为了利用 CFB 制作一种自同步的,可以处理任意位情况错误的流密码,需要使用一个与块的大小相同的移位寄存器,并用IVIV 将寄存器初始化。然后,将寄存器内容使用块密码加密,然后将结果的最高xx 位与明文的xx 进行异或,以产生密文的xx 位。下一步将生成的xx 位密文移入寄存器中,并对下面的xx 位明文重复这一过程。

加密过程:SiS_i 是移位寄存器的第ii 个状态,head(a,x)head(a,x) 是指aa 的高xx 位,nn 是指IVIV 的位数

Ci=head(EK(Si1),x)PiC_i = head(E_K(S_{i-1}),x)\oplus P_i

Pi=head(EK(Si1),x)CiP_i = head(E_K(S_{i-1}),x)\oplus C_i

Si=((Si1<<x)+Ci)mod2nS_i = ((S_{i-1}<<x)+C_i){\,\,}mod{\,\,}2^n

S0=IVS_0 = IV

简单来说,就是用 DES 加密初始向量IVIV 称为regreg,取高xx 位与明文异或获得密文,将这一组获得的密文接在regreg 去掉低xx 位后获得新的regreg' 并不断重复此过程。

优点:

  • 与 ECB,CBC 不同,CFB 不需要进行填充,因为是流模式

缺点:

  • 与 CBC 类似,加密过程是串行的,因此并不能并行化,解密可以使用并行化

# OFB 模式

输出反馈模式(Output feedback,OFB 模式)可以将块密码变成同步的流密码。它产生密钥流的块,然后将其与明文块进行异或,得到密文。

加密过程:

Ci=PiOiC_i = P_i \oplus O_i

Pi=CiOiP_i = C_i \oplus O_i

Oi=EK(Oi1)O_i = E_K(O_{i-1})

O0=IVO_0 = IV

# CTR 模式

计数器模式(Counter mode,CTR 模式)与 OFB 相似,CTR 将块密码变为流密码。它通过递增一个加密计数器以产生连续的密钥流,其中,计数器可以是任意保证长时间不产生重复输出的函数,但使用一个普通的计数器是最简单和最常见的做法。

计数器流由两部分组成,第一部分为 Nonce,必须保证每次加密都不同;第二部分为 Counter,即每次加密都进行加法操作的计数器。这两部分保证了每次加密的不同。

# 第四章 消息认证码和散列函数

# 消息认证码(MacMac

消息认证码是密码学的一个重要研究方向,是保证消息完整性的基本算法,利用密钥计算消息的认证信息。只有拥有密钥的发送方才能对该消息产生当前的认证信息。

消息算法包括三个子算法:

  • 密钥生成子算法GenGen —— 算法输入:安全参数nn;算法输出:满足特定分布的密钥kk
  • 消息认证码子算法MacMac —— 算法输入:密钥kk 和消息m{0,1}m \in \left\{0,1\right\}^*;算法输出:MacMac 标签tagtagtMac(k,m)t \leftarrow Mac(k,m)
  • 验证子算法VrfyVrfy —— 算法输入:密钥kk,消息mm,标签tt;算法输出:b=Vrfy(k,m,t)b=Vrfy(k,m,t) 验证通过为11,验证失败为00

正确性:Vrfy(k,m,Mac(k,m))=1Vrfy(k,m,Mac(k,m))=1

# 消息认证码的安全性

为了确定消息认证码的安全性,我们设计伪造实验:

敌手和消息认证算法获得安全参数nNn \in \mathbb{N},进行以下步骤

  1. 敌手A\mathcal{A} 发送消息mi{0,1}m_i \in \left\{0,1\right\}^*

  2. 消息认证算法计算Gen(n)Gen(n) 获得密钥kkMacMac 语言机计算标签tagi=Mac(k,mi)tag_i = Mac(k,m_i) 并返回给敌手A\mathcal{A},令QQ 表示所有敌手A\mathcal{A} 查询过的所有明文mim_i 的集合

  3. 敌手A\mathcal{A} 伪造出(m,t)(m^*,t^*)

  4. Vrfyk(m,t)=1Vrfy_k(m^*,t^*)=1mQm^* \notin Q,则敌手A\mathcal{A} 伪造实验成功,实验输出MacforgeA,Π(n)=1Mac-forge_{\mathcal{A},\Pi}(n)=1;否则输出MacforgeA,Π(n)=0Mac-forge_{\mathcal{A},\Pi}(n)=0

根据上面的实验,只要敌手A\mathcal{A} 能够伪造出明文 - 标签对的概率小于可忽略函数,那么这个消息认证码算法就是安全的

消息认证码方案Π=(Gen,Mac,Vrfy)\Pi = (Gen, Mac, Vrfy) 是安全的,如果对所有的 PPT 敌手\mathcal

Pr[MacforgeA,Π(n)=1]negl(n)\Pr[Mac-forge_{\mathcal{A},\Pi}(n)=1] \leq negl(n)

然而,消息认证码方案只保证了消息确实是从拥有密钥kk 的一方发送的。如果有控制了通信信道的中间人攻击,仍然可以重放、乱序或删除消息。

# 构造具体的消息认证码方案

# CBC-MAC

CBC-MAC 是运用 CBC 模式对消息m=(m1,m2,,mn)m=(m_1,m_2,…,m_n) 进行加密,获得的tagi=Mac(k,tagi1mi)tag_i = Mac(k, tag_{i-1} \oplus m_i)tag=tagntag = tag_n

以上的 CBC-MAC 叫做 Basic CBC-MAC,只适合于固定长的mm。攻击者可以建立m=(),tag=Mac(k,m)m' = ||(\oplus),{\,\,}tag = Mac(k, m') 来攻破加密方案

# 散列函数(HASH 函数)

散列函数(Cryptographic HASH Function)

  • 已知xx,计算y=f(x)y=f(x) 容易
  • 已知yy,计算xx 使得y=f(x)y = f(x) 困难
  • y 是定长的

HASH 函数产生的定长的输出又可称为 “摘要

HASH 函数的特点:

  • 任意给定hh,则很难找到MM 使得h=H(M)h=H(M) ,即给出 HASH 值,要求输入MM 在计算上是不可行的,即运算过程是不可逆的,这种性质称为函数的单向性,或抗原像攻击
  • 给定消息MM 和其 HASH 值H(M)H(M),要找到另一个MM',且MMM\not={M'},使得H(M)=H(M)H(M) = H(M') 在计算上是不可行的,这条性质被称为抗弱碰撞性,或抗第二原像攻击
  • 找到两个不同的消息MMM \not ={M'},使得它们的摘要值H(M)=H(M)H(M)=H(M'),在计算上是不可行的,这条性质被称为抗强碰撞性

# 构造 HASH 函数

# Merkle-Damgård 结构

Merkle-Damgård 结构(MD 结构)利用压缩函数进行迭代处理

MD 结构流程

MD 结构对输入消息进行填充,让消息变成固定长度的整数倍(比如 512 或 1024),通常是用 0 来填充。为了避免压缩函数删掉后面额外的 0 导致填充和不填充后的结果是一样的情况,要将第一个填充位改为 1。

在加密过程中,初始向量IVIVM1M_1 进行加密得到h1h_1h1h_1 再和M2M_2 进行加密,重复到最后输出 HASH 值

# Sponge 结构

海绵结构(Sponge 结构)利用置换ff 构造

Sponge 结构流程

海绵函数被分成左右两个部分,左边叫 “吸收部分”,右边叫 “输出部分”

海绵函数由statestate,函数ff,填充函数padpad 三个部分组成。state=r+cstate = r + cff 为置换函数

每一轮,statestate 中的rrbit 部分与消息mim_i 异或再进入ff 函数中置换,最后与cnc_n 拼接得到吸收部分的结果。

然后再通过输出部分获得最后结果

# 利用 HASH 函数构造 Mac 方案

直接使用Mac(k,m)=Hash(km)Mac(k,m) = Hash(k||m) 是不安全的,证明如下:

Mac(k,m1m2)=HASH(km1m2)=f(HASH(km1),m2)=f(Mac(k,m1),m2)\begin{matrix} Mac(k,m_1||m_2)\\ =HASH(k||m_1||m_2)\\ =f(HASH(k||m_1), m_2)\\ =f(Mac(k,m_1),m_2) \end{matrix}

注意到压缩函数ff 的构造是公开的,这意味着询问得到一个信息的 MAC 值之后可以往后计算任意消息的 MAC 值

一般比较常用的 HASH 构造 Mac 方案有:NMACHMAC,详细算法看 https://zh.wikipedia.org/wiki/HMAC

# 第五章 公钥密码学

到第五章之前学的所有密码学模型里面,加密采用的密钥与解密采用的密钥是相同的。我们称这类密码体制为对称密钥密码体制。

对称密码体制的缺点是加密方和解密方必须在传输密文前使用一个安全信道交换密钥,这在实际中很难实现。

同时,在共有NN 个用户的系统中,每个用户维护N1N-1 个密钥,整个系统中有N2N^2 量级的密钥,这样使得密钥的管理非常麻烦。

为此引入公钥密码体制,公钥密码体制中加密密钥和解密密钥不同,并且已知加密密钥无法计算得到解密密钥。

因此实体可以对外公布自己的加密密钥,其他实体就可以利用该加密密钥加密消息。由于其他实体没有解密密钥,因此无法解密密文,因此可以保证消息的私密性。

  • 一个密钥是加密密钥,发送者用来加密消息,是公开的,称为公开密钥
  • 另一个密钥是解密密钥,接收者用来解密恢复明文,是秘密持有的,称为解密密钥

# Diffie-Hellman 密钥交换算法

Diffie-Hellman 密钥交换算法基于离散对数的计算困难,因为离散对数的分布基本没有什么规律

离散对数:

GF(p)GF(p) 上,有一个原根gg. 现给定g,h0g,h\not={0},要求找出xx,使得

gxh(modp)g^x \equiv h \pmod p

我们称xx 为 " 以gg 为底,hh 的离散对数 ",记为logg(h)log_g(h)

Diffie-Hellman 密钥交换算法的思路:既然计算离散对数是困难的,那么只要把信息隐藏在离散对数中,通过传递gxg^x 可以使得窃听者无法获得xx

1.Alice 和 Bob 通过任意渠道,达成共识(g,p)(g,p). 其中pp 是一个质数,gg 是它的一个原根

2.Alice 想一个随机数aa,计算得到A=gaA=g^a,将AA 发送给 Bob

3.Bob 想一个随机数bb,计算得到B=gbB=g^b,将BB 发送给 Alice

4.Alice 得到BB 后,计算BaB^a 作为密钥

5.Bob 得到AA 后,计算AbA^b 作为密钥

通过上面的过程,很容易得到 Alice 和 Bob 得到的密钥是相同的,因为Ba=(gb)a=(ga)b=AbB^a = (g^b)^a = (g^a)^b = A^b

并且在这个过程中,窃听者只能获得gg,pp,AA,BB 四个信息,但通过这些信息无法简单计算出aabb 的值,也就无法计算出密钥,这样就完成了在被完全监听的信道中的安全密钥交换

# RSA 加密方案

公钥体系可以抽象成一种陷门单向函数

  • 单向:已知明文xx 和加密密钥kk 很容易计算出密文yy,但知道yy 和公钥kk 很难计算出明文xx
  • 陷门:已知密文yy 和解密密钥dd,可以很容易计算出明文xx. 解密密钥dd 是单向函数的陷门

RSA 密码体制定义如下:

N=p×qN=p \times q,其中ppqq 为素数。设M=C=Zn\mathcal{M} = \mathcal{C} = \mathbb{Z}_n,密钥K={(n,p,q,e,d):ed1(modϕ(n))}K = \left\{(n,p,q,e,d):ed \equiv 1 \pmod{\phi(n)}\right\},定义

  • 加密:EncK(x)=xe(modn)Enc_K(x) = x^e \pmod n
  • 解密:DecK(y)=yd(modn)Dec_K(y) = y^d \pmod n

公钥:nn,ee;私钥:pp,qq,dd

具体数学基础看 https://www.ruanx.net/rsa-intro/,下面只贴出相关 pdf 内容

RSA 算法具体过程:

生成两个大素数,ppqqpp\not =

npqn \leftarrow pq,且ϕ(n)(p1)(q1)\phi(n) \leftarrow (p-1)(q-1)

选择一个随机数e(1<e<ϕ(n))e(1<e<\phi(n)),使得gcd(e,ϕ(n))=1gcd(e,\phi(n))=1

de1modϕ(n)d \leftarrow e^{-1} \mod \phi(n)

公钥为(n,e)(n,e);私钥为(p,q,d)(p,q,d)

# OAEP vs. OAEP+

最优非对称加密填充(OAEP)经常与 RSA 加密一起使用的填充方案,填充流程如下:

已知三个函数,G()G(·),H()H(·),f()f(·)。其中GGHH 为随机预言(比如加密散列函数),ff 为单向陷门置换函数(比如 RSA 算法)

1. 用k1k_1 位长的00 串将消息mm 填充至nk0n-k_0 位的长度

2. 随机生成k0k_0 位长的串rr

3. 用GGk0k_0 位长的rr 扩展至nk0n-k_0 位长

4.X=(m00...00)G(r)X = (m||00...00) \oplus G(r)

5. 用HHnk0n-k_0 位长的XX 缩短至k0k_0 位长

6.Y=rH(X)Y = r \oplus H(X)

7. 输出f(XY)f(X||Y)

# 素性检测

# 初等数论基础

二次剩余:

对奇素数pp 和整数aaaa 是模pp 的二次剩余,如果a0modpa \not ={0} \mod p 且同余方程y2amodpy^2 \equiv a \mod p 有一个解yZpy \in \mathbb{Z}^*_p

Legendre 符号

(ap)={1,paa是模p的二次剩余1,paa不是模p的二次剩余0,pa\left(\frac{a}{p}\right) = \left\{ \begin{aligned} 1, & {\,\,\,\,\,\,\,\,}p \nmid a {\,\,} 且a是模p的二次剩余 & \\ -1,& {\,\,\,\,\,\,\,\,}p \nmid a {\,\,} 且a不是模p的二次剩余 & \\ 0, & {\,\,\,\,\,\,\,\,}p \mid a \end{aligned} \right.

Euler 准则:

pp 为一个奇素数,aa 为一个正整数

a(p1)/2(ap){1(modp),x2a(modp)有解1(modp),x2a(modp)无解a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \equiv \left\{ \begin{aligned} 1 \pmod p, & {\,\,\,\,\,\,\,\,} 若x^2 \equiv a \pmod p 有解 \\ -1\pmod p, & {\,\,\,\,\,\,\,\,} 若x^2 \equiv a \pmod p 无解 \end{aligned} \right.

费马小定理:

pp 为素数,aa 为任意自然数,则

apa(modp)a^p \equiv a \pmod p

gcd(a,p)=1gcd(a,p) = 1,则p(ap11)p | (a^{p-1} - 1),即

ap11(modp)a^{p-1} \equiv 1 \pmod p

二次探测定理:

pp 为素数,那么下面的同余方程仅有两个解,a=1a=1a=p1a = p - 1

a21(modp)a^2 \equiv 1 \pmod p

# Miller-Rabin 素性检测

根据费马小定理,设待检测的数为xx,偶数不用检测,下面只讨论xx 为奇数的情况

xx 为奇数,则x1x-1 为偶数,可以表示为2sd2^sd,其中dd 为奇数

所以可以将ax1a^{x-1} 表示为a^

我们已经知道对于奇素数xx,由费马小定理可知

a2sd1(modx)a^{2^sd} \equiv 1 \pmod x

对于modpmod{\,\,\,\,}p 意义下的(a20d,a21d,a22d,...,a2rd,...,22sd),0rs1(a^{2^0d},a^{2^1d},a^{2^2d},...,a^{2^rd},...,2^{2^sd}),{\,\,}0 \leq r \leq s - 1 序列,最后一位一定为11

根据二次探测定理,我们可以对这个序列进行检测,他们的解要么全都是11,要么在出现p1p-1 后全是11,且最后一位满足费马小定理

Miller-Rabin 素性检测基于上面的逆否,如果能找到这样一个aa 不满足上原理,那么xx 就不是素数,这样的aa 称为xx 是合数的一个凭证,否则aa 可能是证明xx 是素数的 “强伪证”。

# 第五章 离散对数问题和 ElGamal 密码体制

# ElGamal 密码体制

Elgamal 密码体制基于 Diffie-Hellman 密钥交换算法。

# 椭圆曲线加密

# 定义

# 初始定义

在密码学中,满足 Weierstrass 方程Y2=X3+AX+BY^2=X^3+AX+B 的点集

{(x,y)x,yy2=x3+ax+b}\left\{(x,y)|x,y \in y^2=x^3+ax+b \right\}

称为椭圆曲线

# 椭圆曲线上的加法定义

在椭圆曲线E:Y2=X3+AX+BE:Y^2=X^3+AX+B 假设有两个点PPQQ,则P+QP+Q 定义为:

连接PQPQ 形成一条直线,这条直线交于EERR 点,RR 关于xx 轴的对称点RR' 即为P+QP+Q 的结果

P+Q=RP+Q=R'

# 无穷远点

如果直线PQPQ 与椭圆曲线EE 的交点只有两个,那么P+QP+Q 就不成立。交点只有两个的情况是PPQQ 关于xx 轴对称。

为了解决这种情况,引入了无穷远点的概念。

假设P(x1,y1)P(x_1,y_1)Q(x1,y1)Q(x_1,-y_1) 的连线交EE 于某个无穷远点,记为O\mathcal{O},也就是说

P+Q=OP+Q=\mathcal{O}

无穷远点是单位元,有P+O=O+P=PP+\mathcal{O}=\mathcal{O}+P=P

# 模素数意义下的椭圆曲线定义

有了无穷远点后,我们可以给出在模素数意义下的椭圆曲线的真正定义

p>3p>3 且为素数,在Zp\mathbb{Z}_p 上的同余方程

y2x3+ax+b(modp)y^2 \equiv x^3 + ax + b \pmod p

的解集(x,y)Zp×Zp(x,y) \in \mathbb{Z}_p \times \mathbb{Z}_p,连同一个特殊的无穷远点O\mathcal{O},共同构成Zp\mathbb{Z}_p 上的椭圆曲线E:y2=x3+ax+bE:y^2=x^3+ax+b

其中a,ba,b 满足

4a3+27b204a^3+27b^2 \not={0}

为什么a,ba,b 需要满足4a3+27b204a^3+27b^2 \not={0} 呢?

如果4a3+27b2=04a^3+27b^2 = 0,椭圆曲线会存在奇点,无法用有限域上的加法运算,所以在实际运用中抛弃存在奇点的椭圆曲线

# 运算

Zp\mathbb{Z}_p 有限域上的椭圆曲线加法运算满足下列性质

有单位元:P+O=O+P=PP+\mathcal{O} = \mathcal{O} + P = P

有逆元:P+(P)=OP+(-P)=\mathcal{O},其中P-PPP 关于xx 轴的对称点

结合律:(P+Q)+R=P+(Q+R)(P+Q)+R = P+(Q+R)

交换律:P+Q+Q+PP+Q+Q+P

从而(E,+)(E,+) 是一个阿贝尔群,于是可以定义数乘运算

对于正整数nn 和椭圆曲线上的点PP,定义

nP=P+P+P++PnP = P + P + P + \dots + P

对于椭圆曲线上的点P(x1,y1)P(x_1,y_1)Q(x2,y2)Q(x_2,y_2)R(x3,y3)=P+QR(x_3,y_3) = P + Q 给出具体公式的交点计算如下

x3=λ2x1x2y3=λ(x1x3)y1\begin{aligned} x_3 & = \lambda^2 - x_1 - x_2\\ y_3 & = \lambda(x_1 - x_3) - y_1 \end{aligned}

λ={(y2y1)(x2x1)1PQ(3x12+a)(2y1)1P=Q\lambda = \left\{ \begin{aligned} & (y_2-y_1)(x_2-x_1)^{-1} & {\,\,\,\,\,\,\,\,} P \not={Q} \\ & (3x^2_1+a)(2y_1)^{-1} & {\,\,\,\,\,\,\,\,} P=Q \end{aligned} \right.

# 椭圆曲线的离散对数问题

经典的椭圆曲线上的离散对数问题,是给定PPnPnP,要推出nn 的值

EE 是有限域Zp\mathbb{Z}_p 上的椭圆曲线,P,QE(Zp)P,Q \in E(\mathbb{Z}_p). 椭圆曲线离散对数问题是指:找到一个整数nn 使得Q=nPQ=nP. 我们记

n=logP(Q)n = log_P(Q)

并称nn 是以PP 为底QQ 的椭圆曲线离散对数

举个例子,考虑Z73\mathbb{Z}_{73} 上的椭圆曲线

E:Y2=X3+8X+7E:Y^2 = X^3 + 8X + 7

其上有点P(32,53)P(32,53) 和点Q(39,17)Q(39,17). 通过计算可以得到Q=11PQ=11P,于是logP(Q)=11log_P(Q)=11

很明显,符合条件的nn 会有很多个,为了简化问题,我们定义PP是使得xP=yP,x>yxP=yP,x>y 的最小的s:=xys:=x-y,于是sPsP 显然就是无穷远点。

# 第六章 数字签名

# 定义

数字签名算法定义包括三个子算法

密钥生成 (KeyGen{\rm KeyGen})

  • 输入:安全参数nn
  • 输出:私钥sksk,公钥pkpk

签名 (Sig{\rm Sig})

  • 输入:私钥sksk 和消息mm
  • 输出:签名σSig(sk,m)\sigma \leftarrow \rm{Sig}(sk,m)

验证 (Vrfy{\rm Vrfy})

  • 输入:公钥pkpk,消息mm,签名σ\sigma
  • 输出:1/01/0. b=Vrfy(pk,m,σ)b=\rm{Vrfy}(pk,m,\sigma) 验证通过为 1,验证失败为 0.

正确性定义:

Vrfy(pk,m,Sig(sk,m))=1\rm{Vrfy}(pk,m,\rm{Sig}(sk,m))=1

# 数字签名安全模型

抵抗选择消息攻击 (CMA) 的数字签名算法 (Sig-forge 实验流程)

攻击者通过查询获得一些消息的签名,不能构造出没有查询过的消息的签名

Pr[SigforgeA,Π(n)=1]negl(n)\rm{Pr}[\rm{Sig} - \rm{forge}_{\cal{A},\Pi}(n)=1] \leq \rm{negl}(n)

# 常见数字签名算法

# RSA 签名方案

KeyGen\rm{KeyGen}. K={(n,p,q,a,b):n=pq,pq是素数,ab1(modϕ(n)),公钥(n,b),私钥(p,q,a)}\cal{K}=\left\{(n,p,q,a,b):n=pq,p和q是素数,ab \equiv 1 \pmod{\phi(n)},公钥(n,b),私钥(p,q,a)\right\}

Sig\rm{Sig}. 对于消息mm,用私钥计算mm 的签名

y=SigK(x)=xamodny = {\rm{Sig}}_{\cal{K}}(x)=x^a \mod n

Vrfy\rm{Vrfy}. 给定消息mm 和签名σ\sigma,用公钥验证

VrfyK(x,y)=1x=ybmodn{\rm Vrfy_{\cal{K}}}(x,y)=1 \iff x = y^b \mod n

# ElGamal 签名方案

KeyGen\rm KeyGen. 设αZp\alpha \in {\Bbb{Z}_p} 是一个生成元,P=Zp×Zp1{\cal{P}}={\Bbb{Z}^*_{p}} \times {\Bbb{Z}^*_{p-1}},定义

K={(p,α,b,β):β=αb,公钥是(p,α,β),私钥是b}{\cal{K}} = \left\{(p,\alpha,b,\beta):\beta = \alpha ^ b, 公钥是(p,\alpha, \beta), 私钥是b \right\}

Sig\rm Sig. 对于消息xx,选择一个秘密随机数rZp1r \in {\Bbb Z}^*_{p-1},计算

γ=αrmodp,δ=(xbγ)r1mod(p1)\gamma = \alpha ^ r \mod p, {\,\,\,\,}\delta = (x-b\gamma)r^{-1} \mod{(p-1)}

定义签名为

SigK(x,r)=(γ,δ){\rm Sig}_{\cal K}(x,r) = (\gamma, \delta)

Vrfy\rm Vrfy. 对于给定签名(γ,δ)(\gamma, \delta) 和消息xx

VrfyK(x,(γ,δ))=1βγγδ=αxmodp{\rm Vrfy}_{\cal K}(x,(\gamma,\delta))=1 \iff \beta ^ \gamma \gamma ^ \delta = \alpha ^ x \mod p

ElGamal 签名方案是非确定性的,也就是说对任意给定的的消息有很多有效的数字签名

如果泄露rr,且gcd(γ,p1)=1{\rm gcd}(\gamma, p - 1) = 1,则可以很容易算出私钥bb

βγγδαbγαrδαxmodpb=(xrδ)γ1mod(p1)\begin{aligned} &\beta ^ \gamma \gamma ^ \delta \equiv \alpha ^ {b \gamma} \alpha ^ {r \delta} \equiv \alpha ^ x \mod p \\ &\Rightarrow b = (x - r\delta)\gamma^{-1} \mod{(p-1)} \end{aligned}

# 数字签名算法 (DSA)

KeyGen{\rm KeyGen}. 设pp 是长为LLbit 的素数,在Zp{\Bbb Z}^*_p 上其离散对数问题是难解的,其中L0(mod64)L \equiv 0 \pmod{64}512L1024512 \leq L \leq 1024qq 是能被p1p-1 整除的160160bit 的素数,设αZp\alpha \in {\Bbb Z}^*_p11ppqq 次根。定义

K={(p,q,α,b,β):βαb(modp)}{\cal K} = \left\{(p,q,\alpha,b,\beta): \beta \equiv \alpha ^ b \pmod p \right\}

其中0bq10 \leq b \leq q - 1p,q,α,βp,q,\alpha,\beta 是公钥,bb 是私钥

Sig.{\rm Sig.} 对于消息xxK={(p,q,α,b,β):βαb(modp)}{\cal K} = \left\{(p,q,\alpha,b,\beta): \beta \equiv \alpha ^ b \pmod p \right\} 和一个秘密随机数rZpr \in {\Bbb Z}^*_p1rq11 \leq r \leq q - 1,计算

γ=(αrmodp)modqδ=(SHA1(x)+bγ)r1modq\begin{aligned} &\gamma = (\alpha ^ r \mod{p}) \mod{q}\\ &\delta = ({\rm SHA-1}(x)+b\gamma)r^{-1} \mod{q} \end{aligned}

定义签名为

SigK(x,r)=(γ,δ){\rm Sig}_{\cal K}(x,r) = (\gamma, \delta)

Vrfy.{\rm Vrfy.}x{0,1},γ,δZqx \in \left\{0,1\right\}^*,\gamma,\delta \in {\Bbb Z_q},验证通过下面计算完成

e1=SHA1(x)δ1modqe2=γδ1modqVrfyK(x,(γ,δ))=1(αe1βe2modp)modq=γ\begin{aligned} e_1 & = {\rm SHA-1}(x)\delta^{-1} \mod{q}\\ e_2 & = \gamma \delta^{-1} \mod{q}\\ {\rm Vrfy}_{\cal K}(x,(\gamma, \delta)) = 1 & \iff (\alpha ^ {e_1} \beta ^ {e_2} \mod{p}) \mod{q} = \gamma \end{aligned}

# Schnorr 签名方案

KeyGen.{\rm KeyGen.}pp 是使得Zp{\Bbb Z}^*_p 上离散对数问题难题的一个素数,qq 是能被p1p-1 整除的素数。设αZp\alpha \in {\Bbb Z}^*_p11ppqq 次根,h:{0,1}Zqh:\left\{0,1\right\}^* \rightarrow {\Bbb Z}_q 是一个安全的Hash{\rm Hash} 函数,定义

K={(p,q,α,b,β):βαb(modp)}{\cal K} = \left\{(p,q,\alpha,b,\beta):\beta \equiv \alpha ^ b \pmod{p}\right\}

其中0bq10 \leq b \leq q - 1p,q,α,βp,q,\alpha,\beta 是公钥,bb 是私钥

Sig.{\rm Sig.} 对于消息xxK={(p,q,α,b,β):βαb(modp)}{\cal K} = \left\{(p,q,\alpha,b,\beta):\beta \equiv \alpha ^ b \pmod{p}\right\} 和一个秘密随机数rZpr \in {\Bbb Z}^*_p1rq11 \leq r \leq q - 1,计算

γ=h(xαrmodp)δ=r+bγmodp\begin{aligned} &\gamma = h(x||\alpha ^ r \mod{p})\\ &\delta = r + b\gamma \mod{p} \end{aligned}

定义签名为

SigK(x,r)=(γ,δ){\rm Sig}_{\cal K}(x,r)=(\gamma, \delta)

Vrfy.{\rm Vrfy.}x{0,1},γ,δZqx \in \left\{0,1\right\}^*,\gamma,\delta \in {\Bbb Z_q},验证通过下面计算完成:

VefyK(x,(γ,δ))=1h(xαδβγmodp)=γ{\rm Vefy}_{\cal K}(x,(\gamma, \delta)) = 1 \iff h(x||\alpha^\delta\beta^{-\gamma} \mod{p}) = \gamma

# 椭圆曲线数字签名算法 (ECDSA)

KeyGen.{\rm KeyGen.}pp 是一个大素数,EE 是定义在Fp{\Bbb F}_p 上的椭圆曲线。设AAEE 上阶为qqqq 为素数)的一个点,使得<A><A> 上的离散对数问题是个困难问题。定义:

K={(p,q,E,A,m,B):BmA,mZq}{\cal K} = \left\{(p,q,E,A,m,B):B \equiv mA, m \in {\Bbb Z}_q\right\}

其中0mq10 \leq m \leq q - 1p,q,E,A,Bp,q,E,A,B 是公钥,mm 是私钥

Sig.{\rm Sig.} 对于消息xxK={(p,q,E,A,m,B):BmA,mZq}{\cal K} = \left\{(p,q,E,A,m,B):B \equiv mA, m \in {\Bbb Z}_q\right\} 和一个秘密随机数kZqk \in {\Bbb Z}^*_q1kq1