专栏首页包罗万想Dan Boneh密码学笔记11

Dan Boneh密码学笔记11

11.Public Key Encryption from trapdoor permutations

1.Public key encryption: definitions and security

2.Constructions

3.The RSA trapdoor permutation

4.PKCS 1

5.Is RSA a one-way function?

6.RSA in practice

1.Public key encryption: definitions and security

加密用对方的公钥,对方解密用他的私钥

应用:仅针对窃听安全的密钥交换协议

x是共享密钥

公钥加密在非互动应用中非常有用。

Bob用Alice的公钥加密电子邮件后发送给Alice。

公钥加密用于建立会话。

非对称密码与对称密码的窃听安全定义的关系

对称密码中,分为一次加密和多次加密情况,安全性是不同的。

非对称加密中,只要一次加密是安全的,则多次加密也是安全的。

公私钥对天生就是用来加密多个信息的。

现在看看更强大的攻击者,主动攻击。

发送方会通过SSL把邮件加密后发给Gmail服务器,Gmail服务器会中断SSL连接,然后把邮件转发给合适的接收方。假设这份邮件是使用计数器模式加密的(篡改CBC的IV导致重定向)或类似的。,然后当攻击者截获了这个邮件,他可以改变接收方。Gmail服务器收到邮件后会转发给攻击者。

我们的目标是设计安全的公钥系统,即使攻击者可以篡改密文还可以解密特定的密文

有这么一个限制,攻击者可以提交任何他选择的密文,除了挑战密文。

攻击者可以询问他选择的任何密文的解密,除了挑战密文。即使攻击者获得素有的解密,他依然不能分辨出他得到的是m0还是m1的加密。这是一个非常保守的定义。攻击者的目标是判断挑战密文是m0还是m1的加密。

攻击者干了这么多,无法判断挑战密文是m0还是m1的加密。这个系统就是选择密文安全(CCA)的。

前面我们看过的电子邮件的例子的特点,假设选定的加密系统满足给定信息的的加密,攻击者可以改变接收方从to Alice 改成to Charlie。

那么我们可以这样赢得CCA游戏,攻击思路如下:

第一步攻击者得到了公钥,攻击者会发出两个等长度的明文,第一个明文body是0,第二个明文body是1。两个明文都给Alice。Alice回复后,攻击者会得到挑战密文c。现在攻击者会使用他的能力去修改接收方,他会返回给Alice一个密文c'。c'是to Charlie的明文加密结果,其body是挑战密文c记为b。现在因为明文不同,密文也不同,所以c'一定和挑战密文c不一样。因此,挑战者现在必须解密,根据CCA游戏的定义,挑战者必须解密任何不同于挑战密文的密文。 那么挑战者解密了,给攻击者解密结果m',他给了攻击者b,现在攻击者可以输出挑战结果b了。他以优势1赢得了这个游戏。

因为攻击者能够改变挑战密文从一个接收方改到另一个,使得他能以优势1赢下这个CCA游戏。

2.Constructions

构建CCA安全的系统

陷门置换trapdoor permutation

使用公钥pk计算这个函数在任意点的值,使用私钥sk计算函数的逆

安全的陷门函数

单向函数,这个函数可以在任一点计算,但求它的逆是困难的

简单说,非常容易地从正向计算这个函数,但没人能从反方向计算这个函数。除非他们有这个陷门私钥sk

对称加密系统取K中的密钥,陷门函数取X中的元素作为输入

哈希函数H,从X映射到K,也就是把集合X中的元素映射成密钥用于对称加密系统。开始构建公钥加密系统

陷门函数F只用于随机值x,信息是用对称密钥系统加密的。

ro表示CCA安全性。

这个方案是CCA安全的。

ISO标准定义了这种公钥加密模式

一种错误使用陷门函数来构建的公钥加密系统

为什么不要用陷门函数直接加密信息?是完全不安全的。

这里没有随机性被使用到,不可能是语义安全的。

永远不要这么做!

3.The RSA trapdoor permutation

一个经典的陷门函数叫做RSA

φ(N)其实和N很接近

意味着,如果我们选取模N中的随机元素,非常有可能这个元素也在Z_N*中。

非常不可能选择一个Z_N中的随机元素得到的元素却是不可逆的。

几乎所有的Z_N中的元素都是可逆的

e加密指数,d解密指数

对教科书式RSA 的攻击

服务器私钥为(N,d),公钥为(e,N)

浏览器生成随机数叫做预备主密钥K,用RSA直接加密K

双方都有了共享密钥

用RSA直接加密K ,攻击者看到的密文c=k^e in Zn

