零知识证明:椭圆曲线基础

区块链资讯热门分享2020-01-19 18:35:26  阅读 -评论 0

原文标题:《零知识证明 - 椭圆曲线基础》
原文来源:星想法

对椭圆曲线的学习,个人推荐如下的链接,没有太多的术语,解释的比较清楚。

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/

https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/

本文也是在上述链接的基础上的总结。

1. 实数域上的椭圆曲线

 1.1 定义

椭圆曲线的数学定义可以查看 Wolfram MathWorld:http://mathworld.wolfram.com/EllipticCurve.html。不是密码学或者数学专业的小伙伴,看的是一头雾水。便于工程理解,椭圆曲线是一系列满足如下方程的点:

零知识证明:椭圆曲线基础

并且零知识证明:椭圆曲线基础。该方程称为椭圆曲线的 Weierstrass 方程。

如下是 b=1, a 从 2 到-3 的椭圆曲线:

零知识证明:椭圆曲线基础

从方程可以看出,椭圆曲线是关于 x 坐标对称的曲线。除了坐标系上曲线的点,椭圆曲线额外定义一个点(无穷远处),记为 0。

也就是说,椭圆曲线是由如下的点组成:

零知识证明:椭圆曲线基础

1.2 基于椭圆曲线的群定义

在椭圆曲线的基础上,可以定义一个加法群:

*所有椭圆曲线上的点,就是这个群里的元素

*单位元就是 0

*点 P 的逆元是点 P 相对 x 坐标的对称点

*加法定义如下:在椭圆曲线上,和一条直线相交的 3 个点 P,Q 以及 R,三点相加满足零知识证明:椭圆曲线基础。也就说,椭圆曲线上的两点相加的结果,还在椭圆曲线上。

结合群的定义,可以证明定义的这个加法群,就是阿贝尔群。

封闭性:因为椭圆曲线上的点相加,还是椭圆曲线上的点。

结合律:零知识证明:椭圆曲线基础

单位元 : 单位元是 0

逆元 : 一个椭圆曲线上的点 P 的逆元,是相对 x 坐标的对称点

交换律:零知识证明:椭圆曲线基础

1.3 椭圆曲线加法计算

因为零知识证明:椭圆曲线基础,也就是说零知识证明:椭圆曲线基础。计算零知识证明:椭圆曲线基础的方法就比较直观了:连接 P 和 Q 划一条线,该线和椭圆曲线交的另外一个点为 R。零知识证明:椭圆曲线基础的结果就是 R 的逆。

零知识证明:椭圆曲线基础

考虑几种特殊情况,对加法计算进行「修正」:

*零知识证明:椭圆曲线基础或者零知识证明:椭圆曲线基础:因为定义 0 为无穷远处,不能基于无穷远处划线。但是因为定义了 0 为单位元,所以零知识证明:椭圆曲线基础以及零知识证明:椭圆曲线基础

*零知识证明:椭圆曲线基础:因为两个点是对称的,所以基于这两个点划的线垂直于 x 轴,不再相交于其他点。零知识证明:椭圆曲线基础

*零知识证明:椭圆曲线基础:如果 P 和 Q 是同一个点的话,那存在多条线穿过这「两个」点。如果把 Q 看作是无限接近 P 的过程,可以看出,穿过 P 和 Q 的是椭圆曲线在 P 点的切线。如果切线和椭圆曲线相交的点为 R,则零知识证明:椭圆曲线基础零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

*零知识证明:椭圆曲线基础,并且不存在第三个点相交:这种情况和上一种情况有点类似,也就是说,P/Q 的连线是椭圆曲线的切线。如果 P 点是切点,零知识证明:椭圆曲线基础。也就是说,零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

1.4 加法计算推导

加法的定义是完备的。针对最普通的情况,就是在椭圆曲线上一条直线能穿过三个点,分别是 P,Q。

零知识证明:椭圆曲线基础。这条直线有个斜率:

零知识证明:椭圆曲线基础

可以推导出:

零知识证明:椭圆曲线基础

或者

零知识证明:椭圆曲线基础

当然,如果 P/Q 是同一个点的话,斜率的计算公式不同。

1.5 标量乘法(Scalar Multiplication)

