
零知识证明 – 椭圆曲线基础
对椭圆曲线的学习,个人推荐如下的链接,没有太多的术语,解释的比较清楚。
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=nP的计算比较容易。但是,在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%27s_algorithm。
2.7 标量乘法
和实数域上一样,可以使用double后相加的方法计算。在有限域上,有额外的特性,举个例子:
已知以及点
。点P的标量乘法的结果是循环的,只有五个点。
…
很容易看出,在有限域上的椭圆曲线中一个点标量乘法的结果,组成一个在加法操作下的循环子群。在子群中的点,所有的加法的结果都还在子群中。而且,存在一个点,幂次(加法操作)能生成子群中的所有点。这样的点,称为“生成元”。
绕了一大圈,在有限域上的椭圆曲线上,存在很多个循环子群。子群是基于加法操作。
2.8 循环子群的阶
Schoof算法能确定整个基于有限域上的椭圆曲线上的点的个数,但是不能确定循环子群的个数。
拉格朗日定理指出,对于任何有限群G,G的每个子群H的阶次(元素数)都会被G的阶次整除。
https://en.wikipedia.org/wiki/Lagrange%27s_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,具有加法同态的特性。离散对数问题指的是,在循环子群上已知两点,却很难知道两点的标量。
作者:Star Li
比推快讯
更多 >>- Project Hunt:链上预测市场 The Clearing Company 为过去 7 天新增 Top 人物关注者最多的项目
- RootData:IO、BMT、AGI 将于一周后解锁代币
- 乌克兰议会一读通过加密货币合法化和税收法案
- 数据:股票代币化平台 xStocks 昨日 DEX 交易额达 286 万美元
- 花旗:预计 2030 年全球 10% 市场交易额将通过数字资产和代币化证券进行
- 三个新创建钱包从 FalconX 接收 6.56 万枚 ETH,价值 2.93 亿美元
- 某地址再次加仓 MKR,当前持仓价值超 1034 万美元,浮亏 142.1 万美元
- 某鲸鱼地址正卖出 PEPE 和 PENDLE 头寸以换仓 AAVE 和 ENA
- NEIRO 第一大持仓实体 Trend Research 将 7790 万枚 NEIRO 转入 Bybit
- 分析师:SOL 表现优异,预计未来将有大量国库资金流入,可能会复制 ETH 的涨势
- PUMP 上涨触及 0.004 USDT,24 小时涨幅约 8%
- Bitmine 地址过去 1 小时收到 80,325 枚 ETH,约合 3.58 亿美元
- 某 BTC 地址在沉寂 12.5 年后苏醒转移 0.25 枚 BTC,总计持有 479 枚 BTC
- 数据:某沉睡 12.8 年的比特币钱包激活,持有 479 枚比特币,约合 5,368.36 万美元
- 加密主播 Gainzy 因“意外点击”导致自己的代币市值暴跌 99%
- 比特币金融服务 River:客户平均将 22%利润再投入 BTC
- 巴西上市公司 Méliuz 增持 9.01 枚 BTC,总持仓增至 604.69 枚
- Coinbase CEO:目前平台每天约 40%的代码均由 AI 生成
- TON Strategy Company 批准 2.5 亿美元股票回购计划
- Bitmine 再次从 Galaxy Digital 处收到 14665.5 枚 ETH
- Jupiter 推出空投检查工具,可一键查询 Solana 生态的潜在空投
- 美国企业家 Grant Cardone 以 400 枚比特币挂牌迈阿密豪宅,72 小时内达成交易
- HIFI 回应下架 Binance:无法提供任何建设性意见,将集中资源保障关键基础设施运行
- USD.AI 宣布将新增 5000 万美元的存款额度
- 2249 美元做空 ETH巨浮亏近 1800 万美元,曾 25 倍高杠杆滚仓被套四个月
- WLFI:金库中解锁的 WLFI 代币处置权归属于社区,而非由团队自行决定
- CARDS 24 小时涨超 200%,现报价 0.2068 美元
- Moonshot 新增上线 CARDS
- 中信证券:预测年底金价有望超过 3730 美元
- 比特币单日算力创下 1.279 ZH/s 的历史新高
- Moonshot 上线 xStocks 代币化股票,暂不适用于美国用户
- American Bitcoin 上市首日上涨近 17%,Eric Trump 所持该公司股份价值已超 5 亿美元
- Anchorage 面向机构投资者新增 Starknet 质押服务
- 特朗普:马斯克最终会重新与共和党结盟
- 比特币主导地位下滑至 55 %,山寨币轮动迹象显现
- 美联储 9 月降息概率高达 96.6%,维持利率不变概率仅 3.4%
- 数据:支持美元交易的加密交易所8月交易量升至2790亿美元
- 法国监管机构对谷歌处以创纪录的3.25亿欧元罚款
- 美股收盘三大股指涨跌不一,谷歌大涨 9%
- OpenAI二次股票发售规模增至超百亿,估值达5000亿美元
- 预测市场Polymarket已获CFTC批准重返美国市场
- SUI Group Holdings:持仓SUI代币价值已超3亿美元
- 美联储理事提名人米兰承诺维护央行独立性
- Chainalysis 发布 2025 年全球加密货币采用指数,印度、美国和巴基斯坦位列前三
- 美联储卡什卡利:有充分理由相信经济将出现温和降温,利率还有空间温和下调
- 美联储褐皮书显示消费开支持平或下滑
- 美联储褐皮书:上次报告以来大部分联邦储备地区经济活动几乎没有变化
- 特朗普警告:法院否决关税政策将废除贸易协议并重创美国经济
- 美联储卡什卡利:通胀过高,劳动力市场降温迹象显现
- 美联储卡什卡利称经济放缓,朝软着陆迈进
比推专栏
更多 >>观点
比推热门文章
- 乌克兰议会一读通过加密货币合法化和税收法案
- 数据:股票代币化平台 xStocks 昨日 DEX 交易额达 286 万美元
- 花旗:预计 2030 年全球 10% 市场交易额将通过数字资产和代币化证券进行
- 三个新创建钱包从 FalconX 接收 6.56 万枚 ETH,价值 2.93 亿美元
- 某地址再次加仓 MKR,当前持仓价值超 1034 万美元,浮亏 142.1 万美元
- 某鲸鱼地址正卖出 PEPE 和 PENDLE 头寸以换仓 AAVE 和 ENA
- NEIRO 第一大持仓实体 Trend Research 将 7790 万枚 NEIRO 转入 Bybit
- 分析师:SOL 表现优异,预计未来将有大量国库资金流入,可能会复制 ETH 的涨势
- PUMP 上涨触及 0.004 USDT,24 小时涨幅约 8%
- Bitmine 地址过去 1 小时收到 80,325 枚 ETH,约合 3.58 亿美元