作者: evilpan
原文鏈接: https://mp.weixin.qq.com/s/c-GVbyzrdU7RV8qjW0NMIA

本文為作者投稿，Seebug Paper 期待你的分享，凡經采用即有禮品相送！
投稿郵箱：paper@seebug.org

前言

之前寫過一篇對稱加密與攻擊案例分析，而對于非對稱加密，雖然接觸的時間不短了，但一直沒有很系統的記錄過。因此趁著國慶家里蹲的五天長假，就來好好回顧總結一下。

其實從加密的定語就能看出，對稱加密表示通信雙方是擁有同樣信息的(即信息對稱)。信息可以是預共享的秘鑰(PSK)，也可以是事先約定的編解碼方法(如凱撒密碼)。非對稱加密則將信息分為兩部分，例如秘鑰A和秘鑰B，通過秘鑰A加密的信息可以用秘鑰B進行解密，反之通過秘鑰B加密的信息也可以通過秘鑰A進行解密。通常這對秘鑰可以叫做公鑰和私鑰，公鑰對外發布，私鑰自己保留，從而在信息不對稱的情況下實現加密和認證。

非對稱加密的實現方法有很多，大都依賴于難題假設(hardness assumptions)。基于一個常量時間內被公認不可解的難題，將該問題的答案分為不同因子，組成對應非對稱密碼學算法的公鑰和私鑰。例如RSA基于大素數分解問題，(EC)DSA基于離散對數問題等。本文重點關注RSA非對稱加密。

RSA原理

RSA應該是最早的公鑰加密系統之一了，其名稱是三個發明者的名字首字母縮寫(Rivest–Shamir–Adleman)。其算法所基于的難題假設是質數分解問題，在此之前先簡單介紹一下涉及到的數學基礎。

歐拉函數：φ(n)，表示小于n的正整數中與n互質的數的數目。如果n能寫做兩個不同質數p和q的乘積，那么則有φ(n) = (p - 1)(q - 1)。證明：略。
同余：給定一個正整m，如果兩個整數a和b滿足(a-b)被m整除，那么就稱為a和b對模m同余，記作a≡b(mod m)，其中≡是同余符號。同余的兩個數有一些有趣的特性，比如反身性、對稱性、傳遞性等等，詳見《數論》。
模逆元：也叫模倒數(modular multiplicative inverse)。整數a的模逆元為整數x，則滿足ax≡1(mod m)，其中m為模(modulus)。
歐拉公式：若a與n互為質數，則滿足a^φ(n)≡1(mod n)，證明：參考拉格朗日定理。
lcm：least common multiple，最小公倍數。
gcd：greatest common devisor，最大公約數。
互質：co-prime，兩個正整數a、b互質意味著能同時被它們整除的數只有1，即gcd(a, b) = 1

秘鑰構成

有了上面的數學基礎，再來看RSA公私鑰的組成和生成過程。秘鑰生成主要有以下幾步，其實每一步在實踐上都有注意事項，這個后面單獨說。

找到兩個不同的質數p和q
計算其乘積n=pq
計算φ(n)，由于p和q是質數，根據歐拉定理得φ(n) = lcm(p-1, q-1)
選擇一個整數e，滿足1 < e < φ(n)且gcd(e, φ(n)) = 1，即e和φ(n)互質
計算一個e的模逆元 d，對應模為φ(n)。計算過程涉及拓展歐幾里得算法和貝祖恒等式，d就是其中一個貝祖系數(coefficient)

在上面的數字中挑選出構造非對稱加密的元素：

公鑰：(n, e)
私鑰：(n, d)

e和d分別是公鑰和私鑰的核心，這兩個數互為模逆元。要想通過公鑰e推算出私鑰d，就需要知道φ(n)；而計算φ(n)=(p-1)(q-1)則需要知道p和q；公私鑰都已知n=pq，所以這就是難題假設的關鍵：當n很大的時候很難計算出對應的p和q。

加密與解密

假設我們有公鑰(n, e)，需要加密的內容為m，m是個小于n的正整數。則密文c為：

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

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

對方擁有私鑰(n, d)，對密文c解密可獲得明文m，方法如下：

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

這里值得注意的是，由于明文m是通過模n獲取的，所以要求m<n，這也是為什么RSA加密有長度限制的原因。

舉一個具體的例子，

