# RSA_Exercise

**Repository Path**: barytes/rsa_-exercise

## Basic Information

- **Project Name**: RSA_Exercise
- **Description**: RSA-PKCS#1-v1_5简单实现
- **Primary Language**: C
- **License**: MulanPSL-1.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 4
- **Forks**: 1
- **Created**: 2020-10-28
- **Last Updated**: 2024-09-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# RSA实验报告

本次实验简单实现了 RSAES-PKCS1-v1_5 体系的RSA算法。完整代码可见如下 gitee 仓库：

[barytes / RSA_Exercise](https://gitee.com/barytes/rsa_-exercise)

## 原理描述

### 记号

1. c：密文表示，一个 0 - n-1 的整型
2. C：密文，一个八位字节的字串
3. e：RSA公钥指数
4. EM：已编码信息，一个八位字节的字串
5. emBits：以位为单位的EM的长度
6. emLen：以八位字节为单位的EM的长度
7. k：以八位字节为单位的 RSA 模值 n 的长度
8. K：RSA私钥
9. m：消息表示，一个0 - n-1的整型值
10. M：消息，一个八位字节的字串
11. mLen：以八位字节为单位的M的长度
12. n：RSA 模值
13. (n, e)：RSA 公钥
14. p，q：RSA 模值 n 的两个质因子
15. u：RSA 模值 n 的质因子数量，u >= 2
16. x：一个非负整数
17. X：x 对应的八位字节字串
18. xLen：以八位字节为单位的 X 的长度

### 密钥类型

#### RSA 公钥

RSA 公钥为一个整型值的二元组，其元素分别为：

1. n：RSA 模值，一个正整型值
2. e：RSA 公钥指数，一个正整型值

n 为多个（大于等于2）不同的大质数 r_i（i = 1，2，..... ，u）的乘积，在此实验中令 n 为两个大质数 p，q 的乘积。而公钥指数 e 是一个 3 - n-1 之间的整型，且满足` GCD( e, φ(n) ) = 1`。φ(n) 为（r_i - 1）的最小公倍数，在此实验中即`（p-1）*（q-1）`。

#### RSA私钥

RSA 私钥有两种表示方式，简单的一种是一个二元组：

1. n：RSA 模值，一个正整型值
2. d：RSA 私钥指数，一个正整型值

d 是一个小于 n 的正整型值，满足` ed ≡ 1 (mod φ(n))`。

另一种详见文档。

### 原语

#### 数据转换原语

##### I2OSP

I2OSP 将一个非负整型值转换为一个特定长度的八位字节的字串。

输入：

- x：需要转换的非负整型值
- xLen：结果字串的预期长度

输出：

- X：对应的八位字节的字串，长度为 xLen

异常：

- “integer too large”

步骤：

1. 如果  `x >= 256^xLen`，输出"integer too large"并停止。

2. 将 x 写成一个 256 进制的 xLen 位的表示方式：

   `x = x_(xLen-1)*256^(xLen-1) + x_(xLen-2)*256^(xLen-2) + ... + x_1*256 + x_0`

   其中 `0 <= x_i < 256`（注意：当 x 小于 256^(xLen-1) 时，一或多个高位数字为0）。

3. 将整型值 x_(xLen-i) 赋值给一个八位字节 X_i (1 <= i <= xLen)，输出字串X如下：

   `X = X_1 X_2 ... X_xLen`

##### OS2IP

OS2IP 将一个八位字节的字串转换为一个非负整数。

输入：八位字节字串 X

输出：对应非负整型 x

步骤：

1. 令 X_1 X_2 ... X_xLen 分别为 X 从头到尾的各个八位字节，并令 x_(xLen-i) 为 X_i 对应的整型值(1 <= i <= xLen)
2. 令 `x = x_(xLen-1)*256^(xLen-1) + x_(xLen-2)*256^(xLen-2) + ... + x_1*256 + x_0`
3. 输出 x

#### 密码学原语

##### RSAEP

RSAEP((n, e), m)

输入：

1. （n, e）：RSA 公钥（假定公钥对是合法的）
2. m：代表消息的整型值，0 <= m <= n-1

输出：

​	c：表示密文的整型值，0 <= c <= n-1

异常：

​	"message representive out of range"

步骤：

1. 如果 m 并非在 0 - n-1 之间，输出"message representive out of range" 并停止
2. 令 `c = m^e mod n`
3. 输出 c

##### RSADP

RSADP(K, c)

输入：

1. K：RSA 密钥，K = (n, d)（假定 K 是合法的）
2. c：表示密文的整型值，0 <= c <= n-1

输出：

​	m：代表消息的整型值，0 <= m <= n-1

异常：

​	"ciphertext representive out of range"

步骤：

1. 如果 c 并非在 0 - n-1 之间，输出"ciphertext representive out of range" 并停止
2. 令 `m = c^d mod n`
3. 输出 m

### RSAES-PKCS#1-v1_5体系

#### 加密操作

RSAES-PKCS1-V1_5-ENCRYPT ((n, e), M)

输入：

1. (n, e) ：接收方的 RSA 公钥
2. M：需要加密的消息，长度为 mLen 字节的字串，其中 mLen <= k - 11

输出：

​	C：密文，长度为 k 字节的字串

异常：
	”message too long“

步骤：

1. 长度检查：如果 mLen > k -11，输出 ”message too long“ 并停止

2. EME-PKCS1-v1_5 编码：

   1. 生成一个由 k - mLen - 3 个随机非0八位字节组成的字串 PS，其长度至少为 8 字节

   2. 将 PS、M 和其他填充值拼接为长度为 k 字节的字串 EM：

      `EM = 0x00 || 0x02 || PS || 0x00 || M`

3. RSA 加密：
   1. 将 EM 转换为整型值 m：`m = OS2IP (EM) `
   2. 对 m 应用 RSAEP 原语得到整型值 c：`c = RSAEP ((n, e), m)`
   3. 将整型值 c 转换为长度为 k 字节的字串 C：`C = I2OSP (c, k)`
4. 输出 C

#### 解密操作

RSAES-PKCS1-V1_5-DECRYPT (K, C)

输入：

1. K：接收方的 RSA 私钥
2. C：需要解密的密文，长度为 k 字节的字串，其中 k 为 RSA 模值的长度

输出：

​	M：明文，长度最多为 k-11 字节的字串

异常：
	”decryption error“

步骤：

1. 长度检查：如果 密文 C 的长度并非 k 字节，或 k < 11，输出 ”decryption error“ 并停止

2. RSA 解密：

   1. 将 C 转换为整型值 c：`c = OS2IP (C) `
   2. 对 c 应用 RSADP 原语得到整型值 c：`m = RSADP ((n, d), c)`
   3. 将整型值 m 转换为长度为 k 字节的字串 EM：EM = I2OSP (m, k)`

3. EME-PKCS1-v1_5 解码：

   1. 将 EM 按照如下格式解码：

      `EM = 0x00 || 0x02 || PS || 0x00 || M`

   2. 如果 EM 格式不正确，输出 ”decryption error“ 并停止

4. 输出 M

## 数据结构设计

1. 字串：本代码使用`unsigned char*` 类型表示体系中八位字节字串，并将`unsigned char`类型包装为自定义类型`UCHAR`。
2. 整型值：本代码依赖于大整数运算库 gmp，使用 gmp 中的数据类型 mpz_t 表示整型值。
3. 长度：对于字节长度，本代码使用`unsigned int`类型表示；对于位长度，本代码使用`unsigned long`类型表示；并将二者分别包装为`SIZE_T`和`SIZE_BIT_T`。

## 密钥生成

本代码中，密钥生成模块为`generateKeys()`函数，其逻辑结构如下：

```
generateKeys(k){
	检查k是否合法
	设置e为65537
	随机生成(k+1)/2 bit整数p_tmp
	while(1){
		设置p为大于p_tmp的下一个质数
		do{
			生成k/2 bit整数q_tmp
			设置q为大于q_tmp的下一个质数
			计算 n = pq
		}while(n 位数小于k)
		计算φ(n) = (p-1)(q-1)
		若gcd(φ(n), e) != 1, 则continue
		计算e的模φ(n)逆元d
		返回n,e,d 
	}
}
```

完整代码如下：

```c
int generateKeys(const SIZE_BIT_T k, mpz_t *kn, mpz_t *ke, mpz_t *kd){
    //检查k是否合法
    if(k < MIN_K|| k > MAX_K){
        return ERROR_INT;
    }
    mpz_t p, q, n, d, e, p_tmp, q_tmp, p_m1, q_m1, phi_n, gcd;
    mpz_inits(p, q, n, d, e, p_tmp, q_tmp, p_m1, q_m1, phi_n, gcd, NULL);
    
	//设置e为常数值65537
    mpz_set_ui(e, 65537);
	//设置随机数种子
    gmp_randstate_t state;
    gmp_randinit_default(state);
    clock_t tm = time(NULL);
    gmp_randseed_ui(state, tm);
	//设定p、q比特数
    mp_bitcnt_t p_bitcnt = (k + 1) >> 1;
    mp_bitcnt_t q_bitcnt = k - p_bitcnt;
    //生成p_bitcnt比特随机整数p_tmp
    mpz_rrandomb(p_tmp, state, p_bitcnt);
    //寻找合适的p、q、
    while(1) {
        //生成n的其中一个质因子p
        //p为大于p_tmp的下一个质数
        mpz_nextprime(p, p_tmp);
        //生成k bit的大整数n
        do {
            //生成n的另一个质因子q
            gmp_randseed_ui(state, ++tm);
            mpz_rrandomb(q_tmp, state, q_bitcnt);
            mpz_nextprime(q, q_tmp);
            if(mpz_cmp(p, q) < 0) {
                mpz_swap(p, q);
            }
            //计算n
            mpz_mul(n, p, q);
        } while(mpz_sizeinbase(n, 2) < k);
		//计算φ(n)=(p-1)(q-1)
        mpz_sub_ui(p_m1, p, 1);
        mpz_sub_ui(q_m1, q, 1);
        mpz_mul(phi_n, p_m1, q_m1);
        //计算gcd(φ(n), e)
        mpz_gcd(gcd, phi_n, e);
        //若gcd(φ(n), e) != 1，则重新寻找p、q
        if (mpz_cmp_ui(gcd, 1) != 0) continue;
		
        //计算d为e的模φ(n)逆元
        mpz_invert(d, e, phi_n);
        //返回n，e，d
        mpz_set(*kn, n);
        mpz_set(*ke, e);
        mpz_set(*kd, d);
        break;
    }

    mpz_clears(p, q, n, d, e, p_tmp, q_tmp, p_m1, q_m1, phi_n, gcd, NULL);
    return 0;
}
```

## 加密

本代码中，`RSA_PKCS1_v1_5_Encrypt()`函数实现了加密功能，其调用结构如下：

```
RSA_PKCS1_v1_5_Encrypt(M, n, e, k) = C
	|--EME_PKCS1_v1_5_Encoding(M, k, mLen) = EM
	|--OS2IP(EM, k) = m
    |--RSAEP(m, n, e) = c
    |--I2OSP(c, k) = C
```

完整代码如下：

```c
int RSA_PKCS1_v1_5_Encrypt(const UCHAR *M, const mpz_t n, const mpz_t e, const SIZE_T k, UCHAR **C){
    int mLen = strlen(M);
    if(mLen > k - 11){
        printf("message too long\n");
        return ERROR_INT;
    }

    UCHAR *EM = (UCHAR*)malloc(k+1);
    *C = (UCHAR*)malloc(k+1);
    mpz_t m, c;
    memset(EM, '\0', k+1);
    memset(*C, '\0', k+1);
    mpz_inits(m, c, NULL);

    EME_PKCS1_v1_5_Encoding(EM, M, k, mLen);
    OS2IP(&m, EM, k);
    RSAEP(&c, m, n, e);
    I2OSP(*C, c, k);

    mpz_clears(m, c, NULL);
    free(EM);
    return 0;
}
```

### I2OSP

`I2OSP()`函数实现了将 xLen 字节整数 x 转换为对应字串 X 的功能。

该功能的本质在于将大整数 x 按八位字节截断，将各个字节的值分别存储于单字节 char 变量中，并最终将 x 转化为一个 char 数组，即字串 X 。

```
x：|------------------------------a_big_int----------------------------------|
                                     |
                                     v
X：|-char-|-char-|-char-|-char-|-char-|-char-|-char-|-char-|-char-|-char-|---|
```

数学上来说，该功能是将十进制的大整数 x 转换为256进制的表示，并将256进制 x 各位的值存储于一个八位字节的 char 中。

函数逻辑如下：

```
for(i=1; i<=xLen; i++){
	X[i-1] = x/(256^(xLen-i))
	x = x % 256^(xLen-i)
}
```

完整代码如下：

```c
void I2OSP(UCHAR *X, mpz_t x, const SIZE_T xLen) {
    mpz_t uplim, base, pow, xi, remain;
    mpz_inits(uplim, base, pow, xi, remain, NULL);
    mpz_set(remain, x);
    mpz_set_ui(base, 256);
    mpz_pow_ui(uplim, base, xLen);

    if (mpz_cmp(x, uplim) >= 0){
        printf("integer too large\n");
        mpz_clears(uplim, base, pow, xi, NULL);
        return;
    }

    int i = 1;
    while(i <= xLen) {
        mpz_pow_ui(pow, base, (xLen - i));
        mpz_tdiv_q(xi, remain, pow);
        mpz_mod(remain, x, pow);
        X[i-1] = (UCHAR)mpz_get_ui(xi);
        i++;
    }

    mpz_clears(uplim, base, pow, xi, remain, NULL);
}
```

### OS2IP

`OS2IP()`函数实现了将 xLen 字节字串 X 转化为对应整型 x 的功能。该功能即为`I2OSP()`的逆过程，实质上为256进制数 X 转换为十进制 x 的过程。函数逻辑如下：

```
for(i=1; i<=xLen; i++){ 
	x += X[i-1] * 256^(xLen-i)
}
```

完整代码如下：

```c
void OS2IP(mpz_t *x, const UCHAR *X, const SIZE_T xLen){
    int i=1;
    mpz_t tmp, pow, base, xi;
    mpz_inits(tmp, pow, base, xi, NULL);
    mpz_set_ui(*x, 0);
    mpz_set_ui(base, 256);
    while(i <= xLen) {
        mpz_pow_ui(pow, base, (xLen- i));
        mpz_mul_ui(xi, pow, X[i-1]);
        mpz_add(tmp, tmp, xi);
        i++;
    }
    mpz_set(*x, tmp);
    mpz_clears(tmp, pow, base, xi, NULL);
}
```

### RSAEP

`RSAEP()`完成的是加密工作，实际上只是计算了算式 `c = m^e mod n` ，完整代码如下：

```c
void RSAEP(mpz_t *c, const mpz_t m, const mpz_t n, const mpz_t e){
    mpz_t up_lim, down_lim;
    mpz_inits(up_lim, down_lim, NULL);
    mpz_set_ui(down_lim, 0);
    mpz_sub_ui(up_lim, n, 1);

    if(mpz_cmp(m, down_lim) < 0 || mpz_cmp(m, up_lim) > 0){
        mpz_clears(up_lim, down_lim, NULL);
        printf("message representive out of range\n");
        return;
    }
    mpz_powm(*c, m, e, n);
    mpz_clears(up_lim, down_lim, NULL);
} 
```

## 解密

函数`RSA_PKCS1_v1_5_Decrypt()`实现了解密功能。其调用结构如下：

```
RSA_PKCS1_v1_5_Decrypt(C, n, d, k) = M
	|-- OS2IP(C, k) = c
	|-- RSADP(c, n, d) = m
	|-- I2OSP(m, k) = EM
	|-- EME_PKCS1_v1_5_Decoding(EM, k) = M
```

完整代码如下：

```c
int RSA_PKCS1_v1_5_Decrypt(const UCHAR *C, const mpz_t n, const mpz_t d, const SIZE_T k, UCHAR **M){
    UCHAR *EM = (UCHAR*)malloc(k+1);
    *M = (UCHAR*)malloc(k+1);
    mpz_t c, m;
    mpz_inits(c, m, NULL);
    memset(EM, '\0', k+1);
    memset(*M, '\0', k+1);

    OS2IP(&c, C, k);
    RSADP(&m, c, n, d);
    I2OSP(EM, m, k); 
    EME_PKCS1_v1_5_Decoding(*M, EM, k);

    free(EM);
    mpz_clears(c, m, NULL);
    return 0;
}
```

### RSADP

`RSADP()`完成的是解密工作，实际上只是计算了算式 `m = c^d mod n` ，完整代码如下：

```c
void RSADP(mpz_t *m, const mpz_t c, const mpz_t n, const mpz_t d){
    mpz_t up_lim, down_lim;
    mpz_inits(up_lim, down_lim, NULL);
    mpz_set_ui(down_lim, 0);
    mpz_sub_ui(up_lim, n, 1);

    if(mpz_cmp(c, down_lim) < 0 || mpz_cmp(c, up_lim) > 0){
        mpz_clears(up_lim, down_lim, NULL);
        printf("message representive out of range\n");
        return;
    }
    mpz_powm(*m, c, d, n);
    mpz_clears(up_lim, down_lim, NULL);
}
```

## 编解码

### 编码

函数`EME_PKCS1_v1_5_Encoding()`实现了编码功能：输入消息 M 填充为长度为 k 字节的串 EM 。

该函数仅是进行了简单的函数拼接。不过需要注意的地方有三点：

1. EM 填充的字节值如下所示：

   ```
   EM = 0x00 || 0x02 || PS || 0x00 || M
          |       |     |       |     |
   value: 0       2     ascii   0     ascii
   ```

2. 为便于调试，使用`randStr()`函数生成随机字串 PS 时，`randStr()`函数生成的字串仅是 ASCII 码表 0x21 - 0x7E 的可显示字符。

3. `mystrcat(str1, str2, idx1, len2)`函数的作用如下：将 str2 起长度 len2 的字符逐个填进 str1 的 idx1 起往后的位置。该函数要求 str1 从 idx1 起有足够的位置容纳 len2 个字符。

完整代码如下：

```c
void EME_PKCS1_v1_5_Encoding(UCHAR *EM, const UCHAR *M, const SIZE_T k, const SIZE_T mLen){
    UCHAR prefix[] = {0, 2};
    UCHAR suffix[] = {0};
    UCHAR *ps = (char*)malloc(k - mLen - 3);
    memset(ps, 0, k-mLen-3);
    randStr(ps, k-mLen-3);

    EM[0] = prefix[0];
    EM[1] = prefix[1];
    int i = 2;
    i = mystrcat(EM, ps, i, k-mLen-3);
    i = mystrcat(EM, suffix, i, 1);
    i = mystrcat(EM, M, i, mLen);
    free(ps);
}
```

### 解码

函数`EME_PKCS1_v1_5_Decoding()`实现了解码功能：将 EM 按填充格式解码为 M。

函数逻辑如下：从EM 的第三个字节（前两个字节分别为 0x00 和 0x02），即 PS 的第一个字节开始向后扫描，遇到值为 0 的字节后读取后续的字节为消息 M。

完整代码如下：

```c
void EME_PKCS1_v1_5_Decoding(UCHAR *M, const UCHAR *EM, const SIZE_T emLen){
    int i = 2, j = 0;
    bool is_msg = false;

    while(i < emLen){
        if(is_msg){
            M[j] = EM[i];
            j++;
        }
        if(EM[i] == 0){
            is_msg = true;
        }
        i++;
    }
}
```

## 实验结果示例

![image-20201028192923094](https://i.loli.net/2020/10/28/aosCD1cy9ZKRFqL.png)

![image-20201028193101981](https://i.loli.net/2020/10/28/twsfJ3IXa6EvKWG.png)

## 参考资料

1. [PKCS #1: RSA Cryptography Specifications Version 2.2](https://datatracker.ietf.org/doc/rfc8017/)