【密码技术】RSA算法总结（数学知识/CTF题型）

admin
admin
admin
102360
文章
87
评论
2023年7月24日08:22:47评论53 views字数 81154阅读270分30秒阅读模式

一.RSA简介

简要概括就两句话：公钥（e）加密，私钥（d）解密。

【密码技术】RSA算法总结（数学知识/CTF题型）

二.RSA过程

【密码技术】RSA算法总结（数学知识/CTF题型）

三.RSA各参数

p 和 q：两个大的质数，是另一个参数N的的两个因子。

N/n：大整数，可以称之为模数。

e 和 d：公钥和私钥，互为无反数的两个指数。

(N, e)：公钥对，有N

(N, d)：私钥对，也有N

c 和 m：密文和明文。

pow(x, y, z)：效果等效pow(x, y)1 % z， 先计算x的y次方，如果存在另一个参数z，需要再对结果进行取模。

密钥长度：n以二进制表示的的位数，例如密钥长度为512代表n用二进制表示的长度为512bit。

对于RSA加密算法，公钥(N, e)为公钥，可以任意公开，破解RSA最直接（亦或是暴力）的方法就是分解整数N，然后计算欧拉函数φ(n)=(p-1) * (q-1),再通过d * e ≡ 1 mod φ(N)，即可计算出 d，然后就可以使用私钥(N, d)通过m = pow(c,d,N)解密明文。

四.数学知识

  1. 质数与互质数：

一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为质数（素数）；否则称为合数。例如，15＝3×5，所以15不是素数，13除了等于13×1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。1不是质数，也不是合数公约数只有1的两个数，叫做互质数。

2.同余定理：

“≡”是数论中表示同余的符号。同余的定义如下：给定一个正整数m，如果两个整数a和b满足a - b能被m整除，即(a - b) mod m = 0，那么就称整数a与b对模m同余，记作a ≡ b ( mod m)，同时可成立a mod m = b。注意，同余与模运算是不同的。显然,有如下事实：（1）若a≡0(mod m)，则m|a；（2）a≡b(mod m)等价于a与b分别用m去除，余数相同。

3.欧拉函数：

任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方法就叫做欧拉函数，以φ(n)表示.例如：在1到8之中，与8形成互质关系的是1、3、5、7，所以φ(n)=φ(8)=4。φ(n)=(p-1)(q-1)由来：例如：和15互质的为1,2,4,7,8,11,13,14,将15分解成3,5且两者互质，故φ(n)=φ(15)=φ(3) * φ(5)=(3-1)* (5-1)=8

【密码技术】RSA算法总结（数学知识/CTF题型）

4.欧拉定理：

如果两个正整数a和n两者互质，则n的欧拉函数φ(n)也可以下面的等式也成立：a^φ(n)≡1(mod n)。也就是说，a的φ(n)次方被n除的余数为1。这就是φ(n)与公钥e互质的原因。

5.模反元素：

根据欧拉定理，有：
a^φ(n) = a × a^(φ(n)−1)≡1(mod n)

令b=a^(φ(n)−1)，得：a×b≡1(mod n)

b就是a的模反元素 所以，如果两个正整数a和n互质，那么一定可以找到整数b使得ab-1被n整除，或者说ab被n除的余数是1。私钥d与公钥e的乘积d*e 减去1可以被φ(n)整除，或者说ed乘积除以φ(n)的余数为1。或者说de乘积与1对模φ(n)同余，这就是私钥的d加密原理。

【密码技术】RSA算法总结（数学知识/CTF题型）

PS：利用两者乘积求n或由n反推p与q，通常n往往是一个 1024bit 的超大数，很难分解为两个质数。

脚本（n+e+c+p+q=m脚本）

#!/usr/bin/env python3# -*- coding: utf-8 -*-
import libnumfrom Crypto.Util.number import long_to_bytes
def rsa_decrypt(ciphertext, n, e, p, q):    d = libnum.invmod(e, (p - 1) * (q - 1))    decrypted_data = pow(ciphertext, d, n)    return decrypted_data
if __name__ == "__main__":    c = 0x6cd55a2bbb49dfd2831e34b76cb5bdfad34418a4be96180b618581e9b6319f86  # c：密文    n = 108539847268573990275234024354672437246525085076605516960320005722741589898641    e = 65537    q = 333360321402603178263879595968004169219    p = 325593180411801742356727264127253758939
    # 解密密文，得到明文数值m    m = rsa_decrypt(c, n, e, p, q)
    # 将明文数值m转换为字节串，即字符串    string = long_to_bytes(m)
    print("解密后的明文为:", string.decode('utf-8'))

五.题型/常识等

  1. 最简单情况是知道p、q和公钥e，求出私钥d。

脚本如下：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2
def calculate_private_key(p, q, e):    phi_n = (p - 1) * (q - 1)    d = gmpy2.invert(e, phi_n)    return d
if __name__ == "__main__":    p = gmpy2.mpz(18443)  # 初始化大整数p    q = gmpy2.mpz(49891)  # 初始化大整数q    e = gmpy2.mpz(19)     # 初始化大整数e
    # 计算私钥d    d = calculate_private_key(p, q, e)
    print("p = %s, q = %s, e = %s" % (p, q, e))    print("私钥d =n%s" % d)

