LitCTF2024

[toc]

Crypto

little_fermat

题目：

from Crypto.Util.number import *
from sympy import *
from secret import flag,gen_x

m = bytes_to_long(flag)

e = 65537
p = getPrime(512)
q = nextprime(p)
n = p * q

x = gen_x(p)

assert pow(666666, x, p) == 1

m = m ^ x
c = pow(m, e, n)

print(f'n = {n}')
print(f'c = {c}')

题目描述：

Do you know fermat?

解题思路：

根据断言判断为费马小定理

$a^{p-1}\equiv 1\ (mod \ p)$

所以x= p-1

根据给出数据解出m后异或即可

little_fermat_plus

题目：

from Crypto.Util.number import *
from sympy import *
from secret import flag,gen_x

m = bytes_to_long(flag)

e = 65537
p = getPrime(512)
q = nextprime(p)
n = p * q

x = gen_x(p)

assert pow(666666, x, p) == 1 ** 1024

m = m ^ x
c = pow(m, e, n)

print(f'n = {n}')
print(f'c = {c}')

题目描述：

caution difference

解题思路：

费马小定理扩展，原本的费马定理长这样

$a^{p-1} \equiv 1 \ (mod\ p)$

在对两边取1024次方后长这样

$a^{1024*（p-1）}\equiv 1^{1024}\ (mod\ p)$

所以根据断言，x = 1024*（p-1）

求出m后异或x即可

common_primes

题目：

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

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q1 = getPrime(512)
q2 = getPrime(512)
n1 = p * q1
n2 = p * q2
c1 = pow(m, e, n1)
c2 = pow(m, e, n2)

print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")

题目描述：

OK,it’s your common primes

解题思路：

$gcd(n1,n2) = p$

common_primes_plus

题目描述：

It’s not hard,trust me

题目：

from Crypto.Util.number import *
from secret import flag,a,b,c,d

assert a*c == b*d + 1
m = bytes_to_long(flag)

e = 65537
p = getPrime(512)
q1 = getPrime(512)
q2 = getPrime(512)
n1 = p * q1
n2 = p * q2

hint1 = a * n1 + b * n2
hint2 = c * n1 + d * n2
c = pow(m,e,n1)

print(f"n1 = {n1}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")
print(f"c = {c}")

解题思路：

根据定理，由于a,b,c,d互素，ac-bd=1。所以

$gcd(hint1,hint2) = gcd(n1,n2) = p$

得到p后常规rsa

CRT

题目描述：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

题目：

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

m = bytes_to_long(flag)
e = 10

n_list = []
c_list = []
for i in range(10):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    c = pow(m,e,n)
    n_list.append(n)
    c_list.append(c)

print(f"n_list = {n_list}")
print(f"c_list = {c_list}")

解题思路：

常规CRT脚本

CRT_plus

题目描述：

也许要在老祖宗留下来的基础上改变一下

题目：

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

m = bytes_to_long(flag)

e = 5
A = [random.randint(1, 128) for i in range(e)]
B = [random.randint(1, 1024) for i in range(e)]

C = []
N = []

for i in range(e):
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    c = pow(A[i] * m + B[i], e, n)
    N.append(n)
    C.append(c)

print(f'A = {A}')
print(f'B = {B}')
print(f'C = {C}')
print(f'N = {N}')

解题思路：

smell_e

题目描述：

I spilt the flag into several blocks,can you solve the problem?

题目：

from Crypto.Util.number import *
import libnum
from  gmpy2 import iroot
n = ……
c_list = [……]
e=3
flag= b""
for i in c_list:
    k = 0
    while 1:
        res = iroot(i+k*n,e)  #c+k*n 开3次方根 能开3次方即可
        #print(res)
        #res = (mpz(13040004482819713819817340524563023159919305047824600478799740488797710355579494486728991357), True)
        if(res[1] == True):
            flag += libnum.n2s(int(res[0]))
            break
        k=k+1
print(flag)

解题思路：

小e，直接开方即可

smell_e_plus

题目描述：

You need to change your mind

题目：

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

e = random.randint(1000,2000)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
c_list = []

for m in flag:
    c_list.append(pow(ord(m),e,n))

print(f"n = {n}")
print(f"c_list = {c_list}")

解题思路：

首先确定flag的开头为L，已知e的范围，在遍历e的情况下对“L”进行加密，得到e的值。随后对每个字符都进行爆破，依次得到flag的每个字符。

EasyRSA

题目描述：

怎么说呢，就……真的挺简单的

题目：

from Crypto.Util.number import *
from secret import flag
p=getPrime(256)
print(p)
n=p**4
m=bytes_to_long(flag)
e=65537
c=pow(m,e,n)
print(c)

解题思路：

n为p的4次方，对n直接开方得到p，$phi = p^4-p^3$ 解得m后，发现为fake flag，并给出了hint。多次尝试发现hint为q，与上一步p相乘得到n，求解c2