打算学习一下RSA，说不定以后会用到

我对RSA的理解

RSA是一种非对称加密方法，加密解密时需要两个密钥–公钥和私钥，加密的时候用公钥，解密的时候用私钥

公钥就是可以公开的密钥，可以被任何人得知；私钥就是要自己保存好的密钥，一旦泄露私钥，加密后的数据安全就得不到保障

我们上网时使用的HTTPS就采用了对称加密（典型的对称加密算法有DES、3DES、AES）和非对称加密（一般是RSA）混合，举这个例子只是想说明RSA随处可见，当然其它非对称加密算法如DSA、ECC也非常经典

RSA加密

RSA在如今算力还不足以强行破解的情况下非常安全，所以借用网上两句话总结RSA（这两句话可以先不看，毕竟是总结）：

“RSA算法所依赖的是对极大整数做因数分解，所以对极大整数做因数分解的难度决定了RSA算法的可靠性。今天只有短的RSA钥匙才可能被强力方式破解。但目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不可能被破解的。“

”这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全(网络通信中一般都是2048位的)。“

用一些程序简单体验加密解密

首先是Shell-Linux环境openssl直接演示一下

openssl的genrsa用于生成密钥对（生成并输入一个RSA私钥）

生成一个私钥

在终端输入

1	openssl genrsa -out rsa.pem -aes128 -passout pass:12345678 2048

rsa.pem意思是输出的文件名

-aes128意思是指定加密算法aes128，方法还有-aes128, -aes192, -aes256

-passout意思是指定密钥文件的加密口令

pass:12345678意思是指定密码12345678

2048意思是指定密钥长度2048

openssl-gen

ls

可以看到生成了一个文件（私钥文件）

打开以后可以发现里面就是公钥（这个密钥文件可以看到加密算法信息）

openssl的rsa用于处理RSA密钥的格式转换等问题

用rsa指令提取公钥

1	openssl rsa -in rsa.pem -passin pass:12345678 -pubout -out pub.pem

rsa.pem意思是输入的文件名，因为前面有个参数-in

-passin意思是输入加密口令

pass:12345678意思是密码12345678

-pubout意思是输出公钥

-out意思是输出到文件，后面的pub.pem 是文件名

打开生成的文件看一看（这个就是公钥）

openssl的rsaut用于处理加密和解密操作

由于公钥私钥都有了，现在到了激动人心的加密解密步骤

先创个txt文件，里面随便输入一些信息再保存

cat一下txt可以看到现在txt里面是明文

用rsautl给它加密一下

1
2

openssl rsautl -encrypt -in 1.txt -inkey rsa.pem -passin pass:12345678 -out encrypt.txt //这样写就是用私钥文件提取公钥再进行加密
openssl rsautl -encrypt -in 1.txt -inkey pub.pem -pubin -out encrypt1.txt  //这样写就是直接用公钥文件加密

命令我就不解释了，和前面差不多

都执行一下，也不知道为什么输出的文件不一样

图一（文件encrypt.txt）

图二（文件encrypt1.txt）

加密操作完成，下面就是解密操作了(解密的话就必须要用私钥了)

用rsautl给它解密一下

1
2

openssl rsautl -decrypt -in encrypt.txt -inkey rsa.pem -passin pass:12345678 -out out.txt //文件encrypt.txt
openssl rsautl -decrypt -in encrypt1.txt -inkey rsa.pem -passin pass:12345678 -out out1.txt //文件encrypt1.txt，可以不管这行，毕竟是一样的

可以看到解密出来的文件都是一样的

然后是易懂的Python3程序

是Python3哦

参考了这篇博客：这里

首先先安装所需模块

1 2	pip3 install pycryptodome pip3 install rsa

生成公钥和私钥

import rsa
 
bit = 2048 #2048位加密


pubkey, privkey = rsa.newkeys(bit)    # 生成公钥、私钥

privkey = privkey.save_pkcs1()  # 保存为 .pem 格式
with open("privkey.pem", "wb") as x:  # 保存私钥
    x.write(privkey)#私钥写入privkey.pem

pubkey = pubkey.save_pkcs1()  # 保存为 .pem 格式
with open("pubkey.pem", "wb") as x:  # 保存公钥
    x.write(pubkey)#公钥写入pubkey.pem

这里的公钥和私钥可以直接拿去openssl用哦

这个例子是为了说明pem文件是通用的

例如我拿这里的私钥来提取公钥

1	openssl rsa -in privkey.pem -pubout -out pub.pem

