2016 Sharif CTF unterscheide

知识点：费马小定理

当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