Sky's blog

浅谈RSA公钥非素数问题

字数统计: 914阅读时长: 4 min
2019/02/21 Share

前言

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

例题1

题干如下

1
2
3
4
5
6
e = 12
p = 58380004430307803367806996460773123603790305789098384488952056206615768274527
q = 81859526975720060649380098193671612801200505029127076539457680155487669622867
ciphertext = 206087215323690202467878926681944491769659156726458690815919286163630886447291570510196171585626143608988384615185921752409380788006476576337410136447460

算出的m转化成字符串

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

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

我们可以得到

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

1
libnum.invmod(e,phi_n)

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

1
ValueError: no invmod for given @a and @n

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

1
print libnum.gcd(e,phi_n)

发现结果为4,那么原因很明显,因为公钥和phi_n不互素
这里我们可以将公钥进行拆分

1
e = 12 = 3*4

我们可以知道

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

这样一来,我们可以求出4d,因为gcd(3,phi_n)=1
那么既然是4d,怎么解密呢?
我们知道

我们不妨将式1两边同时4次方,为验证两边依旧相等,我们做如下证明:
首先将同余式换成等式

同时4次方

我们知道右边多项式展开后,除了最后一项为c^4d以外,其余每项必然带着n
我们等式两边同时取余n,得到

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

1
2
3
4
5
6
7
8
9
10
11
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为

1
20106844800109502536288854016069119595196463634259079507316147175432925273818188038332257297004492492765022431372230373366290144995921

于是我们可以得到式子(结果太大,这里我做一个简略)

将同余式转换成等式得到

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

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

发现结果

1
(mpz(2117561251816846604440536517998717L), 1)

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

1
2117561251816846604440536517998717

我们转成string得到flag:

1
hgame{xxxxxxx}

例题2

题干如下

1
2
3
4
5
6
7
8
9
10
11
12
e1:0x33240

e2:0x3e4f

n:0x9439682bf1b4ab48c43c524778c579cc844b60872275725c1dc893b5bcb358b9f136e4dab2a06318bb0c80e202a14bc54ea334519bec023934e01e9378abf329893f3870979e9f2f2be8fff4df931216a77007a2509f49f697bf286285e97fac5dc6e4a164b5c2cc430887b18136437ba67777bda05aafdeaf918221c812b4c7d1665238f84ab0fab7a77fcae92a0596e58343be7a8e6e75a5017c63a67eb11964970659cd6110e9ec6502288e9e443d86229ef2364dfecb63e2d90993a75356854eb874797340eece1b19974e86bee07019610467d44ec595e04af02b574a97fa98bdb2e779871c804219cab715f4a80fef7f8fb52251d86077560b39c1c2a1

c1:0x7c7f315a3ebbe305c1ad8bd2f73b1bb8e300912b6b8ba1b331ac2419d3da5a9a605fd62915c11f8921c450525d2efda7d48f1e503041498f4f0676760b43c770ff2968bd942c7ef95e401dd7facbd4e5404a0ed3ad96ae505f87c4e12439a2da636f047d84b1256c0e363f63373732cbaf24bda22d931d001dcca124f5a19f9e28608ebd90161e728b782eb67deeba4cc81b6df4e7ee29a156f51a0e5148618c6e81c31a91036c982debd1897e6f3c1e5e248789c933a4bf30d0721a18ab8708d827858b77c1a020764550a7fe2ebd48b6848d9c4d211fd853b7a02a859fa0c72160675d832c94e0e43355363a2166b3d41b8137100c18841e34ff52786867d

c2:0xf3a8b9b739196ba270c8896bd3806e9907fca2592d28385ef24afadc2a408b7942214dad5b9e14808ab988fb15fbd93e725edcc0509ab0dd1656557019ae93c38031d2a7c84895ee3da1150eda04cd2815ee3debaa7c2651b62639f785f6cabf83f93bf3cce7778ab369631ea6145438c3cd4d93d6f2759be3cc187651a33b3cc4c3b477604477143c32dfff62461fdfd9f8aa879257489bbf977417ce0fbe89e3f2464475624aafef57dd9ea60339793c69b53ca71d745d626f45e6a7beb9fcbd9d1a259433d36139345b7bb4f392e78f1b5be0d2c56ad50767ee851fac670946356b3c05d0605bf243b89c7e683cc75030b71633632fb95c84075201352d6

c1=pow(m, e1, n)
c2=pow(m, e2, n)

我们有条件

本应利用

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

1
print libnum.gcd(e1,e2)

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

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

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

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

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

上下两式相乘,即可得到

又因为

所以可以得到

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

那么依旧是之前的操作,我们可以遍历k,找到刚好开3次方的k,此时开3次方即为M
这里也是比较简单,k=0的时候就成立了,无需遍历,脚本如下

1
2
3
4
5
6
7
8
9
10
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的变题基本都是可以解决的XD

点击赞赏二维码,您的支持将鼓励我继续创作!
CATALOG
  1. 1. 前言
  2. 2. 例题1
  3. 3. 例题2
  4. 4. 后记