# ZJY-RSA

**Repository Path**: pukailiang/ZJY-RSA

## Basic Information

- **Project Name**: ZJY-RSA
- **Description**: 非对称加密算法
- **Primary Language**: C
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 3
- **Created**: 2023-02-17
- **Last Updated**: 2023-02-17

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## RSA-1024bit

### 介绍
非对称加密算法--基于 RSAES-PKCS1-v1_5 体系实现

### 原理描述

- RSA是一种非对称加密算法，采用随机生成两个大素数`p`和`q`，并通过`p`和`q`进一步计算得到对应的公钥`(n, e)`----私钥`(n, d)`对，其中`n`、`e`、`d`也是大整数。信息接收者A持有该私钥`pri`并且没有任何第二个人知道该密钥对（包括要给信息接收者发送信息的那个人），然后将私钥对应的公钥`pub`公开给全世界所有人。如果有人要给信息接收者A发送信息，信息内容会以某种固定方式进行加密，该加密过程需要用到A的私钥对应的公钥`pub`进行计算。加密之后得到一串密文，将密文通过某种方式发送给信息接收者A之后，A通过他的私钥`pri`对密文进行解密，解密过程也是一系列固定的计算过程且也需要用到私钥`pri`。解密之后的内容就是信息发送者所要发送的真实内容。

- 上述原理描述看起来会让人觉得过程非常简单，很容易就能破解，但是这个非对称加密算法的安全性还是挺高的。对极大整数进行因数分解的难度 (The Factoring Problem) 决定了 RSA 算法的可靠性。换言之，对一个极大整数做因数分解愈困难，RSA 算法就愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。
  
- 目前还没有可靠的攻击 RSA 算法的方式。短的 RSA 钥匙可能被强力方式解破 (比如 768个二进制位、即对应于232个十进制位以下的整数)。只要 RSA 密钥的长度足够长 (比如 1024-bit 至 15360-bit)，用RSA 加密的信息看来很难被破解。

### 数据结构设计

- 本次RSA算法的实现用到了`gmp`大数库来实现大数的运算，可以大大优化算法的速度和降低算法实现的难度。但要学习`gmp`大数库的相关知识。
  
- 由于操作的对象比较容易描述，大部分内容可以用字符数组来进行操作和存储。所以并没有使用其他的数据结构。


### 密钥生成

- 生成过程：
   + 选择两个不同的大素数 p 和 q，计算 N = pq。
   + 引用欧拉 $\varphi$ 函数，小于 N 且与 N 互素的正整数个数为$\varphi$(N) = $\varphi$(pq) = $\varphi$(p)$\varphi$(q) = (p-1) (q-1)。
   + 选择一个整数 e，1< e < $\varphi$(N) 且 gcd(e, $\varphi$(N)) = 1。
   + 求一个满足后面同余式的 d：ed  $\equiv$ 1 (mod  $\varphi$(N))。其中 d 是 e 模 $\varphi$(N)逆元，可以通过扩展欧几里得算法得到且 d 是必须是一个足够大的正整数。
   + 将 p 和 q 的记录销毁 (当 N 足够大时，寻找 p, q 将极其困难)。
   + 以 (e, N) 作为公钥，(d, N) 作为私钥。假设 Alice 想通过一个不可靠的媒体接收 Bob 的一条私人讯息，Alice 将她的公钥 (e, N) 公开给 Bob，而将她的私钥 (d, N) 严密收藏起来。

- 代码实现如下：
  
