序言

本文仅对未前文未出现的原理进行推导、解释或引文。

前情提要：CTF实战分享 | Crypto-RSA

[AFCTF 2018]你能看出这是什么加密么

题目：

p=0x928fb6aa9d813b6c3270131818a7c54edb18e3806942b88670106c1821e0326364194a8c49392849432b37632f0abe3f3c52e909b939c91c50e41a7b8cd00c67d6743b4f

q=0xec301417ccdffa679a8dcc4027dd0d75baf9d441625ed8930472165717f4732884c33f25d4ee6a6c9ae6c44aedad039b0b72cf42cab7f80d32b74061

e=0x10001

c=0x70c9133e1647e95c3cb99bd998a9028b5bf492929725a9e8e6d2e277fa0f37205580b196e5f121a2e83bc80a8204c99f5036a07c8cf6f96c420369b4161d2654a7eccbdaf583204b645e137b3bd15c5ce865298416fd5831cba0d947113ed5be5426b708b89451934d11f9aed9085b48b729449e461ff0863552149b965e22b6   

思路：

p,q,c,e四要素全了

代码：

import gmpy2
from Crypto.Util.number import *

p=0x928fb6aa9d813b6c3270131818a7c54edb18e3806942b88670106c1821e0326364194a8c49392849432b37632f0abe3f3c52e909b939c91c50e41a7b8cd00c67d6743b4f

q=0xec301417ccdffa679a8dcc4027dd0d75baf9d441625ed8930472165717f4732884c33f25d4ee6a6c9ae6c44aedad039b0b72cf42cab7f80d32b74061

e=0x10001

c=0x70c9133e1647e95c3cb99bd998a9028b5bf492929725a9e8e6d2e277fa0f37205580b196e5f121a2e83bc80a8204c99f5036a07c8cf6f96c420369b4161d2654a7eccbdaf583204b645e137b3bd15c5ce865298416fd5831cba0d947113ed5be5426b708b89451934d11f9aed9085b48b729449e461ff0863552149b965e22b6

n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[0ctf 2016]rsa

题目：

rsa.zip

思路：

给的是两个文件，有需求可以去下

三步走，

1.读取文件内容

得到了n,e,c

2.分解一下n试试

得到了三个参数

3.此时我们得到了e=3,p,q,r,n,c

此时我们根据条件构造一个多项式

f=x^3-c(mod n)

但是此时数太大了

但是我们还有三个参数p,q,r

得到三个多项式

f=x^3-c(mod p)

f=x^3-c(mod q)

f=x^3-c(mod r)

再通过这三个方程的解作依赖中国剩余定理求出公共解

解题：

1.读取文件内容

from Crypto.PublicKey.RSA import importKey
from Crypto.Util.number import *
from gmpy2 import *
#读取文件获取n,c,e
with open("public.pem","rb") as f:
    f=f.read()
with open("flag.enc","rb") as f2:
    f2=f2.read()
c=bytes_to_long(f2)
t=importKey(f)
e=t.e
n=t.n
print(e,n,c,sep='\n')

2.sagemath 整环求解，中国剩余定理

e=3
n=23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067
c=2485360255306619684345131431867350432205477625621366642887752720125176463993839766742234027524
p = 32581479300404876772405716877547
q = 26440615366395242196516853423447
r = 27038194053540661979045656526063
P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()

P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()

P.<a>=PolynomialRing(Zmod(r),implementation='NTL')
g=a^e-c
mrs=g.monic().roots()
flag=[]
for mpp in mps:
    x=mpp[0]
    for mqq in mqs:
        y=mqq[0]
        for mrr in mrs:
            z=mrr[0]
            solution = CRT_list([int(x), int(y),int(z)], [p, q,r])
            flag.append(solution)
print(flag)

3.从flag中遍历得到真正解

from Crypto.PublicKey.RSA import importKey
from Crypto.Util.number import *
from gmpy2 import *