在加法的基础上,定义了标量乘法,同一个点相加多次:

零知识证明:椭圆曲线基础

计算标量乘法,最简单的方法是一个个 P 点相加。如果 n 是 k 位的话,算法复杂度是:零知识证明:椭圆曲线基础

有个快速的计算方法:double 后相加。假设 n=151,二进制表示为:零知识证明:椭圆曲线基础

还是用 n=151 举个例子:

零知识证明:椭圆曲线基础

"Double" 主要是依次获得某个位对应的变量的结果。如果该位是 1,就加到最后的结果中。这种算法的复杂度是:零知识证明:椭圆曲线基础

1.6 对数问题

已知 n 和 P,零知识证明:椭圆曲线基础的计算比较容易。但是,在 Q 和 P 已知的情况下,求解 n 非常困难,没有多项式时间求解算法。

2. 有限域上的椭圆曲线

上面介绍的是基于实数的椭圆曲线的点,可以构造一个群。考虑特征数为的有限域,为素数。该有限域是由模 的结果组成,记零知识证明:椭圆曲线基础。因为有限域中的元素都有逆元,也就是零知识证明:椭圆曲线基础,则零知识证明:椭圆曲线基础

2.1 扩展欧几里得定理

给予二整数 a 与 b, 必存在有整数 x 与 y 使得 ax + by = gcd(a,b)。gcd(a,b) 是最大公约数。

2.2 模 p 运算下的乘法逆

假设元素 a,在模运算下,有逆元 x。满足,零知识证明:椭圆曲线基础。也就是说,

零知识证明:椭圆曲线基础

通过扩展欧几里得定理,可以求得 x 和 y。x 就是 a 的乘法逆。

2.3 在 F_p 定义椭圆曲线

零知识证明:椭圆曲线基础上椭圆曲线定义如下:

零知识证明:椭圆曲线基础

定义和实数上的定义类似。如下是零知识证明:椭圆曲线基础,p 分别是 19,97,127,487 对应的椭圆曲线的点。

零知识证明:椭圆曲线基础

椭圆曲线是关于零知识证明:椭圆曲线基础对称,因为

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

在模 p 的情况下,这两个等式相等。

2.4 点加

和实数上椭圆曲线的点加类似,定义在一条「线」上的三点相加等于 0:零知识证明:椭圆曲线基础。在零知识证明:椭圆曲线基础有限域上,一条直线定义为:零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

上图是零知识证明:椭圆曲线基础的椭圆曲线,其中零知识证明:椭圆曲线基础。图中的黄色的一系列的斜线是零知识证明:椭圆曲线基础的直线。R 就在其中一条斜线上,-R 就是图中标出的 R 的对称点,也就是 P+Q 的结果。

点加性质:

*零知识证明:椭圆曲线基础

*零知识证明:椭圆曲线基础,也就是,-Q 是横坐标相同但纵坐标相反的点,也就是,相对 p/2 对称的点。

*零知识证明:椭圆曲线基础

2.5 点加计算

假设三个点在一条线上,零知识证明:椭圆曲线基础零知识证明:椭圆曲线基础零知识证明:椭圆曲线基础。如果 P 和 Q 不是同一个点:

零知识证明:椭圆曲线基础

从而,推导出:

零知识证明:椭圆曲线基础

其他条件下的推导,涉及的公式比较多。有兴趣的小伙伴可以自行推导。

2.6 在有限群上的椭圆曲线有多少点?

椭圆曲线上的点的个数,称为「阶」。如果枚举 0~p-1,查看点的个数,不太现实,因为 p 是一个非常大的质数。Schoof 算法能在多项式时间确定椭圆曲线阶:https://en.wikipedia.org/wiki/Schoof%27 s_algorithm。

2.7 标量乘法

和实数域上一样,可以使用 double 后相加的方法计算。在有限域上,有额外的特性,举个例子:

零知识证明:椭圆曲线基础

已知零知识证明:椭圆曲线基础以及点零知识证明:椭圆曲线基础。点 P 的标量乘法的结果是循环的,只有五个点。

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础

很容易看出,在有限域上的椭圆曲线中一个点标量乘法的结果,组成一个在加法操作下的循环子群。在子群中的点,所有的加法的结果都还在子群中。而且,存在一个点,幂次(加法操作)能生成子群中的所有点。这样的点,称为「生成元」。

