专栏首页包罗万想GCAC55 13.1 Definition of a digital signature​

GCAC55 13.1 Definition of a digital signature​

13.1 Definition of a digital signature

Chapter 13 Digital signatures

在本章和下一章中,我们将开发数字签名的概念。尽管物理世界签名和数字签名之间有些相似之处,但这两者是完全不同的。我们通过三个示例来激发数字签名。

示例1:软件分发。假设一家软件公司SoftAreUs发布了其产品的软件更新。客户通过某种方式(例如,从公共分发站点或对等网络)下载软件更新文件U。在将U安装到他们的计算机上之前,客户希望确认U确实来自SoftAreUs。为此,SoftAreUs在U后面添加了一个短标签,称为签名。只有SoftAreU可以在U上生成签名,但是世界上任何人都可以对其进行验证。请注意,这里没有保密问题-每个人都可以使用更新文件U。MAC系统在此设置中没有用,因为SoftAreUs不会与其每个客户维护共享的密钥。一些软件分发系统使用抗冲突哈希,但是这需要一个在线只读服务器,每个客户都可以使用该服务器检查接收到的文件U的哈希值是否与只读服务器上的哈希值匹配。

为了提供一种干净的解决方案,而又没有其他安全性基础架构,我们需要一种称为数字签名的新加密机制。签名过程如下:

  • 首先,SoftAreUs生成一个签名私钥sk和一些表示为pk的相应公钥。 SoftAreUs将私钥sk保留给自己。公钥pk硬编码到SoftAreUs出售的软件的所有副本中,用于验证使用sk发行的签名。
  • 为了对软件更新文件U进行签名,SoftAreUs运行以(sk,U)作为输入的签名算法S。该算法输出一个短签名σ。然后,SoftAreUs将线对(U,σ)交付给其所有客户。
  • 客户Bob得到了(U,σ)和公钥pk,使用以(pk,U,σ)作为输入的签名验证算法V,来检查此消息-签名对的有效性。该算法根据签名是否有效来输出接受还是拒绝。回想一下,Bob从SoftAreUs的预安装软件系统中获取pk。

该机制在实践中广泛用于各种软件更新系统中。为了安全起见,我们必须要求拥有pk的对手不能在伪造的更新文件上生成有效的签名。我们将在下一部分中对此进行精确说明。

我们强调数字签名σ是要签名的数据U的函数。这与物理世界中的签名有很大不同,在物理世界中,无论要签署什么文档,签名都始终相同。

示例2:经过身份验证的电子邮件。作为第二个激励示例,假设Bob收到一封声称来自他的朋友Alice的电子邮件。Bob希望验证电子邮件确实来自Alice。MAC消息认证码可以完成这项工作,但是需要Alice和Bob具有共享的密钥。如果他们从未见过并且不共享密钥怎么办?数字签名提供了一种简单的解决方案。首先,Alice生成一个公/私钥对(pk,sk)。现在,我们假设Alice将pk放置在公共只读目录中。我们将在一分钟内讨论如何摆脱该目录。

向Bob发送电子邮件m时,Alice在使用她的私钥派生的m上生成签名σ。然后,她将(m,σ)发送给Bob。Bob分两步接收(m,σ)并验证m来自Alice。首先,Bob检索Alice的公钥pk。其次,Bob在三元组(pk,m,σ)上运行签名验证算法。如果算法输出接受,则向Bob保证消息来自Alice。更确切地说,Bob确信消息是由知道Alice的私钥的人发送的。通常,这只会是Alice,但如果Alice的私钥被盗,则该消息可能来自小偷。

作为一个更具体的示例,域密钥标识邮件(DKIM)系统是在Internet上广泛使用的电子邮件签名系统。使用DKIM的组织会生成一个公/私钥对(pk,sk),并使用sk来签名该组织的每个外发电子邮件。该组织将公钥pk放置在与该组织关联的DNS记录中,以便任何人都可以读取pk。电子邮件收件人会验证每封收到的DKIM电子邮件上的签名,以确保电子邮件来源是所声明的组织。如果签名有效,则电子邮件将被发送,否则将被丢弃。DKIM被广泛用作一种机制,使垃圾邮件发送者更难以发送伪装来自信誉良好的来源的垃圾邮件。

示例3:证书。作为数字签名的第三个激励示例,我们认为它们是使用最广泛的应用程序。在第11章和上面的经过身份验证的电子邮件系统中,我们假定公钥是从只读公用目录获得的。但是,实际上没有公用目录。取而代之的是,Alice的公钥pk由某个第三方认证,简称为证书颁发机构或CA。我们将在第13.8节中详细了解此过程的工作方式。现在,我们简要解释一下认证过程中如何使用签名。