得到

新建一个txt，存点信息

如下1.txt

再拿公钥加密1.txt

1	openssl rsautl -encrypt -in 1.txt -inkey pub.pem -pubin -out encrypt.txt

加密内容如下

再拿私钥解密

1	openssl rsautl -decrypt -in encrypt.txt -inkey privkey.pem -out 2.txt

解密出的2.txt内容和1.txt相同

拿公钥加密和拿私钥解密

直接上程序

import rsa
 

#载入要加密的文件（原文）
with open("1.txt", "rb") as x:
    text_read = x.read()

#载入私钥
with open("privkey.pem", "rb") as x:
    privkey = x.read()
    privkey = rsa.PrivateKey.load_pkcs1(privkey)
    
#载入公钥    
with open("pubkey.pem", "rb") as x:
    pubkey = x.read()
    pubkey = rsa.PublicKey.load_pkcs1(pubkey)
    

with open("encrypt1.txt", "wb") as x:  # 保存加密后的文件(密文)
    cipher_text = rsa.encrypt(text_read, pubkey) # 使用公钥加密
    x.write(cipher_text)

with open("3.txt", "wb") as x:  # 保存解密后的文件(原文)
    with open("encrypt1.txt", "rb") as y:#读取密文
     cipher_text = y.read()#读取密文字符串到cipher_text变量
     text = rsa.decrypt(cipher_text, privkey)   # 使用私钥解密
     x.write(text)

生成密文

可以看到生成了密文如下

解出的原文与原文一致

深入分析加密解密过程

前面RSA加密解密小试已经完成，接下来要开始了解RSA的原理了

分析式子

我们直接看式子吧

1 2	C ≡ M^e * (mod N) //加密 M ≡ C^d * (mod N) //解密

先确定一下表层意思：

M为原文，C为加密后得到的密文

N和e为公钥，d、N为私钥

那么它们代表什么呢？

N实际上是一个大整数，d、e则是互为无反数的两个指数

加密式子

1	C ≡ M^e * (mod N)

解释：密文 = 明文的e次幂乘以N的模

解密式子

1	M ≡ C^d * (mod N)

解释：明文 = 密文的d次幂乘以N的模

这样是不是好理解一些呢？

分析原理

接下来我们来分析加密原理，这一步是为了理解它

待更新

比较简单的例题

CTFshow crypto4

题目给出了p、q和e

360截图17960322110124105

我们只需要按照公式来就好，这道题只需要下面三个公式

1
2
3

(Φ（n） * k  + 1 ) / e = d
Φ（n）=  (p-1)*(q-1)
n=p*q

k是整数，只需要使用整数进行遍历求解就可以了

下面是python3的解题程序

#Edit by lx
#公式参考：https://blog.csdn.net/qq_38313548/article/details/85387466
#Φ（n） * k  + 1 =ed和（Φ（n） * k  + 1 ）/ e = d
p=447685307
q=2037
e=17
n=p*q
nn=(p-1)*(q-1)

k=1
while True:
  d = ((nn * k)  + 1) / e 
  dd = int(d)
  if dd == d:
    break
  else:
    k += 1

print("CTF.show crypto4: flag{d} is ", "flag{0}{1}{2}".format("{", int(d), "}"))

CTFshow crypto5

题目提供了p、q、e、c

360截图18720121376746

需要下面的公式，求d的公式上面已经给出，这里不再赘述

1	m = c ** d mod n

python3解题程序如下

#Edit by lx
#公式参考：https://www.jianshu.com/p/de710ef3b3e6
# m = c ** d mod n
import math
p=447685307 
q=2037 
e=17 
c=704796792
n=p*q
nn=(p-1)*(q-1)

k=1
while True:
  d = ((nn * k)  + 1) / e 
  dd = int(d)
  if dd == d:
    break
  else:
    k += 1


print("CTF.show crypto5: flag{m} is ", "flag{" + "{}".format(pow(c, int(d), n)) + "}")

给定加密后的文件和公钥文件（解法为生成私钥）

题目给的文件

给定了公钥文件public.key

给定了加密后的文件flag.enc

