title: buuctf题解
date: 2022-03-21 20:28:10
categories:
tags: 题解

[NCTF2019]childRSA

以下是题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag


def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

from Crypto.Util.number import isPrime, sieve_base as primes 是一个可以理解的在numpy或纯python中实现的主要筛子。重点是提供易于理解的筛子，而不是绝对最快的实现。虽然numpy的实现相当快，但能够在30秒内在我的中端笔记本电脑上计算出前1亿个素数。

先看p和q的生成，他是由若干个素数相乘最后加1，所以我们定义若干个素数相乘为pdr，也是（（p-1）或者（q-1））的倍数，所以可以设为k(p-1),再根据费马定理，a^(p-1)^=1 mod p ，所以a^k(p-1)^-1肯定是p的倍数，根据费马！2与p 互素，所以2^k(p-1)^-1与n的最大公约数就是p，再用n/p=q

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
import binascii
from Crypto.Util.number import isPrime, sieve_base as primes

e = 0x10001
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
#primes为前10000个素数的列表
#计算prd = ∏ primes
prd = 1
for i in primes:
    prd *= i
#p为(2^prd-1)和n的公约数
p = gmpy2.gcd(gmpy2.powmod(2,prd,n)-1,n)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))	#计算私钥d
m = gmpy2.powmod(c, d, n)    #解密

flag = binascii.unhexlify(hex(m)[2:])
print(flag)

[HDCTF2019]bbbbbbrsa

下面是题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from base64 import b64encode as b32encode
from gmpy2 import invert,gcd,iroot
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
import random

flag = "******************************"

nbit = 128

p = getPrime(nbit)
q = getPrime(nbit)
n = p*q

print p
print n

phi = (p-1)*(q-1)

e = random.randint(50000,70000)

while True:
	if gcd(e,phi) == 1:
		break;
	else:
		e -= 1;

c = pow(int(b2a_hex(flag),16),e,n)

print b32encode(str(c))[::-1]

# 2373740699529364991763589324200093466206785561836101840381622237225512234632

[::-1]意思是将其倒置；所以在base64解码的时候要先将其转过来,

解题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import base64
import gmpy2
from Crypto.Util.number import long_to_bytes
p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c = "==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM"
s=(c[::-1])
print(s)
b=base64.b64decode(s)
cf=2373740699529364991763589324200093466206785561836101840381622237225512234632
q=n//p
phi=(p-1)*(q-1)
print(phi)
for e in range(50000,70000):
    if(gmpy2.gcd(e,phi)==1):
        d=gmpy2.invert(e,phi)
        p
        flag=long_to_bytes(pow(cf,d,n))
        if b"flag" in flag:
            print(flag)
#flag{rs4_1s_s1mpl3!#}

[GWCTF 2019]BabyRSA

下面是题目：(下列两个题目都用到了sympy模块)

介绍一下sympy模块:SymPy 可以支持很多初等数学，高等数学，甚至研究生数学的符号计算。在初等数学和高等数学中，SymPy 可以支持的内容包括但不限于：

  1. 基础计算（Basic Operations）；

  2. 公式简化（Simplification）；

  3. 微积分（Calculus）；

  4. 解方程（Solver）；

  5. 矩阵（Matrices）；

  6. 几何（geometry）；

  7. 级数（Series）;

    在更多的数学领域中，SymPy 可以支持的内容包括但不限于：

    1. 范畴论（Category Theory）；
    2. 微分几何（Differential Geometry）；
    3. 常微分方程（ODE）；
    4. 偏微分方程（PDE）；
    5. 傅立叶变换（Fourier Transform）；
    6. 集合论（Set Theory）；
    7. 逻辑计算（Logic Theory）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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()

这些代码应该看得懂：就是将flag将其分成两份，分别为f1和f2，分别转为长数据；

解题思路：分解大整数N，然后求出e和phi(也就是(p-1) $\times$(q-1))，然后利用sympy模块；导入a,b,c.

用solve解决；

以下是解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
from sympy import *
from sympy.abc import a, b, c
from Crypto.Util.number import long_to_bytes
N=636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737
q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699
e=65537
d=gmpy2.invert(e,(p-1)*(q-1))
c1=pow(m1,d,N)
c2=pow(m2,d,N)

aa = solve([a + b - c1, pow(a, 3) + pow(b, 3) - c2], [a, b])
print(aa)
f1=1141553212031156130619789508463772513350070909
f2=1590956290598033029862556611630426044507841845
print(long_to_bytes(f2)+long_to_bytes(f1))
#GWHT{f709e0e2cfe7e530ca8972959a1033b2}
#flag{f709e0e2cfe7e530ca8972959a1033b2}

[BJDCTF2020]easyrsa

题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import getPrime,bytes_to_long
from sympy import Derivative #求导函数
from fractions import Fraction #分子在前，分母在后。
from secret import flag

p=getPrime(1024)
q=getPrime(1024)
e=65537
n=p*q
z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))
m=bytes_to_long(flag)
c=pow(m,e,n)
print(c,z,n)
'''
output:
7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441

'''

原理很简单：已知c,e,n,z。求p和q，由z=Fraction(1,Derivative(arctan(p),p))-Fraction(1,Derivative(arth(q),q))这串代码可知：z=p^2^+q^2^

又因为n=p $\times$ q,所以可知q+p等于sqrt(z+2 $\times$ n),q-p等于sqrt(z-2 $\times$ n),剩下的就容易了

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
c=7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035
z=32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482
n=15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441
import math
from gmpy2 import invert,iroot
from Crypto.Util.number import long_to_bytes
x=iroot(z+2*n,2)[0]
y=iroot(z-2*n,2)[0]
q=(x+y)//2
p=n//q
e=65537
d=invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

可怜的RSA

题目给出了两个文件：一个是flag.enc,一个是public.key公钥，对于此类题目肯定要进行公钥分析，在public.key中提取e和n。

下面是提取公钥代码：

1
2
3
4
5
6
7
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用factor.pq分解求出p,q.

接下来就好写了

代码上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from base64 import b64decode
n = 79832181757332818552764610761349592984614744432279135328398999801627880283610900361281249973175805069916210179560506497075132524902086881120372213626641879468491936860976686933630869673826972619938321951599146744807653301076026577949579618331502776303983485566046485431039541708467141408260220098592761245010678592347501894176269580510459729633673468068467144199744563731826362102608811033400887813754780282628099443490170016087838606998017490456601315802448567772411623826281747245660954245413781519794295336197555688543537992197142258053220453757666537840276416475602759374950715283890232230741542737319569819793988431443
e = 65537
d=406853230956379689450620815713768871010712825839536410687962650677800895818003893712259622281477453292088146173840036827322518131453630576229976208523593618949818777897059256426591560532784635697190752924923710375949616954069804342573867253630978123632384795587951365482103468722384133084798614863870775897915929475258974188300927376911833763105616386167881813301748585233563049693794370642976326692672223638908164822104832415788577945314264232531947860576966629150456995512932232264881080618006698700677529111454508900582785420549466798020451488168615035256292977390692401388790460066327347700109341639992159475755036449
p = 3133337
q = 25478326064937419292200172136399497719081842914528228316455906211693118321971399936004729134841162974144246271486439695786036588117424611881955950996219646807378822278285638261582099108339438949573034101215141156156408742843820048066830863814362379885720395082318462850002901605689761876319151147352730090957556940842144299887394678743607766937828094478336401159449035878306853716216548374273462386508307367713112073004011383418967894930554067582453248981022011922883374442736848045920676341361871231787163441467533076890081721882179369168787287724769642665399992556052144845878600126283968890273067575342061776244939
key_info = RSA.construct((n, e, d, p, q))
key = RSA.importKey(key_info.exportKey())
key = PKCS1_OAEP.new(key)
f = open('flag.enc', 'r').read()
c = b64decode(f)
flag = key.decrypt(c)
print(flag)#afctf{R54_|5_$0_B0rin9}#flag{R54_|5_$0_B0rin9}

[NCTF2019]babyRSA

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from flag import flag
def nextPrime(n):    
    n += 2 if n & 1 else 1
    while not isPrime(n):        
        n += 2    
        return n
    p = getPrime(1024)
    q = nextPrime(p)
    n = p * q
    e = 0x10001
    d = inverse(e, (p-1) * (q-1))
    c = pow(bytes_to_long(flag.encode()), e, n)
    # d = 19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913# c = 5382723168073828110696168558294206681757991149022777821127563301413483223874527233300721180839298617076705685041174247415826157096583055069337393987892262764211225227035880754417457056723909135525244957935906902665679777101130111392780237502928656225705262431431953003520093932924375902111280077255205118217436744112064069429678632923259898627997145803892753989255615273140300021040654505901442787810653626524305706316663169341797205752938755590056568986738227803487467274114398257187962140796551136220532809687606867385639367743705527511680719955380746377631156468689844150878381460560990755652899449340045313521804

题目给出了e和d；由此想到RSA的算法 e $\times$d$\equiv$1 mod phi(n)，因为已知e和d，可以知道ed-1是n的倍数，所以k(p-1)(q-1)等于ed-1

我们从二进制位数分析：

