"rarreg.key"是如何生成的？

WinRAR使用了基于ECC的签名算法来生成 rarreg.key 文件，其使用的签名算法是中国SM2数字签名算法的变体。与各种标准ECDSA不同的是，WinRAR使用的椭圆曲线是一个基于复合域 $GF2p15p17-inlined$ 上的曲线。

1. 复合域 $GF2p15p17-inlined$

基域 $GF2p15-inlined$ 采用标准基（多项式基）来表达，采用的不可约多项式为：

$P(\alpha)=\alpha^{15}+\alpha+1$

各项系数全部位于 $GF2-inlined$ 。设基域的标准基为：

$B_1=\{1,\alpha,\alpha^2,\ldots,\alpha^{14}\}$

则位于基域 $GF2p15-inlined$ 上的元素 $A-inlined$ 可以用如下方式表达：

$A=\sum_{i=0}^{14}a_i\alpha^i \quad \quad \quad a_i\in\textrm{GF}(2)$

复合域 $GF2p15p17-inlined$ 的不可约多项式为：

$Q(\beta)=\beta^{17}+\beta^3+1$

各项系数全部位于 $GF2p15-inlined$ 。设复合域的标准基为：

$B_2=\{1,\beta,\beta^2,\ldots,\beta^{16}\}$

则位于复合域 $GF2p15p17-inlined$ 上的元素 $B-inlined$ 可以用如下方式表达：

$B=\sum_{j=0}^{16}(\sum_{i=0}^{14}a_{j,i}\alpha^i)\beta^j=\sum_{j=0}^{16}\sum_{i=0}^{14}a_{j,i}\alpha^i\beta^j \quad \quad \quad a_{j,i}\in\textrm{GF}(2)$

为了方便表述我们用255比特的大数 $D-inlined$ 来表示位于复合域 $GF2p15p17-inlined$ 上的元素 $B-inlined$ 。它们的对应关系为：

$B=\sum_{j=0}^{16}\sum_{i=0}^{14}a_{j,i}\alpha^i\beta^j \leftrightarrow D=\sum_{j=0}^{16}\sum_{i=0}^{14}a_{j,i}\cdot 2^{15j+i}$

2. 复合域 $GF2p15p17-inlined$ 上的椭圆曲线

曲线方程为：

$y^2+xy=x^3+161 \quad \quad \quad 161\in\textrm{GF}((2^{15})^{17})$

基点 $G-inlined$ 为：

$\begin{aligned} G&=(G_x,G_y) \\ G_x&=\textrm{0x56fdcbc6a27acee0cc2996e0096ae74feb1acf220a2341b898b549440297b8cc} \quad G_x\in\textrm{GF}((2^{15})^{17})\\ G_y&=\textrm{0x20da32e8afc90b7cf0e76bde44496b4d0794054e6ea60f388682463132f931a7} \quad G_y\in\textrm{GF}((2^{15})^{17}) \end{aligned}$

基点 $G-inlined$ 的阶 $n-inlined$ 为：

$n=\textrm{0x1026dd85081b82314691ced9bbec30547840e4bf72d8b5e0d258442bbcd31} \quad n\in\nolinebreak\mathbb{Z}$

3. 消息哈希算法

设长度为 $l-inlined$ 的消息为：

$M=m_0m_1 \ldots m_{l-1} \quad \quad m_i\in[0, 256)$

则消息 $M-inlined$ 的SHA1值为：

$\textrm{SHA}_1(M)=S_0||S_1||S_2||S_3||S_4 \quad \quad S_i\in[0, 2^{32})$

其中 $S_0,S_1,S_2,S_3,S_4$ 为SHA1算法输出时的5个状态值；将这5个状态值按照大端字节序依次输出，即为的SHA1哈希值 $\textrm{SHA}_1(M)$ 。

WinRAR在做完SHA1计算后，采用大数 $h-inlined$ 作为ECC签名时消息的哈希：

$h=(\sum_{i=0}^{4}S_i \cdot 2^{32i})+\textrm{0x1bd10xb4e33c7c0ffd8d43} \cdot 2^{32*5}$

4. ECC签名算法

设私钥为 $k-inlined$ ，公钥为 $P-inlined$ ，即：

$P=k \cdot G$

消息哈希为 $h-inlined$ ，则签名 $(r,s)$ 为：

生成随机数 $Rnd-inlined$ ，满足 $0<Rnd<n$ 。
计算 $r-inlined$

   <img src="http://latex.codecogs.com/svg.latex?r%3D%28%28Rnd%20%5Ccdot%20G%29_x&plus;h%29%5C%20%5C%20Mod%5C%20%5C%20n">