假设K的一个64位密钥,k是0到2^64-1的一个整数

首先,假设k正好能分解成几个差不多大小的数的乘积,写成k=k1·k2

K1和k2都小于2^34,这有20%的概率会发生,把这个k带入到定义密文的函数值,把k替换成k1·k2,k1移到另一边,得到这个灰色的方程

攻击者知道c、e、N,利用灰色方程进行中间相遇攻击

一旦找到合适的k1和k2,可以很容易地还原k

Step1构建一张表存放左边所有的的可能值

Step2检查右边的这个值是否在第一步构建的表里

暴力破解需要2^64次,这里只要2^34次做第一步。

因为要指数运算,所以整个破解用时2^40次

永远不要直接用RSA加密,必须通过一个加密机制,比如ISO标准

4.PKCS 1

公钥密码学一号标准

实际中,系统生成一个对称加密密钥,然后让RSA去加密这个给定的对称加密密钥,而不是生成对称密钥作为RSA加密的一部分。

实际中,RSA系统有一个输入的对称密钥需要加密。

例如,可能是个AES密钥128位,然后这个密钥被加密。把这128位扩展成整个模的大小,例如模是2048位的。然后应用RSA函数。

如何进行这样的预处理呢?把128扩展成2048再RSA

如何论证得到的系统是安全的呢?

广泛应用PKCS1.5

模式2 表示加密,模式1 表示签名

PKCS1模式2:

取明文比如128位的AES密钥,放在要产生的值的最低128位,接下来在它后面附上16个1,即16进制的FF,然后接下来把它附在这个随机密码本的后面,这个密码本中任何地方都不含FF,这个密码本类似于1900位随机数,但是不含FF。最后在结果的最高位放上02,表示这个明文已经被PKCS1模式2编码了。这就是整个2048位的字符串。作为RSA的输入。

解密的时候,识别02,移除掉前面的密码本直到遇到FF。

这个机制应用非常广泛,比如HTTPS

当PKCS1使用在HTTPS中时,攻击思路

假设攻击者截获了PKCS1的密文

服务器检查密文的前两个字节是不是02。不是就error

攻击者可以测试任意密文的逆是否以02开头,这足以完全解密攻击者想解密的任何密文。

攻击者选择一个随机值r,构建一个新密文c'也就是r^e·c mod N

如果我们把r带入RSA函数,我们只是与RSA明文相乘,PKCS1封装的明文m乘以r,计算整项的e次方。

询问r·x的开头是否是02,数百万次,就可以还原x的全部了。

为什么呢?

举个例子叫做baby bleichenbacher

设想攻击者可以发送密文c,网页服务器会用私钥解密,假设服务器不检查开头是否是02,而是看最高位是否是1. 如果是1,服务器说yes。不是1 返回no。进一步简化,假设RSA的模N是2的某次幂。

现在,通过给服务器发送密文c,攻击者只是学习明文x的最高位。

服务器完全泄露了最高位yes、no。

现在攻击者可以把密文乘以2^e。就有去乘明文x的效果。2x。因为我们是在2的n次方模下的。乘2就意味着左移。

学到2x的最高位,就等于学到了x的次高位。

重复这一步,大约一两千次,就还原了x

需要询问上百万次是因为攻击者要询问开头是否是02.

如何抵抗这一攻击?RFC尽力改动最小。

用RSA解密后,你会获得一个并不是PKCS1编码的明文也就是说不是02开头的。你可以选取某个随机字符串r,只假定明文是一个随机字符串r,当什么也没发生。当然稍后协议会失败。

也就是说,如果PKCS1编码失败 ,你会说预备主密钥是这个随机字符串,我们继续协议,然后建立会话失败。导致会话终止。

不告诉攻击者开头是否是02,只是假定明文是某个随机值

用一种不同的方法来进行使用RSA的加密,即所谓的优化非对称加密补齐OAEP。

OAEP是更好的使用RSA加密的方法。

128位的AES,再附上01,然后再加一组0,然后也选择一个随机值,使得整个字符串与你的RSA模一样大比如说2047位。

在你应用RSA函数之前,首先选取你选的随机数把它交给哈希函数。

这个哈希函数产生一个值与你编码的左边一样大。把输出求异或。把得到的结果交给另一个哈希函数G。用一个随机值去异或,最后得到两个值。联结起来得到2047位长的字符串。

后来有人证明了事实上如果只假设RSA函数是陷门函数,是一个安全的陷门函数。使用RSA加密是CCA安全的话,我们还必须假设函数H和G是某种理想的哈希函数才行。这些叫做随机神谕。假设H和G 是随机函数。