2.n较小时（256bit）可以rsatool或kali上yafu解密。

在线分解大素数：

http://www.factordb.com/index.php

3.n较大时（大于768bit）只能爆破或利用在线网站， 这一类在线网站的原理是储存了部分n分解成功的的值。

4.由p,q,dp,dq,c求明文m的算法,其中涉及的数学知识：参考另一篇博客。

5.已知密文文件（flag.enc/cipher.bin/flag.b64）和公钥文件（pubkey.pem/key.pem/key.pub）求解明文 m：

1）利用rsatools工具：

语法：

python RsaCtfTool.py --publickey key.pem --uncipherfile cipher.bin

2）

【密码技术】RSA算法总结（数学知识/CTF题型）

6.已知c ，e，n（非常大），和 dp，dq，求解明文m（领航杯2019的一道题：EasyRSA或2019山东省赛“深思杯”中 被加密的消息 一题，两者类似。）：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2from Crypto.Util.number import long_to_bytes
def rsa_decrypt(ciphertext, n, e, dp):    for i in range(1, 65538):        if (dp * e - 1) % i == 0:            if n % (((dp * e - 1) // i) + 1) == 0:                p = (((dp * e - 1) // i) + 1)                q = n // (((dp * e - 1) // i) + 1)                phi = (p - 1) * (q - 1)                d = gmpy2.invert(e, phi) % phi                return long_to_bytes(pow(ciphertext, d, n))
if __name__ == "__main__":    e = 65537    n = 16969752165509132627630266968748854330340701692125427619559836488350298234735571480353078614975580378467355952333755313935516513773552163392952656321490268452556604858966899956242107008410558657924344295651939297328007932245741660910510032969527598266270511004857674534802203387399678231880894252328431133224653544948661283777645985028207609526654816645155558915197745062569124587412378716049814040670665079480055644873470756602993387261939566958806296599782943460141582045150971031211218617091283284118573714029266331227327398724265170352646794068702789645980810005549376399535110820052472419846801809110186557162127    dp = 1781625775291028870269685257521108090329543012728705467782546913951537642623621769246441122189948671374990946405164459867410646825591310622618379116284293794090970292165263334749393009999335413089903796624326168039618287078192646490488534062803960418790874890435529393047389228718835244370645215187358081805    c = 0x6c78dcee37830f3ec4ab4989d40fbb595060b3fbc395d52ad26defc13372c1a3948c5388f4e450e46e016c7803133d6881e5efc3b90a4789448097c94124590b1e7949f2524d7edccd61a27691c18d090ac1f54643b563141306045417581e3b263f4ad2816136a48b106f3058b08e2a810f4ae8ef25916cc110b41ac8158ce69ecbe20fc60c1ddb20154c6646bc5142aefe47abf053a8ac949d5bc057bb18b191ad08070fe9ec5d76b1fceae685514532448c1b388b2d38e7241ac19c296e95e4e021a3a4015d909a1d53a2eb7fa86f6329f4e6c937f958be576c58fab4d9c9126999c99bb28718efc41a6f5db52b47942a2ddf21639f020b5489699cf22b46
    # 解密密文，得到明文    decrypted_message = rsa_decrypt(c, n, e, dp)    print("解密后的明文为:", decrypted_message.decode('utf-8'))

7.公共模数攻击：【BUUCTF :RSA3】
适用于：使用相同的模数 N 、不同的私钥，加密同一明文消息。

【密码技术】RSA算法总结（数学知识/CTF题型）

【密码技术】RSA算法总结（数学知识/CTF题型）

exp：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
from gmpy2 import invert
# 欧几里得算法def egcd(a, b):    if a == 0:        return (b, 0, 1)    else:        g, y, x = egcd(b % a, a)        return (g, x - (b // a) * y, y)
def mpz_to_str(m):    hex_str = hex(m)[2:]    if len(hex_str) % 2 != 0:        hex_str = "0" + hex_str    return bytes.fromhex(hex_str).decode("utf-8")
def main():    n = 22708078815885011462462049064339185898712439277226831073457888403129378547350292420267016551819052430779004755846649044001024141485283286483130702616057274698473611149508798869706347501931583117632710700787228016480127677393649929530416598686027354216422565934459015161927613607902831542857977859612596282353679327773303727004407262197231586324599181983572622404590354084541788062262164510140605868122410388090174420147752408554129789760902300898046273909007852818474030770699647647363015102118956737673941354217692696044969695308506436573142565573487583507037356944848039864382339216266670673567488871508925311154801    c1 = 22322035275663237041646893770451933509324701913484303338076210603542612758956262869640822486470121149424485571361007421293675516338822195280313794991136048140918842471219840263536338886250492682739436410013436651161720725855484866690084788721349555662019879081501113222996123305533009325964377798892703161521852805956811219563883312896330156298621674684353919547558127920925706842808914762199011054955816534977675267395009575347820387073483928425066536361482774892370969520740304287456555508933372782327506569010772537497541764311429052216291198932092617792645253901478910801592878203564861118912045464959832566051361    c2 = 18702010045187015556548691642394982835669262147230212731309938675226458555210425972429418449273410535387985931036711854265623905066805665751803269106880746769003478900791099590239513925449748814075904017471585572848473556490565450062664706449128415834787961947266259789785962922238701134079720414228414066193071495304612341052987455615930023536823801499269773357186087452747500840640419365011554421183037505653461286732740983702740822671148045619497667184586123657285604061875653909567822328914065337797733444640351518775487649819978262363617265797982843179630888729407238496650987720428708217115257989007867331698397    e1 = 11187289    e2 = 9647291    s = egcd(e1, e2)    s1 = s[1]    s2 = s[2]    # 求模反元素    if s1 < 0:        s1 = -s1        c1 = invert(c1, n)    elif s2 < 0:        s2 = -s2        c2 = invert(c2, n)
    m = pow(c1, s1, n) * pow(c2, s2, n) % n    decrypted_message = mpz_to_str(m)    print("Decrypted message:", decrypted_message)
if __name__ == '__main__':    main()

8.已知n（非常大）,e,d求p,q（无法直接 从n分解）：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
import randomimport hashlib
def gcd(a, b):    if a < b:        a, b = b, a    while b != 0:        temp = a % b        a = b        b = temp    return a
def get_pq(n, e, d):    p = 1    q = 1    while p == 1 and q == 1:        k = d * e - 1        g = random.randint(0, n)        while p == 1 and q == 1 and k % 2 == 0:            k //= 2            y = pow(g, k, n)            if y != 1 and gcd(y - 1, n) > 1:                p = gcd(y - 1, n)                q = n // p    return p, q
def main():    n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309    e = 65537    d = 94599283799736674301380685280594381390923686253390792532895605779853044350622131213982318758322648944583146295754555534857526856437432666546308299574420087752597763115856540148581653417575472841120618851580068814757405535328265762608394303439607385208223679755286443291726688776962087410076483700455205352980401616754077792393004666816154938926922655422902554086735338530116621349538694326325540082353408648033776103524381462645247707103452734397241070801901829182855474261665618037166440894140783894750721033154326381975781861065766267288690203662140774551945549307205760153585431611115683    p, q = get_pq(n, e, d)    print("p =", p)    print("q =", q)    flag = "flag{" + hashlib.md5(str(p + q).encode('utf-8')).hexdigest() + "}"    print("Flag:", flag)
if __name__ == '__main__':    main()

9.利用公约数：

【密码技术】RSA算法总结（数学知识/CTF题型）

【密码技术】RSA算法总结（数学知识/CTF题型）

10.Roll按行加密（加密是按行进行的）：

题目是这样的：

{920139713,19}70479679275221115227470416418414022368270835483295235263072905459788476483295235459788476663551792475206804459788476428313374475206804459788476425392137704796792458265677341524652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476

完全考猜测猜到n=920139713，e=19，以下每一列组成密文c。
思路是：分解n，得p,q 根据p,q 获得欧拉数，根据欧拉数 获得 d，根据d 获得m
参考write-up。

六、攻击方式

1.其实破解rsa最直接方法就是分解模数N得q、p，基本只适用于N较小的时候，不过为保证安全性大部分时候都很难解出来，参考：

【密码技术】RSA算法总结（数学知识/CTF题型）

2.RSA低加密指数e攻击（e很小或很大）：最好参考这篇博客。

【密码技术】RSA算法总结（数学知识/CTF题型）

【密码技术】RSA算法总结（数学知识/CTF题型）

1）e=2：把密文c开平方求解
因为c≡m^e(mod n)，所以相当于将明文m平方后得到的密文c，开根号即可。

【密码技术】RSA算法总结（数学知识/CTF题型）

2）小明文攻击，例题：

【密码技术】RSA算法总结（数学知识/CTF题型）

3）低指数攻击大多数出现在e很大的时候：

可以直接github用工具：

https://github.com/pablocelayes/rsa-wiener-attack

3.yafu工具使用：
不能直接分解n，不能使用公约数分解n，可以尝试yafu。

在p，q的取值差异过大，或者p，q的取值过于相近的时候，Format方法与Pollard rho方法都可以很快将n分解成功。此类分解方法有一个开源项目yafu将其自动化实现了，不论n的大小，只要p和q存在相差过大或者过近时，都可以通过yafu很快地分解成功。

【密码技术】RSA算法总结（数学知识/CTF题型）

4.模不互素（存在两个或更多模数 n 且N1和N2不互质）：

适用情况：存在两个或更多模数 ，且gcd(N1,N2)!=1 也就是N1和N2不互质。

适用于，n超级大，用 yafu 的factor分解不了 的情况。

5.低加密指数广播攻击（模数n、密文c不同，明文m、加密指数e相同）

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。

适用范围:模数n、密文c不同，明文m、加密指数e相同。

一般的话e=k ，k是题目给出的n和c的组数。

【密码技术】RSA算法总结（数学知识/CTF题型）

例题：Jarvis OJ -2018强网杯nextrsa-Level9

exp：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2import hashlibfrom functools import reduce
def CRT(items):    N = reduce(lambda x, y: x * y, [i[1] for i in items])    result = 0    for a, n in items:        m = N // n        d, _, s = gmpy2.gcdext(n, m)        result += a * s * m    return result % N, N
def main():    e = 3    n1 = 8564529398597496052509875513481234511905571293608253591774352345237876733293108831203723008958367224489489969614656703455962549261315442327443089652074571708651505447379309166100331065440172781968875497386410667715026180057913363208450111095566219238303387888025161407043477291378931412269049849744457547932264137377411127192940332805452317547219248055802197050456726624516860024108642571703812719370387292166670300197241575461417648592309869669813372010765766544607691011957968652581504886331252936146901456910589102484807039294566703917033093028140452849747910537865958098720693569821256189593894121111357731919189    n2 = 12222166297277342805260668042066733749258843622057497574551492680820573970618063356710810891221670366396148862070530068431772630271300064517141331380959413811482890080103511756363920299387620181525172247384085449944650678616398890947062703879307721506228672839270493453501648644787019360131991056158375296484870723717496184332078521221915234959627683952251865227849249752415242124235776428944052873501045127442031423538183282845800971359590735184850648986263721823804859410866927117413289461014754456802566932965710529063515405296476007642849800772934170961993925017146017197762805148533435040675962332469643915192423    n3 = 5057224034499776793532654516178914954537547410664409403680432108569079856741764362023185604595829263918927121465578691201904227912897025244771553860102714429349163283510695391193774853323951653123109509215361937850724934183826508070404239791710229214063382081391564954935544392514769166830815475459218792639383796711824752291158895292103354274632470559179266550681095452239666165213986993496109747058314685303485222302144835490056402939133225003233112131275635419321982899965442010765766544607691011957968652581504886331252936146901456910589102484807039294566703917033093028140452849747910537865958098720693569821256189593894121111357731919189
    c = [        20010971557789931948130798983030201950038450269144104532821030667924400788869920238579729514672630221804096063149106742412869966814701225466606392171030411339119559280790040322081104363393453503417465768386174002015870794567148694722215873094298859132439253412531445187990845476275251348800166731481176155530755581153710085966976765505591809596417849783597055650440598035159288091495453205698044687869932756053447012994409598155552263807571713982758132066319612777306466708222135510918174055647735727504029507503430288609410745159037684948343055275573269067165460711584845480188706531450367147105629493736100726092945,        19200052919818196558567528701224082155105852846109782021681848107226495293687021416871117444987923837810238872836818190457667509409714021669160815809413653880491792640346474248859559867743715715552372738909255050196638006472279364316678941257894898953088366861786500472095752890593521428325838148184891778283229870316694059734109045397448347320487605412988229047015174998893589731503114337273121463601984792339337970193596813660178636222764332155999993506914518600565394196792457144962180040786607335687020278442899146954126853580244264273526509238060494624980807993322975135366653181977147866567146492356137019414255,        1394721540127922627584993749596603212491913755865039994631041458882716953251760080638497574652888386411767951258467542002582418260315909190241131591474627765734174146981015346732559115044918706641616288474447294129332475081232268241201488455865700933615291016346552048997127415783072860387265063527874160016186183078384940312292521628077750464413013768765371508493304331719166196330883242895556903378707199640686499970367957552543041110199009425369612644492288765891769004579050802446992426813215932250347386859783813875543314196764160792696291742850356532493945652482643696238487389412404616537620013009141601852080    ]
    data = list(zip(c, [n1, n2, n3]))    x, n = CRT(data)    m = gmpy2.iroot(x, e)[0]    flag = "flag{" + hashlib.md5(str(m).encode('utf-8')).hexdigest() + "}"    print("Flag:", flag)
if __name__ == '__main__':    main()

七.题型总结（待积累补充）：

各题型解析，exp参考的：https://blog.csdn.net/huanghelouzi/article/details/82943615

  • 已知p、q、e求解d

  • 已知p、q、e、c求解明文

  • 已知c、n、e求解明文

  • 已知c、e，求解明文

  • 求解d

————————————————

版权声明：本文为CSDN博主「暮w光」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/qi_SJQ_/article/details/121299078

[CTF密码学]RSA相关题目解题方法与python脚本总结（附例题）

RSA作为一种非常经典的非对称公开密钥加密体制，属于是CTF密码学题目中的常客。对刚接触密码学的新手来说，一上来看到各种几百上千位的数字难免感到头大，但实际上了解了RSA的原理和常见解题技巧后也没有那么复杂，常规的RSA题目我觉得算是密码学中比较好拿分的部分了。下面就来介绍一下RSA相关算法原理和各种各样的解题思路。

以下文章内容不会涉及到很多数学相关知识或算法具体原理，仅以最直白简略的语言来阐述解基本题目的方法思路，要想进一步加深对RSA密码体制的理解还请自行翻阅相关资料。

RSA算法概述

RSA是一种非对称加密体制 ，所谓非对称就是加密钥和解密钥不一样，要解决加解密相关问题，我们首先要弄清楚RSA加密解密流程中用到了哪些东西：

明文  m：就是待加密的文本啦，一般也就是我们的flag。

密文 C：加密完成后的密文，一般题目会给你，我们要做的就是根据密文解密出明文。

公钥 e（加密钥）：用来加密的密钥，是一个整数，是公开的。

两个大素数 p,q：RSA加密的关键部分，一般不会告诉你。我们选取两个大素数并计算它们的乘积，得到n=p*q。后面会用p,q,n来加密解密。由于p,q非常大，想要对n进行因式分解得到p，q非常困难，这也确保了RSA的安全性。

私钥 d（解密钥）：用来解密，一般不会告诉你，d满足e*d mod (p-1)(q-1)=1，所以我们只要知道e和p,q就可以把d算出来。

加密过程：

解密过程：

 以上就是一个常规RSA算法的组成部分。通过上面的内容我们可以知道要想解密一段密文，我们需要c,d,n三个值。其中c我们是知道的，而n和d都可以通过p,q,e算出来，e我们一般也是知道的，也就是说常规的rsa题目我们的解题思路就是想想怎样把p和q求出来。并以此进行解密。

思路一、分解n得到p,q

适用情况：n已知且可因式分解

既然n = p*q，那么最常规的想法就是把n因式分解得到p,q，上面说n很难分解，但对于一些不太大的n，我们可以借助工具去分解它。下面介绍两种常规因式分解方法：

第一种：在线因式分解网站，例如factordb.com，我们可以利用在线网站快速分解出p,q

第二种：yafu大数分解工具，windows下载地址：yafu download | SourceForge.net使用相关命令分解n:

yafu-x64 factor(n)                               //常规分解n

yafu-x64 "factor(@)" -batchfile 1.txt   //把n复制到txt文件中再分解，用于n过长的情况

例题：BUUCTF：[WUSTCTF2020]babyrsa

附件给出了c,n,e：

【密码技术】RSA算法总结（数学知识/CTF题型）

n不太大，可以对其进行因式分解得到p,q。以yafu为例：

【密码技术】RSA算法总结（数学知识/CTF题型）

得到p，q后按解密方法算出明文即可，python脚本如下：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2from Crypto.Util.number import long_to_bytes
q = 189239861511125143212536989589123569301p = 386123125371923651191219869811293586459
e = 65537c = 28767758880940662779934612526152562406674613203406706867456395986985664083182n = q * p
d = gmpy2.invert(e, (p - 1) * (q - 1))print("d =", d)
m = pow(c, d, n)print("m =", m)
plaintext = long_to_bytes(m)print("Plaintext:", plaintext)

运行即可得到flag，这也是最常规的解密RSA的脚本结构。

【密码技术】RSA算法总结（数学知识/CTF题型）

思路二、低加密指数攻击（e很小）

适用情况：n很大但是e很小，一般e=3

n很大时我们就不能因式分解了，当然还有其他思路，例如当e很小时，比如e=3，有【密码技术】RSA算法总结（数学知识/CTF题型），我们可以对k进行爆破，直到【密码技术】RSA算法总结（数学知识/CTF题型）可以开根，借此得到m。

例题：BUUCTF DangrousRSA

【密码技术】RSA算法总结（数学知识/CTF题型）

题目的n很大，但e仅仅是3，此时我们就可以进行低加密指数攻击，python脚本如下：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2from Crypto.Util.number import long_to_bytes
def de(c, e, n):    k = 0    while True:        m = c + n * k        result, flag = gmpy2.iroot(m, e)        if flag:            return result        k += 1
e = 3n = 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793c = 0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
m = de(c, e, n)print(m)print(long_to_bytes(m))

思路三、低指数加密广播攻击（e很小;多组n,c）

适用情况：很多组不同的n和c，但用的是同一个e且很小。

此时我们可以使用中国剩余定理来求出【密码技术】RSA算法总结（数学知识/CTF题型），什么是中国剩余定理自己去了解，这里只讲怎么用python解题，见例题：

例题：BUUCTF RSA4

题目给了很多组n和c

【密码技术】RSA算法总结（数学知识/CTF题型）

当n很大时我们就可以考虑e=3的低指数情况，把n和c放到数组里，像n=[n1,n2,n3]，c=[c1,c2,c3].然后最方便的是调用sympy库里的中国剩余定理，也就是crt(c,n)方法直接可以求出m的e次，然后开方得到m就行了。其中sympy也是第三方库，可以pip或者pycharm里导入的时候顺手装上去就行了。

这道题还有一点要注意的是给出的n和c是五进制，注意先转换成10进制。python解题脚本如下：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2from Crypto.Util.number import long_to_bytesfrom sympy.ntheory.modular import crt
N1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004', 5)c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243', 5)
N2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114', 5)c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344', 5)
N3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323', 5)c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242', 5)
e = 3n = [N1, N2, N3]c = [c1, c2, c3]
resultant, mod = crt(n, c)value, is_perfect = gmpy2.iroot(resultant, e)
# Convert the integer to bytes and decode as a stringplaintext_bytes = long_to_bytes(value)plaintext_string = plaintext_bytes.decode(errors='ignore')print(plaintext_string)

