哈希函数中的数字签名技术.doc
《哈希函数中的数字签名技术.doc》由会员分享,可在线阅读,更多相关《哈希函数中的数字签名技术.doc(8页珍藏版)》请在三一文库上搜索。
1、哈希函数中的数字签名技术文中所讲的数字签名技术,就是我们在密码学中保证身份同一性所用到的最重要的工具。身份同一性的意思即是,如何证明某条消息就是“我”发出的,别人不能伪造,我也不能抵赖。虽然数字签名技术也会用到成对的密钥对,但与我们所说的公钥密码学重点却有所不同。(2)可以将本文视为思考密码学工具的一个教程或者范本,能耐心读下去,也就明白了密码学是怎么样一回事、我们在密码学中是如何思考的。回首近几年,我有幸经历了两个相互冲突、却又令人着迷的时代潮流变迁。第一个潮流变迁是:专家学者们耗费四十年设计的密码学,终于派上用场;从信息加密、电话安全、到加密数字货币,我们可以在生活的方方面面发现使用密码学
2、的例子。第二个潮流变迁是:所有密码学家已经做好准备,迎接以上美好的幻灭。正文开始之前我得重申一下,本文所讲的不是所谓量子计算启示录(末日预言),也不是要讲 21 世纪密码学的成功。我们要谈论的是另一件未成定局的事情密码学有史以来最简单的(也是最酷炫的)技术之一:基于散列函数的签名。在 20 世纪 70 年代末,Leslie Lamport 发明了基于哈希函数(Hash Function,又称散列函数)的签名 ,并经过 Ralph Merkle 等人进一步改进。而后的很多年,这被视为密码学领域一滩有趣的“死水”,因为除了相应地产生冗长的(对比其他复杂方案)签名,基于哈希函数的签名好像没有什么作用
3、。然而近几年来,这项技术似乎有了复苏的迹象。这很大程度归因于它的特性不同于其他基于RSA或离散对数假设的签名,哈希函数签名被视为可以抵抗量子计算攻击(如 Shors 算法)。首先,我们进行一些背景介绍。背景:哈希函数和签名方法在正式介绍哈希函数签名之前,首先你得知道密码学中的哈希函数是什么。哈希函数可以接受一串字符(任意长度)作为输入,经过“消化”后,产生固定长度的输出。常见的密码学哈希运算,像是 SHA2、SHA3 或 Blake2 等,经运算会产生长度介于 256 512 位的输出。一个函数 H(。) 要被称作“密码学”哈希函数,必须满足一些安全性的要求。这些要求有很多,不过我们主要聚焦在
4、以下三个方面:抗-原像攻击 Pre-image resistance (或俗称“单向性”):给定输出 Y=H(X),想要找到对应的输入 X 使得 H(X)=Y 是一件“极度费时”的工作。(这里当然存在许多例外,但最棒的部分在于,不论 X 属于什么分布,找到 X 的时间成本和暴力搜寻相同。)抗-次原像攻击:这和前者有些微的差别。给定输入 X,对于攻击者来说,要找到另一个 X 使得 H(X)=H(X) 是非常困难的。抗-碰撞:很难找到两个输入 X1, X2,使得 H(X1)=H(X2)。要注意的是,这个假设的条件比 抗-次原像攻击还要严苛。因为攻击者可以从无垠的选择中寻找任意两个输入。我们相信所有
5、本文提到的哈希函数示例都能提供上述的所有特性。换言之,没有任何可行的(甚至是概念上的)方法能破解它。当然这种情况也是会变的,如果破解的方法被找到,我们当然会立即停用哈希函数(稍后会讨论关于量子计算攻击的特例)。我们的目标是使用哈希函数构造数字签名方案,因此简要回顾数字签名这个词能带来很大的帮助。数字签名方法源于公钥的使用,使用者(签署人)生成一对密钥:公钥和私钥。使用者自行保管私钥,并能够用私钥“签署”任何消息,从而产生相应的数字签名。任何一个持有公钥的人都能验证该消息正确性和相关签名。从安全的角度来说,我们希望签名是不可伪造的,或是说“存在不可伪造性”。这意味着攻击者(没有私钥控制权的人)无
6、法在某段消息上伪造你的签名。Lamport 一次性签名在 1979 年,一位名叫 Leslie Lamport 的数学家发明了世界上第一个基于哈希函数的签名。Lamport 发现只要使用简单的哈希函数,或是单向函数,就可以构建出非常强大的数字签名方法。强大的前提是,用户只需要做一次签名的动作就能保证安全性!后续会做更详细的阐述。为了更好的讨论,我们假设以下条件:一个哈希函数,它能接受 256 位的输入并产生 256 位的输出; SHA256 哈希函数就是个绝佳的示范工具;我们也需要能产生随机输入的方法。假设我们的目标是对 256 位的消息进行签名。要得到我们需要的密钥,首先需要生成随机的 51
7、2 个位字符串,每个位字符串长度为 256 位。为了便于理解,我们将这些字串列为两个独立的表,并以符号代指:sk0= sk10, sk20, 。.,sk2560sk1= sk11, sk21, 。.,sk2561我们以列表 (sk0, sk1) 表示用来签名的 密钥。接下来为了生成公钥,我们将随机的位字符串通过 H(。) 进行哈希运算,得到公钥如下表:pk0= H(sk10), H(sk20), 。.,H(sk2560)pk1= H(sk11), H(sk21), 。.,H(sk2561)现在我们可以将公钥 (pk0,pk1) 公布给所有人知道。比如说,我们可以把公钥发给朋友,嵌入证书中,或是
8、发布在 Keybase 上。接着我们使用密钥对 256 位消息 M 进行签名。首先我们得将消息 M 重现为独立的 256 位元(Bit,又称“比特”):M1, M2, 。., M256 0, 1签名算法的其余部分非常简单。我们从消息 M 的第 1 位至第 256 位,逐一相应在密钥列表中的其中一个密钥上取出字符串。而所选密钥取决于我们要签名的消息每一位(bit)的值。具体一点地说,对于 i = 1,256,如果第 i 位的消息位元 Mi = 0,我们会从 sk0 表中选择第 i 个字符 (ski0) ,作为我们签名的一部分;如果第 i 位的消息位元 Mi = 1,我们则从 sk1 表进行前述过
9、程(即,如果我们要对消息 M 中的第 3 位进行签名,而该位值为 0,则使用 sk0 中的第三位,sk03,作为我们签名的一部分)。对每个消息位元完成此操作后,我们将选中的字符串连接,得到签名。过程如图示说明,因为部分过程化简,密钥和消息长度只有 8 个 bit(位元)。要注意的是,每个色块代表的都是不同的随机 256 位字符串。当某个用户(已经知道公钥 (pk0, pk1)收到消息 M 和签名,她能够轻易地验证这个签名。我们以 si 表示签名中第 i 个组成部分,用户能够检查相应的消息 Mi 并计算哈希值 H(si) 。如果 Mi = 0 ,则哈希值必须匹配公钥 pk0 中的元素;如果 Mi
10、 = 1 ,则哈希值必须匹配公钥 pk1 中的元素。如果签名中的每个元素经过哈希运算后,都能找到对应的正确部分的公钥,我们就会说这个签名是有效的。以下是验证过程图示,签名中至少有一个签名元素:如果你开始觉得 Lamport 的计划有些疯狂,你既是对的,也是错的。首先探讨下这个数字签名方法的弊端。我们会发现, Lamport 方法的签名和密钥实在太大了,大约有数千 bits。而且更要命的是,这个方法存在严重的安全局限:每个密钥只能被用来签名一个消息,所以 Lamport 方法作为“一次性签名” 在这里被拿来举例。这种安全局限为什么存在呢?回想一下, Lamport 签名表明了在各个消息位元上可能
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 函数 中的 数字签名 技术
链接地址:https://www.31doc.com/p-3406270.html