绕了一大圈,在有限域上的椭圆曲线上,存在很多个循环子群。子群是基于加法操作。

2.8 循环子群的阶

Schoof 算法能确定整个基于有限域上的椭圆曲线上的点的个数,但是不能确定循环子群的个数。

拉格朗日定理指出,对于任何有限群 G,G 的每个子群 H 的阶次(元素数)都会被 G 的阶次整除。

https://en.wikipedia.org/wiki/Lagrange%27 s_theorem_(group_theory)

该定理给寻找循环子群的阶 n,提供了一个思路:

1/ 利用 Schoof 算法,计算出整个椭圆曲线的阶

2/ 找出其所有的约数

3/ 找出最小的约数 n,满足零知识证明:椭圆曲线基础

2.9 寻找生成元

通常使用椭圆曲线算法,先选择曲线,计算椭圆曲线的阶,然后在这条曲线上找到最大的子群。找子群,就是寻找子群对应的生成元。

假设椭圆曲线的阶为 N,子群的阶为 n,由拉格朗日定理,零知识证明:椭圆曲线基础

又因为椭圆曲线的阶为 N,P 为椭圆曲线上的随机的点,存在零知识证明:椭圆曲线基础。也就是说零知识证明:椭圆曲线基础

零知识证明:椭圆曲线基础为子群的生成元。

2.10 离散对数问题

已知两个在子群上的点 P 和 Q,求解零知识证明:椭圆曲线基础是非常难的问题。目前该问题没有多项式时间求解算法。

2.11 同态

如果子群的阶为 r,则零知识证明:椭圆曲线基础

*同态加法 :零知识证明:椭圆曲线基础

总结:

有限域上的椭圆曲线是零知识证明的基础。零知识的实现是基于离散对数问题。从计算的角度来看,F_p 是个有限域,在之基础上建立的椭圆曲线点的运算都是在这个域范围内。有限域上的椭圆曲线上有很多循环子群 F_r,具有加法同态的特性。离散对数问题指的是,在循环子群上已知两点,却很难知道两点的标量。

来源链接:weixin.qq.com

区块律动 BlockBeats 提醒,根据银保监会等五部门于 2018 年 8 月发布《关于防范以「虚拟货币」「区块链」名义进行非法集资的风险提示》的文件,请广大公众理性看待区块链,不要盲目相信天花乱坠的承诺,树立正确的货币观念和投资理念,切实提高风险意识;对发现的违法犯罪线索,可积极向有关部门举报反映。    

