【CTF】RSA初探
简单的RSA原理理解和实现。
核心知识
- 欧拉定理
$$a^{\phi(n)} \equiv 1 \pmod n$$
-
费马小定理
$$a^{p-1} \equiv 1 \pmod p$$
实际上是欧拉定理中,$N$取质数,此时$\phi(N) = N - 1$。可以用来求乘法逆元。
-
米勒-拉宾素性检验
不能对费马小定理逆用,即:满足$a^{p-1} \equiv 1 \pmod p$的$p$不一定是质数,但是不是质数的概率是小的。多取几个$a$来验证,就可以让$p$近似是个素数。
二次检验:满足$x^2 \equiv 1 \pmod p$的$x$取值如果是平凡的($x = 1$和$x = p-1$),那么$p$是质数,否则$p$是合数。
可以这么证明:$x^2 \equiv 1 \pmod p$即$(x+1)(x-1) \equiv 0 \pmod p$。如果$p$是质数,那么$x+1$和$x-1$一定不能整除$p$;如果$p$是合数,才有可能存在$x+1$或$x-1$能够整除$p$。
-
大整数快速分解质因数
要计算大整数$N$的欧拉函数$\phi(N)$的复杂度为指数,可以认为是计算不可解问题。
-
扩展欧几里得算法
用于求解$Ax + By = 1$问题时,直接套用。
template<typename T>
T exgcd(const T& a, const T& b, T& x, T& y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
T r = exgcd(b, a%b, x, y);
T tmp = y;
y = x - (a / b) * y;
x = tmp;
return r;
}
背景
加密算法分为对称加密、不对称加密两种。对称加密的加密、解密钥是一致的,但要求通信双方提前约定密钥,难以进行互联网通信;而不对称加密的加密、解密钥不同。在RSA中,加密钥为公钥,可以对外公开,而私钥不对外公开。
大致流程
假设发送方和接收方为A和B,要发送的信息为$a$。
-
由接收方开始,确定公钥$E$和大整数$N$,计算出私钥$D$,将$(N, E)$发送给A。
-
A使用$(N, E)$加密信息$a$为$c$,将$c$发送给B。这个步骤中,$c = a^{E} \bmod N$。
-
B使用私钥$D$将$c$还原为$a$。这个步骤中,$a = c^{D} \bmod N$。
原理
不难看出,要令$c = a^{E} \bmod N$和$a = c^{D} \bmod N$同时满足,只需要令$a^{DE} \equiv a\pmod N$。注意到欧拉定理$a^{\phi(N)} \equiv 1 \pmod N$,稍作变换可以得到:
$$a^{k\phi(N)} \equiv 1 \pmod N$$
$$a^{k\phi(N)+1} \equiv a \pmod N$$
所以只需要让$DE = k\phi(N)+1$即可。此即:
$$DE \equiv 1 \pmod {\phi(N)}$$
具体操作流程
-
B选择一个大整数$N = pq$,其中$p, q$均为质数。
-
B计算$\phi(N) = (p-1)(q-1)$,再选择一个$E$使得$(N, E)$。这里可以先选择$3, 7, 65537$中的一个。使用扩展欧几里得算法再算出$D$使得$DE \equiv 1 \pmod {\phi(N)}$。将$(N, E)$发送给A。
-
A将要加密的$a$经过运算$c = a^{E} \bmod N$后,发送给B。
-
B将密文$c$经过运算$a = c^{D} \bmod N$解密。