为了生成经过认证的公钥,Alice首先为某些公钥密码系统(例如,公钥加密方案或签名方案)生成一个公/私钥对(pk,sk)。接下来,Alice将她的公钥pk提交给CA。然后,CA验证她声称自己是Alice,然后,一旦CA确信自己正在与Alice对话,则CA会构造一个声明m,说“公钥pk属于Alice。”最后,CA在消息m上签名。使用自己的私钥skCA并将配对Cert:=(m,σCA)发送回Alice,该配对Cert被称为pk的证书。当Bob需要Alice的公钥时,他首先从Alice获得Alice的证书,并在证书中验证CA的签名。如果签名有效,则Bob可以确信pk是Alice的公钥。 CA的数字签名的主要目的是向Bob证明声明m是由CA发出的。当然,要验证CA的签名,Bob需要CA的公钥pkCA。通常,CA公钥预先安装有操作系统或Web浏览器。换句话说,我们仅假设Bob的计算机上已经可以使用CA的公钥。

当然,可以概括上述内容,以便CA的Alice证书将多个公钥与其身份相关联,例如用于加密和签名的公钥。

不可否认。上面经过身份验证的电子邮件系统的一个有趣的特性是Bob现在有证据表明消息m来自Alice。他可以将对(m,σ)展示给法官,法官也可以验证Alice的签名。因此,例如,如果m说Alice同意将她的汽车卖给Bob,那么Alice(在某种意义上)致力于这项交易。Bob可以使用Alice的签名作为Alice同意将其汽车出售给Bob的证据,该签名将Alice绑定到消息m上。数字签名提供的此属性称为不可否认性。

不幸的是,事情并不是那么简单。Alice可以通过声明公钥pk不是她的签名来拒绝签名,因此签名不是由她发布的。或者,她可以声称自己的私钥sk被盗,并且签名是由小偷发出的。毕竟,计算机一直受到威胁,而且密钥一直都被盗。更糟糕的是,Alice在生成私钥后可能会故意泄露她的私钥,从而使所有签名失效。此时的法官不知道该相信谁。

这些问题部分是为什么数字签名不经常用于法律目的的原因。数字签名主要是一种用于对计算机系统中的数据进行身份验证的加密工具。它们是高级机制(例如密钥交换协议)的有用构建基块,但与法律体系无关。美国和欧洲有数项立法措施试图阐明对文件进行数字签名的过程。例如,在美国,对文件进行电子签名不需要密码数字签名。我们将在第13.9节中讨论数字签名的法律方面。

由于MAC是非绑定的,因此在MAC上下文中不会出现不可否认性。要了解原因,请假设Alice和Bob共享一个密钥,并且Alice向Bob发送一条带有附加MAC标签的消息。 Bob不能使用该标签使法官信服该消息是来自Alice的,因为Bob可以使用MAC密钥自己轻松地生成标签。因此,Alice可以轻松地拒绝发送该消息。签名系统的不对称性(签名者具有sk,而验证者具有pk)使Alice更难(尽管并非不可能)拒绝发送已签名的消息。

13.1 Definition of a digital signature

现在我们对数字签名方案的工作方式有了直观的了解,我们可以更精确地定义它们。从功能上讲,数字签名类似于MAC。主要区别在于,在MAC中,签名和验证算法都使用相同的密钥,而在数字签名方案中,签名算法使用一个私钥sk,而验证算法使用公钥pk。

13.1.1 Secure signatures

安全签名方案的定义类似于安全MAC的定义。我们赋予对手进行选定消息攻击CMA的权力,即攻击者可以在他选择的任何消息上请求签名。即使具有这种能力,对手也不能创建存在的伪造,即攻击者无法为某些新消息m输出有效的消息签名对(m,σ)。这里的“新”是指对手先前未要求签名的消息。

更准确地说,我们使用挑战者和对手A之间的攻击游戏来定义安全签名。该游戏在下面和图13.1中进行描述。

验证查询。在我们对MAC的讨论中,我们证明了定理6.1,该定理表明,标签验证查询无助于对手伪造MAC。对于数字签名,验证查询不是问题——对手始终可以为自己验证(消息-签名)对。因此,不需要用于数字签名的定理6.1的类似物。

防止多密钥攻击的安全性。在实际系统中,有许多用户,并且对于i = 1,...,n,每个用户可以具有一个签名密钥对(pki,ski)。对pk1的选定消息攻击CMA能否帮助对手伪造pk2的签名?如果可能的话,那么我们对安全签名的定义将是不充分的,因为它不能对现实世界的攻击进行建模。就像我们对其他安全原语所做的一样,可以将安全签名的概念推广到多密钥设置,并证明安全签名在多密钥设置中也是安全的。见练习13.2。在练习6.3中,我们证明了安全MAC系统的类似事实。