其中 $(Rnd \cdot G)_x$ 表示取 $Rnd \cdot G$ 的X坐标，同时将X坐标从 $GF2p15p17-inlined$ 转换为大数。

若 $r=0$ 或者 $r+Rnd=n$ 则回到步骤1。

计算 $s-inlined$

   <img src="http://latex.codecogs.com/svg.latex?s%3D%28Rnd-kr%29%5C%20%5C%20Mod%5C%20%5C%20n">

若 $s=0$ 则回到步骤1。

输出 $(r,s)$ 。

5. WinRAR的私钥生成算法

该算法会利用长度为 $l-inlined$ 的数据

$T=t_0t_1 \ldots t_{l-1} \quad \quad t_i\in[0,256)$

来生成私钥 $k-inlined$ 。

设6个32位整数为 $g_0,g_1,g_2,g_3,g_4,g_5$ ，则有

   <img src="http://latex.codecogs.com/svg.latex?g_j%3D%5Csum_%7Bi%3D0%7D%5E%7B3%7Dg_%7Bj%2Ci%7D%20%5Ccdot%202%5E%7B8i%7D%20%5Cquad%20%5Cquad%20g_%7Bj%2Ci%7D%5Cin%5B0%2C256%29">

令 $g_0=0$ 。
如果 $l\neq 0$ 则计算 $T-inlined$ 的SHA1值，并将状态值 $S_i$ 赋值给 $g_{i+1}$ ：

   <img src="http://latex.codecogs.com/svg.latex?%5Cbegin%7Baligned%7D%20%5Ctextrm%7BSHA%7D_1%28T%29%26%3DS_0%7C%7CS_1%7C%7CS_2%7C%7CS_3%7C%7CS_4%20%5C%5C%20g_1%26%3DS_0%20%5C%5C%20g_2%26%3DS_1%20%5C%5C%20g_3%26%3DS_2%20%5C%5C%20g_4%26%3DS_3%20%5C%5C%20g_5%26%3DS_4%20%5C%5C%20%5Cend%7Baligned%7D">

否则，即 $l=0$ 时，令：

   <img src="http://latex.codecogs.com/svg.latex?%5Cbegin%7Baligned%7D%20g_1%26%3D%5Ctextrm%7B0xeb3eb781%7D%20%5C%5C%20g_2%26%3D%5Ctextrm%7B0x50265329%7D%20%5C%5C%20g_3%26%3D%5Ctextrm%7B0xdc5ef4a3%7D%20%5C%5C%20g_4%26%3D%5Ctextrm%7B0x6847b9d5%7D%20%5C%5C%20g_5%26%3D%5Ctextrm%7B0xcde43b4c%7D%20%5C%5C%20%5Cend%7Baligned%7D">

把 $g_0$ 作为计数器，自增1。

计算SHA1值：

   <img src="http://latex.codecogs.com/svg.latex?%5Ctextrm%7BSHA%7D_1%28g_%7B0%2C0%7D%7C%7Cg_%7B0%2C1%7D%7C%7Cg_%7B0%2C2%7D%7C%7Cg_%7B0%2C3%7D%7C%7Cg_%7B1%2C0%7D%7C%7Cg_%7B1%2C1%7D%7C%7C%5Cldots%7C%7Cg_%7B5%2C0%7D%7C%7Cg_%7B5%2C1%7D%7C%7Cg_%7B5%2C2%7D%7C%7Cg_%7B5%2C3%7D%29%3DS_0%7C%7CS_1%7C%7CS_2%7C%7CS_3%7C%7CS_4">

取 $S_0$ 的低16位并记为 $k_{g_0}$ 。

步骤4再重复14次。
重复执行完后会得到 $k_1,k_2,k_3,\ldots,k_{15}$ ，则输出私钥

   <img src="http://latex.codecogs.com/svg.latex?k%3D%5Csum_%7Bi%3D1%7D%5E%7B15%7Dk_i%20%5Ccdot%202%5E%7B16i%7D">

6. WinRAR的公钥和私钥

WinRAR的私钥 $k-inlined$ 为：

$k=\textrm{0x59fe6abcca90bdb95f0105271fa85fb9f11f467450c1ae9044b7fd61d65e} \quad \quad k\in\nolinebreak\mathbb{Z}$

该私钥是通过算法5生成的，其中数据 $T-inlined$ 的长度为0。

公钥 $P-inlined$ 为：

$\begin{aligned} P&=(P_x,P_y) \\ P_x&=\textrm{0x3861220ed9b36c9753df09a159dfb148135d495db3af8373425ee9a28884ba1a} \quad P_x\in\textrm{GF}((2^{15})^{17}) \\ P_y&=\textrm{0x12b64e62db43a56114554b0cbd573379338cea9124c8443c4f50e6c8b013ec20} \quad P_y\in\textrm{GF}((2^{15})^{17}) \end{aligned}$

