HDCTF2023Normalrsa(revenge) 2024.4.4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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，Q都是低指数加密，简单的爆破一下开出来就可以得到p，q了

1
2
3
4
5
6
7
8
9
10
def modroot(c,e,n):
    for i in range(100): 
        m=c+i*n
        if gmpy2.iroot(m,e)[0]:
            return gmpy2.iroot(m,e)[0]
p=modroot(P,2,n)
q=modroot(Q,2,n)
r=n//(p*q)
d=inverse(e,(p-1)*(q-1)*(r-1))
print(long_to_bytes(pow(c,d,n)))

BJDCTF2020EasyRSA 2024.4.7

1
2
3
4
5
6
7
8
9
10
11
p = getPrime(1024)
q = getPrime(1024)
e = 6553
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)

看题目后，发现主要需要解决的是z与p，q的关系，发现是p的正切求导的倒数减去q反切求导的倒数，所以可以发现数学关系 于是我们还可以的得到这样的两个式子 开方得到p，q

1
2
3
4
5
6
7
8
9
pq1=gmpy2.iroot(z+2*n,2)[0]
pq2=gmpy2.iroot(z-2*n,2)[0]

p=(pq1+pq2)//2
q=(pq1-pq2)//2
d=gmpy2.invert(e, (p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))

鹤城杯2021BabyRSA 2024.4.8

1
2
3
4
5
6
7
8
9
10
11
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)

题目条件给出了p的高300位，以及q的低256位，首先可以从如下关系中得到p的低256位 p剩余的位数使用coppersmith求解，直接求解发现失败，尝试爆破几位后得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
mi=2**265
qh=hint1<<724
ql=n*inverse(hint2,mi)%mi
pxp=qh+ql
PR.<x>=PolynomialRing(Zmod(n))
for i in range(64):
    f=pxp+x*64*mi+i*mi
    f=f.monic()
    xpx=f.small_roots(2**453,0.4)
    if len(xpx):
        print(xpx[0])
        break
p=int(pxp+xpx[0]*64*mi+i*mi)
print(n%p)
q=n//p
d=inverse(e,(p-1)*(q-1))
flag=int(pow(ct,d,n))
print(long_to_bytes(flag))

2024.4.9

今天做的题相对简单，只有简单的古典加密，基础的欧拉函数，以及可以直接分解n的一幕，简单的维纳攻击，不写了。

红明谷CTF2022easy_ya 2024.4.10

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 flag import flag
def gen():
    e = 3
    while True:
        try:
            p = getPrime(512)
            q = getPrime(512)
            n = p*q
            phi = (p-1)*(q-1)
            d = inverse(e,phi)
            return p,q,d,n,e
        except:
            continue
    return
p,q,d,n,e = gen()
r = getPrime(512)
m = bytes_to_long(flag+os.urandom(32))
M = m%r
c = pow(m,e,n)
print("r = %d"%r)
print("M = %d"%M)
print("n = %d"%n)
print("e = %d"%e)
print("c = %d"%c)

根据题目已知 根据等式使用CopperSmith求解k

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
from gmpy2  import *
PR.<x>=PolynomialRing(Zmod(n))
f=(M+x*r)**3-c
f=f.monic()
k=f.small_roots()
m=k[0]*r+M
print(long_to_bytes(m))

LitCTF2023Euler 2024.4.10

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

根据题目 c = pow(m,n-p-q+3,n) 其中，又，（）所以， 直接开方即可得m

1
2
3
4
5
6
7
8
def modroot(c,e,n):
    for i in range(512): 
        m=c+i*n
        if gmpy2.iroot(m,e)[0]:
            return gmpy2.iroot(m,e)[0]
m=int(modroot(c,2,n))
print(long_to_bytes(m))