在实际中,实现OAEP时,对于H和G,人们就使用SHA-256

为什么要叫做优化非对称加密补齐呢?Optimalasymmetric encryption padding

为什么要说优化呢?

如果你看密文,会注意到其密文是尽可能短的。密文与RSA输出一样长。

在ISO标准中,加密非常短的明文,必须使用RSA加密x,在x后面附上使用对称加密系统加密的短消息,即使你必须加密128位AES密钥,根据ISO标准,你会获得一个RSA输出加上一段对称密码。而在OAEP中,只获得了一个RSA输出,没有其他东西。

所以密文长度是优化的。

这个定理依赖于RSA的性质,事实上,如果你使用一个普通的陷门置换,那么这个定理不成立。其他的置换未必具备RSA的代数性质。

如果只有一个普通的陷门置换,如何正确的使用OAEP呢?

OAEP+, padding不是固定的010000

而是m和r的哈希值,这种方案是CCA安全的

SAEP+,当RSA的公钥指数等于3时,实际上不需要第二阶段的加密工作G

如何解密SAEP的密文ct。

先RSA逆得到x和r

最后我们要确保补齐w(m,r)是正确的。

如果是,输出m,不是,输出无效

检查补齐是否正确是很重要的

实际上,实现OAEP可能是很困难的。这对计时攻击来说是脆弱的。

5.Is RSA a one-way function?

在不知道陷门的情况下,求RSA的逆真的有这么难 吗?

如果可以分解模,使用中国剩余定理可解。

但是分解模是非常困难的问题。

一定要分解模N吗?

规约reduction,有一个计算模N的e次方根的算法,我们就能获得一个分解合数的算法。任何人都不能计算模N的e次方根以比分解模更快的速度

Φ(N)是偶数,e、d与φ(N)互质,e=2偶数不能拿来当作RSA指数,真正合法的最小的RSA指数等于3

如果我给你一个有效算法来计算模N的立方根,你能使用这个算法来分解模N吗?

提高RSA加解密的性能,用一个小的d

正常情况下,d约与模一般大,比如2000位,通过使用仅为128位的d,我可以提高RSA解密速度20倍。这是个非常糟糕的点子。

Michael wiener有个攻击,一旦私钥指数d小于模的4次方,如果模大约是2048位,这意味着如果d小于2的512次方,那么RSA是完全不安全的。

给定一个公钥e,可以很快地还原出私钥d。

所以有传言说,这个攻击可以针对最多512位,那么为什么不让这个模,比如530位,那么这个攻击就不能用了。但我们依然可以加速RSA解密4倍,因为我们把指数从2000位降到比如说530位。事实上还是不安全的。

wiener攻击有个扩展,如果d小于N^0.292,那么RSA也是不安全的。

即使d大约为N^0.4999,RSA依然是不安全的。

这不是正确的提高RSA性能的方法。

Wkener攻击的细节

我们有(N,e)目标是还原私钥指数d

d是小于N的四次方根的

两边同时除以d·φ(N)

加上绝对值

φ(N)与N非常接近

我们只需要这个分式小于1/根号N

我们知道e,不知道φ(N),所以不知道e/φ(N)

e/φ(N)与e/N 接近

p和q大约是N长度的一半

两边平方后再取倒数再乘0.5

中间那块红色,根据三角不等式推出,是绝对值的性质

满足这个条件的分式最多也只有log(N)个

这是一个著名的连分式算法continued fraction algorithm,它从分式e/N开始,他会还原log(N)个可能的k/d的值,我们只需要一个一个去试,直到我们找到正确的k/d,分母一定是d

如果私钥太小,小于N的四次方根的话,我们就可以轻松地完全还原d

6.RSA in practice

加速RSA,可以选择小点的e,推荐值,使用重复平方法,加密只要17次乘法。

标准的RSA解密,RSA-CRT,带中国剩余的RSA,这个方法让RSA解密速度加速4倍

如果使用128位的AES加密,应该使用一个3000位的模,尽管大家都用2048位模

一些针对RSA的攻击,数学上成功实现。但是这些实现对特定的侧信道攻击是脆弱的。

计时攻击、功耗分析攻击,错误攻击。

RSA解密时发生了某个错误,一个错误将完全泄露密钥。

许多密码学库都会检查RSA解密的结果在返回结果给调用者之前。

检查方法是取这个指数的输出,计算它的e次方,检查是否又回到了c mod N。如果是这样,说明这个解密是正确的。e比d小很多,所以这么做。这依然引入一个10%的开销。

