四面八方
题目如下：
key1:security
key2:information
密文啊这是，骚年加油：zhnjinhoopcfcuktlj看了大佬的博客才知道这是四方密码，科普一下：
四方密码是一种对称式加密法，由法国人Felix Delastelle（1840年–1902年）发明。
这种方法将字母两个一组，然后采用多字母替换密码。 [1]
四方密码用4个5×5的矩阵来加密。每个矩阵都有25个字母（通常会取消Q或将I,J视作同一样，或改进为6×6的矩阵，加入10个数字）。
加密原理：
首先选择两个英文字作密匙，例如example和keyword。对于每一个密匙，将重复出现的字母去除，即example要转成exampl，然后将每个字母顺序放入矩阵，再将余下的字母顺序放入矩阵，便得出加密矩阵。
将这两个加密矩阵放在右上角和左下角，余下的两个角放a到z顺序的矩阵： [1]
加密的步骤：
两个字母一组地分开讯息：（例如hello world变成he ll ow or ld）；
找出第一个字母在左上角矩阵的位置；
同样道理，找第二个字母在右下角矩阵的位置；
找右上角矩阵中，和第一个字母同行，第二个字母同列的字母；
找左下角矩阵中，和第一个字母同列，第二个字母同行的字母；
得到的这两个字母就是加密过的讯息。
he lp me ob iw an ke no bi的加密结果：FY NF NE HW BX AF FO KH MD
引用大佬博客中的一张图片：
通过在线解密工具，如下图：
在进行爆破：
就是flag啦。
[AFCTF2018]你听过一次一密么？
这里直接贴上大佬的博客链接（https://www.ruanx.net/many-time-pad/）
[MRCTF2020]Easy_RSA
题目如下：
import sympy
from gmpy2 import gcd, invert
from random import randint
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
import base64
from zlib import *
flag = b"MRCTF{XXXX}"
base = 65537
def gen_prime(N):
A = 0
while 1:
A = getPrime(N)
if A % 8 == 5:
break
return A
def gen_p():
p = getPrime(1024)
q = getPrime(1024)
assert (p < q)
n = p * q
print("P_n = ", n)
F_n = (p - 1) * (q - 1)
print("P_F_n = ", F_n)
factor2 = 2021 * p + 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
return sympy.nextprime(factor2)
def gen_q():
p = getPrime(1024)
q = getPrime(1024)
assert (p < q)
n = p * q
print("Q_n = ", n)
e = getRandomNBitInteger(53)
F_n = (p - 1) * (q - 1)
while gcd(e, F_n) != 1:
e = getRandomNBitInteger(53)
d = invert(e, F_n)
print("Q_E_D = ", e * d)
factor2 = 2021 * p - 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
return sympy.nextprime(factor2)
if __name__ == "__main__":
_E = base
_P = gen_p()
_Q = gen_q()
assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1)
_M = bytes_to_long(flag)
_C = pow(_M, _E, _P * _Q)
print("Ciphertext = ", _C)
'''
P_n = 14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024336556028267742021320891681762543660468484018686865891073110757394154024833552558863671537491089957038648328973790692356014778420333896705595252711514117478072828880198506187667924020260600124717243067420876363980538994101929437978668709128652587073901337310278665778299513763593234951137512120572797739181693
P_F_n = 14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024099427363967321110127562039879018616082926935567951378185280882426903064598376668106616694623540074057210432790309571018778281723710994930151635857933293394780142192586806292968028305922173313521186946635709194350912242693822450297748434301924950358561859804256788098033426537956252964976682327991427626735740
Q_n = 20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
Q_E_D = 100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
Ciphertext = 40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021
'''是一个RSA加密过程，属于RSA嵌套题，分别利用第一重RSA生成p和q，在进行对明文的加密。所以我们需要对题目中给出的几个常量来求得p和q。首先是利用P_n和P_F_n来求p，P_n = p1 q1， P_F_n = (p1 - 1) (q1 - 1)，这样两个未知数两个方程可以求得p1和q1，注意的是p1小于q1。
脚本如下：
from sympy import *
x = Symbol('x')
y = Symbol('y')
print(solve([x * y - P_n, (x - 1) * (y - 1) - P_F_n], [x, y]))再来看看生成q的函数，这里直接进行对Q_n的因数分解。在csdn上看到了大佬分解Q_n的操作：
#coding=utf-8
from random import randint
import gmpy2
def oddR(r):
while r%2==0:
r=r//2
return r
def bits(b):
k=[]
while b:
if b%2!=0:
k.append(1)
else:
k.append(0)
b>>=1
k.reverse()
return k
def quickmod(a,b,n): #a^b mod n 快速幂模n运算
f=1
k=bits(b)
for i in range(len(k)):
f=(f*f)%n
if k[i]:
f=(f*a)%n
return f
def gcd(m,n):
while(n!=0):
m,n=n,m%n
return m
def func(e_d,N):
k=e_d-1
r=oddR(k) #求出k=2^t*r中的r
while True:
b=randint(2,N-1) #获取区间(2,N-1)的一个随机数
a=quickmod(b,r,N)
if a==1:
continue
y=gcd(a-1,N)
if a>1 and y>1:
q=N//y
return q
else:
r=r*2
def deciphering(e_d,n): 、
p=func(e_d,n)
q=n//p
phi=n-(p+q)+1
if p*q==n:
print p
print q
else:
print"error"
n = 20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
e_d= 100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
deciphering(e_d,n)最后就是正常的RSA解密了。
n = p * q
phin = (p - 1) * (q - 1)
d = inverse(e, phin)
m = pow(Ciphertext, d, n)
print(long_to_bytes(m))[De1CTF2019]babyrsa
[ACTF新生赛2020]crypto-aes
题目如下：
aes.py:
from Cryptodome.Cipher import AES
import os
import gmpy2
from flag import FLAG
from Cryptodome.Util.number import *
def main():
key=os.urandom(2)*16
iv=os.urandom(16)
print(bytes_to_long(key)^bytes_to_long(iv))
aes=AES.new(key,AES.MODE_CBC,iv)
enc_flag = aes.encrypt(FLAG)
print(enc_flag)
if __name__=="__main__":
main()
------------------------------------------------------------------------------------------------------------
output:
91144196586662942563895769614300232343026691029427747065707381728622849079757
b'\x8c-\xcd\xde\xa7\xe9\x7f.b\x8aKs\xf1\xba\xc75\xc4d\x13\x07\xac\xa4&\xd6\x91\xfe\xf3\x14\x10|\xf8p'在加密算法中os.urandom()函数的作用是随机生成一个适合加密的字节，语法如下：
语法 os.urandom（size）
参数：
size:字符串随机字节的大小
返回值：该方法返回一个字符串，该字符串表示适合加密使用的随机字节。
例 os.urandom(1)
输出：b'\x91'
二进制：10010001 （8bits）AES.new(key, mode, args, *kwargs)
param key(参数密钥):
在对称密码中使用的秘密密钥。
它必须为16、24或32个字节长（分别用于AES-128， AES-192或AES-256）。mode（模式）
模式（支持的MODE_*常量之一）–用于加密或解密的链接模式。
学习链接：https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.htmlKeyword Arguments（关键字参数）：
IV（字节，字节组，memoryview） - （只适用于MODE_CBC，MODE_CFB，MODE_OFB，和MODE_OPENPGP模式）。
用于加密或解密的初始化向量。
对于MODE_CBC，MODE_CFB和MODE_OFB它必须是16个字节。解题的关键在于获取key和iv，通过观察发现key的生成是先生成2个字节的数据然后复制16份形成32字节的数据。iv是直接生成一个16字节的数据。接着key的低16位和iv进行异或就是output中的第一个数据的二进制数，而key的高16位是没有发生变动的，high_key_16 = xor_16。这样我们可以通过异或的结果的高16位来得到key，得到key之后再和xor异或就可以得到iv，最后就是构造出aes对象对enc_flag解密。脚本如下：
from Crypto.Cipher import AES
import os
import gmpy2
from Crypto.Util.number import *
xor = 91144196586662942563895769614300232343026691029427747065707381728622849079757
enc_flag = b'\x8c-\xcd\xde\xa7\xe9\x7f.b\x8aKs\xf1\xba\xc75\xc4d\x13\x07\xac\xa4&\xd6\x91\xfe\xf3\x14\x10|\xf8p'
key_iv = long_to_bytes(xor)
high_key = key_iv[0:16]
key = key_iv[0:16] * 2
iv = bytes_to_long(key[16:]) ^ bytes_to_long(key_iv[16:])
iv = long_to_bytes(iv)
aes=AES.new(key,AES.MODE_CBC,iv)
flag = aes.decrypt(enc_flag)
print(flag)[INSHack2019]Yet Another RSA Challenge - Part 1
题目如下：
import subprocess
p = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
q = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
flag = int('INSA{REDACTED}'.encode('hex'), 16)
N = int(p,16) * int(q,16)
print N
print '0x'+p.replace('9F','FC')
print pow(flag,65537,N)
------------------------------------------------------------------------------------------------------------
output:
719579745653303119025873098043848913976880838286635817351790189702008424828505522253331968992725441130409959387942238566082746772468987336980704680915524591881919460709921709513741059003955050088052599067720107149755856317364317707629467090624585752920523062378696431510814381603360130752588995217840721808871896469275562085215852034302374902524921137398710508865248881286824902780186249148613287250056380811479959269915786545911048030947364841177976623684660771594747297272818410589981294227084173316280447729440036251406684111603371364957690353449585185893322538541593242187738587675489180722498945337715511212885934126635221601469699184812336984707723198731876940991485904637481371763302337637617744175461566445514603405016576604569057507997291470369704260553992902776099599438704680775883984720946337235834374667842758010444010254965664863296455406931885650448386682827401907759661117637294838753325610213809162253020362015045242003388829769019579522792182295457962911430276020610658073659629786668639126004851910536565721128484604554703970965744790413684836096724064390486888113608024265771815004188203124405817878645103282802994701531113849607969243815078720289912255827700390198089699808626116357304202660642601149742427766381
0xDCC5A0BD3A1FC0BEB0DA1C2E8CF6B474481B7C12849B76E03C4C946724DB577D2825D6AA193DB559BC9DBABE1DDE8B5E7805E48749EF002F622F7CDBD7853B200E2A027E87E331AFCFD066ED9900F1E5F5E5196A451A6F9E329EB889D773F08E5FBF45AACB818FD186DD74626180294DCC31805A88D1B71DE5BFEF3ED01F12678D906A833A78EDCE9BDAF22BBE45C0BFB7A82AFE42C1C3B8581C83BF43DFE31BFD81527E507686956458905CC9A660604552A060109DC81D01F229A264AB67C6D7168721AB36DE769CEAFB97F238050193EC942078DDF5329A387F46253A4411A9C8BB71F9AEB11AC9623E41C14FCD2739D76E69283E57DDB11FC531B4611EE3
596380963583874022971492302071822444225514552231574984926542429117396590795270181084030717066220888052607057994262255729890598322976783889090993129161030148064314476199052180347747135088933481343974996843632511300255010825580875930722684714290535684951679115573751200980708359500292172387447570080875531002842462002727646367063816531958020271149645805755077133231395881833164790825731218786554806777097126212126561056170733032553159740167058242065879953688453169613384659653035659118823444582576657499974059388261153064772228570460351169216103620379299362366574826080703907036316546232196313193923841110510170689800892941998845140534954264505413254429240789223724066502818922164419890197058252325607667959185100118251170368909192832882776642565026481260424714348087206462283972676596101498123547647078981435969530082351104111747783346230914935599764345176602456069568419879060577771404946743580809330315332836749661503035076868102720709045692483171306425207758972682717326821412843569770615848397477633761506670219845039890098105484693890695897858251238713238301401843678654564558196040100908796513657968507381392735855990706254646471937809011610992016368630851454275478216664521360246605400986428230407975530880206404171034278692756题目中告诉了我们p，不过其中的十六进制数被替换了，这里就直接使用爆破恢复原来的p。脚本如下：
from Crypto.Util.number import *
import gmpy2
import numpy as np
e = 65537
n = 719579745653303119025873098043848913976880838286635817351790189702008424828505522253331968992725441130409959387942238566082746772468987336980704680915524591881919460709921709513741059003955050088052599067720107149755856317364317707629467090624585752920523062378696431510814381603360130752588995217840721808871896469275562085215852034302374902524921137398710508865248881286824902780186249148613287250056380811479959269915786545911048030947364841177976623684660771594747297272818410589981294227084173316280447729440036251406684111603371364957690353449585185893322538541593242187738587675489180722498945337715511212885934126635221601469699184812336984707723198731876940991485904637481371763302337637617744175461566445514603405016576604569057507997291470369704260553992902776099599438704680775883984720946337235834374667842758010444010254965664863296455406931885650448386682827401907759661117637294838753325610213809162253020362015045242003388829769019579522792182295457962911430276020610658073659629786668639126004851910536565721128484604554703970965744790413684836096724064390486888113608024265771815004188203124405817878645103282802994701531113849607969243815078720289912255827700390198089699808626116357304202660642601149742427766381
cipher = 596380963583874022971492302071822444225514552231574984926542429117396590795270181084030717066220888052607057994262255729890598322976783889090993129161030148064314476199052180347747135088933481343974996843632511300255010825580875930722684714290535684951679115573751200980708359500292172387447570080875531002842462002727646367063816531958020271149645805755077133231395881833164790825731218786554806777097126212126561056170733032553159740167058242065879953688453169613384659653035659118823444582576657499974059388261153064772228570460351169216103620379299362366574826080703907036316546232196313193923841110510170689800892941998845140534954264505413254429240789223724066502818922164419890197058252325607667959185100118251170368909192832882776642565026481260424714348087206462283972676596101498123547647078981435969530082351104111747783346230914935599764345176602456069568419879060577771404946743580809330315332836749661503035076868102720709045692483171306425207758972682717326821412843569770615848397477633761506670219845039890098105484693890695897858251238713238301401843678654564558196040100908796513657968507381392735855990706254646471937809011610992016368630851454275478216664521360246605400986428230407975530880206404171034278692756
np.array()
plain=['9F','FC']
for a in plain:
for b in plain:
for c in plain:
for d in plain:
p="DCC5A0BD3A1"+a+"0BEB0DA1C2E8CF6B474481B7C12849B76E03C4C946724DB577D2825D6AA193DB559BC9DBABE1DDE8B5E7805E48749EF002F622F7CDBD7853B200E2A027E87E331A"+b+"FD066ED9900F1E5F5E5196A451A6F9E329EB889D773F08E5FBF45AACB818FD186DD74626180294DCC31805A88D1B71DE5BFEF3ED01F12678D906A833A78EDCE9BDAF22BBE45C0BFB7A82AFE42C1C3B8581C83BF43DFE31BFD81527E507686956458905CC9A660604552A060109DC81D01F229A264AB67C6D7168721AB36DE769CEAFB97F238050193EC942078DDF5329A387F46253A4411A9C8BB71F9AEB11AC9623E41C14"+c+"D2739D76E69283E57DDB11"+d+"531B4611EE3"
p1=int(p,16)
if(n%p1==0):
print (p1)
#27869881035956015184979178092922248885674897320108269064145135676677416930908750101386898785101159450077433625380803555071301130739332256486285289470097290409044426739584302074834857801721989648648799253740641480496433764509396039330395579654527851232078667173592401475356727873045602595552393666889257027478385213547302885118341490346766830846876201911076530008127691612594913799272782226366932754058372641521481522494577124999360890113778202218378165756595787931498460866236502220175258385407478826827807650036729385244897815805427164434537088709092238894902485613707990645011133078730017425033369999448757627854563
p = 27869881035956015184979178092922248885674897320108269064145135676677416930908750101386898785101159450077433625380803555071301130739332256486285289470097290409044426739584302074834857801721989648648799253740641480496433764509396039330395579654527851232078667173592401475356727873045602595552393666889257027478385213547302885118341490346766830846876201911076530008127691612594913799272782226366932754058372641521481522494577124999360890113778202218378165756595787931498460866236502220175258385407478826827807650036729385244897815805427164434537088709092238894902485613707990645011133078730017425033369999448757627854563
q = n // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
# print(type(c))
m = pow(cipher, d, n)
print (long_to_bytes(m))[AFCTF2018]花开藏宝地
题目如下：
题面.txt:
第80804238007977405688648566160504278593148666302626415149704905628622876270862865768337953835725801963142685182510812938072115996355782396318303927020705623120652014080032809421180400984242061592520733710243483947230962631945045134540159517488288781666622635328316972979183761952842010806304748313326215619695085380586052550443025074501971925005072999275628549710915357400946408857号藏宝图
我把我的宝藏都藏在了那里！
那个神秘的地方！
于是我把藏宝图分成了5份，交给五位贤者让他们帮我妥善保管，并且只要搜集3份就可以获得宝藏的地址。
第一位贤者将藏宝图放进时空门中说道：
“那么口令就是我的生日吧，那可是个好数字呢。”
第二位贤者将藏宝图放进宝箱，【小】声念着自己的名字锁上了宝箱。
第三位贤者将藏宝图施上咒语丢进大海：“只要【大】声喊出那句咒语就可以把水驱逐！”
第四位贤者找了个破锁锁上了宝箱，狡黠地笑着：“谁知道它是坏的呢？”
第五位贤者给藏宝图裹上了隐身衣，放入了一个匣子里
据说，只有拥有【智慧】与【力量】就可以获得宝藏了呢！~
你是这样的勇者吗？
------------------------------------------------------------------------------------------------------------
另外还有4个加密的压缩包，和没有加密的内容为空的压缩包。初步分析这5个压缩包就是那五位贤者分到的包藏图。
刚开始的想法：按照题目给的意思打开其中的三个压缩包，然后把包藏图的序号进行5等分，再看看里面有什么奥秘。
后来发现并不能提供什么关键的线索，然后想了想不如看看原始数据有社么内容，直接long_to_bytes()。
from Crypto.Util.number import *
m = 80804238007977405688648566160504278593148666302626415149704905628622876270862865768337953835725801963142685182510812938072115996355782396318303927020705623120652014080032809421180400984242061592520733710243483947230962631945045134540159517488288781666622635328316972979183761952842010806304748313326215619695085380586052550443025074501971925005072999275628549710915357400946408857
print(long_to_bytes(m))
#b"A treasure map is a map that marks the location of buried treasure, a lost mine, a valuable secret or a hidden locale. So flag is afctf{1sn't_s0_int3Resting}\x99"haha，flag就在里面了。
[GUET-CTF2019]NO SOS
题目如下：
..-.-.-.–…….–..-…-..-…–.-.-….-..-..–.-.-..-.-..—-其中的’.’和’–’被修改过，恢复至原样：
..-.-.-.--.......--..-...-..-...--.-.-....-..-..--.-.-..-.-..----把’.’换成0，把’-‘换成’1’。二进制转16进制：
aababababbaaaaaaabbaabaaabaabaaabbababaaaabaabaabbababaababaabbbb就是熟悉的培根密码，进行解密：
FLAGISGUETKKP[NPUCTF2020]共 模 攻 击 （很好的题，打个tag）
题目如下：
hint.py:
from gmpy2 import *
from Crypto.Util.number import *
from secret import hint
m = bytes_to_long(hint)
p = getPrime(256)
c = pow(m, 256, p)
print(p)
p, q = getPrime(256), getPrime(256)
n = p * q
e1, e2 = getPrime(32), getPrime(32)
c1, c2 = pow(c, e1, n), pow(c, e2, n)
print(n)
print(e1, c1)
print(e2, c2)
'''
107316975771284342108362954945096489708900302633734520943905283655283318535709
6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
2303413961 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
2622163991 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
'''
------------------------------------------------------------------------------------------------------------
task.py:
from gmpy2 import *
from Crypto.Util.number import *
from secret import flag
flag = flag.strip(b"npuctf{").strip(b"}")
m = bytes_to_long(flag)
p, q = getPrime(512), getPrime(512)
n = p * q
e1, e2 = p, q
c1, c2 = pow(m, e1, n), pow(m, e2, n)
print(n)
print(c1)
print(c2)
'''
128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585
'''先从hint入手，思路是：通过共模攻击得到c，再由c的到明文。值得注意的是明文的加密过程中模数使用的是p，是一个素数，所以这里需要用到sympy.nthroot_mod()函数，脚本如下：
from Crypto.Util.number import *
from sympy import *
import libnum
import gmpy2
#扩展欧几里得算法，求得a与b的系数
def exgcd(a , b):
#当a % b == 0时表示已求得最大公约数和两个系数
if (b == 0):
#返回的第一个参数最大公约数，第二个参数a的系数，第三个参数是b的系数
#这里0和任何数的最大公约数是这个数的本身
return (b, 1, 0)
else:
#将函数返回的结果依次赋值给d, x, y
d, x, y = exgcd(b, a % b)
return (d, y, x - (a // b) * y)
n = 6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
c1 = 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
e1= 2303413961
c2 = 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
e2= 2622163991
s = exgcd(e1, e2)
s1 = s[1]
s2 = s[2]
#当s是负数的时候，一个数的负数次幂，先计算c的模反元素cr，然后求cr的-s次幂。
if (s1 < 0):
s1 = -s1
c1 = inverse(c1, n)
elif (s2 < 0):
s2 = -s2
c2 = inverse(c2, n)
c = pow(c1,s1,n) * pow(c2,s2,n) % n
#19384002358725759679198917686763310349050988223627625096050800369760484237557
p = 107316975771284342108362954945096489708900302633734520943905283655283318535709
m = nthroot_mod(c, 256, p)
print(long_to_bytes(m))
#b'm.bit_length() < 400'提示了m的长度，这样我们可以联想到CopperSmith定理。Coppersmith定理的内容为：在一个e阶的mod n多项式f(x)中，如果有一个根小于n^1/e，就可以运用一个O(log n)的算法求出这些根。
从task文件中我们知道c1 = m^p mod n, c2 = m^q mod n。p和q都是512位，n是在1024位左右，整除512后肯定比m大，因为m小于400位，这样我们就可以利用CopperSmith定理了。
推导：
m^p ≡ m mod p; m^q ≡ m mod q。
c1 = k1 p + m + k2 p q —> 整理得 c1 = m + i p
c2 = h1 q + m + h2 p q —> 整理得 c2 = m + j q
c1 + c2 = 2m + (i p + j q) ————————-①
c1 c2 = m ^ 2 + m (i p + j q) + i p j * q ————————-②
通过两个方程消去(i p + j q)有关的项，生成等式：
m ^ 2 - (c1 + c2)m + c1 c2 = ijn ≡ 0 mod n
这样就可以利用sage，在n的整数群里找出m。
sage: n = 1282053047437519858896793511958367994343243469961297538962349179826472
....: 54577214018524580290192396070591032007818847697193260130051396080104704981
....: 59419060285424193677732443167356467790077399227346353471700958753015248072
....: 54487740185505626038948830797119954343320083634703210690976197867936170995
....: 17770260029108149
....: c1 = 968606542352752022173681301950898396080375583888845227375006111212715
....: 71335123981588807994043800468529002147570655597610639680977780779494880330
....: 66946638978849704671031921337622839113802197638892517130776003005845693489
....: 87715894358362613172837439516145051368403646387069144244335667820449261116
....: 39955612412134198
....: c2 = 956685316641644831640847607294070371651074841669996560338049733894373
....: 06666566674562741460235838377684956374841385720908912461050182192222674655
....: 95710692705776272469703739932909158740030049375350999465338363044226512016
....: 68653424661104929998167423657796078652652793396668195448637746229819794932
....: 3271904405241585
....: a = c1 + c2
sage: b = c1 * c2
sage: PR.<m> = PolynomialRing(Zmod(n))
sage: f = m ^ 2 - a*m + b
sage: f.small_roots(X = 2 ^ 400)
[4242839043019782000788118887372132807371568279472499477998758466224002905442227156537788110520335652385855]最后long_to_byte就是flag。
[BJDCTF2020]伏羲六十四卦
题目如下：
ciphertext.txt:
这是什么，怎么看起来像是再算64卦！！！
密文:升随临损巽睽颐萃小过讼艮颐小过震蛊屯未济中孚艮困恒晋升损蛊萃蛊未济巽解艮贲未济观豫损蛊晋噬嗑晋旅解大畜困未济随蒙升解睽未济井困未济旅萃未济震蒙未济师涣归妹大有
嗯？为什么还有个b呢?
b=7
flag：请按照格式BJD{}
------------------------------------------------------------------------------------------------------------
我有没有用呢？.py
# -- coding:UTF-8 --
from secret import flag
def encrpyt5():
enc=''
for i in flag:
enc+=chr((a*(ord(i)-97)+b)%26+97)
return(enc)
def encrypt4():
temp=''
offset=5
for i in range(len(enc)):
temp+=chr(ord(enc[i])-offset-i)
return(temp)先是对64卦中的密文进行解密，因为在py文件中涉及到字符串，所以要构造出64卦的二进制数的字典。最后将二进制转为ASCII码，脚本如下：
import base64
cipher1 = "升随临损巽睽颐萃小过讼艮颐小过震蛊屯未济中孚艮困恒晋升损蛊萃蛊未济巽解艮贲未济观豫损蛊晋噬嗑晋旅解大畜困未济随蒙升解睽未济井困未济旅萃未济震蒙未济师涣归妹大有"
dic ={'坤': '000000', '剥': '000001', '比': '000010', '观': '000011', '豫': '000100', '晋': '000101', '萃': '000110', '否': '000111', '谦': '001000', '艮': '001001', '蹇': '001010', '渐': '001011', '小过': '001100', '旅': '001101', '咸': '001110', '遁': '001111', '师': '010000', '蒙': '010001', '坎': '010010', '涣': '010011', '解': '010100', '未济': '010101', '困': '010110', '讼': '010111', '升': '011000', '蛊': '011001', '井': '011010', '巽': '011011', '恒': '011100', '鼎': '011101', '大过': '011110', '姤': '011111', '复': '100000', '颐': '100001', '屯': '100010', '益': '100011', '震': '100100', '噬嗑': '100101', '随': '100110', '无妄': '100111', '明夷': '101000', '贲': '101001', '既济': '101010', '家人': '101011', '丰': '101100', '离': '101101', '革': '101110', '同人': '101111', '临': '110000', '损': '110001', '节': '110010', '中孚': '110011', '归妹': '110100', '睽': '110101', '兑': '110110', '履': '110111', '泰': '111000', '大畜': '111001', '需': '111010', '小畜': '111011', '大壮': '111100', '大有': '111101', '夬': '111110', '乾': '111111'}
k = 0
ans = ''
for i in range(0, len(cipher1)):
if k == 1:
k = 0
continue
try:
ans += dic[cipher1[i]]
except:
ans += dic[cipher1[i] + cipher1[i + 1]]
k = 1
#print(ans)
enc = ''
for i in range(0, len(ans), 8):
enc += chr(eval('0b' + ans[i:i + 8]))
print(enc)
#bl1oXF1ra2FbW2VpV1dfUmBiT11dYE5NVVdXSUZYSFVDUA==结果是一串base64密文，解密：
b64plainer = base64.b64decode(enc).decode()
print(b64plainer)
#n]h\\]kka[[eiWW_R`bO]]`NMUWWIFXHUCP最后再用到py文件的两个加密函数，分别构造出解密函数，由于不知道a是多少，所以直接进行爆破：
def decrypt5(enc):
for a in range(1, 200):
flag = ''
for i in enc:
for k in range(200):
if (ord(i) - 97 + k * 26 - 7) % a == 0:
flag += chr((ord(i) - 97 + k * 26 - 7) // a + 97)
break
print(flag)
plainer = decrypt4(b64plainer)
plainer = decrypt5(plainer)
#bjdcongratulationsongettingtheflag[UTCTF2020]OTP
题目如下：
Encoded A: 213c234c2322282057730b32492e720b35732b2124553d354c22352224237f1826283d7b0651
Encoded B: 3b3b463829225b3632630b542623767f39674431343b353435412223243b7f162028397a103e
Original A: 5448452042455354204354462043415445474f52592049532043525950544f47524150485921
Original B: 4e4f205448452042455354204f4e452049532042494e415259204558504c4f49544154494f4e
A XOR A: 7574666c61677b7477305f74696d335f703464737d7574666c61677b7477305f74696d335f70
B XOR B: 7574666c61677b7477305f74696d335f703464737d7574666c61677b7477305f74696d335f70一次一密，题目中的Encode A其实是Original A通过与某个数相异或而得到的，而题目恰恰给了这个神秘数字（key），所以我们就得到了flag，直接long_to_bytes()即可：
utflag{tw0_tim3_p4ds}utflag{tw0_tim3_p[NPUCTF2020]认清形势，建立信心
题目如下：
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
p = getPrime(25)
e = # Hidden
q = getPrime(25)
n = p * q
m = bytes_to_long(flag.strip(b"npuctf{").strip(b"}"))
c = pow(m, e, n)
print(c)
print(pow(2, e, n))
print(pow(4, e, n))
print(pow(8, e, n))
'''
169169912654178
128509160179202
518818742414340
358553002064450
'''根据题目提供的线索，有下列等式：
y1 = 2^e % n
y2 = 4^e % n
y3 = 8^e % n
其中y1、y2、y3是下面的三个数字。
经过变换有：y2 = y1^2 % n；y3 = y1 y2 % n。接着，我们通过y1^2 - y2 和 y1 y2 - y3找到二者的最小公因数。脚本如下：
c = 169169912654178
y1 = 128509160179202
y2 = 518818742414340
y3 = 358553002064450
print(gcd(y1**2 - y2, y1 * y2 - y3))
#1054494004042394去factordb分解，可得到p和q（其中2舍去，因为我们上面所构造出的等式其实都是基于以2为底的指数），然后再通过离散对数找到e，最后就是基本的RSA解密操作了。完整脚本如下：
from sympy import *
from gmpy2 import *
from Crypto.Util.number import *
c = 169169912654178
y1 = 128509160179202
y2 = 518818742414340
y3 = 358553002064450
#print(gcd(y1**2 - y2, y1 * y2 - y3))
p = 18195301
q = 28977097
n = p * q
phin = (p - 1) * (q - 1)
e = discrete_log(n, y1, 2)
d = inverse(e, phin)
m = pow(c, d, n)
print(long_to_bytes(m))[UTCTF2020]hill
题目如下：
wznqca{d4uqop0fk_q1nwofDbzg_eu}希尔密码：
26个字母一次编号：0、1、2、……25。把要加密的密文中的字符依次映射，放入到一个n*n的矩阵，加密的矩阵是自定义的，所以加密的过程是：
M * A = C
很显然要想得到M，那就得乘上A的逆矩阵。而本题可以先猜测前面的几个字符“utflag”，这样子就可以找到逆矩阵，假设n = 2，脚本如下：
import string
s='wznqcaduqopfkqnwofDbzgeu'
flag_pre = "utctf"
def getit(a1, b1, c1, a2, b2, c2, a3, b3, c3):
for i in range(26):
for j in range(26):
if(a1 * i + b1 * j) % 26 == c1 and (a2 * i + b2 * j) % 26 == c2 and (a3 * i + b3 * j) % 26 ==c3:
return(i, j)
x1=getit(22,25,20,13,16,5,2,0,0)
x2=getit(22,25,19,13,16,11,2,0,6)
flag = ""
for i in range(0, len(s), 2):
flag += string.ascii_letters[(string.ascii_letters.index(s[i]) * x1[0] + string.ascii_letters.index(s[i + 1]) * x1[1]) % 26]
flag += string.ascii_letters[(string.ascii_letters.index(s[i]) * x2[0] + string.ascii_letters.index(s[i + 1]) * x2[1]) % 26]
print(flag)
#utflag{d4nger0us_c1pherText_qq}
[De1CTF2019]babyrsa
题目如下：
import binascii
from data import e1,e2,p,q1p,q1q,hint,flag
n = [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L]
c = [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L]
f=lambda m,e,n,c:pow(m,e,n)==c
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)
ee1 = 42
ee2 = 3
ce1 = 45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
assert(pow(e1,ee1,n)==ce1)
assert(pow(e2+tmp,ee2,n)==ce2)
e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
hint=int(binascii.hexlify(hint),16)
assert(q1p*q1q==n)
assert(q1p<q1q)
assert(c==pow(hint,e,n))
flag=int(binascii.hexlify(flag),16)
q1=q1p
q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(c1==pow(flag,e1,p*q1))
assert(c2==pow(flag,e2,p*q2))看到最后的加密算法，用到了e1、e2、p、q1、q2等需要求解的数。首先看看p怎么求的吧，map函数将参数应用到f函数，相当于有4个p^4 %n = c，所以这里用到的是中国剩余定理。
转到第二段的e1和e2的加密算法，c1比n小数十个数量级，有可能是因为e1的42次方很小导致模n没有效果，所以直接对c1开42次方。ee2很小，直接用低加密指数攻击获取(e2+tmp)。
看到第三段加密算法，q1q和q1p相乘得到n，对n进行分解就可以得到了。hint内容：orz…you.found.me.but.sorry.no.hint…keep.on.and.enjoy.it!
来到最后一关，前面得到的e1和e2都不是素数，对它们进行分解后是2 x 7 x。。。，下面又只有两个密文，所以它的特征符合RSA相关信息攻击。前几天做到的funnyrsa2就是这种题型，所以可以直接引用前面做过的脚本，完整的脚本如下：
from Crypto.Util.number import *
import gmpy2
def CRT(a_list, m_list):
M = 1
for i in range(len(m_list)):
M *= m_list[i]
x = 0
for i in range(len(m_list)):
Mi = M // m_list[i]
Mi_inverse = inverse(Mi, m_list[i])
x += a_list[i] * Mi * Mi_inverse
x %= M
return x
n = [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791]
c = [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797]
p = gmpy2.iroot(CRT(c, n), 4)[0]
e = 46531
n = 16278524034278364842964386062476113517067911891699789991355982121084973951738324063305190630865511554888330215827724887964565979607808294168282995825864982603759381323048907814961279012375346497781046417204954101076457350988751188332353062731641153547102721113593787978587135707313755661153376485647168543680503160420091693269984008764444291289486805840439906620313162344057956594836197521501755378387944609246120662335790110901623740990451586621846212047950084207251595169141015645449217847180683357626383565631317253913942886396494396189837432429078251573229378917400841832190737518763297323901586866664595327850603
c = 14992132140996160330967307558503117255626925777426611978518339050671013041490724616892634911030918360867974894371539160853827180596100892180735770688723270765387697604426715670445270819626709364566478781273676115921657967761494619448095207169386364541164659123273236874649888236433399127407801843412677293516986398190165291102109310458304626261648346825196743539220198199366711858135271877662410355585767124059539217274691606825103355310348607611233052725805236763220343249873849646219850954945346791015858261715967952461021650307307454434510851869862964236227932964442289459508441345652423088404453536608812799355469
q1p = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
q1q = 127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088835693
phin1 = (q1p - 1) * (q1q - 1)
d = inverse(e, phin1)
m = pow(c, d, n)
print(long_to_bytes(m))
ee1 = 42
ee2 = 3
ce1 = 45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
e1 = gmpy2.iroot(ce1, ee1)[0]
#print(m1[0])
#15218928658178
k = 0
while 1:
ans = gmpy2.iroot(k * n + ce2, ee2)
if(ans[1] == True):
sum = ans[0]
break
k += 1
sum = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449290342499311738517
e2 = sum - tmp
#print(e2)
#381791429275130
q1 = q1p
q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c1 = 262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
assert(gmpy2.gcd(e1, (p - 1) * (q1 - 1)) == gmpy2.gcd(e2, (p - 1) * (q2 - 1)))
tmp = gmpy2.gcd(e1, (p - 1) * (q1 - 1))
e1 = e1 // tmp
e2 = e2 // tmp
d1 = inverse(e1, (p - 1) * (q1 - 1))
d2 = inverse(e2, (p - 1) * (q2 - 1))
m1 = pow(c1, d1, p * q1)
m2 = pow(c2, d2, p * q2)
m3 = m1 % p
m2 = m2 % q2
m1 = m1 % q1
alist = [m1, m2, m3]
mlist = [q1, q2, p]
m = CRT(alist, mlist)
n = q1 * q2
phin = (q1 - 1) * (q2 - 1)
d = inverse(7, phin)
m = pow(m, d, n)
print(long_to_bytes(gmpy2.iroot(m, 2)[0]))[QCTF2018]Xman-RSA
下面的加密脚本可以通过词频分析获得：
加密脚本：
from gmpy2 import is_prime
from os import urandom
import base64
def bytes_to_num(b):
return int(b.encode('hex'), 16)
def num_to_bytes(n):
b = hex(n)[2:-1]
b = '0' + b if len(b) % 2 == 1 else b
return b.decode('hex')
def get_a_prime(l):
random_Teed = urandom(l)
num = bytes_to_num(random_Teed)
while True:
if is_prime(num):
break
num+= 1
return num
def encrypt(s, e, n):
p = bytes_to_num(s)
p = pow(p, e, n)
return num_to_bytes(p).encode('hex')
def separate(n):
p = n % 4
t = (p * p) % 4
return t == 1
f = open('flag.txt', 'r')
flag = f.read()
msg1 = ""
msg2 = ""
for i in range(len(flag)):
if separate(i):
msg2 += flag[i]
else:
msg1 += flag[i]
p1 = get_a_prime(128)
p2 = get_a_prime(128)
p3 = get_a_prime(128)
n1 = p1 * p2
n2 = p1 * p3
e = 0x1001
c1 = encrypt(msg1, e, n1)
c2 = encrypt(msg2, e, n2)
print(c1)
print(c2)
#n1 encrypto
e1 = 0x1001
e2 = 0x101
p4 = get_a_prime(128)
p5 = get_a_prime(128)
n3 = p4 * p5
c1 = num_to_bytes(pow(n1, e1, n3)).encode('hex')
c2 = num_to_bytes(pow(n1, e2, n3)).encode('hex')
print(c1)
print(c2)
print(base64.b64encode(num_to_bytes(n2)))
print(base64.b64encode(num_to_bytes(n3)))脚本中除了separate()函数意外，其他函数可以通过库函数替代。有关flag的加密就是n1和n2，n1还通过了RSA加密。所以思路很清晰就是要先得到n1和n2，n1可以通过共模攻击求得，n2通过base64解密后转int。然后发现n1和n2有公因数，直接公因数分解两个n，最后通过RSA基操和separate()函数还原明文。脚本如下：
from Crypto.Util.number import *
from base64 import *
from gmpy2 import *
n2 = "PVNHb2BfGAnmxLrbKhgsYXRwWIL9eOj6K0s3I0slKHCTXTAUtZh3T0r+RoSlhpO3+77AY8P7WETYz2Jzuv5FV/mMODoFrM5fMyQsNt90VynR6J3Jv+fnPJPsm2hJ1Fqt7EKaVRwCbt6a4BdcRoHJsYN/+eh7k/X+FL5XM7viyvQxyFawQrhSV79FIoX6xfjtGW+uAeVF7DScRcl49dlwODhFD7SeLqzoYDJPIQS+VSb3YtvrDgdV+EhuS1bfWvkkXRijlJEpLrgWYmMdfsYX8u/+Ylf5xcBGn3hv1YhQrBCg77AHuUF2w/gJ/ADHFiMcH3ux3nqOsuwnbGSr7jA6Cw=="
n3 = "TmNVbWUhCXR1od3gBpM+HGMKK/4ErfIKITxomQ/QmNCZlzmmsNyPXQBiMEeUB8udO7lWjQTYGjD6k21xjThHTNDG4z6C2cNNPz73VIaNTGz0hrh6CmqDowFbyrk+rv53QSkVKPa8EZnFKwGz9B3zXimm1D+01cov7V/ZDfrHrEjsDkgK4ZlrQxPpZAPl+yqGlRK8soBKhY/PF3/GjbquRYeYKbagpUmWOhLnF4/+DP33ve/EpaSAPirZXzf8hyatL4/5tAZ0uNq9W6T4GoMG+N7aS2GeyUA2sLJMHymW4cFK5l5kUvjslRdXOHTmz5eHxqIV6TmSBQRgovUijlNamQ=="
n2 = b64decode(n2)
n3 = b64decode(n3)
n2 = bytes_to_long(n2)
n3 = bytes_to_long(n3)
n1_c1 = "2639c28e3609a4a8c953cca9c326e8e062756305ae8aee6efcd346458aade3ee8c2106ab9dfe5f470804f366af738aa493fd2dc26cb249a922e121287f3eddec0ed8dea89747dc57aed7cd2089d75c23a69bf601f490a64f73f6a583081ae3a7ed52238c13a95d3322065adba9053ee5b12f1de1873dbad9fbf4a50a2f58088df0fddfe2ed8ca1118c81268c8c0fd5572494276f4e48b5eb424f116e6f5e9d66da1b6b3a8f102539b690c1636e82906a46f3c5434d5b04ed7938861f8d453908970eccef07bf13f723d6fdd26a61be8b9462d0ddfbedc91886df194ea022e56c1780aa6c76b9f1c7d5ea743dc75cec3c805324e90ea577fa396a1effdafa3090"
n1_c2 = "42ff1157363d9cd10da64eb4382b6457ebb740dbef40ade9b24a174d0145adaa0115d86aa2fc2a41257f2b62486eaebb655925dac78dd8d13ab405aef5b8b8f9830094c712193500db49fb801e1368c73f88f6d8533c99c8e7259f8b9d1c926c47215ed327114f235ba8c873af7a0052aa2d32c52880db55c5615e5a1793b690c37efdd5e503f717bb8de716303e4d6c4116f62d81be852c5d36ef282a958d8c82cf3b458dcc8191dcc7b490f227d1562b1d57fbcf7bf4b78a5d90cd385fd79c8ca4688e7d62b3204aeaf9692ba4d4e44875eaa63642775846434f9ce51d138ca702d907849823b1e86896e4ea6223f93fae68b026cfe5fa5a665569a9e3948a"
n1_c1 = int(n1_c1, 16)
n1_c2 = int(n1_c2, 16)
n1_e1 = 0x1001
n1_e2 = 0x101
def exgcd(a , b):
if (b == 0):
return (b, 1, 0)
else:
d, x, y = exgcd(b, a % b)
return (d, y, x - (a // b) * y)
s = exgcd(n1_e1, n1_e2)
s1 = s[1]
s2 = s[2]
if (s1 < 0):
s1 = -s1
n1_c1 = inverse(n1_c1, n3)
elif (s2 < 0):
s2 = -s2
n1_c2 = inverse(n1_c2, n3)
n1 = pow(n1_c1,s1,n3) * pow(n1_c2,s2,n3) % n3
c1 = "1240198b148089290e375b999569f0d53c32d356b2e95f5acee070f016b3bef243d0b5e46d9ad7aa7dfe2f21bda920d0ac7ce7b1e48f22b2de410c6f391ce7c4347c65ffc9704ecb3068005e9f35cbbb7b27e0f7a18f4f42ae572d77aaa3ee189418d6a07bab7d93beaa365c98349d8599eb68d21313795f380f05f5b3dfdc6272635ede1f83d308c0fdb2baf444b9ee138132d0d532c3c7e60efb25b9bf9cb62dba9833aa3706344229bd6045f0877661a073b6deef2763452d0ad7ab3404ba494b93fd6dfdf4c28e4fe83a72884a99ddf15ca030ace978f2da87b79b4f504f1d15b5b96c654f6cd5179b72ed5f84d3a16a8f0d5bf6774e7fd98d27bf3c9839"
c2 = "129d5d4ab3f9e8017d4e6761702467bbeb1b884b6c4f8ff397d078a8c41186a3d52977fa2307d5b6a0ad01fedfc3ba7b70f776ba3790a43444fb954e5afd64b1a3abeb6507cf70a5eb44678a886adf81cb4848a35afb4db7cd7818f566c7e6e2911f5ababdbdd2d4ff9825827e58d48d5466e021a64599b3e867840c07e29582961f81643df07f678a61a9f9027ebd34094e272dfbdc4619fa0ac60f0189af785df77e7ec784e086cf692a7bf7113a7fb8446a65efa8b431c6f72c14bcfa49c9b491fb1d87f2570059e0f13166a85bb555b40549f45f04bc5dbd09d8b858a5382be6497d88197ffb86381085756365bd757ec3cdfa8a77ba1728ec2de596c5ab"
c1 = int(c1, 16)
c2 = int(c2, 16)
e = 0x1001
p = gcd(n1, n2)
n1_q = n1 // p
n2_q = n2 // p
phin1 = (p - 1) * (n1_q - 1)
phin2 = (p - 1) * (n2_q - 1)
d1 = inverse(e, phin1)
d2 = inverse(e, phin2)
flag1 = pow(c1, d1, n1)
flag2 = pow(c2, d2, n2)
flag1 = long_to_bytes(flag1).decode()
flag2 = long_to_bytes(flag2).decode()
def separate(n):
p = n % 4
t = (p * p) % 4
return t == 1
flag=''
length = len(flag1) + len(flag2)
index1 = 0
index2 = 0
for i in range(length):
if separate(i):
flag += flag2[index2]
index2 = index2 + 1
else:
flag += flag1[index1]
index1 = index1 + 1
print(flag)