之前写过一篇对称加密与攻击案例分析，而对于非对称加密，虽然接触的时间不短了，但一直没有很系统的记录过。因此趁着国庆家里蹲的五天长假，就来好好回顾总结一下。

其实从加密的定语就能看出，对称加密表示通信双方是拥有同样信息的(即信息对称)。信息可以是预共享的秘钥(PSK)，也可以是事先约定的编解码方法(如凯撒密码)。非对称加密则将信息分为两部分，例如秘钥A和秘钥B，通过秘钥A加密的信息可以用秘钥B进行解密，反之通过秘钥B加密的信息也可以通过秘钥A进行解密。通常这对秘钥可以叫做公钥和私钥，公钥对外发布，私钥自己保留，从而在信息不对称的情况下实现加密和认证。

非对称加密的实现方法有很多，大都依赖于难题假设(hardness assumptions)。基于一个常量时间内被公认不可解的难题，将该问题的答案分为不同因子，组成对应非对称密码学算法的公钥和私钥。例如RSA基于大素数分解问题，(EC)DSA基于离散对数问题等。本文重点关注RSA非对称加密。

RSA应该是最早的公钥加密系统之一了，其名称是三个发明者的名字首字母缩写(Rivest–Shamir–Adleman)。其算法所基于的难题假设是质数分解问题，在此之前先简单介绍一下涉及到的数学基础。

有了上面的数学基础，再来看RSA公私钥的组成和生成过程。秘钥生成主要有以下几步，其实每一步在实践上都有注意事项，这个后面单独说。

在上面的数字中挑选出构造非对称加密的元素：

e和d分别是公钥和私钥的核心，这两个数互为模逆元。要想通过公钥e推算出私钥d，就需要知道φ(n)；而计算φ(n)=(p-1)(q-1)则需要知道p和q；公私钥都已知n=pq，所以这就是难题假设的关键：当n很大的时候很难计算出对应的p和q。

假设我们有公钥(n, e)，需要加密的内容为m，m是个小于n的正整数。则密文c为：

使用模指数运算，即便数字很大也可以很快算出。

对方拥有私钥(n, d)，对密文c解密可获得明文m，方法如下：

这里值得注意的是，由于明文m是通过模n获取的，所以要求m<n，这也是为什么RSA加密有长度限制的原因。

举一个具体的例子，

加密和解密函数分别为：

假设加密的内容为1337，可以用python进行简单的验证：

感兴趣的可以自己尝试一下。

RSA算法除了可以用来进行加密，同样也能用来进行签名。签名的目的是确保发送的信息是由对应私钥的持有者发布的，而且信息没有遇到篡改。公钥签名则使用私钥校验，私钥签名则使用公钥校验，和加密方向类似。

签名所依赖的数学原理是指数的运算规则，对于整数h，有：

这里的h可以是我们所发送信息的哈希值，比如md5或者sha256。因此对于私钥的持有者而言，签名实际上就可以转换为用私钥对hash进行加密的过程。

消息的接收方收到信息以及加密的hash，使用发送者的公钥对签名进行解密，并计算消息的hash，将解密后的值与hash进行比对即可实现校验过程。

回顾上面秘钥构成的一节，有几个地方说得其实有点含糊，比如选择p、q、e的地方，存在了一定的主观性。只要满足条件，就可以任意选择吗？事实上在有些场景下选择不当也会导致潜在的安全问题。

我们知道在秘钥生成的第一步就是选择两个足够大的质数，这两个数都是需要秘密保存的，任何一个数泄露都会导致质数分解的难度假设无效。那么问题来了，多大的数才算够大？这两个数之间的关系会影响难题假设吗？

对于第一个问题，我们可以参考算力增长和近期的挑战情况判断。例如，一个称为YAFU工具可以在20分钟左右分解一个300位的质数，如下：

截止至2019年，被分解的最大RSA数有795位，分解使用了900个CPU年的算力。

同时，对应权威机构的建议也是其中一个参考来源，例如NIST或者密码局。根据NIST的判断，非对称加密的秘钥强度和对称加密之间有近似的类比关系：

并且NIST建议目前的RSA秘钥安全强度是2048位，如果需要工作到2030年之后，就使用3072位的秘钥。

