密码学协议结构基础—单向函数和陷门单向函数

单向函数(one-way function)和陷门单向函数(trapdoor one-way function)的概念是公开密钥密码学的核心之一。尽管其本身并非一个协议,但其是重要的理论基础,对于很多协议来说,其是一个重要的基本结构模块。了解和掌握单向函数,是非常重要以及必要的。本文将对其简述,希望对大家有所帮助。
单向函数(one-way function)和陷门单向函数(trapdoor one-way function)的概念是公开密钥密码学的核心之一。尽管其本身并非一个协议,但其是重要的理论基础,对于很多协议来说,其是一个重要的基本结构模块。了解和掌握单向函数,是非常重要以及必要的。本文将对其简述,希望对大家有所帮助。

单向函数(one-way function)的概念是公开密钥密码学的核心之一。尽管其本身并非一个协议,但其是重要的理论基础,对于很多协议来说,其是一个重要的基本结构模块。

单向函数顺向计算起来非常的容易,但求逆却非常的困难。也就是说,已知x,我们很容易计算出f(x)。但已知f(x),却很难计算出x。
注:这里的“难”定义为,即使世界上所有的计算机都用来参与计算,从f(x)计算出x也要花费数百万年的时间。

现举一个现实生活中的例子帮助大家理解,打碎碗碟是一个很好的单向函数的例子,我们将碗碟打碎成数千片的碎片是一件很容易的事情,但要把这些碎片再拼成一个完整无缺的碗碟,却是一件非常困难的事情。

如果按照严格的数学定义,目前为止其实并不能完美的证明单向函数的存在性,同时也没有实际的证据能够构造出单向函数。即使如此,还是有很多函数看起来像单向函数:我们可以有效的计算它们,但至今为止我们还不知道有什么有效的方法能够容易的求出它们的逆。比如,在有限域中计算x的平方很容易,但计算x的根则难得多。

我们现想想,单向函数有什么好处,单向函数可以用于加密吗?结论是单向函数一般是不用于加密的,因为用单向函数进行加密往往是不行的(因为没有人能破解它)。
还是用上述现实生活中的例子进行说明,你要给你的朋友传递一个信息,你将信息写在了盘子上,然后你将盘子摔成无数的碎片,并将这些碎片寄给你的朋友,要求你朋友读取你在盘子上写的信息。这是不是一件十分滑稽的事情。
那么单向函数是不是就没有意义了呢,事实当然不是这样,单向函数在密码学领域里发挥着非常重要的作用,其更是很多应用的理论基础。

单向函数的密码学应用
1)一个简单的应用就是口令保护。我们熟知的口令保护方法是用对称加密算法进行加密。然而,对称算法加密一是必须有密钥,二是该密钥对验证口令的系统必须是可知的,因此意味着验证口令的系统总是可以获取口令的明文的。这样在口令的使用者与验证口令的系统之间存在严重的信息不对称。我们可以使用单向函数对口令进行保护来解决这一问题。比如,系统方只存放口令经单向函数运算过的函数值,而验证则是将用户口令重新计算函数值,然后将和系统中存放的值进行比对。如果比对成功,则验证通过。动态口令认证机制很多都是基于单向函数的原理进行设计的。
2)另一个单向函数的应用,是大家熟知的用于数字签名时产生信息摘要的单向散列函数。由于公钥密码体制的运算量往往较大,为了避免对待签文件进行全文签名,一般在签名运算前使用单向散列算法对签名文件进行摘要处理,将待签文件压缩成一个分组之内的定长位串,以提高签名的效率。MD5和SHA-1就是两个曾被广泛使用的、具有单向函数性质的摘要算法。

陷门单向函数(trapdoor one-way function)
单向陷门函数trapdoor one-way function)是一类特殊的单向函数,其存在一个陷门。
单向陷门函数包含两个明显特征:
1)一是单向性。
2)二是存在陷门。
所谓单向性,也称不可逆性。而所谓陷门,也成为后门。
比如函数f(x),若已知x计算出f(x)很容易,而已知f(x),逆向求x则很困难。但若存在一个k,使得知道要是知道k,则可以很容易地计算出f(x)的逆;而不知道k,则无法计算出函数f(x)的逆,那么我们就称函数f(x)为单向陷门函数,而k称为陷门。
现举一个陷门单向函数的例子帮助理解,拆开表是一个很好的陷门单向函数的例子,我们将表拆成数百片小片非常容易,而把这些小片重新组装成能够工作的表则非常的困难,但我们如果通过秘密消息(表的装配指令),就可以很容易将表复原。这里的“表的装配指令”就是上述的陷门k。
zy



你可能感兴趣的文章

相关问题

1 条评论

请先 登录 后评论
不写代码的码农
于中阳Mercina-zy

区块链研究/开发 信息安全

78 篇文章

作家榜 »

  1. 社区运营-小以 442 文章
  2. 社区运营-小链 245 文章
  3. 于中阳Mercina-zy 78 文章
  4. 涂晶 72 文章
  5. 李晓琼 45 文章
  6. 兄弟连区块链培训 41 文章
  7. 吴寿鹤 36 文章
  8. John-smith 26 文章