p = 61, q = 53
n = 61 x 53 = 3233
φ(n) = lcm(p-1, q-1) = lcm(60, 52) = 780
e = 17
d = 413

公鑰: (n = 3233, e = 17)
私鑰: (n = 3233, d = 413)

加密和解密函數分別為：

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

假設加密的內容為1337，可以用python進行簡單的驗證：

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

感興趣的可以自己嘗試一下。

簽名和校驗

RSA算法除了可以用來進行加密，同樣也能用來進行簽名。簽名的目的是確保發送的信息是由對應私鑰的持有者發布的，而且信息沒有遇到篡改。公鑰簽名則使用私鑰校驗，私鑰簽名則使用公鑰校驗，和加密方向類似。

簽名所依賴的數學原理是指數的運算規則，對于整數h，有：

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

這里的h可以是我們所發送信息的哈希值，比如md5或者sha256。因此對于私鑰的持有者而言，簽名實際上就可以轉換為用私鑰對hash進行加密的過程。

消息的接收方收到信息以及加密的hash，使用發送者的公鑰對簽名進行解密，并計算消息的hash，將解密后的值與hash進行比對即可實現校驗過程。

安全陷阱

回顧上面秘鑰構成的一節，有幾個地方說得其實有點含糊，比如選擇p、q、e的地方，存在了一定的主觀性。只要滿足條件，就可以任意選擇嗎？事實上在有些場景下選擇不當也會導致潛在的安全問題。

質數選擇

我們知道在秘鑰生成的第一步就是選擇兩個足夠大的質數，這兩個數都是需要秘密保存的，任何一個數泄露都會導致質數分解的難度假設無效。那么問題來了，多大的數才算夠大？這兩個數之間的關系會影響難題假設嗎？

對于第一個問題，我們可以參考算力增長和近期的挑戰情況判斷。例如，一個稱為YAFU工具可以在20分鐘左右分解一個300位的質數，如下：

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

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

同時，對應權威機構的建議也是其中一個參考來源，例如NIST或者密碼局。根據NIST的判斷，非對稱加密的秘鑰強度和對稱加密之間有近似的類比關系：

1024位的RSA秘鑰強度相當于80位的對稱加密秘鑰
2048位的RSA秘鑰強度相當于112位的對稱加密秘鑰
3072位的RSA秘鑰強度相當于128位的對稱加密秘鑰

并且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，據不完全統計，涉及到的攻擊場景有下面這些：

Hastad's Broadcast Attack
Franklin-Reiter Related Message Attack
Coppersmith's Short Pad Attack
Partial Key Exposure Attack
...

感興趣的朋友可以查看文末的參考資料，這里就不展開了。值得一提的是這種情況的危害相對于前面選擇過小的私鑰指數情形而言相對較輕一些，即便選取了較小的公鑰指數，距離成功的攻擊也有不少的計算量。現實中私鑰指數一般選擇e = 2^16 + 1 = 65537就可以很好地防御攻擊了，后面在拆解一些現實中的秘鑰時也會看到。

Padding

我們前面所指的加密、解密和簽名運算，明文和密文標的都是一個整數，該整數小于n。這種方式叫做plain RSA(Textbook RSA或裸加密)，在現實中很少直接使用。plain RSA實際上存在許多安全隱患，列舉一些如下：

當使用較小的公鑰指數e(比如3)加密較小的明文m(比如*m<n^(1/e)*)時，由于m^e嚴格小于模n，因此只要對密文進行e方根取整，就可以很容易解密獲得明文。
如果同樣的明文發送給e個以上的接收方，并且接收方的公鑰指數e相同，p、q不同，那么通過中國剩余定理(孫子定理)，中間人就可以很容易解密出明文信息。可以參考前面提到的Coppersmith's Attack。

《孫子算經》：有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

另外最最重要的一點，由于RSA加密本身沒有隨機數參與，因此是一種確定性加密算法，即同樣的明文加密一定會出現同樣的密文。從這點來看，裸RSA加密并不是語義安全的。

非語義安全的加密系統，很有可能會受到Chosen plaintext attack攻擊的影響。舉例來說，RSA的一個特性是兩個密文的乘積等于對應明文的乘積：

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

如果攻擊者想要解密某個特定密文c ≡ m^e (mod n)，他可以讓私鑰持有方去解密一個構造的密文c′ ≡ cr^e (mod n)，r是攻擊者選擇的值。由于前面提到的乘積特性，實際上密文c'的明文值是mr (mod n)，因此如果解密成功，攻擊者就可以計算出原本密文c的明文m。

