首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >ECC非对称加密算法

ECC非对称加密算法

作者头像
用户1733462
发布2018-06-01 14:28:13
3K0
发布2018-06-01 14:28:13
举报
文章被收录于专栏:数据处理数据处理

椭圆曲线

椭圆曲线在代数上的表示是下面这个方程: y2 = x3 + ax + b 其中,a = 0, b = 7 (比特币系统所使用的版本),它的图形如下:

椭圆曲线有一些很有用的特征

  • 一条非垂直的直线与椭圆曲线相交于两点,若这两点均不是切点,则曲线上必有第三点与那条直线相交
  • 过曲线上任意一点的非垂直切线与该曲线必有且仅有另一个交点。

利用这些特征,我们可以定义两种运算:“异点相加”和“同点加倍”。

“异点相加”, P + Q = r, 定义为:r为r’基于x轴的反射点(对称点)。其中,R’为包含P和Q的直线与曲线的第三个交点,如图上所示。

同样,“同点加倍”,P + P = r, 定义为:作一条过P点的切线,先求出该切线与曲线的另一交点R’,再计算r‘基于x轴的反射点r。

求r 坐标,得到一个非常美的结果

当p!=q

当p=q

有限域

同时,并不是所有的椭圆曲线都适合加密。y2=x3+ax+b是一类可以用来加密的椭圆曲线,也是最为简单的一类。下面我们就把y2=x3+ax+b 这条曲线定义在Fp(模p剩余类构成的域)上: 选择两个满足下列条件的小于p(p为素数)的非负整数a、b 4a3+27b2≠0 (mod p) 则满足下列方程的所有点(x,y),再加上 无穷远点O∞ ,构成一条椭圆曲线。 y2=x3+ax+b (mod p) 其中 x,y属于0到p-1间的整数,准确的说是模素数p剩余类,并将这条椭圆曲线记为Ep(a,b)。

这里为什么要加上无穷远点呢,无穷远点来自于射影平面,射影平面比欧式平面多了无穷远点,所有无穷远点构成无穷远直线,射影平面有一个重要假设:

平行线在无穷远处相较于一个点,即无穷远点O点,并且每条直线只有一个无穷远点

在椭圆曲线Ep(a,b)中p1+r1=O,p1+O=p1,p2+r2=O,p2+O=p2 所有椭圆线点按照P+Q=r算法构成加群 O为单元零元,p1,r1互为逆元,p2,r2互为逆元。

举个例子

令p = 71,a=0,b=7,曲线点已经离散了,但还是对称的,对称点互为逆元

加群有72个元素(加一个无穷远点)每个元素阶如下。

令p = 79,a=0,b=7,加群元素个数67(素数),素数阶群,每个元素的阶(除了单位元)都是67,都是群的生成元,计算出来结果

算法原理

考虑如下等式:K=kG [其中 K,G为Ep(a,b)上的点,k为小于n(n是点G的阶)的整数],不难发现,给定k和G,根据加法法则,计算K很容易;但给定K和G,求k就相对困难了。这就是椭圆曲线加密算法采用的难题,我们把点G称为基点(base point)。

加解密流程: 1、用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G。 2、用户A选择一个私有密钥k,并生成公开密钥K=kG。 3、用户A将Ep(a,b)和点K,G传给用户B。 4、用户B接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数r。 5、用户B计算点C1=M+rK;C2=rG。 6、用户B将C1、C2传给用户A。 7、用户A接到信息后,计算C1-kC2,结果就是点M。因为 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M, 再对点M进行解码就可以得到明文。

G = (1,18)
prikey = 40
pubkey = get_add(G, prikey)
r = 16
M = (34,24)
C1 = get_r(M,get_add(pubkey, r))
C2 = get_add(G, r)
temp = get_add(C2,prikey)
get_r(C1,(temp[0], MOD-temp[1]))]))

最后一步解密结果和原文一样

[34, 24]

签名过程如下:

