BUUCTF 每日打卡 2021-8-3

引言

摸鱼中。。。

[i春秋云上巅峰赛2021]crtrsa

题面： 加密的sage代码如下：

from secret import flagn,p,q
#p and q are two primes generated by getPrime
import random
def key_gen():
	while True:
		dp = random.randint(1,1<<20)
		dq = random.randint(1,q-1)
		if gcd(dp, p - 1) == 1 and gcd(dq, q - 1) == 1:
			d = crt([dp,dq],[p-1,q-1])
			phi = (p-1)*(q-1)
			R = Integers(phi)
			e = R(d)^-1
			return p*q,e
n,e = key_gen()
print e
print n
print pow(flagn,int(e),n)

看代码的时候，数学关系很容易找，而且很多，感觉好像能行 最核心的是d = crt([dp,dq],[p-1,q-1])，翻译成数学语言就是： \[ \begin{cases} d \equiv dp \space mod \space dq\\ d \equiv (p-1) \space mod \space (q-1) \end{cases} \] 还有一条隐藏的或者说是约定俗成的数学关系就是： \[ \begin{cases} dp \equiv d\space mod\space (p-1)\\ dq \equiv d\space mod\space (q-1) \end{cases} \] （虽然当时不确定，鬼知道出题人会出什么幺蛾子，后来发现是我想多了） 其他的都是常规的RSA 看起来线索很多，但又无从下手 后来badm0nkey前辈提醒我，从dp下手爆破 因为dp = random.randint(1,1<<20)，也就是说\(1\leq dp \leq 1048576\)，是容易遍历的 但是即使容易遍历，但是出了dp，其他相关的未知量也是未知的，遍历过程中怎么判断这个dp就是我们想要的呢？ 比赛结束后，前辈给了我答案，推导过程如下： 首先，根据RSA加密算法，有 \[ e\cdot d \equiv 1 \space mod \space (p-1)(q-1) \] 那么有\(e\cdot d \equiv 1 \space mod \space (p-1)\) 又\(dq \equiv d\space mod\space (q-1)\) 故 \[ e\cdot dq \equiv ed\space mod\space (q-1) \equiv 1\space mod\space (q-1) \] 故\(\exists k\in \mathbb{Z}\)​，\(s.t.\)​ \[ e\cdot dp=1+k(p-1) \] 移项得\(e\cdot dp-1=k(p-1)\) 由费马小定理，假如\(a\)是一个整数，\(p\)是一个质数，那么\(a^{p} - a\)是p的倍数，可以表示为 \[ a^p \equiv a \space mod\space p \] 如果\(a\)不是\(p\)的倍数，这个定理也可以写成 \[ a^{p-1} \equiv 1 \space mod\space p \] 可以推出 \[ a^{k(p-1)} \equiv 1 \space mod\space p \] 那么又\(\exists t\in \mathbb{Z}\)​，\(s.t.\)​ \[ a^{k(p-1)} = 1+tp \] 移项得\(a^{k(p-1)} - 1=tp\) 在模N的情况下也成立，也就是有\(e\cdot dp-1\equiv k(p-1) \space mod \space N\)，则\(a^{e\cdot dp-1} - 1\equiv a^{k(p-1)} - 1 \space mod \space N \equiv tp \space mod \space N\) 所以，只要\(gcd(a^{e\cdot dp-1}, N) \neq 1\)，则这个dp就是我们想要的，并且\(gcd(a^{e\cdot dp-1}, N) =p\) 解密代码如下：

from Crypto.Util.number import *
from tqdm import tqdm

e = 2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
N = 6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983
c = 4082777468662493175049853412968913980472986215497247773911290709560282223053863513029985115855416847643274608394467813391117463817805000754191093158289399

for dp in tqdm(range(3, 1<<20, 2)):
    tmp = e*dp-1
    t = pow(3, tmp, N)
    p = GCD(N, t-1)
    if p != 1:
        print("find p!")
        q = N//p
        phi = (p-1)*(q-1)
        d = inverse(e, phi)
        m = pow(c, d, N)
        print(long_to_bytes(m))
        break

结果为：

结语

以后可能要两日一更了，太多事情没干 希望继续坚持