flag=[14575581396555875063286278270752232069025486022590800034412184690981081178665249519065985803685, 20273014103169850432517184383378298054179993157382597702603040162619132899948023796278277511269, 1515872729797161495186483275231243795196573763727065676932467030113544901967856091319674835059, 13151549744193905008649162659079215553603232734516481193694205400728374265340052771862164820540, 18848982450807880377880068771705281538757739869308278861885060872366425986622827049074456528124, 91841077435191440549367663558227279774320475652746836214487739860837988642659344115853851914, 11593946940464063114201205314336822056082594538100605152475800662668231666662930226338069622856, 17291379647078038483432111426962888041237101672892402820666656134306283387945704503550361330440, 21826949252375729949742683588818718529313688847283160806914496377274629414005251979132645992297]
for i in flag:
    m=long_to_bytes(i)
    print(m)

[LitCTF 2023]factordb (中级)

题目：

e = 65537
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
c = 87677652386897749300638591365341016390128692783949277305987828177045932576708

思路：

只给了三个参数，考虑一下直接分解

分解出来两个参数

p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239

代码：

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

e = 65537 
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461 
c = 87677652386897749300638591365341016390128692783949277305987828177045932576708
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

[HDCTF 2023]Normal_Rsa(revenge)

题目：

from Crypto.Util.number import *
#from shin import flag


m=bytes_to_long(b'HDCTF{******}')
e=65537
p=getPrime(256)
q=getPrime(512)
r=getPrime(512)
n=p*q*r
P=pow(p,2,n)
Q=pow(q,2,n)
c=pow(m,e,n)
print(f"P = {P}")
print(f"Q = {Q}")
print(f"n = {n}")
print(f"c = {c}")
'''
P = 8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q = 112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n = 12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c = 7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785
'''

思路：

核心的三个公式

P=pow(p,2,n)

Q=pow(q,2,n)

c=pow(m,e,n)

得到三个关系式

P%n=p^2%n

Q%n=q^2%n

c%n=m^e%n

对P,Q关于模n开根号

然后按照正常求解路线即可

代码：

import libnum
import gmpy2
import hashlib
from gmpy2 import *
from Crypto.Util.number import *
from gmpy2 import gmpy2



P = 8760210374362848654680470219309962250697808334943036049450523139299289451311563307524647192830909610600414977679146980314602124963105772780782771611415961
Q = 112922164039059900199889201785103245191294292153751065719557417134111270255457254419542226991791126571932603494783040069250074265447784962930254787907978286600866688977261723388531394128477338117384319760669476853506179783674957791710109694089037373611516089267817074863685247440204926676748540110584172821401
n = 12260605124589736699896772236316146708681543140877060257859757789407603137409427771651536724218984023652680193208019939451539427781667333168267801603484921516526297136507792965087544395912271944257535087877112172195116066600141520444466165090654943192437314974202605817650874838887065260835145310202223862370942385079960284761150198033810408432423049423155161537072427702512211122538749
c = 7072137651389218220368861685871400051412849006784353415843217734634414633151439071501997728907026771187082554241548140511778339825678295970901188560688120351732774013575439738988314665372544333857252548895896968938603508567509519521067106462947341820462381584577074292318137318996958312889307024181925808817792124688476198837079551204388055776209441429996815747449815546163371300963785
e=65537
p=iroot(P,2)[0]
q=iroot(Q,2)[0]
r=n//(p*q)
assert p*q*r==n
d=invert(e,(p-1)*(q-1)*(r-1))
m=pow(c,d,n)
print(long_to_bytes(m))

[LitCTF 2023]easy_math (中级)

题目:

from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(128)
n = p*q
hint = p**3-q**5
c = pow(m,e,n)
print(f'n = {n}')
print(f'c = {c}')
print(f'hint = {hint}')
'''
n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932
'''

思路：

根据题目

我们得到两个公式

hint=p^3-q^5

n=p*q

因式分解了半天

然后想到了python可以解方程

代码：

import gmpy2
import sympy as sp
from Crypto.Util.number import long_to_bytes

# 定义符号变量p,q
p, q = sp.symbols('p q')

