|
博主正在学习INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些笔记供自己回忆，如有错误请指正。整理成一个系列现代密码学，方便检索。
- 第二章定义了完美安全及其对应的密码方案“一次一密”，
- 第三章介绍了
- 第五章将介绍哈希函数，而5.1节先介绍哈希函数的定义。
密码学的假设
密码学是基于假设的一门学科，
- 最基础的假设是
P
≠
N
P
P\neq NP
P?=NP
- 更强一点的是单向函数存在
- 更强一点的是
P
R
F
PRF
PRF存在
- 更强一点的是抗碰撞哈希函数存在
- 更强的是公钥加密算法存在
抗碰撞哈希函数定义
- 将任意长度的长的输入字符串映射到固定长度的短的输出字符串
- 抗碰撞：
x
≠
x
′
x\neq x'
x?=x′，
H
(
x
)
=
H
(
x
′
)
H(x)=H(x')
H(x)=H(x′)
与数据结构中定义的哈希函数的不同
-
- 数据结构中的哈希函数：最小化碰撞；
- 密码学中的哈希函数：抗碰撞是一个要求
-
- 数据结构中的哈希函数：元素选择独立于哈希函数，也不需要考虑是否会导致碰撞；
- 密码学中的哈希函数：元素选择需要考虑哈希函数以及是否会导致碰撞
抗碰撞性
- keyed哈希函数/有密钥的哈希函数
-
H
s
(
x
)
=
d
e
f
H
(
s
,
x
)
H^s(x)\overset{def}{=}H(s,x)
Hs(x)=defH(s,x)
- 这里的密钥与其他密钥至少有两个不同：
- 不是所有字符串都对应有效密钥，
H
s
H^s
Hs可能不是一个抗碰撞哈希函数（所以往往有一个专门的keyGen函数生成有效密钥）
- 密钥
s
s
s是公开的
- unkeyed哈希函数/无密钥的哈希函数
- 从理论上来说，这种哈希函数不是抗碰撞的：没有密钥，则一定存在一个破解算法知道这个固定的key，硬编码这种碰撞对
(
x
,
x
′
)
(x,x')
(x,x′)到破解算法中
- 从实践上来说，还是抗碰撞的：虽然有这样一个破解算法，但在多项式时间内找不到
安全性：抗碰撞哈希函数>抗目标碰撞哈希函数>单向函数
- 抗碰撞哈希函数：给定密钥
s
s
s，PPT敌手不能找到一个碰撞对
(
x
,
x
′
)
(x,x')
(x,x′)，
x
′
≠
x
x'\neq x
x′?=x使得
H
s
(
x
′
)
=
H
s
(
x
)
H^s(x')=H^s(x)
Hs(x′)=Hs(x)
- 抗目标碰撞哈希函数：给定密钥
s
s
s和一个均匀随机
x
x
x，PPT敌手不能找到一个
x
′
≠
x
x'\neq x
x′?=x使得
H
s
(
x
′
)
=
H
s
(
x
)
H^s(x')=H^s(x)
Hs(x′)=Hs(x)，则称
H
s
(
x
)
H^s(x)
Hs(x)是抗目标碰撞的 / target-collision resistance / Second-preimage resistance。
- 单向函数：给定密钥
s
s
s和一个均匀随机字符串
y
y
y，PPT敌手找不到一个
x
x
x使得
H
s
(
x
)
=
y
H^s(x)=y
Hs(x)=y，则称
H
s
(
x
)
H^s(x)
Hs(x)是单向函数，或者preimage resistance。
安全性强弱：
- 如果一个哈希函数是抗碰撞的，则一定是抗目标碰撞的
- 如果一个哈希函数式抗目标碰撞的，则一定是单向函数
|