解决了秘钥长度的问题，我们再看p和q以及它们的关系。判断一个数是不是质数(素数)的方法称为素性测试。其中有一些算法可以提高测试速度，比如启发性测试和费马素性测试，后者通常用来在RSA秘钥生成中快速筛选数据。

在"A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"中提出，出于安全性考量，p和q应该随机选取，而且应该有相似的量级，但是在长度上又有若干位的不同，才能更难被计算机分解。这其实是从实践上考虑的，但也引出了一个问题：什么样的数好分解，什么样的数难分解？只可惜目前并没有明确的结论。也许在数学专家的钻研下，已经有了一种快速分解满足特定条件大数的方法，只不过出于“国家安全”并未公开，这大概也是我们推国密而舍RSA的原因之一吧。

私钥指数就是私钥中的d，在计算时我们提到这是模逆元算式的一个解。事实上该算式通常是多解的，那么在这种情况下如何选择呢？正确答案是随机选择一个解。曾经有过的情况是秘钥生成者为了解密时计算速度更快，选择一个比较小的d作为私钥指数。由于模指数运算的时间复杂度是log2(d)，在模为1024字节的情况下，一个较小的d甚至可以令运算速度提高10倍。

这样看似没怎么影响安全性，但实际上M. Wiener提出了一种攻击方法]令这种情况完全破坏了RSA加密的根基。Wiener定理如下：

因此，使用一个过小的私钥指数虽然提升了解密运算速度，但同时也提升了攻击者还原私钥d的计算效率。

详细的证明过程见: M. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36:553-558, 1990

前面秘钥生成的过程中第四步我们说需要选择一个整数e，满足1 < e < φ(n)且gcd(e, φ(n)) = 1，即e和φ(n)互质。这个e是公钥的重要组成，因此称为公钥指数。

作为一个选择困难症患者，依旧是看到选择两个字就犯难。既然要求e和φ(n)互质即可，那么我随便选个满足要求的质数不就行了吗，比如e=3。估计抱有和我同样想法的人不在少数，但这样其实是有问题的，从结论上看会导致攻击者可以在特定情况下较为高效地还原私钥d，据不完全统计，涉及到的攻击场景有下面这些：

感兴趣的朋友可以查看文末的参考资料，这里就不展开了。值得一提的是这种情况的危害相对于前面选择过小的私钥指数情形而言相对较轻一些，即便选取了较小的公钥指数，距离成功的攻击也有不少的计算量。现实中私钥指数一般选择e = 2^16 + 1 = 65537就可以很好地防御攻击了，后面在拆解一些现实中的秘钥时也会看到。

我们前面所指的加密、解密和签名运算，明文和密文标的都是一个整数，该整数小于n。这种方式叫做plain RSA(Textbook RSA或裸加密)，在现实中很少直接使用。plain RSA实际上存在许多安全隐患，列举一些如下：

《孙子算经》：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

另外最最重要的一点，由于RSA加密本身没有随机数参与，因此是一种确定性加密算法，即同样的明文加密一定会出现同样的密文。从这点来看，裸RSA加密并不是语义安全的。

非语义安全的加密系统，很有可能会受到Chosen plaintext attack攻击的影响。举例来说，RSA的一个特性是两个密文的乘积等于对应明文的乘积：

如果攻击者想要解密某个特定密文c m^e (mod n)，他可以让私钥持有方去解密一个构造的密文c′ cr^e (mod n)，r是攻击者选择的值。由于前面提到的乘积特性，实际上密文c'的明文值是mr (mod n)，因此如果解密成功，攻击者就可以计算出原本密文c的明文m。

除了上面介绍的这些，裸加密很存在许多其他隐患。为了缓解这些问题，真实的RSA实现中通常还会在明文加密之前进行一定的填充。填充要求能引入足够的随机性，但是也需要能够方便地对明文进行还原(unpading)。之前对称加密介绍的一种填充PKCS#5可以实现后者，但是没有随机性。