思路四、公因数攻击（多组n,c）

适用情况：很多组n和c

和上面的广播攻击类似，题目会给你很多组n和c。我们知道n=p*q，而p、q是两个大素数。所以说当有很多组n的时候，很有可能出现两个n之间存在公因数。而这个公因数就是p和q其中的一个，当然知道其中一个另一个也就知道了，我们就可以求出d进而根据对应密文求出m。

例题：BUUCTF RSA5

题目中e = 65537，然后给了多达20组的n和c。

【密码技术】RSA算法总结（数学知识/CTF题型）

此时我们就可以尝试公因数攻击，对所有n进行两两对比看看有没有公因数，如果发现公因数就可以顺势解出明文，python脚本如下：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
from operator import invertfrom gmpy2 import *from Crypto.Util.number import *
def gcd(x, y):    if y > x:        x, y = y, x    while x % y != 0:        a = x % y        x = y        y = a    return y
# List of n and c values
n1 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207c1 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320
n2 = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759c2 = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855
n3 = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491c3 = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862
n4 = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751c4 = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613
n5 = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067c5 = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357
n6 = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369c6 = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932
n7 = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137c7 = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179
n8 = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191c8 = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006
n9 = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941c9 = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934
n10 = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491c10 = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869
n11 = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019c11 = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467
n12 = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299c12 = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971
n13 = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551c13 = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175
n14 = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987c14 = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457
n15 = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837c15 = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842
n16 = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451c16 = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724
n17 = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499c17 = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024
n18 = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973c18 = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887
n19 = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603c19 = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889
n20 = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659c20 = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346
n = []c = []
# Add your n and c values heren_values = [n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12, n13, n14, n15, n16, n17, n18, n19, n20]c_values = [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12, c13, c14, c15, c16, c17, c18, c19, c20]
# Exponent value (e) is fixede = 65537
# Find p and q for each pair of n values having a common gcdfor i in range(len(n_values)):    for j in range(i + 1, len(n_values)):        if gcd(n_values[i], n_values[j]) != 1:            print(i, j)            N = n_values[i]            p = gcd(n_values[i], n_values[j])            print('n =', N)            print('p =', p)            q = N // p            phi = (p - 1) * (q - 1)            d = invert(e, phi)            m = pow(c_values[i], d, N)            print('Decrypted Message:', long_to_bytes(m))

