Crypto笔记

Introduction

凯撒移位密码：key space太小

单字母替代密码：一个字母的加密方式总是一样的，统计攻击破解，如果我们知道一个字母在明文中出现的频率，就可以极大缩小明文的搜索空间

替代方法：多字母替换

維吉尼亞密碼 or 多字母移位密碼：是多密码替换的特殊情况 破解方式：先确定加密密钥的长度m，然后break出m个加密密钥（统计攻击破解）

Perfect Secrecy（完美保密性）

Defining an encryption scheme

密文空间 M 上的一个加密算法 (Gen, Enc, Dec) 是完美保密的，如果对于 M 上的每个分布都有 \(Pr[M=m|C=c]=Pr[M=m]\)，对于每个 \(m \in M\) 和每个 \(c \in C\)，且 \(Pr[C = c] > 0\)。

可以用贝叶斯公式等完成证明；

完美保密性含义：不会因为知道密文而获取到明文的任何信息。

一个等效的完美保密性的定义:

一种加密方案 (Gen, Enc, Dec) 在消息空间 M 上是完全保密的，当且仅当对于每个 m, m′ ∈ M 和每个 c ∈ C：\(Pr[C = c|M = m] = Pr[C = c|M = m′]\)

密文的分布相对于明文是独立的

完美不可分辨性：

A向B发送两组明文\(m_1,m_2\),B通过Gen获取一个密钥k，并均匀随机的抽取明文中的其中一个n进行加密，将加密后的密文传给A。通过获取到的密文c，A猜测n是第一位还是第二位。如果猜对了，则\(PrivK^{eav}_{A,\Pi}=1\) 有完美保密性当且仅当有完美不可分辨性

一次一密：

只有密码只使用一次和只知密文时有保密性

完美保密性的限制：

必须要求|K|>=|M|

香农定理：

一个加密算法，有|M|=|K|=|C|,当且仅当满足下列性质时，算法是完美保密的： Gen选取密钥是对于每一个密钥k，都以相同的概率\(\frac{1}{|K|}\)获取 对于每一个明文m和密文c，存在一个唯一的密钥k，使得\(Enc_k(m)\) 输出c

计算安全理论

计算安全性的渐进方法 有效的对手 = 随机算法 + 多项式时间 有界 = 概率多项式时间Probabilistic Polynomial-Time（有界）算法= PPT 算法

一个从自然数到非负实数的函数 negl(·) 是可忽略的，如果对于每一个正多项式 p，都存在一个 N，使得对于所有整数 \(n > N，negl(n) < 1/p(n)\)。 一个从自然数到非负实数的函数 negl(·) 是可忽略的，如果对于每一个正整数 c，都存在一个 \(N_c\)，使得对于所有整数 \(n > N_c，negl(n) < 1/n^c\)。

设\(negl_1\) 和 \(negl_2\)是可忽略函数。那么， 1. 如果存在一个整数 \(N_c\) 使得对于所有 \(n ≥ N_c，f(n) < negl_1(n)\) 成立，则 f(n) 是可忽略的。

2. 函数 \(negl_3(n) = negl_1(n) + negl_2(n)\) 也是可忽略的。

3. 对于任何正多项式 p，定义函数 \(negl_4\) 为 \(negl4(n) = p(n) · negl_1(n)\)，则 \(negl_4\) 也是可忽略的。

常见的可忽略函数

\(2^{-n},2^{-\sqrt{n}},n^{-logn}\)都是可以忽略的

一个方案是安全的，如果对于每一个多项式时间有界对手 A 进行某种形式上指定类型的攻击，A 成功攻击的概率是可忽略的。

等价定义：一个方案是安全的，如果对于每一个多项式时间有界对手 A 进行某种形式上指定类型的攻击，并且对于每一个正多项式 p，存在一个整数 N，使得当 n > N 时，A 成功攻击的概率小于 \(\frac{1}{p(n)}\)。

indistinguishable encryptions in the presence of an eavesdropper or EAV-secure

对于任意n，存在一个可以忽略的函数negl，使得 \[Pr[PrivK^{env}_{A,\Pi}=1]\leq \frac{1}{2}+negl(n)\] 一个等效的定义： \[Pr[out_A(PrivK^{env}_{A,\Pi}(n,0))=1]-Pr[out_A(PrivK^{env}_{A,\Pi}(n,1))=1]\leq negl(n)\] 其中\(PrivK^{env}_{A,\Pi}(n,b)\)表示在不可区分性实验中使用一个固定的b，并且out代表A的输出。

构建在计算上安全的加密

伪随机数发生器

令l(·)是一个多项式，令G是一个确定多项式时间算法，该算法满足：对于任意输入\(s=\{0,1\}^n\),算法输出一个长度为l(n)的字符串，如果满足下列两个条件，则称G是一个伪随机发生器：

1.扩展性：对于每个n来说，l(n)>n

2.伪随机性：对于所有的概率随机性多项式时间的区分器D来说，存在一个可忽略函数negl，满足 \[|Pr[D(r)=1]-Pr[D(G(s))=1]|\leq negl(n)\] 其中r是从\(\{0,1\}^l(n)\)中均匀随机选择的，种子s是从\(\{0,1\}^n\)中选择的。

用伪随机数发生器构造的一次一密是EAV安全的

证明方法是用规约，已知伪随机数发生器和真随机之间是eav安全的，无法用PPT算法来分辨，那么：

假设构造的一次一密\(Pr[Privk^{eav}_{A,\pi}=1]=\frac{1}{2}+\epsilon(n)\)

我们要证\(\epsilon(n)\leq negl(n)\),否则存在一个算法可以区分伪随机数和真随机

于是通过这两种一次一密构建了一个区分器D

当w=r时，\(Pr[D[w]=1]=Pr[D[r]]=Pr[Privk^{eav}_{A,\hat{\pi}}=1]=\frac{1}{2}\)

当w=G(n)时，\(Pr[D[w]=1]=Pr[D[G[n]]=1]=Pr[Privk^{eav}_{A,\pi}=1]=\frac{1}{2}+\epsilon(n)\)

其中第二个等号成立，是由于D就是由A构造出来的函数，通过A的输出来充当D的输出，所以两个函数的输出其实是相同的。

所以\(|Pr[D[r]]-Pr[D[G[n]]]|=\epsilon(n)\)

由伪随机数发生器的定义，\(\epsilon(n)\leq negl(n)\)

所以构造出来的一次一密\(Pr[Privk^{eav}_{A,\pi}=1]=\frac{1}{2}+\epsilon(n)\leq \frac{1}{2} + negl(n)\)

流密码

流密码是一种确定性的算法，分为两步：

初始化Init：输入一个随机种子s和一个可选的初始化向量IV，输出一个初始化状态\(St_0\)

获取密码Getbits：输入前一个状态\(St_{i-1}\),输出当前状态\(St_t\)和获取到的密钥流\(y_i\)

