年底了,有点忙。忙着给自己2019年做标记,忙着和小伙伴聚聚餐,谈谈创业,谈谈今年的状态。手头的产品也在打磨。区块链技术是个有趣的行业,爱并痛着。上个星期,自己把零知识...
本文标题零知识证明 - 椭圆曲线基础,作者:知世,本文有1144个文字,大小约为5KB,预计阅读时间3分钟,请您欣赏。知世金融网众多优秀文章,如果想要浏览更多相关文章,请使用网站导航的搜索进行搜索。本站虽然不乏优秀之作,但仅作为投资者学习参考。
年底了,有点忙。忙着给自己2019年做标记,忙着和小伙伴聚聚餐,谈谈创业,谈谈今年的状态。手头的产品也在打磨。区块链技术是个有趣的行业,爱并痛着。上个星期,自己把零知识证明证明的理解梳理了一下,也尝试直播五天分享我的理解。直播非常好玩,Zoom直播性能不错。感受比较深的是,像这样需要比较繁杂的理论基础的知识不太好讲,很多人在听了第一天之后都撤了。也非常感谢和我一起坚持到最后的小伙伴,更要感谢加入零知识证明技术星球的小伙伴,你们的陪同给我很大的动力。
做技术的小伙伴,一定要注意底层理论的积累,虽然底层理论学习貌似枯燥无味,却能让你能进行更高效率的证明或者推演。
对椭圆曲线的学习,个人推荐如下的链接,没有太多的术语,解释的比较清楚。
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。不是密码学或者数学专业的小伙伴,看的是一头雾水。便于工程理解,椭圆曲线是一系列满足如下方程的点:
从方程可以看出,椭圆曲线是关于x坐标对称的曲线。除了坐标系上曲线的点,椭圆曲线额外定义一个点(无穷远处),记为 0。
也就是说,椭圆曲线是由如下的点组成:
1.2 基于椭圆曲线的群定义
在椭圆曲线的基础上,可以定义一个加法群:
· 所有椭圆曲线上的点,就是这个群里的元素
· 单位元就是0
· 点P的逆元是点P相对x坐标的对称点
结合群的定义,可以证明定义的这个加法群,就是阿贝尔群。
1.3 椭圆曲线加法计算
1.4 加法计算推导
当然,如果P/Q是同一个点的话,斜率的计算公式不同。
1.5 标量乘法(Scalar Multiplication)
在加法的基础上,定义了标量乘法,同一个点相加多次:
1.6 对数问题
2. 有限域上的椭圆曲线
上面介绍的是基于实数的椭圆曲线的点,可以构造一个群。考虑特征数为的有限域, 为素数。
2.1 扩展欧几里得定理
给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。gcd(a,b)是最大公约数。
2.2 模p运算下的乘法逆
通过扩展欧几里得定理,可以求得x和y。x就是a的乘法逆。
2.3 在F_p定义椭圆曲线
在模p的情况下,这两个等式相等。
2.4 点加
2.5 点加计算
其他条件下的推导,涉及的公式比较多。有兴趣的小伙伴可以自行推导。
2.6 在有限群上的椭圆曲线有多少点?
椭圆曲线上的点的个数,称为“阶”。如果枚举0~p-1,查看点的个数,不太现实,因为p是一个非常大的质数。Schoof算法能在多项式时间确定椭圆曲线阶:https://en.wikipedia.org/wiki/Schoof%27s_algorithm。
2.7 标量乘法
和实数域上一样,可以使用double后相加的方法计算。在有限域上,有额外的特性,举个例子:
很容易看出,在有限域上的椭圆曲线中一个点标量乘法的结果,组成一个在加法操作下的循环子群。在子群中的点,所有的加法的结果都还在子群中。而且,存在一个点,幂次(加法操作)能生成子群中的所有点。这样的点,称为“生成元”。
绕了一大圈,在有限域上的椭圆曲线上,存在很多个循环子群。子群是基于加法操作。
2.8 循环子群的阶
Schoof算法能确定整个基于有限域上的椭圆曲线上的点的个数,但是不能确定循环子群的个数。
拉格朗日定理指出,对于任何有限群G,G的每个子群H的阶次(元素数)都会被G的阶次整除。
https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)
该定理给寻找循环子群的阶n,提供了一个思路:
1/ 利用Schoof算法,计算出整个椭圆曲线的阶
2/ 找出其所有的约数
2.9 寻找生成元
通常使用椭圆曲线算法,先选择曲线,计算椭圆曲线的阶,然后在这条曲线上找到最大的子群。找子群,就是寻找子群对应的生成元。
2.10 离散对数问题
2.11 同态
总结:
有限域上的椭圆曲线是零知识证明的基础。零知识的实现是基于离散对数问题。从计算的角度来看,F_p是个有限域,在之基础上建立的椭圆曲线点的运算都是在这个域范围内。有限域上的椭圆曲线上有很多循环子群F_r,具有加法同态的特性。离散对数问题指的是,在循环子群上已知两点,却很难知道两点的标量。
本文相关推荐: 关于椭圆曲线密码学的探究
以上便是知世金融网给大家分享的关于零知识证明 - 椭圆曲线基础/qkl/29124.html的相关信息了,希望能帮助到大家,更多金融相关信息,敬请关注知世金融网!
网站内容均来自互联网,如侵害您的利益联系客服进行删除!
上一篇:实锤多次再自证?CSW到底为了什么?BSV狂拉暴割幕后推手?
下一篇:高效市场假设和bitebS2F模型:biteb价值的预测
本文标题:零知识证明 - 椭圆曲线基础
本文地址:/index.php?s=article&c=search&keyword=%E6%A4%AD%E5%9C%86