【CTF】RSA初探

2021-07-04 约 1035 字预计阅读 3 分钟

简单的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$解密。

目录

【CTF】RSA初探

核心知识

背景

大致流程

原理

具体操作流程