除了上面介紹的這些，裸加密很存在許多其他隱患。為了緩解這些問題，真實的RSA實現中通常還會在明文加密之前進行一定的填充。填充要求能引入足夠的隨機性，但是也需要能夠方便地對明文進行還原(unpading)。之前對稱加密介紹的一種填充PKCS#5可以實現后者，但是沒有隨機性。

PKCS#1標準中最初就包含了精心設計的填充方法。雖然是精心設計，但在1998年Bleichenbacher在Crypto會議上對其展示了一種稱為adaptive chosen ciphertext attack的攻擊方法，兩年后在Eurocrypt 大會上也有人提出一些潛在的不安全性。這期間PKCS#1標準也一直進行修訂，比如引入OAEP填充方式等。

如果使用過高級語言中封裝的RSA加密庫，應該也會發現其提供的接口都是可以指定Padding的，比如Python的例子：

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)

Java的例子：

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;
}

基礎設施

介紹完了理論，想必很多人也覺得枯燥無味了。誠然，理論與實踐結合才是密碼學大放異彩的地方，我們日常生活中每天上網用到的https，手機系統用到的應用簽名、Secure Boot，各種認證和校驗，無不涉及到非對稱加密。實踐依賴于背后的數學根基，但同時也在易用性和標準化上做了很多工作，在此基礎上構建了廣泛應用的秘鑰基礎設施。值得一提的是，這里的基礎設施并不是狹義的PKI，而是涉及到的標準和實踐，下面會挑一些來進行介紹。

ASN.1

為了解決高級語言中結構化數據在磁盤、網絡中傳輸后能夠進行還原，我們早先有JSON、XML等表示，現在有protobuf、thrift等序列化方法。不過在更早之前就有了跨平臺的抽象語法標準ASN.1(Abstract Syntax Notation One)，ASN.1定義在X.208中，提供了標準的IDL接口描述語言，可以用來表示一系列類型和值。

在ASN.1中，類型就是一組值。有些類型包含了有限的值，但是有些類型也可以包含無限的值。ASN.1包含四種類型：

簡單類型，即沒有組合的”原子“類型
結構類型，類型的組合
標記類型，從其他類型衍生的類型
其他類型，例如CHOICE和ANY類型

類型和名稱都可以通過賦值符號::=進行命名。除了CHIOCE和ANY的每個ASN.1類型都包含一個標記(tag)，tag可以理解成唯一的標識符，當且僅當tag相等時對應類型才相等。tag也有4個種類：

通用標記(Universal)
應用標記(Application)
私有標記(Private)
上下文標記(Context-Specific)

通用標記是定義在X.208中的，具有全局唯一性，其他標記在不同應用中可能會有不同的含義。擁有通用標記的類型大部分是簡單類型，如BIT STRGING、INTEGER、IA5String、OBJECT IDENTIFIER等，也有結構類型如SEQUENCE、SET等。一個簡單的ASN.1文件如下：

Person ::= SEQUENCE {
    age INTEGER,
    name OCTETSTRING,
    birth Date, -- 注釋：這里的組合類型在下面定義
}
Date ::= SEQUENCE {
    year INTEGER,
    month INTEGER,
    day INTEGER
}

ASN.1僅僅是一個抽象的表示方法，編碼方式則定義在X.209中。常見的編碼實現有：

BER：Basic Encoding Rules
DER：Distinguished Encoding Rules
XER：XML Encoding Rules
JER：JSON Encoding Rules
...

編碼實現多種多樣，和RSA相關的主要是DER編碼。DER是BER的一個子集，編碼方式為TLV(Type-Length-Value)結構，具體定義在X.509標準中。

X.509

在密碼學中，X.509定義了公鑰證書的標準(RFC5280)，其最常見的應用場景之一就是HTTPS中的TLS/SSL認證中。公鑰證書中包括公鑰和身份信息(如域名、組織或個人)，并且是經過簽名的。權威認證的簽名機構CA(certificate authority )公鑰證書預置在我們的瀏覽器或者操作系統中，因此可以認證簽名的有效性。

X.509同樣使用ASN.1來描述，但經歷了多個版本的變化，例如：

https://tools.ietf.org/html/rfc2459#appendix-A
https://tools.ietf.org/html/rfc3280#appendix-A
https://tools.ietf.org/html/rfc5280#appendix-A

