区块链中的数学 – 离散域模素数上的加法&椭圆曲线中离散对数问题

本节介绍如何让椭圆曲线点的坐标离散化。

## 写在前面 上一节我们介绍了[群论的概念和椭圆曲线在实数域上点坐标满足Abel群的加法运算](https://learnblockchain.cn/article/1530)，但是实数域上加法运算不能满足实际安全需要，因为实数是连续的，知道结果就可以使用逆运算求解。 我们或许已经知道椭圆曲线的安全是基于离散对数求解的困难性。本节要介绍的就是如何让椭圆曲线点的坐标离散化。 ## 模素数P运算 模运算 a mod p:表示a除以p的余数。 密码学采用有限域上的椭圆曲线，即椭圆方程系数和变量取值均在一个有限的范围内，使用模素数?的有限域?p，将模运算引入到椭圆曲线算术中，变量和系数从集合[0,?−1]中取值而非是在实数上取值。这个域上的方程得到如下改造： $y^2\ mod\ p =(x^3+ax+b)\ mod\ p$ 判别式$(4a^3+ 27b^2)\ mpd\ p\ !=0$ 满足上式所有正整数解和无穷远点O，数学符号记为$E_p(a,b)$, 这是一个有限的离散（非连续）的点集。由此可知集合中的点分布在(0,0)到(?−1,?−1)的象限中。实际上，集合??(?,?)与模?的加法运算构成循环阿贝尔群。 如果素数p选择的比较小，可以通过暴力求解方法，求出中所有的点。 举例说明，对于p=23, a=1,b=3, 共有27个点如下： `(0,7) (6,15) (15,9) (0,16) (7,10) (15,14) (2,6) (7,13) (19,2) (2,17) (10,1) (19,21) (4,5) (10,22) (21,4) (4,18) (12,8) (21,19) (5,8) (12,15) (22,1) (5,15) (14,1) (22,22) (6,8) (14,22) O ` 最后一个是O点。这些点在坐标系中就是离散的一组点，大家可以自行画一下，增加感官认识。可以验证满足方程: $y^2\ mod\ 23 =(x^3+x+3)\ mod\ 23$ ## 离散域模素数上的加法 ??(?,?)上的加法规则和实数域上的加法基本一致，但是多加了模运算。模?的加法没有直观上的几何解释，只有代数描述。 求解$(x_r,y_r)$的代数表达式为： $x_r=(k^2−x_p−x_q)\ mod\ p$ $y_r=(−y_p+?(x_p−x_r))\ mod\ p$ 可以看出求解过程沿用[上一节](https://learnblockchain.cn/article/1530)说的实数域上的求解方法，只是最后都mod p. 上式中: $k=(y_q-y_p/x_q-x_p)\ mod\ p$ (当p!=q) $k=((3x_p^2+a)/2y_p)\ mod\ p $(当p==q) 例如?=1,?=1,?=23,?(3,10),?(13,16)，求?=?+?. 此时?≠?，计算: $k=(y_q-y_p/x_q-x_p)\ mod\ p=(16−10/13−3)\ mod\ 23=6×10^{-1}\ mod\ 23$. 要计算上式首先要计算$10^{-1}\ mod\ 23$. 令$?\equiv 10^{-1}(mod23)$ [注：≡ 符号表示模等于，等价于? mod 23=(mod23),下同]，由于10≡10(mod23)，所以10?≡1(mod23)， 利用扩展[欧几里德算法](https://learnblockchain.cn/article/1528)（参考历史文章）求得?=7. k=6×7mod23=19 所以$x_r=(k^2−x_p−x_q)\ mod\ p = (19^2 - 3−13) mod23 = 345\ mod\ 23=0$ $y_r=(−y_p+?(x_p−x_r))\ mod\ p = (19×(3−0)−10)\ mod\ 23=47\ mod\ 23 = 1$ 所以?=(0,1). 还可以按照以上规则计算2?,3?等等倍乘点。 ## 椭圆曲线中的离散对数问题 有了以上知识点，现在可以引出椭圆曲线中的离散对数问题了。 构造一个数学难题来保证加密的安全性是密码学中加密算法的主要思想。类似RSA算法（后续会有文章专门描述）中大数的质因子分解难题一样，椭圆曲线也提供了类似的数学难题。 考虑?=??，其中?,?∈??(?,?),?<?。 对于给定的?,?计算?是很容易的；反过来给定?,?，计算?是相当困难的，这就是椭圆曲线的离散对数问题（这里之所以称之为离散对数问题大概是为了与其他加密算法的说法保持一致，便于理解）。 因此，可以将?作为公钥，公开出去；?作为私钥，秘密保管，通过公钥来破解私钥十分困难。 目前由椭圆曲线公钥求解私钥的最有效算法复杂度为?()，其中?是阶数?(群论中的阶数指群中元素的个数)的最大素因子。 本文例子中，选取的p比较小，实际用的p是个非常大的整数，比如256位或者更大，这样大的数靠暴力运算不可行的。好了，到这里，椭圆曲线加密算法为什么采用离散域，为什么引入模运算以及安全性原理都清楚了。[下一节将介绍具体的加密过程](https://learnblockchain.cn/article/1550)。 欢迎关注公众号：blocksight

