强网杯2023-crypto-部分复现

未分类
616 词

目录

[]

https://blog.xmcve.com/2023/12/18/强网杯2023-Writeup/#title-16)

speed up

强网先锋分类里有个speed up，可以直接oeis查出来A244060 - OEIS,不过看各个wp，其实也有一些解法。

sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sage: x = factorial(2^27)
sage: open('aaa.txt','w').write(str(x))
1032606162
 
 
 
>>> a = open('aaa.txt', 'rb').read()
>>> res = 0
>>> for i in a:
...     res += i-0x30
...
>>> from hashlib import sha256
>>> sha256(str(res).encode()).hexdigest()
'bbdee5c548fddfc76617c562952a3a3b03d423985c095521a8661d248fad3797'

[强网杯2023] 只作了几个小题-CSDN博客

也可以使用gmpy2库的fac函数求2^27的阶乘，花费时间大概7~10分钟左右。

not_only_rsa

原题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import bytes_to_long
from secret import flag
import os

n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
m = bytes_to_long(flag)

flag = flag + os.urandom(n.bit_length() // 8 - len(flag) - 1)
m = bytes_to_long(flag)

c = pow(m, e, n)

with open('out.txt', 'w') as f:
    print(f"{n = }", file=f)
    print(f"{e = }", file=f)
    print(f"{c = }", file=f)

解法：

factordb看一下n，发现n是p的5次，然而出来的phi和e不互素，于是还需要解决域上开高次根的问题。

以前常用的是AMM算法，但是AMM的做法是将n分解后，在小模数上去开根最后crt的做法，这里，做不了最后的crt。

在wp里见到一个sage的函数nth_root，可用于开域上高次根和AMM效果一致，通过调整参数all是否为True，可以获得全部根或一个根。

但考虑到一次出全部根比较慢，仍然需要去寻找一个借助单根遍历全部根的方法。

根据欧拉定理，如果x是模n的一个根，并且g是模n的原根，那么 (x * g^phi/e mod n) 也是模n的一个根

根据这个结论，取y=pow(2,phi//e,n)可以完成遍历

同理取K(1).nth_root(e)也有同样的效果

简单证明：

$xg^{phi/e} mod (n) = (x^eg^{phi})^{1/e} mod (n) = (c*1)^{1/e} mod (n) = c^{1/e} mod (n)$

$x1^{1/e} mod (n) = (x^e1)^{1/e} mod (n) = (c*1)^{1/e} mod (n) = c^{1/e} mod (n)$

后面测试过，其实K(1).nth_root(e)就是k次y=pow(2,phi//e,n)相乘的结果。

更具体且严谨的证明应该涉及原根和群一类的知识，暂且搁置

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import  long_to_bytes
p=91027438112295439314606669837102361953591324472804851543344131406676387779969
e = 641747
c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943
n=p^5
phi=p^5-p^4
K=Zmod(p^5)
x=K(c).nth_root(e)
#y=K(1).nth_root(e)
y=pow(2,phi//e,n)
from tqdm import tqdm
for i in tqdm(range(e)):
    x=(x*y)%n
    m=long_to_bytes(int(x))
    if b"flag" in m:
        print(m)
        break