浅谈RSA公钥非素数问题

前言

最近刷题，遇到2道公钥不互素的题目，这里简单记录一下解决方案，主要还是灵活掌握公式推导。

例题1

题干如下：

e = 12
p = 58380004430307803367806996460773123603790305789098384488952056206615768274527
q = 81859526975720060649380098193671612801200505029127076539457680155487669622867
ciphertext = 206087215323690202467878926681944491769659156726458690815919286163630886447291570510196171585626143608988384615185921752409380788006476576337410136447460

算出的m转化成字符串。

我们知道RSA的概述公式如下：

我们现在既然已知p,q，根据公式：

我们可以得到：

那么求e对于phi_n的逆元即可，我们可以使用：

libnum.invmod(e,phi_n)

那么问题来了，我们运行后却得到报错：

ValueError: no invmod for given @a and @n

这是为什么呢？我们测试一下：

print libnum.gcd(e,phi_n)

发现结果为4，那么原因很明显，因为公钥和phi_n不互素。

这里我们可以将公钥进行拆分。

e = 12 = 3*4

我们可以知道：

既然phi_n与3*4不互素，我们可以灵活的将4*d看成一个整体，得到：

这样一来，我们可以求出4d，因为gcd(3,phi_n)=1

那么既然是4d，怎么解密呢？

我们知道：

我们不妨将式1两边同时4次方，为验证两边依旧相等，我们做如下证明：

首先将同余式换成等式：

同时4次方：

我们知道右边多项式展开后，除了最后一项为c^4d以外，其余每项必然带着n。

我们等式两边同时取余n，得到：

这样一来我们可以构造出4d的解密形式，我们不妨进行计算：

import gmpy
import libnum
e = 12
p = 58380004430307803367806996460773123603790305789098384488952056206615768274527
q = 81859526975720060649380098193671612801200505029127076539457680155487669622867
n=p*q
c = 206087215323690202467878926681944491769659156726458690815919286163630886447291570510196171585626143608988384615185921752409380788006476576337410136447460
phi = (p-1)*(q-1)
d4 = libnum.invmod(3,phi)
m4 = pow(c,d4,n)
print m4

得到m^4为

20106844800109502536288854016069119595196463634259079507316147175432925273818188038332257297004492492765022431372230373366290144995921

于是我们可以得到式子（结果太大，这里我做一个简略）

将同余式转换成等式得到：

这里我们可以选择对k进行爆破，找到一个刚好可以开4次方的k，此时开4次方后结果即为m。

我们直接测试一下：

m = gmpy.root(m4,4)
print m

发现结果：

(mpz(2117561251816846604440536517998717L), 1)

发现刚好可以开4次方，于是可以得到结果：

2117561251816846604440536517998717

我们转成string得到flag:

hgame{xxxxxxx}

例题2

题干如下：

e1:0x33240
 
e2:0x3e4f
 
n:0x9439682bf1b4ab48c43c524778c579cc844b60872275725c1dc893b5bcb358b9f136e4dab2a06318bb0c80e202a14bc54ea334519bec023934e01e9378abf329893f3870979e9f2f2be8fff4df931216a77007a2509f49f697bf286285e97fac5dc6e4a164b5c2cc430887b18136437ba67777bda05aafdeaf918221c812b4c7d1665238f84ab0fab7a77fcae92a0596e58343be7a8e6e75a5017c63a67eb11964970659cd6110e9ec6502288e9e443d86229ef2364dfecb63e2d90993a75356854eb874797340eece1b19974e86bee07019610467d44ec595e04af02b574a97fa98bdb2e779871c804219cab715f4a80fef7f8fb52251d86077560b39c1c2a1
 
c1:0x7c7f315a3ebbe305c1ad8bd2f73b1bb8e300912b6b8ba1b331ac2419d3da5a9a605fd62915c11f8921c450525d2efda7d48f1e503041498f4f0676760b43c770ff2968bd942c7ef95e401dd7facbd4e5404a0ed3ad96ae505f87c4e12439a2da636f047d84b1256c0e363f63373732cbaf24bda22d931d001dcca124f5a19f9e28608ebd90161e728b782eb67deeba4cc81b6df4e7ee29a156f51a0e5148618c6e81c31a91036c982debd1897e6f3c1e5e248789c933a4bf30d0721a18ab8708d827858b77c1a020764550a7fe2ebd48b6848d9c4d211fd853b7a02a859fa0c72160675d832c94e0e43355363a2166b3d41b8137100c18841e34ff52786867d
 
c2:0xf3a8b9b739196ba270c8896bd3806e9907fca2592d28385ef24afadc2a408b7942214dad5b9e14808ab988fb15fbd93e725edcc0509ab0dd1656557019ae93c38031d2a7c84895ee3da1150eda04cd2815ee3debaa7c2651b62639f785f6cabf83f93bf3cce7778ab369631ea6145438c3cd4d93d6f2759be3cc187651a33b3cc4c3b477604477143c32dfff62461fdfd9f8aa879257489bbf977417ce0fbe89e3f2464475624aafef57dd9ea60339793c69b53ca71d745d626f45e6a7beb9fcbd9d1a259433d36139345b7bb4f392e78f1b5be0d2c56ad50767ee851fac670946356b3c05d0605bf243b89c7e683cc75030b71633632fb95c84075201352d6
 
c1=pow(m, e1, n)
c2=pow(m, e2, n)

我们有条件：

本应利用：

但这里e_1和e_2不互素，所以我们有：

print libnum.gcd(e1,e2)

得到结果为3，所以得到如下等式：

我们可以将之前同余式化为如下形式：

然后式子1两边同时进行s1次方，式子2进行s2次方，得到：

右边的高次展开式中，除了最后一项：

一定每一项都含有n，所以同时取余n的时候，只剩下最后一项：

上下两式相乘，即可得到：

又因为：

所以可以得到：

那么依旧回到之前的问题，我们有：

那么依旧是之前的操作，我们可以遍历k，找到刚好开3次方的k，此时开3次方即为M。

这里也是比较简单，k=0的时候就成立了，无需遍历，脚本如下：

s1, s2, tmp = libnum.xgcd(e1, e2)
if s1 < 0:
    s1 = - s1
    c1 = gmpy2.invert(c1, n)
elif s2 < 0:
    s2 = - s2
    c2 = gmpy2.invert(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
m = 211655262573966881062823795220179644607412162371069
print gmpy.root(m,3)[0]

后记

写这篇文章不仅限于分享，只要能熟练推导RSA基础公式，不硬套脚本，一些RSA的变题基本都是可以解决的。