Contents

# 秘钥生成与正确性

## RSA秘钥生成

1. 选择两个大素数 p ,q
2. 计算 $n$ = $p * q$
3. 计算 $\phi$( n ) = $( p - 1 )( q - 1 )$
4. 选择 e $\in$ $Z^m$ 且 gcd（m，e）= 1
5. 计算私钥 d 满足 d * e = 1 mod $\phi$(n)

## RSA 核心原理

$C^d$ $\equiv$ $M^{d * e}$ $\equiv$ $M$ mod $n$

• $d * e = 1 + t * \phi(n)$
• $M^{d * e}\equiv M^{1 + t * \phi(n)}\equiv M * M^{t * \phi(n)}\equiv 1 * M$ mod $n$

# 7.5.2 使用中国余数定理快速加解密（CRT）

1. 约简基元素 $M$：

$M_p$ $\equiv$ $M$ mod $p$

$M_q$ $\equiv$ $M$ mod $q$

2. 计算两个指数并进行列出的指数运算

两个指数：

$d_p\equiv d$ mod $(p-1)$

$d_q\equiv d$ mod $(q-1)$

运算：

$C_p\equiv M^{d_p}_p$ mod $p$

$C_q\equiv M^{d_q}_q$ mod $q$

3. 逆向换到问题域：

$C$ $\equiv$ $C_p * M_p * q$ + $C_q * M_q * p$ mod $n$