目录

【CTF】RSA初探

简单的RSA原理理解和实现。

核心知识

  1. 欧拉定理

$$a^{\phi(n)} \equiv 1 \pmod n$$

  1. 费马小定理

    $$a^{p-1} \equiv 1 \pmod p$$

    实际上是欧拉定理中,$N$取质数,此时$\phi(N) = N - 1$。可以用来求乘法逆元。

  2. 米勒-拉宾素性检验

    不能对费马小定理逆用,即:满足$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$。

  3. 大整数快速分解质因数

    要计算大整数$N$的欧拉函数$\phi(N)$的复杂度为指数,可以认为是计算不可解问题。

  4. 扩展欧几里得算法

    用于求解$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$。

  1. 由接收方开始,确定公钥$E$和大整数$N$,计算出私钥$D$,将$(N, E)$发送给A。

  2. A使用$(N, E)$加密信息$a$为$c$,将$c$发送给B。这个步骤中,$c = a^{E} \bmod N$。

  3. 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)}$$

具体操作流程

  1. B选择一个大整数$N = pq$,其中$p, q$均为质数。

  2. B计算$\phi(N) = (p-1)(q-1)$,再选择一个$E$使得$(N, E)$。这里可以先选择$3, 7, 65537$中的一个。使用扩展欧几里得算法再算出$D$使得$DE \equiv 1 \pmod {\phi(N)}$。将$(N, E)$发送给A。

  3. A将要加密的$a$经过运算$c = a^{E} \bmod N$后,发送给B。

  4. B将密文$c$经过运算$a = c^{D} \bmod N$解密。