精华内容
下载资源
问答
  • 圆曲线
    千次阅读
    2022-01-30 11:53:19

    大概了解区块链底层加密算法的同学都会听到一个名词叫”椭圆曲线“,它是抽象代数和数论中一个非常重要的概念,同时也是数学研究领域的一个重要分支,在理论研究上,英国数学家正是借助椭圆曲线证明了费马大定理,在应用上它则在加解密上发挥重大作用。

    椭圆曲线表面上看起来似乎没有那么复杂,任何满足如下形式的方程都称为椭圆曲线:
    y^2 = x ^3 + a.x + b

    它跟一般多项式不同在于,它左边y是取平方。正是因为这个特性,所以椭圆曲线具有x轴对称的特点,这些曲线的图形类似如下形状:
    请添加图片描述
    在比特币中,使用的椭圆曲线有个”不明觉厉“的名称叫secp256k1,其实就是将上面公式中的a取0,b取7,也就是:
    y ^ 2 = x ^ 3 + 7

    在椭圆曲线上,有一些特定点所形成的集合在加解密上能发挥重大作用,因此我们先用代码定义椭圆曲线的点:

    class EllipticPoint:
        def __init__(self, x, y, a, b):
            '''
            x, y, a, b 分别对应椭圆曲线公式上的参数
            '''
            self.x = x
            self.y = y
            self.a = a
            self.b = b
            #验证x,y是否在曲线上,也就是将x,y带入公式后左右两边要想等
            if self.y ** 2 != x ** 3 + a * x + b:
                raise ValueError(f"x:{x}, y:{y} is no a elliptic point")
    
        def __eq__(self, other):
            return self.x == other.x and self.y == other.y and self.a == other.a and self.b == other.b
            
        def __ne__(self, other):
            return self.x != other.x or self.y != other.y or self.a != other.a or self.b != other.b
    

    接下来我们要定义椭圆曲线上点的”加法“,显然这里的加法绝对不是普通四则运算上的加法,根据椭圆曲线的图形特征,任意一条直线与它相交的情况只有三种可能,一种是只有一个交点:
    请添加图片描述
    一种是有三个交点:
    请添加图片描述
    还有一种是有两个交点,这种情况又分为两种情形,分别为:
    请添加图片描述
    这种情形是直线与x轴平行,还有一种情形如下:
    请添加图片描述
    这种情形为直线为椭圆曲线的切线。由此椭圆曲线上点的”加法“定义如下,假设有两个在椭圆曲线上的点A, B,它们所形成直线如果与椭圆曲线有三个交点C,那么将c点沿着x轴对称后所得的点就是A"+"B的结果,情形如下:请添加图片描述

    显然这样的定义会带来困惑,例如当A,B所形成的直线与x轴平行,那么这条直线只会与椭圆曲线形成两个交点,于是就不会像前面描述的那样通过第三个交点来找到A “+” B对应的点。这种情况的处理方法显示出了数学的抽象性,虽然没有第三个交点,但我们可以定义出这个不存在的点,我们认为在这种情况下,A,B所形成的直线与椭圆曲线在”无限远“处相交,我们用I来表示这个定义中的第三个交点,同时我们把这次情况下称A和B互为相反数,也就是 A = -B, B = -A, 眼尖的同学可能从这里联想到了前面描述有限群时的”零元“,其实我们这里就能把这个无限远处的交点I与有限群中的”零元“关联起来。

    我们这么定义的加法就存在若干特性:
    1,对任意一个点A,存在-A,使得 A + -A = I, 所谓-A就是将A根据x轴做对称
    2,A “+” B = “B” + “A”, 这个不难理解,因为A,B两点形成的直线跟椭圆曲线第三个交点都是固定的
    3,(A “+” B) “+” C = A “+” (B “+” C)这个叫结合性,这个就不好理解,我们必须结合图形来看,首先看等式左边的情形:
    请添加图片描述
    接下来看等式右边的情形:请添加图片描述
    可以看到等式左边和右边在计算后,结果都对应右上角的黄色实心点。现在我们可以对点的”加法“进行代码实现,首先我们需要定义点I的坐标,由于改点在无限远处,因此它的x和y坐标都在无穷大出,我们在代码中用None来表示这个点的坐标,于是如果椭圆曲线参数a,b分别取值7,11,那么I的表示为:

    EllipticPoint(None, None, 7, 11)
    

    于是我们希望”加法操作要满足如下情况:

    A = EliipticPoint(-1, -1,7, 11)
    B = EllipticPoint(-1, 1,7, 11)
    I = EllipticPoint(None, None, 7, 11)
    A + B == I
    A + I == A
    B + I == B 
    

    要实现EllipticPoint(None, None, 7, 11),我们需要修改前面的初始化函数,如果x,y取值为None,那么就不用判断点是否在曲线上,于是__init__修改为:

     def __init__(self, x, y, a, b):
            '''
            x, y, a, b 分别对应椭圆曲线公式上的参数
            '''
            self.x = x
            self.y = y
            self.a = a
            self.b = b
            if x is None and y is None:
                return
            #验证x,y是否在曲线上,也就是将x,y带入公式后左右两边要想等
            if self.y ** 2 != x ** 3 + a * x + b:
                raise ValueError(f"x:{x}, y:{y} is no a elliptic point")
    

    接下来我们实现加法操作:

        def __add__(self, other):
            #首先判断给定点在该椭圆曲线上
            if self.a != other.a or self.b != other.b:
                raise ValueError(f"given point is no on the samve elliptic curve")
    
            # 如果本身是零元,那么实现I + A = A
            if self.x is None and self.y is None:
                return other
    
            # 如果输入点是零元,那么加法结果就是本身:
            if other.x is None and other.y is None:
                return self
    
            # 如果输入点与当前点互为相反数,也就是关于x轴对称,那么返回无限远交点I
            if self.x == other.x and self.y == -other.y:
                return EllipticPoint(None, None, self.a, self.b)
    
            '''
            如果当前点与给定点形成的直线与椭圆曲线有三个交点,首先我们要计算A(x1,y1),B(x2,y2)所形成直线的斜率
            s = (y2-y1)/(x2-x1), 于是A,B所形成的直线方程就是 y = s * (x-x1) + y1,
            由于椭圆曲线的方程为 y^2 = x^2 + a*x + b,由于直线与曲线相交,假设叫点的坐标为x', y'
            由于交点在直线上,因此满足 y' = s * (x' - x1) + y1, 同时又满足y' ^ 2 = x' ^ 3 + a * x' + b,
            将左边带入到右边就有:
            (s * (x' - x1)) ^ 2 = x' ^ 3 + a * x' + b
            把公式左边挪到右边然后进行化简后就有:
            x ^3 - (s^2) * (x^2) + (a + 2*(s^2)*x1 - 2*s*y1)*x + b - (s^2)*(x1^2)+2*s*x1*y1-(y1 ^2) = 0  (公式1)
            如果我们把第三个交点C的坐标设置为(x3, y3),于是A,B,C显然能满足如下公式:
            (x-x1)*(x-x2)*(x-x3) = 0
            将其展开后为:
            x^3 - (x1 + x2 + x3) * (x^2) + (x1*x2 + x1*x3 + x2+x3)*x - x1*x2*x3 = 0  (公式2)
            我们把公式1 和公式2中对应项的系数一一对应起来,也就是两个公式中x^3的系数是1,公式1中x^2的系数是(s^2),
            公式2中x^2的系数为(x1 + x2 + x3),于是对应起来:
            s^2 <-> (x1 + x2 + x3)  (#1)
            公式1中x对应系数为(a + 2*(s^2)*x1 - 2*s*y1), 公式2中x对应系数为(x1*x2 + x1*x3 + x2+x3),于是对应起来:
            (a + 2*(s^2)*x1 - 2*s*y1) <-> (x1*x2 + x1*x3 + x2+x3)
            公式1中常数项为b - (s^2)*(x1^2)+2*s*x1*y1-(y1 ^2), 公式2中常数项为 x1*x2*x3,对应起来就是:
            b - (s^2)*(x1^2)+2*s*x1*y1-(y1 ^2) <-> x1*x2*x3
            
            根据代数理论中中的Vieta定律,如果如果两个多项式的根要相同,他们对应项的系数必须相等,于是有:
            s^2 = (x1 + x2 + x3)  (#1)
            (a + 2*(s^2)*x1 - 2*s*y1) = (x1*x2 + x1*x3 + x2+x3)
            b - (s^2)*(x1^2)+2*s*x1*y1-(y1 ^2) = x1*x2*x3
            于是我们可以从(#1)中把x3 解出来:
            x3 = s^2 - x1 - x2 
            然后把x3放入直线方程将y3解出来:
            y3 = -(s(x3-x1)+y1) = s * (x1 - x3) - y1
            '''
            if self.x != other.x:
                s = (other.y - self.y) / (other.x - self.x)
                x3 = s ** 2 - self.x - other.x
                y3 = s * (self.x - x3) - self.y
                return EllipticPoint(x3, y3, self.a, self.b)
            '''
            如果self.x == other.x and self.y == other.y ,这种情况下对应椭圆曲线上一点的切线,这时
            我们要计算切线与曲线的另一个交点。根据微积分,函数f(x)在给定点x处的切线对应斜率就是f'(x),
            椭圆曲线函数为y^2 = x^3 + a*x + b, 左右两步对x求导有:
            2y*(d(y)/d(x)) = 3x^2 + a, d(y)/d(x)就是f'(x),我们需要将其计算出来,也就有:
            s = d(y)/d(x) = (3*x^2+a)/(2*y),接下来的计算跟上面一样,只不过把x2换成x1,于是有:
            x3 = s^2 - 2*x1, y3 = s * (x1 - x3) - y1
            '''
            if self == other and self.y != 0:
                s = (3 * self.x ** 2 + self.a) / 2 * self.y
                x3 = s ** 2 - 2 * self.x
                y3 = s * (self.x - x3) - self.y
                return EllipticPoint(x3, y3, self.a, self.b)
    
            '''
            还有最后一种情况,直线不但与y轴平行,而且还是曲线的切线,有就是一根竖直线与曲线在圆头出相切,
            这个点也是y坐标为0的点
            '''
            if self == other and self.y == 0:
                return EllipticPoint(None, None, self.a, self.b)
    

    在两点的"加法“操作中有一些数学推导,例如用到了线性代数中的Vieta定理,它的证明我们不用关心,直接采用其结论就好了。在计算椭圆曲线两点相加时,总共有四种情况要考虑,分别为两点形成的直线与曲线相交于第3点;两点在同一条竖直线上;两点其实是同一点,这种情况计算改点切线与曲线相交的另一点;两点都是同一点,而且y坐标为0,这种情况如下图所示:
    请添加图片描述
    我们测试完成的代码看看情况:

    #曲线上一点的切线与曲线交点
    a = EllipticPoint(-1, -1, 5, 7)
    print(a + a)
    
    #曲线上两点形成的连线与曲线相交于第3点
    a = EllipticPoint(2, 5, 5, 7)
    b = EllipticPoint(-1, -1, 5, 7)
    print(a + b)
    
    #曲线上两点在一条竖直线上
    a = EllipticPoint(2, 5, 5, 7)
    b = EllipticPoint(2, -5, 5, 7)
    print(a + b)
    

    代码运行后所得结果如下:

    x:18.0, y:77.0, a:5, b:7
    x:3.0, y:-7.0, a:5, b:7
    x:None, y:None, a:5, b:7
    

    下一节我们看看如何使用椭圆曲线来进行加解密。代码该链接获取https://github.com/wycl16514/Point_Of_Elliptic_Curve.git

    更多相关内容
  • 圆曲线坐标计算公式

    2020-07-11 07:27:04
    圆曲线中桩边桩坐标计算公式:X=XZY+2&TImes;R&TImes;SIN(L&pide;2R)&TImes;COS{α±(L&pide;2R)}+S&TImes;COS{α±(L&pide;R)+M};Y =YZY+2×R×SIN(L&pide;2R)×SIN{α±(L&pide;2R)}+S×SIN{α±(L&...
  • 圆曲线.zip,圆曲线计算,Form1.cs,Program.cs,.vs,圆曲线计算,v16,.suo,Server,sqlite3,storage.ide,db.lock,Form1.resx,Properties,Settings.settings,Resources.Designer.cs,AssemblyInfo.cs,Settings.Designer.cs,...
  • 通过对椭圆和抛物曲线零件的数控车削加工来研究圆弧插补逼近非圆曲线的应用。计算非圆曲线上任一点的曲率半径R值,解决圆弧逼近非圆曲线的难点。采用HNC-21华中数控系统中的变量和复合循环指令来编写加工程序,并在...
  • 曲线坐标计算程序可计算圆曲线带有缓和曲线中、边桩坐标及切线方位角,若只需计算圆曲线则缓和曲线输入0即可。 功能介绍 1、本软件可计算圆曲线带有缓和曲线中、边桩坐标及切线方位角,若只需计算圆曲线则缓和曲线...
  • 文中利用平面几何学"同弧上的弦切角等于所对圆心角的一半"定理,解决圆曲线上任意点坐标计算中方位角推算方法,此方法可直接得到圆曲线上任意点的坐标方位角和边长,省略了标准计算方法通过切点为中间过渡的计算办法,最...
  • 椭圆曲线

    千次阅读 2021-05-07 14:42:39
    一,椭圆曲线 在椭圆曲线加密https://blog.csdn.net/nameofcsdn/article/details/115627882一文中,主要讨论的是,椭圆曲线的一些和加密相关的特性, 本文讨论其他的一些特性。 椭圆曲线加密中给出了常用椭圆曲线...

    目录

    一,椭圆曲线

    二,椭圆曲线上的有理点

    1,y^2=x^3+x

    2,y^2=x^3-4x^2+16

    3,y^2=x^3+17

    三,挠点系

    1,挠点系

    2,挠点系的意义

    3,有理挠点系

    4,挠定理

    (1)Nagell-Lutz定理

    (2)Mazur定理

    四,椭圆曲线上的整点

    1,挠点系和整点

    2,y^2=x^3+17

    3,Siegel定理


    一,椭圆曲线

    在椭圆曲线加密https://blog.csdn.net/nameofcsdn/article/details/115627882一文中,主要讨论的是,椭圆曲线的一些和加密相关的特性,

    本文讨论其他的一些特性。

    椭圆曲线加密中给出了常用椭圆曲线的方程y^2=ax^3+bx^2+cx+d

    本文使用它规约之后的形式:y^2=x^3+ax^2+bx+c

    ​​​​​​​判别式:\Delta =-4a^3c+a^2b^2-4b^3-27c^2+18abc   如果\Delta不为0那么它就是椭圆曲线。

    参考:https://blog.csdn.net/nameofcsdn/article/details/105172343

    本文不讨论加密,所以没有无穷远点。

     

     

    二,椭圆曲线上的有理点

    1,y^2=x^3+x

    证明曲线y^2=x^3+x上唯一的有理点是(0,0)

    证明:假设存在其他有理解,设x=a/b,y=c/d

    \frac{c^2}{d^2}=\frac{a^3+ab^2}{b^3}

    两边都是最简分数,所以c^2=a^3+ab^2,d^2=b^3

    所以c=st,a=s^2,a^2+b^2=t^2,b=u^2,d=u^3

    所以s^4+u^4=t^2

    而这个方程其实是无解的,证明参考https://blog.csdn.net/nameofcsdn/article/details/115708334

    所以y^2=x^3+x没有其他有理解。

    2,y^2=x^3-4x^2+16

    曲线y^2=x^3-4x^2+16上只有4个有理点:x=0或4,y=4或-4

    这4个点连成的6条直线,有2条是垂直的,还有4条分别是这4个点处的切线,这6条直线都和曲线没有第三个交点。

    3,y^2=x^3+17

    曲线y^2=x^3+17上有无穷多有理点

     

    三,挠点系

    椭圆曲线y^2=x^3+ax^2+bx+c,其中a,b,c都是整数

    1,挠点系

    如果椭圆曲线上有t个点,t>=3,

    且任意两点连成的直线,要么和曲线没有第三个交点,要么第三个交点就在这t个点中,

    那么我们称,这t个点构成一个挠点系。

    2,挠点系的意义

    挠点系的存在告诉我们,通过连接直线寻找第三个点的方法,有可能只能找到有限个点。

    3,有理挠点系

    如果一个挠点系中都是有理点,那么我们称之为有理挠点系。

    显然,2个有理点连成的直线,要么和曲线交于有理点,要么没有第三个交点。

    所以,如果有理点的个数是有限的,那么所有的有理点就可以构成一个挠点系

    4,挠定理

    如果椭圆曲线存在有理挠点系,判别式\Delta =-4a^3c+a^2b^2-4b^3-27c^2+18abc不为0,那么:

    (1)Nagell-Lutz定理

    该挠点系中所有点都是整点,且对于每个点,纵坐标y要么是0,要么满足y^2|16\Delta

    PS:有可能有整点不在挠点系中

    (2)Mazur定理

    该挠点系中至多只有15个点

    PS:有理点要么不超过15个,要么有无穷多个。如果一个有理点不在任何一个挠点系中,那么有理点一定是无穷多的。

     

    四,椭圆曲线上的整点

    1,挠点系和整点

    因为通过2个整点并不能直接得到一个新的整点(这和有理点不同),所以挠定理和整点关系不大。

    有可能有整点不在挠点系中。

    2,y^2=x^3+17

    曲线y^2=x^3+17上的整点(-2,3)不在任何一个挠点系中。

    在x<10^100的范围内,所有的整点如下:

    x=-1,-2,2,4,8,43,42,5234,一共16个点。

    看起来似乎x大于5234的整点非常少,有可能没有了。

    3,Siegel定理

    椭圆曲线y^2=x^3+ax^2+bx+c,其中a,b,c都是整数

    如果判别式\Delta =-4a^3c+a^2b^2-4b^3-27c^2+18abc不为0,那么曲线上只有有限个整点

    展开全文
  • 椭圆曲线密码学导论(中文).pdf
  • 采用最小二乘法拟合圆曲线(matlab程序)采用最小二乘法拟合圆曲线(matlab程序)采用最小二乘法拟合圆曲线(matlab程序)采用最小二乘法拟合圆曲线(matlab程序)采用最小二乘法拟合圆曲线(matlab程序)采用最小...
  • 圆曲线放样要素计算

    2016-06-03 17:53:20
    圆曲线放样点坐标计算
  • 文中详细叙述了圆曲线巷道的施测、检查过程,综合运用CAD、全站仪、CASIO计算器的先进性能,结合生产实际总结出了圆曲线施工的具体步骤,实用性较好,供工程技术人员参考。
  • 椭圆曲线入门详解

    千次阅读 2021-04-20 07:11:23
    转载请注明http://blog.csdn.net/boksic 如有疑问欢迎留言如果不知道数学上...什么是椭圆曲线椭圆曲线(Elliptic curve)叫椭圆曲线只是因为方程跟椭圆的曲线积分比较相似椭圆曲线方程可以统一为当然还有要求至于长什...

    转载请注明http://blog.csdn.net/boksic 如有疑问欢迎留言

    如果不知道数学上的群、循环群等概念,可以先了解ElGamal加密算法 后再回过来椭圆曲线加密

    这两个算法有共通之处,都是在离散问题难解群上的加密算法,椭圆曲线是进一步的加深

    首先,什么是椭圆曲线

    椭圆曲线(Elliptic curve)

    叫椭圆曲线只是因为方程跟椭圆的曲线积分比较相似

    椭圆曲线方程可以统一为

    75862713_1.png当然还有要求

    至于长什么样,绘个图看看

    用matlab写了一个模拟程序,可以控制a,b变化,显示曲线的图像。

    clear;clc;figure(1);

    a=0;

    b=0;

    h_text1=uicontrol('Style','text','String','a','Position',[50 20 50 20]);

    h_text1=uicontrol('Style','text','String','b','Position',[50 0 50 20]);

    ezplot(strcat('x+',num2str(a),'*y'));

    h_slider1=uicontrol('Style','slider','Position',[100 20 200 20],...

    'Max',10,'Min',-10,'callback',['a=num2str(get(gcbo,''value''));',...

    'ezplot(strcat(num2str(b),''+x^3+'',num2str(a),''*x-y^2''))']);

    %h_text2=uicontrol('Style','text','String','b');

    h_slider2=uicontrol('Style','slider','Position',[100 0 200 20],...

    'Max',10,'Min',-10,'callback',['b=num2str(get(gcbo,''value''));',...

    'ezplot(strcat(num2str(b),''+x^3+'',num2str(a),''*x-y^2''))']);

    75862713_2.gif

    再直观一点

    (不得不说在这方面,Mathematica比Matlab要方便强力太多,用MATLAB做这个图像速度慢代码长步骤复杂效果烂)

    b=0,a在[-20,20]上变动时的图像

    a=-6,b在[-20,20]上变动时的图像

    Plot3D[{(x^3+y*x)^0.5,-(x^3+y*x)^0.5},{x,-7,7},{y,-20,20}]

    Plot3D[{(x^3-6x+y)^0.5,-(x^3-6x+y)^0.5},{x,-7,7},{y,20,-20}]

    75862713_3.gif

    75862713_4.gif

    "受ElGamal密码启发,在其它离散对数问题难解的群中,同样可以构成ELGamal密码。于是人们开始寻找其它离散问题难解的群。研究发现,有限域GF(p)上的椭圆曲线的解点构成交换群,而且离散对数问题是难解的。于是可在此群上建立ELGamal密码,并称为椭圆曲线密码。"

    解点交换群

    为了构成加法交换群,需要定义元素、单位元、逆元素、加法

    解点

    设p是大于3的素数,且4a3+27b2 ≠0 mod p ,称

    y^2 =x^3 +ax+b ,a,b∈GF(p)

    为GF(p)上的椭圆曲线。

    由椭圆曲线可得到一个同余方程:

    y^2 =x^3 +ax+b    mod p

    其解为一个二元组,x,y∈GF(p),将此二元组描画到椭圆曲线上便为一个点,于是又称其为解点。

    单位元

    引进一个无穷点O(∞,∞),简记为0,作为0元素。

    O(∞,∞)+O(∞,∞)=0+0=0 。

    并定义对于所有的解点P(x ,y)有

    P(x ,y)+O=O+ P(x ,y)=P(x ,y)

    逆元素

    任何解点R(x ,y)的逆就是 R(x ,-y)。

    加法

    P(x1 ,y1)+Q(x2 ,y2)=R(x3 ,y3)

    (提醒一下,这里的运算都是模运算,值都是整数,像除法是模逆运算)

    定义s = (yP ? yQ)/(xP ?xQ),即PQ线的斜率

    总共3种情况

    1.一般情况下 R = P + Q = (xR, ? yR)其中

    75862713_5.png

    75862713_6.png

    2.如果xP = xQ,yP = ?yQ(包括yP =yQ = 0的情形)

    结果R就是无穷远点0

    3 尽管xP = xQ但yP = yQ ≠ 0那么R =P +P = 2P = (xR,?yR)有

    75862713_7.png

    75862713_8.png

    75862713_6.png

    加法的几何意义

    设P和Q是椭圆曲线的两个点,则连接P和Q的直线与椭圆曲线的另一交点关于横轴的对称点即为R点。在该群中P + Q + R = 0

    75862713_9.png

    椭圆曲线交换群实例

    对于标准方程y^2=x^3+ax+b (mod p) 设定基本参数

    p=31,a=2,b=17

    随便找一个在曲线上(即满足该方程)的点P=(10,13)

    然后按照上面提到的公式来逐一计算2P,3P,4P.....

    我用的Python来计算(调用的mod_inv是模下的除运算,代码可参看前面的文章):

    px,py=10,13

    x,y=px,py

    a,b=2,17

    p=31

    for i in range(p+20):

    if(x==px and y==py):

    x3=(9*x**4-8*x*y**2+6*a*x**2+a**2)\

    *mod_inv(4*y**2,p)%p

    y3=((3*x**2+a)*(x-x3)*mod_inv(2*y,p)-y)%p

    elif(x==px):

    x3,y3=0,0

    elif(x==0 and y==0):

    x3,y3=px,py

    else:

    x3=(((y-py)*mod_inv(x-px,p))**2-x-px)%p

    y3=((y-py)*(px-x3)*mod_inv(x-px,p)-py)%p

    str = "%dP= (%d,%d)"%(i+2,x3,y3)

    print str,

    x,y=x3,y3

    可以得到

    2P= (21,19) 3P= (19,30) 4P= (27,10)

    5P= (29,25) 6P= (24,1) 7P= (30,13)

    8P= (22,18) 9P= (8,24) 10P= (20,11)

    11P= (6,11) 12P= (23,27) 13P= (12,23)

    14P= (3,22) 15P= (7,23) 16P= (1,19)

    17P= (17,2) 18P= (9,12) 19P= (13,15)

    20P= (5,11) 21P= (5,20) 22P= (13,16)

    23P= (9,19) 24P= (17,29) 25P= (1,12)

    26P= (7,8) 27P= (3,9) 28P= (12,8)

    29P= (23,4) 30P= (6,20) 31P= (20,20)

    32P= (8,7) 33P= (22,13) 34P= (30,18)

    35P= (24,30) 36P= (29,6) 37P= (27,21)

    38P= (19,1) 39P= (21,12) 40P= (10,18)

    41P= (0,0) 42P= (10,13)

    matlab显示一下,点的分布与顺序都是杂乱无章

    75862713_10.gif

    展开全文
  • 首先提出一个基于椭圆曲线密码体制的签密方案。该方案是数字签名和公钥加密的有机集成,除了具有认证性、保密性外,还具有计算量与通信量小等特点。在此基础上,构造了一个基于椭圆曲线密码体制的(t,n)门限签密...
  • 椭圆曲线数字签名算法(ECDSA)

    千次阅读 2022-02-01 22:40:42
    一. 椭圆曲线加密算法 简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全,RSA加密算法也是一种非对称加密算法,在公开密钥加密和...

    一. 椭圆曲线加密算法
    简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全,RSA加密算法也是一种非对称加密算法,在公开密钥加密和电子商业中RSA被广泛使用。据研究,160位ECC加密安全性相当于1024位RSA加密,210位ECC加密安全性相当于2048位RSA加密(有待考证)
    二. 什么是椭圆曲线
    Wolfram MathWorld给出了个准确非凡的定义椭圆曲线。椭圆曲线可以暂时简单的理解为描述了特定点的集合的公式:
    在这里插入图片描述
    以下是a和b参数的变化对应的图形的示例:
    在这里插入图片描述
    b=1,a取值范围从2到-3
    在这里插入图片描述
    特殊曲线:左边参数是a=b=0,右边参数是a=-3,b=2.这两条都不是符合标准的曲线。
    a和b的取值变化决定了曲线在坐标系上的不同形状。从图中可以看到,椭圆曲线是相对X轴对称。
    另外定义一个无穷大的点(也可以成为理想点),以符号0,也就是零表示该点。
    三. 阿贝尔群
    椭圆曲线也可以有运算,像实数的加减乘除一样,这就需要使用到加群。19世纪挪威的尼尔斯·阿贝尔抽象出了加群(又叫阿贝尔群或交换群)。数学中的群是一个集合,我们为它定义了一个“加法”,并用符号+表示。假定群用 表示,则加法必须遵循以下四个特性:

    封闭性:如果a和b都是 的成员,那么a+b也是 的成员;
    结合律:(a + b) + c = a + (b + c);
    单位元:a+0=0+a=a,0就是单位元;
    逆元:对于任意值a必定存在b,使得a+b=0。

    如果再增加一个条件,交换律:a + b = b + a,则称这个群为阿贝尔群,根据这个定义整数集是个阿贝尔群。

    四. 椭圆的几何加法
    因为椭圆曲线是阿贝尔群,所以公式P+Q+R=0 以及 P+Q=−R成立。在椭圆曲线上画出点P和点Q,连直线穿过P和Q,该直线会与椭圆曲线相较于第三个点,称之为R。根据R取得R的逆元-R,P+Q=-R。
    在这里插入图片描述
    运用几何学的方法很容易得到我们要的结果,但是我们需要再对一些更精确的解释。特别是有一些问题需要考虑:
    • 如果P=0或者Q=0(0是无穷远点)呢?无法画出该直线,因为无穷远点无法体现在直角坐标系里。但是既然已经定义了无穷远点0,那么对于任意给定的P或者Q,P+0=P以及0+Q=Q都是成立的。
    • 如果P=-Q呢?这种情况下该直线是与X轴是垂直的,并且不会与椭圆曲线相交于第三个点。 根据公理,P就是Q的逆元,P+Q=P+(-P)=0。
    • 如果P=Q呢?这种情况下,存在无数条线穿过这个点。这里要用到极限的思维。假设线上有另外一个点Q1,让Q1不断靠近P, 随着Q1不断靠近P,最终Q1无限靠近P,产生了一条直线与椭圆曲线相切。那么可以得到 P+P=-R, 在这里R就是该直线与椭圆曲线的另外一个交点。
    在这里插入图片描述
    • 如果P≠Q,但是不存在第三个交点R呢?这种情况和上一个情况很类似。实际上,这种情况下该直线跟椭圆曲线是相切的关系。
    在这里插入图片描述
    假设P就是相切的点。在上一个情况里,有该等式P+P=-Q。而在这里变成了P+Q=-P。另一方面,如果Q是相切的点,那么P+Q=-Q。
    五. 代数上的加法
    要计算点的加法的话,我们必须把前面的几何学的讨论转到代数上的讨论,考虑非0,非对称的点P(x1,y1)和Q(x2,y2),R(x3,y3)为过P,Q与曲线相交点,则:
    x3=k^2−x1−x2
    y3=k(x1−x3)−y1
    若P=Q,则k=(3x1^2+a)/2y1
    若P≠Q,则k= (y2−y1)/ (x2−x1)

    六. 标量乘法
    同点加法,若有k个相同的点P相加,记作kP 。 P+P=2P
    在这里插入图片描述
    P+P+P=2P+P=3P
    在这里插入图片描述
    七. 有限域椭圆曲线
    椭圆曲线是连续的,并不适合用于加密;所以,我们必须把椭圆曲线变成离散的点,我们要把椭圆曲线定义在有限域上。
    我们给出一个有限域Fp
    1.Fp中有p(p为质数)个元素0,1,2,…, p-2,p-1
    2.Fp的加法是a + b ≡ c ( m o d p )
    3.Fp的乘法是a × b ≡ c ( m o d p )
    4.Fp的除法是a ÷ b ≡ c ( m o d p ) , 即 a × b ^− 1 ≡ c ( m o d p ) , b^ − 1 也 是 一 个 0 到 p − 1 之 间 的 整 数 , 但 满 足 b × b ^− 1 ≡ 1 ( m o d p )
    5.Fp的单位元是1,零元是 0
    6.Fp域内运算满足交换律、结合律、分配律
    7.椭圆曲线Ep(a,b),p为质数,x,y∈[0,p-1]
    在这里插入图片描述
    选择两个满足下列约束条件的小于p的非负整数a、b :
    在这里插入图片描述
    有限域椭圆曲线点的阶, 如果椭圆曲线上一点P,存在最小的正整数n使得数乘n P = O∞,则将n称为P的阶,若n不存在,则P是无限阶的.

    八. 椭圆曲线加密
    考虑K=kG,其中K、G为椭圆曲线Ep(a,b)上的点,n为G的阶(n G = O∞ ),k为小于n的整数。则给定k和G,根据加法法则,计算K很容易但反过来,给定K和G,求k就非常困难。因为实际使用中的ECC原则上把p取得相当大,n也相当大,要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据 。

    1.点G称为基点(base point)
    2.k(k<n)为私有密钥(private key)
    3.K为公开密钥(public key)

    下面是利用椭圆曲线进行加密通信的过程(公钥加密私钥解密过程):
    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(r<n)。
    5、用户B计算点C 1 = M + r K和C 2 = r G。
    6、用户B将C 1 、 C 2 传给用户A。
    7、用户A接到信息后,计算C 1 − k C 2 ,结果就是点M。再对点M进行解码就可以得到明文。
    因为C 1 − k C 2 = M + r K − k ( r G ) = M + r k G − k r G = M

    九. 数字签名
    数字签名是公钥密码学发展过程中最重要的概念之一,产生和使用数字签名过程的一般模型如图所示
    在这里插入图片描述
    十. 椭圆曲线数字签名算法(ECDSA)
    ECDSA处理过程:
    1.参与数字签名的所有通信方都使用相同的全局参数,用于定义椭圆曲线以及曲线上的基点
    2.签名者首先生成一对公私钥。对于私钥,选择一个随机数或者伪随机数作为私钥,利用随机数和基点算出另一点,作为公钥
    3.对消息计算Hash值,用私钥、全局参数和Hash值生成签名
    4.验证者用签名者的公钥、全局参数等验证。
    全局参数:
    在这里插入图片描述
    密钥生成:
    每个签名者都要生成一对公私钥,假设是Bob
    在这里插入图片描述
    这里是定义在在这里插入图片描述
    上的椭圆曲线,椭圆曲线上的乘法运算就是多个点的累加运算,最后的结果还是椭圆曲线上的点,有了公钥之后,Bob对消息m生成320字节的数字签名:
    在这里插入图片描述
    第2步确保最后算出的公钥(椭圆曲线上的点)是落在曲线上。第5步,如果为O点也是不符合的,所以也要重新生成。
    Alice在获得Bob的公钥和全局参数后,即可校验签名
    在这里插入图片描述
    在这里插入图片描述
    该过程有效性证明如下,如果Alice收到的消息确实是Bob签署的,那么
    s = (e+dr)k^-1 mod n
    于是 k= (e+dr)s^-1 mod n
    = (e s^-1 + dr s^-1) mod n
    = (we +wdr) mod n
    =(u1 + u2d) mod n
    现在考虑u1G + u2Q = u1G + u2dG = (u1 + u2d)G = KG
    在验证过程的步骤6中,有v = x1 mod n , 这里解点 X =(x1,y1) = u1G + u2Q。因为
    R = x mod n 且x 是解点kG的x 坐标,又因为 我们已知 u1G + u2Q = KG,所以可得到 v = r。

    展开全文
  • 椭圆曲线公钥密码体制

    千次阅读 2020-06-25 19:34:39
    椭圆曲线公钥密码体制1 背景介绍1.1 密码体制的含义1.2 椭圆曲线密码体制2 算法过程2.1 理论基础2.2 基于离散对数上的难解问题2.3 加解密过程2.4 攻击3 算法实现3.1 运行环境3.2 明文:3.3 实验结果3.4 结果分析4 ...
  • 通过分析非圆曲线类零件数控车削技术编程方法,针对复杂非圆曲线斜椭圆、斜双曲线和斜抛物线数控车削编程中存在的技术难题,利用NC二次曲线创建和三维建模功能完成复杂非圆曲线零件的建模,并研究了复杂非圆曲线零件在...
  • 在中小型企业生产中,为了降低成本,提高利润率,大部分的程序编写还是通过手动编程的方式实现,一...但涉及到双曲线、抛物线、椭圆轮廊等具有非圆曲线零件加工时,G1、G2、G3显得无能为力,这时就需要进行宏程序的编辑使用。
  • 比特币的公钥有65个字节,包括一个前缀加上两个256 bit 的整数,这两个整数就对应椭圆曲线上的一个点的 x 值和 y 值。 第三个是签名,签名就是一个证明我的确执行了签署操作的数字。签名主要由两项内容运算得出,一...
  • 椭圆曲线加法原理计算

    千次阅读 2021-01-03 08:32:59
    3)上的椭圆曲线,因为素域FpF_pFp​的特征不为2,3,所以素域FpF_pFp​上的椭圆曲线E的WeierstrassWeierstrassWeierstrass方程可设为 E:y2=x3+a4x+a6 E: y^2 = x^3 + a_4x + a_6 E:y2=x3+a4​x+a6​ 其判别式Δ=−16...
  • 【密码学-2】什么是椭圆曲线密码

    千次阅读 2022-04-13 20:23:02
    文章目录前言一、椭圆曲线是什么?二、使用步骤1.引入库2.读入数据总结 本文共XXXX字,阅读全文约需X分钟。 前言 上回书我们说到,在常见的三种公钥密码学算法中,椭圆曲线密码学在相同的安全等级下有着更短的密钥...
  • 曲线Curve结构定义一级目录 /// Curve related structs. pub mod curve { pub use crate::{ field::{Field, FieldStorage}, group::{Affine, AffineStorage, Jacobian, AFFINE_G, CURVE_B}, scalar::Scalar, };...
  • 公路工程测量放线圆曲线、缓和曲线(完整缓和曲线、非完整缓和曲线)计算解析.pdf
  • 区块链的基石--椭圆曲线密码学

    千次阅读 2020-12-04 19:08:28
    椭圆曲线密码学椭圆曲线密码学(ECC, Elliptic Curve Cryptography)是基于椭圆曲线数学的一种公钥加密方法。什么是公钥加密方法在诸如 DES、AES 这类对称密码系统中,信息的发送方使用一把密钥进行加密,接收方使用...
  • 国密局发布的SM2椭圆曲线公钥密码算法文档,pdf,完整版的。1、总则;2、数字签名算法;3、密码交换协议;4、公钥加密算法
  • 椭圆曲线密码算法(ECC)

    千次阅读 2019-11-06 18:25:30
    网上有很多关于ECC的文章,但是讲明白的很少,最近发现了一个大佬的博客,里面将ECC...比特币使用椭圆曲线算法生成公钥和私钥,选择的是secp256k1曲线。  椭圆曲线密码学(ECC)是(Elliptic Curve Cryptography)...
  • 讨论比特币的加密算法,椭圆曲线始终是绕不开的坑。以下笔记是观看比特币加密教程总结而成,图片来源于网络。 ECDSA算法 椭圆曲线乘法(又称为ECDSA)是密码学重要的非对称加密算法,同时在比特币系统中,私钥的...
  • 椭圆曲线加解密

    千次阅读 2019-05-16 14:17:41
    椭圆曲线加密算法,即:Elliptic Curve Cryptography,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全。据研究,160位ECC加密安全...
  • 带有缓和曲线的圆曲线放样计算表
  • SM2椭圆曲线

    千次阅读 2019-09-21 18:56:16
    实现SM2椭圆曲线公钥密码算法,对给出的英文消息进行加密得到密文,并能通过密文解密出明文。 环境 Windows10,MinGW-W64-builds-4.3.5,miracl 7.0.1 方案设计 背景 SM2椭圆曲线公钥密码算法,SM3密码杂凑算法 原理...
  • 为了更好地选择非圆曲线轮廓加工的最佳逼近方法,以椭圆曲线轮廓的加工为例,建立了圆弧逼近、直线逼近和近似加工误差的数学模型,探讨了如何选取圆弧逼近法中逼近圆弧的半径。运用QBASIC编程计算出了相同条件下不同...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 93,253
精华内容 37,301
关键字:

圆曲线

友情链接: ZhiyiaoBasic.rar