当使用公共的模数n,不同的私钥e1, e2对同一密文进行加密时,如果能截获密文c1, c2那么可能可以直接解密。
之所以说可能，是因为条件还是有要求的，比如说：e1和e2需要互素。推导过程如下：
若gcd(e1, e2) = 1, 即e1 e2互素时，由扩展欧几里德算法可知：
必然存在整数s1, s2。使得下式①成立：e1s1 + e2s2 = 1
e1 e2都为正数那么，s1 s2是一正一负的，这里可以假设s1是负数。
若记明文为m, e1,e2共用模数加密后的密文为c1, c2。即c1 = me1, c2 = me2
那么可以根据①构造下式(运算皆mod n)：
c1s1 * c2s2 = (me1)s1 * (me2)s2 = me1s1 + e2s2 = m1 = m
这里做简单的2个回顾/讨论.
- 为什么e1 e2互素,由扩展欧几里德算法可知必然存在e1s1 + e2s2 = 1？
- 如此解密会不会破坏可逆性质？
问题1：相当于复习一下推导过程。
a = q1b + r1 r1 = ax1 + by1
b = q2r1 + r2 r2 = ax2 + by2
r1 = q3r2 + r3 r3 = ax3 + by3
... ...
rn-2 = qnrn-1 + rn rn = axn + byn
rn-1 = qn+1rn + 0
对左边一列观察/移项可知 ri = ri-2 - ri-1qi ②
而由右边又可知
ri-2 = axi-1 + byi-2
ri-1 = axi-1 + byi-1
上2式代入②可得ri = a(xi-2 + qixi-1) + b(yi-2-qiyi-1)
又已经假设了ri = axi + byi 所以可得等式
xi = xi-2 - qixi-1
yi = yi-2 -qiyi-1 这个等式也就是说，i行的xi和yi，依赖于前两行的x和y和当前行的q。如果我们从r1开始计算,需要知道r-1和r0,这两项的值定为a, b.那么
由r-1 = ax-1 + by-1 = a 以及 r0= ax0 + by0 = b
这四项的值也随之确定，也就是说，开头的条件是满足的。至于结束：原始的欧几里得算法，当
rn-1 = qn+1rn + 0时结束，此时右边的一列即rn = axn + byn。即我们可以得到这样一个xn和yn，使得rn = axn + byn,而rn又是gcd(a, b)，又因为a，b互素，即gcd(a, b) = 1
综上所述e1 e2互素,由扩展欧几里德算法可知必然存在e1s1 + e2s2 = 1
问题2:我们构造的是mod n条件下（域内）的 (me1)s1 * (me2)s2，没有改变目标明文，也没有通过其他明文来跳转，所以我认为能正确还原明文。。我认为而已。
然后就是例题：有个人用同一个模数N对同一段明文m用不同的秘钥e1 e2加密得c1 c2，你现在获取了这5个参数，求m。
头文件
#ifndef BASICALGORITHM_H
#define BASICALGORITHM_H
#include<gmp.h>
#include<gmpxx.h>
typedef mpz_class bn; // big number
/**
* 快速幂取模,输入a, b, c
* 返回: a^b mod c
*/
bn F_exp(bn a, bn b, bn c);
/**
* 快速乘取模,输入a, b, c
* 返回: a*b mod c
*/
bn F_mul(bn a, bn b, bn c);
/**
* 扩展欧几里德
* 通过引用x y返回a,b对应的逆元
*/
void exgcd(bn a, bn b, bn& x, bn& y);
/**
* 一般gcd,返回gcd(a, b)
*/
bn gcd(bn a, bn b);
#endif
main文件
#include<bits/stdc++.h>
#include"BasicAlgorithm.h"
using namespace std;
int main() {
bn N("1889570071", 10);
bn e1("1021763679", 10); bn e2("519424709", 10);
bn c[2];
c[0].set_str("1244183534", 10); c[1].set_str("732959706", 10);
/*e1s[0] + e2s[1] = gcd(e1, e2)*/
bn s[2], x, rev;
exgcd(e1, e2, s[0], s[1]);
/*tn : the negative one*/
int tn = 0;
if (s[1] < 0) tn = 1;
/**
* 得知下标为tn的s为负数(自然!tn就是正数的了)
* 求s[tn]对应的密文模n的正数逆rev，假设s[0] < 0
* 因 c1^s[0] = (c1^(-1))^(-s[0]) 如此就能全部域内正数操作了
*/
exgcd(N, c[tn], x, rev);
if (rev < 0) rev = (rev + N) % N;
bn res = F_mul(F_exp(rev, -s[tn], N), F_exp(c[!tn], s[!tn], N), N);
cout<<"RESULT ->\n" <<res <<"\n";
return 0;
}
得结果
RESULT ->
1054592380