# 定义方程组
y1 = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932
y2 = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
eq1 = p**3 - q**5 - y1
eq2 = p * q - y2

# 求解方程组
sol = sp.solve((eq1, eq2), (p, q))
print(sol)

# 解题
e = 65537
n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
p = 7321664971326604351487965655099805117568571010588695608389113791312918573783115429227542573780838065461696504325762281209452761930184231131129306271846427
q = 304683618109085947723284393392507415311
d = gmpy2.invert(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))

[zer0pts 2020]ROR

题目：

import random
from secret import flag

ror = lambda x, l, b: (x >> l) | ((x & ((1<<l)-1)) << (b-l))

N = 1
for base in [2, 3, 7]:
    N *= pow(base, random.randint(123, 456))
e = random.randint(271828, 314159)

m = int.from_bytes(flag, byteorder='big')
assert m.bit_length() < N.bit_length()

for i in range(m.bit_length()):
    print(pow(ror(m, i, m.bit_length()), e, N))

思路：

m.bit_length()是chall.txt文件的行数+1

# 文件中每行都是一个ci

# ci=pow(ri,e,N)

# e = random.randint(271828, 314159)

# N = 2^r1*3^r2*7^r3

# ror(m,i,m.bit_length())中i的范围是[1,m.bit_length())

# 此时我们更换一下

# ror=(m>>i)|((m & ((1<<i)-1)) << (m.bit_length()-i))

# 此时将代码进行分布分析

# step 1:

# m>>i

# 右移i位置 得到高位(b-i)位

# step 2:

# ((x & ((1<<i)-1))

# (1<<i) 1左移l位得到 100000共i个0 此时有i+1位 再减去1 得到11111---1共i位1

# x&((1<<i)-1)就是将x的低i位与上1

# step 3:

# ((x & ((1<<l)-1)) << (b-l)

#  step 2的数 左移动b-i位置 仅剩i位低位和b-i个0 如:bi+00000

# step 4:

# (x >> l) | ((x & ((1<<l)-1)) << (b-l))

# 可以得到

# i个低位+(b-i)个低位的表现形式：从右侧移出的位会重新从左侧进入

# 此时我们可以得到

# for i in range(m.bit_length())

# 这个遍历中 将m循环了m.bit_length()-1次

# 因此在给出的chall.txt文件中我们我们无法得出一个原始的m^e%n因为没有移m.bit_length()位

# 我们可以得到出两个关系式对i在(1,m.bit_length())内成立

# m=mi<<i+mi>>(b-i)

# mi=m<<(b-i)+m>>i

# 因此需要进一步分析

题目中仅给出了不确定的n的范围，e的范围和一堆ci

想要得出相应的参数很难，那我们从获取的信息

mi=m<<(b-i)+m>>i

ci%n=mi^e%n

由于2|N

ci%2=mi^e%2

此时我们发现

c的最低位就是m的最低位，遍历得到所有c的最低为合并可得m。

解题：

from Crypto.Util.number import *
with open('chall.txt', 'r') as f:
    lines = f.readlines()
    m = ''
    for i in lines:
        m += str(bin(int(i))[-1])
    c=int(m[::-1], 2)
    print(c)
    # 取每一个的最后一位，连接起来，然后翻转
    print(long_to_bytes(c))

威尔逊定理

[长安杯 2021]checkin

题目：

from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(16)
n = p*q
m = bytes_to_long(flag)
for i in range(1,p-q):
    m = m*i%n
e = 1049
print(pow(2,e,n))
print(pow(m,e,n))
#4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
#3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

思路：

三个关键点：

for i in range(1,p-q):

m = m*i%n

print(pow(2,e,n))

print(pow(m,e,n))

此时令m1=m*(p-q-1)!%n

可以得到

c1=2^e%n

c2=m1^e%n

e=1049

此时我们可以根据

c1=2^e%n

e=1049

爆破出n

存在整数k使得：k*n=c1-2^e

但是我们看到一个更好的爆破方法

我们发现了一个参数

q = getPrime(16)

q只有16bit

只需要保证2^15---2^16之间的素数可以整除kn我们就可以得到kp

