浅谈RSA公钥非素数问题

crypto

字数统计: 914阅读时长: 4 min

 2019/02/21  Share

前言

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

例题1

题干如下

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

算出的m转化成字符串

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

$c \equiv m^{e} \text{ } mod \text{ } n \\ m \equiv c^{d} \text{ } mod \text{ } n \\ \phi (n) = (p-1)*(q-1) \\ d*e \equiv 1 \text{ } mod \text{ } \phi (n)$

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

$d*e \equiv 1 \text{ } mod \text{ } \phi (n)$

我们可以得到

$d \equiv e^{-1} \text{ } mod \text{ } \phi (n)$

那么求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

我们可以知道

$d*3*4 \equiv 1 \text{ } mod \text{ } \phi (n)$

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

$d*4 \equiv 3^{-1} \text{ } mod \text{ } \phi (n)$

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

$m \equiv c^{d} \text{ } mod \text{ } n \\ d*4 \equiv 3^{-1} \text{ } mod \text{ } \phi (n)$

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

$m = k*n + c^{d}$

同时4次方

$m^4 = (k*n+c^d)^4$

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

$m^4 \equiv c^{4d} \text{ } mod \text{ } 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为

1	20106844800109502536288854016069119595196463634259079507316147175432925273818188038332257297004492492765022431372230373366290144995921

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

$m^4 \equiv 2010684... mod \text{ } n$

将同余式转换成等式得到

$m^4 = k*n + 2010684...$

这里我们可以选择对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

题干如下

e1:0x33240

e2:0x3e4f

n:0x9439682bf1b4ab48c43c524778c579cc844b60872275725c1dc893b5bcb358b9f136e4dab2a06318bb0c80e202a14bc54ea334519bec023934e01e9378abf329893f3870979e9f2f2be8fff4df931216a77007a2509f49f697bf286285e97fac5dc6e4a164b5c2cc430887b18136437ba67777bda05aafdeaf918221c812b4c7d1665238f84ab0fab7a77fcae92a0596e58343be7a8e6e75a5017c63a67eb11964970659cd6110e9ec6502288e9e443d86229ef2364dfecb63e2d90993a75356854eb874797340eece1b19974e86bee07019610467d44ec595e04af02b574a97fa98bdb2e779871c804219cab715f4a80fef7f8fb52251d86077560b39c1c2a1

c1:0x7c7f315a3ebbe305c1ad8bd2f73b1bb8e300912b6b8ba1b331ac2419d3da5a9a605fd62915c11f8921c450525d2efda7d48f1e503041498f4f0676760b43c770ff2968bd942c7ef95e401dd7facbd4e5404a0ed3ad96ae505f87c4e12439a2da636f047d84b1256c0e363f63373732cbaf24bda22d931d001dcca124f5a19f9e28608ebd90161e728b782eb67deeba4cc81b6df4e7ee29a156f51a0e5148618c6e81c31a91036c982debd1897e6f3c1e5e248789c933a4bf30d0721a18ab8708d827858b77c1a020764550a7fe2ebd48b6848d9c4d211fd853b7a02a859fa0c72160675d832c94e0e43355363a2166b3d41b8137100c18841e34ff52786867d

c2:0xf3a8b9b739196ba270c8896bd3806e9907fca2592d28385ef24afadc2a408b7942214dad5b9e14808ab988fb15fbd93e725edcc0509ab0dd1656557019ae93c38031d2a7c84895ee3da1150eda04cd2815ee3debaa7c2651b62639f785f6cabf83f93bf3cce7778ab369631ea6145438c3cd4d93d6f2759be3cc187651a33b3cc4c3b477604477143c32dfff62461fdfd9f8aa879257489bbf977417ce0fbe89e3f2464475624aafef57dd9ea60339793c69b53ca71d745d626f45e6a7beb9fcbd9d1a259433d36139345b7bb4f392e78f1b5be0d2c56ad50767ee851fac670946356b3c05d0605bf243b89c7e683cc75030b71633632fb95c84075201352d6

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

我们有条件

$C_1 \equiv M^{e_1} \text{ } mod \text{ } n \\ C_2 \equiv M^{e_2} \text{ } mod \text{ } n \\$

本应利用

$gcd(e_1,e_2)=1 \\ s_1e_1+s_2e_2 = 1$

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

1	print libnum.gcd(e1,e2)

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

$gcd(e_1,e_2)=3 \\ s_1e_1+s_2e_2 = 3$

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

$C_1 = k_1n+M^{e_1} \\ C_2 = k_2n+M^{e_2} \\$

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

$C_1^{s_1} = (k_1n+M^{e_1})^{s_1} \\ C_2^{s_2} = (k_2n+M^{e_2})^{s_2} \\$

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

$M^{e_1s_1} \\ M^{e_2s_2}$

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

$C_1^{s_1} \equiv M^{e_1s_1} \text{ } mod \text{ } n \\ C_2^{s_2} \equiv M^{e_2s_2} \text{ } mod \text{ } n \\$

上下两式相乘，即可得到

$C_1^{s_1}C_2^{s_2} \equiv M^{e_1s_1+e_2s_2} \text{ } mod \text{ } n \\$

又因为

$s_1e_1+s_2e_2 = 3$

所以可以得到

$C_1^{s_1}C_2^{s_2} \equiv M^3 \text{ } mod \text{ } n \\$

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

$k*n + C_1^{s_1}C_2^{s_2} = M^3$

那么依旧是之前的操作，我们可以遍历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的变题基本都是可以解决的XD

点击赞赏二维码，您的支持将鼓励我继续创作！

Next Post

2019 安恒杯 2月月赛 Writeup
Previous Post

2019 Hgame Week4 Crypto&Sign_in_SemiHard

CATALOG

1. 前言
2. 例题1
3. 例题2
4. 后记



缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true