优点：简单高效，可以加密任意长度的明文

缺点：不能用相同的密钥流加密明文，否则容易发现明文之间的相关性，容易受到字节翻转攻击

同步模式: 双方使用密钥流的不同部分来加密每个信息。在这个模式下，双方必须同步通讯，来得知流的多少位已经被使用。这个算法虽然是确定性的，但在每一次加密过程中，密钥是互不重复的，因此对于每次加密来说，相同的明文也会被加密成不同的密文。

非同步模式： 双方可以独立进行加密，无需维护状态。但是，这里需要 PRG 有两个输入：一个种子k以及一个初始向量IV. 如果两个初始向量不一样，那么 PRG 的生成结果也不一样。

在非同步模式下，加密方法为\(Enc_k(m)=<IV,G(k,IV)\oplus m>\) 其中IV是随机选择的，与异或结果一同输出，攻击者能得到IV，但是由于没有种子k，所以依然没法解密。

线性反馈移位寄存器（LFSR）

一个n位的寄存器有n个寄存器\(s_{n-1}...s_{0}\)和n个反馈常数\(c_{n-1}...c_0\)

当前状态即为n个寄存器里面值的集合，下一个状态为： 对于低n-1位，直接把上面一位向右移一位，对于最高位，是将原先所有的n位寄存器中的值和反馈常数相乘之后进行异或操作。

输出是字节序列\(s_0^{(0)},s_0^{(1)}...\)

缺点：一个n位的线性反馈移位寄存器，在最多\(2^n\)次移位后就会重复原先的序列。由于线性，一个4位的寄存器在接受到前八位输出后就能破解刚开始的状态和反馈常数。

增加非线性

为了防止上面的破解方法，可以在GetBits函数中生成状态或者获得bit时引入非线性 在私钥加密中，块密码比流密码更加安全

CPA安全和伪随机函数

多消息窃听者实验：\(Privk^{mult}_{A,\Pi}(n)\)

敌手A被给定一个输入\(1^n\),输出一对消息向量\(\vec{M}_0=(m_0^1...m_0^t)\)以及\(\vec{M}_1=(m_1^1...m_1^t)\)

通过运行\(Gen(1^n)\)生成一个密钥k和选择一个随机比特b，对所有i，计算密文\(c^i\gets Enc_k(m_b^i)\),并且把密文向量\(\vec{C}=(c^1...c^t)\)给A

A输出一个比特b'进行比较。

窃听者存在的情况下不可区分多次加密

一个对称密钥加密方案\(\Pi\),如果对所有的概率多项式时间敌手A，存在一个可忽略函数negl,满足 \(Pr[Privk^{mult}_{A,\Pi}=1]\leq \frac{1}{2}+negl\)

则称其具有窃听者存在的情况下不可区分多次加密

命题：存在这样的对称加密方案，满足窃听者存在情况下不可区分的加密，但不满足窃听者存在情况下不可区分的多次加密。

需要概率加密。

选择明文攻击(CPA)的安全性

CPA的想法是增强了敌手的能力，原先敌手只能被动的接受信息，现在敌手可以主动的访问加密机。

CPA不可区分实验\(Privk^{CPA}_{A,\Pi}(n)\),敌手可以要求语言机加密消息\(m_0、m_1\),从而获得\(c_0 \gets Enc_k(m_0)\)和\(c_1 \gets Enc_k(m_1)\)

必须要把随机性作为加密过程的一部分，确保相同消息加密后密文是不同的。

伪随机函数

如果一个函数\(F_k\)(对于一个均匀随机密钥k)，与一个均匀随机函数是不可区分的，那么我们称这个函数是伪随机函数。

正式定义：对于一个长度保持的密钥函数\(F:(0,1)^{l_{key}(n)}\times(0,1)^{l_{in}(n)}\to (0,1)^{l_{out}(n)},l_{key}(n)=l_{in}(n)=l_{out}(n)=n\),f是一个均匀随机函数，F是一个伪随机函数如果对于所有的PPT 区分器D，都有一个可忽略函数negl使得 \[|Pr[D^{F_k(\cdot)}(1^n)=1]-Pr[D^{f(\cdot)}(1^n)=1]|\leq negl(n)\]

随机函数接受两个输入，一个是密钥k，另一个是输入x，对于n位长的真随机函数，其规模是\(2^{n2^n}\),而对于密钥长度为n的伪随机函数，其规模是\(2^n\).如果

基于伪随机函数构造CPA安全加密

令F是伪随机函数，定义一个消息长度为n的对称密钥加密方案如下：

Gen：输入\(1^n\),均匀随机选择\(k \gets \{0,1\}^n\),并将其作为密钥输出。

Enc:输入密钥k，以及一个消息\(m\in \{0,1\}^n\),均匀随机选择随机数\(r\gets\{0,1\}^n\),输出密文 \(c:=<r,F_k(r)\oplus m>\)

Dec:输入一个密钥\(k\in \{0,1\}^n\),以及一个密文c=<r,s>,输出明文消息 \(m:=F_k(r)\oplus s\)

如果F是伪随机函数，则构造方案如上的消息长度为n的定长对称密钥加密方案在CPA下具备不可区分加密。

令\(\hat{\Pi}\)为用真随机函数f取代Fk的构造方法。

敌手A对他的加密预言机问询q(n)次，有\(Pr[Privk^{cpa}_{A,\hat{\Pi}=1}]\leq \frac{1}{2}+\frac{q(n)}{2^n}\)

同样构造区分器D

D被指定了输入\(1^n\)以及可以访问预言机\(O:\{0,1\}^n \to \{0,1\}^n\)

运行A(1^n),用下面方式回答问询：

1.均匀随机选择\(r\gets \{0,1\}^n\) 2.问询O(r),获得s'

