现代密码学(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

欢迎来到Zero Online Judge!

Zero OJ是一个去中心化的Online Judge,基于ZeroNet平台,每个人都可以提供题目、回答问题。由于其去中心化的特性,只要有一个结点存在,本OJ就不会关闭,并且访问人数越多访问越快。
可惜由于去中心化的问题本OJ没有一个中心化的服务器用于评测,用户只需要提供输出答案即可,我们使用了一些密码学协议保障①用户不能从网站数据中获取答案②用户可以通过网站数据验证自己答案是否正确③其他用户可以确认某用户是否真正通过某问题。

要访问本OJ,请先安装ZeroNet,由于一些众所周知的原因ZeroNet的访问在不同程度上有一些问题,目前来说windows平台可以直接访问,其他平台需要一定的专业知识。
第一次访问ZeroNet可能需要十几分钟的时间,此后访问速度会加快,当您成功访问后即可进入Zero OJ

更多消息请参考开发者后记