1、选择一条椭圆曲线Ep(a,b),和基点G; 2、选择私有密钥k(k<n,n为G的阶),利用基点G计算公开密钥K=kG; 3、产生一个随机整数r(r<n),计算点R=rG; 4、将原数据和点R的坐标值x,y作为参数,计算SHA1做为hash,即Hash=SHA1(原数据,x,y); 5、计算s≡r - Hash * k (mod n) 6、r和s做为签名值,如果r和s其中一个为0,重新从第3步开始执行

验证过程如下: 1、接受方在收到消息(m)和签名值(r,s)后,进行以下运算 2、计算:sG+H(m)K=(x1,y1), r1≡ x1 mod p。 3、验证等式:r1 ≡ r mod p。 4、如果等式成立,接受签名,否则签名无效。

import numpy as np
import  sys  
import matplotlib.pyplot as plt
def ecc_equation(a, b):
    def ecc(x):
        return x**3+a*x+7
    return ecc

# 求平方根
def get_square_root_mod(mod):
    def get_square_root(n):
        lr = []
        if n >= mod:
            n = n%mod
        for el in xrange(0, mod):
            if el**2%mod == n:
                return el
    return get_square_root
# y
def get_y(x):
    return [x,get_square_root(ecc(x))]

# 检查点是否在曲线上
def check_point(p, mod=MOD):
    if p[1]**2%mod == (ecc(p[0]))%mod:
        return True
    else:
        return False
# 求element在模mod剩余类群逆元
def invert(element, mod):
    if element >= mod:
        element = element%mod
    if element == 0:
        return None
    for index in xrange(1, mod):
        if element*index%mod == 1:
            return index
# 给出p,q求r=p+q
# if p != q
# c = (py-qy)/(px-qx)
# rx = c^2 - px-qx
# ry = c(px-rx)-py
# if p ==q
# c = (3px^2+a)/2py,rx = c^2-2px,ry=c(px-rx)-py
def get_r(p, q,mod=MOD, a=A):
    p = map(lambda x: x % mod, p)
    q = map(lambda x: x % mod, q)
    if p[0] == q[0] and (p[1]+q[1])%mod==0:
        #互为逆元点和为无穷远点,方便处理 记为[np.infty,np.infty]
        return [np.infty,np.infty]
    if p != q:
        c = (p[1]-q[1])*invert(p[0]-q[0], mod)%mod
    else:
        c = (3*p[0]**2+a)*invert(2*p[1],mod)%mod
    rx = (c**2-p[0]-q[0])%mod
    ry = (c*(p[0]-rx)-p[1])%mod
    return [rx,ry]

# 构建循环群
def cycle_group(generate_el):
    power = [generate_el]
    lr = generate_el
    while True:
        lr = get_r(generate_el, lr)
        power.append(lr)
        if lr == [np.infty, np.infty]:
            return power
# 求倍点
def get_add(G, multiple):
    lr = G
    for index in xrange(1, multiple):
        lr = get_r(lr, G)
    return lr
# 功能同上,利用同点加倍,性能更高
def get_multiple(G, multiple):
    if multiple%2 == 0:
        temp = get_multiple(G, multiple/2)
        return get_r(temp,temp)
    else:
        if multiple > 1:
            temp = get_multiple(G, multiple-1)
            return get_r(G, temp)
        else:
            return G
import numpy as np
import  sys  
import matplotlib.pyplot as plt

A = 0
B = 7
MOD = 79
#79
ecc = ecc_equation(A,B)
get_square_root = get_square_root_mod(MOD)
x = xrange(0,MOD)
y = map(get_y, x)
y = np.array(y)
total = y[np.where(y[:,1]>-1)]
total_inverse =map(lambda x:[x[0], MOD-x[1]],filter(filtery , total))
total = np.concatenate((total, total_inverse),axis=0)
#print total

plt.scatter(total[:,0], total[:,1])
plt.show()
print len(total)
print total[np.where(total[:,1]==0)]
print map(lambda x:len(x), map(cycle_group, total))
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.01.17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 椭圆曲线
  • 椭圆曲线有一些很有用的特征
  • 求r 坐标,得到一个非常美的结果
  • 有限域
  • 算法原理
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档