离散对数问题

写在前面#

通常习惯把各种链接资料放在文章末尾，但是这次有很多很多很好的资料，想先写在前面

对sage各种DLP方法的介绍离散对数
pohlig-hellman算法(适用于p-1光滑)很细致的例子离散对数问题——pohlig-hellman算法讲解(有例子)

目前我学习的ECC相关还少，下面的内容基本只涉及普通有限域的内容，

sage函数 #

参数说明：base底，a的对数，ord为base的阶，可以缺省，operation可以是+与*，默认为*；bounds是一个区间(ld, ud)需要保证所计算的对数在此去区间内。

通用的方法： discrete_log(a,base,ord,operation)
Pollard-Rho算法：discrete_log_rho(a,base,ord,operation)
Pollard-kangaroo算法（lambda算法）：discrete_log_lambda(a,base,bounds,operation)
小步大步法(Baby Step Giant Step)：bsgs(base,a,bounds,operation)

一些🌰#

秒解的dlp#

[XYCTF 2024]Complex_dlp#

题目附件

1
from Crypto.Util.number import *
2
from secrets import flag
3

4

5
class Complex:
6
    def __init__(self, re, im):
7
        self.re = re
8
        self.im = im
9

10
    def __mul__(self, c):
11
        re_ = self.re * c.re - self.im * c.im
12
        im_ = self.re * c.im + self.im * c.re
13
        return Complex(re_, im_)
14

15
    def __str__(self):
16
        if self.im == 0:
17
            return str(self.re)
18
        elif self.re == 0:
19
            if abs(self.im) == 1:
20
                return f"{'-' if self.im < 0 else ''}i"
21
            else:
22
                return f"{self.im}i"
23
        else:
24
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"
25

26

27
def complex_pow(c, exp, n):
28
    result = Complex(1, 0)
29
    while exp > 0:
30
        if exp & 1:
31
            result = result * c
32
            result.re = result.re % n
33
            result.im = result.im % n
34
        c = c * c
35
        c.re = c.re % n
36
        c.im = c.im % n
37
        exp >>= 1
38
    return result
39

40

41
flag = flag.strip(b"XYCTF{").strip(b"}")
42
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
43
g = Complex(3, 7)
44
x = bytes_to_long(flag)
45
print(complex_pow(g, x, p))
46
# 5699996596230726507553778181714315375600519769517892864468100565238657988087817 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908i

复数域下的DLP问题

(3+7i)^x \equiv y \pmod{p}

尝试过从模长、辐角和实部虚部自身关系入手，实在难以处理 $\mod{p}$ 这个条件:

自己写一段小数尝试找规律：

1
g = Complex(3,7)
2
p = 17
3
for x in range(64):
4
    y = complex_pow(g,x,p)
5
    re,im = y.re, y.im
6
    print(f"{x = } \t {str(y)} \t {re**2 + im**2} \t {(re**2 + im**2) % p}")
7