1
2
3
4
5
6
7
8
9
d=19275778946037899718035455438175509175723911466127462154506916564101519923603308900331427601983476886255849200332374081996442976307058597390881168155862238533018621944733299208108185814179466844504468163200369996564265921022888670062554504758512453217434777820468049494313818291727050400752551716550403647148197148884408264686846693842118387217753516963449753809860354047619256787869400297858568139700396567519469825398575103885487624463424429913017729585620877168171603444111464692841379661112075123399343270610272287865200880398193573260848268633461983435015031227070217852728240847398084414687146397303110709214913
e=65537
print(e.bit_length())
print(d.bit_length())
s=e*d-1
r=2**16
print(s.bit_length())
print(d.bit_length())
print(s.bit_length()//r.bit_length())

因为p $\times$q二进制位数大于2048位数，又因为ed-1的位数位2064，且看我的代码可得d的二进制位数位2048，e为17，所以k的位数肯定小于17，所以可得k值在小于2^16^；

所以写代码可得：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
e=0x10001
d = 
c = 
import sympy.crypto
import gmpy2
e_d_1=e*d-1
p=0
q=0
for k in range(pow(2,15),pow(2,16)):
    if e_d_1%k==0:
        p=sympy.prevprime(gmpy2.iroot(e_d_1//k,2)[0])    #开根号求出比根号小的一个素数。叫作先前质数
        q=sympy.nextprime(p)       #意思为p的下一个素数
        if (p-1)*(q-1)*k==e_d_1:
                     break
n=p*q
print(n)
m=gmpy2.powmod(c,d,n)
print(m)
import binascii
print(binascii.unhexlify(hex(m)[2:]))
#NCTF{70u2_nn47h_14_v3ry_gOO0000000d}

Samemod

题目如下：

1
2
3
4
5
6
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,773}
{6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249,839}

message1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
message2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

解题思路：

一眼就知道共模攻击，但是解出m的时进行编码时发现出不来flag，但是我们发现明文数字中，有flag的敏感数字，102，97，等；于是我们用Ascll编码可解；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

from gmpy2 import invert, gcdext
n= 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
e1= 773
e2= 839
c1= 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
c2= 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535

s = gcdext(e1, e2)
m = pow(c1, s[1], n) * pow(c2, s[2], n) % n
print(m)
#1021089710312311910410111011910111610410511010710511610511511211111511510598108101125
#flag=hex(result)[2:].decode('hex')
result=str(m)
flag=""
i=0
while i < len(result):
    if result[i]=='1':
        c=chr(int(result[i:i+3]))                            #这边的一大坨是用脚本分开这些数字进行编码；
        i+=3
    else:
        c=chr(int(result[i:i+2]))
        i+=2
    flag+=c
print(flag)
#flag{whenwethinkitispossible}
cipher=[102,108,97,103,123,119,104,101,110,119,101,116,104,105,110,107,105,116,105,115,112,111,115,115,105,98,108,101,125]
flag=""
for i in range(len(cipher)):                         #这里呢，可以自己手动，数字不大，很方便；
    flag+=chr(cipher[i])
print(flag)
#1021089710312311910410111011910111610410511010710511610511511211111511510598108101125
#flag{whenwethinkitispossible}
#flag{whenwethinkitispossible}

[RoarCTF2019]RSA

以下是题目：

1
2
3
4
5
6
7
A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x
p=next_prime(z*x*y)
q=next_prime(z)
A =  2683349182678714524247469512793476009861014781004924905484127480308161377768192868061561886577048646432382128960881487463427414176114486885830693959404989743229103516924432512724195654425703453612710310587164417035878308390676612592848750287387318129424195208623440294647817367740878211949147526287091298307480502897462279102572556822231669438279317474828479089719046386411971105448723910594710418093977044179949800373224354729179833393219827789389078869290217569511230868967647963089430594258815146362187250855166897553056073744582946148472068334167445499314471518357535261186318756327890016183228412253724
n =  117930806043507374325982291823027285148807239117987369609583515353889814856088099671454394340816761242974462268435911765045576377767711593100416932019831889059333166946263184861287975722954992219766493089630810876984781113645362450398009234556085330943125568377741065242183073882558834603430862598066786475299918395341014877416901185392905676043795425126968745185649565106322336954427505104906770493155723995382318346714944184577894150229037758434597242564815299174950147754426950251419204917376517360505024549691723683358170823416757973059354784142601436519500811159036795034676360028928301979780528294114933347127
c =  41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128

解题思路：

此题有点奇怪；用它的算法去算p和q，有点算不出，因为未知量太多，关键是x和y未知；所以我想到了一个好工具，yahu分解；

分解可以得到p和q，剩下的迎刃而解；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import gmpy2
import sympy

p=139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183
q=842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569

c=41971850275428383625653350824107291609587853887037624239544762751558838294718672159979929266922528917912189124713273673948051464226519605803745171340724343705832198554680196798623263806617998072496026019940476324971696928551159371970207365741517064295956376809297272541800647747885170905737868568000101029143923792003486793278197051326716680212726111099439262589341050943913401067673851885114314709706016622157285023272496793595281054074260451116213815934843317894898883215362289599366101018081513215120728297131352439066930452281829446586562062242527329672575620261776042653626411730955819001674118193293313612128
n=p*q
phin=(p-1)*(q-1)
from Crypto.Util.number import *
e=3
while(e<0x10003):                   #因为不知道e，所以我们进行爆破，假设它小于65539；
    try:
        d=gmpy2.invert(e,phin)
        #print d,e
        m=pow(c,d,n)
        flag = long_to_bytes(m)
        if b"CTF" in flag:
            print (flag)
    except:
        pass
    e = sympy.nextprime(e)
#b'RoarCTF{wm-l1l1ll1l1l1l111ll}'
#跑上30秒左右可得；

坏蛋是雷宾

题目：

老牌刺客之王混进了女王的住所。一天，女王得到了一个匿名举报，说她的侍卫里有一个刺客，叫做Rabin，而他的信息就在一份文件里，文件中有附带一个Pk，是523798549，密文是162853095，校验码二进制值是110001，根据说明是放在明文后一起加密的，明文与密文长度相同。加密算法和这位老牌刺客同名。快拯救女王，答案是求得的明文，进行32位md5小写哈希字符串，提交即可。 注意：得到的 flag 请包上 flag{} 提交

解题：很明显已经告诉你算法是rabin(RAS的衍生)非对称加密，由题意得N=523798549，c=162853095，效验位110001；

先普及一下什么是rabin(他的加密方式是怎样的？)；

再引入一张加强理解：

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from gmpy2 import *
from Crypto.Util.number import *
import base64

N = 523798549
c=162853095
p=10663
q=49123
e=2


c_p=pow(c,(p+1)//4,p)
c_q=pow(c,(q+1)//4,q)

a=invert(p,q)
b=invert(q,p)
x=(a*p*c_q+b*q*c_p) % N
y=(a*p*c_q-b*q*c_p) % N
o=N-x
p=N-y


print(bin(x%N))
print(bin(y%N))
print(bin(o))
print(bin(p))
l="10010011100100100101010" #这是提出效验位之后的数字；效验位就是让你找到flag
import hashlib
data = str(int(l,2))
v=hashlib.md5(data.encode(encoding='UTF-8')).hexdigest()
print(v)

[NPUCTF2020]EzRSA

题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from gmpy2 import lcm , powmod , invert , gcd , mpz
from Crypto.Util.number import getPrime
from sympy import nextprime
from random import randint
import math
from decimal import Decimal


p = getPrime(1024)
q = getPrime(1024)
n = p * q
gift = lcm(p - 1 , q - 1)
e = 54722
flag = b'NPUCTF{******************}'
m = int.from_bytes(flag , 'big')
c = powmod(m , e , n)
print('n: ' , n)
print('gift: ' , gift)
print('c: ' , c)
e=54722
n=17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
gift=2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
c=3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319

题目意思就是让你求phi(n),我们可以从位数来进行分析；我们知道，phi(n)//(除)lcm((p-1),(q-1))等于最大公约数，说明k倍的lcm等于phi(n),通过位数分得到，gift的位数是2045，且n的位数通常是2048，所以我们可以进行爆破，k小于2^3^.以下是解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import  gmpy2
from Crypto.Util.number import long_to_bytes
e = 54722
n=  17083941230213489700426636484487738282426471494607098847295335339638177583685457921198569105417734668692072727759139358207667248703952436680183153327606147421932365889983347282046439156176685765143620637107347870401946946501620531665573668068349080410807996582297505889946205052879002028936125315312256470583622913646319779125559691270916064588684997382451412747432722966919513413709987353038375477178385125453567111965259721484997156799355617642131569095810304077131053588483057244340742751804935494087687363416921314041547093118565767609667033859583125275322077617576783247853718516166743858265291135353895239981121
gift=  2135492653776686212553329560560967285303308936825887355911916917454772197960682240149821138177216833586509090969892419775958406087994054585022894165950768427741545736247918410255804894522085720642952579638418483800243368312702566458196708508543635051350999572787188236243275631609875253617015664414032058822919469443284453403064076232765024248435543326597418851751586308514540124571309152787559712950209357825576896132278045112177910266019741013995106579484868768251084453338417115483515132869594712162052362083414163954681306259137057581036657441897428432575924018950961141822554251369262248368899977337886190114104
c= 3738960639194737957667684143565005503596276451617922474669745529299929395507971435311181578387223323429323286927370576955078618335757508161263585164126047545413028829873269342924092339298957635079736446851837414357757312525158356579607212496060244403765822636515347192211817658170822313646743520831977673861869637519843133863288550058359429455052676323196728280408508614527953057214779165450356577820378810467527006377296194102671360302059901897977339728292345132827184227155061326328585640019916328847372295754472832318258636054663091475801235050657401857262960415898483713074139212596685365780269667500271108538319
print(gift.bit_length())
e= e//2
for i in range(8):
    phi = gift*i
    try:
        d= gmpy2.invert(e,phi)
        m= pow(c,int(d),n)
        flag=long_to_bytes(gmpy2.iroot(m,2)[0])
        if  b'NPUCTF' in flag:
           print(flag)
    except ZeroDivisionError:
        continue

#[网鼎杯 2020 青龙组]you_raise_me_up

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
import random

n = 2 ** 512
m = random.randint(2, n-1) | 1
c = pow(m, bytes_to_long(flag), n)
print 'm = ' + str(m)
print 'c = ' + str(c)

# m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
# c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499

代码应该不难看懂，意思就是m^flag^mod n,求指数flag，这里的考点是离散对数，所以我们导入模块，sympy。解题代码如下：

1
2
3
4
5
6
7
8
9
from sympy.ntheory import discrete_log #这里是离散对数函数；
a="0x666c61677b35663935636139332d313539342d373632642d656430622d6139313339363932636234617d"
b=int(a,16)
n = 2**512
m = 391190709124527428959489662565274039318305952172936859403855079581402770986890308469084735451207885386318986881041563704825943945069343345307381099559075
c = 6665851394203214245856789450723658632520816791621796775909766895233000234023642878786025644953797995373211308485605397024123180085924117610802485972584499
flag_dec = discrete_log(n,c,m) #得到flag的十进制值
print(hex(flag_dec)) #转为十六进制后打印出来
print(bytes.fromhex(hex(b)[2:]))

[RoarCTF2019]babyRSA

以下是题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sympy
import random

def myGetPrime():
    A= getPrime(513)
    print(A)
    B=A-random.randint(1e3,1e5)
    print(B)
    return sympy.nextPrime((B!)%A)
p=myGetPrime()
#A1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
#B1=21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596

q=myGetPrime()
#A2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
#B2=16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026

r=myGetPrime()

n=p*q*r
#n=85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
c=pow(flag,e,n)
#e=0x1001
#c=75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
#so,what is the flag?

题目解析：A的选取是从函数getprime中选取的，然后等于A减去一个10^3^到10^5^之间的一个数，我们直接求阶乘肯定算不出来，所以我们观察可以得到，这里考察的威尔逊定理：由威尔逊可得：(A-1)!$\equiv$-1 mod A;题目返回的是B!%A,可以说用凑来解这个题目吧，设K*B！$\equiv$ -1 mod A;k等于(A-1)!/(B!),这样的计算量大大减少，就是B+1后面的阶乘。所以我们两边同时乘k的模逆，就可以求得：B！$\equiv$ -K^-1^mod A;

所以B!%A就等于k的模逆；以下是解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import gmpy2
import sympy
import binascii


# p = sympy.nextPrime((B!)%A)
def getPrime(A, B):
    k = 1
    for i in range(B + 1, A):
        k = (k * i)% A
    res = (-gmpy2.invert(k, A))%A
    return sympy.nextprime(res)


if __name__ == '__main__':
    A1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467234407
    B1 = 21856963452461630437348278434191434000066076750419027493852463513469865262064340836613831066602300959772632397773487317560339056658299954464169264467140596
    A2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858418927
    B2 = 16466113115839228119767887899308820025749260933863446888224167169857612178664139545726340867406790754560227516013796269941438076818194617030304851858351026
    n = 85492663786275292159831603391083876175149354309327673008716627650718160585639723100793347534649628330416631255660901307533909900431413447524262332232659153047067908693481947121069070451562822417357656432171870951184673132554213690123308042697361969986360375060954702920656364144154145812838558365334172935931441424096270206140691814662318562696925767991937369782627908408239087358033165410020690152067715711112732252038588432896758405898709010342467882264362733
    e = 0x1001
    c = 75700883021669577739329316795450706204502635802310731477156998834710820770245219468703245302009998932067080383977560299708060476222089630209972629755965140317526034680452483360917378812244365884527186056341888615564335560765053550155758362271622330017433403027261127561225585912484777829588501213961110690451987625502701331485141639684356427316905122995759825241133872734362716041819819948645662803292418802204430874521342108413623635150475963121220095236776428
    p = getPrime(A1, B1)
    q = getPrime(A2, B2)
    r = n // (p * q)
    d = gmpy2.invert(e, (p - 1) * (q - 1) * (r - 1))
    m = gmpy2.powmod(c, d, n)
    flag = bytes.fromhex(hex(m)[2:])
    print(flag)
#RoarCTF{wm-CongrAtu1ation4-1t4-ju4t-A-bAby-R4A}

RSA & what

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from Crypto.Util.number import bytes_to_long, getPrime
from random import randint
from gmpy2 import powmod

p = getPrime(2048)
q = getPrime(2048)
N = p*q
Phi = (p-1)*(q-1)
def get_enc_key(N,Phi):
    e = getPrime(N)
    if Phi % e == 0:
        return get_enc_key(N, Phi)
    else:
        return e
e1 = get_enc_key(randint(10, 12), Phi)
e2 = get_enc_key(randint(10, 12), Phi)

fr = open(r"./base64", "rb")#flag is in this file
f1 = open(r"./HUB1", "wb")
f2 = open(r"./HUB2", "wb")
base64 = fr.read(255)
f1.write("%d\n%d\n" % (N, e1))
f2.write("%d\n%d\n" % (N, e2))
while len(base64)>0:
    pt = bytes_to_long(base64)
    ct1 = powmod(pt, e1, N)
    ct2 = powmod(pt, e2, N)
    f1.write("\n%d" % ct1)
    f2.write("\n%d" % ct2)
    base64 = fr.read(255)
fr.close()
f1.close()
f2.close()
还有三个文件：Hub1，Hub2，和一个提示用base64；大家应该知道那些大整数对应什么；所以在这里不在强调；我们看到文件里面的n相同，所以想到共模攻击；

共模解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from gmpy2 import*
from libnum import*
from Crypto.Util.number import*
import base64
import binascii

N =785095419718268286866508214304816985447077293766819398728046411166917810820484759314291028976498223661229395009474063173705162627037610993539617751905443039278227583504604808251931083818909467613277587874545761074364427549966555519371913859875313577282243053150056274667798049694695703660313532933165449312949725581708965417273055582216295994587600975970124811496270080896977076946000102701030260990598181466447208054713391526313700681341093922240317428173599031624125155188216489476825606191521182034969120343287691181300399683515414809262700457525876691808180257730351707673660380698973884642306898810000633684878715402823143549139850732982897459698089649561190746850698130299458080255582312696873149210028240898137822888492559957665067936573356367589784593119016624072433872744537432005911668494455733330689385141214653091888017782049043434862620306783436169856564175929871100669913438980899219579329897753233450934770193915434791427728636586218049874617231705308003720066269312729135764175698611068808404054125581540114956463603240222497919384691718744014002554201602395969312999994159599536026359879060218056496345745457493919771337601177449899066579857630036350871090452649830775029695488575574985078428560054253180863725364147
e2 = 599
c21=592169079372093727306100216011395857825646323934289480976073629037543922902098120901138454462177159996376654176248238979132528728327590301098966139983157980612320563496546128644967731000716697705104079039156276714872147463350811303393260622707024952543509891692246246277965823414460326811240048060543656588688604452353899779068825120910282167004715339763187734797180326976132213325054697165320479166356562518029805927741656605174809726397565772271562066078076105491745903986597877400370206718954975288721072048333678609055008135809089304229015364348490924974097403734627265297637171818849461766523691595241613878709865506436588268999163342945070495338153600520537498539457396582804692959296612715752573140296135784933206146091436617979599749774330699946637591406356289409716084034451049094715202196203486088368791744107629271647320273259836915312794297246589501008666299165717722507702866033454215783240025504356157664454861755286285777763585177751796252655008206383024707883077513745863312079349790275094080707502392866946325796914450602264462588722052297430827681750827349094323968337670311272933785838850649376115667223821665435911506351891489985627506615492005617098615432522564204152887767244129985681083657783356557756654335186
c22=373940646416832740878733255707567753033716583448402000789202767511920210382830343955553654111486728333980557319799362514960627879016797491389812007768832730979916230647641872759001906846747977631675704310179448857128160385701185892914523053669366534408863734305635222625590986006420486092550427301086984563126480814987024980594613542978310129247678826691418335300577577527951623696426435497835228167084738007750914270251001921329521479047662848650808989996085600197309361410863238526802127877523767262921515150984998560136647154865791163316503073285223966216441025637452229043510097323724381056976302288136843260163922706692913035222445496716008888946581535004546355744211680390731257309941902587303353139951102244865270295414474488798335404630458489706639805186573874814586736746232358849677477533671968344154242963289415569487579895910660999043578737461300406937828924818002658292769882181668784501439254131996848948120781562158861495883827848139425862249576454689133681009549361314460818658995959098228995702202268649635363105549975932395335076521137604288520082040121286614922986554652700056148966514178935952363036963217619879899671383604638416567950421350546204434902113156720006282720889591288850271076074941927715678306057176
c23=527630926460622936571385649841758214453416849039412401087443444317101857090904711485538107058823056085840539073345920792871368232355475394571098380596835468509997340505604333730547799560998822989747473780307779717715522787724471724766494090783971030594671013168209717686720448579582618378459567979027822271918653169622428153856198907810040224340270362413432495029672123261375400927159831537760709974778708160583252613784358234858583174544777979242887938827573604837766801998381379999076416444683891078093889686055482709838668356120916040352123019019255084513769603803814947774554028717814638951416291274696771515474086351482107953150253616922787262398450376249126999644026382478413080973933173079111305142716133389111399235545279259017424722601848670061556859163943895466553927946412523750166582734005733378328468250568944945912238495877929717101722314678120172228493787964904072583905721074766711732215815561012960394537195757832959268603775112932862105945720853959285187521763557915356428113876893276879775603217718981852114599706699524551973934242045743122744146361596971245034059345915315495232135483464496114770357536576200511490922413208178149869347802988786513451486411409887164516065062084917556120712465074206435831498113605
c24=8786437178698940322877889807009957616777351844979869726962356553244050911283984280960665761649310895230455072977431415102053987735969326553978994853162483051544656873294555116009995592043183070208706258164840540599577072097104139505857517663273929851202628854185356185647194933800084230503413037858893307713037149307477830536758283681093517617820169181420796105338681582230788318108428132051793761014952837330456262272828627355701464740578197966332613127307037255647286823496355917642353327912440019621838870388091824748629637425759125214639885130163183752378908729773517053259212525494555880921052679512582051516604297098204363525081039382358483926727008679327719083138865969291911863630382097160230960738043575559330264018212774424527719153248563876760067931499029384228993253862501939337758514377472011933279273181144830381169849387893799390755052093069179605579485710343655570028592595882436632426527654452895431758715126580164902410286422637215098476316042367916779431052267545769495994723721129943616294879642305545894912914632980455031755879087401575310699765408473606166727137934224515998416625122213056208800095077933103150699272650116151674702438463062734472714004926103668378506804002740045547964716693536349447660850580
c25=205314962204511500352858372254132533167549960825498949618514841570703199264867431580754674275990554478140637041427842111391746883257447120035947621456863890934062044010795443059281736346976175772415034838334682726635263432655537852942177334888025283748611576171534251461847349566505628290587224150869640386437623371249743165260396675220683302142805646368906930575140628610003919131999295855501215111393294818218799982703289304596989070475000081175510085432290264502023736899104746316830742226946395027029820825791831870857382647221322734605026210073093918331247494307555600335550942340526536281372036612138713881098866303169425501998978400008829873080965592009371176208668290074288903681417933657472279670688597862835627506340169978450918788539270346340385928840299573889292189531738082166408734046381423516467694328971385421907314814283489322619386570046183556572383980777277173349209330683424343658179781015072259378576130442222984963071166207642585589822061597282467850868050737957726423713761694231879497037175627546427449730638216214828463003483408928375620315193290871300316930139260521382533279767663839278693750409419493280753368451508802658272220767624766390639285308433607255253282702383762149755935518922075584637512494819
c26=271453634732502613378948161256470991260052778799128789839624515809143527363206813219580098196957510291648493698144497567392065251244844074992734669490296293997386198359280316655904691639367482203210051809125904410431506925238374843856343243276508280641059690938930957474434518308646618959004216831130099873532714372402117796666560677624822509159287675432413016478948594640872091688482149004426363946048517480052906306290126242866034249478040406351940088231081456109195799442996799641647167552689564613346415247906852055588498305665928450828756152103096629274760601528737639415361467941349982213641454967962723875032638267311935042334584913897338553953961877439389588793074211502597238465542889335363559052368180212013206172712561221352833891640659020253527584706465205486408990762759230842192028381048563437724528409174790022752557512795782713125166158329880702730769957185428522011430144840232256419113631679343171680631630775266488738173707357123139368825087043785842169049943237537188129367275730984789479909103397937113837824575137021012333461552176687570010445744268373840742899299977372834041925102853718964831225250407279578465008537542659673685686242773379131904890865110699190451534445434533919127658976874721029586168106207

e1 = 1697
c11=412629526163150748619328091306742267675740578011800062477174189782151273970783531227579758540364970485350157944321579108232221072397135934034064481497887079641131808838242743811511451355024436983050572020925065644355566434625618133203024215941534926113892937988520918939061441606915556516246057349589921494351383160036280826024605351878408056180907759973804117263002554923041750587548819746346813966673034182913325507826219961923932100526305289894965216608254252188398580139545189681875824089456195044984585824938384521905334289906422454152976834867304693292466676355760173232407753256256317546190171995276258924613533179898467683358934751999655196790168438343198229183747091108262988777659858609744709324571850262293294975336628234767258858873839342596887193772615000676401522431518310648303975593582965021189182246986957349253156736526071639973844039068996404290548474640668851856078201093335425412842295604919065487301340901573809617549185106072798799159726375235125260509158832996701927878713084753334549129580912412168594170659605421750204835970231909591063407612779337478065175988365401590396247576709343727196106058477166945670117868989025903023998142850338956985816131805349549059377047477131270847579095628384569645636821650
c12=494644347943710545224678831941589086572700792465459558770782213550069709458568349686998660541810166872034041584767487150140111151788221460027897193248273461607411027815984883969396220626358625041781558277804930212654296704055890683796941327712758797770820006623289146990000114915293539639766846910274034245607746230740851938158390562286057002223177609606376329007676845450142537930798148258428701466415483232670659815791064681384406494388237742330786225557303988025468036820082959712050733095860546860468575857084616069132051094882919253745234762029759124776348047587755897123575123506976140900565238840752841856713613368250071926171873213897914794115466890719123299469964019450899291410760762179836946570945555295288184698184555018368687708432612286248476073758067175481771199066581572870175460016017100414479346437034291784837132240891321931601494414908927713208448927221095745802380014441841139882391378410438764884597938773868771896252329517440068673532468372840830510218585255432000690265226016573313570977945083879214961394087065558376158826938257664840570952233832852869328785568175434516247720356520242602299510374317488182738732700078879665745909603766482100138001417023680647717824323143388857817595766172152883484274718248
c13=152942283599728307168144137370127212672611894072038732126041098102628831053000986759260271210671922070555948023688596575415822984026159010574404359474670428678518262175033880513984372909748992727828381694416776740981021730545374002974037896534944567124543272737618380646771071804878796585983783360553761828325817820260204820004421979881871027255562690952334900616675606524933557440263648233514757200263521499508373975003431306847453046714027687108396945719803444444954079308404947126216395526551292104722047878178373207886033071857277857997932255251315982837892164421298202073945919187779856785892717251746704537315003771369737854896595170485152591013676942418134278534037654467840633528916812275267230155352077736583130992587670941654695382287023971261529987384520843829695778029311786431227409189019205818351911572757145556993606643464336196802350204616056286497246016800105003143046120608673496196758720552776772796609670537056331996894322779267635281472481559819839042424017171718303214059720568484939239370144038161541354254182769979771948759413102933987773401644506930205164891773826513161783736386604783484446345744957119469799231796368324927570694496679453313927562345656690240414624431304646248599226046524702364131095964335
c14=79717988936247951265489157583697956031893477858854186991051529161879478488281744062318600470906120960002282886511477294555606503083169449335174864424180701080203993329996226566203834693869525797695969610065991941396723959032680019082506816443041598300477625793433080664346470586416385854692124426348587211026568667694805849554780794033764714016521711467557284846737236374990121316809833819996821592832639024026411520407330206281265390130763948165694574512140518775603040182029818771866749548761938870605590174330887949847420877829240131490902432602005681085180807294176837646062568094875766945890382971790015490163385088144673549085079635083262975154206269679142412897438231719704933258660779310737302680265445437771977749959110744959368586293082016067927548564967400845992380076107522755566531760628823374519718763740378295585535591752887339222947397184116326706799921515431185636740825707782742373783475781052674257292910213843986132987466810027275052416774693363446184518901899202502828670309452622347532932678874990809930682575738653876289384151496807194146308614368821006660626870989784697045160231069428458961107751207771093777394616856305293335603892178327520756554333365975114235981173451368131680404850832773147333013716920
c15=123111353650401158556639983459870663057297871992927053886971224773529636525110628183715748795987525113177540092814119928708272290370336537110381023134637759740716140969662183269370676630325583385284994943164692397459103195434968057377474610500216801375394703781249039351368816958227409657934091741509357152328382960684515093945552479461382281913961956745154260686029997827565075768703774895750561575155143606297116391666385705899138085693913246313778033627210312268959737394553510894720099165193981333775907531107232556909478156441457899797515694348816961762796703443502856101079430585547997496001098926600499728389113862894833789669213630332988693669889340482430613291490613803204484751470676686041002772556117213612152322606737150858116122936539131795111263513114569794532805886643087299918196635113037777138666914296986040549274559835214505300618256105508764026461518876579387159881983544667258537064954616097750399839661065797883103731694314852301848272092388637114950059216922969842082648527035538090054093890365647676119748995243416337805666557501345234056968476142608491830438065401219751688687373709390057521910942736632126729711606256158399963682990881473178216060827021373776598901281958527655543318413664277921492723185984
c16=36869806815936046911848195817405817350259890871483063184373728397968909458432625046025376290214729914038387534731762237978339011724858818860181178811639468996206294711495853807311240013786226884265118119546377272154555615363105236192878292703331473547623021744317034819416624562896226194523639793573028006666236271812390759036235867495803255905843636447252225413871038762657801345647584493917576263471587347202664391908570140389126903204602391093990827188675090199750617303773574821926387194478875191828814971296674530519321530805302667925998711835019806761133078403281404889374663875077339168901297819436499920958268483684335998301056068380228873524800383911402490807139268964095165069610454677558808756444381542173782815227920906224931028457073652453777424387873533280455944646592996920617956675786286711447540353883400282402551158169958389450168079568459656526911857835375748015814860506707921852997096156275804955989964215077733621769938075413007804223217091604613132253046399456747595300404564172224333936405545921819654435437072133387523533568472443532200069133022979195685683508297337961701169394794966256415112246587706103819620428258245999539040721929317130088874161577093962579487428358736401687123174207198251449851429295

c1 = [c11,c12,c13,c14,c15,c16]
c2 = [c21,c22,c23,c24,c25,c26]

s = ''
a = gcdext(e1,e2)
for i in range(6):
    m = pow(c1[i],a[1],N)*pow(c2[i],a[2],N)%N
    s += binascii.unhexlify(hex(m)[2:]).decode()     #16进制转字符串（另一种写法）
ans=s.split('\n')   # 通过分隔符\n对 s 内的字符串进行切片操作#这里面的代码借鉴了我大哥博主宁嘉；

但是解出来是一大串base64编码；这里就涉及base64隐写了；反编回去；

这里介绍以下base64编码过程；base64编码原理：

  base64由64个字符组成，使用6位即可表示，而一个字节由8位二进制组成，所以最后需要将8位拆分为6位二进制。

例如给定一个字符，首先需要对应ASCII码表的值，并将其转换为二进制，如“r”对应114，二进制为01110010。接着需要把8位二进制划分为6位，不足6位的在后面补零，使其是6的倍数。然后将其对应base64码表的字符，000000对应“=”即可。#借用以下CSDN博主「R0be1l」写的，写得非常好！

举一例，编码字符“ro”

     r                      o

  01110010    01101111

—>011100 100110 1111100 000000 （红色代表隐写位，2位）

—> 28 38 60 =

—> c m 8 = （base64码表符号）

即字符“ro”进行base64编码后为“cm8=”。

从以上两个例子可以得出：若编码结尾有一个“=”，表示可隐写2位，两个“=”表示可隐写4位。

解码过程就是逆过程:先找到base64字符串对应的数值，然后将其转换为二进制，六个一组，不足补0，再将所有的二进制进行整合，划分为8位一组，每8位就转换为对应的ascill码字符串；下面还是借鉴我大哥的代码，因为写的太好！而且容易理解；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
libase64=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','0','1','2','3','4','5','6','7','8','9','+','/']
def myb64_bytes(str):
    s=''
    temp=str.replace('=','')         #去掉=号
    for i in temp:
        s+=bin(libase64.index(i))[2:].zfill(6)
    return s

def bytes_to_string(str):
    s=''
    for i in range(0,len(str),8):
        s+=chr(eval('0b'+str[i:i+8]))
    return s

flag = ''
for i in ans:
    b=myb64_bytes(i)
    temp=len(b)%8
    if temp !=0:
        flag += b[-temp:]
    else:
        flag=flag

print(bytes_to_string(flag))

#[MRCTF2020]babyRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import sympy
import random
from gmpy2 import gcd, invert
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
from z3 import *
flag = b"MRCTF{xxxx}"
base = 65537


def GCD(A):
    B = 1
    for i in range(1, len(A)):
        B = gcd(A[i-1], A[i])
    return B


def gen_p():
    P = [0 for i in range(17)]
    P[0] = getPrime(128)
    for i in range(1, 17):
        P[i] = sympy.nextprime(P[i-1])
    print("P_p :", P[9])
    n = 1
    for i in range(17):
        n *= P[i]
    p = getPrime(1024)
    factor = pow(p, base, n)
    print("P_factor :", factor)
    return sympy.nextprime(p)


def gen_q():
    sub_Q = getPrime(1024)
    Q_1 = getPrime(1024)
    Q_2 = getPrime(1024)
    Q = sub_Q ** Q_2 % Q_1
    print("Q_1: ", Q_1)
    print("Q_2: ", Q_2)
    print("sub_Q: ", sub_Q)
    return sympy.nextprime(Q)


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的值需要解一个RSA，因为他的素数是相邻的，已知p[9],所以我们可以把所有素数一一求出来，利用sympy模块的prevprime和nextprime，求出来后就求phi(就是每个p[i]-1的乘积)，然后求e的逆元，解出p，q的生成相当容易，不再多说，看下面代码；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
P_p=206027926847308612719677572554991143421
P_factor=213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839
Q_1=103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521
Q_2=151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743
sub_Q=168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651
Ciphertext=1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832
import gmpy2
import Crypto
import sympy
base = 65537
q=sympy.nextprime(gmpy2.powmod(sub_Q,Q_2,Q_1))
P=[]
for i in range(9):
    P_p=sympy.prevprime(P_p)
P.append(P_p)
for i in range(1,17):
    P.append(sympy.nextprime(P[i-1]))
print(P)
n=1
phi=1
for i in range(17):
    n*=P[i]
    phi*=(P[i]-1)
based=gmpy2.invert(base,phi)
_p=gmpy2.powmod(P_factor,based,n)
p=sympy.nextprime(_p)
d=gmpy2.invert(base,(p-1)*(q-1))
plaintext=gmpy2.powmod(Ciphertext,d,p*q)
import binascii
print(binascii.unhexlify(hex(plaintext)[2:]))

[MRCTF2020]Easy_RSA

以下是题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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
'''

题解：代码很长但是题目不是特别难，这里定义了两个函数分别生成了p和q，仔细去看p的生成不是很难，给出了p里面的n和phi就可以求出p，而生成q，就只给出了ed和n这里我们就要去研究如何算出q，这里有个简便方法哇，直接factor分解，还有一种就是算法啦，ed−1=kϕ=k(p−1)(q−1)=k(pq−(p+q)+1)=>(ed−1)//pq<(ed−1)//(pq−(p+q)+1)=k.去意会意会吧。

以下是解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from gmpy2 import *
from sympy import *
from Crypto.Util.number import long_to_bytes
P_n =  14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024336556028267742021320891681762543660468484018686865891073110757394154024833552558863671537491089957038648328973790692356014778420333896705595252711514117478072828880198506187667924020260600124717243067420876363980538994101929437978668709128652587073901337310278665778299513763593234951137512120572797739181693
P_F_n =  14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024099427363967321110127562039879018616082926935567951378185280882426903064598376668106616694623540074057210432790309571018778281723710994930151635857933293394780142192586806292968028305922173313521186946635709194350912242693822450297748434301924950358561859804256788098033426537956252964976682327991427626735740
Q_n =  20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
Q_E_D =  100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
C =  40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021
def get_p(n,phi):
    x=P_n-P_F_n+1
    y=iroot(x**2-4*P_n,2)[0]
    q=(x+y)//2
    p=x-q
    factor2 = 2021 * p + 2020 * q
    if factor2 < 0:
        factor2 = (-1) * factor2
    return nextprime(factor2)
def get_q(n,phi):
    x = Q_n - Q_F_n +1
    y = iroot(x ** 2 - 4 * Q_n, 2)[0]
    q = (x + y) // 2
    p = x-q
    factor2 = 2021 * p - 2020 * q
    if factor2 < 0:
        factor2 = (-1) * factor2
    return nextprime(factor2)
if __name__ == "__main__":
    _E = 65537
    _P = get_p(P_n,P_F_n)
    print(_P)
    k = ((Q_E_D - 1) // Q_n) + 1
    Q_F_n = (Q_E_D - 1) // k
    _Q = get_q(Q_n,Q_F_n)
    print(_Q)
    d=invert(_E,(_P-1)*(_Q-1))
    print(d)
    M =powmod(C,int(d),_P*_Q)  #这里的d删去int 我能不知道为啥报错，也可以把得到的数单独放出去解就不会报错
    print(long_to_bytes(M))

[INSHack2017]rsa16m

题目：给出了很大很大的而且还给了提示，密钥很大很大，所以我们可以用低指数加密去做；

以下是大哥宁嘉的代码：（浅浅的借用一下）：

1
2
3
4
5
6
7
8
9
10
11
from gmpy2 import*
from libnum import*
from Crypto.Util.number import long_to_bytes

f=open('rsa',"r")
f.readline()
c=int(f.readline().strip("\n").split("=")[1],16)   #试验了一下，去掉strip("\n")不会错，如多方便理解的话，就把字符串去掉，然后用"="划分；
e=0x10001
m=iroot(c,e)[0]
print(long_to_bytes(m))
#INSA{(I)NSA_W0uld_bE_pr0uD}

[ACTF新生赛2020]crypto-aes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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函数：它是用来获取一个指定长度的bytes对象, 它实际上是在获取不同操作系统特定提供的随机源。

1
2
3
4
5
6
7
8
9
10
>>> os.urandom(1)
b'\x03'
>>> os.urandom(2)
b'\t['
>>> os.urandom(3)
b'\xdb\x8a\x7f'
>>> os.urandom(4)
b'Q\xeal\xf4'
>>> len(os.urandom(4))
4

key是随机生成两个字节然后乘16，也就是16个一模一样的两个字节，总共就是32字节，256bit，再看到iv，他是随机生成16个字节，128bit，然后分别转换为数字去异或，由异或可知，key的高位128bit是没有参与异或的，由此可以将输出的前16个字节乘2就可以得到原来的key，接下来容易了，异或是可以逆的；

下面就是激动人心的时候了；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#python3
from Crypto.Cipher import AES
import os
from gmpy2 import*
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'
out = long_to_bytes(xor)
key = out[:16]*2
# print(key)
iv = bytes_to_long(key[16:])^bytes_to_long(out[16:])
# print(iv)
iv = long_to_bytes(iv)
# print(iv)
aes = AES.new(key,AES.MODE_CBC,iv)
flag = aes.decrypt(enc_flag)
print(flag)

#[INSHack2019]Yet Another RSA Challenge - Part 1

题目如下：

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

题解：p和q的生成很简单，解出p和q就真相大白了，p的那里它把p里面的”9F”替换成”FC”，当然不要想当然哈哈哈，就直接逆回去，要设想一下，如果p刚开始就有”FC”，然后把所有的”FC”都替换了肯定不符合题意，所以我们直接分析p里面与多少个”FC”然后去组合。

解密脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import*
from gmpy2 import*
from libnum import*
from Crypto.Util.number import long_to_bytes
N = 719579745653303119025873098043848913976880838286635817351790189702008424828505522253331968992725441130409959387942238566082746772468987336980704680915524591881919460709921709513741059003955050088052599067720107149755856317364317707629467090624585752920523062378696431510814381603360130752588995217840721808871896469275562085215852034302374902524921137398710508865248881286824902780186249148613287250056380811479959269915786545911048030947364841177976623684660771594747297272818410589981294227084173316280447729440036251406684111603371364957690353449585185893322538541593242187738587675489180722498945337715511212885934126635221601469699184812336984707723198731876940991485904637481371763302337637617744175461566445514603405016576604569057507997291470369704260553992902776099599438704680775883984720946337235834374667842758010444010254965664863296455406931885650448386682827401907759661117637294838753325610213809162253020362015045242003388829769019579522792182295457962911430276020610658073659629786668639126004851910536565721128484604554703970965744790413684836096724064390486888113608024265771815004188203124405817878645103282802994701531113849607969243815078720289912255827700390198089699808626116357304202660642601149742427766381
cipher = 596380963583874022971492302071822444225514552231574984926542429117396590795270181084030717066220888052607057994262255729890598322976783889090993129161030148064314476199052180347747135088933481343974996843632511300255010825580875930722684714290535684951679115573751200980708359500292172387447570080875531002842462002727646367063816531958020271149645805755077133231395881833164790825731218786554806777097126212126561056170733032553159740167058242065879953688453169613384659653035659118823444582576657499974059388261153064772228570460351169216103620379299362366574826080703907036316546232196313193923841110510170689800892941998845140534954264505413254429240789223724066502818922164419890197058252325607667959185100118251170368909192832882776642565026481260424714348087206462283972676596101498123547647078981435969530082351104111747783346230914935599764345176602456069568419879060577771404946743580809330315332836749661503035076868102720709045692483171306425207758972682717326821412843569770615848397477633761506670219845039890098105484693890695897858251238713238301401843678654564558196040100908796513657968507381392735855990706254646471937809011610992016368630851454275478216664521360246605400986428230407975530880206404171034278692756
plain = ['9F','FC']
for a in plain:
    for b in plain:
        for c in plain:
            for d in plain:
                p1 = '0xDCC5A0BD3A1' +a+ '0BEB0DA1C2E8CF6B474481B7C12849B76E03C4C946724DB577D2825D6AA193DB559BC9DBABE1DDE8B5E7805E48749EF002F622F7CDBD7853B200E2A027E87E331A' +b+ 'FD066ED9900F1E5F5E5196A451A6F9E329EB889D773F08E5FBF45AACB818FD186DD74626180294DCC31805A88D1B71DE5BFEF3ED01F12678D906A833A78EDCE9BDAF22BBE45C0BFB7A82AFE42C1C3B8581C83BF43DFE31BFD81527E507686956458905CC9A660604552A060109DC81D01F229A264AB67C6D7168721AB36DE769CEAFB97F238050193EC942078DDF5329A387F46253A4411A9C8BB71F9AEB11AC9623E41C14' +c+ 'D2739D76E69283E57DDB11' +d+ '531B4611EE3'
                p = int(p1,16)
                print(a,b,c,d)
                if(N%p == 0):
                    print(p)
p = 27869881035956015184979178092922248885674897320108269064145135676677416930908750101386898785101159450077433625380803555071301130739332256486285289470097290409044426739584302074834857801721989648648799253740641480496433764509396039330395579654527851232078667173592401475356727873045602595552393666889257027478385213547302885118341490346766830846876201911076530008127691612594913799272782226366932754058372641521481522494577124999360890113778202218378165756595787931498460866236502220175258385407478826827807650036729385244897815805427164434537088709092238894902485613707990645011133078730017425033369999448757627854563
q = N//p
phi = (p-1)*(q-1)
e = 65537
d = invert(e,phi)
m = pow(cipher,d,N)
print(long_to_bytes(m))
#声明一下这是大哥的脚本。

[De1CTF2019]babyrsa

下面是题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import binascii
from data import e1,e2,p,q1p,q1q,hint,flag

n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797]
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))

题解：这是一道综合性题目;一步一步的来的，所以需要花费一点时间;

先看到第一部分：给出了多组n和c，e也已知，想到中国剩余定理，用其解出p，代码的意思我会注释；

再看到第二部分：是让我们求e1和e2，看到给出的e很小可以进行直接爆破；但是发现e2爆破不出来，于是我们可以进行位数分析，通过位数分析，我们发现tmp的三次方的位数有2063位数，可是n的位数只有2047位数，所以我们就可以判定k值的范围，2^15^~2^16^.

再看到第三部分，就是分解n求出q和p，然后选择较小的一个作为下一个题目的q1.

最后一部分也是最难的部分，我们知道所有的条件但是用常规的解密，他却报错说，e1和(p-1)(q1-1)不互素，e2和(p-1)(q2-1)，下面我手动写一下过程；

解题脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#第一部分：
x=1
n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797]
for i in range (4):
      x*=n[i]
print(x)
N=483726804824395060737990644424225088939093644024749883326337526723844262894632316361090847282687597231416323629418898842256448633120011753535392249447242341392718447776466489918515454416642955027296413022540425457845402550418061278261427592309367305961456244641915115423322508436398830141093324809580223996713898659941315006089551757756141487469005928717013115719621947258569898553984069210000845855285606903049787162074105698436901842949058653070179249527629858719016984347109762288616005892337956871780150774250061538518887143811074648292768091646319945924563788768898163601115426307498553574970436408055617846036007957540184643248369913536847043284593396572019219746442177676758802324798194840036347653230659057007245117559410490034222278922651203645197429129176408694733468581978961302613813856259361215221022140192590201198131157713248382974678694161047514579351446152362888661966252896371012520287210436151539043303308190696523899836802985844477015308897355321995953767813443752770719142826540998600554190954487385955775091346801616182024219334338239894664501609701732836453131952086736608951241420559854600595649031430514178098660623928178766983519466137403425299256713620319964853086108648415241247641728146121409489398269022149306868592578400862714407392671882317670058267652991878613059881267395107550016705475922109244768523518843548447414644156892347403325995371119246938606582245352638648354819588244971141580783685896545652885632448503644145954463466508996797703829632015440142039231377432589868105197375571663320134983634161224600002649565259495503017703298092872895472143621874762357066797491921161531614892444167191976685616341966252765380699201356093597180814235104513686529009081747138947053398365621332998345819067451516179979482721796092694487330061694013540792274671732464213740517142774321052196513741868848786334480320778857805309305248663089095918024926234316062614869468029185700257700468425040348369003991474402998379187828578193695434316376735388144462586651841973757094570144476267321200443114020745601281246064276895454862732893824684327152747669148664174348071529613469239102783275158564097304091024727584391777618828203701885992532090197094451803118009065071069610647043866913232808651281513109503883287272470830267271829432992756558502357277121937768755401818201078403125660867243037825448128147843685767141350854085994017907217684141094796131825213452907620773571879507460217249431846992989322350752008602570164139450386313305984859
n1=N//n[0]
from gmpy2 import *
n2=N//n[1]
n3=N//n[2]
n4=N//n[3]
n_1=invert(n1,n[0])
n_2=invert(n2,n[1])
n_3=invert(n3,n[2])
n_4=invert(n4,n[3])
m=(iroot((n1*n_1*c[0]+n2*n_2*c[1]+n3*n_3*c[2]+n4*n_4*c[3])%N,4))[0]
#p=109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453
#第二部分：
ee1 = 42
ee2 = 3
ce1 =  45722651786340123946960815003059322528810481841378247280642868553607692149509126962872583037142461398806689489141741494974836882341505234255325683219092163052843461632338442529011502378931140356111756932712822516814023166068902569458299933391973504078898958921809723346229893913662577294963528318424676803942288386430172430880307619748186863890050113934573820505570928109017842647598266634344447182347849367714564686341871007505886728393751147033556889217604647355628557502208364412269944908011305064122941446516990168924709684092200183860653173856272384
ce2 =  13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp =  864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n  =  15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039
print(ce1.bit_length())
from gmpy2 import *
for i in range(2**15,2**16):
    x=n*i+ce2
    temp=iroot(x,3)
    if temp[1]==True:
      e2=temp[0]-tmp
      break
print(e2)
print(n.bit_length())
print((ce2).bit_length())
print(((tmp)**3).bit_length())
k=0
while True:
    x=k*n+ce1
    a=iroot(x,42)
    if a[1]==True:
        print(a[0])
        break
#e2=381791429275130
#e1=15218928658178

#第三部分
#直接factor 分解取最小的那个；
e2=381791429275130
e1=15218928658178
p=109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453
q2=114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
q1=127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871
c1=262739975753930281690942784321252339035906196846340713237510382364557685379543498765074448825799342194332681181129770046075018122033421983227887719610112028230603166527303021036386350781414447347150383783816869784006598225583375458609586450854602862569022571672049158809874763812834044257419199631217527367046624888837755311215081173386523806086783266198390289097231168172692326653657393522561741947951887577156666663584249108899327053951891486355179939770150550995812478327735917006194574412518819299303783243886962455399783601229227718787081785391010424030509937403600351414176138124705168002288620664809270046124
c2=7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596
phi = (q1-1)
print(gcd(e1,q1-1))
# print(gcd(e1,phi))       #gcd = 2
dq = invert(e1//2,phi)
x = pow(c1,dq,q1)
m = iroot(x,2)[0]
from libnum import *
print(n2s(int(m)))

[NPUCTF2020]共 模 攻 击

给出了hint和task：hint肯定是给出提示，然后task有flag

下面代码是题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
'''

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 =m^256^mod p,我们直接用常规思路去求发现e和p-1不互素，然后发现e和p-1的公约数是4，于是我们用invert(e//4，p-1)的思路去求还是不互素，然后看wp，要用sympy里面的nthroot_mod函数，这里顺便附上它的源代码

有兴趣可以去了解；

我们解出来的提示是m.bit_length() < 400

由于hint提示了m有长度限制，所以联想到Coppersmith定理。Coppersmith定理的内容为：在一个e阶的mod n多项式f(x)中，如果有一个根小于n^1/e，就可以运用一个O(log n)的算法求出这些根[3]。计算可得m是满足这个情况的。

task中我们可以获取的信息有：

c 1 = m^p^ mod n = m^p^ mod p ∗ q c1 = m^p^ mod n = m^p^ mod p*q
c1=m^p^ modn=m^p^ mod p∗q

c 2 = m^q^ mod n = m^q^ mod p ∗ q c2 = m^q^ mod n = m^q^ mod p*q
c2=m^q^ modn=m^q^ mod p∗q

因为p、q为素数，所以由费马定理可得：

m^p^ ≡ m mod p m^p^ ≡ m mod p
m^p^≡m modp

m ^q^≡ m mod q m^q^ ≡ m mod q
m^q^ ≡m mod q

所以，又有：

c 1 = m + i p + x p q ， 可 整 理 成 c 1 = m + i p c1 = m + ip + xpq，可整理成 c1 = m + ip
c1=m+ip+xpq，可整理成c1=m+ip

c 2 = m + j q + y p q ， 可 整 理 成 c 2 = m + j q c2 = m + jq + ypq，可整理成 c2 = m + jq
c2=m+jq+ypq，可整理成c2=m+jq

因此：

c 1 ∗ c 2 = m 2 + ( i p + j q ) m + i j n c1 * c2 = m2 + (ip + jq)m + ijn
c1∗c2=m2+(ip+jq)m+ijn

( c 1 + c 2 ) m = 2 m 2 + ( i p + j q ) m (c1 + c2)m = 2m2 + (ip+jq)m
(c1+c2)m=2m2+(ip+jq)m

有 ： m 2 − ( c 1 + c 2 ) m + c 1 ∗ c 2 = i j n ≡ 0 m o d n 有： m2 - (c1 + c2)m + c1 * c2 = ijn ≡ 0 mod n
有：m2−(c1+c2)m+c1∗c2=ijn≡0modn
原文链接：https://blog.csdn.net/m0_52727862/article/details/119304377

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
from sympy import *
n= 6807492006219935335233722232024809784434293293172317282814978688931711423939629682224374870233587969960713638310068784415474535033780772766171320461281579
e1= 2303413961
e2= 2622163991
c1= 1754421169036191391717309256938035960912941109206872374826444526733030696056821731708193270151759843780894750696642659795452787547355043345348714129217723
c2= 1613454015951555289711148366977297613624544025937559371784736059448454437652633847111272619248126613500028992813732842041018588707201458398726700828844249
s = gcdext(e1, e2)
print(s)
m = pow(c1, s[1], n) * pow(c2, s[2], n) % n
print((m))
p=107316975771284342108362954945096489708900302633734520943905283655283318535709
c=19384002358725759679198917686763310349050988223627625096050800369760484237557
print(long_to_bytes(nthroot_mod(c,256,p)))
n=128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
c1=96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
c2=9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585
print(c1.bit_length())
print(n.bit_length())
#这里要用到sage：
下面是代码：
n = 128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
c1 = 96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
c2 = 9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585

PR.<m> = PolynomialRing(Zmod(n))
f = m^2-(c1+c2)*m+c1*c2
x0 = f.small_roots(X=2^400)
print(x0)

print(long_to_bytes(4242839043019782000788118887372132807371568279472499477998758466224002905442227156537788110520335652385855))

[羊城杯 2020]RRRRRRRSA

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import hashlib
import sympy
from Crypto.Util.number import *

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

flag1 = flag[:19].encode()
flag2 = flag[19:].encode()
assert(len(flag) == 38)

P1 = getPrime(1038)
P2 = sympy.nextprime(P1)
assert(P2 - P1 < 1000)

Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)

N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2

E1 = getPrime(1024)
E2 = sympy.nextprime(E1)

m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)

c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)


output = open('secret', 'w')
output.write('N1=' + str(N1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('E1=' + str(E1) + '\n')
output.write('N2=' + str(N2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('E2=' + str(E2) + '\n')
output.close()

题目代码不难理解，难理解是是解题啊！不看wp还真解不出来；有一篇论文的；可以尝试去翻译理解；论文链接：https://eprint.iacr.org/2015/399.pdf

题解：N1=p1^2^ *Q1 ,N2=p2^2^ *Q2 其中涉及很多定理；下面是我写的笔记，很重要的定理，其中这题必须要了解连分数的意义，可以去哔哩哔哩里面去学习一下；

对了其中求连分数sagemath里面可以直接求；

在sagemath里面输入continue_fraction(N1/N2)可求

可以多去尝试连分数和欧几里得算法的关系：

连分数算法

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import *
import gmpy2,sympy

N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393


m=

for n in range(len(m)):
    temp = m[:n]
    num = 0 # 分子  这里是初始值
    deno = 1 # 分母
    for x in temp[::-1]:  #将其倒置
        num,deno = deno, deno * x + num    #这里就是他们的关系
    if N2 % deno == 0 and deno != 1:
        Q2 = deno
        print(Q2)
        break
Q1 = sympy.prevprime(Q2)
P1 = gmpy2.iroot(N1 // Q1,2)[0]
P2 = gmpy2.iroot(N2 // Q2,2)[0]
fai_n1 = (P1-1)*P1*(Q1-1)
fai_n2 = (P2-1)*P2*(Q2-1)
d1 = gmpy2.invert(E1,fai_n1)
d2 = gmpy2.invert(E2,fai_n2)
m1 = pow(c1,d1,N1)
m2 = pow(c2,d2,N2)
print(bytes.decode(long_to_bytes(m1)),end="")
print(bytes.decode(long_to_bytes(m2)))

#[UTCTF2020]hill

##希尔算法

利用矩阵的原理去加密

算法原理：

一个n*n矩阵(加密矩阵) A
一个英文字符串s
记 a=0,b=1,c=2…z=25

  1. 先将s转成数字表示形式.

  2. 分组,比如s得到的序列为 x1,x2,x3,x4,x5,x6 n=2,那么要分成每列两个元素的矩阵即:
    x1 x3 x5
    x2 x4 x6
    加密过程: 记上述的矩阵为M,得到的密文矩阵为C,则转化过程为:
    (AM)%26=C(注意是M左乘一个A)
    解密过程:
    M=(A-1 C)%26
    一般做题过程中n不会太高.

    以下是题目：

    wznqca{d4uqop0fk_q1nwofDbzg_eu}

    猜测前面六位为utflag；假设n=2

    则加密矩阵为2*2矩阵；求明文我们必须知道加密矩阵，加密矩阵的逆矩阵乘上密文即可求出明文：

    求出2*2加密矩阵

    上代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    s='wznqcaduqopfkqnwofDbzgeu'
    flag_pre='utflag'
    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)
    import string
    flag=''
    for i in range(0, len(s),2):
        flag+=string.ascii_letters[(x1[0]*string.ascii_letters.index(s[i])+x1[1]*string.ascii_letters.index(s[i+1]))%26]
        flag+=string.ascii_letters[(x2[0]*string.ascii_letters.index(s[i])+x2[1]*string.ascii_letters.index(s[i+1]))%26]
    print(flag)

    #强国杯babyrsa

    题目：

    1
    2
    3
    4
    p=141755878485521250585193526506481835647909733133264484491826506533095411036871187581787386511037412174342774745629361598256663156186634190655768748475210357241858257598757038958971434010720283092093970656262829235604751943313758736375629372244903654343619477366460118493729379823214225182978297539467629343751
    q=105791326767350254361775085198789512601280034667878018736203482690296402930705105880941292311523491531268219920304105707946817881385239201060719345266176935014448981721004118085446297034921832910808404583724823060617037938408978927482413705465188767091927899538738934603096246585672422519596415454996951648933
    e=33
    c=1406397112339697711604857959634535602308393200925612487282395712494883971454736568217895405105641804234918132815025852520686132492440369381524536605289927570796848067004330389550235386191718059158797682686883851836520235452554108372524737561747360657926629011197101279036266730814165126504183746702642346930678406881723781517084042121908048000756941192812817934470545903542277748760076963885109519709405907055218814798421840231218418875714770702389870687977272565851870471136169739851824446107960081481505725577148169000576421732034715421196693795925511463683392371022845041003197960494696500662560942126741476511550

    题解：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    from Crypto.Util.number import long_to_bytes
    from gmpy2 import *

    def decrypt(p, q, e, c):
        n = p * q
        phi = (p - 1) * (q - 1)
        d = invert(e // 3, phi)
        m = pow(c, d, n)
        while 1:
            msg = iroot(m, 3)
            if msg[1]==True:
                print(long_to_bytes(msg[0]))
                break
            m += n

    p=115527813793076185316851381449805634312168762458657191403286815066526250953188706928583056798579604342852966744015346317325822694054887219898915721915782637754329465514052854924553817535032759938725270570934210214428213523012934841467181935253769089655932739804044118941188314706468747928929674022797932677491
    q=166400672883439986828248067692123363689048001045100362967157232932898845079847645677561248632693179197251519134531321011154377754163164855606639412545072704732134708868296084256496193743609181923015517115351345445824153230019197616579730076056575061573322756305055859636790371958064604509869192577321790513607
    e=33
    c=2115560894194923855739630759560263432863369647495989278797186061331927960652175182534536593259714647189428014744205682895048988970744494185844850545176656896750073471540369186693731841022954707114460986390619090986241777895532597176340296883545005058917849321578371609829147178589075514145416374661047508694566576157432639591003296975055455249269260800329069263661498941662392614602189878893057734163983485998267416879197126412977444307775211162627226211229437593330963712320994664878058875181731837287047039480049127389471576406574432640255100250675953098648028434804235316276464230311654580987077193891045891045379
    decrypt(p, q, e, c)

    国赛 LCG

    题目代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    from Crypto.Util.number import *

    flag = getRandomNBitInteger(32)

    class LCG:
        def __init__(self):
            self.a = getRandomNBitInteger(32)
            self.b = getRandomNBitInteger(32)
            self.c = getRandomNBitInteger(32)
            self.n = getPrime(32)
            self.seed = getRandomNBitInteger(32)

        def next(self):
            self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.n
            return self.seed 

        def output(self):
            print("b = {}\nn = {}".format(self.b, self.n))
            print("seed = {}".format(self.seed))
            print("s1 = {}".format(self.next()))
            print("s2 = {}".format(self.next()))

    lcg = LCG()
    lcg.output()
    c1 = ((flag * lcg.a + lcg.c) % lcg.n) >> 16
    c2 = ((c1 * lcg.a + lcg.c) % lcg.n) >> 16
    print("c1 = {}".format(c1))
    print("c2 = {}".format(c2))
    print("flag = {}".format(flag))
    '''
    b = 3831416627
    n = 2273386207
    seed = 2403188683
    s1 = 260742417
    s2 = 447908860
    c1 = 17275
    c2 = 28951
    '''

    解题思路

    看已知条件就知道要求出c和a

    求a：联立方程，设a为x，因为x × seed^2^ + b × seed - s1 = -c 1

    ​ 又因为x*seed^2^ + b × seed -s2= - c 2

    所以一式减去二式

    利用corrppermith攻击

    求出根，根就是a

    再利用a和s1求出c ,设c为x；所以a × seed^2^ +b ×seed +c - s1 == 0

    所以解出c

    解题代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    from sage.all import *
    from Crypto.Util.number import long_to_bytes
    from hashlib import md5
    from binascii import hexlify

    b = 3831416627
    n = 2273386207
    seed = 2403188683
    s1 = 260742417
    s2 = 447908860
    c1 = 17275
    c2 = 28951

    N = Zmod(n)
    x = polygen(N)
    f = x * seed**2 + b * seed - s1 - (x*s1**2+b*s1-s2)
    a = f.roots()[0][0]
    print("a =",f.roots()[0][0])
    x = a
    assert (x * seed**2 + b * seed - s1 - (x*s1**2+b*s1-s2))%n == 0

    x = polygen(N)
    f = a * seed**2 + b*seed + x - s1
    c = f.roots()[0][0]
    print("c =", c)
    x = c
    assert (a * seed**2 + b*seed + x - s1)%n == 0

    c0 = []
    for i in range(2**16):
            if (( (c1*(2**16) + i) * a + c )%n) >> 16 == c2:
                    c0.append((c1*2**16+i))


    flag = []
    for cc0 in c0:
            x = polygen(N)
            f = x * a + c - cc0
            flag.append(int(f.roots()[0][0]))

    for fs in flag:
            for i in range(1000):
                    if (fs+n*i)>=2**32:
                            break
                    print("flag{%s}"%md5(str(fs+n*i).encode()).hexdigest())

    [BJDCTF2020]伏羲六十四卦

    这是什么，怎么看起来像是再算64卦！！！

    密文:升随临损巽睽颐萃小过讼艮颐小过震蛊屯未济中孚艮困恒晋升损蛊萃蛊未济巽解艮贲未济观豫损蛊晋噬嗑晋旅解大畜困未济随蒙升解睽未济井困未济旅萃未济震蒙未济师涣归妹大有

    嗯？为什么还有个b呢?
    b=7

    flag：请按照格式BJD{}

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # -- 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卦，在网上找到64卦和二进制的关系；

    得到的密文再根据给出的加密脚本逆回去；

    下面是解题代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    s='升随临损巽睽颐萃小过讼艮颐小过震蛊屯未济中孚艮困恒晋升损蛊萃蛊未济巽解艮贲未济观豫损蛊晋噬嗑晋旅解大畜困未济随蒙升解睽未济井困未济旅萃未济震蒙未济师涣归妹大有'
    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'}
    li=[]
    i=0
    k=0
    for i in range (len(s)):
        if k==1:               '''这里解释一下，如果是两个字符的，然后k=1，又因为下一次循坏的时候要加二所以就写这串代码让它                               再次循环一次,实现了加一；
                               '''
            k=0
            continue
        try:
            li.append(dic[s[i]])
        except:
            t=""
            t=t+s[i]+s[i+1]
            li.append(dic[t])
            k=1
    print(li)
    enc="".join(li)
    print(enc)
    c=""
    for i in range(0,len(enc),8):
        c+=chr(eval("0b"+enc[i:i+8]))
    print(c)
    from base64 import*
    cipher=b64decode(c).decode()
    print(cipher)
    def decrypt4(enc):
        temp=''
        offset=5
        for i in range(len(enc)):
            temp+=chr(ord(enc[i])+offset+i)
        return(temp)
    def decrpyt5(flag):
        for a in range(1,200):
            enc=""
            for i in flag:
              for k in range(200):
                if (ord(i)-97-7+k*26)%a==0:
                    enc+=chr((ord(i)-97-7+k*26)//a+97)
                    break

            print(enc)



    a=decrypt4(cipher)
    decrpyt5(a)