知识点:费马小定理

当p为素数时,a^(p-1)≡1(mod p)


题目分析:

#!/usr/bin/python
 
import gmpy
import random, os
from Crypto.Util.number import *
from Crypto.Cipher import AES
 
from secret import flag, q, p1, p2, h
 
assert (gmpy.is_prime(q) == 0) + (q-1) % p1 + (q-1) % p2 + (p2 - p1 > 10**8) + (pow(h, 1023*p1*p2, q) == 1) == 0
 
key = os.urandom(128)
IV = key[16:32]
mode = AES.MODE_CBC
aes = AES.new(key[:16], mode, IV=IV)
flag_enc = aes.encrypt(flag)
 
rand = bytes_to_long(key)
benc = bin(bytes_to_long(flag_enc))[2:]
 
A = []
for b in benc:
    try:
        r = gmpy.next_prime(random.randint(3, q-2))
        s = gmpy.invert(r, q-1)
        if b == '0':
            a = pow(h, r*r*p1, q)*q*rand + rand + 1
        else:
            a = pow(h, s*s*p2, q)*q*rand + rand + 1
        A.append(str(int(a)))
        rand += 1
    except:
        print 'Failed'
 
fenc = open('enc.txt', 'w')
fenc.write('\n'.join(A))
fenc.close()

大概瞄一眼:AES + 幂次加密

AES这个好弄,只要得到了key和IV,逆向就是写个py的事,重点是如何分析幂次


assert (gmpy.is_prime(q) == 0) + (q-1) % p1 + (q-1) % p2 + (p2 - p1 > 10**8) + (pow(h, 1023*p1*p2, q) == 1) == 0

这行assert其实很重要,告诉了我们几个重要消息:

A:q是素数

B:p1 | (q - 1)

C:p2 | (q - 1)

D:p2 - p1 < 10 ** 8

E:h ^ (1023 * p1 * p2) % q ==0(这个条件没搞明白啥用)

条件BC告诉我们:q-1是可以分解的,条件D告诉我们:可以考虑用工具yafu来跑出来

q是素数,那么q-1是偶数,那么q-1可以写成2*p1*p2*x的形式


根据代码,我们可以从数据中计算出q和rand

把A理解成数列,那么A[i]-A[i-1]是B数列,B数列求gcd就可以得到q,rand=A[0] % q - 1

然后分解q-1,得到q-1=2*p1*p2

要知道b == '0'还是b == '1',用到费马小定理:

q是素数,所以有:a ^ (q - 1) ≡1(mod q),也就是:a ^ (2 * p1 * p2) ≡1(mod q)

m ^ (2 * p2) ≡ h ^ (2 * p1 * p2 * r * r)  ≡ 1时,b = '0',反之一样

然后把所有的拼接起来,跑AES逆向结束


代码在这:

https://github.com/sonickun/ctf-crypto-writeups/blob/master/2016/sharif-ctf/unterscheide/solver.py