RSA加密算法在Java與C#中的跨語言密鑰轉換問題
前言
??前段時間遇到個項目問題，涉及RSA加密，研究了幾天，終于解決了，情況是這樣的，項目使用的是.net framework的框架，需要對網絡傳輸的個人數據進行加密，首先能從服務器直接獲取一個加密用的公鑰，使用這個公鑰對本地個人數據加密后，再進行傳輸。
??出現的問題是完成加密后的數據在服務器端始終無法解析，折騰了好一段時間才知道是由于服務器端的Java和客戶端的C#兩者使用的RSA算法的密鑰格式不一致，而.net framework沒有提供對于相應格式的密鑰的轉換支持，C#對RSA相關密鑰格式的支持在.net core之后才完善。
??問題找到了，解決方案兩條思路，第一找開源庫，研究了一下RSA，看了一圈github上的開源庫，感覺開源庫功能過于全面而復雜，引入項目增加的代碼量太大，又看一下解析規則，感覺并不是太復雜，于是嘗試第二條路自己解析，從頭記錄一下解決方案：
1 算法簡介
??RSA算法是一種廣泛使用的非對稱加密算法，是目前最優秀的公鑰方案之一。RSA算法基于一個數學理論支持，即獲取兩個大素數相乘的結果很簡單，而對它們的乘積進行因式分解卻極其困難。
對稱加密：同一個密鑰可以同時用作加密和解密，稱為對稱加密。
非對稱加密：非對稱加密算法需要兩個密鑰分別進行加密和解密，即公鑰和私鑰。
1.1 算法步驟
- p、q（兩個大素數）: 取兩個足夠大的素數p、q
- N（合數）: 令N = p * q
- L: L = (p-1) * (q-1)
- E（公有冪）: 使得E與L互質，且1 < E < L
- D（私有冪）: 使得（D*E）% L = 1，且1 < D < L
素數：除了1和它自身外，不能被其他自然數整除的大于1的自然數。
合數：除了素數以外的大于1的自然數。
互質:公約數只有1的兩個整數，叫做互質整數。
其中p和q是兩個很大的素數，N是他們的乘積，用于之后求模，它是個合數，即合數模，E是公鑰中的冪指數，D是私鑰中的冪指數。
得到的（E，N）即為公鑰，（D，N）即為私鑰。
公鑰與私鑰是一對，如果用公鑰對數據進行加密，只有用對應的私鑰才能解密；如果用私鑰對數據進行加密，那么只有用對應的公鑰才能解密。
公鑰加密——私鑰解密
加密過程：密文=（明文^E）mod N
解密過程：明文=（密文^D）mod N
也可以反過來，私鑰加密——公鑰解密
加密過程：密文=（明文^D）mod N
解密過程：明文=（密文^E）mod N
由于公鑰和私鑰都是數的組合，我們一般把合數模N的二進制位數長度稱作密鑰的長度。一般密鑰會要求一定的長度，RSA從提出到現在已近二十年，經歷了各種攻擊的考驗，目前被破解的最長RSA密鑰是768個二進制位，因此可以認為，768位的密鑰不用擔心受到除了國家安全管理（NSA）外的其他事物的危害，1024位的密鑰幾乎已經是安全的。
加、解密的過程是個模指數運算過程。
1.2 算法示例
取p = 3、q = 11
計算N：N = p * q = 3 * 11 = 33
計算L：L = (p - 1) * (q - 1) = 20
取E = 3，可滿足E與L互質，且1 < E < L
取D = 7，可滿足(D * E) % L = 1，即(D * 3) % 20 = 1，且1 < D < L
得到(3, 33)為公鑰，(7, 33)為私鑰
該例中的N為33，即二進制的10 0001，即例子中密鑰的長度為5
例子里的數取得很小以便于理解。
給定要加密的明文“7”，演示加密和解密的過程：
進行“公鑰加密、私鑰解密”
加密過程：密文 = （明文^E）mod N = (7 ^ 3) % 33 = 343 % 33 = 13，得到加密后的密文為“13”
解密過程：明文 = （密文^D）mod N = (13 ^ 7) % 33 = 62748517 % 33 = 7，解回明文“7”
反過來，進行“私鑰加密，公鑰解密”
加密過程：密文 = （明文^D）mod N = (7 ^ 7) % 33 = 823543 % 33 = 28，得到加密后的密文為“28”
解密過程：明文 = （密文^E）mod N = (28 ^ 3) % 33 = 21952 % 33 = 7，解回明文“7”
例子中的明文為數字，加密算法可以用于各種數據信息（數字、字母、符號、圖片、音頻、視頻），現實中的所有數據在計算機中都是使用二進制的“0”、“1”組合的形式表示的，再通過解碼可以轉換成能夠理解的數據信息格式。
2 密鑰格式
??RSA算法的密鑰具有多種不同的描述格式，例如PEM格式、ASN格式、XML格式、DER格式等，使用不同的密鑰格式通過對應的規則都可以用來表示密鑰對象，解析出各個字段的內容。
2.1 PEM格式
PEM格式又具有多種填充方式從“PKCS#1”一直到“PKCS#15”，常用的是“PKCS#1”和“PKCS#8”，它們的文件頭也可能存在區別。
公鑰
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBALDTR8eu33xA4ru/JPbEsIapTTF1SzEi
IjAbntCXdEK6xdwsuomv7kL7rVQXef2rzhvzBSyZxuRbf33u6fi4jW8CAwEAAQ==
-----END PUBLIC KEY-----
私鑰
-----BEGIN PRIVATE KEY-----
MIIBVQIBADANBgkqhkiG9w0BAQEFAASCAT8wggE7AgEAAkEAsNNHx67ffEDiu78k
9sSwhqlNMXVLMSIiMBue0Jd0QrrF3Cy6ia/uQvutVBd5/avOG/MFLJnG5Ft/fe7p
+LiNbwIDAQABAkEAmKtS5k1OF/HN0VwPhh/8acfzJiinaxyVeAPg8yhQ8OryQxG2
CnqTgG4V2PAMvxX42W+ZqA0zTFXx4EtWmq8FQQIhANjpAY7W6TAidjy2qlmfuSl4
DoY75bKJRsg2GVVYDDyTAiEA0LD88irK80hKj2JeAgEP0NXyYV8QZSuEM5Qk0G3U
0TUCIFpNhwyEhEg50KeuFHWDfX66MLHJtfMCG6m2fA1/vnhpAiEAowF7sdRHDdvr
kS+uajZWGjLizbepYLyq2HbggoUnc/kCICj08MHdsE2excF0rtNi457J57ZhnTsj
9uDBvPY+9JTT
-----END PRIVATE KEY-----
2.2 ASN格式
ASN格式是一串純Base64字符串，可以看成去掉了PEM格式的頭尾描述后的形式。
公鑰
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBALDTR8eu33xA4ru/JPbEsIapTTF1SzEi
IjAbntCXdEK6xdwsuomv7kL7rVQXef2rzhvzBSyZxuRbf33u6fi4jW8CAwEAAQ==
私鑰
MIIBVQIBADANBgkqhkiG9w0BAQEFAASCAT8wggE7AgEAAkEAsNNHx67ffEDiu78k
9sSwhqlNMXVLMSIiMBue0Jd0QrrF3Cy6ia/uQvutVBd5/avOG/MFLJnG5Ft/fe7p
+LiNbwIDAQABAkEAmKtS5k1OF/HN0VwPhh/8acfzJiinaxyVeAPg8yhQ8OryQxG2
CnqTgG4V2PAMvxX42W+ZqA0zTFXx4EtWmq8FQQIhANjpAY7W6TAidjy2qlmfuSl4
DoY75bKJRsg2GVVYDDyTAiEA0LD88irK80hKj2JeAgEP0NXyYV8QZSuEM5Qk0G3U
0TUCIFpNhwyEhEg50KeuFHWDfX66MLHJtfMCG6m2fA1/vnhpAiEAowF7sdRHDdvr
kS+uajZWGjLizbepYLyq2HbggoUnc/kCICj08MHdsE2excF0rtNi457J57ZhnTsj
9uDBvPY+9JTT
2.3 XML格式
XML格式密鑰是C#語言下的默認格式，使用XML描述語言將密鑰對象的各個字段表示出來。
公鑰
<RSAKeyValue>
<Modulus>
riLSQFVDC229P5F+Mkicbkpg5OC8+SeL6hvkJXIGYiN/e4YnprCxuIp5sH9AwWup4WJmObPKd1jOVGm07UwgVU7CDtTaVe1Uuk78yJBwgRuSteQjHYMmH6nG5YHvvONuvkmLnyIKGygJBL+4+Qmd3GaCHRtIrdfShlH3UbPINlM=
</Modulus>
<Exponent>
AQAB
</Exponent>
</RSAKeyValue>
私鑰
<RSAKeyValue>
<Modulus>
riLSQFVDC229P5F+Mkicbkpg5OC8+SeL6hvkJXIGYiN/e4YnprCxuIp5sH9AwWup4WJmObPKd1jOVGm07UwgVU7CDtTaVe1Uuk78yJBwgRuSteQjHYMmH6nG5YHvvONuvkmLnyIKGygJBL+4+Qmd3GaCHRtIrdfShlH3UbPINlM=
</Modulus>
<Exponent>
AQAB
</Exponent>
<P>
6yCboYtKzIezMOFzGzzW8dp7SBT8f7jTRzH1ZIKQYKF0Mq/39k80SeUvY578O031+bg6i3cbNvvAhL8XjqTtmQ==
</P>
<Q>
vZgnL5LHnNE5uUW5NBwYvZbIz6hWNzc6kyDGimI8WBBFJOI06IdYGL2VMeGVs4lt5a1tM7T3c6gzBKgDQpL+yw==
</Q>
<DP>
p5tV9YDyr/unq5d6Uxc6bar9qHN1TqJ00VJ2h9BelNNinmM70fPB5U8fSddiG/BGAF3oNdSQrNAm+zmw1DkTOQ==
</DP>
<DQ>
fxS1b1XbJmm3X1A0y5DppGqlP0t+PpRuVp/pdGhUOlLthcN540KU8kBg+IZUaXr8hq6wO7BZDNT5HW3ggYc18Q==
</DQ>
<InverseQ>
q29etXnlszOH0FlQWDL9yLfJ+EruH4VURY1mZGz/+/qvPewUwyEf+EqJkZHVXEijnSa1CiFELK2YE9PhkUp2Xw==
</InverseQ>
<D>
bZUoLqf5KwYCJDDQ85/SIW3ZD++FvF1wpQCsUAwzjCq+nONNrI5hKLqr3bAW9iFkpJshrYpBDV3rah+jZfmUFk/UZeur2+kA2r5r1or34+HiIhT4sehU1lxww4DvTzf1/1ivG4LCvUPoFtT67Zdh8pNEC27N6bFDL8fbSU7GcmE=
</D>
</RSAKeyValue>
2.4 DER格式
DER格式是一種十六進制的密鑰格式
公鑰
30818902818100C19CFA5EA25F99C482499E3A557C7D0C3ABB375B19900CF4956E39F5B1EACA46A37CEE30DDBEA72979B6DABA11D4B9BD51CB1D79ED667607E65CF53491EE6BE35155072D5EFB96BA0E0FC0B9C1DFEDFA30886F645218CC680E55A7D5568AD59283E9BB3DC82970F6B3F6DD83FB308E2C610F362C71977D428614ED5FB59EFDB10203010001
私鑰
3082025D020100028181009951BFB322876658587C207F2AFC2F2638DFD4EEEE925669C4A9487A3774891AEBE638940318B1AE270784FCFBE768C8C989E33B3953D820326DFAC7862AA133F96EE216C1B3F5651D45194CA02E9926E8FF133B2C03BB22BFE8C60B13D4757F263D4A792B188A8183FAB53B193C8AF8AB8EAB7020547C20D5BC90E1B369DBA902030100010281800FD9829ECB28022D89E0331FD25AC5A906E224CA1A81A84B40D85B34BF3CDDDB999D7025E4F80D8E3A5CADA3D58AC3AB56225A0A4A4FDF9CDC79C01E16419BEE71997546C68E6408E5D9C044858DCB6393F285D3EBAAD0C75298F61B33B752EB8E1ABA4D66E5380FF52DE07929A96367673CDAE5945A0C13F3503FABEDB1758D024100C52F9745C13B77968D52F29ACDEE00F2DF07AF8025048348B054B7EFF460097CAB824212447F674B55CF74E489DD399E702D3D655C74484248E05CA2E9DCCEE7024100C70CA9EA361ED73C42627254F33A3FA81AD0AADD64D45A1E536E64C7E31737B7ED3FCC20E03A082673C6E7A7270640F6132AA295FF406D6133090E7D89397EEF024100883505936395065872AAB77683854216824536CF97C2744543B8618E5909F5C3AE5D3DF28C6A4D19D6DE84EA50E905A211EECE18343306AEF2D43869388E1445024100B061FE6776D1D974A276CE4D8CC2FF099DC96EBF84CBCF97B3E2CD177B9A655B6CB6EDD1EC20407CA2778D6B475F794D152AE0ABFE663F06B4CCBFB46A5732AD02404981E8728E85719A319C9A8C4C7D3B162BFA728AD5FD054C0A45A9A625385167F0822D2398680FD75BF29A3C20A4D72D2115ABD06F27B3819214AAC77284518A
3 密鑰解析（ASN.1）
??不管RSA算法的密鑰格式形式如何，其最終目的是表示密鑰的內容，RSA算法的密鑰最終需要被解析成一個類似結構體的對象，其解析規則遵循ASN.1標準。
??ASN.1抽象語法標記（Abstract Syntax Notation One），描述了一種對數據進行表示、編碼、傳輸和解碼的數據格式。提供了一整套正規的格式用于描述對象的結構。數字1被加在ASN的后邊，是為了保持ASN的開放性，可以讓以后功能更加強大的ASN被命名為ASN.2等，但至今也沒有出現。
??ASN.1中關聯了多個標準化編碼規則，基本編碼規則（BER）、規范編碼規則（CER）、識別名編碼規則（DER）、壓縮編碼規則（PER）和 XML編碼規則（XER）。其中BER、CER、DER、PER都是二進制編碼規則，BER（BasicEncoding Rules）是ASN.1中最早定義的編碼規則，其他編碼規則是在BER的基礎上添加新的規則而構成的。
3.1 BER編碼規則
??傳輸語法的格式為TLV三元組<Tag, Length, Value>，其中Value字段又能繼續包含新的TLV三元組，即可以產生嵌套<T, L, <T, L, V>>。
??密鑰的各種格式最終都會被轉換成二進制，基于八位組的大字節序（Big-Endian）編碼方式，高八位在左，低八位在右來解析。例如DER格式的十六進制密鑰“30819f300d0609…………”的轉換如下：
| 十六進制密鑰 | 二進制高八位 | 二進制低八位 |
|---|---|---|
| 30 | 0011 | 0000 |
| 81 | 1000 | 0001 |
| 9F | 1001 | 1111 |
| 30 | 0011 | 0000 |
| 0D | 0000 | 1101 |
| 06 | 0000 | 0110 |
| 09 | 0000 | 1001 |
跨語言加密解密的時候需要考慮各個語言的字節序編碼方式（Big-Endian與Little-Endian），C/C++語言的字節序跟編譯平臺的CPU相關，主流的Intel-x86架構采用小字節序，Java語言采用大字節序，用于網絡傳輸的網絡字節序是大字節序，多端互操作的情況下，需要考慮大小字節序的轉換問題，額外處理。
3.1.1 Tag字段
包含一個或若干個八位組（即字節），以十六進制“30”為例，二進制表示為“0011 0000”，各個位的含義如下：
| 第7位 | 第6位 | 第5位 | 第4位 | 第3位 | 第2位 | 第1位 | 第0位 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 標簽類型 | 標簽類型 | 編碼方式 | 值類型 | 值類型 | 值類型 | 值類型 | 值類型 |
第7、6位指明標簽分類：
| 值 | 標簽分類 |
|---|---|
| 00 | universal 通用標簽 |
| 01 | application 應用標簽 |
| 10 | context-specific 上下文專用標簽 |
| 11 | private 私有標簽 |
3.1.1.1 通用標簽
當Tag分類為”universal 通用標簽“時，第5位指明標簽編碼方式：
| 值 | 編碼方式 |
|---|---|
| 0 | primitive 原始類型 |
| 1 | constructed 構造類型 |
當Tag分類為”universal 通用標簽“時，第4~0位：指明標簽值的類型：
| 值（二進制） | 值（十進制） | 值類型 |
|---|---|---|
| 00000 | 0 | 保留 |
| 00001 | 1 | Boolean 布爾類型 |
| 00010 | 2 | Integer 整型 |
| 00011 | 3 | Bit String 位串 |
| 00100 | 4 | Octet String 字節串（八位位組串） |
| 00101 | 5 | NULL 空值 |
| 00110 | 6 | Object Identifier 對象標識符 |
| 00111 | 7 | Object Description |
| 01000 | 8 | External，Instance of |
| 01001 | 9 | Real 實數 |
| 01010 | 10 | Enumerated 枚舉類型 |
| 01011 | 11 | Embedded PDV |
| 01100 | 12 | UTF8 String |
| 01101 | 13 | Relative-oid |
| 01110 | 14 | 保留 |
| 01111 | 15 | 保留 |
| 10000 | 16 | Sequence 序列，Sequence of 單類型序列 |
| 10001 | 17 | Set集合，Set of 單類型集合 |
| 10010 | 18 | Numeric String |
| 10011 | 19 | Printable String |
| 10100 | 20 | Teletex String，T61 String |
| 10101 | 21 | Videotex String |
| 10110 | 22 | IA5 String |
| 10111 | 23 | UTC Time |
| 11000 | 24 | Generalized Time |
| 11001 | 25 | Graphic String |
| 11010 | 26 | Visible String，ISO646 String |
| 11011 | 27 | General String |
| 11100 | 28 | Universal String |
| 11101 | 29 | Character String |
| 11110 | 30 | BMP String |
| 11111 | 31 | 保留 |
3.1.1.2 非通用標簽
當Tag分類不為”universal 通用標簽“，而是另外三種時，在后續的多個八位組中編碼，第一個八位組后五位固定全部為1，其余的八位組最高位為1表示后續還有，為0表示Tag結束。
| 第一個八位組 | 第二個八位組 | 第二個八位組 | …… | 第n個八位組 |
|---|---|---|---|---|
| 01 11 1111 | 1xxx xxxx | 1xxx xxxx | 1… … | 0xxx xxxx |
| 高位01表示“application 應用標簽” 后五位固定全為1 |
高位為1，表示還在編碼 | 高位為1，表示還在編碼 | 高位為1，表示還在編碼 | 高位為0，表示結束 |
3.1.2 Length字段
Length字段的組織方式有兩大類：定長方式和不定長方式，第一個八位組不為0x80表示定長方式，為0x80表示不定長方式：
3.1.2.1 定長方式
定長方式中，按長度是否超過一個八位，又分為短形式、長形式，最高位為”0“表示短形式，最高位為”1“表示長形式：
短形式
各個位的含義如下：
| 最高位 | 后7位 |
|---|---|
| 0 | xxx xxxx |
| 0表示短形式 | 表示TLV三元組中的Value字段占用的字節數（范圍0~127） |
長形式
各個位的含義如下：
| 第一個八位組 | …… |
|---|---|
| 1xxx xxxx | …… |
| 最高位”1“表示長形式 后7位表示需要繼續編碼的長度（字節數） |
按照第一個八位提供的長度值，繼續編碼，其數值表示TLV三元組中的Value字段占用的字節數（范圍0~256^126-1） |
3.1.2.2 不定長方式
Length所在八位組固定編碼為0x80，但在Value編碼結束后以兩個0x00結尾。
| 第一個八位組 | …… | 第n-1個八位組 | 第n個八位組 |
|---|---|---|---|
| 1000 0000 | …… | 0000 0000 | 0000 0000 |
| 0x80表示不定長方式 | 不為0x00，表示還在編碼，其數值表示TLV三元組中的Value字段占用的字節數 | 遇到第一個0x00 | 遇到兩個連續的0x00表示結束 |
3.1.3 Value字段
該字段內可能包含基礎數據，也可能包含嵌套的TLV三元組，需要具體解析。
3.2 公鑰解析示例
按照上述規則，解析一個密鑰實例，以公鑰為例（DER格式）解析方式如下：
30819f300d06092a864886f70d010101050003818d0030818902818100890f1a96bb296740990674217c96afe8bbbc63ba69123a55c87f03afe36f106522c2935a650a6bfd929a575941396d888424e4ee702e33f5ea2275d4d9e8c80c6c503a07c1f471f501e89abd4c6fd169b4c32460e1fd35ff2bbdb3febaa4c28a5b549b20017caea2652761b2a7edb22cb765921e18f1fe9315a8ade66625d11d0203010001
按照ASN.1規范的BER編碼規則對每個字節進行解析如下：
| 字節序號 | 密鑰原文 | 對應的二進制 | TLV組 （“····”縮進） |
語義 |
|---|---|---|---|---|
| 0 | 30 | 0011 0000 | T | Tag值 Universal類型 結構體——類型SEQUENCE |
| 1 | 81 | 1000 0001 | L | Length值 定長 長類型——長度1個字節 |
| 2 | 9F | 1001 1111 | ——實際長度159個字節（0x9F轉十進制） | |
| V{ | Value值{ | |||
| 3 | 30 | 0011 0000 | ····T | Tag值 Universal類型 結構體 類型SEQUENCE |
| 4 | 0D | 0000 1101 | ····L | Length值 定長 短類型——實際長度13個字節 |
| ····V{ | Value值{ | |||
| 5 | 06 | 0000 0110 | ········T | Tag值 Universal類型 原數據——類型OBJECT IDENTIFIER |
| 6 | 09 | 0000 1001 | ········L | Length值 定長 短類型——實際長度9個字節 |
| ········V{ | Value值{ | |||
| 7~11 | 2A 86 48 86 F7 | ············ | ||
| 12~15 | 0D 01 01 01 | ············ | ||
| ········} | } | |||
| 16 | 05 | 0000 0101 | ········T | Tag值 Universal類型 原數據——類型NULL |
| 17 | 00 | 0000 0000 | ········T | Tag值 Universal類型 原數據——類型BER保留 |
| ····} | } | |||
| 18 | 03 | 0000 0011 | ····T | Tag值 Universal類型 原數據——類型BIT STRING |
| 19 | 81 | 1000 0001 | ····L | Length值 定長 長類型——長度1個字節 |
| 20 | 8D | 1000 1101 | ····· | ——實際長度141個字節 |
| ····V{ | Value值{ | |||
| 21 | 00 | ········ | unused bit | |
| 22 | 30 | ········T | Tag值 Universal類型 結構體 類型SEQUENCE | |
| 23 | 81 | 1000 0001 | ········L | Length值 定長 長類型——長度1個字節 |
| 24 | 89 | 1000 1001 | ········ | ——實際長度137個字節 |
| ········V{ | Value值{ | |||
| 25 | 02 | 0000 0010 | ············T | Tag值 Universal類型 原數據——類型INTEGER |
| 26 | 81 | 1000 0001 | ············L | Length值 定長 長類型——長度1個字節 |
| 27 | 81 | 1000 0001 | ············ | ——實際長度129個字節 |
| ············V{ | Value值{ | |||
| 28 | 00 | ················ | 首字節的MSB=1時，補0 | |
| 29~156 | 89 0F 1A 96 BB | ················ | ||
| 29 67 40 99 06 | ················ | |||
| 74 21 7C 96 AF | ················ | |||
| E8 BB BC 63 BA | ················ | |||
| 69 12 3A 55 C8 | ················ | |||
| 7F 03 AF E3 6F | ················ | |||
| 10 65 22 C2 93 | ················ | |||
| 5A 65 0A 6B FD | ················ | |||
| 92 9A 57 59 41 | ················ | |||
| 39 6D 88 84 24 | ················ | 128字節的公鑰值modulus | ||
| E4 EE 70 2E 33 | ················ | |||
| F5 EA 22 75 D4 | ················ | |||
| D9 E8 C8 0C 6C | ················ | |||
| 50 3A 07 C1 F4 | ················ | |||
| 71 F5 01 E8 9A | ················ | |||
| BD 4C 6F D1 69 | ················ | |||
| B4 C3 24 60 E1 | ················ | |||
| FD 35 FF 2B BD | ················ | |||
| B3 FE BA A4 C2 | ················ | |||
| 8A 5B 54 9B 20 | ················ | |||
| 01 7C AE A2 65 | ················ | |||
| 27 61 B2 A7 ED | ················ | |||
| B2 2C B7 65 92 | ················ | |||
| 1E 18 F1 FE 93 | ················ | |||
| 15 A8 AD E6 66 | ················ | |||
| 25 D1 1D | ················ | |||
| ············} | } | |||
| 157 | 02 | 0000 0010 | ············T | Tag值 Universal類型 原數據——類型INTEGER |
| 158 | 03 | 0000 0011 | ············L | Length值 定長 短類型——實際長度3個字節 |
| ············V{ | Value值{ | |||
| 159 | 01 | ················ | ||
| 160 | 00 | ················ | 3字節的公有冪值exponent | |
| 161 | 01 | ················ | ||
| ············} | } | |||
| ········} | } | |||
| ····} | } | |||
| } | } |
解析完的公鑰對象的結構形式如下：
SEQUENCE{ // 159個字節
SEQUENCE{ // 13個字節
OBJECT IDENTIFIER{ // 9個字節
}
}
BIT STRING{ // 141個字節
SEQUENCE{ // 137個字節
INTEGER{ // 129個字節
補0 // 1個字節
modulus // 128個字節，模數，即N
}
INTEGER{
exponent // 3個字節，公有冪值，即E
}
}
}
}
至此我們已經從DER密鑰格式的十六進制串中解析出了模數modulus和公有冪exponent，即公鑰內容。
解出了公鑰的內容，要向其它幾種密鑰格式轉換，只需要按照對應的格式規則進行處理即可，很多語言都有現呈的類可以進行構造（C#中提供RSACryptoServiceProvider類）。例子中是公鑰的解析，在RSA算法中，私鑰對象的結構要比公鑰多幾個字段，但解析方式是一樣的，同樣遵循ASN.1規范。
4 源代碼
最后貼上客戶端的C#源碼，從DER格式的公鑰中解出模數和公有冪：
/**
* 從DER格式的公鑰字符串解析出modulus和exponent
*/
internal static KeyValuePair<byte[], byte[]> DecodeHexPublicKey(string hexPublicKey)
{
try
{
byte[] keyBytes = HexStringToByte(hexPublicKey); // 字符串轉成十六進制字節數組
if (keyBytes[0] != 0x30) // 第一個字節的文件頭必須解析成SEQUENCE結構
{
throw new Exception("head of file cannot decode to SEQUENCE");
}
// 解析主結構體（SEQUENCE結構體）
int mainSequenceLength = 0;
int currentIndex = 1; // 從第二個字節開始解析
mainSequenceLength = DecodeTLV_Length(keyBytes, ref currentIndex); // 獲取主SEQUENCE結構體的長度
// 解析inner（SEQUENCE結構體）
int innerSequenceLength = 15; // inner的固定長度15
currentIndex += innerSequenceLength; // 跳過即可
// 解析bitString（Bit String類型）
currentIndex++; // 下標跳過Bit String數據的Tag字段，移向Length字段
int bitStringLength = DecodeTLV_Length(keyBytes, ref currentIndex); // 獲取Bit String數據的長度
currentIndex++; // Bit String的Value字段帶一個unused bit，跳過
// 解析參數結構體（SEQUENCE結構體）
currentIndex++; // 下標跳過參數結構體的Tag字段，移向Length字段
int paramSequenceLength = DecodeTLV_Length(keyBytes, ref currentIndex); // 獲取參數SEQUENCE結構體的長度
// 解析modulus模數N
byte[] modulus = DecodeInteger(keyBytes, ref currentIndex);
// 解析exponent公開冪E
byte[] exponent = DecodeInteger(keyBytes, ref currentIndex);
// 公鑰（E，N）
KeyValuePair<byte[], byte[]> result = new KeyValuePair<byte[], byte[]>(modulus, exponent);
return result;
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
return new KeyValuePair<byte[], byte[]>();
}
}
/**
* 字符串以十六進制的規則轉為字節數組
*/
private static byte[] HexStringToByte(string hexString)
{
hexString = hexString.Replace(" ", "");
if ((hexString.Length % 2) != 0)
{
hexString += " ";
}
byte[] returnBytes = new byte[hexString.Length / 2];
for (int i = 0; i < returnBytes.Length; i++)
{
returnBytes[i] = Convert.ToByte(hexString.Substring(i * 2, 2), 16);
}
return returnBytes;
}
/**
* 解碼ASN.1規則中的INTEGER類型，返回解碼后的數據，處理完成后currentIndex的位置會移到該類型數據末尾的下一個位置
* @param data 密鑰字節數組(十六進制)
* @param currentIndex 表示當前需要解碼的Integer的Tag字段的位置
*/
private static byte[] DecodeInteger(byte[] dataInteger, ref int currentIndex)
{
if (dataInteger[currentIndex] != 0x02)
{
throw new Exception("head of file cannot decode to INTEGER");
}
currentIndex += 1;
var len = DecodeTLV_Length(dataInteger, ref currentIndex);
int integerStart = currentIndex;
int integerEnd = currentIndex + len - 1;
// 跳過補零位，>0x7f時補0
while (dataInteger[currentIndex] == 0)
{
currentIndex++;
}
if (dataInteger[currentIndex] > 0x7f)
{
integerStart = currentIndex;
}
byte[] result = dataInteger.Where((item, index) => index >= integerStart & index <= integerEnd).ToArray();
currentIndex = integerEnd + 1; // 處理完成后currentIndex移到末尾的下一個位置
return result;
}
/**
* 解碼TLV元組中的Length字節，返回實際長度，返回0表示錯誤，處理完成后currentIndex的位置會移到Length字段末尾的下一個位置
* @param data 密鑰字節數組(十六進制)
* @param index 表示當前需要解碼的TLV元組中的Length字段的位置
*/
private static int DecodeTLV_Length(byte[] data, ref int currentIndex)
{
try
{
int length = data[currentIndex]; // 獲取當前字節，十進制表示
if (length == 0) // 解碼不能為：0000 0000，拋出異常
{
throw new Exception("parameter length in TLV cannot be 0x00");
}
else if(length < 0x80) // 解碼為：0xxx xxxx，定長式、短形式：最高位為0，后7位表示長度的實際值
{
++currentIndex; // 處理完成后currentIndex移到末尾的下一個位置
return length;
}
else if(length == 0x80) // 解碼為：1000 0000，不定長式：以兩個連續的0x00結尾
{
int result = 0;
int count = 0; // 連續遇到0x00的次數
while (count != 2)
{
++currentIndex; // 獲取下一個字節
int temp = data[currentIndex];
if (temp == 0x00) // 遇到0x00
{
++count;
}
else
{
count = 0;
}
++result;
}
++currentIndex; // 處理完成后currentIndex移到末尾的下一個位置
return result;
}
else // 解碼為：1xxx xxxx，定長式、長形式：最高位為1，后7位表示長度的實際值會占用接下的多少個字節數
{
length &= 0x7F; // 當前值和“0111 1111”進行按位與，提取出length后7位的1，后7位的十進制表示長度的實際值占用的字節數
int result = 0;
for (int i = length - 1; i >= 0; i--)
{
++currentIndex; // 獲取下一個字節
int temp = data[currentIndex] << (i * 8); // 計算當前字節所在的位置表示的值，每多一個字節需要左移八位
result += temp;
}
++currentIndex; // 處理完成后currentIndex移到末尾的下一個位置
return result;
}
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
++currentIndex; // 處理完成后currentIndex移到末尾的下一個位置
return 0;
}
}
特別注意：如果場景涉及大字節序和小字節序（Big-Endian與Little-Endian）的轉換，需要額外處理。
總結
??RSA算法本身的原理并不復雜，其中的密鑰解析依賴于密鑰的格式規范，各種密鑰格式的互轉都可以先轉換成原始的密鑰內容結構體對象，再按照不同的密鑰格式規范進行組裝，期間可能會涉及到base64字符串的轉換、不同進制的轉換、大小字節序的轉換等問題，本文提供了對十六進制DER格式公鑰解析的具體解決方案。
浙公網安備 33010602011771號