GVd1d3viIXFfcHapEYuo5fAvIiUS83adrtMW/MgPwxVBSl46joFCQ1plcnlDGfL19K/3PvChV6n5QGohzfVyz2Z5GdTlaknxvHDUGf5HCukokyPwK/1EYU7NzrhGE7J5jPdi0Aj7xi/Odxy0hGMgpaBLd/nL3N8O6i9pc4Gg3O8soOlciBG/6/xdfN3SzSStMYIN8nfZZMSq3xDDvz4YB7TcTBh4ik4wYhuC77gmT+HWOv5gLTNQ3EkZs5N3EAopy11zHNYU80yv1jtFGcluNPyXYttU5qU33jcp0Wuznac+t+AZHeSQy5vk8DyWorSGMiS+J4KNqSVlDs12EqXEqqJ0uA==

解题方法

先从公钥文件中提取n和e，

借助python里的Crypto包中的PublicKey模块很容易完成

from Crypto.PublicKey import RSA

f = open('./public.key', 'rb').read()
pub = RSA.importKey(f)
n = pub.n
e = pub.e
print(n, '\n', e)
# n = 79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443
# e = 65537

然后看看n能不能分解，

因为条件有限，想要做出的话一般都是能分解的，

可以借助各种分解n的工具或者在线网站

这题是可以分解的，分解出来p、q如下

1
2

p = 3133337
q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939

接下来一切都容易了，求出d然后生成私钥以解密文件，

尝试直接使用RSA算式算不能直接算出来，必须拿私钥解

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import *

p = 3133337
q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)

#使用n、e、d、p、q生成私钥
rsa_components=(n,e,int(d),p,q)
arsa=RSA.construct(rsa_components)
rsakey = RSA.importKey(arsa.exportKey())
rsakey = PKCS1_OAEP.new(rsakey)

之后按照正常流程解密，完整程序如下

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Util.number import *
import base64
import gmpy2
import rsa
f = open('.\public.key', 'rb').read()
pub = RSA.importKey(f)
n = pub.n
e = pub.e
print(n, '\n', e)

# n = 79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443
# e = 65537

p = 3133337
q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)


#key_info = RSA.construct((n, e, d, p, q))
#key = RSA.importKey(key_info.exportKey())
#key = PKCS1_OAEP.new(key)
#key = rsa.PrivateKey(n,e,d,q,p) 
f = open('.\flag.enc', 'r').read()

rsa_components=(n,e,int(d),p,q)
 
arsa=RSA.construct(rsa_components)
 
rsakey = RSA.importKey(arsa.exportKey())
 
rsakey = PKCS1_OAEP.new(rsakey)
'''
decrypted = rsakey.decrypt(c_bytes)
 
print(rsa_components)
'''

c=base64.b64decode(f)

flag=rsakey.decrypt(c)
print(flag)



c=bytes_to_long(c)
print(c)
m=gmpy2.powmod(c,d,n)
print(long_to_bytes(m).decode('utf-32'))

已知N和两段密文

题目给的文件

题目提供了一个加密程序encrypt.py

import hashlib
import sympy
from Crypto.Util.number import *

flag = 'GWHT{******}'
secret = '******'

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)

N = p * q

e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open('secret', 'w')
output.write('N=' + str(N) + '\n')
output.write('m1=' + str(m1) + '\n')
output.write('m2=' + str(m2) + '\n')
output.close()

同时给了输出文件secret，内容是N和两段密文

m1是由原文c1RSA加密后的密文，c1是F1 + F2即flag前半段和flag后半段相加

（注意，这里的相加并不是字符串拼接，是两端flag被转成了整数然后相加）

m2是由原文c2RSA加密后的密文，c2是F1三次方后再加上F2三次方

N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546

解题方法

解这前提条件是能分解N出pq，不然没法解密RSA

1
2

p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737

然后RSA解密得到c1、c2

import gmpy2
N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546

e=65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
c1 = pow(m1, d, N)
c2 = pow(m2, d, N)

上面已经说了c1、c2的由来：

c1 = F1 + F2，c1^2 = ( F1 + F2) ^ 2 = F1^2 + F2^2 + 2F1*F2
c2 = pow(F1, 3) + pow(F2, 3) = F1^3 + F2^3

