由于这题难到我了，所以做个md来记录
1.题目内容
\[ p = 8637633767257008567099653486541091171320491509433615\newline447539162437911244175885667806398411790524083553445158113\newline502227745206205327690939504032994699902053229 \newline\newline q = 126406749739964727691760479371708834209270508214800\newline1058159313713537247388059561373733763062975257734614703928\newline4030082593490776630572584959954205336880228469 \newline\newline dp = 650079570221683462110904235119326153065004384105625\newline2930930949663358625016881832840728066026150264693076109354\newline874099841380454881716097778307268116910582929 \newline\newline dq = 783472263673553449019532580386470672380574033551303\newline8891379117604388816836745560980982567956735122019630021754\newline38762767516968043599582527539160811120550041 \newline\newline c = 24722305403887382073567316467649080662631552905960\newline22939907910799560215441817605633580063888752761416407353043\newline7657085079676157350205351945222989351316076486\newline5735995760419783398722659250627643185360890073102702785261596\newline78937431903862892400747915525118983959970607\newline934142974736675784325993445942031372107342103852\newline\newline \] 其中 \[ dp=d\%(p-1)\newline dq=d\%(q-1) \] 已知这些数字，解RSA原文吧
不得不说这数字比我命还长。。。
2.尝试
要解密密文，我一开始想的是找私钥d
思路很简单粗暴——试商
1 |
|
但就从这一堆比我命还长的数就能看出来，结果基本跑不出来
那只能换个方式
但我没有思路，只能选择看答案
3.不会，看答案
1 | p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 |
重点应该就是这部分了
暂且不深究gmpy2库里面有什么
gmpy2.invert(q,p)返回的是q在模p下的逆元，然后赋值给I，即 \[ Iq≡1\quad(mod\space p) \] 然后再定义 \[ mp=c^{dp}\%p\newline mq=c^{dq}\%q \] 但最后比较疑惑人的是这一步 \[ m = (((mp-mq)*I)\%p)*q+mq \] 至少我看答案的时候不知道这是个什么
定理提供
1.中国剩余定理
但问问AI就了解到了——中国剩余定理（Chinese Remainder Theorem，CRT） \[ 若有一组模数m_{1},m_{2},m_{3}...m_{k},一组余数r_{1},r_{2},r_{3}...r_{k}\newline 并且数组m满足其中所有数两两互质 (详：∀i≠j，满足i,j∈[1,k]且为整数，则有gcd(m_{i},m_{j})=1)\newline 则对关于x的方程组\newline \left\{ \begin{aligned} &x≡r_{1}\quad(mod\space m_{1})\newline &x≡r_{2}\quad(mod\space m_{2})\newline &x≡r_{3}\quad(mod\space m_{3})\newline &...\newline &x≡r_{k}\quad(mod\space m_{k}) \end{aligned} \right. \newline 记M=\prod\limits_{i=1}^{k}{m_i}\newline 在[0,M-1]的范围内一定存在唯一整数解x\newline 并且这个定理也给出了求解x的方式：\newline 1.计算M=\prod\limits_{i=1}^{k}{m_i}\newline 2.计算M_i=\frac{M}{m_i}，其中i取遍1到k\newline 3.计算y_i，y_i满足M_iy_i≡1\quad(mod\space m_i)，即y_i是M_i在模M下的逆元。\newline 可以使用扩展欧几里得算法来计算逆元\quad(后面会补充说明)\newline 4.计算最后结果x\newline x≡\sum\limits_{i=1}^{k}r_iM_iy_i\quad(mod\space M)\newline 取x∈[0,M-1]，即x=(\sum\limits_{i=1}^{k}r_iM_iy_i)\%M\newline、 \]
内容并不复杂，但单看内容还是太生硬了，还是有个证明比较舒服
先证明解是正确的 \[ 已知x≡\sum\limits_{i=1}^{k}r_iM_iy_i\quad(mod\space M)，且x∈[0,M-1]，求证x满足方程组\newline \left\{ \begin{aligned} &x≡r_{1}\quad(mod\space m_{1})\newline &x≡r_{2}\quad(mod\space m_{2})\newline &x≡r_{3}\quad(mod\space m_{3})\newline &...\newline &x≡r_{k}\quad(mod\space m_{k}) \end{aligned} \right.\newline、 \] 证明： \[ 记x=r_1M_1y_1+r_2M_2y_2+...+r_kM_ky_k+jM，其中j∈Z\newline 先看特例\quad x≡r_{1}\quad(mod\space m_{1})\newline 我们知道\quad M=\prod\limits_{i=1}^{k}{m_i}\quad，\quad M_i=\frac{M}{m_i}=\frac{\prod\limits_{n=1}^{k}{m_n}}{m_i}\newline 所以除了M_1,剩下的M_2,M_3...M_k和M都含有因数m_1\newline 所以x≡\sum\limits_{i=1}^{k}(r_iM_iy_i)+jM≡r_1M_1y_1\quad(mod\space m_1)\newline 现在只需要证r_1M_1y_1≡r_1\quad(mod\space m_1)\newline 已知M_iy_i≡1\quad(mod\space m_i)\space⇨\space M_1y_1-1=fm_1\space⇨\space M_1y_1=fm_1+1\newline r_1M_1y_1=r_1(fm_1+1)=r_1fm_1+r_1\newline r_1fm_1显然是m_1的倍数，可以消去，剩下r_1，也就得到了\newline x≡\sum\limits_{i=1}^{k}(r_iM_iy_i)+jM≡r_1M_1y_1≡r_1\quad(mod\space m_1)\newline 即x≡r_1\quad(mod\space m_1)\newline \] 特例就如此出来了
当然还没完，我们想要的是通解
其实也很简单，因为在上面的过程中，我们并没有使用什么特殊的性质，基本只需要把1改成变量 \[ 记x=r_1M_1y_1+r_2M_2y_2+...+r_kM_ky_k+jM，其中j∈Z\newline 需证明\quad x≡r_{t}\quad(mod\space m_{t})对任意的t∈[1,k]\space\&\space t∈Z成立\newline 已知\quad M=\prod\limits_{i=1}^{k}{m_i}\quad，\quad M_t=\frac{M}{m_t}=\frac{\prod\limits_{i=1}^{k}{m_i}}{m_t}\newline 除了M_t,剩下的M_1,M_2,M_3...M_k和M都含有因数m_t\newline 所以x≡\sum\limits_{i=1}^{k}(r_iM_iy_i)+jM≡r_tM_ty_t\quad(mod\space m_t)\newline 现在只需要证r_tM_ty_t≡r_t\quad(mod\space m_t)\newline 已知M_ty_t≡1\quad(mod\space m_t)\space⇨\space M_ty_t-1=fm_t\space⇨\space M_ty_t=fm_t+1\newline r_tM_ty_t=r_t(fm_t+1)=r_tfm_t+r_t\newline r_tfm_t显然是m_t的倍数，可以消去，剩下r_t，也就得到了\newline x≡\sum\limits_{i=1}^{k}(r_iM_iy_i)+jM≡r_tM_ty_t≡r_t\quad(mod\space m_t)\newline 即x≡r_t\quad(mod\space m_t)对于任意t∈[1,k]成立\newline \] 如此，我们就证明了这个解是正确的
接下来我们证明这个解在[0,M-1]内是唯一的
唯一证明这种事交给反证法比较好做，因为正着来基本看不出方法，但反过来否定它就比较容易找到逻辑漏洞从而证伪 \[ 已知方程组\newline \left\{ \begin{aligned} &x≡r_{1}\quad(mod\space m_{1})\newline &x≡r_{2}\quad(mod\space m_{2})\newline &x≡r_{3}\quad(mod\space m_{3})\newline &...\newline &x≡r_{k}\quad(mod\space m_{k}) \end{aligned} \right.\newline 证明这个方程组在[0,M-1]内的解唯一 \] 证明： \[ 假设这个方程组有多个解x_1,x_2..x_n∈[0,M-1]，其中n∈[2,M](因为0到M-1一共有M个数)\newline 那么就有\newline \left\{ \begin{aligned} &x_1≡x_2≡...≡x_n\quad(mod\space m_{1})\newline &x_1≡x_2≡...≡x_n\quad(mod\space m_{2})\newline &x_1≡x_2≡...≡x_n\quad(mod\space m_{3})\newline &...\newline &x_1≡x_2≡...≡x_n\quad(mod\space m_{k}) \end{aligned} \right.\newline 任取两个整数i≠j∈[1,n]\newline 有x_i≡x_j\quad(mod\space m_{t})\quad(t是[1,k]内的任意整数) 即x_i-x_j是m_1，m_2，m_3...m_k的公倍数\newline 又因为数组m所有数两两互质\newline 所以m_1，m_2，m_3...m_k的公倍数一定是\prod\limits_{i=1}^{k}{m_i}=M的倍数\quad(后面会补充证明)\newline 所以x_i，x_j至少相差一个M\newline 但这与x_1,x_2..x_n∈[0,M-1]矛盾，即任意两个解相差不可能大于M-1\newline 所以这个解在[0,M-1]必定唯一 \]
2.欧几里得算法
这东西是个求最大公约数的技巧，它的内容就是 \[ gcd(a,b)=gcd(a,b\%a)\newline (默认a，b均大于等于0吧，我不太会讨论负数证明)\newline 求两数的最大公约数可以用求余来缩小数字 \]
在证明这个等式之前，我们先证另一个东西 \[ 若a≥0,b≥0,k∈Z且b+ka≥0\newline 则(a,b)和(a,b+ka)一定拥有相同的公因数\newline (前提：问(0,0)的公因数没有意义，故默认排除\newline a≠0，问(a,0)的公因数和问a的因数等价，因为任何数都是0的因数) \] 这个并不复杂，顺着题目来就行
证明 \[ 设表示a和b所有的公因数组成集合A，a和b+ka所有的公因数组成集合B\newline 我们要证明A和B等价\newline 那就来证A的元素一定在B里面，同时B的元素一定在A里面\newline 取∀p∈A,q∈B\newline 现证明p∈B\newline 有a≡0\quad(mod\space p)⇨ka≡0\quad(mod\space p)（同余两侧可以同乘非正数），又b≡0\quad(mod\space p)\newline 所以b+ka≡0\quad(mod\space p)\newline 即p同时是a和b+ka的因数，即a和b+ka的公因数，得p∈B\newline \newline 现证明q∈A\newline 其实套用上面就好\newline p∈B说明(a,b)的公因数一定是(a,b+ka)的公因数\newline 那么(a,b+ka)的公因数一定是(a,(b+ka)+(-ka)=b)的公因数\newline 即q∈A\newline 由此，命题得证 \] 接下来再进一步，我们证明 \[ 若a≥0,b≥0,k∈Z且b+ka≥0\newline 则gcd(a,b)=gcd(a,b+ka)\newline (同样的，问gcd(0,0)没有意义,gcd(a,0)是a自身) \] 证明: \[ 因为gcd(a,b)是a和b+ka的公因数⇨gcd(a,b)≤gcd(a,b+ka)\newline 因为gcd(a,b+ka)是a和b的公因数⇨gcd(a,b+ka)≤gcd(a,b)\newline 所以只能有gcd(a,b)=gcd(a,b+ka)\newline 命题得证 \] 这么做完，欧几里得算法更是显然，因为b%a一定能写成b+ka的形式，用求余只是为了让数字缩小得最快
这部分我是改来改去，因为在证欧几里得算法的过程中发现欧几里得算法是狭义的结果，我们可以直接由大推小
3.扩展欧几里得算法
在说明这个之前，我们要先提一个东西——贝祖等式 \[ ax+by=gcd(a,b)\newline 对于任意两个整数a，b，一定存在一组整数x，y使等式成立 \] 但一样的，我不想讨论负数，所以默认a，b≥0
这个等式看起来挺难让人相信的，但数学的证明经常就是用严谨的逻辑推翻人的直觉。。。
\[ 待证等式是对称等式，不妨令a≤b\newline 利用欧几里得算法求gcd(a,b)的方式就是反复求余，直到其中一项为0\newline 那么第一步先证明反复求余最终会有一个0 \] 证明： \[ 有0≤r_2≤r_1且r_1，r_2不同时为0\newline 当r_2=r_1时显然求余会得0\newline 当r_2<r_1时:\newline r_{n+1}=r_{n-1}\%r_{n}\quad(r_n≠0)\newline r_{n+1}=r_n\quad(r_n=0)\newline 所以当r_n≠0时r_{n+1}严格小于r_n\newline 即r在r_n=0前是递减数列，至多经过r_1项后，即r_{r_{1}+1}一定是0\newline 所以如此反复求余后一定会有0\newline \] 回过来看 \[ gcd(r_2,r_1)=gcd(r_3=r_1\%r_2,r_2)=gcd(r_4=r_2\%r_3,r_3)=gcd(r_5=r_3\%r_4,r_4)=...=gcd(r_{n+1}=r_{n-1}\%r_n,r_n)=...\newline =gcd(r_{k+1}=0,r_k>0)=r_k \] 将r2，r1视作贝祖等式里的a，b，那么gcd(a,b)=gcd(r2,r1)=rk，所以我们要找到一组整数x，y，能够满足r2x+r1y=rk
因为我们不可能一步步从r3算到rk，对于这种步数不确定的东西，我们可以使用归纳法
证明: \[ 仅讨论r_n>0的情况\newline 令r_n=p_nr_2+q_nr_1\quad(n≥3)\newline 现证明任意p_n,q_n(n≥3)均为整数\newline 显然的，r_3=r_1\%r_2可以写作r_3=p_3r_2+q_3r_1的形式，且p_3,q_3均为整数\newline 令整数m满足r_4=r_2\%r_3=r_2-mr_3=r_2-m(p_3r_2+q_3r_1)=(1-mp_3)r_2-mq_3r_1\newline =p_4r_2-q_4r_1\newline 显然p_4=(1-mp_3),q_4=mq_3均为整数\newline \newline r_{i-1}=p_{i-1}r_2+q_{i-1}r_1\newline r_{i}=p_{i}r_2+q_{i}r_1\newline 假设p_{i-1},q_{i-1},p_{i},q_{i}均为整数\newline r_{i+1}=r_{i-1}\%r_{i}=p_{i+1}r_{2}+q_{i+1}r_{1}\newline 现在要证明p_{i+1},q_{i+1}是整数\newline 整数k满足r_{i+1}=r_{i-1}\%r_{i}=r_i-kr_{i-1}=(p_{i}r_2+q_{i}r_1)-k(p_{i-1}r_2+q_{i-1}r_1)\newline =(p_i-kp_{i-1})r_2+(q_i-kq_{i-1})r_1\newline 显然p_{i+1}=(p_i-kp_{i-1})，q_{i+1}=(q_i-kq_{i-1})均为整数\newline 所以对任意r_n>0，r_n=p_nr_2+q_nr_1\quad(n≥3)\newline 都有p_n,q_n为整数 \] 自然就有 \[ ax+by=gcd(a,b)\newline 对于任意两个整数a，b，一定存在一组整数x，y使等式成立 \]
扩展欧几里得算法相对于欧几里得算法多了个计算其中的x，y，即贝祖系数的功能
剩余部分待补充
4.正解说明
1 | p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 |
其中 \[ dp=d\%(p-1)\newline dq=d\%(q-1) \] 解答：
\[ c^d=c^{k_1(p-1)+dp}=(c^{p-1})^{^{k_1}}c^{dp}\newline 一般情况下，c和p是互质的(不互质的概率太小，忽略)\newline 由费马小定理可以知道\newline c^{p-1}≡1\quad(mod\space p)⇨(c^{p-1})^{^{k_1}}≡1\quad(mod\space p)\newline ⇨(c^{p-1})^{^{k_1}}-1=k_2p⇨(c^{p-1})^{^{k_1}}=k_2p+1\newline 所以c^d=(c^{p-1})^{^{k_1}}c^{dp}=(k_2p+1)c^{dp}≡c^{dp}\quad(mod\space p)\newline 即c^d≡c^{dp}≡mp\quad(mod\space p) \] 同理有 \[ m≡c^d≡mp\quad(mod\space p)\newline m≡c^d≡mq\quad(mod\space q)\newline \] 接下来证明 \[ m = (((mp-mq)*I)\%p)*q+mq\newline \newline 中国剩余定理告诉我们\newline m≡mp\quad(mod\space p)\newline m≡mq\quad(mod\space q)\newline 同时满足这两个方程的m存在且唯一\newline 那我们只需要说明\newline (((mp-mq)I)\%p)*q+mq≡mp\quad(mod\space p)\newline (((mp-mq)I)\%p)*q+mq≡mq\quad(mod\space q)\newline \] . \[ 设x=kp+r\newline (x\quad mod\space p)y=ry\newline xy=(kp+r)y=kpy+ry\newline 所以有(x\quad mod\space p)y≡xy\quad(mod\space q)\newline \] . \[ 所以\newline (((mp-mq)I)\%p)*q+mq≡(mp-mq)Iq+mq\quad(mod\space p)\newline 我们知道Iq≡1\quad(mod\space p)⇨Iq-1=kp⇨Iq=kp+1\newline (mp-mq)Iq+mq=kp(mp-mq)+mp-mq+mq≡mp\quad(mod\space p) \] 后者就很显然 \[ (((mp-mq)I)\%p)*q+mq\newline (((mp-mq)I)\%p)*q含有因子q，所以\newline (((mp-mq)I)\%p)*q+mq≡mq\quad(mod\space q)\newline \] 如此就能说明m = (((mp-mq)*I)%p)*q+mq这步是正确的
只不过最后的数字需要utf-8解码
1 | m = (((mp-mq)*I)%p)*q+mq #求明文公式 |
说实话我还不知道这部要怎么联想
但不过把数字扔给ai应该它看的出来
5.瞎想
\[ m≡c^d≡mp\quad(mod\space p)\newline m≡c^d≡mq\quad(mod\space q)\newline \]
我既然已经知道这两个等式，为什么我不用中国剩余定理来解m？
说不准这个方式也是可行
如果也是正解的话那可能比原本搜到的答案更容易想到？
毕竟搜出来的解给我一种先射箭后画靶的感觉，根本想不到
1 | p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 |
跑了一下，可行