8
# x = 0    1               1       1
9
# x = 1    3 + 7i          58      7
10
# x = 2    11 + 8i         185     15
11
# x = 3    11 + 16i        377     3
12
# x = 4    6 + 6i          72      4
13
# x = 5    10 + 9i         181     11
14
# x = 6    1 + 12i         145     9
15
# x = 7    4 + 9i          97      12
16
# x = 8    4i              16      16
17
# x = 9    6 + 12i         180     10
18
# x = 10   2 + 10i         104     2
19
# x = 11   4 + 10i         116     14
20
# x = 12   10 + 7i         149     13
21
# x = 13   15 + 6i         261     6
22
# x = 14   3 + 4i          25      8
23
# x = 15   15 + 16i        481     5
24
# x = 16   1               1       1
25
# x = 17   3 + 7i          58      7
26
# x = 18   11 + 8i         185     15
27
# x = 19   11 + 16i        377     3
28
# x = 20   6 + 6i          72      4
29
# x = 21   10 + 9i         181     11
30
# x = 22   1 + 12i         145     9
31
# x = 23   4 + 9i          97      12
32
# x = 24   4i              16      16
33
# x = 25   6 + 12i         180     10
34
# x = 26   2 + 10i         104     2
35
# x = 27   4 + 10i         116     14
36
# x = 28   10 + 7i         149     13
37
# x = 29   15 + 6i         261     6
38
# x = 30   3 + 4i          25      8
39
# x = 31   15 + 16i        481     5
40
# x = 32   1               1       1
41
# x = 33   3 + 7i          58      7
42
# x = 34   11 + 8i         185     15
43
# x = 35   11 + 16i        377     3
44
# x = 36   6 + 6i          72      4
45
# x = 37   10 + 9i         181     11
46
# x = 38   1 + 12i         145     9
47
# x = 39   4 + 9i          97      12
48
# x = 40   4i              16      16
49
# x = 41   6 + 12i         180     10
50
# x = 42   2 + 10i         104     2
51
# x = 43   4 + 10i         116     14
52
# x = 44   10 + 7i         149     13
53
# x = 45   15 + 6i         261     6
54
# x = 46   3 + 4i          25      8
55
# x = 47   15 + 16i        481     5
56
# x = 48   1               1       1
57
# x = 49   3 + 7i          58      7
58
# x = 50   11 + 8i         185     15
59
# x = 51   11 + 16i        377     3
60
# x = 52   6 + 6i          72      4
61
# x = 53   10 + 9i         181     11
62
# x = 54   1 + 12i         145     9
63
# x = 55   4 + 9i          97      12
64
# x = 56   4i              16      16
65
# x = 57   6 + 12i         180     10
66
# x = 58   2 + 10i         104     2
67
# x = 59   4 + 10i         116     14
68
# x = 60   10 + 7i         149     13
69
# x = 61   15 + 6i         261     6
70
# x = 62   3 + 4i          25      8
71
# x = 63   15 + 16i        481     5

复数 $y_i$ 有明显的循环结构，但是其阶和 $p$ 的关系不明确，瞎猜与 $\varphi(p) = p^2 - 1$ 有关（？）

但是模长平方再模除的循环结构很明确，不完全归纳猜测其阶即为 $p-1$

简单证明一下：

记某复数 $c$ 及其共轭为：

c = (a+bi)\\ \bar{c} = (a-bi)

则二者与模长平方的关系有：

c \bar{c} = \bar{c} c = a^2 - b^2 i^2 = a^2 + b^2

取正整数 $n$ 作为指数：

(c\bar{c})^n = (\bar{c} c)^n =c^n \bar{c} ^ n = \bar{c} ^ n c^n = (a^2 + b^2)^n

关键的一个关系：

(c\bar{c})^n =c^n \bar{c} ^ n

其中 $(c\bar{c}),(c^n \bar{c}^n) \in \mathbb{Z}$ ，就可以应用模除了

1
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
2
re = 5699996596230726507553778181714315375600519769517892864468100565238657988087817
3
im = 198037503897625840198829901785272602849546728822078622977599179234202360717671908
4
Zp = Zmod(p)
5
g = Zp(3^2 + 7^2)
6
y = Zp(re ^ 2 + im ^ 2)
7
print("g =", g)
8
print("y =", y)
9
print("g ^ x = y")
10
# g = 58
11
# y = 440338354863477089588878295048682566041450520053821907911657559153659930236947297
12
# g ^ x = y

最后扔给discrete_log解之：

1
from Crypto.Util.number import *
2
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
3
Zp = Zmod(p)
4
g = Zp(58)
5
y = Zp(440338354863477089588878295048682566041450520053821907911657559153659930236947297)
6
# g ^ x = y
7
x = discrete_log(y,g)
8
print("x =",x)
9
print(long_to_bytes(x))
10
# x = 11043386733210093783917591062922767739440701223101839768310052590794700044066655
11
# b'___c0mp13x_d1p_15_3@5y_f0r_y0u___'

秒解的原因猜测 —— $(p-1)$ 光滑，可用pohlig-hellman算法

1
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
2
print(factor(p-1))
3
# 2 * 269 * 1787 * 12923 * 13513 * 25127 * 26267 * 31957 * 49921 * 57163 * 60101 * 71353 * 73039 * 73091 * 75193 * 76163 * 88001 * 96233 * 100469

音乐

离散对数问题

写在前面#

sage函数 #

一些🌰#

秒解的dlp#

[XYCTF 2024]Complex_dlp#

需要#

评论区

文章目录

音乐

离散对数问题

写在前面#

sage函数#

一些🌰#

秒解的dlp#

[XYCTF 2024]Complex_dlp#

需要#

评论区

文章目录

sage函数 #