然后可以使用h=((c1^2)//3)-(c2//(3*c1))这个逆推式子配合已知条件h=a*b, c1=a+b再使用求解器,

求出a、b，ab是转为整数的f两段lag

from z3 import*

h=1816161263733358048121941530698342818827717719035680583254778301273837138120341137307387105#((c1**2)//3)-(c2//(3*c1))
s=Solver()
a=Int('a')
b=Int('b')

#print(h) h=ab c1=a+b

s.add(a+b == 2732509502629189160482346120094198557857912754)

s.add(a*b == h)
assert s.check() == sat

完整程序如下

import gmpy2
import sympy
from Crypto.Util.number import *
from z3 import*

N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546

p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737

e=65537
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
c1 = pow(m1, d, N)
c2 = pow(m2, d, N)

h=1816161263733358048121941530698342818827717719035680583254778301273837138120341137307387105#((c1**2)//3)-(c2//(3*c1))
s=Solver()
a=Int('a')
b=Int('b')

#print(h) h=ab c1=a+b

s.add(a+b == 2732509502629189160482346120094198557857912754)

s.add(a*b == h)
assert s.check() == sat

F = s.model()[a].as_long()
T = s.model()[b].as_long()
'''
print(F)
print(T)

F1 + F2 = c1
c2 = pow(F1, 3) + pow(F2, 3)
'''


flag1=long_to_bytes(F)
flag2=long_to_bytes(T)
print(flag2+flag1)

提供五个公钥（一个N、五个e）和一个私钥（N，d）和密文

题目给的文件

题目提供了一个程序，看起来比较简洁

功能其实也比较简洁，可以看到e定好了，然后生成pq再算N和d（生成公钥、私钥）

接着五次循环生成五个质数作为公钥的e，N一直不变

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import math
from gmpy2 import next_prime

FLAG = b"crypto{????????????????????????????????????????????????}"

p = getPrime(1024)
q = getPrime(1024)
N = p*q
phi = (p-1)*(q-1)
e = 0x10001
d = inverse(e, phi)

my_key = (N, d)

friends = 5
friend_keys = [(N, getPrime(17)) for _ in range(friends)]

cipher = bytes_to_long(FLAG)

for key in friend_keys:
    cipher = pow(cipher, key[1], key[0])

print(f"My private key: {my_key}")
print(f"My Friend's public keys: {friend_keys}")
print(f"Encrypted flag: {cipher}")

提供了输出output.txt

My private key: (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 2734411677251148030723138005716109733838866545375527602018255159319631026653190783670493107936401603981429171880504360560494771017246468702902647370954220312452541342858747590576273775107870450853533717116684326976263006435733382045807971890762018747729574021057430331778033982359184838159747331236538501849965329264774927607570410347019418407451937875684373454982306923178403161216817237890962651214718831954215200637651103907209347900857824722653217179548148145687181377220544864521808230122730967452981435355334932104265488075777638608041325256776275200067541533022527964743478554948792578057708522350812154888097)
My Friend's public keys: [(21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 106979), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 108533), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 69557), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 97117), (21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771, 103231)]
Encrypted flag: 20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117

解题方法

第一步看看能不能分解N，这里发现可以分解，得到pq如下

1
2

p=134460556242811604004061671529264401215233974442536870999694816691450423689575549530215841622090861571494882591368883283016107051686642467260643894947947473532769025695530343815260424314855023688439603651834585971233941772580950216838838690315383700689885536546289584980534945897919914730948196240662991266027
q=161469718942256895682124261315253003309512855995894840701317251772156087404025170146631429756064534716206164807382734456438092732743677793224010769460318383691408352089793973150914149255603969984103815563896440419666191368964699279209687091969164697704779792586727943470780308857107052647197945528236341228473

然后从给的输出My Friend's public keys里面可以找到五个e，

注意要倒着来，因为要逆推解回去

1	e = [103231,97117,69557,108533,106979]

接下来就好办了，将他们五个私钥（d）算出来

import gmpy2

p=134460556242811604004061671529264401215233974442536870999694816691450423689575549530215841622090861571494882591368883283016107051686642467260643894947947473532769025695530343815260424314855023688439603651834585971233941772580950216838838690315383700689885536546289584980534945897919914730948196240662991266027
q=161469718942256895682124261315253003309512855995894840701317251772156087404025170146631429756064534716206164807382734456438092732743677793224010769460318383691408352089793973150914149255603969984103815563896440419666191368964699279209687091969164697704779792586727943470780308857107052647197945528236341228473
phi=(p-1)*(q-1)
e = [103231,97117,69557,108533,106979]
d=[]
for i in e:
    d.append(gmpy2.invert(i,phi)) 
print(d)

再依次解密即可

from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse
import gmpy2

n=21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
c=20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117

m=c
d = [gmpy2.mpz(14976934932676584321683381078589206129802696756347452400490526455696084573015258129692134121798160701052182095773579625055482988152534986446433913203836896533116280256175147942609851284152010144289592625959098055077182547510273874680366469520622967613934401816095053670139111862241214210679418688843207294719210638623059808156603513328070063949694399651593684751165494538800859543190296638019941609102416138469099277831161767829712633873825215808675809899233312091622558923332734521949634469025857591717937024761525022508322488701416182627700447279235588065578502556218141914246088262668554149203042454115911908310703), gmpy2.mpz(5456163066690715087320481993447953020336098077226032646195134412678367908517553348084665801066919445803662455439884803615849841397425529510630693361018110614451312888862006100411867838751667824763724068918315434794777195905815326114637697844562227361928073265792791706114698362419938680722573266355483239860495738115984738276434551710706011594962374898002014841960346301695815553438493222542191889345149269329179557961899079070252028307877859707553245360807224594850647972239997678597545123073105250014889873415867041148644893646931372529032752016030171065755070279488542886213197677662096550188941698416151969760149), gmpy2.mpz(15024086703144100608380300358259382719406977034681648081709158397660796568388968274444301806306053572976616273207620544383192890753083687360230375098004028174572915807907583511198729702530708550238604058119599634446768784996796764406486651554057902600480052493140087866828751517513269631020096592636884399213526171592136163100622270081650859270616743443139937663157666369223280576135733495764121507761953952082664122323986852385046296980748569014549167425185196014846509188210816943153326070977328568075781794943605293980775097141919067574420550307640683196765763433945973704011906495769535888208516068354804409843661), gmpy2.mpz(12762167551366118071720753744231860996946029784706127808630453143965397526458562017144637131573025032347652825700705574407926404974960017901138675107791898181088334411754746792961729531047620446657788706529017031690852859630362989981642393145799974168660009557192705782072568903218272152721384118659895273792607456441482752175000904895599966587373947009470910210482039251273529151591382824028317250374946135838665754782067757582230136689327761412090471825427644488982414008809801936600403775685071388080476656096562493113134124931942591798528521358435132906022897366507245220769035091349539691776009546693221700181645), gmpy2.mpz(17312789047115721718151694136426552941284855738779804364018779659349232886160261403877195921800160981820551978627208288844536701814738862188766791962568000737911220780227869935631696179261131793895509577735783857923826531822580715078877738786352320675373439667502945538153803639887509535733732048518331639166555561603435452580318499918711921292809871549619588262475139443271531521507856705793350365006396297148290332190622868448791245935939328202068843118455938152934836416501933205585863944190269994029439678543734710002351332414419120168882166315801322919286837384476389282429234027483332019975830017618850680549227)]

for i in d:
    m=gmpy2.powmod(m,i,n)
print(long_to_bytes(m))

完整程序如下

import gmpy2
from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long, inverse

n=21711308225346315542706844618441565741046498277716979943478360598053144971379956916575370343448988601905854572029635846626259487297950305231661109855854947494209135205589258643517961521594924368498672064293208230802441077390193682958095111922082677813175804775628884377724377647428385841831277059274172982280545237765559969228707506857561215268491024097063920337721783673060530181637161577401589126558556182546896783307370517275046522704047385786111489447064794210010802761708615907245523492585896286374996088089317826162798278528296206977900274431829829206103227171839270887476436899494428371323874689055690729986771
c=20304610279578186738172766224224793119885071262464464448863461184092225736054747976985179673905441502689126216282897704508745403799054734121583968853999791604281615154100736259131453424385364324630229671185343778172807262640709301838274824603101692485662726226902121105591137437331463201881264245562214012160875177167442010952439360623396658974413900469093836794752270399520074596329058725874834082188697377597949405779039139194196065364426213208345461407030771089787529200057105746584493554722790592530472869581310117300343461207750821737840042745530876391793484035024644475535353227851321505537398888106855012746117
p=134460556242811604004061671529264401215233974442536870999694816691450423689575549530215841622090861571494882591368883283016107051686642467260643894947947473532769025695530343815260424314855023688439603651834585971233941772580950216838838690315383700689885536546289584980534945897919914730948196240662991266027
q=161469718942256895682124261315253003309512855995894840701317251772156087404025170146631429756064534716206164807382734456438092732743677793224010769460318383691408352089793973150914149255603969984103815563896440419666191368964699279209687091969164697704779792586727943470780308857107052647197945528236341228473
phi=(p-1)*(q-1)
e = [103231,97117,69557,108533,106979]
d=[]
for i in e:
    d.append(gmpy2.invert(i,phi)) 
print(d) 

m=c
for i in d:
    m=gmpy2.powmod(m,i,n)
print(long_to_bytes(m))