事實上X.509是由國際電信聯盟(ITU)管理的，權威版本可以在ITU的網站上看到，同時ITU也提供了X.509以及對應拓展包的ASN.1壓縮包下載。

X509中定義了許多字段，列舉一些常見的解釋一下：

Serial Number：CA所簽名的證書都都包含的一個針對該CA的序列號
Subject：主題名稱，CA所簽名的目標對象標識符，通常使用X.500或者LDAP格式來描述
Issuer：簽發者名稱，CA本身的標識符。對于自簽名的證書而言，Issuer和Subject是相同的，例如根證書
Subject Public Key Info：Subject的公鑰信息，包括公鑰算法和對應的公鑰，例如RSA公鑰則包括之前介紹過的模n和公鑰指數e的值
Signature：Issuer對Subject公鑰證書的簽名
Validity period：Issuer對Subject公鑰證書簽名的有效時間

以B站的的HTTPS證書為例，我們也可以使用openssl查看公鑰詳細信息：

$ 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:58
    Signature Algorithm: sha256WithRSAEncryption
        Issuer:
            countryName               = BE
            organizationName          = GlobalSign nv-sa
            commonName                = GlobalSign Organization Validation CA - SHA256 - G2
        Validity
            Not Before: Sep 18 09:32:07 2018 GMT
            Not After : Sep 18 09:21:04 2020 GMT
        Subject:
            countryName               = CN
            stateOrProvinceName       = 上海
            localityName              = 上海
            organizationName          = 上海幻電信息科技有限公司
            commonName                = *.bilibili.com
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                Public-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:f9
                Exponent: 65537 (0x10001)
        X509v3 extensions:
            X509v3 Key Usage: critical
                Digital Signature, Key Encipherment
            Authority Information Access:
                CA Issuers - URI:http://secure.globalsign.com/cacert/gsorganizationvalsha2g2r1.crt
                OCSP - URI:http://ocsp2.globalsign.com/gsorganizationvalsha2g2

            X509v3 Certificate Policies:
                Policy: 1.3.6.1.4.1.4146.1.20
                  CPS: https://www.globalsign.com/repository/
                Policy: 2.23.140.1.2.2

            X509v3 Basic Constraints:
                CA:FALSE
            X509v3 Subject Alternative Name:
                DNS:*.bilibili.com, DNS:bilibili.com
            X509v3 Extended Key Usage:
                TLS Web Server Authentication, TLS Web Client Authentication
            X509v3 Subject Key Identifier:
                0D:DB:87:B5:F7:C5:57:18:2B:1F:71:56:19:64:1A:DE:C3:C9:12:06
            X509v3 Authority Key Identifier:
                keyid:96:DE:61:F1:BD:1C:16:29:53:1C:C0:CC:7D:3B:83:00:40:E6:1A:7C

            1.3.6.1.4.1.11129.2.4.2:
                ...i.g.u..u..Y|..C._..n.V.GV6.J.`....^......e.........F0D. ^.R..~AV|..A.....@..c.......u ... A$MqBP..iY1Jl]c......}..o.p.(.t..v.......X......gp
.....e.........G0E. s.2...-.*+..!......+Ui..2....j;..!..v..v$-m.R..Z#J. TB....3...7x..Y.v.oSv.1.1.....Q..w.......).....7.....e.........G0E.!....v]W....'.\G.]....B..Hn.c....u. ..Cb.....l0L.-.......O....7.....
    Signature Algorithm: sha256WithRSAEncryption
         35: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:91

可以看到實際中的公鑰指數e為65537，這里的Modulus即為n，使用冒號分隔十六進制的方式表示，轉換為整數是0x00dace77d9e2...，另外如名字所言，X509第三版(v3)包含了可選的拓展選項，對于HTTPS而言最重要的是Subject Alternative Name，即所認證的域名。其他拓展選項詳細說明可以參考RFC5280的介紹。

秘鑰分析

最后再來分析幾個實際落到我們磁盤上的秘鑰結構。

ssh

對于開發者而言ssh都不會陌生，其除了可以使用密碼登錄遠程服務器，也可以通過私鑰登錄。使用ssh-keygen工具可以直接生成私鑰id_rsa和公鑰id_rsa.pub，格式為RSA-2048。先看公鑰：

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDEkBTUATNtj5xzF8S+CXzh+8A3LzTXeHyIZams0g37hAFi1SmYK82QAANxUzypUSZSHTY+WnMjOmNEpqgEmE5MWg3tYp4hK7tSyI2/UYUQu8y9KUPa7dnwYA+gkPWxM4sEu3u3bh6dP6bf/t8u6I1fca4tmiEcIqlq3DRz9YQXwIHr27ld5gHFiyEO6vi1ECtddnz6DKuzpQ6Dj1QNVmCF6N81DXfpmTRmVIZV+vZbfD35f1/iw116jQ5lW5VVF00fz7NqYgdK3KH9TiSexJduXjMczyamrTjotNpWZo98JcltkxJF1vYRPIDgX7rTbOzIV/DiCzgROU3JmacI9lmf evilpan

其中重要的中間的base64，解碼后hexdump出來如下：

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.).+...
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.!+.R
00000060: c88d bf51 8510 bbcc bd29 43da edd9 f060  ...Q.....)C....`
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  !.....+]v|......
000000b0: 838f 540d 5660 85e8 df35 0d77 e999 3466  ..T.V`...5.w..4f
000000c0: 5486 55fa f65b 7c3d f97f 5fe2 c35d 7a8d  T.U..[|=.._..]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公鑰的定義如下：

The "ssh-rsa" key format has the following specific encoding:

      string    "ssh-rsa"
      mpint     e
      mpint     n

而在RFC4251中包含了string和mprint類型的定義：

string

    [...] They are stored as a uint32 containing its length
    (number of bytes that follow) and zero (= empty string) or more
    bytes that are the value of the string.  Terminating null
    characters are not used. [...]

mpint

    Represents multiple precision integers in two's complement format,
    stored as a string, 8 bits per byte, MSB first. [...]

說白了三個字段都是Length-Value格式，轉換如下：

(4 bytes)   00 00 00 07          = 7
(7 bytes)   73 73 68 2d 72 73 61 = "ssh-rsa" 字符串
(4 bytes)   00 00 00 03          = 3
(3 bytes)   01 00 01             = 65537 (公鑰指數e)
(4 bytes)   00 00 01 01          = 257
(257 bytes) 00 c4 .. f6 59 9f    = 模n

再看私鑰：

注意這里和網上很多文章說的不太一樣了，因為之前ssh-keygen生成的直接是RSA私鑰，比如：

前者是PKCS#1定義的DER編碼私鑰，在下一節中詳細介紹。以前openssh默認是支持PKCS#1的，不過現在使用了自己的一套格式，大致布局如下：

"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 format
    32-bit length, keytype
    32-bit length, pub0
    32-bit length, pub1
32-bit length for rnd+prv+comment+pad
    64-bit dummy checksum?  # a random 32-bit int, repeated
    32-bit length, keytype  # the private key (including public)
    32-bit length, pub0     # Public Key parts
    32-bit length, pub1
    32-bit length, prv0     # Private Key parts
    ...                     # (number varies by type)
    32-bit length, comment  # comment string
    padding bytes 0x010203  # pad to blocksize (see notes below)

詳細關于OpenSSH新的私鑰格式詳情可以參考：

The OpenSSH Private Key Format
https://github.com/openssh/openssh-portable/blob/master/sshkey.c

AVB

AVB即Android Verified Boot，是安卓中對系統鏡像完整性保護的方案。最近在工作中有對其進行了一點研究，不過這里并不是深入介紹AVB，而只看其中涉及到RSA的秘鑰。

在我們自行編譯安卓源碼(AOSP)時，會發現一系列秘鑰：

$ 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.pem

每組秘鑰分別負責用來對不同的組件進行簽名，我們主要看Verified Boot相關的秘鑰verity，安卓中使用該秘鑰對boot.img進行簽名，并自定義了簽名的ASN.1格式：

    AndroidVerifiedBootSignature DEFINITIONS ::=
    BEGIN
        formatVersion ::= INTEGER
        certificate ::= Certificate
        algorithmIdentifier ::= SEQUENCE {
            algorithm OBJECT IDENTIFIER,
            parameters ANY DEFINED BY algorithm OPTIONAL
        }
        authenticatedAttributes ::= SEQUENCE {
            target CHARACTER STRING,
            length INTEGER
        }
        signature ::= OCTET STRING
    END

其中證書Certificate類型是在X.509中定義的。

私鑰的存儲格式有幾種常見類型，比如PKCS#1(RFC3447)和PKCS#8(RFC5208)。

例如PKCS#1中定義私鑰的ASN.1表示如下：

  Version ::= INTEGER { two-prime(0), multi(1) }
      (CONSTRAINED BY
      {-- version must be multi if otherPrimeInfos present --})

  RSAPrivateKey ::= SEQUENCE {
      version           Version,
      modulus           INTEGER,  -- n
      publicExponent    INTEGER,  -- e
      privateExponent   INTEGER,  -- d
      prime1            INTEGER,  -- p
      prime2            INTEGER,  -- q
      exponent1         INTEGER,  -- d mod (p-1)
      exponent2         INTEGER,  -- d mod (q-1)
      coefficient       INTEGER,  -- (inverse of q) mod p
      otherPrimeInfos   OtherPrimeInfos OPTIONAL
  }

一般而言，我們保存的私鑰都是der格式，即使用DER對相應的ASN.1定義進行編碼。許多高級語言中提供了對應的庫函數方便從DER中進行反序列化獲取原始數據，比如Python的from Crypto.Util.asn1 import DerSequence。同時也有些在線工具可以方便查看DER的反序列化內容，比如：

https://lapo.it/asn1js
https://asn1.io/asn1playground/

回到上面的verity私鑰，我們將其轉換為PKCS#1格式：

openssl pkcs8 -nocrypt -in build/target/product/security/verity.pk8 -inform DER

解析對應的字段并將其與上面的ASN.1對比。

SEQUENCE (3 elem)
  INTEGER 0
  SEQUENCE (2 elem)
    OBJECT IDENTIFIER 1.2.840.113549.1.1.1 rsaEncryption (PKCS #1)
    NULL
  OCTET STRING (1 elem)
    SEQUENCE (9 elem)
      INTEGER 0
      INTEGER (2048 bit) 294034013011457495254632688690709311939827882765990777183788030470572…
      INTEGER 65537
      INTEGER (2047 bit) 152690229409630177395988743674731983661872870808474054654559379297267…
      INTEGER (1024 bit) 172086361699816285157285992007634379277365906572602995588734914497382…
      INTEGER (1024 bit) 170864216145358483792372871509731496788274625374475577044849125456480…
      INTEGER (1024 bit) 121316723122128141459586606081095008794617691006109580880887598144682…
      INTEGER (1024 bit) 160008079977555979458768333051051332108378146438007378884805916911676…
      INTEGER (1024 bit) 111229147058742660120109027367598084873926761525467238165320120548663…

可以對應RSA秘鑰的各個元素：

n = 2940340130...
e = 65537
d = 1526902294...
...

后記

本文主要介紹了RSA的基本原理以及常見的安全陷阱，其中大部分的實現隱患出在定義中關于選擇的地方，比如對于質數p、q以及公鑰指數e的選擇，在某些情況下選擇不當會導致在數學上求解難度驟減；RSA裸加密本身并非語義安全，容易受到CPA攻擊。對于現代機器學習而言，通過學習語義從端到端還原明文也不是不可能的事。

除此之外，RSA還存在時序攻擊、隨機數以及側信道等潛在威脅沒有在文中介紹。即便小心翼翼地按照最佳實踐去實現了RSA，也依然有不確定性：大質數分解真的很難嗎？這個問題目前并沒有確切證偽，只有經驗性的結論。有人說RSA-2048堅不可摧，對于這點我還是持懷疑態度，不說NSA已經“破解”了RSA，至少對于滿足某些條件的質數，可能存在特別的分解方式，畢竟歷史上密碼學的后門總是留得猝不及防。

雖然存在不確定性，RSA也已經是當今最為廣泛使用的秘鑰基礎設施根基，所以文章也對常見的實現標準和一些常見秘鑰進行了介紹和分析，一方面是對自己學習研究的記錄，另一方面也希望能對感興趣的朋友提供點參考。如果你也對密碼學感興趣，歡迎加群一起交流學習!

參考資料

WikiPedia - RSA cryptosystem
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
Twenty Years of Attacks on the RSA Cryptosystem
M. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36:553-558, 1990
A Layman's Guide to a Subset of ASN.1, BER, and DER

Paper 本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/1191/

Paper - 安全技術精粹

RSA 安全與秘鑰基礎設施

目錄

前言