不可伪造的签名我们对存在性伪造的定义与安全MAC的定义有些不同。在这里,我们仅要求对手不能在新消息m上伪造签名。我们不排除对手从m上的其他签名产生m上的新签名。也就是说,即使对手可以将有效对(m,σ)转换为新的有效对(m,σ'),签名方案也是安全的。

相反,对于MAC安全性,我们坚持认为,给定消息标签对(m,t),对手不能为m创建新的有效标签t'!= t。这对于证明第9.4.1节中的“encrypt-then-MAC”结构的安全性是必要的。还需要证明MAC验证查询对对手没有帮助(请参阅定理6.1和练习6.7)。

可以类似地增强定义13.2,以要求对不可存在性伪造这一更严格的概念。我们在以下经过修改的攻击游戏中捕获了这一点。

强大的安全性确保了对于安全的签名方案,对手无法像MAC所要求的那样在先前签名的消息上创建新的签名。在某些特定情况下,要求签名满足此更强的安全性概念,例如[43、26]和第13.7节中描述的符号加密结构。但是,最常见的是定义13.2是足够的。无论如何,任何安全签名方案S =(G,S,V)都可以转换为高度安全的签名方案S’=(G’,S’,V’)。见习题14.10。

安全定义的局限性。定义13.2确保没有密钥就很难生成有效的消息签名对。但是,该定义未捕获签名方案的其他几个理想属性:

•绑定签名。定义13.2不需要将签名者绑定到她签名的消息。也就是说,假设签名者在某些消息m上生成签名σ。该定义不排除签名者产生另一条消息m'!= m,其中σ是有效签名。消息m可能说“Alice欠Bob10美元”,而消息m'则说“Alice欠Bob1美元。”由于σ是两条消息上的有效签名,因此法官无法判断Alice实际签名了什么消息。见练习13.3。

对于数字签名的许多应用,我们不需要将签名者绑定到已签名的消息。因此,我们不需要签名方案来强制执行此属性。但是,本章和下一章中的许多构造确实会将签名者绑定到消息上。也就是说,签名者不能产生两个具有相同签名的不同消息。

•重复签名密钥选择(DSKS)。令S =(G,S,V)是签名方案,而令(m,σ)是关于某些公钥pk的有效消息签名对。如果看到(m,σ)的攻击者可以生成密钥对pk',sk',使得(m,σ)对于公钥pk'也有效,则据说签名方案S易受DSKS攻击。我们要求攻击者同时产生pk'和sk'。练习13.4给出了易受DSKS攻击的签名方案的示例。

DSKS漏洞可能导致许多不良后果。例如,假设(m,σ)是学生Alice提交的签名家庭作业解决方案集。在提交截止日期之后,未提交解决方案集的攻击者Molly可以使用DSKS攻击来声称作业提交(m,σ)是她的。为此,Molly使用DSKS攻击来生成密钥对pk',sk',使得(m,σ)是密钥pk'的有效消息签名对。由于作业是在公钥pk和pk'下正确签名的,因此教授无法分辨是谁提交了作业(假设作业m无法识别Alice)。实际上,DSKS攻击已用于攻击某些密钥交换协议,如第21章所述。

定义13.2并不排除DSKS攻击。但是,免疫签名方案以抵抗DSKS攻击是很容易的:签名者只需在签名消息之前将其公钥附加到该消息即可。验证者在验证签名之前会做同样的事情。这样,签名的公钥将与消息一起进行身份验证(请参阅练习13.5)。在签名之前将公钥附加到消息上是一种很好的做法,并且在许多实际应用中建议这样做。

13.1.2 Mathematical details 忽略,跳过

本文分享自微信公众号 - 包罗万想(An-mind),作者:安包

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • GCAC65 14.1 Basic Lamport signatures

    参考资料:http://www.qukuaiwang.com.cn/news/142627.html

    安包
  • GCAC69 14.2 A general Lamport framework

    参考资料:https://www.freebuf.com/column/169190.html

    安包
  • Short Group Signatures

    论文地址:https://link.springer.com/chapter/10.1007/978-3-540-28628-8_3

    安包
  • 会话劫持

      在现实生活中,比如你去市场买菜,在交完钱后你要求先去干一些别的事情,稍候再来拿菜;如果这个时候某个陌生人要求把菜拿走,卖菜的人会把菜给陌生人吗?!当然,这只...

    那一叶随风
  • 在Debian 8上使用Postfix配置SPF和DKIM

    SPF(发件人策略框架)是一种向邮件服务器标识允许哪些主机为给定域发送电子邮件的系统。设置SPF有助于防止您的电子邮件被归类为垃圾邮件。

    番茄味
  • Python-爬虫小计

    py3study
  • Centreon+Nagios实战第四篇——监控端安装NDOUtils

    接下来启动MySql,对MySql进行配置 service mysqld start

    我是李超人
  • 少年成名,野路子的奇妙逆袭

    专访尹毅(法师Seay):少年成名,野路子的奇妙逆袭 ? 张爱玲说过,出名要趁早。信息安全行业相对其他行业更是如此,也更能体现出技术比学历重要,高手更能公平的实...

    zhisheng
  • 申请无数个iTunes 帐号的简易方法 博客分类: 柴米油盐

    3、点开左边菜单栏STORE,iTunes Store,然后在右这的App Store里随便找一个分类,比如书籍,然后找一个免费的应用;

    阿敏总司令
  • Mybatis 解析 SQL 源码分析一

    在使用 Mybatis 的时候,我们在 Mapper.xml 配置文件中书写 SQL;文件中还配置了对应的dao,SQL 中还可以使用一些诸如for循环,if判...

    Java技术大杂烩

扫码关注云+社区

领取腾讯云代金券