声明:链世界登载此文仅出于分享区块链知识,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。此文如侵犯到您的合法权益,请联系我们kefu@lianshijie.com

    参与讨论 (0 人参与讨论)

    相关推荐

    中信银行打造“区块链”信用证结算!

    中信银行打造“区块链”信用证结算!

    科技不会改变金融的实质,但却能让金融服务更高效,能让资金供、需方信息不对称的问题更好地解决。近期,中信银行首个区块链项目——基于区块链的国内信用证信息传输系统(简称BCLC)(一期)成功上线,这是国内银行业第一次将区块链技术应用于信用证结算领域。 据中信银行国际业务部总经理助理张栩青介绍,将现在流行的区块链技术应用在国内信用证中,改变了银行传统信用证业务模式,信用证的开立、通知、交单、承兑报文

    中国信息技术部门成立区块链研究实验室

    中国信息技术部门成立区块链研究实验室

    暴走时评:本月初,中国政府对国内的ICO和数字货币交易所的打击在世界范围内引起了强大反响,但政府已经多次声明不会将区块链与数字货币划等号,依然非常重视区块链技术在中国的发展。鉴于中国工业和信息化部成立了一个专门研究区块链的实验室,这一论调也得到了进一步的证实。 虽然中国政府最近在大力打击比特币交易所和ICO,但仍然致力于开发区块链在其他领域的潜力。 据财新网报道,中国工业和信息化部已经成立了一

     分布式账本中的生命科学

    分布式账本中的生命科学

    生物科学是医学领域涉及遗传研究,疾病预防和生活方式治疗(lifestyle treatments)的学科。它已经存在了很长时间,但区块链技术的基础设施应用给该学科提供了重大进步的可能性。 根据Pistoia Alliance进行的2016年6月份高级制药和生命科学领袖调查,83%的受访者表示,他们预计在五年内将全面采用区块链技术。 Pistoia Alliance是一个全球性的非营利组织,致

    区块链vs.核能:日本最大电力公司东京电力(TEPCO)寻求使用区块链减轻对核电的依赖

    区块链vs.核能:日本最大电力公司东京电力(TEPCO)寻求使用区块链减轻对核电的依赖

    东京电力公司 (TEPCO) 对于能源过度中心化的风险可以说绝不陌生。 也许最著名的就是2011年发生的福岛核电站事故,这个日本最大的能源公司如今正在寻求区块链技术来防止这种灾难再次发生。 然而,从使用微型风车的分布式风力发电到用于存储在电力成本低时购买的电力的智能电池,可替代能源项目一直以来都属于个人慈善事业。 然而,TEPCO风险投资部门主管Jeffrey Char认为区块链能够帮助为这

    继证监会发表代币发行声明之后,香港交易所Gatecoin将下线部分ICO币

    继证监会发表代币发行声明之后,香港交易所Gatecoin将下线部分ICO币

    经过一系列监管以及合规审查后,香港交易所Gatecoin将会下线那些被金融监管部门定性为"证券"的代币。 香港加密货币交易所Gatecoin透露,如果在该平台交易的ICO代币在法律上符合"证券"定义,他们就会下线这些代币。据巴比特上月报道,香港主要的金融监管部门证券及期货事务监察委员会(SFC)表达了对ICO这种日渐普及的募资模式的担忧。 尽管ICO中售卖的数字代币通常都被定义为虚拟商品,但

    IBM与超级账本共同加入去中心化身份基金会(DIF),推动创建区块链ID行业标准

    IBM与超级账本共同加入去中心化身份基金会(DIF),推动创建区块链ID行业标准

    IBM与超级账本已经签署协议加入去中心化身份基金会(DIF),这个于今年初成立的联盟旨在帮助推动基于区块链的ID系统的互操作性和标准。 这两个企业区块链大佬加入了这个有各种企业组成的团体,其中包括像微软和埃森哲这样的大企业,还有像Civic和Gem这样的创业公司,以及像uPort和Sovrin这样的开源项目。 DIF执行主管告诉Coindesk说: "这应该是一个信号,表明在这一领域有广泛的

    为打击人口贩卖,牙买加警方盯上了犯罪分子的比特币钱包

    为打击人口贩卖,牙买加警方盯上了犯罪分子的比特币钱包

    作为打击人口贩卖计划的一部分,牙买加警方已经开始行动,锁定了那些试图用比特币和数字支付来掩人耳目的犯罪分子。 越来越多的人口贩卖者都开始转向数字货币来帮助他们进行地下活动并接收非法活动所得,但牙买加警方已经盯上他们了。 牙买加的'大生意' 不幸的是,人口贩卖以及性奴市场规模十分庞大,预计涉资1500亿美元。在牙买加,大约有7000个妇女、儿童以及成年男性被奴役,他们的操控者出售奴役服务的价格

    深圳市将发布《深圳市扶持金融业发展若干措施》,奖励区块链、数字货币等金融创新

    10月9日,深圳市人民政府向各区人民政府,市政府直属各单位印发《深圳市扶持金融业发展若干措施》(以下简称"《若干措施》")。深圳市政府表示,此举是为进一步完善金融支持政策体系,吸引集聚优质金融资源,推动全市金融业可持续均衡发展,加快建设国际化金融创新中心。 《若干措施》共分五大项,33条。内容包括:坚持服务导向,优化金融政策环境;发展金融总部经济,鼓励金融总部企业做大做强;支持金融企业分支机构

    麦妖榜
    更新日期 2019-09-03
    排名用户贡献值
    1牛市来了30910
    2BitettFan24187
    3等待的宿命23810
    4区块大康20369
    5六叶树20310
    6linjm122719429
    7天下无双16192
    8lizhen00215280
    9让时间淡忘14586
    10yelanyi050511349
    返回顶部 ↑