3.返回密文\(<r,s'\oplus m_b>\)

当A输出两个消息m，随机选择一个比特b

1.均匀随机选择r

2.问询O(r),获得相应s'

3.返回挑战密文\(<r,s'\oplus m_b>\)

最后A输出一个b'

有\(Pr[D^{F_k(\cdot)}(1^n)=1]=Pr[Privk^{cpa}_{A,\Pi}(n)=1]=\frac{1}{2}+\epsilon(n)\)

\(Pr[D^{f(\cdot)}(1^n)=1]=Pr[Privk^{cpa}_{A,\hat{\Pi}}(n)=1]=\frac{1}{2}+\frac{q(n)}{2^n}\)

\(|Pr[D^{F_k(\cdot)}(1^n)=1]-Pr[D^{f(\cdot)}(1^n)=1]|=\epsilon(n)-\frac{q(n)}{2^n}\) 证毕

任意CPA安全的加密方案对多次加密也是安全的

排序和伪随机排序

设\(Perm_n\)是\(\{0,1\}^n\)所有排列的集合，则\(Perm_n\)的规模是\((2^n)!\)

一个伪随机排列就是输入一个k和x，输出y，并且没有一个有效的方法来区分这个排列和随机选择的函数，则称这个排列是一个伪随机排列。因为这两者看上去是相同的，除非能找到一对不同的值x和y，使得f(x)=f(y)

当一个伪随机排列的长度足够长，那么他和一个伪随机函数是不可区分的，即如果F是一个伪随机排列。且\(I_{in}>n\),那么F也是一个伪随机函数。

强伪随机排列

如果给区分器使用逆排序预言机的能力，其依然无法区分\(F_k\)和一个随机置换，则称F是强伪随机置换。

\(F:\{0,1\}^*\times \{0,1\}^*\to \{0,1\}^*\)是一个有效的带密钥的置换，如果对于所有多项式时间区分器D，存在一个可忽略函数negl,使得 \[|Pr[D^{F_k(\cdot)F_k^{-1}(\cdot)(1^n)}=1]-Pr[D^{f(\cdot)f^{-1}(\cdot)(1^n)}=1]|\leq negl(n)\] 则称F是强伪随机置换

PRFs and PRGs相互构造

分组密码Block Cipher

分组密码是一个高效的、含k输入的排列函数

\(F:\{0,1\}^n\times \{0,1\}^l\to \{0,1\}^l\)

F就是一个含k的排列函数，高效体现在给定k，可以很快计算出\(F_k(x)\)和他的逆\(F_k^{-1}(x)\),n是键长，l是块长

无论是分组密码还是流密码，其本身都不是一个加密的方式，其提供了一种操作模式

分组密码+操作方式=长信息加密方式

常见的操作方式有：

电子代码簿Electronic Code Book（ECB）模式；

密码块链接Cipher Block Chaining（CBC）模式；

输出反馈Output Feedback（OFB）模式；

计数器Counter（CTR）模式。

让m代表明文，\(m_1,m_2...m_l\)代表明文块

ECB模式

ECB模式很简单，就是\(c:=<F_k(m_1),F_k(m_2)...F_k(m_l )>\)

安全性：由于是确定性算法，所以不是CPA安全的，不安全，永远不应该被应用。

CBC模式

第一段密文\(c_0\)赋值为一个随机数IV，然后逐个生成后面的密文：

\(c_i:=F_k(c_{i-1}\oplus m_i)\) for i=1...l

生成密文\(<c_0,c_1...c_l>\)

解密要用\(F_k^{-1}\)

\(m_i:=F_k^{-1}(c_i)\oplus c_{i-1}\)

分析：这个加密是概率性的，如果F是一个伪随机函数，那么CBC是CPA安全的，缺点是加密过程不能并行进行。

OFB模式

加密时生成一个随机串IV，为加密的每个块生成一个随机密码

\(y_0:=IV,y_i=F_k(y_{i-1})\),然后与明文块进行异或操作：\(c_i=m_i\oplus y_i\)

密文是\(<IV,c_1,c_2...c_l>\)

分析：\(F_k\)不需要逆运算，如果F是伪随机函数，那么OFB模式是CPA安全的，同时支持预先操作，把要用的随机密码提前生成出来

CTR模式

在加密时生成一个随机数ctr，以如下方式为每一个块产生随机密码：

\(y_i=F_k(ctr+i),c_i=y_i\oplus m_i\),生成的密文是\(<ctr,c_1,...c_l>\)

分析：如果F是伪随机函数，那么是CPA的，并且支持并行计算。

设计分组密码

The avalanche effect一个好的分组密码应该有雪崩效应

输入改变一点点必须要影响输出的每一位

SPN: Substitution-Permutation Networks替换排列网络

SPN满足confusion-diffusion paradigm(混淆扩散范式)

重复多次混淆步骤和扩散步骤：

分组密码的输入被分成了若干小块，每一轮，先把每一个小块输入到一个随机排列中，再使用一个混合排列把所有小块混合到一起

SPN是基于上面范式的变体来运行的：

1.key mixing：在每一回合中，先将输入和子密钥(sub-key or round-key)进行异或操作

2.substitution:在进行key mixing后，每一个子块i被输入到一个固定的，可逆的替换函数\(S_i\)(S盒)中

3.Permutation：S盒的所有输出进行排列

替换步骤和排列步骤的细节都是公开的，任何攻击者都可以知道。只有钥匙被保密。（这种设置被称为克霍夫原理）

输出是最后一次进行key mixing后的结果，即先进行上面三步r次，最后再进行一次key mixing。

Feistel network

与SPN的区别是不需要函数可逆

第i次round function \(\hat{f_i}\)有两个输入，一个是子密钥\(k_i\)，另一个是一个\(\frac{l}{2}\)长的字串，输出一个同样长度的字串。定义\(f_i(R)=\hat{f_i(k_i,R)}\)

加密流程：

\(L_i=R_{i-1}\)

\(R_i=L_{i-1}\oplus f_i(R_{i-1})\)

解密流程：

\(R_{i-1}=L_i\)

\(L_{i-1}=R_i\oplus f_i(R_{i-1})\)

\(\hat{f_i}\)是固定的，并且是公开的，但是\(f_i\)不是。

分组密码样例

DES

缺点：key太短

3DES

实现112位安全，但是现在推荐最短长度为128，所以推荐用AES替代

AES

128-bit block length.

supports 128-bit (10 rounds), 192-bit (12 rounds), 256-bit(14 rounds)keys.

消息验证

加密无法完成消息认证的完整性测试

消息鉴别码(MAC)

消息鉴别码(MAC)是一个概率多项式时间算法三元组(Gen Mac Vrfy)满足：

Gen输入参数\(1^n\),输出密钥k，\(|k|\geq n\)

Mac输入k和消息m，输出t，算法是随机的，即\(t\gets Mac_k(m)\)

Vrfy输入密钥k，消息m和标记t，输出比特位b。\(b:=Vrfy_k(m,t)\)

消息鉴别码的安全性

如何是攻破一个MAC方案？

如果敌手能够输出任意消息以及标记，满足：

1.t是消息m的有效标记，即Vrfy(m,t)=1

2.敌手在之前没有获得过m的MAC标记（重放攻击并不被认为是攻破了消息鉴别码）

消息鉴别码实验\(Mac-forge_{A,\Pi}(n)\)

1.运行Gen获得一个随机密钥k

2.敌手获得输入值\(1^n\),并能够访问预言机\(Mac_k()\),最后输出一对(m,t)的值，并用\(Q\)表示所有\(A\)对预言机的询问集合

3.实验输出结果为1，当且仅当Vrfy(m,t)=1,\(m\notin Q\)

如果没有敌手能在上述实验中以不可忽略概率成功，则认为Mac是安全的

消息认证码\(\Pi =(Gen，Mac，Vrfy)\)在自适应选择消息攻击下是不可避免的或者安全的，如果对所有PPT敌手A，都有一个不可忽略函数negl使得\(Pr[Mac-forge_{A,\Pi}(n)=1]\leq negl(n)\)

一个安全的MAC可以确保对手不能在任何以前从未进行过身份验证的新消息上生成有效的标记。

然而上面的定义只能保证在面对新消息时敌手不能产生一个合法的标记，但是并不能保证在原先见过的消息中不能产生一个合法的新标记。一个强安全的MAC可以破解如上的弱点。

定义一个相似的实验叫做\(Mac-sforge_{A,\Pi}(n)\)

1.产生一个随机的k

2.2.敌手获得输入值\(1^n\),并能够访问预言机\(Mac_k()\),最后输出一对(m,t)的值，并用\(Q\)表示所有\(A\)对预言机的询问的对的集合，这里的对指的是消息m和对应的标记t

3.实验输出结果为1，当且仅当\(Vrfy_k(m,t)=1,(m,t)\notin Q\),写作\(Mac-sforge_{A,\Pi}(n)=1\)

一个MAC是强的，如果对所有PPT敌手A，有\(Pr[Mac-sforge_{A,\Pi}(n)=1]\leq negl(n)\)

如果有时候需要发相同的消息，但是该消息已经在原先被发送过了，这样接收者在收到这个消息时会拒绝这样的消息。解决方案有如下两种：

第一种是在加密过程中加入序列号，对i||m进行加密

第二种是加入一个时间戳，将时间戳给负在加密过程中

构造安全MAC

构造一个定长的MAC：

用Gen生成一个密钥k，存在一个函数l，Mac只对\(m \in \{0,1\}^{l(n)}\)有定义，我们把这种加密称作对消息长度为l(n)的消息的定长MAC。

如果MAC的标记t是通过一个PRF获得的，那么对于一个原先未经身份验证的消息伪造标记需要对手在一个新的输入上正确猜测PRF的输出，然而这对任何PPT的对手都是不可行的。

于是可以进行以下构造：

Mac：在输入key \(k\in \{0,1\}^n\),消息\(m \in\{0,1\}^n\),输出\(t:=F_k(m)\)

Vrfy:在输入key \(k\in \{0,1\}^n\),消息\(m \in\{0,1\}^n\),标记t$ {0,1}^n$,输出1 iff \(t=F_k(m)\)

对长消息进行身份验证

对长消息分块后分别进行MAC，在ppt中提到了三种方式，但都是不安全的，具体内容可以重新阅读ppt；通常用的方式是CBC-MAC，但在对不同长度的消息进行身份验证时可能也是不安全的，在这种情况下可以使用CBC-MAC的变体，具体内容在ppt没有提及。

CBC-MAC

令F是一个PRF，固定长度函数l：

Mac:k，m=l(n)·n

把m分成等长的块：\(m=m_0m_1...m_l\)

令\(t_0:=0^n\),然后从i=1到l:

\(t_i:=F_k(f_{i-1}\oplus m_i)\)

输出\(t_l\)作为标签

Vrfy:输入是k，m，t 如果m的长度不是l(n)·n,输出0，否则当且仅当\(t=Mac_k(m)\)时输出1.

CBC-MAC v.s. CBC-mode encryption

MAC不适用一个随机的初始串IV，并且只输出最后一个块

身份验证的加密 Authenticated Encryption

目的是同时完成对消息的加密和对身份的验证

A private-key encryption is an authenticated encryption scheme if it is CCA-secure and unforgeable.即一个私钥加密方案是身份验证加密如果他是CCA安全的并且是不可伪造的

CCA安全

CCA不可分辨性实验：

\(Privk^{cca}_{A,\Pi}(n)\):

1.通过Gen(\(1^n\))生成一个密钥k

2.敌手给定输入\(1^n\),也可以访问神预机的加密和解密\(Enc_k,Dec_k\),输出一对等长消息\(m_0,m_1\)

3.随机选择一个比特位，然后生成挑战密文\(c\gets Enc_k(m_b)\)并发送给A

4.敌手继续访问神预机，但是不允许对挑战密文本身进行询问。最终，敌手输出b'.如果b=b',则输出1，否则输出0.

一个加密方法在选择明文攻击下有完美不可分辨性，或者CCA安全，如果对所有的PPT敌手都有一个可忽略函数negl，有

\(Pr[Privk^{cca}_{A,\Pi}(n)=1]\leq \frac{1}{2}+negl(n)\)

到目前为止所有提到的加密方案都不是CCA安全的。CCA安全意味着不可延展性，如果敌手想去修改一个密文，要么这个密文是不合法的，要么是一个和原先的明文没有任何关系的明文所对应的密文。

消息完整性实验

\(Enc-forge_{A,\Pi}(n)\):

1.通过Gen(\(1^n\))生成一个密钥k

2.敌手给定输入\(1^n\),也可以访问神预机的加密\(Enc_k\),输出一个密文c

3.令\(m=Dec_k(c)\),令Q是A所有询问结果的集合 这个实验输出1当且仅当(1).$m\(,即解密失败 (2).\)m Q$(即m还没有被询问过)

一个私钥加密方案是不可伪造的如果对所有的PPT敌手，都有一个可忽略函数negl使得

\(Pr[Enc-forge_{A,\Pi}(n)=1]\leq negl(n)\)

构造AE

基础想法是结合一个CPA安全加密方案和一个MAC方案来构造AE。有三种方法来实现这个想法： 令\(\Pi_E=(Enc,Dec)\)是任意一个CPA安全的加密方案，\(\Pi_M=(Mac,Vrfy)\)是任意一个强MAC的方案

Encrypt-and-authenticate.

发送方和接受方使用同样的密钥

\(k_E\gets^{\$}\{0,1\}^n\),\(k_M\gets^{\$}\{0,1\}^n\)

对于消息m，发送者计算

\(c\gets Enc_{k_E}(m),t\gets Enc_{k_M}(m)\)

把\((c,t)\)发送给接收者

接收者解密c获得m，假设没有错误，这时再验证标记t，如果\(Vrfy(m,t)=1\),则输出m，否则输出error。

缺点：消息保密不一定受到保护（因为安全的MAC不保证任何保密）。具体来说，加密和身份验证方案对于选择明文攻击可能是不安全的（因为在实践中使用的大多数MAC都是确定性的）。

Authenticate-then-encrypt

发送方和接受方使用同样的密钥

\(k_E\gets^{\$}\{0,1\}^n\),\(k_M\gets^{\$}\{0,1\}^n\)

对于消息m，发送者计算

\(t\gets Enc_{k_M}(m),c\gets Enc_{k_E}(m||t)\)

把\((c,t)\)发送给接收者

接收者解密c获得m||t，假设没有错误，这时再验证标记t，如果\(Vrfy(m,t)=1\),则输出m，否则输出error。

缺点：密文完整性没有得到保护，因此敌手可以操纵密文，此外，接受者必须先解密密文，才能获知消息是否真实。这种方案不应该被使用

Encrypt-then-authenticate

Gen:\(k_E\gets^{\$}\{0,1\}^n\),\(k_M\gets^{\$}\{0,1\}^n\)

Enc:对于消息m，发送者计算\(c\gets Enc_{k_E}(m)\)，\(t\gets Enc_{k_M}(c)\)

把\((c,t)\)发送给接收者

Dec:输出error如果\(Vrfy(c,t)\neq 1\),否则输出\(Dec_{k_E}(c)\).

如上构造是一种经过认证的加密方案

\(\Pi_M\)直接说明了如上的加密方案是不可伪造的

如上构造的CCA安全降低到\(\Pi_E\)CPA安全性。

这是构造AE的最理想的方法。

哈希函数

有时候我们需要把一个长字符串压缩成一个短的字符串，这样我们就用到哈希函数（有时叫做消息摘要函数）

我们使用哈希函数进行密码学的实际应用中，应该满足如下两个条件

1.抗碰撞： 我们应该难以找到\(m_0,m_1\),使得\(hash(m_0)=hash(m_1)\)

2.完全不可预测： 应该和一个随机的映射是不可区分的

哈希函数\(H^s(x)=H(s,x)\),一般s是不保密的

哈希函数的形式化定义(Gen,H),其中Gen是一个概率算法，输入一个\(1^n\)的安全密钥，输出一个密钥s

H接受输入s和一个字符串x，输出一个对应的串\(H^s(x)\in \{0,1\}^{l(n)}\)

碰撞检测实验

\(Hash-coll_{A,\Pi}(n)\)

随机产生一个密钥s，敌手A把密钥s和两个字符串x,x'发送过去，输出1当且仅当\(x\neq x'\) and \(H^s(x)=H^s(x')\)

一个哈希函数是抗碰撞的如果对所有的PPT敌手都有\(Pr[Hash-coll_{A,\Pi}(n)=1]\leq negl(n)\)

在实践中一般不需要这么高的安全性

Second-preimage or taget-collision resistance:

如果给定一个s和一个随机的x，对任何PPT敌手，都不可能找到一个x',使得\(x\neq x'\)且\(H^s(x)=H^{s}(x')\)

Preimage resistance:

给定一个s和一个随机的y，对任何PPT敌手，都不可能找到一个x，使得\(H^s(x)=y\)

事实上有:\(c.r.\to 2nd p.r. \to p.r.\)

域扩展

用定长的哈希来解决变长的输入：

The Merkle-Damgard Transform

假设一个哈希函数是将一个a+b位的输入压缩成一个a位的输出，构造如下哈希函数：

Gen和原先的哈希函数相同

H接受一个密钥s和一个任意长度字符串x的输入，实行下面两个步骤：

1.划分和填充：

设输入的x的长度是L，其中L的长度小于\(2^b\),把x用0进行若干次填充，使其长度是b的倍数,再将其划分成B+1块，其中$B= :x_1,x_2,...x_{B+1} $

2.连锁压缩:

选取初始随机向量IV，长度为a

计算\(z_i:=h^s(z_{i-1}||x_i)\),最终输出\(H^s(x)=z_{B+1}\)

如果原哈希函数是抗碰撞的，那么新的哈希函数也是抗碰撞的

MAC and HASH

用哈希函数来扩展MAC域

给定一个定长的MAC和一个任意长度的消息，如何用这个MAC来进行身份验证？

先把这个消息给哈希到一个定长的消息，再对这个消息计算MAC生成标签。

这个MAC是安全的变长MAC如果使用MAC是一个安全的定长MAC且哈希是抗碰撞哈希。

用哈希函数构建MACs

HMAC：已证明的安全的构造方法

哈希函数常见的攻击方式

1.生日攻击

对于n个不同的数中挑选，只要\(\sqrt{n}\)次挑选，就有\(\frac{1}{2}\)的概率找到一个碰撞。

由此，一个有n位输出的哈希函数，其安全性就只有\(\frac{n}{2}\)位了

One-Way Functions and Hard-Core Predicates (单向函数与硬核谓词)

one way fuctions(OWF)是一类函数，易于计算，但是很难求逆，单向函数的存在实现了很多有用的概念，如PRF、PRG等

定义：

1.易于计算：存在PPT算法\(M_f\)来计算f，对所有x，\(M_f(x)=f(x)\)

2.难于求逆：对任意PPT算法A，存在一个不可忽略函数negl,使得\(Pr_{x\gets^{\$} \{0,1\}^n}[A(1^n,f(x))\in f^{-1}(f(x))]\leq negl(n)\)

其中有两个要素，其一是x是均匀随机选取的，而非任意挑选其中一个x，我们求的是平均；其二是我们只需要求出其中一个原像，而不需要所有原像或者最初的x。

可以定义一个实验\(Invert_{A,f}(n)\)

难以求逆性质要求对所有PPT敌手A，都有一个不可忽略函数negl，使得\(Pr[Invert_{A,f}(n)=1]\leq negl(n)\)

OWF的候选人

目前还不清楚是否存在OWF，但是有几个候选人，至今未找到多项式时间的解决方案，于是暂定其是OWF；

1.两个n位的质数相乘之后进行分解；

2.子集和问题，给定n个数和一个index set I，给出对应的和，找出原始的I；

3.离散对数问题。输出一个指数p和一个随机元素\(g\in \{2,3...p-1\}\),定义\(f_{p,g}=g^{x}\) mod p

Hard-core predicates硬核谓词

f(x)是OWF能推出从f(x)中我们无法获得任何关于x的信息吗

不一定。

反例：

假设g是一个OWF，f(x1||x2)=x1||g(x2),f是OWF，但是泄露了前面一半的信息

我们用硬核谓词来建模f(x)隐藏的信息

一个函数hc：\(\{0,1\}^*\to \{0,1\}\)是一个函数f的硬核谓词如果hc可以在多项式时间内计算，并且对每一个PPT敌手A都有一个可忽略函数negl使得\(Pr_{x\gets \{0,1\}^n}[A(1^n,f(x))=hc(x)]\leq \frac{1}{2}+negl(n)\)

上述定义并不要求f(x)是OWF。

Goldreich-Levin Theorem

假设OWF存在。那么存在一个OWF g和一个g的硬核谓词hc

例如给定OWF f和g，那么hc可以如下构造：

\(g(x,r)=(f(x),r) for |x|=|r|\)

\(hc(x,r)=\oplus ^n_{i=1}x_i · r_i\)

用OWF构造PRG

用最小扩展来构造PRG

假设f是一个单向排列，hc是f的一个硬核谓词，那么G(s)=f(s)||hc(s)是一个扩展1位的PRG。

用多项式扩展来构造PRG

每次多生成一位。

Number Theory and Cryptographic Hardness Assumptions (数论与密码学困难度假设)

a|b:a整除b

余数表示的唯一性：a=qb+r

存在X，Y，使得Xa+Yb=gcd(a,b),且gcd(a,b)是可以以这种形式表示的最小整数。且这种表示不是唯一的，存在无数组XY。

gcd可以用欧几里得算法计算，XY可以用扩展欧几里得算法计算。

\(gcd_{loop}\)(a, b)： r=0 while (b \(\neq\) 0) { r = a mod b; a = b; b = r; } return a;

扩展欧几里得方法找到XY：

在模运算意义下加减乘运算都封闭

除法运算不封闭

b是模N意义下可逆的：存在c，bc=1 mod N,c称为b的乘法逆元

\(b^{-1}\):b在1~N-1里面的唯一的逆元

定义下面的除法操作：\([a/b mod N]=[ab^{-1} mod N]\)

因此只要除数的逆元存在，那么除数就是良定义的，ab=cb mod N 就能推出a=c mod N

b是可逆的当且仅当gcd(b,N)=1

求乘法逆元可以用欧几里得扩展算法。

群论

很多加密系统都是基于群论的

一个群是一个代数结构，由一个元素集G和一个二元操作符组成的

满足封闭性、满足结合律、有单位元、有逆元

Closure. g, h ∈ G, g ◦ h ∈ G

Existence of an identity. e ◦ g = g = g ◦ e.

Existence of inverses. g ◦ h = e = h ◦ g

Associativity. g1, g2, g3 ∈ G, (g1 ◦ g2) ◦ g3 = g1 ◦ (g2 ◦ g3)

如果是可交换的，那么是阿贝尔群

对于任意整数N，我们可以在模乘法意义下构造一个群吗：可以，\(Z^*_N=\{b\in \{1,...N-1\}|gcd(b,N)=1\}\)

所有元素都是与N互质的。这个集合称为N的简化剩余系，而\(Z_N\)成为N的完全剩余系。

欧拉phi函数

\(\phi(N)=|Z^*_N|\),\(\phi\)成为欧拉phi函数。

有如下定理：

令\(N=\Pi_ip_i^{e_i}\),其中\(P_i\)是不同的质数，\(e_i\geq 1\),那么\(\phi(n)=\Pi_ip_i^{e^i-1}(p_i-1)\)

例如\(N=15=3*5，Z^*_N=\{1, 2, 4, 7, 8, 11, 13, 14\}=8=(5-1)(3-1)\)

费马欧拉定理：

对任意N>1 和\(a\in Z^*_N\),\(a^{\phi(N)}=1\) mod N.当N是质数p的时候，\(a^{p-1}=1\) mod p

令G是有限集，m=|G|,是群的阶数，对于任意元素\(g\in G,g^m=1\)

质数检验：给定N，计算\(\sqrt{N}\),对里面的质数进行计算，看是不是N的因数，要都不是，那么N是质数。

中国剩余定理

令N=pq，pq互质，那么\(Z_n\simeq Z_p \times Z_q\),\(Z_N^* \simeq \Z_p^*\times Z_q^*\)

进一步的，令f是一个从x到\(x_p,x_q\)的映射,f(x)=([x mod p],[x mod q]),那么f是一个同构映射。

令N=\(p_1p_2p_3...p_l\)，那么\(Z_n\simeq Z_{p_1} \times Z_{p_2} ... \times Z_{p_l}\),\(Z_n^*\simeq Z_{p_1}^* \times Z_{p_2}^* ... \times Z_{p_l}^*\)

这里面9X+35Y=1,得Y=8;7X+45Y=1,得Y=5;5X+63Y=1,得Y=2

如何找原像

RSA假设

分解假设认为如下分解问题是困难的：

这个问题通过运行一个多项式时间算法 GenMoudulus来进行实例化，给定输入1^n,输出(N,p,q),其中N=pq，p和q是n位的质数

\(Factor_{A,GenModulus}(n):\)

运行GenModulus\((1^n)\)获得(N,p,q)

A给定N输出p' q'

输出1 如果 p'·q'=N

分解问题是困难的如果对于所有PPT敌手都有一个可忽略函数negl使得\(Pr[Factor_{A,GenModulus}(n)=1]\leq negl(n)\)

RSA问题是和分解问题及其相关的

The RSA experiment \(RSA_{invA,GenRSA}(n)\)

运行GenRSA\((1^n)\)获得(N,e,d),N是两个n位的质数的乘积，\(gcd(e,\phi(N))=1\) 且\(ed=1\) mod \(\phi(N)\)

均匀随机选取一个\(y \in Z^*_N\)

A给定N,e,y,输出\(x \in Z^*_N\)

如果\(y=x^e\) mod N,输出1，否则输出0

RSA问题是困难的如果对所有PPT敌手都有一个可忽略函数negl使得\(Pr[RSA_{invA,GenRSA}(n)=1]\leq negl(n)\)

循环群中的密码学假设

循环群和生成元

设群的阶数是m，={\(g^0,g^1,g^2...g^{i-1}\)}是一个循环群，g是一个生成元,i是最小的正整数，使得\(g^i=1\)，i称为g的阶数

i总是存在而且小于等于m

如果g的阶数是m，那么g是一个循环群的生成元

离散对数问题和diffie-hellman假设

设G是一个生成元为g，阶数为q的循环群

对群中的任意一个元素h，都存在一个x，使得\(g^x=h\)

我们把x称为h相对于g的离散对数，写作\(x=log_g(h)\)

The discrete-logarithm experiment \(DLog_{A,\mathcal{G} }\)

运行\(\mathcal{G}(1^n)\)来获得(G,q,g),其中G是一个生成元为g，阶数为q的循环群

选取随机G中一个元素h

A给定(G,q,g,h),输出x

实验的结果是1，当且仅当\(g^x=h\)

我们称离散对数问题是困难的，如果对所有PPT敌手都有一个可忽略函数negl使得\(Pr[DLog_{A,\mathcal{G} }=1]\leq negl(n)\)

离散对数假设是假设存在一个G，而离散对数问题是困难的。

Key Management and the Public-Key Revolution (密钥管理与公钥加密变革)

KDC

密钥集散中心：和所有实体之间都有一个初始的密钥，当A想和B交流时，用A的密钥加密消息向KDC发出申请，KDC解密后知道A的请求，于是生成一个新的密钥，分别用A和B的密钥加密后发给A和B，这样A和B就可以用这个新密钥进行通信。

在通信结束后，A和B都把这个密钥销毁。不过这种方法有一个缺点，就是KDC需要保存所有的密钥，如果KDC被攻破，那么所有的密钥都会泄露。

Needham-Schroeder key-distribution protocol

如何不依赖于KDC来建立一个安全的密钥交换协议？

The Diffie-Hellman key-exchange protocol

令$ $是一个PPT算法，输入\(1^n\)，输出(G,q,g),其中G是一个生成元为g，阶数为q（q=n）的循环群

D-H key-exchange protocol is constructed as follows

正确性：\(K_A=h_B^x=(g^y)^x=g^{xy}=(g^x)^y=h_A^y=K_B\)

安全性：敌手可以看到G,q,g,\(h_A\),\(h_B\)，但是不能看到x,y

通过定义实验来证明安全性：

The key-exchange experiment \(KE_{A,\Pi}^{eav}(n)\)

两个主体都持有\(1^n\),运行密钥交换协议，产生了一个包含有两者所有暴露信息的文本Trans，并且输出了一个两个主体所共同持有的密钥k

随机选择一位b，如果b=0，那么\(\hat{k}:=k\)，否则均匀随机选择\(\hat{k}\in \{0,1\}^n\)

\(\mathcal{A}\) 给定Trans和\(\hat{k}\),输出一位b'

实验输出1，当且仅当b=b'

这个密钥交换协议在有窃听者在场的情况下是安全的，当且仅当如果对所有PPT敌手\(\mathcal{A}\)，都有一个可忽略函数negl使得\(Pr[KE_{A,\Pi}^{eav}(n)=1]\leq \frac{1}{2}+negl(n)\)

为了简化这个问题，随机生成的一个k修改为从G中随机选一个元素，这样问题被重新定义为\(\hat{KE}^{eav}_{A,\Pi}(n)\)

如果和\(\mathcal{G}\)相关判定性diffie-hellman问题是困难的，那么这个密钥交换协议是安全的。

DH密钥很容易受到中间人攻击，因此在实践中不单独使用

公钥加密

一个公钥加密方案可以写成一个PPT算法的三元组

Gen：输入\(1^n\)，输出一个公钥pk和一个私钥sk

Enc：输入pk和一个消息m，输出密文\(c\gets Enc_{pk}(m)\)

Dec：输入sk和密文c，输出消息m，\(m:=Dec_{sk}(c)\)

在有窃听者的情况下设计实验来考虑公钥加密的安全性：

The eavesdropping indistinguishability experiment \(PubK^{eav}_{A,\Pi}(n)\)

运行Gen(1^n)获得(pk,sk)

敌手给定公钥pk，输出两个消息m0,m1

随机选择一个比特位b，生成密文\(c\gets Enc_{pk}(m_b)\)，把c发送给敌手A,c称为挑战密文

A输出一个比特b'，实验输出1当且仅当b=b'

一个公钥加密方案在窃听者存在时进行无法区分的加密，如果对所有PPT敌手A，都有一个可忽略函数negl使得\(Pr[PubK^{eav}_{A,\Pi}(n)=1]\leq \frac{1}{2}+negl(n)\)

与私钥加密不同，如果一个公钥加密方案在窃听者存在的情况下具有难以区分的加密，那么它是CPA安全的，即对CPA对手具有难以区分的加密。

因为(1) A是pk（用于加密），(2)Enc是公开已知的。因此，A可以自己加密任何消息，这相当于有一个加密神预机。

如果一个公钥加密方案是CPA安全的，那么他也有对多条消息加密的不可区分性。

CPA安全的定长加密方案意味着CPA安全的任意长度加密方案。

用如下实验来定义CCA安全\(PubK^{cca}_{A,\Pi}(n)\)

Gen(\(1^n\))获得(pk,sk)

敌手给定公钥pk，可以访问解密预言机\(Dec_{sk}(·)\),输出一对等长的消息m0,m1

随机选择一个比特位b，生成密文\(c\gets Enc_{pk}(m_b)\)，把c发送给敌手A,c称为挑战密文

A继续访问解密预言机，但是不允许对挑战密文本身进行询问。最终，敌手输出b'，实验输出1当且仅当b=b'

一个公钥加密方案是CCA安全的，如果对所有的PPT敌手A，都有一个可忽略函数negl使得\(Pr[PubK^{cca}_{A,\Pi}(n)=1]\leq \frac{1}{2}+negl(n)\)

类似于cpa安全的公钥加密，我们有：如果加密方案是cca安全的，那么在chosen ciphertext attacks下也有无法区分的（多个）加密。

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!have trouble in understanding the following content

但是和公钥加密的CPA安全不同，将定长的CCA安全的公钥加密方案扩展到任意长度的消息并不是CCA安全的

因为敌手可以对挑战密文块重新排序，从而获得一个新的密文。

公钥加密的优点：

密钥分发更加简单，对于用户数量未知的开放系统更加便捷。

公钥加密的缺点：

加密速度慢2-3个数量级，公钥加密通常具有更大的密文扩展（因此可能需要存储/传输更多的位）。

Hybrid Encryption and the KEM/DEM Paradigm混合加密和两种范式

为了同时利用公钥加密和私钥加密的优点，避免两者的缺点，提出了混合加密的概念

The key-encapsulation mechanism (KEM)密钥封装机制

data-encapsulation mechanism (DEM)是一个私钥加密方案，称为数据封装机制

CDH/DDH-Based Encryption

El Gamal encryption scheme

令\(\mathcal{G}\)是一个PPT算法，输入\(1^n\)，输出(G,q,g),其中G是一个生成元为g，阶数为q（q=n）的循环群

Gen：输入\(1^n\)，运行\(\mathcal{G}(1^n)\)获得(G,q,g),随机选择一个x，计算h=\(g^x\),公钥是<G,q,g,h>,私钥是<G,q,g,x>,消息空间是G

Enc:输入公钥<G,q,g,h>和一个消息m，随机选择一个y,输出密文<\(g^y\),\(h^y·m\)>

Dec:输入私钥<G,q,g,x>和密文<\(c_1,c_2\)>，输出\(\hat{m}:=c_2/c_1^x\)

如果DDH问题相对于\(\mathcal{G}\)是困难的，那么El Gamal加密方案是CPA安全的。

证明见书本**

但是不是CCA安全的

RSA加密

plain RSA

RSA加密基于如下trapdoor one-way function

“one way”:给定一个均可见的整数e和N，对于任意\(m\in Z_N^*\),容易计算c=[\(m^e\) mod N]，但是从c计算m是困难的

"trapdoor information"：如果已知N的分解，那么从c计算m是容易的

RSA密钥生成算法运行如下：

GenRSA

输入安全参数1^n

输出N,e,d

1.(N,p,q)\(\gets\) GenModulus(\(1^n\))

2.\(\phi(N)=(p-1)(q-1)\)

3.选择一个e，使得gcd(e,\(\phi(N)\))=1

4.计算d:=[\(e^{-1}\) mod \(\phi(N)\)]

5.Return (N,e,d)

给定密钥生成算法GenRSA，RSA加密方案是如下的三元组：

The plain RSA encryption scheme

Gen:运行GenRSA(\(1^n\))获得(N,e,d),公钥是(N,e),私钥是(N,d)

Enc：输入公钥pk=(N,e)和一个消息m\(\in Z^*_N\)，输出密文c=[\(m^e\) mod N]

Dec:输入私钥sk=(N,d)和密文\(c\in Z^*_N\)，输出\(m:=c^d\) mod N

为什么plain RSA是不安全的：

plain RSA不是CPA安全的，或者说在有窃听者在场的情况下没有不可区分的加密

No deterministic public-key encryption scheme is CPA-secure.

因为缺少随机性，敌手可以让其加密两条消息m0和m1，然后将结果与挑战密文相互比较

RSA加密的安全性的先决条件是要求被加密的m是随机选择的，但是在这里m不是从\(Z^*_N\)中均匀随机选择的，c也不是均匀分布的，因此RSA假设并不适用于plain RSA

Padded RSA

为了克服如上缺点，使用了填充RSA的方法。

在加密之前，消息被“随机填充”（或随机映射）到\(Z_N^*\)中的一个长消息。长随机消息被输入加密算法并生成密文。

要解密，需要将密文输入解密算法，并使用“去填充”操作从输出中恢复原始消息（这需要映射是可逆的）。

安全性主要取决于所使用的特定映射。

RSA Laboratories Public-Key Cryptography Standard (PKCS)

如果r的长度是N的一半，那么它是CPA安全的

optimal asymmetric encryption padding (OAEP)

Digital Signature Schemes (数字签名机制)

与MAC一样都是用来保证消息完整性的，区别在于数字签名是所有人都可以进行验证的。数字签名还提供了不可抵赖性non-repudiation。

数字签名不如MAC高效，一个可能的方式是用哈希-签名范式，把一个长消息哈希，再签名。

数字签名方案：

一个数字签名方案包含三个PPT算法：

key-generation algorithm:输入\(1^n\)，输出一个公钥pk和一个私钥sk

signing algorithm:输入私钥sk和一个消息m，输出签名\(\sigma\),写作\(\sigma\gets Sign_{sk}(m)\)

verification algorithm:输入公钥pk，一个消息m和一个签名\(\sigma\)，输出1或0，写作\(Vrfy_{pk}(m,\sigma)\)

定义如下实验\(Sig-forge_{A,\Pi}\)(n):

运行Gen(1^n)获得(pk,sk)

敌手A给定pk，可以访问加密预言机Sign_{sk}(·)，令Q是A所有询问结果的集合

A输出一个消息m和一个签名\(\sigma\)

A获胜如果\(Vrfy_{pk}(m,\sigma)=1\)且m\(\notin\) Q中,输出1

一个数字签名方案是在自适应选择消息攻击下不可伪造的，如果对所有PPT敌手A，都有一个可忽略函数negl使得\(Pr[Sig-forge_{A,\Pi}(n)=1]\leq negl(n)\)

Theorem

如果\(\Pi\)是一个数字签名方案，那么\(\Pi\)是一个长度为l的安全的数字签名方案，\(\Pi_H\)是一个长度为l的抗碰撞的哈希函数，那么如上构造的哈希-签名方案就是一个任意长度消息的安全的数字签名方案。

RSA签名

Plain RSA签名是不安全的

Gen:运行GenRSA(\(1^n\))获得(N,e,d),公钥是(N,e),私钥是(N,d)

Sign:输入私钥sk=(N,d)和一个消息m，输出签名\(\sigma:=m^d\) mod N

Vrfy:输入公钥pk=(N,e)和一个消息m和一个签名\(\sigma\)，输出1当且仅当\(\sigma^e\) mod N=m

攻击方式：

1.无消息攻击，一个签名是合法的当且仅当\(\sigma^e\) mod N=m

为了生成一个合法的签名，敌手任意选择了一个签名\(\hat{\sigma} \in Z_N^*\)，然后计算\(\hat{m}=\hat{\sigma}^e\) mod N,最后输出(\(\hat{m}\),\(\hat{\sigma}\))

造成这个漏洞的原因是容易求逆，在已知签名的情况下很容易求出消息

2.由RSA签名的可塑性来伪造m的签名

找到两个消息m0和m1，使得\(m_0·m_1\) mod N=m，那么\(\sigma_0·\sigma_1\) mod N=1，那么\(\sigma_0\)和\(\sigma_1\)都是合法的签名

RSA-FDH signature scheme

为了避免如上伪造，可以在签名前对消息进行一个变换H(·)，其中这个变换要满足1.单向函数，2.不可塑性，3.抗碰撞

基于如上条件，构造了RSA-FDH signature scheme

H是一个随机函数，把输入映射到\(Z_N^*\)上。

Gen:运行GenRSA(\(1^n\))获得(N,e,d),公钥是(N,e),私钥是(N,d)

Sign:输入私钥sk=(N,d)和一个消息m，输出签名\(\sigma:=H(m)^d\) mod N

Vrfy:输入公钥pk=(N,e)和一个消息m和一个签名\(\sigma\)，输出1当且仅当\(\sigma^e\) mod N=H(m)

If the RSA problem is hard relative to GenRSA and H is modeled as a random oracle, then RSA-FDH signature is secure.

来自离散对数问题的签名

The Identification Scheme

身份识别方案是用来向别人证明自己身份的，在这里，我们将注意力限制在公钥识别方案上。

在公钥设置中，识别方案允许你向某人（称为验证者）证明您是与特定公钥相对应的那个人。

我们通过证明我们知道与公钥相关的私钥来实现这一点。

我们的问题是，如何不告诉验证者我们的私钥就能证明我们知道它。

方案1.证明者把\(x\in Z_q\)发送给验证者，验证者计算y=\(g^x\)，看是否与公钥相同，但是会泄露私钥x

方案2.the Schnorr identification scheme

证明者随机选择一个b\(\gets Z_q\),计算I=\(g^b\),把I发送给验证者

验证者随机选择一个a\(\gets Z_q\)(call a challenge)，计算y=\(g^a\)，把y发送给证明者

证明者计算X=[ax+b mod q]，把X发送给验证者

验证者接受当且仅当\(y^a*I=g^X\)

我们说这个认证方案是安全的，如果没有PPT敌手可以通过上述的验证方案来获得关于私钥的任何信息。

证明方案有如下两种：

1. constructing a simulator S that does NOT know x, but can simulate the view or transcript (i.e. the messages it sees) of an eavesdropper in the scheme.

(2)proving NO PPT adversaries can differentiate the simulated view and the real view.

The Schnorr signature scheme

一个认证方案可以通过如下步骤转换为一个签名方案：

The signer acts as a prover, runs the identification scheme by itself.

It generates a challenge a by applying some random function H to I and m.

It generates the correct response X and uses (a, X) as the signature of m.

The Fiat-Shamir transform：把上述的三轮交互式验证转换为两轮的非交互式验证。

H是一个哈希函数，这个变换被用来构建非交互式的加密协议

签名(a,X)被限制到了一个特定的消息m，m的改变会导致a的巨大变化(a=H(m,I))

签名是难以伪造的，因为不知道私钥

结语：

给分情况 ： 期中考试：20% 100分 平时作业：40% 100+100+90+100 期末考试：40% 82分 总评92分