加密算法初探

Intro

互联网上看到的一个简单的游戏：

接下来我们将进行一个加密&解密的游戏，按照以下操作步骤来进行：

取明文（你想要加密的内容）：任意一个6位数(或者6位以下)

已知公钥：381523

密文生成算法：(明文×公钥)→截取后6位

告诉我密文，我可以通过私钥得出明文
例如：明文123456，则123456*381523=47101303488
那么密文就是：303488

这只是一个入门的小游戏，由于本例采用的模数规模不大，容易被暴力算法攻破，下面来对这个游戏进行一定的解析。

不难看出，截取后六位即模数 $Mod=1e6$ ，设明文为A，公钥为E，密文为B，则有 $A*E\%Mod=B$ 。在我得到密文后，我会根据手中的私钥D与密文B相乘截取后六位，即可以得到明文A，即 $B*D\%Mod=A$

在这个过程中，不妨将第一个式子代入上式，则有 $(A*E\%Mod)*D\%Mod=A$ ，利用模运算的法则，等价于求 $(E*D)\%Mod=1$ ，用数学语言表示为 $E*D\equiv1(mod \ Mod)$

这时我们使用扩展欧几里得算法即可求解。

#include <cstdio>
typedef long long LL;
LL ExtGCD(LL a, LL b, LL &x, LL &y){
    // x, y 为引用传参，故最终程序结束后，x,y会被赋值为可行解
    if(b==0){
        // 递归终点，ax+by=GCD(a,b)的b为0，故方程变为
        // ax=a，则可行解可以是 x=1, y=0
        x=1, y=0;
        return a;
    }
    LL d=ExtGCD(b, a%b, x, y), t=x;
    x=y, y=t-a/b*x;
    return d;  // 这里返回值是GCD(a,b)的结果，即最大公约数
}
LL x,y;
int main(){
    printf("%lld\n",ExtGCD(381523,1000000,x,y));
    printf("%lld, %lld",x,y);
    return 0;
}

ExtGCD算法是用来计算 $ax+by=GCD(a,b)$ 的一组可行解。因此上述代码中公钥E是方程中的a，解得x为对应的私钥D。这是因为 $(E*D)\%Mod=1$

等价于 $ED-k*Mod=GCD(E,Mod)$ ，要求的参数即可与通式一一对应。

由于该例中模数为1e6，我们只需要构造一个形如Nn1的合数，其中N为任意正整数，n为多个0，0的个数取决于你想要加密的最大位数减一……再把Nn1因式分解，真因子分为两堆分别相乘得到互为公私钥的两个数就可以了……
当然，这个所谓的加密，攻击起来不难，不需要找到真正的私钥，只需要尝试找1n1、2n1……这类数，可得到完全不一样的私钥，但可以解密！本例中私钥为2587，则在对1e6取模的意义下，私钥1002587、2002587等等都可以使用，且不影响解密结果。这里是一个爆破该私钥的代码：

#include <cstdio>
typedef long long LL;
const LL E=381523;
int mod=1e6,n=1e7,c,a[100000];

void work1(){
    LL tmp=1;
    for(int i=1;i<=n;i++){
        tmp=1ll*i*E%mod;
        if(tmp==1) a[++c]=i;
    }
    printf("%d\n",c);
    for(int i=1;i<=c;i++){
        printf("%d ",a[i]);
    }
}

void work2(){
    LL tmp=0;
    for(int i=1;i<=n;i++){
        tmp=1ll*i*1000000+1;
        if(tmp%E==0) a[++c]=i;
    }
    printf("%d\n",c);
    for(int i=1;i<=c;i++){
        printf("%d ",a[i]);
    }
}

int main(){
    work2();
    return 0;
}

work1函数可以暴力解出符合条件的私钥，work2函数模仿上述假私钥构建思路进行爆破，运行结果为：

1
2
3

27
987 382510 764033 1145556 1527079 1908602 2290125 2671648 3053171 3434694 3816217 4197740 4579263 4960786 5342309 5723832 6105355 6486878 6868401 7249924 7631447 8012970 8394493 8776016 9157539 9539062 9920585
....