NSSCTFcrypto 2024.4.13

1
2
3
4
5
6
7
8
9
10
11
12
	flag=b"NSSCTF{xxxxxxxxxxxxxxxxxxx}"  
p = getPrime(2048) 
q = getPrime(2048) 
n = p*q
g = n+1
flag = flag + os.urandom(256)
m = bytes_to_long(flag)
assert m < n
c=(pow(g,p,n*n)*pow(m,n,n*n))%(n*n)
print(f"c={str(c)}")
print(f"n={str(n)}")
print(f"hint={str(pow(m,n,n*n))}")

看了一眼，发现是一种类似Paillier算法的加密，搜索查看了

应用密码学 | Paillier同态加密算法简介 - 知乎 (zhihu.com)

发现了其中有关二项式定理的部分

001

发现题目中用p代替了m，一番推理找到了求解p的方法。

1
2
3
4
5
6
7
8
9
10
11
12
#首先求出
c_1 = c*inverse(hint,n**2) %n**2
#从之前了解到的，c_1=p*n+1 mod n**2
#c_1 = p*n+1+k*n**2 -> (c_1-1)/n = p+k*n = p*(1+k*q)
#发现c_1有一个因子p所以，p = gcd((c_1-1)//n,n)
c_1 = c*inverse(hint,n**2)%n**2
p = gmpy2.gcd((c_1-1)//n,n)
q = n//p
d = inverse(n,(p-1)*(q-1))
m = pow(hint,d,n)
print(long_to_bytes(m))

安洵杯2020_easyaes

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

iv = flag.strip(b'd0g3{').strip(b'}')

LENGTH = len(key)
assert LENGTH == 16

hint = os.urandom(4) * 8
print(bytes_to_long(hint)^bytes_to_long(key))

msg = b'Welcome to this competition, I hope you can have fun today!!!!!!'

def encrypto(message):

    aes = AES.new(key,AES.MODE_CBC,iv)
    return aes.encrypt(message)

print(binascii.hexlify(encrypto(msg))[-32:])

看题后发现题目给的hint长度很短，直接打印异或结果其中重复部分即为hint，然后直接解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
x=56631233292325412205528754798133970783633216936302049893130220461139160682777
c=b'3c976c92aff4095a23e885b195077b66'
c=long_to_bytes(int(c,16))
tmp = long_to_bytes(x)[:4]
print("tmp:",tmp)
key = long_to_bytes(bytes_to_long(tmp*8)^x)
print(key)

msg = b'Welcome to this competition, I hope you can have fun today!!!!!!'
mblock=[msg[i:i+16] for i in range(0,len(msg),16)]
mblock.reverse()

for j in mblock:
    aes = AES.new(key, AES.MODE_ECB)
    de = aes.decrypt(c)
    c=bytes([_a^_b for _a,_b in zip(de,j)])
    print(c)

LitCTF2024_common_primes_plus 2024.6.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from secret import flag,a,b,c,d

assert a*c == b*d + 1
assert isPrime(a) and isPrime(b) and isPrime(c) and isPrime(d)
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互素，且 时 我们有 由此可知求解 即可得到p

1
2
3
4
5
6
7
8
9
10
from gmpy2 import *
e=65537
n1 = ...
hint1 = ...
hint2 = ... 
c = ...
p=gmpy2.gcd(hint1,hint2)
print(n1%p)
d=gmpy2.invert(e,p-1)
print(long_to_bytes(pow(c,d,p)))

LitCTF2024_little_fermat_plus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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}')

题目是对费马小定理的拓展，首先我们可以由得马小定理得到 所以我们所需要的x其实是，但是做题时并没有发下面这一点，而是在发现普通x长度小于m时对x进行左移10位，也相当与*1024.

1
2
3
4
5
6
7
8
9
10
11
12
n=...
c=...
p=...
q=...
x=q-1
x=x<<10
e = 65537
d=inverse(e, (q-1)*(p-1))
m=pow(c, d, n)
print(bin(x))
print(bin(m))
print(long_to_bytes(m^x))

LitCTF2024_Polynomial_plus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
m = bytes_to_long(flag)

while True:
    k = getRandomNBitInteger(64)
    p = k**10 + 22*k**8 + 53*k**6 - 22*k**4 - 39*k**2 + 114514
    q = k**9 + 10*k**7 - 13*k**6 - 2*k**4 + 111*k**2 + 1919810
    
    if isPrime(p) and isPrime(q):
        e = 65537
        n = p * q
        c = pow(m,e,n)
        print(f"n = {n}")
        print(f"c = {c}")
        break

直接sage求解方程即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#sage
from Crypto.Util.number import *
n = int(...)
c = int(...)
e=65537
k=var('k')
f=(k**9 + 10*k**7 - 13*k**6 - 2*k**4 + 111*k**2 + 1919810)*(k**10 + 22*k**8 + 53*k**6 - 22*k**4 - 39*k**2 + 114514)-n
x=solve(f,k)
print(x)
kk=int(x[0].rhs())

q=int(kk**9 + 10*kk**7 - 13*kk**6 - 2*kk**4 + 111*kk**2 + 1919810)
p=int(kk**10 + 22*kk**8 + 53*kk**6 - 22*kk**4 - 39*kk**2 + 114514)
print(n%p)
d=int(inverse(e,q-1))
print(long_to_bytes(pow(c,d,q)))

官方wp解法：

发现p，q的首项都在多项式中非常大所以 则 ，尝试对n开方得到k的值，如果并非准确的k值也没关系，因为p，q受k值影响较大，从当前k值爆破很宽就可以得到正确的k。从而求解。