展示一个这些攻击的例子

错误攻击,针对带中国剩余定理的RSA的

假设计算一个质数模q的时候发生错误,另一个模p没有发生错误

组合这两个结果后,会得到一个输出x'。

p能整除这个量,q不能

我们一旦获得N的因子分解,就可以计算φ(N)了,就可以自己根据公钥计算解密指数了,还原了私钥

另一种针对RSA的攻击,RSA密钥生成算法是有问题的。当它的熵不够时,(熵不够意味着随机性不强)这里会发生错误。

OpenSSL生成RSA密钥的方法如下:

先给这个伪随机数发生器以种子,然后他使用了伪随机数发生器生成的随机字符串来生成第一个质数p,他还会继续给伪随机数发生器种子,然后从伪随机数发生器生成q。最后输出p和q的乘积。

假设密钥生成正好是在防火墙启动后,prng还没有多少熵,防火墙很可能生成的质数p来自于一个低熵的集合,这意味着p的可能取值不多。在我们生成了p之后,生成质数实际上花了不少时间,几毫秒。防火墙生成的密钥会有更多熵,q来自高熵的集合。

现在的问题是,许多不同的防火墙,如果他们生成一个RSA密钥,他们中的许多最后会使用同样的质数p,但q不同。

如果我们看两个不同防火墙上的两个RSA模N1,N2,如果我们计算N1和N2的gcd,他们有着不同的q,但是p是一样的。所以如果我们计算gcd,会得到一个N的因子分解,还包括N1和N2,然后我们可以解出N1,N2的私钥了。

计算大量的公钥对N1和N2的gcd,发现了很多这些密钥都有公因子,就可以分解这些模了

许多网页服务器公钥都是脆弱的,只是因为它们使用了低熵的RSA密钥

生成密钥时,重要的是你的发生器的种子是合理选取的,不要在机器刚刚启动时就生成密钥。

第一篇,选择密文安全对公钥密码是如此重要,除了bleichenbacher攻击,还有许多其他攻击

第二篇,survey综述,讨论了许多RSA系统上的不同的攻击

第三篇,OAEP

第四篇,对RSA和其他公钥系统的密钥长度分析,为你的公钥系统选取合适密钥长度。即使你是在使用对称密钥系统。

补充。中国剩余定理CRT

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

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

原始发表时间:2019-09-06

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Dan Boneh密码学笔记7

    1.Active attacks on CPA-secure encryption

    安包
  • Dan Boneh密码学笔记4

    4.modes of operation: many time key (CBC)

    安包
  • Day1对称加密、分组密码模式

    特点:双向保证机密性;加密效率高, 适合加密大数据, 大文件;加密强度不高, 相对于非对称加密。

    安包
  • RSA会议:2015六大新型攻击趋势

    SANS专家在RSA会议上向大家展示了未来攻击方式的趋势。 该项研究由SANS主管John Pescatore主导,Counter Hack Challenge...

    FB客服
  • 利用OpenCV进行人脸对齐

    人脸对齐,即根据图像中人脸的几何结构对图像进行仿射变换(旋转、缩放、平移等),将人脸变换到一个统一的状态。人脸对齐是人脸识别的一个重要步骤,可以提升人脸识别的精...

    OpenCV学堂
  • Wi-Fi安全的未来:评估WPA3中的漏洞

    近期,安全研究专家Matty Vanhoef和Eyal Ronen对WPA3 Wi-Fi标准进行了一次安全分析研究,并成功从中发现了五个安全漏洞。其中,有四个安...

    FB客服
  • 一个“良心未泯”的国产敲诈者病毒分析

    一、 前言 近两年,以敲诈勒索为目的的文件加密恶意软件逐渐成为恶意软件中的主力军。以Locky家族,ceber家族为典型代表的敲诈勒索软件席卷国外,对政府机构,...

    FB客服
  • WannaCry 蠕虫详细分析

    2017 年 5 月 12 日,WannaCry 蠕虫通过 MS17-010 漏洞在全球范围大爆发,感染了大量的计算机,该蠕虫感染计算机后会向计算机中植入敲诈者...

    杜成法
  • 腾讯安全团队深入解析wannacry蠕虫病毒

    前言 原文作者:腾讯电脑管家 来源:http://www.freebuf.com/articles/system/134578.html 我只是知识的搬运...

    若与
  • 腾讯安全团队深入解析wannacry蠕虫病毒

    ? 作者:腾讯电脑管家 来源: http://www.freebuf.com/articles/system/134578.html 背景: 2017年5...

    小小科

扫码关注云+社区

领取腾讯云代金券