RSA公钥密码体制

2018-12-04 本文已影响0人壹东一兮

前言

RSA密码是目前使用最为广泛的公钥密码。它的可靠性是基于大数的因子分解问题，只有很短的RSA密钥才可能被穷举法破解，只要密钥的长度足够长，用RSA加密的信息实际上是不可能被破解的。

M为明文，C为密文

确定n
独立选取两个大素数p，q（100~200位十进制数字） $n=p×q$ 。
确定e
计算n的欧拉函数值 $\phi(n) =（p-1）×（q-1）$ ，在 $1$ ~ $\phi(n)$ 中随机选取整数e，使得 $gcd(\phi(n),e)=1$ ,即欧拉函数值和公钥的最大公因数为1，即为互素数。
确定d
计算e 模 $\phi(n)$ 的乘法逆元，即为d。 $ed\equiv1(mod\ \phi(n))$ (同余）
即 $ed\ mod\ \phi(n) = 1$

欧拉函数
定义：小于n且与n互素对的正整数的个数，记为 $\Phi(n)$ ,把 $\Phi(n)$ 称为欧拉函数。显然对于素数p，每一个小于p的正整数都与p互素，所以有 $\Phi(p)=p-1$ 。
定理：设有两个素数p和q，p $\neq$ q,那么对于n=pq，有
$\Phi(n)=\Phi(pq)=\Phi(p)\times\Phi(q)=(p-1)\times(q-1)$
欧拉定理
对于任意互素的整数a和n，有 $a^{\Phi(n)}\equiv1\ mod\ n$ 。