``` C
void GenerateKey(mpz_t e, mpz_t d, mpz_t N) {
  // 选择两个不同的大素数
  // 设置随机生成数
  gmp_randstate_t grst;
  gmp_randinit_default(grst);
  gmp_randseed_ui(grst, time(NULL));
  // 生成随机大素数
  mpz_t p, q, N1;
  mpz_inits(p, q, N1, NULL);
  //验证e和N的欧拉是否互斥
  mpz_t mol;
  mpz_init(mol);
  // 0 <= p,q <= 2^MODULU_BITS
  while(1) {
    mpz_urandomb(p, grst, MODULU_BITS / 2 - 1);
    mpz_urandomb(q, grst, MODULU_BITS / 2 + 1);
    // 调整为素数
    mpz_nextprime(p, p);
    mpz_nextprime(q, q);

    // N = p*q
    mpz_mul(N, p, q);

    // phi(N) = (p-1)*(q-1)
    mpz_sub_ui(p, p, 1);
    mpz_sub_ui(q, q, 1);
    mpz_mul(N1, p, q);

    // chose e
    // such that 1 < e < phi(N), and gcd(e, phi(N))=1
    // 1. 65537
    mpz_init_set_ui(e, 65537);

    // 求e的逆元, ed mod phi(N) = 1
    mpz_invert(d, e, N1);

    // gmp_printf("PUB: \ne = %Zx\nN = %Zx\n", e, N);
    // gmp_printf("PRI: \nd = %Zx\nN = %Zx\n", d, N);
    mpz_gcd(mol, N1, e);
    // gmp_printf("%Zd\n", mol);

    char buf[2*MODULU_BYTES + 1] = { '\0' }; 
    //cout << "strlen(buf): " << strlen(buf) << endl;

    gmp_sprintf(buf, "%0Zx", N);

    // cout << "strlen(buf): " << strlen(buf) << endl;
    // cout << "buf: " << buf << endl;

    if(strlen(buf) == MODULU_BYTES * 2 && mpz_cmp_ui(mol, 1) == 0) {
      //mpz_clear(mol);
      break;
    }
  }

  //释放内存
  mpz_clears(p, q, N1, mol, NULL);
}
```

### 加密
- 加密过程
   + 现在 Bob 想给 Alice 送一个消息 M，他知道 Alice 产生的公钥 (e, N)。
   + Bob 使用事先与 Alice 约好的格式将 M 转换为一个小于 N 的整数 n，比如他可以将每一个字符转换为其数字形式的 Unicode 码，然后将这些数字连在一起组成整数 n (假如他的信息非常长的话，他可以将这个信息分为几段，逐段加密)。
   + Bob 引用公钥 (e, N)，利用后面的公式，将 n 加密为 c： c = n<sup>e</sup> mod N。
   + Bob 算出 c 后可以将它经公开媒体传递给 Alice。

- 代码实现如下：
  
``` C
/* 
 * RSAES-PKCS1-V1_5-ENCRYPT ((n, e), M)
 * Iuput: (n, e): recipient’s RSA public key (k denotes the length in octets of the modulus n)
 *         M: message to be encrypted, an octet string of length mLen, where mLen <= k - 11
 * Ouput: C: ciphertext, an octet string of length k
 * Error: "message too long"
 */ 
void RSAES_PKCS1_V1_5_ENCRYPT(mpz_t n, mpz_t e, const unsigned char* M, unsigned char* C) {
  unsigned int m2Len = strlen((const char*)M);
  unsigned int mLen = m2Len / 2;

  //1. Length checking
  if (mLen > MODULU_BYTES - 11) {
    printf("ERROR: message too long\n");
    exit(-1);
  }

  //2. EME-PKCS1-v1_5 encoding
  char EM[2*MODULU_BYTES+1] = { '\0' };
  PKCS1_encoding(M, mLen, MODULU_BYTES, (unsigned char*)EM);
  // cout << "EM is: " << EM << endl;
  // cout << "strlen(EM) is: " << strlen(EM) << endl;

  //3. RSA encryption:
  // 3.a OS2IP
  mpz_t m;
  mpz_init(m);
  OS2IP((unsigned char*)EM, m, MODULU_BYTES);
  //3.b RSAEP
  mpz_t c;
  mpz_init(c);
  RSAEP(n, e, m, c);

  //3.c I2OSP
  I2OSP(c, MODULU_BYTES, C);


  //释放内存
  mpz_clear(m);
  mpz_clear(c);
}
```

### 解密

- 解密过程
   + Alice 得到 Bob 的消息 c 后利用她的私钥 (d, N) 解码。
   + Alice 利用以下的公式将 c 转换为 n'：n' = c<sup>d</sup> mod N
   + Alice 得到的 n’ 就是 Bob 的 n，因此可以将原来的信息 M 准确复原。

- 代码实现如下：