或者

# !/usr/bin/env python3# -*- coding: utf-8 -*-
from operator import invert # 这个是调用了invert后自动出来的^_^from gmpy2 import * # gmpy2中也有invert也可以用gmpy2.invertfrom Crypto.Util.number import *
"""该函数返回两个数的最大公约数"""def gcd(x, y):   if y > x:         x, y = y, x   # y为较小值   while(x % y != 0):  # 上面的比较大小也可以省略，因为如果x较小，第一次进while循环后也会交换xy         a=x%y         x=y         y=a   return y
'''究极简单的写法'''# def gcd(a,b):#     while b!=0:#         a,b=b,a%b#     return a
''' 像菜鸟教程上给的求gcd的代码就太基础了运行起来太慢，所以要用上面的辗转相除法来求gcd'''# def hcf(x, y):#    """ 该函数返回两个数的最大公约数""" #    # 获取最小值#    if x > y:#        smaller = y#    else:#        smaller = x #    for i in range(1,smaller + 1):#        if((x % i == 0) and (y % i == 0)):#            hcf = i #    return hcf e = 65537
n1 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207c1 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320
n2 = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759c2 = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855
n3 = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491c3 = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862
n4 = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751c4 = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613
n5 = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067c5 = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357
n6 = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369c6 = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932
n7 = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137c7 = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179
n8 = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191c8 = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006
n9 = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941c9 = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934
n10 = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491c10 = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869
n11 = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019c11 = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467
n12 = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299c12 = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971
n13 = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551c13 = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175
n14 = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987c14 = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457
n15 = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837c15 = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842
n16 = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451c16 = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724
n17 = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499c17 = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024
n18 = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973c18 = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887
n19 = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603c19 = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889
n20 = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659c20 = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346
n=[n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19,n20]
# 计算所有给出的n的两两之间的最大公约数，把不是1的结果都输出出来，得到pfor i in range(len(n)):    for j in range(i+1,len(n)):  # 经实验发现range的首尾相同时，循环体内容不会执行所以没有报错        if(gcd(n[i],n[j])!=1):            print(i,j)  # 本题的输出只有4 17，即n5和n18有最大公约数            N=n[i]  # 这里我选择用n5的值作为n，所以后面密文也要用c5            p=gcd(n[i],n[j])            print('n=',N)            print('p=',p)# p=132585806383798600305426957307612567604223562626764190211333136246643723811046149337852966828729052476725552361132437370521548707664977123165279305052971868012755509160408641100548744046621516877981864180076497524093201404558036301820216274968638825245150755772559259575544101918590311068466601618472464832499q=N//p  # q=172130338499326278748088659642118539903263306644625489813269854049704514120598134934786316771912260248369075948864036229605563950070491992643125838594149381631362120542615545158696925360916086470107987771246645459433841320759048661246016875180635458357799131806734777129141845728102816378815607663660131827433phi=(p-1)*(q-1)d=invert(e,phi)m=pow(c5,d,N)  # 因为前面的N取的是n[4]，要注意其对应值是n5，所以密文是c5# print(m)  # m=13040004482825176402070107903979416267670062118522537076883968693524598900675425175282673277print(long_to_bytes(m))
'''最后这么写也能得到结果，调用bytes的函数不需要import Crypto库，但要注意先转16进制，然后调用fromhex时还要去掉最前面的0x(hex()函数的结果是str，fromhex()的参数也是str)，实际上，long_to_bytes是在函数内部自行做了先把数字转16进制再将16进制数两两一组转换成ascii码对应字符'''# print(hex(m))# print(bytes.fromhex(hex(m)[2:]))

