高级密码学复习1-HUST版
可证明安全性、IBE、PRE
- 安全的定义：安全是基于信任构建的标准“可满足性”；基于信任而不是基于试验的原因是（试验的成本过高）
- 信任源具有动态性，信任源是否可信可能随着时间和环境而发生变化。
-
密码学的信任源是数学难题。
-
安全的定义在密码学中的具体形式化是语义安全或者是可证明安全
-
语义安全性定义了攻击者的计算能力、定义了攻击目标。
Q1:语义安全性为什么能够作为定义密码算法安全性的标准?
因为语义安全性将攻击者的攻击能力最大化，攻击目标最小化，并不考虑攻击者的攻击形式（这样的好处是既不会陷于某种攻击方式而丧失普遍性，又构造了最有利于攻击者的情况，若仍能够说明密码算法的安全，则密码算法是真的安全）
Q2:如何定义攻击者的能力，和攻击目标？
假设攻击者能够获得最强的信息获取能力，获得所有的公开信息（例如算法的公开参数和算法等）；计算能力的最大上限（一般考虑能够具有解决多项式的问题的能力）
攻击目标限定于只要能够获得1bit的信息。（可以参考语义安全性的游戏理解）
- 语义安全性的游戏：
-
什么是安全参数？
RSA 具有1024位的加密密钥，这可以通过量化安全性进行证明，在密码学原理的课程中，我们有了解到
2
80
2^{80}
280破解复杂度是一个密码算法安全性的分水岭，超过这个复杂度的算法才具有实用的安全性。而加密密钥的长度（N=1024）可以直接影响破解的复杂度，越长的加密密钥带来越高的破解复杂度，但同时会带来更大的计算开销。
安全参数是量化安全性的重要依据，所有可证明安全的密码算法都有量化安全性。
-
为什么随机数对加密算法的安全性至关重要？
从信息论的角度首先理解，对于任何一个函数，函数的输入熵一定大于等于函数的输出熵，加密算法也不例外。确定性算法无法增加输出的熵。但密码算法要做到安全性，必须要是输出满足一定的随机性（即熵够大），随机数则作为一个桥梁，引入随机数（高熵）可以增加输入熵，在理论上符合信息论的观点。
-
为什么完善保密性（密码学原理中前两章的内容）中没有引入随机数？
因为完善保密性要求明文尽可能满足均匀分布（输入满足高熵）；要求密钥也是随机的（采用一次一密的方法）。从这两点我们也可以看出完善保密性在现实中并不具有实用性。
基于身份加密（IBE）
前言：首先认识到传统公钥密码体制和公钥基础设施PKI的不足，发掘本质问题，萌生IBE的思想，算法远没有思想重要。比如你来设想一个场景，海王杨师傅如果要给他的一千个女朋友发送520的情书，这时候他就得询问PKI一千次关于女朋友公钥，得到PKI的询问之后，他才能将情书发出去（必须等待PKI的响应，因为如果其中一个女朋友的公钥失效了，她就可能解不开情书，她就会生气！！！后果不堪设想。这样消耗的时间和精力太多，这对于杨师傅来说，是绝对不可能允许产生的。
- 公钥基础设施存在的问题
-
产生问题的本质原因
公钥是随机生成的，与用户没有天然的绑定关系。CA的存在就是通过一种外力人为地将公钥和用户身份进行绑定。
-
IBE的思想
-
IBE算法的唯一重点
生成用户私钥的身份信息是什么？（邮件系统中是用户的邮箱地址）
-
双线性映射
考点一、非常重要
T1 证明双线性映射的结合律
e
^
(
a
,
b
+
c
)
=
e
^
(
a
,
b
)
∗
e
^
(
a
,
c
)
hat{e}(a,b+c)=hat{e}(a,b)*hat{e}(a,c)
e^(a,b+c)=e^(a,b)∗e^(a,c)
已
知
b
,
c
属
于
加
法
群
，
不
妨
设
g
为
生
成
元
,
b
=
r
g
,
c
=
s
g
,
e
^
(
a
,
b
+
c
)
=
e
^
(
a
,
(
r
+
s
)
g
)
=
e
^
(
a
,
g
)
(
r
+
s
)
=
e
^
(
a
,
g
)
r
∗
e
^
(
a
,
g
)
s
=
e
^
(
a
,
b
)
∗
e
^
(
a
,
c
)
=
e
^
(
a
,
b
)
∗
e
^
(
a
,
c
)
已知b,c属于加法群，不妨设g为生成元,b=rg,c=sg,hat{e}(a,b+c)=hat{e}(a,(r+s)g)=hat{e}(a,g)^{(r+s)}=hat{e}(a,g)^r*hat{e}(a,g)^s=hat{e}(a,b)*hat{e}(a,c)=hat{e}(a,b)*hat{e}(a,c)
已知b,c属于加法群，不妨设g为生成元,b=rg,c=sg,e^(a,b+c)=e^(a,(r+s)g)=e^(a,g)(r+s)=e^(a,g)r∗e^(a,g)s=e^(a,b)∗e^(a,c)=e^(a,b)∗e^(a,c)
T2 运用双线性映射证明密文的可解密性
H
2
(
e
^
(
d
I
D
,
U
)
)
=
H
2
(
e
^
(
H
1
(
I
D
)
,
P
s
)
r
)
H_2(hat{e}(d_{ID},U))=H_2(hat{e}(H_1(ID),P_s)^r)
H2(e^(dID,U))=H2(e^(H1(ID),Ps)r)
H
2
(
e
^
(
d
I
D
,
U
)
)
=
H
2
(
e
^
(
s
H
1
(
I
D
)
,
r
P
)
)
=
H
2
(
e
^
(
H
1
(
I
D
)
,
s
P
)
r
)
=
H
2
(
e
^
(
H
1
(
I
D
)
,
P
s
)
r
)
H_2(hat{e}(d_{ID},U))=H_2(hat{e}(sH_1(ID),rP))=H_2(hat{e}(H_1(ID),sP)^r)=H_2(hat{e}(H_1(ID),P_s)^r)
H2(e^(dID,U))=H2(e^(sH1(ID),rP))=H2(e^(H1(ID),sP)r)=H2(e^(H1(ID),Ps)r)
- IBE小结
代理重加密
前言：如果机智的小王将一份通知文件上传到了云服务器中，这时候文件在云端是加密的（使用的私钥是
S
k
王
Sk_{王}
Sk王），但这个时候，他要把这个文件分享给小袁，懒惰的小王不想从云端将文件下载下来， 然后解密，然后用小袁的公钥进行加密，然后再发给她。有没有一种办法能够将这个文件直接从云端以密文的形式直接发给小袁，而且小袁能够用
s
k
袁
sk_{袁}
sk袁进行解密的呢？？？
PRE就是一种解决密文安全共享的技术，这个思想与我们之前学习的DES、AES、RSA、EIGamal、IBE等实现密文安全传输有很大不同。
- PRE是什么？
有没有一种办法能将文件下载-文件解密-文件再加密结合呢。PRE就是在云端完成了发送发密钥加密的密文到接收方密钥加密的密文的转化。
- PRE实现方法？
直接的思路：先解密再加密。存在两个问题：1、云端不知道解密密钥，2、云端在解密过程中知道了明文信息。
- PRE是如何做到无泄漏的安全性的呢（思想，具体见算法）？
PRE将脱密过程和再加密过程合二为一，不泄露中间结果，同时要注意保证解密密钥的安全
- PRE算法的核心
-
PRE算法和IBE算法的异同点：
1）关注
H
2
H_2
H2哈希函数（不同）
2）私钥的生成方式（相同）加法群到乘法群的映射，和乘法群到乘法群的映射没有本质区别。
3）密文
C
C
C的第二部分，去掉了
H
2
H_2
H2哈希函数。为什么？为了更好的进行后续计算，如果使用会导致无法重加密
4）密文
C
C
C的第二部分和密文的解密过程，采用代数运算代替异或运算，保留密文的可计算性质。
-
证明PRE重加密密文的可解密性
利用双线性映射的结合律
验证解密的过程
M
e
^
(
p
r
,
H
2
(
x
)
)
=
C
2
e
^
(
C
1
,
R
3
)
Mhat{e}(p^r,H_2(x))=C_2hat{e}(C_1,R_3)
Me^(pr,H2(x))=C2e^(C1,R3)
C
2
e
^
(
C
1
,
R
3
)
=
M
∗
e
^
(
P
s
,
H
1
(
i
d
1
)
r
)
∗
e
^
(
p
r
,
s
k
i
d
−
1
∗
H
2
(
x
)
)
=
M
∗
e
^
(
P
s
,
H
1
(
i
d
1
)
r
)
∗
e
^
(
P
r
,
s
k
i
d
−
1
)
∗
e
^
(
P
r
,
H
2
(
x
)
)
=
M
∗
e
^
(
P
s
,
H
1
(
i
d
1
)
r
)
∗
e
^
(
P
r
,
H
1
(
i
d
)
−
s
)
∗
e
^
(
P
r
,
H
2
(
x
)
)
=
M
∗
e
^
(
P
r
,
H
2
(
x
)
)
C_2hat{e}(C_1,R_3)=M*hat{e}(P_s,H_1(id_1)^r)*hat{e}(p^r,sk^{-1}_{id}*H_2(x))= \ M*hat{e}(P_s,H_1(id_1)^r)*hat{e}(P^r,sk^{-1}_{id})*hat{e}(P^r,H_2(x))=\ M*hat{e}(P^s,H_1(id_1)^r)*hat{e}(P^r,H_1(id)^{-s})*hat{e}(P^r,H_2(x))=\ M*hat{e}(P^r,H_2(x))
C2e^(C1,R3)=M∗e^(Ps,H1(id1)r)∗e^(pr,skid−1∗H2(x))=M∗e^(Ps,H1(id1)r)∗e^(Pr,skid−1)∗e^(Pr,H2(x))=M∗e^(Ps,H1(id1)r)∗e^(Pr,H1(id)−s)∗e^(Pr,H2(x))=M∗e^(Pr,H2(x))