写在前面

上一节我们介绍了群论的概念和椭圆曲线在实数域上点坐标满足Abel群的加法运算，但是实数域上加法运算不能满足实际安全需要，因为实数是连续的，知道结果就可以使用逆运算求解。

我们或许已经知道椭圆曲线的安全是基于离散对数求解的困难性。本节要介绍的就是如何让椭圆曲线点的坐标离散化。

模素数P运算

模运算 a mod p:表示a除以p的余数。

密码学采用有限域上的椭圆曲线，即椭圆方程系数和变量取值均在一个有限的范围内，使用模素数?的有限域?p，将模运算引入到椭圆曲线算术中，变量和系数从集合[0,?−1]中取值而非是在实数上取值。这个域上的方程得到如下改造：

$y^2\ mod\ p =(x^3+ax+b)\ mod\ p$

判别式$(4a^3+ 27b^2)\ mpd\ p\ !=0$

满足上式所有正整数解和无穷远点O，数学符号记为$E_p(a,b)$, 这是一个有限的离散（非连续）的点集。由此可知集合中的点分布在(0,0)到(?−1,?−1)的象限中。实际上，集合??(?,?)与模?的加法运算构成循环阿贝尔群。

如果素数p选择的比较小，可以通过暴力求解方法，求出中所有的点。

举例说明，对于p=23, a=1,b=3, 共有27个点如下： (0,7) (6,15) (15,9) (0,16) (7,10) (15,14) (2,6) (7,13) (19,2) (2,17) (10,1) (19,21) (4,5) (10,22) (21,4) (4,18) (12,8) (21,19) (5,8) (12,15) (22,1) (5,15) (14,1) (22,22) (6,8) (14,22) O

最后一个是O点。这些点在坐标系中就是离散的一组点，大家可以自行画一下，增加感官认识。可以验证满足方程:

$y^2\ mod\ 23 =(x^3+x+3)\ mod\ 23$

离散域模素数上的加法

??(?,?)上的加法规则和实数域上的加法基本一致，但是多加了模运算。模?的加法没有直观上的几何解释，只有代数描述。 求解$(x_r,y_r)$的代数表达式为：

$x_r=(k^2−x_p−x_q)\ mod\ p$

$y_r=(−y_p+?(x_p−x_r))\ mod\ p$ 可以看出求解过程沿用上一节说的实数域上的求解方法，只是最后都mod p. 上式中:

$k=(y_q-y_p/x_q-x_p)\ mod\ p$ (当p!=q)

$k=((3x_p^2+a)/2y_p)\ mod\ p $(当p==q)

例如?=1,?=1,?=23,?(3,10),?(13,16)，求?=?+?.

此时?≠?，计算:

$k=(y_q-y_p/x_q-x_p)\ mod\ p=(16−10/13−3)\ mod\ 23=6×10^{-1}\ mod\ 23$.

要计算上式首先要计算$10^{-1}\ mod\ 23$.

令$?\equiv 10^{-1}(mod23)$ [注：≡ 符号表示模等于，等价于? mod 23=(mod23),下同]，由于10≡10(mod23)，所以10?≡1(mod23)， 利用扩展欧几里德算法（参考历史文章）求得?=7.

k=6×7mod23=19

所以$x_r=(k^2−x_p−x_q)\ mod\ p = (19^2 - 3−13) mod23 = 345\ mod\ 23=0$ $y_r=(−y_p+?(x_p−x_r))\ mod\ p = (19×(3−0)−10)\ mod\ 23=47\ mod\ 23 = 1$

所以?=(0,1).

还可以按照以上规则计算2?,3?等等倍乘点。

椭圆曲线中的离散对数问题

有了以上知识点，现在可以引出椭圆曲线中的离散对数问题了。 构造一个数学难题来保证加密的安全性是密码学中加密算法的主要思想。类似RSA算法（后续会有文章专门描述）中大数的质因子分解难题一样，椭圆曲线也提供了类似的数学难题。

考虑?=??，其中?,?∈??(?,?),?<?。

对于给定的?,?计算?是很容易的；反过来给定?,?，计算?是相当困难的，这就是椭圆曲线的离散对数问题（这里之所以称之为离散对数问题大概是为了与其他加密算法的说法保持一致，便于理解）。

因此，可以将?作为公钥，公开出去；?作为私钥，秘密保管，通过公钥来破解私钥十分困难。

目前由椭圆曲线公钥求解私钥的最有效算法复杂度为?()，其中?是阶数?(群论中的阶数指群中元素的个数)的最大素因子。

本文例子中，选取的p比较小，实际用的p是个非常大的整数，比如256位或者更大，这样大的数靠暴力运算不可行的。好了，到这里，椭圆曲线加密算法为什么采用离散域，为什么引入模运算以及安全性原理都清楚了。下一节将介绍具体的加密过程。

欢迎关注公众号：blocksight

区块链技术网。

• 发表于 2020-04-23 19:25
• 阅读 ( 1255 )
• 学分 ( 0 )
• 分类：入门/理论