思路五、低解密指数攻击（e很大）

适用情况：e很大

和低加密指数攻击相反，当e很大的时候我们怎么办呢，这里就要用到低解密指数攻击。当e很大时，相对的d就会很小。这里我们用到github上一个wienerHacker脚本pablocelayes/rsa-wiener-attack: A Python implementation of the Wiener attack on RSA public-key encryption scheme. (github.com)

 下载之后把里面RSAwienerHacker.py改一改输入题目给你的e和n就可以帮你解出d。

例题：BUUCTF RSA2

【密码技术】RSA算法总结（数学知识/CTF题型）

【密码技术】RSA算法总结（数学知识/CTF题型）

 有了d后续进行一些转换就很简单了，解密脚本如下：

注意python2和python3在hex转换时数据结尾相差差一个L字符，会导致hash值不一样

这里就是按照原题给的计算式去处理d值，这里有个小坑，就是由于Python2和Python3有一点区别，在Python3中，hex(d)得到的值在输出形式上相比Python2少了一个末尾的L，再用这个值去做hash得到的md5值也就不同了。经实验发现，正确的结果可以用Python2直接得到，或在Python3中做hash时给参数末尾加上L。

# !/usr/bin/env python3# -*- coding: utf-8 -*-
import hashlib
N = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
d = 8920758995414587152829426558580025657357328745839747693739591820283538307445dd = hex(d)[:] + "L"flag = "flag{" + hashlib.md5(dd.encode("utf-8")).hexdigest() + "}"print(flag)

