当前位置:首页 >> 信息与通信 >>

离散对数问题其及应用---ZML


离散对数问题及其应用
主讲人:ZML

离散对数问题(单向性)
模算术 时钟算术

x mod p
45 mod 60 105 mod 60

例:

我们考虑当模数 p为素数的情形,比如: 17

离散对数问题

集合G ? ?1, 16? 在 mod17的乘法运算下
*

可以构成一个乘法循环群
可以找到一个原根(生成元)g , 生成乘法群G 中所有元素: G ? ? g , g , g ,..., g
* 0 1 2
i

*

15

? ?? g ? .

记?i ? g mod p (i ? 0,1, 14,15)

利用原根的求解算法: 对于奇素数p, p ? 1 ? ? pi ei
i ?1 s

离散对数问题

2 12 4
7 8

6

1

若g

p ?1 pi

3 9 10

? 1(mod p ), 对所有的pi

则g是模 p 的一个原根。

容易找到一个原根 g ? 3

14

16 11 15

13 5

离散对数问题

原根 g ? 3
i

p ? 17
2 6 1

?i ? 3 mod17

i?0
3 9 10

12 4
7 8 14

? 0 ? 3 mod17
0

16 11 15

13 5

离散对数问题

原根 g ? 3
i

p ? 17
2 6 1

?i ? 3 mod17

12 4
7 8 14

3

i ?1
9 10

?1 ? 3 mod17
1

16 11 15

13 5

离散对数问题

原根 g ? 3
i

p ? 17
2 6 1

?i ? 3 mod17

12 4
7 8 14

3

? 2 ? 3 mod17
2

i ? 2 9
10

16 11 15

13 5

离散对数问题

原根 g ? 3
i

p ? 17
2

?i ? 3 mod17
?15 ? 3 mod17
15

i ? 15
6 1

12 4
7 8 14

3 9 10 13 5

? 6 mod17

16 11 15

离散对数问题

原根 g ? 3
i
16

p ? 17
2 12
4 7 8 6

?i ? 3 mod17
15

i ? 16 "0"
1
“周期”

?16 ? 3 mod17
? 3 ? 3mod17
ord ( g ) ? p ? 1 k k mod p ?1 g ?g mod p
“循环”

3 9 10

14

16 11 15

13 5

离散对数问题

原根 g ? 3
?

p ? 17
i??
4
7 8 14 16 11 15 2 12 6 1 3 9 10 13 5

3 ? 12 mod17
Hard!!!
离散“对数”问题

离散对数问题

单向函数
3 mod 17 3 mod 17
NP问题
? 29

EASY

12 12

HARD

离散对数问题的应用

Diffie-Hellman Key Exchange Protocol

Whitfield Diffie

Martin Hellman

Alice

Bob

? p, g ?
Sk A

? p, g ?
Sk B

Pk A ? g

Sk A

mod p

Pk B ? g

Sk B

mod p

Pk B

Pk A

Pk B

Sk A

mod p

Pk A

Sk B

mod p

Alice

Bob

? p, g ?
Sk A

? p, g ?
Sk B

Alice

Bob

?17,3?
Sk A ? 13

?17,3?
Sk B ? 6

Pk A ? g

Sk A

mod p

Pk B ? g

Sk B

mod p

313 ? 12 mod17 36 ? 15 mod17

Pk B

Pk A

Pk B ? 15
13

Pk A ? 12
6

Pk B

Sk A

mod p

Pk A

Sk B

mod p

15 ? 2 mod17 12 ? 2 mod17

小结
? 基于乘法群,构建了一个NP困难问题(离散对数问题)
? 应用于构造安全的密码算法或协议
? DH密钥交换方案 ? ElGamal公钥密码算法 ? 基于离散对数问题的比特承诺方案

The End!



相关文章:
更多相关标签: