How is "rarreg.key" generated?

中文版

WinRAR uses an ECC-based signature algorithm to generate rarreg.key. The algorithm it used is a varient of Chinese SM2 digital signature algorithm. Different to many standard ECDSAs, the curve that WinRAR selected is a curve over composite field $GF2p15p17-inlined$ .

1. Composite field $GF2p15p17-inlined$

Elements in ground field $GF2p15-inlined$ are represented with standard basis, i.e. polynomial basis. The irreducible polynomial is

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

where each coefficients is in $GF2-inlined$ . If we use

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

as the standard basis of the ground field, an element $A-inlined$ in $GF2p15-inlined$ can be denoted as

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

The irreducible polynomial of composite field $GF2p15p17-inlined$ is

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

where each coefficients is in $GF2p15-inlined$ . If we use

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

as the standard basis of the composite field, an element $B-inlined$ in $GF2p15p17-inlined$ can be denoted as

$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)$

For clarity, we use $D-inlined$ , which is a 255-bits-long integer to denote an element $B-inlined$ in $GF2p15p17-inlined$ . The map between them is

$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. Elliptic curve over $GF2p15p17-inlined$

The equation of the elliptic curve that WinRAR uses is

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

The base point $G-inlined$ is

$\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}$

whose order $n-inlined$ is

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

3. Message hash algorithm

We use

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

to denote a message whose length is $l-inlined$ . So the SHA1 value of $M-inlined$ should be

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

where $S_0,S_1,S_2,S_3,S_4$ are 5 state values when SHA1 outputs. Generally speaking, the final SHA1 value should be the join of these 5 state values while each of state values is serialized in big-endian.

However, WinRAR doesn't serialize the 5 state values. Instead, it use a big integer $h-inlined$ as the hash of the input message.

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

4. ECC digital signature algorithm

We use $k-inlined$ to denote private key, $P-inlined$ to denote public key. So there must be

$P=k \cdot G$

If we use $h-inlined$ to denote the hash of input data, WinRAR use the following algorithm to perform signing:

Generate a random big integer $Rnd-inlined$ which satisfies $0<Rnd<n$ .
Calculate $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">

where $(Rnd \cdot G)_x$ means we take X coordinate of $Rnd \cdot G$ and convert it from $GF2p15p17-inlined$ to a big integer.

If $r=0$ or $r+Rnd=n$ , go back to step 1.

Calculate $s-inlined$

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

If $s=0$ , go back to step 1.

Output $(r,s)$ .

5. WinRAR private key generation algorithm

We use

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

to denote input data whose length is $l-inlined$ . WinRAR use it to generate private key $k-inlined$ .

We use $g_0,g_1,g_2,g_3,g_4,g_5$ to denote 6 32-bits-long integer. So there is

   <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">

Let $g_0=0$ .
If $l\neq 0$ , we calculate SHA1 value of $T-inlined$ . Then assign SHA1 state value $S_i$ to $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">

Otherwise, when $l=0$ , we let

   <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">

Regard $g_0$ as counter, add itself by 1.

Calculate 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">

We takes the lowest 16 bits of $S_0$ and donote it as $k_{g_0}$ .

Repeat step 4 again with 14 times.
After that, we will get $k_1,k_2,k_3,\ldots,k_{15}$ . Then output private key

   <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. The private key and public key of WinRAR

Private key $k-inlined$ is

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

This private key is generated by the algorithm describled in section 5 where the length of data $T-inlined$ is zero.

Public key $P-inlined$ is

$\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. Generation of "rarreg.key"

The generation of license file rarreg.key requires 2 arguments:

Username, an ANSI-encoded string, without null-terminator. Denoted as

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

License type, an ANSI-encoded string, without null-terminator. Denoted as

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

The following is the algorithm to generate rarreg.key.

Use the algorithm describled in section 5, with argument $UU-inlined$ , to generate private key $k_U$ and public key $P_U$ . Then output hexlified public key string with SM2 compressed public key format. The hexlified public key is denoted as $Temp-inlined$ .

The length of $Temp-inlined$ should be 64. If less, pad with '0' until the length is 64.

Let $Data3-inlined$ be

   <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">

Use the algorithm describled in section 5, with argument $Data3-inlined$ , to generate private key $k_{Data^3}$ and public key $P_{Data^3}$ . Then output hexlified public key string with SM2 compressed public key format. The hexlified public key is denoted as $Data0-inlined$ .

The length of $Data0-inlined$ should be 64. If less, pad with '0' until the length is 64.

Let $UID-inlined$ be

   <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">

Use the algorithm describled in section 4, with argument $LL-inlined$ and private key $k-inlined$ describled section 6, to get signature $(r_L,s_L)$ .

The bit length of $r_L$ and $s_L$ shall not be more than 240. Otherwise, repeat this step.

Convert $r_L$ and $s_L$ to hex-integer string $SZ^{r_L}$ and $SZ^{s_L}$ , without "0x" prefix.

If the length of $SZ^{r_L}$ or $SZ^{s_L}$ is less than 60, pad character '0' until the length is 60.

Let $Data1-inlined$ be

   <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">

Let $Temp-inlined$ be

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

Use the algorithm describled in section 4, with argument $Temp-inlined$ and private key $k-inlined$ describled section 6, to get signature $(r_{Temp},s_{Temp})$ .

The bit length of $r_{Temp}$ and $s_{Temp}$ shall not be more than 240. Otherwise, repeat this step.

Convert $r_{Temp}$ and $s_{Temp}$ to hex-integer string $SZ^{r_{Temp}}$ and $SZ^{s_{Temp}}$ , without "0x" prefix.

If the length of $SZ^{r_{Temp}}$ or $SZ^{s_{Temp}}$ is less than 60, pad character '0' until the length is 60.

Let $Data2-inlined$ be

$Data^2=\texttt{"60"}||SZ^{s_{Temp}}||SZ^{r_{Temp}}$
Calculate CRC32 value of

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

The final checksum the complement of CRC32 value.

Then convert the checksum to decimal string $SZ^{checksum}$ . If the length is less than 10, pad character '0' until the length is 10.
Let $Data-inlined$ be

$Data=Data^0||Data^1||Data^2||Data^3||SZ^{checksum}$
Output with format
- A fixed header "RAR registration data", taking one line.
- Username, taking one line.
- License type, taking one line
- UID, taking one line, with format:
```
<img src="http://latex.codecogs.com/svg.latex?%5Ctexttt%7B%22UID%3D%22%7D%7C%7CUID">
```
- Output $Data-inlined$ , with 54 characters a line.

how-does-it-work.md 17 KB Permalink Cronologia Originale