或者

# !/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2import hashlib
def get_rsa_private_key(p, q, e):    phi = (p - 1) * (q - 1)    d = gmpy2.invert(e, phi)    return d
def generate_flag(d):    dd = hex(d)[:] + "L"    flag = "flag{" + hashlib.md5(dd.encode("utf-8")).hexdigest() + "}"    return flag
if __name__ == "__main__":    n = 101991809777553253470276751399264740131157682329252673501792154507006158434432009141995367241962525705950046253400188884658262496534706438791515071885860897552736656899566915731297225817250639873643376310103992170646906557242832893914902053581087502512787303322747780420210884852166586717636559058152544979471    p = 9046853915223503351787031888977627106934564043204783593118678181991596316582877057556463152579621699010610569526573031954779520781448550677767565207407183    q = 11273732364123571293429600400343309403733952146912318879993851141423284675797325272321856863528776914709992821287788339848962916204774010644058033316303937    e = 46731919563265721307105180410302518676676135509737992912625092976849075262192092549323082367518264378630543338219025744820916471913696072050291990620486581719410354385121760761374229374847695148230596005409978383369740305816082770283909611956355972181848077519920922059268376958811713365106925235218265173085
    d = get_rsa_private_key(p, q, e)    flag = generate_flag(d)    print(flag)