分解一下就可以得到p

然后得到n

然后就可以得到m1的值

m1=m*(p-q-1)!%n

这里很像威尔逊定理，那我们怎么得到关于p(素数)的模呢？

n=p*q

m1=m*(p-q-1)!%n

由上式可以得到

存在整数k使得：k*p*q=m*(p-q-1)!-m1

此时得到公式m1=m*(p-q-1)!%p

乘法遍历[p-q,p)

就可以将上述公式化为

m1*（p-q）*------(p-1)=m*(p-1)%p=m*-1%p

此时将上述公式左边乘上-1模p的逆再模p就可以得到m的值了

代码：

from gmpy2 import *
from Crypto.Util.number import long_to_bytes,isPrime

c1 = 4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
c2 = 3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
e = 1049

kn = pow(2,1049) - c1
# q = getPrime(16)

q = 0
kp = 0
for i in range(2**15,2**16):
    if(isPrime(i)):
        if(kn % i == 0):
            q = i
            kp = kn // q
            break
# 分解得到p
p = 170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231
n = p * q

phi = (p-1)*(q-1)
d = invert(e,phi)
m1 = pow(c2,d,n)
#遍历乘法p-q -p凑出来阶乘
for i in range(p - q , p ):
    m1 = ( m1 * i ) % p
m = m1 * invert(-1,p) % p
flag = long_to_bytes(m)
print(flag)

欧拉定理

[LitCTF 2023]Euler

题目：

from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m,n-p-q+3,n)
print(f'n = {n}')
print(f'c = {c}')
"""
n = 115140122725890943990475192890188343698762004010330526468754961357872096040956340092062274481843042907652320664917728267982409212988849109825729150839069369465433531269728824368749655421846730162477193420534803525810831025762500375845466064264837531992986534097821734242082950392892529951104643690838773406549
c = 406480424882876909664869928877322864482740577681292497936198951316587691545267772748204383995815523935005725558478033908575228532559165174398668885819826720515607326399097899572022020453298441
"""

看到题目是欧拉定理果断使用

n = p*q

c = pow(m,n-p-q+3,n)

欧拉定理的要求是gcd（m,n）=1 这是必然的 因为gcd(m,n)≠1的情况只有m=p或者m=q

由欧拉定理

m^phi%n=1%n

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

此时

c %n=m^(n-p-q+3) %n=m^(p*q-p-q+3) %n=m^2*1%n

m^2=c+kn

只需要遍历k对c+kn开根号即可

解题：

n = 115140122725890943990475192890188343698762004010330526468754961357872096040956340092062274481843042907652320664917728267982409212988849109825729150839069369465433531269728824368749655421846730162477193420534803525810831025762500375845466064264837531992986534097821734242082950392892529951104643690838773406549
c = 406480424882876909664869928877322864482740577681292497936198951316587691545267772748204383995815523935005725558478033908575228532559165174398668885819826720515607326399097899572022020453298441

from gmpy2 import * 
from Crypto.Util.number import * 
for i in range(65535):
    mm=iroot(c+i*n,2)
    if mm[1]:
        m=mm[0]
        break

print(long_to_bytes(m))

二次剩余

不会的看一下初等数论吧。

HDCTF 2023]Math_Rsa

题目：

from Crypto.Util.number import *
from shin import flag


m=bytes_to_long(flag)
r=getPrime(1024)
assert r%4==3
p=getPrime(1024)
assert pow(p,(r-1)//2,r)==1
q=getPrime(1024)
e=65537
n=p*q
a=pow(p,2,r)
c=pow(m,e,n)
print(f"n = {n}")
print(f"r = {r}")
print(f"a = {a}")
print(f"c = {c}")
'''
n = 14859096721972571275113983218934367817755893152876205380485481243331724183921836088288081702352994668073737901001999266644597320501510110156000004121260529706467596723314403262665291609405901413014268847623323618322794733633701355018297180967414569196496398340411723555826597629318524966741762029358820546567319749619243298957600716201084388836601266780686983787343862081546627427588380349