现代密码学(0):基本概念

本系列旨在以简单的语言(中文)来介绍现代密码学中的种种概念和问题。
我认为密码学是一门非常简单优美而又强大的学科,里面有许许多多的精巧构造,学习并理解这些协议不会太花功夫,甚至会觉得这东西怎么这么简单,但自己思考出却并不是一件容易的事情。
本人才疏学浅,如有错误请指出。

要读懂本系列,我期望读者拥有一定编程能力,以及一定的抽象代数知识。我尽量做到使一个熟悉数论的算法竞赛选手或者计算机科学专业的本科高年级无压力读懂所有内容。

好的,作为第零章,我们来(粗糙的)介绍一些简单而且基本的密码学工具

1.单向散列函数

单向散列函数,也就是哈希(hash),一个”好”的哈希函数应该满足
h(x)=y
(1)知晓x可以高效地计算y
(2)知晓y很难找到一个x0使得h(x0)=y
(3)h(x)的分布应尽量均匀

一个hash的简单应用是数字承诺:
Alice和Bob在玩游戏,Alice在心中想一个数$x\in \{0,1\}$,Bob猜中就获胜否则就失败
Bob:不管我猜没猜对,Alice每次都说我是错的,这样我永远赢不了
解决这个问题的方法之一是
(1)Bob生成并发送一个01随机串$r_1$
(2)Alice计算并发送给Bob $h(r_1 || r_2 || x)$其中$||$表示比特位连接,$r_2$是Alice生成的一个01随机串
(3)Bob猜一个数字$y$
(4)Alice公布$r_2$和$x$
(5)Bob检验$h(r_1 || r_2 || x)$是否与之前公布的相同

这个协议的是安全的原因在于Alice若想伪造答案为$\bar x$,她只能不断随机$r$以寻找到$h(r_1 || r || \bar x)=h(r_1 || r_2 || x)$
这是非常困难的

常见的哈希函数有md系列(md4,md5)和sha系列(sha-1,sha256,sha512),顺便一提,md5已经被不建议使用了

2.伪随机数生成
好像没有什么好说的,需要注意的一点是大部分的随机数生成器不是密码学安全的(点名批评梅森旋转生成器mt19937),这个以后会说

3.对称密码
最符合认知的加密,密钥为k
$E_k(x)$为加密
$D_k(x)$为解密
$D_k(E_k(m))=m$

常见的对称密码系统有DES(已退役),AES

4.非对称密码
粗略的讲,非对称密码的解密与加密的密钥不同
公钥为p,私钥为k
$E_p(x)$为加密
$D_k(x)$为解密
$D_k(E_p(m))=m$

常见的非对称密码有RSA,ElGamal

发表评论

电子邮件地址不会被公开。 必填项已用*标注