Sky's blog

椭圆加密算法ECC

Word count: 920 / Reading time: 4 min
2017/06/16 Share

0x00 心酸的开头

今天下午本想做完一道加密,快乐的去学习,结果这个加密愣是给我做到晚上,一怒之下,决定写下来,总不能浪费一下午的时光吧~

0x01 ECC简介

参考链接:http://www.8btc.com/eccmath
大体上的意思是说,给你一个曲线F:y^2=x^3+ax+b
你确定下来a和b,然后找一个在曲线F上的点G(x1,y1)
然后自己随机生成一个k(私钥)
然后生成公钥S=kG
注意,这里的kG可不是k*G这么简单,这是几何意义上的:
S=G+G+G+G+……+G(K个G)
然后把公钥丢出去,私钥留给自己
和RSA差不多啦
重点应该是在于如何求S

1
G(x1,y1),P(x2,y2)

重点来了:核心公式

1
2
3
4
5
x3≡t^2-x1-x2(mod p)
y3≡t(x1-x3)-y1(mod p)
其中
若P=G 则 t=(3x^2+a)/2y1
若P≠G 则 t=(y2-y1)/(x2-x1)

故此可以求出公钥S
为什么这个算法安全呢?你自己试试能不能逆运算就知道了……我跟他正面刚都刚了一下午……

0x02 ECC题目分析

说来就气,先看看题目介绍:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
已知椭圆曲线加密Ep(a,b)参数为

p = 15424654874903

a = 16546484

b = 4548674875

G(6478678675,5636379357093)

私钥为

k = 546768

求公钥K(x,y)

提示:K=kG

提交格式XUSTCTF{x+y}(注意,大括号里面是x和y加起来求和,不是用加号连接)

本来我以为能搜到原题,结果谷歌+百度都无果(可能技巧不够)

那我心想,题解没有,求公钥的算法总有吧(结果又很气,所有的文章里都说可以容易求得,就是不给算法)

于是可怜的我只能自己写一个求公钥脚本了

脚本如下:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# -*- coding:utf8 -*-
a=16546484
p=15424654874903
def egcd(t, b):
if t == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % t, t)
return (g, x - (b // t) * y, y)

def modinv(o, m):
g, x, y = egcd(o, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m

def ecc_m(x1,y1,x2,y2):
if ((x1 == x2) & (y1 == y2)):
fenzi=3*x1*x1+a
fenmu=2*y1
else:
fenzi = y2 - y1
fenmu = x2 - x1
m=(abs(fenzi) * modinv(abs(fenmu), p)) % p
if ((fenzi >= 0 & fenmu >= 0) | (fenzi < 0 & fenmu < 0)):
return m
else:
return p - m

def ecc_x(x1,x2,m):
result_x = m*m-x1-x2
if result_x>0:
return result_x%p
else:
p1=p
if abs(result_x)>p1:
shang=abs(result_x)/p
p1=shang*p+p
return p1+result_x

def ecc_y(x1,result_x,y1,m):
result_y = m*(x1-result_x)-y1
if result_y>0:
return result_y%p
else:
p1 = p
if abs(result_y) > p1:
shang = abs(result_y) / p
p1 = shang * p + p
return p1 + result_y

def ecc_result_x(x1,y1,x2,y2):
m = ecc_m(x1,y1,x2,y2)
result_x=ecc_x(x1,x2,m)
return result_x

def ecc_result_y(x1,y1,x2,y2):
m = ecc_m(x1,y1,x2,y2)
result_x = ecc_x(x1, x2, m)
result_y=ecc_y(x1, result_x, y1, m)
return result_y

x1=x2=x3=6478678675
y1=y2=5636379357093
n=546767
while(n>0):
x2=ecc_result_x(x1,y1,x2,y2)
y2=ecc_result_y(x1,y1,x3,y2)
x3=x2
n-=1
print x2,y2
result = x2+y2
flag = "XUSTCTF{%s}"%result
print flag

运行后即可得到flag

0x03 写在最后

看懂了ECC的公钥算法后就没什么难的了,关键还是在于中间涉及到数论的知识,本人比较渣,想了不少时间,所幸是做出来了~
听说咱大三还要学密码学,里面有这个ECC,哈哈哈哈,以后算公钥我就可以跑脚本啦~

CATALOG
  1. 1. 0x00 心酸的开头
  2. 2. 0x01 ECC简介
  3. 3. 0x02 ECC题目分析
  4. 4. 0x03 写在最后