ECC非对称加密算法

椭圆曲线

椭圆曲线在代数上的表示是下面这个方程: 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))

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(五)——奇异值分解实现推荐算法

一、奇异值分解简介         奇异值分解简称SVD(singular value decomposition),可以理解为:将一个比较复杂的矩阵用更小更简...

258100
来自专栏数据结构与算法

Day5网络流

算法 无源汇上下界可行流 ?  先强制流过l的流量 从s到每个正权点连流量为l的流量  从每个负权点向t连-l的流量 如果容量为0,则不连边 有源汇上下界最大流...

31290
来自专栏专知

【论文推荐】最新六篇情感分析相关论文—深度上下文、支持向量机、两级LSTM、多模态情感分析、软件工程、代码混合

【导读】专知内容组整理了最近六篇情感分析(Sentiment Analysis)相关文章,为大家进行介绍,欢迎查看! 1. Deep contextualize...

1.4K130
来自专栏CDA数据分析师

一篇文章教你如何用R进行数据挖掘

引言 R是一种广泛用于数据分析和统计计算的强大语言,于上世纪90年代开始发展起来。得益于全世界众多 爱好者的无尽努力,大家继而开发出了一种基于R但优于R基本文本...

38050
来自专栏IT大咖说

死磕一周算法,我让服务性能提高 50%

内容来源:haolujun,https://www.cnblogs.com/haolujun/p/9527776.html

19450
来自专栏机器之心

学界 | 密集对象网络:通过机器人操作学习密集的视觉对象描述符

作者:Peter R. Florence、Lucas Manuelli、Russ Tedrake

11930
来自专栏AI研习社

Github 项目推荐 | 用于 C/C++、Java、Matlab/Octave 的特征选择工具箱

FEAST 是用于 C/C++、Java、Matlab/Octave 的特征选择工具集合,它提供了基于滤波器特征选择算法的常用互信息的实现以及 RELIEF 的...

51880
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

超像素经典算法SLIC的代码的深度优化和分析。

     现在这个社会发展的太快,到处都充斥着各种各样的资源,各种开源的平台,如github,codeproject,pudn等等,加上一些大型的官方的开源软件...

514110
来自专栏Echo is learning

machine learning 之 Anomaly detection

13710
来自专栏mathor

第四届蓝桥杯决赛B组C/C++——格子刷油漆

10530

扫码关注云+社区

领取腾讯云代金券