[PKCS#1][rfc]标准中最初就包含了精心设计的填充方法。虽然是精心设计，但在1998年Bleichenbacher在Crypto会议上对其展示了一种称为adaptive chosen ciphertext attack的攻击方法，两年后在Eurocrypt 大会上也有人提出一些潜在的不安全性。这期间PKCS#1标准也一直进行修订，比如引入OAEP填充方式等。

如果使用过高级语言中封装的RSA加密库，应该也会发现其提供的接口都是可以指定Padding的，比如Python的例子：

Java的例子：

介绍完了理论，想必很多人也觉得枯燥无味了。诚然，理论与实践结合才是密码学大放异彩的地方，我们日常生活中每天上网用到的https，手机系统用到的应用签名、Secure Boot，各种认证和校验，无不涉及到非对称加密。实践依赖于背后的数学根基，但同时也在易用性和标准化上做了很多工作，在此基础上构建了广泛应用的秘钥基础设施。值得一提的是，这里的基础设施并不是狭义的PKI，而是涉及到的标准和实践，下面会挑一些来进行介绍。

为了解决高级语言中结构化数据在磁盘、网络中传输后能够进行还原，我们早先有JSON、XML等表示，现在有protobuf、thrift等序列化方法。不过在更早之前就有了跨平台的抽象语法标准ASN.1(Abstract Syntax Notation One)，ASN.1定义在X.208中，提供了标准的IDL接口描述语言，可以用来表示一系列类型和值。

在ASN.1中，类型就是一组值。有些类型包含了有限的值，但是有些类型也可以包含无限的值。ASN.1包含四种类型：

类型和名称都可以通过赋值符号::=进行命名。除了CHIOCE和ANY的每个ASN.1类型都包含一个标记(tag)，tag可以理解成唯一的标识符，当且仅当tag相等时对应类型才相等。tag也有4个种类：

通用标记是定义在X.208中的，具有全局唯一性，其他标记在不同应用中可能会有不同的含义。拥有通用标记的类型大部分是简单类型，如BIT STRGING、INTEGER、IA5String、OBJECT IDENTIFIER等，也有结构类型如SEQUENCE、SET等。一个简单的ASN.1文件如下：

ASN.1仅仅是一个抽象的表示方法，编码方式则定义在X.209中。常见的编码实现有：

编码实现多种多样，和RSA相关的主要是DER编码。DER是BER的一个子集，编码方式为TLV(Type-Length-Value)结构，具体定义在X.509标准中。

在密码学中，X.509定义了公钥证书的标准(RFC5280)，其最常见的应用场景之一就是HTTPS中的TLS/SSL认证中。公钥证书中包括公钥和身份信息(如域名、组织或个人)，并且是经过签名的。权威认证的签名机构CA(certificate authority )公钥证书预置在我们的浏览器或者操作系统中，因此可以认证签名的有效性。

X.509同样使用ASN.1来描述，但经历了多个版本的变化，例如：

事实上X.509是由国际电信联盟(ITU)管理的，权威版本可以在ITU的网站上看到，同时ITU也提供了X.509以及对应拓展包的ASN.1压缩包下载。

X509中定义了许多字段，列举一些常见的解释一下：

以B站的的HTTPS证书为例，我们也可以使用openssl查看公钥详细信息：

可以看到实际中的公钥指数e为65537，这里的Modulus即为n，使用冒号分隔十六进制的方式表示，转换为整数是0x00dace77d9e2...，另外如名字所言，X509第三版(v3)包含了可选的拓展选项，对于HTTPS而言最重要的是Subject Alternative Name，即所认证的域名。其他拓展选项详细说明可以参考RFC5280的介绍。

最后再来分析几个实际落到我们磁盘上的秘钥结构。

对于开发者而言ssh都不会陌生，其除了可以使用密码登录远程服务器，也可以通过私钥登录。使用ssh-keygen工具可以直接生成私钥id_rsa和公钥id_rsa.pub，格式为RSA-2048。先看公钥：

其中重要的中间的base64，解码后hexdump出来如下：

这些数据怎么解析呢？查阅RFC4253我们可以发现ssh公钥的定义如下：

而在RFC4251中包含了string和mprint类型的定义：

说白了三个字段都是Length-Value格式，转换如下：

再看私钥：

注意这里和网上很多文章说的不太一样了，因为之前ssh-keygen生成的直接是RSA私钥，比如：

前者是PKCS#1定义的DER编码私钥，在下一节中详细介绍。以前openssh默认是支持PKCS#1的，不过现在使用了自己的一套格式，大致布局如下：

详细关于OpenSSH新的私钥格式详情可以参考：

AVB即Android Verified Boot，是安卓中对系统镜像完整性保护的方案。最近在工作中有对其进行了一点研究，不过这里并不是深入介绍AVB，而只看其中涉及到RSA的秘钥。

在我们自行编译安卓源码(AOSP)时，会发现一系列秘钥：

每组秘钥分别负责用来对不同的组件进行签名，我们主要看Verified Boot相关的秘钥verity，安卓中使用该秘钥对boot.img进行签名，并自定义了签名的ASN.1格式：

其中证书Certificate类型是在X.509中定义的。

私钥的存储格式有几种常见类型，比如PKCS#1(RFC3447)和PKCS#8(RFC5208)。

例如PKCS#1中定义私钥的ASN.1表示如下：

一般而言，我们保存的私钥都是der格式，即使用DER对相应的ASN.1定义进行编码。许多高级语言中提供了对应的库函数方便从DER中进行反序列化获取原始数据，比如Python的from Crypto.Util.asn1 import DerSequence。同时也有些在线工具可以方便查看DER的反序列化内容，比如：

回到上面的verity私钥，我们将其转换为PKCS#1格式：

解析对应的字段并将其与上面的ASN.1对比。

可以对应RSA秘钥的各个元素：

本文主要介绍了RSA的基本原理以及常见的安全陷阱，其中大部分的实现隐患出在定义中关于选择的地方，比如对于质数p、q以及公钥指数e的选择，在某些情况下选择不当会导致在数学上求解难度骤减；RSA裸加密本身并非语义安全，容易受到CPA攻击。对于现代机器学习而言，通过学习语义从端到端还原明文也不是不可能的事。

除此之外，RSA还存在时序攻击、随机数以及侧信道等潜在威胁没有在文中介绍。即便小心翼翼地按照最佳实践去实现了RSA，也依然有不确定性：大质数分解真的很难吗？这个问题目前并没有确切证伪，只有经验性的结论。有人说RSA-2048坚不可摧，对于这点我还是持怀疑态度，不说NSA已经“破解”了RSA，至少对于满足某些条件的质数，可能存在特别的分解方式，毕竟历史上密码学的后门总是留得猝不及防。

虽然存在不确定性，RSA也已经是当今最为广泛使用的秘钥基础设施根基，所以文章也对常见的实现标准和一些常见秘钥进行了介绍和分析，一方面是对自己学习研究的记录，另一方面也希望能对感兴趣的朋友提供点参考。如果你也对密码学感兴趣，欢迎加群一起交流学习！

A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

Twenty Years of Attacks on the RSA Cryptosystem

m^e  c (mod n)
c = m^e mod n

c^d  (m^e)^d  m (mod n)
m = c^d mod n

enc(m) = m^e mod n
dec(c) = c^d mod n

enc(1337) = 1337**17 % 3233 = 1306
dec(1306) = 1306**413 % 3233 = 1337

(h^e)^d = h^(e*d) = h^(d*e) = (h^d)^e  h (mod n)

m1^e * m2^e  (m1m2)^e (mod n)

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Hash import SHA256

def encrypt(key, plainText) 
    pubkey = RSA.importKey(key)
    cipher = PKCS1_OAEP.new(pubkey, hashAlgo=SHA256)
    encrypted = cipher.encrypt(plaintext)
    return base64.b64encode(encrypted)

String decrypt(String privateKeyStr, cipherText) {
  byte[] cipherTextBytes = DatatypeConverter.parseBase64Binary(cipherText);
    byte[] privateKeyBytes = DatatypeConverter.parseBase64Binary(privateKeyStr);
  KeyFactory kf = KeyFactory.getInstance("RSA");
    PKCS8EncodedKeySpec ks = new PKCS8EncodedKeySpec(privateKeyBytes);
    PrivateKey privateKey = kf.generatePrivate(ks);

    Cipher c = Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");
    c.init(Cipher.DECRYPT_MODE, privateKey, new OAEPParameterSpec("SHA-256",
        "MGF1", MGF1ParameterSpec.SHA256, PSource.PSpecified.DEFAULT));
    byte[] plainTextBytes = c.doFinal(cipherTextBytes);
    String plainText = new String(plainTextBytes);
  return plainText;
}

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课