``` C
/* 
 * RSAES-PKCS1-V1_5-DECRYPT ((n, d), C)
 * Iuput: (n, d): recipient’s RSA private key 
 *         C: ciphertext to be decrypted, an octet string of length k
 *            where k is the length in octets of the RSA modulus n
 * Ouput: M: message, an octet string of length at most k - 11
 * Error: "decryption error"
 */ 
void RSAES_PKCS1_V1_5_DECRYPT(mpz_t n, mpz_t d, const unsigned char* C, unsigned char* M) {
  //1. Length checking
  if (strlen((const char*)C) != 2 * MODULU_BYTES || MODULU_BYTES < 11) {
    printf("ERROR: decryption error\n");
    exit(-1);
  } 

  // cout << " hello1" << endl; 

  //2. RSA decryption
  //2.a OS2IP
  mpz_t c;
  mpz_init(c);
  OS2IP(C, c, MODULU_BYTES);
  //2.b RSADP
  mpz_t m;
  mpz_init(m);
  RSADP(n, d, c, m);
  //2.c I2OSP
  unsigned char *EM = (unsigned char *)malloc((2 * MODULU_BYTES + 1) * sizeof(char));
  EM[2*MODULU_BYTES] = '\0';
  I2OSP(m, MODULU_BYTES, EM);

  //3. EME-PKCS1-v1_5 decoding
  int mLen = 0;
  PKCS1_decoding(EM, MODULU_BYTES, M, mLen);

  //释放内存
  free(EM);
  mpz_clear(c);
  mpz_clear(m);
}
```

### 编解码

#### 编码
  
- 对明文M进行填充操作：**EM = 0x00 || 0x02 || PS || 0x00 || M**
其中EM的长度为RSA的密钥长度，即1024bit。M的长度是可变的，PS的长度随着M的长度的改变而改变。在 PS 和 M 之间增加一个 0x00 是为了解码的时候能够正确的找出M。

- 代码实现如下：

``` C 
/*
 * EME-PKCS1-v1_5 encoding:
 * a. Generate an octet string PS of length k - mLen - 3
 *    consisting of pseudo-randomly generated nonzero octets.
 *    The length of PS will be at least eight octets.
 * 
 * b. Concatenate PS, the message M, and other padding to form
 *    an encoded message EM of length k octets as
 * 
 */ 
void PKCS1_encoding(const unsigned char* M, int mLen, int k, unsigned char* EM) {
  int PS_length = k - mLen - 3;
  int PS_int[PS_length];
  char buf[3] = {'\0'};
  char *PS_char = (char*)malloc((2 * PS_length + 1) * sizeof(char));
  PS_char[2*PS_length] = '\0';
  PS_char[0] = '\0';
  // EM = (char*)malloc((2 * k + 1) * sizeof(char));
  // EM[2*k] = '\0';

  srand(time(0));
  for (int i = 0; i < PS_length; ++i) {
    PS_int[i] = 1 + rand() % 255;
    //cout << PS_int[i] << endl;
    sprintf(buf, "%02x", PS_int[i]);
    strcat(PS_char, buf);
  }

  EM[0] = '0';
  EM[1] = '0';
  EM[2] = '0';
  EM[3] = '2';
  EM[4] = '\0';
  strcat((char*)EM, PS_char);
  EM[4+2*PS_length] = '0';
  EM[5+2*PS_length] = '0';
  EM[6+2*PS_length] = '\0';
  strcat((char*)EM, (const char*)M);

  //释放内存
  free(PS_char);
}
```

#### 解码

- 解码过程和编码过程相反，是从EM中找出有效的明文M，根据EM的特性来找出M。在这里不加赘述。

- 代码实现如下：
  
``` C
/*
 * EME-PKCS1-v1_5 decoding
 * Separate the encoded message EM into an octet string PS consisting of nonzero octets and a message M as
 *                 EM = 0x00 || 0x02 || PS || 0x00 || M
 */ 
void PKCS1_decoding(const unsigned char* EM, int k, unsigned char* M, int mLen) {
  if (EM[0] != '0' || EM[1] != '0' || EM[2] != '0'|| EM[3] != '2') {
    printf("ERROR: decryption error\n");
    exit(-1);
  }
  int PS_length = 0;
  int i = 4;
  while (i < 2 * k) {
    if (EM[i] == '0' && EM[i+1] == '0') {
      break;
    } else {
      PS_length++;
      i = i + 2;
    }
  }

  if (PS_length < 8 || PS_length == k - 2) {
    printf("ERROR: decryption error\n");
    exit(-1);
  }

  for (int j = i + 2; j < 2 * k; ++j) {
    M[j-i-2] = EM[j];
  }
  M[2*k-i-2] = '\0';
  mLen = strlen((const char*)M);

  // printf("PKCS1_decoding: EM is %s\n", EM);
  // printf("PKCS1_decoding: M is %s\n", M);
}
```