【密码技术】RSA算法总结（数学知识/CTF题型）

思路六、共模攻击

适用情况，多组c,e但模数n相同，且e之间最好互质。

当题目给我们很多组c和e，但它们加密使用的模数n相同时，我们可以考虑共模攻击，当e1，e2互质，有gcd(e1,e2)=1，根据扩展欧几里得算法，一定存在整数x,y使得e1*x+e2*y=1。我们可以调用gmpy2.gcdext()来使用扩展欧几里得算法，以此求出x和y。

又根据加密过程

【密码技术】RSA算法总结（数学知识/CTF题型）

所以

(c1^s1*c2^s2)%n = ((m^e1%n)^s1(m^e2%n)^s2)modn

又经过一堆化简之后就可以得到：m = (c1^x*c2^y)modn,得到明文。

例题：BUUCTF  [BJDCTF2020]rsa_output

 题目给了c1,c2;e1,e2以及一个共同的n，尝试共模攻击，脚本如下。

# !/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2from Crypto.Util.number import long_to_bytes
e1 = 2767e2 = 3659n = 21058339337354287847534107544613605305015441090508924094198816691219103399526800112802416383088995253908857460266726925615826895303377801614829364034624475195859997943146305588315939130777450485196290766249612340054354622516207681542973756257677388091926549655162490873849955783768663029138647079874278240867932127196686258800146911620730706734103611833179733264096475286491988063990431085380499075005629807702406676707841324660971173253100956362528346684752959937473852630145893796056675793646430793578265418255919376323796044588559726703858429311784705245069845938316802681575653653770883615525735690306674635167111
c1 = 20152490165522401747723193966902181151098731763998057421967155300933719378216342043730801302534978403741086887969040721959533190058342762057359432663717825826365444996915469039056428416166173920958243044831404924113442512617599426876141184212121677500371236937127571802891321706587610393639446868836987170301813018218408886968263882123084155607494076330256934285171370758586535415136162861138898728910585138378884530819857478609791126971308624318454905992919405355751492789110009313138417265126117273710813843923143381276204802515910527468883224274829962479636527422350190210717694762908096944600267033351813929448599c2 = 11298697323140988812057735324285908480504721454145796535014418738959035245600679947297874517818928181509081545027056523790022598233918011261011973196386395689371526774785582326121959186195586069851592467637819366624044133661016373360885158956955263645614345881350494012328275215821306955212788282617812686548883151066866149060363482958708364726982908798340182288702101023393839781427386537230459436512613047311585875068008210818996941460156589314135010438362447522428206884944952639826677247819066812706835773107059567082822312300721049827013660418610265189288840247186598145741724084351633508492707755206886202876227
# Extended Euclidean Algorithm to find modular inverses_, s1, s2 = gmpy2.gcdext(e1, e2)
# Calculate the original plaintext using Chinese Remainder Theorem (CRT)m = pow(c1, s1, n) * pow(c2, s2, n) % n
# Convert the plaintext to bytes and print the resultprint(long_to_bytes(m))

