本文转自网络文章&＃xff0c;内容均为非盈利&＃xff0c;版权归原作者所有。
转载此文章仅为个人收藏&＃xff0c;分享知识&＃xff0c;如有侵权&＃xff0c;马上删除。原文作者&＃xff1a;evilpan
原文地址&＃xff1a;RSA安全与秘钥基础设施
目录
前言
RSA原理
秘钥构成
加密与解密
签名和校验
安全陷阱
质数选择
私钥指数
公钥指数
Padding
基础设施
ASN.1
X.509
秘钥分析
ssh
AVB
后记
参考资料
其实从加密的定语就能看出&＃xff0c;对称加密表示通信双方是拥有同样信息的(即信息对称)。信息可以是预共享的秘钥(PSK)&＃xff0c;也可以是事先约定的编解码方法(如凯撒密码)。非对称加密则将信息分为两部分&＃xff0c;例如秘钥A和秘钥B&＃xff0c;通过秘钥A加密的信息可以用秘钥B进行解密&＃xff0c;反之通过秘钥B加密的信息也可以通过秘钥A进行解密。通常这对秘钥可以叫做公钥和私钥&＃xff0c;公钥对外发布&＃xff0c;私钥自己保留&＃xff0c;从而在信息不对称的情况下实现加密和认证。
非对称加密的实现方法有很多&＃xff0c;大都依赖于难题假设(hardness assumptions)。基于一个常量时间内被公认不可解的难题&＃xff0c;将该问题的答案分为不同因子&＃xff0c;组成对应非对称密码学算法的公钥和私钥。例如RSA基于大素数分解问题&＃xff0c;(EC)DSA基于离散对数问题等。本文重点关注RSA非对称加密。
RSA应该是最早的公钥加密系统之一了&＃xff0c;其名称是三个发明者的名字首字母缩写(Rivest–Shamir–Adleman)。其算法所基于的难题假设是质数分解问题&＃xff0c;在此之前先简单介绍一下涉及到的数学基础。
a和b对模m同余&＃xff0c;记作ab(mod m)&＃xff0c;其中是同余符号。同余的两个数有一些有趣的特性&＃xff0c;比如反身性、对称性、传递性等等&＃xff0c;详见《数论》。有了上面的数学基础&＃xff0c;再来看RSA公私钥的组成和生成过程。秘钥生成主要有以下几步&＃xff0c;其实每一步在实践上都有注意事项&＃xff0c;这个后面单独说。
在上面的数字中挑选出构造非对称加密的元素&＃xff1a;
e和d分别是公钥和私钥的核心&＃xff0c;这两个数互为模逆元。要想通过公钥e推算出私钥d&＃xff0c;就需要知道φ(n)&＃xff1b;而计算φ(n)&＃61;(p-1)(q-1)则需要知道p和q&＃xff1b;公私钥都已知n&＃61;pq&＃xff0c;所以这就是难题假设的关键&＃xff1a;当n很大的时候很难计算出对应的p和q。
假设我们有公钥(n, e)&＃xff0c;需要加密的内容为m&＃xff0c;m是个小于n的正整数。则密文c为&＃xff1a;
m^e c (mod n)
c &＃61; m^e mod n
使用模指数运算&＃xff0c;即便数字很大也可以很快算出。
对方拥有私钥(n, d)&＃xff0c;对密文c解密可获得明文m&＃xff0c;方法如下&＃xff1a;
c^d (m^e)^d m (mod n)
m &＃61; c^d mod n
这里值得注意的是&＃xff0c;由于明文m是通过模n获取的&＃xff0c;所以要求m 举一个具体的例子&＃xff0c; 加密和解密函数分别为&＃xff1a; 假设加密的内容为1337&＃xff0c;可以用python进行简单的验证&＃xff1a; 感兴趣的可以自己尝试一下。 RSA算法除了可以用来进行加密&＃xff0c;同样也能用来进行签名。签名的目的是确保发送的信息是由对应私钥的持有者发布的&＃xff0c;而且信息没有遇到篡改。公钥签名则使用私钥校验&＃xff0c;私钥签名则使用公钥校验&＃xff0c;和加密方向类似。 签名所依赖的数学原理是指数的运算规则&＃xff0c;对于整数h&＃xff0c;有&＃xff1a; 这里的h可以是我们所发送信息的哈希值&＃xff0c;比如md5或者sha256。因此对于私钥的持有者而言&＃xff0c;签名实际上就可以转换为用私钥对hash进行加密的过程。 消息的接收方收到信息以及加密的hash&＃xff0c;使用发送者的公钥对签名进行解密&＃xff0c;并计算消息的hash&＃xff0c;将解密后的值与hash进行比对即可实现校验过程。 回顾上面秘钥构成的一节&＃xff0c;有几个地方说得其实有点含糊&＃xff0c;比如选择p、q、e的地方&＃xff0c;存在了一定的主观性。只要满足条件&＃xff0c;就可以任意选择吗&＃xff1f;事实上在有些场景下选择不当也会导致潜在的安全问题。 我们知道在秘钥生成的第一步就是选择两个足够大的质数&＃xff0c;这两个数都是需要秘密保存的&＃xff0c;任何一个数泄露都会导致质数分解的难度假设无效。那么问题来了&＃xff0c;多大的数才算够大&＃xff1f;这两个数之间的关系会影响难题假设吗&＃xff1f; 对于第一个问题&＃xff0c;我们可以参考算力增长和近期的挑战情况判断。例如&＃xff0c;一个称为YAFU工具可以在20分钟左右分解一个300位的质数&＃xff0c;如下&＃xff1a; 截止至2019年&＃xff0c;被分解的最大RSA数有795位&＃xff0c;分解使用了900个CPU年的算力。 同时&＃xff0c;对应权威机构的建议也是其中一个参考来源&＃xff0c;例如NIST或者密码局。根据NIST的判断&＃xff0c;非对称加密的秘钥强度和对称加密之间有近似的类比关系&＃xff1a; 并且NIST建议目前的RSA秘钥安全强度是2048位&＃xff0c;如果需要工作到2030年之后&＃xff0c;就使用3072位的秘钥。 解决了秘钥长度的问题&＃xff0c;我们再看p和q以及它们的关系。判断一个数是不是质数(素数)的方法称为素性测试。其中有一些算法可以提高测试速度&＃xff0c;比如启发性测试和费马素性测试&＃xff0c;后者通常用来在RSA秘钥生成中快速筛选数据。 在"A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"中提出&＃xff0c;出于安全性考量&＃xff0c;p和q应该随机选取&＃xff0c;而且应该有相似的量级&＃xff0c;但是在长度上又有若干位的不同&＃xff0c;才能更难被计算机分解。这其实是从实践上考虑的&＃xff0c;但也引出了一个问题&＃xff1a;什么样的数好分解&＃xff0c;什么样的数难分解&＃xff1f;只可惜目前并没有明确的结论。也许在数学专家的钻研下&＃xff0c;已经有了一种快速分解满足特定条件大数的方法&＃xff0c;只不过出于“国家安全”并未公开&＃xff0c;这大概也是我们推国密而舍RSA的原因之一吧。 私钥指数就是私钥中的d&＃xff0c;在计算时我们提到这是模逆元算式的一个解。事实上该算式通常是多解的&＃xff0c;那么在这种情况下如何选择呢&＃xff1f;正确答案是随机选择一个解。曾经有过的情况是秘钥生成者为了解密时计算速度更快&＃xff0c;选择一个比较小的d作为私钥指数。由于模指数运算的时间复杂度是log2(d)&＃xff0c;在模为1024字节的情况下&＃xff0c;一个较小的d甚至可以令运算速度提高10倍。 这样看似没怎么影响安全性&＃xff0c;但实际上 因此&＃xff0c;使用一个过小的私钥指数虽然提升了解密运算速度&＃xff0c;但同时也提升了攻击者还原私钥d的计算效率。 详细的证明过程见: M. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36:553-558, 1990 前面秘钥生成的过程中第四步我们说需要选择一个整数e&＃xff0c;满足1 作为一个选择困难症患者&＃xff0c;依旧是看到选择两个字就犯难。既然要求e和φ(n)互质即可&＃xff0c;那么我随便选个满足要求的质数不就行了吗&＃xff0c;比如e&＃61;3。估计抱有和我同样想法的人不在少数&＃xff0c;但这样其实是有问题的&＃xff0c;从结论上看会导致攻击者可以在特定情况下较为高效地还原私钥d&＃xff0c;据不完全统计&＃xff0c;涉及到的攻击场景有下面这些&＃xff1a; 感兴趣的朋友可以查看文末的参考资料&＃xff0c;这里就不展开了。值得一提的是这种情况的危害相对于前面选择过小的私钥指数情形而言相对较轻一些&＃xff0c;即便选取了较小的公钥指数&＃xff0c;距离成功的攻击也有不少的计算量。现实中私钥指数一般选择 我们前面所指的加密、解密和签名运算&＃xff0c;明文和密文标的都是一个整数&＃xff0c;该整数小于n。这种方式叫做plain RSA(Textbook RSA或裸加密)&＃xff0c;在现实中很少直接使用。plain RSA实际上存在许多安全隐患&＃xff0c;列举一些如下&＃xff1a; 《孙子算经》&＃xff1a;有物不知其数&＃xff0c;三三数之剩二&＃xff0c;五五数之剩三&＃xff0c;七七数之剩二。问物几何&＃xff1f; 另外最最重要的一点&＃xff0c;由于RSA加密本身没有随机数参与&＃xff0c;因此是一种确定性加密算法&＃xff0c;即同样的明文加密一定会出现同样的密文。从这点来看&＃xff0c;裸RSA加密并不是语义安全的。 非语义安全的加密系统&＃xff0c;很有可能会受到Chosen plaintext attack攻击的影响。举例来说&＃xff0c;RSA的一个特性是两个密文的乘积等于对应明文的乘积&＃xff1a; 如果攻击者想要解密某个特定密文c m^e (mod n)&＃xff0c;他可以让私钥持有方去解密一个构造的密文c′ cr^e (mod n)&＃xff0c;r是攻击者选择的值。由于前面提到的乘积特性&＃xff0c;实际上密文c&＃39;的明文值是mr (mod n)&＃xff0c;因此如果解密成功&＃xff0c;攻击者就可以计算出原本密文c的明文m。 除了上面介绍的这些&＃xff0c;裸加密很存在许多其他隐患。为了缓解这些问题&＃xff0c;真实的RSA实现中通常还会在明文加密之前进行一定的填充。填充要求能引入足够的随机性&＃xff0c;但是也需要能够方便地对明文进行还原(unpading)。之前对称加密介绍的一种填充 [PKCS#1][rfc]标准中最初就包含了精心设计的填充方法。虽然是精心设计&＃xff0c;但在1998年Bleichenbacher在Crypto会议上对其展示了一种称为adaptive chosen ciphertext attack的攻击方法&＃xff0c;两年后在Eurocrypt 大会上也有人提出一些潜在的不安全性。这期间PKCS#1标准也一直进行修订&＃xff0c;比如引入 如果使用过高级语言中封装的RSA加密库&＃xff0c;应该也会发现其提供的接口都是可以指定Padding的&＃xff0c;比如&＃xff1a; Python的例子&＃xff1a; Java的例子&＃xff1a; 介绍完了理论&＃xff0c;想必很多人也觉得枯燥无味了。诚然&＃xff0c;理论与实践结合才是密码学大放异彩的地方&＃xff0c;我们日常生活中每天上网用到的 为了解决高级语言中结构化数据在磁盘、网络中传输后能够进行还原&＃xff0c;我们早先有JSON、XML等表示&＃xff0c;现在有protobuf、thrift等序列化方法。不过在更早之前就有了跨平台的抽象语法标准ASN.1(Abstract Syntax Notation One)&＃xff0c;ASN.1定义在 在ASN.1中&＃xff0c;类型就是一组值。有些类型包含了有限的值&＃xff0c;但是有些类型也可以包含无限的值。ASN.1包含四种类型&＃xff1a; 类型和名称都可以通过赋值符号 通用标记是定义在 ASN.1仅仅是一个抽象的表示方法&＃xff0c;编码方式则定义在 编码实现多种多样&＃xff0c;和RSA相关的主要是DER编码。DER是BER的一个子集&＃xff0c;编码方式为TLV(Type-Length-Value)结构&＃xff0c;具体定义在 在密码学中&＃xff0c;X.509定义了公钥证书的标准(RFC5280)&＃xff0c;其最常见的应用场景之一就是HTTPS中的TLS/SSL认证中。公钥证书中包括公钥和身份信息(如域名、组织或个人)&＃xff0c;并且是经过签名的。权威认证的签名机构CA(certificate authority )公钥证书预置在我们的浏览器或者操作系统中&＃xff0c;因此可以认证签名的有效性。 X.509同样使用ASN.1来描述&＃xff0c;但经历了多个版本的变化&＃xff0c;例如&＃xff1a; 事实上X.509是由国际电信联盟(ITU)管理的&＃xff0c;权威版本可以在ITU的网站上看到&＃xff0c;同时ITU也提供了X.509以及对应拓展包的ASN.1压缩包下载。 X509中定义了许多字段&＃xff0c;列举一些常见的解释一下&＃xff1a; 以B站的的HTTPS证书为例&＃xff0c;我们也可以使用openssl查看公钥详细信息&＃xff1a; 可以看到实际中的公钥指数e为65537&＃xff0c;这里的Modulus即为n&＃xff0c;使用冒号分隔十六进制的方式表示&＃xff0c;转换为整数是 最后再来分析几个实际落到我们磁盘上的秘钥结构。 对于开发者而言ssh都不会陌生&＃xff0c;其除了可以使用密码登录远程服务器&＃xff0c;也可以通过私钥登录。使用 其中重要的中间的base64&＃xff0c;解码后hexdump出来如下&＃xff1a; 这些数据怎么解析呢&＃xff1f;查阅 而在 说白了三个字段都是Length-Value格式&＃xff0c;转换如下&＃xff1a; 再看私钥&＃xff1a; 注意这里和网上很多文章说的不太一样了&＃xff0c;因为之前ssh-keygen生成的直接是RSA私钥&＃xff0c;比如&＃xff1a; 前者是PKCS#1定义的DER编码私钥&＃xff0c;在下一节中详细介绍。以前openssh默认是支持PKCS#1的&＃xff0c;不过现在使用了自己的一套格式&＃xff0c;大致布局如下&＃xff1a; 详细关于OpenSSH新的私钥格式详情可以参考&＃xff1a; AVB即 在我们自行编译安卓源码(AOSP)时&＃xff0c;会发现一系列秘钥&＃xff1a; 每组秘钥分别负责用来对不同的组件进行签名&＃xff0c;我们主要看Verified Boot相关的秘钥 其中证书 私钥的存储格式有几种常见类型&＃xff0c;比如PKCS#1(RFC3447)和PKCS#8(RFC5208)。 例如 一般而言&＃xff0c;我们保存的私钥都是der格式&＃xff0c;即使用DER对相应的ASN.1定义进行编码。许多高级语言中提供了对应的库函数方便从DER中进行反序列化获取原始数据&＃xff0c;比如Python的 回到上面的verity私钥&＃xff0c;我们将其转换为PKCS#1格式&＃xff1a; 解析对应的字段并将其与上面的ASN.1对比。 可以对应RSA秘钥的各个元素&＃xff1a; 本文主要介绍了RSA的基本原理以及常见的安全陷阱&＃xff0c;其中大部分的实现隐患出在定义中关于选择的地方&＃xff0c;比如对于质数p、q以及公钥指数e的选择&＃xff0c;在某些情况下选择不当会导致在数学上求解难度骤减&＃xff1b;RSA裸加密本身并非语义安全&＃xff0c;容易受到CPA攻击。对于现代机器学习而言&＃xff0c;通过学习语义从端到端还原明文也不是不可能的事。 除此之外&＃xff0c;RSA还存在时序攻击、随机数以及侧信道等潜在威胁没有在文中介绍。即便小心翼翼地按照最佳实践去实现了RSA&＃xff0c;也依然有不确定性&＃xff1a;大质数分解真的很难吗&＃xff1f;这个问题目前并没有确切证伪&＃xff0c;只有经验性的结论。有人说 虽然存在不确定性&＃xff0c;RSA也已经是当今最为广泛使用的秘钥基础设施根基&＃xff0c;所以文章也对常见的实现标准和一些常见秘钥进行了介绍和分析&＃xff0c;一方面是对自己学习研究的记录&＃xff0c;另一方面也希望能对感兴趣的朋友提供点参考。如果你也对密码学感兴趣&＃xff0c;欢迎加群一起交流学习&＃xff01; A Method for Obtaining Digital Signatures and Public-Key Cryptosystems Twenty Years of Attacks on the RSA Cryptosystemenc(m) &＃61; m^e mod n
dec(c) &＃61; c^d mod nenc(1337) &＃61; 1337**17 % 3233 &＃61; 1306
dec(1306) &＃61; 1306**413 % 3233 &＃61; 1337签名和校验
(h^e)^d &＃61; h^(e*d) &＃61; h^(d*e) &＃61; (h^d)^e h (mod n) 安全陷阱
质数选择
Bits Time Memory used 128 0.4886 seconds 0.1 MiB 192 3.9979 seconds 0.5 MiB 256 103.1746 seconds 3 MiB 300 1175.7826 seconds 10.9 MiB 私钥指数
M. Wiener提出了一种攻击方法]令这种情况完全破坏了RSA加密的根基。Wiener定理如下&＃xff1a;
公钥指数
e &＃61; 2^16 &＃43; 1 &＃61; 65537就可以很好地防御攻击了&＃xff0c;后面在拆解一些现实中的秘钥时也会看到。Padding
m1^e * m2^e (m1m2)^e (mod n)PKCS#5可以实现后者&＃xff0c;但是没有随机性。OAEP填充方式等。from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Hash import SHA256def encrypt(key, plainText)pubkey &＃61; RSA.importKey(key)cipher &＃61; PKCS1_OAEP.new(pubkey, hashAlgo&＃61;SHA256)encrypted &＃61; cipher.encrypt(plaintext)return base64.b64encode(encrypted)String decrypt(String privateKeyStr, cipherText) {byte[] cipherTextBytes &＃61; DatatypeConverter.parseBase64Binary(cipherText);byte[] privateKeyBytes &＃61; DatatypeConverter.parseBase64Binary(privateKeyStr);KeyFactory kf &＃61; KeyFactory.getInstance("RSA");PKCS8EncodedKeySpec ks &＃61; new PKCS8EncodedKeySpec(privateKeyBytes);PrivateKey privateKey &＃61; kf.generatePrivate(ks);Cipher c &＃61; Cipher.getInstance("RSA/ECB/OAEPWithSHA-256AndMGF1Padding");c.init(Cipher.DECRYPT_MODE, privateKey, new OAEPParameterSpec("SHA-256","MGF1", MGF1ParameterSpec.SHA256, PSource.PSpecified.DEFAULT));byte[] plainTextBytes &＃61; c.doFinal(cipherTextBytes);String plainText &＃61; new String(plainTextBytes);return plainText;
}基础设施
https&＃xff0c;手机系统用到的应用签名、Secure Boot&＃xff0c;各种认证和校验&＃xff0c;无不涉及到非对称加密。实践依赖于背后的数学根基&＃xff0c;但同时也在易用性和标准化上做了很多工作&＃xff0c;在此基础上构建了广泛应用的秘钥基础设施。值得一提的是&＃xff0c;这里的基础设施并不是狭义的PKI&＃xff0c;而是涉及到的标准和实践&＃xff0c;下面会挑一些来进行介绍。ASN.1
X.208中&＃xff0c;提供了标准的IDL接口描述语言&＃xff0c;可以用来表示一系列类型和值。CHOICE和ANY类型::&＃61;进行命名。除了CHIOCE和ANY的每个ASN.1类型都包含一个标记(tag)&＃xff0c;tag可以理解成唯一的标识符&＃xff0c;当且仅当tag相等时对应类型才相等。tag也有4个种类&＃xff1a;X.208中的&＃xff0c;具有全局唯一性&＃xff0c;其他标记在不同应用中可能会有不同的含义。拥有通用标记的类型大部分是简单类型&＃xff0c;如BIT STRGING、INTEGER、IA5String、OBJECT IDENTIFIER等&＃xff0c;也有结构类型如SEQUENCE、SET等。一个简单的ASN.1文件如下&＃xff1a;Person ::&＃61; SEQUENCE {age INTEGER,name OCTETSTRING,birth Date, -- 注释&＃xff1a;这里的组合类型在下面定义
}
Date ::&＃61; SEQUENCE {year INTEGER,month INTEGER,day INTEGER
}X.209中。常见的编码实现有&＃xff1a;X.509标准中。X.509
$ openssl s_client -connect bilibili.com:443 -showcerts 2>/dev/null | openssl x509 -noout -text -nameopt multiline,-esc_msb,utf8
Certificate:Data:Version: 3 (0x2)Serial Number:27:6d:f4:81:02:c7:45:53:a7:ee:12:58Signature Algorithm: sha256WithRSAEncryptionIssuer:countryName &＃61; BEorganizationName &＃61; GlobalSign nv-sacommonName &＃61; GlobalSign Organization Validation CA - SHA256 - G2ValidityNot Before: Sep 18 09:32:07 2018 GMTNot After : Sep 18 09:21:04 2020 GMTSubject:countryName &＃61; CNstateOrProvinceName &＃61; 上海localityName &＃61; 上海organizationName &＃61; 上海幻电信息科技有限公司commonName &＃61; *.bilibili.comSubject Public Key Info:Public Key Algorithm: rsaEncryptionPublic-Key: (2048 bit)Modulus:00:da:ce:77:ab:d9:e2:99:25:28:c1:4c:8e:15:ac:22:5a:8a:31:80:0f:20:3b:1d:a9:a6:d2:76:71:25:a0:8b:08:41:31:7a:7f:b9:d3:12:f4:c0:d6:d5:03:bf:7b:e7:56:f2:f0:5b:c4:69:ca:6f:aa:d5:eb:86:a7:06:2f:67:2b:93:d2:70:33:45:40:f7:18:48:68:d4:4f:65:5c:91:7c:aa:64:d4:e2:37:7b:7e:66:83:fe:b3:be:69:20:9b:20:5d:dd:1a:02:0d:53:e8:2a:91:7a:84:c5:12:66:bb:51:6c:c0:40:4a:9d:b5:19:39:35:3a:1d:80:55:7f:b0:85:61:8e:a5:87:24:7c:32:59:35:0d:2c:2e:80:6d:f1:a4:96:1d:12:aa:c9:a6:88:90:15:18:b3:c6:93:8e:49:36:53:20:d7:23:6c:5c:40:4e:23:87:8b:9f:6b:41:d2:52:ac:18:65:d8:6f:d9:a0:43:e6:e9:45:a2:81:e2:7e:f5:8b:0d:91:d2:c0:93:9b:8c:65:18:93:c1:de:1f:f2:82:0c:43:54:17:e9:79:7d:3d:d3:6b:bf:2b:d2:02:8a:93:7c:13:8f:1f:4f:62:81:58:54:81:4f:70:83:57:b0:47:62:1b:81:00:76:3c:46:6d:e7:07:1d:aa:35:5a:c8:f9Exponent: 65537 (0x10001)X509v3 extensions:X509v3 Key Usage: criticalDigital Signature, Key EnciphermentAuthority Information Access:CA Issuers - URI:http://secure.globalsign.com/cacert/gsorganizationvalsha2g2r1.crtOCSP - URI:http://ocsp2.globalsign.com/gsorganizationvalsha2g2X509v3 Certificate Policies:Policy: 1.3.6.1.4.1.4146.1.20CPS: https://www.globalsign.com/repository/Policy: 2.23.140.1.2.2X509v3 Basic Constraints:CA:FALSEX509v3 Subject Alternative Name:DNS:*.bilibili.com, DNS:bilibili.comX509v3 Extended Key Usage:TLS Web Server Authentication, TLS Web Client AuthenticationX509v3 Subject Key Identifier:0D:DB:87:B5:F7:C5:57:18:2B:1F:71:56:19:64:1A:DE:C3:C9:12:06X509v3 Authority Key Identifier:keyid:96:DE:61:F1:BD:1C:16:29:53:1C:C0:CC:7D:3B:83:00:40:E6:1A:7C1.3.6.1.4.1.11129.2.4.2:Signature Algorithm: sha256WithRSAEncryption35:13:01:e0:20:2c:84:ce:76:c9:91:9f:8e:74:f1:5e:49:0d:b9:2d:25:96:ae:e6:87:02:52:ce:0e:d7:64:71:81:8f:30:90:85:24:e1:2c:17:9c:78:31:97:c7:e8:c2:b2:3d:fd:b7:b1:41:25:94:1b:45:79:d4:33:8c:c0:1b:0c:0d:85:3b:8d:41:eb:0c:34:51:54:26:80:e6:a0:d4:ac:75:b3:c9:e9:16:8b:ae:9d:bd:2f:9a:2c:a2:29:49:20:aa:53:88:c7:70:64:ea:d6:67:a3:e7:c4:48:f1:16:64:a5:7a:6b:93:b0:af:00:ee:1c:5f:8d:d2:07:b7:ec:b7:da:1a:d8:e2:07:01:37:e0:78:6a:1c:d7:0d:9b:91:f0:7c:36:c6:8e:f2:59:d0:0a:f0:54:a8:db:a3:f5:c3:1a:24:03:38:86:b0:37:da:89:c1:70:35:c0:1e:02:a2:65:2a:95:68:b1:0e:40:56:0c:82:00:5d:8a:9f:f1:50:d9:ed:4b:43:d9:59:c8:70:75:ab:85:37:13:89:09:07:08:81:ca:b2:0a:bd:b9:57:52:d0:8d:4e:9c:64:06:4a:87:e3:71:3d:b5:47:91:a1:2d:0f:75:46:55:81:ea:a1:31:64:ce:27:c5:59:2e:bf:b5:2c:82:07:a2:32:b9:910x00dace77d9e2...&＃xff0c;另外如名字所言&＃xff0c;X509第三版(v3)包含了可选的拓展选项&＃xff0c;对于HTTPS而言最重要的是Subject Alternative Name&＃xff0c;即所认证的域名。其他拓展选项详细说明可以参考RFC5280的介绍。秘钥分析
ssh
ssh-keygen工具可以直接生成私钥id_rsa和公钥id_rsa.pub&＃xff0c;格式为RSA-2048。先看公钥&＃xff1a;ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDEkBTUATNtj5xzF8S&＃43;CXzh&＃43;8A3LzTXeHyIZams0g37hAFi1SmYK82QAANxUzypUSZSHTY&＃43;WnMjOmNEpqgEmE5MWg3tYp4hK7tSyI2/UYUQu8y9KUPa7dnwYA&＃43;gkPWxM4sEu3u3bh6dP6bf/t8u6I1fca4tmiEcIqlq3DRz9YQXwIHr27ld5gHFiyEO6vi1ECtddnz6DKuzpQ6Dj1QNVmCF6N81DXfpmTRmVIZV&＃43;vZbfD35f1/iw116jQ5lW5VVF00fz7NqYgdK3KH9TiSexJduXjMczyamrTjotNpWZo98JcltkxJF1vYRPIDgX7rTbOzIV/DiCzgROU3JmacI9lmf evilpan 00000000: 0000 0007 7373 682d 7273 6100 0000 0301 ....ssh-rsa.....
00000010: 0001 0000 0101 00c4 9014 d401 336d 8f9c ............3m..
00000020: 7317 c4be 097c e1fb c037 2f34 d778 7c88 s....|...7/4.x|.
00000030: 65a9 acd2 0dfb 8401 62d5 2998 2bcd 9000 e.......b.).&＃43;...
00000040: 0371 533c a951 2652 1d36 3e5a 7323 3a63 .qS<.Q&R.6>Zs#:c
00000050: 44a6 a804 984e 4c5a 0ded 629e 212b bb52 D....NLZ..b.!&＃43;.R
00000060: c88d bf51 8510 bbcc bd29 43da edd9 f060 ...Q.....)C....&＃96;
00000070: 0fa0 90f5 b133 8b04 bb7b b76e 1e9d 3fa6 .....3...{.n..?.
00000080: dffe df2e e88d 5f71 ae2d 9a21 1c22 a96a ......_q.-.!.".j
00000090: dc34 73f5 8417 c081 ebdb b95d e601 c58b .4s........]....
000000a0: 210e eaf8 b510 2b5d 767c fa0c abb3 a50e !.....&＃43;]v|......
000000b0: 838f 540d 5660 85e8 df35 0d77 e999 3466 ..T.V&＃96;...5.w..4f
000000c0: 5486 55fa f65b 7c3d f97f 5fe2 c35d 7a8d T.U..[|&＃61;.._..]z.
000000d0: 0e65 5b95 5517 4d1f cfb3 6a62 074a dca1 .e[.U.M...jb.J..
000000e0: fd4e 249e c497 6e5e 331c cf26 a6ad 38e8 .N$...n^3..&..8.
000000f0: b4da 5666 8f7c 25c9 6d93 1245 d6f6 113c ..Vf.|%.m..E...<
00000100: 80e0 5fba d36c ecc8 57f0 e20b 3811 394d .._..l..W...8.9M
00000110: c999 a708 f659 9f .....Y.RFC4253我们可以发现ssh公钥的定义如下&＃xff1a;The "ssh-rsa" key format has the following specific encoding:string "ssh-rsa"mpint empint n RFC4251中包含了string和mprint类型的定义&＃xff1a;string[...] They are stored as a uint32 containing its length(number of bytes that follow) and zero (&＃61; empty string) or morebytes that are the value of the string. Terminating nullcharacters are not used. [...]mpintRepresents multiple precision integers in two&＃39;s complement format,stored as a string, 8 bits per byte, MSB first. [...] (4 bytes) 00 00 00 07 &＃61; 7
(7 bytes) 73 73 68 2d 72 73 61 &＃61; "ssh-rsa" 字符串
(4 bytes) 00 00 00 03 &＃61; 3
(3 bytes) 01 00 01 &＃61; 65537 (公钥指数e)
(4 bytes) 00 00 01 01 &＃61; 257
(257 bytes) 00 c4 .. f6 59 9f &＃61; 模n-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAABFwAAAAdzc2gtcn
NhAAAAAwEAAQAAAQEAxJAU1AEzbY&＃43;ccxfEvgl84fvANy8013h8iGWprNIN&＃43;4QBYtUpmCvN
kAADcVM8qVEmUh02PlpzIzpjRKaoBJhOTFoN7WKeISu7UsiNv1GFELvMvSlD2u3Z8GAPoJ
...
-----END OPENSSH PRIVATE KEY----------BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCqGKukO1De7zhZj6&＃43;H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUp
wmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j&＃43;skZ6UtW&＃43;5u09lHNsj6tQ5
1s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQABAoGAFijko56&＃43;qGyN8M0RVyaRAXz&＃43;&＃43;xTqHBLh
...
-----END RSA PRIVATE KEY-----"openssh-key-v1"0x00 # NULL-terminated "Auth Magic" string
32-bit length, "none" # ciphername length and string
32-bit length, "none" # kdfname length and string
32-bit length, nil # kdf (0 length, no kdf)
32-bit 0x01 # number of keys, hard-coded to 1 (no length)
32-bit length, sshpub # public key in ssh format32-bit length, keytype32-bit length, pub032-bit length, pub1
32-bit length for rnd&＃43;prv&＃43;comment&＃43;pad64-bit dummy checksum? # a random 32-bit int, repeated32-bit length, keytype # the private key (including public)32-bit length, pub0 # Public Key parts32-bit length, pub132-bit length, prv0 # Private Key parts... # (number varies by type)32-bit length, comment # comment stringpadding bytes 0x010203 # pad to blocksize (see notes below)AVB
Android Verified Boot&＃xff0c;是安卓中对系统镜像完整性保护的方案。最近在工作中有对其进行了一点研究&＃xff0c;不过这里并不是深入介绍AVB&＃xff0c;而只看其中涉及到RSA的秘钥。$ ls build/target/product/security/
Android.mk media.x509.pem shared.pk8 testkey.x509.pem verity_key
README platform.pk8 shared.x509.pem verity.pk8
media.pk8 platform.x509.pem testkey.pk8 verity.x509.pemverity&＃xff0c;安卓中使用该秘钥对boot.img进行签名&＃xff0c;并自定义了签名的ASN.1格式&＃xff1a;AndroidVerifiedBootSignature DEFINITIONS ::&＃61;
BEGINformatVersion ::&＃61; INTEGERcertificate ::&＃61; CertificatealgorithmIdentifier ::&＃61; SEQUENCE {algorithm OBJECT IDENTIFIER,parameters ANY DEFINED BY algorithm OPTIONAL}authenticatedAttributes ::&＃61; SEQUENCE {target CHARACTER STRING,length INTEGER}signature ::&＃61; OCTET STRING
ENDCertificate类型是在X.509中定义的。PKCS#1中定义私钥的ASN.1表示如下&＃xff1a;Version ::&＃61; INTEGER { two-prime(0), multi(1) }(CONSTRAINED BY{-- version must be multi if otherPrimeInfos present --})RSAPrivateKey ::&＃61; SEQUENCE {version Version,modulus INTEGER, -- npublicExponent INTEGER, -- eprivateExponent INTEGER, -- dprime1 INTEGER, -- pprime2 INTEGER, -- qexponent1 INTEGER, -- d mod (p-1)exponent2 INTEGER, -- d mod (q-1)coefficient INTEGER, -- (inverse of q) mod potherPrimeInfos OtherPrimeInfos OPTIONAL
}from Crypto.Util.asn1 import DerSequence。同时也有些在线工具可以方便查看DER的反序列化内容&＃xff0c;比如&＃xff1a;openssl pkcs8 -nocrypt -in build/target/product/security/verity.pk8 -inform DER SEQUENCE (3 elem)INTEGER 0SEQUENCE (2 elem)OBJECT IDENTIFIER 1.2.840.113549.1.1.1 rsaEncryption (PKCS #1)NULLOCTET STRING (1 elem)SEQUENCE (9 elem)INTEGER 0INTEGER (2048 bit) 294034013011457495254632688690709311939827882765990777183788030470572…INTEGER 65537INTEGER (2047 bit) 152690229409630177395988743674731983661872870808474054654559379297267…INTEGER (1024 bit) 172086361699816285157285992007634379277365906572602995588734914497382…INTEGER (1024 bit) 170864216145358483792372871509731496788274625374475577044849125456480…INTEGER (1024 bit) 121316723122128141459586606081095008794617691006109580880887598144682…INTEGER (1024 bit) 160008079977555979458768333051051332108378146438007378884805916911676…INTEGER (1024 bit) 111229147058742660120109027367598084873926761525467238165320120548663… 后记
RSA-2048坚不可摧&＃xff0c;对于这点我还是持怀疑态度&＃xff0c;不说NSA已经“破解”了RSA&＃xff0c;至少对于满足某些条件的质数&＃xff0c;可能存在特别的分解方式&＃xff0c;毕竟历史上密码学的后门总是留得猝不及防。参考资料
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 
