知识点：费马小定理
当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
京公网安备 11010502036488号