思路七、dp泄露

适用情况：题目提供dpdq

有时候除了e,n,c之外题目还会给你像dp,dq这样的值，这是为了方便计算产生的，同时也给了我们另一种解题思路。首先，了解dp,dq是什么东西：

dp=d%(p-1)

然后就可以进行推导，简单过程如下： 

d = dp + k1 * (p-1) d * e = 1 + k2(p-1)(q-1) 把第二个式子的d代换掉：e * (dp + k1(p-1)) = 1 + k2(p-1)(q-1)两边同时对(p-1)取模，消去ke * dp % (p - 1) = 1e * dp = 1 + k(p - 1)

得到这个式子之后我们就可以通过爆破k的方式来求出p，进而求出d。

例题：BUUCTF RSA2

题目提供了dp,e,n,c

【密码技术】RSA算法总结（数学知识/CTF题型）

 python脚本如下：

# !/usr/bin/env python3# -*- coding: utf-8 -*-
import gmpy2from Crypto.Util.number import long_to_bytes
e = 65537n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751
# Factorize n using dp and efor i in range(1, e):    if (dp * e - 1) % i == 0:        if n % (((dp * e - 1) // i) + 1) == 0:            p = ((dp * e - 1) // i) + 1            q = n // (((dp * e - 1) // i) + 1)            break
# Calculate the private key dd = gmpy2.invert(e, (p - 1) * (q - 1))
# Decrypt the ciphertextm = pow(c, d, n)
print("Decrypted plaintext (integer):", m)print("Decrypted plaintext (bytes):", long_to_bytes(m))

【密码技术】RSA算法总结（数学知识/CTF题型）

思路八、dp,dq泄露

适用情况：dp,dq同时泄露

有的时候题目把dpdq都给我们了，这个时候我们不用知道e也可以解密。

此时有：

m1 = c^dpmodp
m2 = c^dqmodq
m = (((m1-m2)*I)%p)*q+m2
其中I为对pq求逆元

例题：BUUCTF RSA1

题目给出p,q,dp,dq,c没有e。

【密码技术】RSA算法总结（数学知识/CTF题型）

此时可以用上述公式求解，python脚本如下：

#!/usr/bin/env python3# -*- coding: utf-8 -*-
from Crypto.Util.number import long_to_bytes
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
# Calculate the modular inverse of q modulo pI = pow(q, -1, p)
# Calculate the first part of the plaintextm1 = pow(c, dp, p)
# Calculate the second part of the plaintextm2 = pow(c, dq, q)
# Calculate the final plaintextm = (((m1 - m2) * I) % p) * q + m2
print("Decrypted plaintext (bytes):", long_to_bytes(m))

————————————————

版权声明：本文为CSDN博主「plexming」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：

https://blog.csdn.net/qq_46145027/article/details/125047313


阅读 10万+

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年7月24日08:22:47
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   【密码技术】RSA算法总结（数学知识/CTF题型）https://cn-sec.com/archives/1901551.html

发表评论

匿名网友 填写信息