7. 授权文件"rarreg.key"的生成

授权文件的生成需要两个参数：

用户名的ANSI字符串，不包括null-terminator；记为

   <img src="http://latex.codecogs.com/svg.latex?U%3Du_0u_1%20%5Cldots%20u_%7Bl-1%7D">

授权类型的ANSI字符串，不包括null-terminator；记为

   <img src="http://latex.codecogs.com/svg.latex?L%3Dl_0l_1%20%5Cldots%20l_%7Bl-1%7D">

rarreg.key 的生成算法如下：

使用用户名 $UU-inlined$ 通过算法5计算出私钥 $k_U$ 以及公钥 $P_U$ ，并将公钥 $P_U$ 按照SM2压缩公钥格式以Hex字符串（ASCII编码）的形式输出。得到的Hex字符串记为临时值 $Temp-inlined$ 。

$Temp-inlined$ 的长度应该为64；若长度不足，则在前面补字符'0'，直到长度为64。

令字符串 $Data3-inlined$ 为

   <img src="http://latex.codecogs.com/svg.latex?Data%5E3%3D%5Ctexttt%7B%2260%22%7D%7C%7CTemp_0%7C%7CTemp_1%7C%7C%5Cldots%7C%7CTemp_%7B47%7D">

使用 $Data3-inlined$ 通过算法5计算出私钥 $k_{Data^3}$ 以及公钥 $P_{Data^3}$ ，并将公钥 $P_{Data^3}$ 按照SM2压缩公钥格式以Hex字符串（ASCII编码）的形式输出。得到的Hex字符串记为 $Data0-inlined$ 。

$Data0-inlined$ 的长度应该为64；若长度不足，则在前面补字符'0'，直到长度为64。

令字符串 $UID-inlined$ 为

   <img src="http://latex.codecogs.com/svg.latex?UID%3DTemp_%7B48%7D%7C%7CTemp_%7B49%7D%7C%7C%5Cldots%7C%7CTemp_%7B63%7D%7C%7CData%5E0_0%7C%7CData%5E0_1%7C%7CData%5E0_2%7C%7CData%5E0_3">

对授权类型 $LL-inlined$ 使用算法4得到签名 $(r_L,s_L)$ ，其中私钥见第6节。

要求 $r_L$ 和 $s_L$ 的长度都不得超过240比特，否则重复该步骤。

将 $r_L$ 和 $s_L$ 以16进制形式输出（无"0x"前缀），分别记为 $SZ^{r_L}$ 和 $SZ^{s_L}$ 。

若长度不满60，则在前面补字符'0'，直到长度为60。

令字符串 $Data1-inlined$ 为

   <img src="http://latex.codecogs.com/svg.latex?Data%5E1%3D%5Ctexttt%7B%2260%22%7D%7C%7CSZ%5E%7Bs_L%7D%7C%7CSZ%5E%7Br_L%7D">

令字符串 $Temp-inlined$ 为

   <img src="http://latex.codecogs.com/svg.latex?Temp%3DU%7C%7CData%5E0">

对 $Temp-inlined$ 使用算法4得到签名 $(r_{Temp},s_{Temp})$ ，其中私钥见第6节。

要求 $r_{Temp}$ 和 $s_{Temp}$ 的长度都不得超过240比特，否则重复该步骤。

将 $r_{Temp}$ 和 $s_{Temp}$ 以16进制形式输出（无"0x"前缀），分别记为 $SZ^{r_{Temp}}$ 和 $SZ^{s_{Temp}}$ 。

若长度不满60，则在前面补字符'0'，直到长度为60。

令字符串 $Data2-inlined$ 为

$Data^2=\texttt{"60"}||SZ^{s_{Temp}}||SZ^{r_{Temp}}$
对

$L||U||Data^0||Data^1||Data^2||Data^3$

计算CRC32值，最终校验和为CRC32值的反。将校验和以10进制形式输出，若长度不满10，则在前面补字符'0'，直到长度为10，记为 $SZ^{checksum}$ 。
令字符串 $Data-inlined$ 为

$Data=Data^0||Data^1||Data^2||Data^3||SZ^{checksum}$
格式化输出。
- 固定文件头"RAR registration data"，占一行。
- 用户名，占一行。
- 授权类型，占一行。
- UID，占一行：
```
<img src="http://latex.codecogs.com/svg.latex?%5Ctexttt%7B%22UID%3D%22%7D%7C%7CUID">
```
- 将 $Data-inlined$ 按照每行54个字符输出。

how-does-it-work.zh-CN.md 16 KB Permalink Riwayat Mentahan