Automne's Shadow.

TSG CTF 2020 Beginner's Crypto WriteUp

Modular operation
2020/07/19 Share

Crypto

拿到的是python脚本文件：

1
2
3
assert(len(open('flag.txt', 'rb').read()) <= 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000)
.endswith('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576'))

从代码里可以看到，flag的长度小于等于50，将flag转换为int然后左移10000位，以指定的175位数字结尾。

首先左移10000位等同于乘以2**10000

然后结合endswith这里，要能想到使用模运算简化计算

计

c=1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576c = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576

于是能得到下面的等式：

flag∗210000%10175=cflag *2^{10000}\%10^{175}=c

flag=c∗(210000)−1%10175flag =c*(2^{10000})^{-1}\%10^{175}

但是这样就结束了吗，并不是，看一下模逆元的定义

automne

可见，只有两个数互质才有模逆元存在，那看一下这两个数是不是互质的，使用扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#encoding=utf-8

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

if __name__ == '__main__':
	a = 2**10000
	b = 10**175
	c = 5**175
	print(egcd(a,b))
	print(egcd(a,c))

从执行结果里可以看到210000和10175并不是互质的，因为最大公约数并不是1

但是210000和5175却是互质的，于是有

flag∗210000%10175=cflag * 2^{10000}\%10^{175} = c

flag∗210000%10175%5175=c%5175flag * 2^{10000}\%10^{175}\%5^{175} = c \%5^{175}

flag∗210000%5175=c%5175flag * 2^{10000}\%5^{175} = c \%5^{175}

flag=c∗(210000)−1%5175flag = c*(2^{10000})^{-1}\%5^{175}

模逆可以用扩展欧几里得算法(可看https://ce-automne.github.io/2020/01/26/LCG%E5%92%8C%E6%A8%A1p%E5%B9%B3%E6%96%B9%E6%A0%B9%E7%BB%93%E5%90%88%E7%9A%84%E9%A2%98%E7%9B%AE/)，也可以用欧拉定理求解，这里通过欧拉定理

automne

flag=c∗(210000)φ(5175)−1=c∗(210000)5175−5174−1flag = c* (2^{10000})^{φ(5^{175})-1}=c*(2^{10000})^{5^{175}-5^{174}-1}

最终的解题脚本：

1
2
3
4
5
6
7
#encoding=utf-8

c = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576
mod = 5 ** 175
phi = 5 ** 175 - 5 ** 174
inv = pow(pow(2, 10000, mod), phi - 1, mod)
print(((c * inv) % mod).to_bytes(50, byteorder='big'))

同样用sage也可以解，里面封装了模逆函数inverse_mod()

1
2
3
4
5
6
7
8
sage: a = 2**10000
sage: b = 5**175
sage: c = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576
sage: d = inverse_mod(a,b)
sage: flag = pow(c*d,1,b)
sage: from Crypto.Util.number import long_to_bytes
sage: long_to_bytes(flag)
'TSGCTF{0K4y_Y0U_are_r3aDy_t0_Go_aNd_dO_M0r3_CryPt}'

参考链接：https://ctftime.org/writeup/22374

原文作者: Automne

原文链接: https://ce-automne.github.io/2020/07/19/TSG-CTF-2020-Beginners-Crypto-WriteUp/

发表日期: July 19th 2020, 8:43:00 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 62
2021
2020
2019
2018
2017
lfsr z3 python reverse fat git broadcastreceiver sha-1 cbc sqli sqlite golang race condition luks hashcat photorec MAC sso oauth 2.0 padding oracle csp xss abe vdex ransomware frida ndk pwntools hashpumpy sourceleakhacker ecb socat fastjson JdbcRowsetImpl idea servlet volatility inet_aton boneh durfee lcg rabin egcd cipolla's algorithm spi snakeyaml ScriptEngineManager malware codereflect mysql yara plugin deserialization log4j rsa binary javascript prototype pollution nodejs shiro ysoserial primefac rsatool ssl AES tshark gmpy2 RsaCtfTool Hex flask ssti ecc Modular operation WebGoat8 order by tomcat nim game .iso gpg outguess sage google cloud sdk zsteg base58 fermat multi-primes prng rmi jndi Paillier Cryptosystem rsa lsb oracle SQL Injection ping delay xor CAS 单点登录 渗透测试 weblogic xxe reflect 010 editor gcd
Crypto Android Web Forensics Misc