0%

杂题闲记

此系列博客主要记录一下一些题的做题想法(各种rz心路历程orz

强网杯

proof for dice2cry

本质上即是partial oracle mod 3

根本问题在于对于(3mmodn)mod3,是否可以根据模数判断m所在区间,即属于(0,13n),(13n,23n),(23n,n) 中的哪一个。

case 0:

如果模3的结果为0,那么其实可以很容易的知道3m并没有被截断,故而属于(0,n) 区间

case 1/2:

对于模数为1或2的情况,并不存在一定的一一对应的解区间,但对于相同的n,1/2对应的区间是一定的,下面给出第二区间的证明(第三区间类似):

m(n,n),(3mn)x,x=1or2

使用反证法,不妨设

 m1,m2, (3m1n)x1mod3,(3m2n)x2mod3, x1x2

两式相减得到

3(m1m2)x3mod3,x30

又因为

3|3(m1m2)

3(m1m2)0mod3,假设错误,命题得证。

安恒8月赛

这次的crypto貌似是shallow,tb还有coin出的。。。确实有水平,比赛的时候只有LCG那个比较有思路,另外俩个有点懵。。感觉这几个题出到月赛有点浪费hh,时间太短,做出来的人并不多

math stream

观察得到LCG的迭代关系为kiaki2+(a+1)ki1+cmodn

然而相关参数n,c,a 一个都没给,只给出了301到307这6个生成数据,需要我们预测最后一个数据,发现数列长度21024,于是考虑可以使用矩阵快速幂(复杂度O(logn))。

计算通项公式

待定系数x,y,z,则有kixki1+zcy(ki1xki2+zc)modn

可知:

x+y=a+1, xy=a, (y1)z=1

得到:

x=a+1+a2+6a+12, y=a+1a2+6a+12, z=2a1a2+6a+1

si=kixki1+zcmodn,则可知siGF(n)上的等比数列,

si+2=yi(k2xk1+zc)modnk1,k2即为初始生成的随机种子

ki+2=xik2+(k2xk1+zc)j=0ixjyijzcj=0i1xj

上面是我做题时的错误路线,我一开始以为是纯数列题orz

构造格子

通过上面的通项公式可以发现,想要将数列的二阶公式降到一阶需要让参数变的异常复杂,故直接使用二阶公式作为来构造格子

kiaki2+(a+1)ki1+cmodn

kiki1a(ki2+ki1)+cmodn

kiki1=a(ki2+ki1)+c+Tn,TZ

由于对a,c,n 一无所知,故只能使用四组kiki+1,ki2+ki1 构造格子

finii=ki+2ki,initi=ki+ki+1

则有finii=ainiti+c+Tin

于是我构造了如下格子:

但前四行的最后一列并无法平衡,因为需要找到B0,B1,B2,B3 使得i=04Bi(finiiainitic)<<minBi, 而我们并不知道a,c,构造出这样的Bi,显然是不可能的,但如果我们能求出n,那么只需将对角线上的1替换为n,即可解决问题。

然后在求解n的过程中,我意识到完全不用格子ojz,直接推就能推出来。。。而且将n代入也未能求解。。。

推导求解

由之前推导的kiki1a(ki2+ki1)+cmodn

则有 (kiki1)(ki1ki2)a(ki1ki3)modn

由此,只要知道了n,则可以计算出a,c

根据同模,利用最大公因数来求n

利用(ki2ki4)(a(ki1ki3)n)

(ki1ki3)(a(ki2ki4)n)n

此部分exp如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def get_f(k, i):
assert len(k) > i-4 >= 0
return abs((k[i] - 2 * k[i-1] + k[i-2]) * (k[i-2] - k[i-4]) - (k[i-1] - k[i-3]) * (k[i-1] - 2 * k[i-2] + k[i-3]))


f_1 = get_f(k, 4)
f_2 = get_f(k, 5)

n = gcd(f_1, f_2)
print('n = ' + str(n))
assert isPrime(n)

a = ((k[3] - 2 * k[2] + k[1]) * inverse(k[2] - k[0], n)) % n
print('a = ' + str(a))

c = ((k[2] - k[1]) - a * (k[0] + k[1])) % n
print('c = ' + str(c))

这里我起初是想使用最早的通项公式,但是发现,那个方程在模n下无解。。于是只能使用矩阵快速幂来做计算

完整exp如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
from Crypto_tools import *

target = 2 ** 1024
k =

cipher =


def get_f(k, i):
assert len(k) > i-4 >= 0
return abs((k[i] - 2 * k[i-1] + k[i-2]) * (k[i-2] - k[i-4]) - (k[i-1] - k[i-3]) * (k[i-1] - 2 * k[i-2] + k[i-3]))


f_1 = get_f(k, 4)
f_2 = get_f(k, 5)

n = gcd(f_1, f_2)
print('n = ' + str(n))
assert isPrime(n)

a = ((k[3] - 2 * k[2] + k[1]) * inverse(k[2] - k[0], n)) % n
print('a = ' + str(a))

c = ((k[2] - k[1]) - a * (k[0] + k[1])) % n
print('c = ' + str(c))

initial_stream = [[k[5], k[4], 1],
[0, 0, 0],
[0, 0, 0]]
initial_coefficient = [[a+1, 1, 0],
[a, 0, 0],
[c, 0, 1]]


final_coefficient = matrix_pow(initial_coefficient, 3, target-305, n)
final_stream = matrix_mul(initial_stream, final_coefficient, 3, n)
key = int(final_stream[0][1]) % n
flag = cipher ^ key
print(long_to_bytes(flag))

Lattice_trick

本题考查的是利用格来辅助解方程的技巧,题给了两个等式:

pq=n

112020p2+452020q2mmodN

根本的困难在于第二个式子中的因子太大,利用sage无法直接求解模方程,我起初是想通过化简式子或是直接将等式搬到格上,但都没有成功,最终看了badmonkey师傅的exp才意识到可以只利用格子来降低参数,将有限域转化为整数域,再使用sage等工具解方程。

抽象问题为寻找到整数A,使得a112020p2+a452020q2b1p2+b2q2modN

b1,b2 较小,此处不难想到可以构造格子,使b1,b2 为格子上SVP即可。

我尝试过构造:

但由于112020本身的位数过大,LLL后的GapSVP会直接返回(N,N)向量,故需要做一些转换(此处的112020112020在N上的模逆):

由此即可得到向量(a1,a2),有a112020p2+a452020q2a1p2+a2q2modN

a=a1112020,a2a1112020452020modN

分析一下p,q的位数,都是512位,故而p2 or q2 的位数也不会超过1024,而求得的a1,a2中最大的为1023位,可知a1p2+a2q2 最大位数为1024+1+1023=2048,而N的位数为2048,故而只需让k遍历-1到1,必然存在a1p2+a2q2=km+(a1p2+a2q2)%N

又有:

(a1p2+a2q2)%N=((a1112020)(112020p2+452020q2)%N)%N

即可与pq=n 联立求解,完整exp如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from Crypto.Util.number import *
from sage.all import *

r =
n,h,N =
c =
e = 65537
h = (h-pow(14, 2020, N) * (r**2))%N


def Reduce(n,m,h):
inv = (45**2020)*inverse(11**2020,m)
lattice = Matrix([
[1,inv],
[0,m]
])

res = lattice.LLL()
a1 = int(res[0,0])
a2 = int(res[0,1])

if a1<0:
a1,a2 = -a1,-a2%m
print('a1 = ' + str(a1))
print('a2 = ' + str(a2))

tmp = int(a1*inverse(11**2020,m)*h)%m
x = var('x')
y = var('y')

for i in range(-1,2):
cur = tmp + i*m
eq1 = x*y==n
eq2 = a2*x**2 + a1*y**2 - cur == 0
res = solve([eq1,eq2],x,y, solution_dict=True)
if len(res) > 2:
print("Got the solution")
print(res[-1])
return int(abs(res[-1][x])), int(abs(res[-1][y]))
print("No solution for %d"%i)

p, q = Reduce(n//r, N ,h)

phi = (p-1)*(q-1)*(r-1)
d = inverse(e, phi)
c = bytes_to_long(c)
m = pow(c,d,n)
print(long_to_bytes(m))
Copper_smith_e_d

已知:

n=pqr, r, ed1mod((p1)(q1)(r1)), detmodn, e=3

可以看到e非常的小为3,故可知ed=1+k(p1)(q1)(r1) 中k小于3,使k遍历1,2,即可得到等式ed=1+k(p1)(q1)(r1), 再将d3tmodn 变为(ed)327tmodn

从而得到方程:(1+k(p1)(q1)(r1))327tmodn

可化简为(1+k(r1)(pq(p+1)+1))3mod27tmodn

有单变量p+q,分析p+q 的位数最大为1025位,而n的位数为3344, 代入Copper_smith参数

即为:β=1,δ=3,p+q12n13ϵ

可近似为21025112n13ϵ

此处也可以随机取两个位数为1024的素数之和近似p+q,将13ϵ 看作ab,找到满足满足(2(p+q))b<naab最小的,则ϵ=13ab, 寻找代码如下:

1
2
3
4
5
6
7
8
9
10
for i in range(10):
p = getPrime(1024)
q = getPrime(1024)
base = 2 * (p+q)
tmp = []
for i in range(1, 100):
for j in range(1, 100):
if base ** i < n ** j:
tmp.append(j/i)
print(1/3 - min(tmp))

21025的寻找结果为0.025

随机p,q寻找的结果约为0.026,(最终求解后验证得ϵ 约为0.0265)

可知ϵ>0.026,取0.03,将参数代入smallroots求解方程即可得到p+q, 从而得到phi,得到flag,完整exp如下(取0.03时计算时间过长。。。改成0.035或0.04之后很快就出了。。似乎越大越快(迷惑?)):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *


n =
c =
r =
t =

PR.<x> = PolynomialRing(Zmod(n))
e_d_3 = (27 * t) % n
p_q = n//r

for k in range(1, 3):
f = (1+k*(r-1) * (p_q-x+1))^3 - e_d_3
solve_1 = f.monic().small_roots(X=2^1025, beta=1, epsilon=0.04)
if len(solve_1) > 0:
p_add_q = solve_1[0]
phi = (r-1) * (p_q-p_add_q+1)
d = inverse(3, phi)
flag = long_to_bytes(pow(c, d, n))
print(flag)