20210704-TCTF-CryptoSecPartWriteUp

 

checkin

看题目提示，只有一个nc链接和提示；没有附件，直接连上试试

返回一个代数式，要我们在10秒之内send结果

先搞一组数据下来

2^(2^11611932) mod 10042342927731289936658394995741010342152682534073824765054222876398250110801680355777521786191146694288599302671845390876211753297708706179377223481420568337199329681700808036260275208806645397912634380102847398612053278616443604561505446777411509098232951708762153696144378866698087620743454024477909423603 = ?

结合提示，我尝试将指数给变小。对模数进行分析，发现是1023位的，用手头现有的工具都不能将其有效分解，也就是降低指数这条路多半是行不通；而且就算是求出了欧拉函数，这个数也是很大的，放到幂上去也不能将指数变小

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# nc 111.186.59.11 16256
from pwn import *
import re

context.log_level = 'debug'


def getroot(s):
    m = re.findall("\d+", s)
    x, n = int(m[2]), int(m[3])
    x = 2**x
    ans = pow(2, x, n)
    return str(ans)


def main():
    sh = remote('111.186.59.11', 16256)
    sh.recvline()
    s = sh.recvuntil('?')
    sh.recvuntil('Your answer: ')
    sh.sendline(getroot(s.decode()))
    sh.recv()
    sh.recv()


main()

之后的我查了一些资料，其中尝试过用自己写的数域筛法分解模数，但想必这种算法，yafu和在线网站应该都包含了，还搭建了分解光滑数的工具也还是不行，但都以失败告终

尚师傅说用sage试试

amazing！竟然出来了，原来对于一般语言计算较慢的大指数，sage可以很快出来；其实细想也是，别的语言并不是慢，而是并不支持存放如此庞大的数，而如果只是一个循环来计算八位数的幂的话，时间复杂度还是允许的

试验一下，sage的上限

后来再研究的时候，发现还有其他的方法，参考N^3CTF-baby_nc