区块链中的数学-抽象的椭圆曲线密钥协商 & Miller Rabin素数判定法

本节扩展了一般椭圆曲线上密码协商的原理，原理更简单易于理解，接着讨论了大素数判定的方法，这是在密码学实现中普遍使用的方法，给出了简单的论证，并不详细

## 写在前面 上一节说了[sm2的密钥协商过程](https://learnblockchain.cn/article/1506)，是针对特定的sm2曲线的， 可以抽象地考虑对于一般的椭圆曲线如何做密钥协商？ 从一般意义上讲，反而更加简单，也更能看清本质所在。 ## 一般意义的椭圆曲线密钥协商 用户A的密钥： 私钥$d_{A_`}$, 公钥$P_A=(x_A,y_A)$ 用户B的密钥： 私钥$d_{B_`}$, 公钥$P_B=(x_B,y_B)$ ### 密钥交换过程 用户A和B要通过协商，产生长度为klen比特的共享密钥数据，用户A是首先发通信，用户B是响应方。 A，B用户实现如下运算步骤： **A用户第一回合：** 1. 用随机数发生器产生随机数$r_A \in [1,n-1]$ 2. 计算椭圆曲线点$R_A=r_A G=(x_1,y_1)$ 3. 将$R_A$发送给用户B **B用户第一回合：** 1. 用随机数发生器产生随机数$r_B \in [1,n-1]$ 2. 计算椭圆曲线点$R_B=r_B G=(x_2,y_2)$ 3. 将$R_B$发送给用户A **A用户第二回合：** 1. 计算$K_A=r_A * R_B$ **B用户第二回合:** 1. 计算:$K_B=r_B * R_B$ 于是得到相同的密钥$K_A=K_B$ 二者相同验证很简单： $K_A=r_A * R_B =r_A * r_B G =r_A G * r_B =r_B * R_A =K_B$ 原理很简单，回想sm2协商过程看起来复杂，本质也是双方产生各自随机数，然后根据随机数相关值计算出一个相同的密钥。 接下来，继续说一个密码学中普通需要考虑的问题，目前我们介绍到的密码学算法，都是要求一个模p的域，p是大素数。看起来没什么问题。实际去实践的时候就会发现： 特别大的素数怎么找？给你一个大的数（比如1000比特位以上的），如何快速判断它是否是素数？ 这么大的数，根据素数定义穷举判断是行不通的！下面介绍一种快速的普通使用的大素数判断方法。 ## Miller Rabin素数判定法 Miller Rabin算法与[费马小定理](https://learnblockchain.cn/article/1558)密切相关: $a^{p-1} \equiv 1 (mod \ P)$ 那么是不是当一个数$p$满足任意$a$使得$a^{p-1} \equiv 1 (mod \ P)$成立的时候它就是素数呢？ 在费马小定理被证明后的很长一段时间里，人们都觉得这是很显然的， 但是终于有一天，有人给出了反例 ,推翻了这个结论,这样的反例称为**伪素数**，这里不再展开。 这是否意味着利用费马小定理的思想去判断素数的思想就是错误的呢？ 答案是的。 但是如果可以人为的把出错率降到非常小呢，比如万分之一，百万分之一或者更小？ 比如，给一个数，我们有$99.99999\%$的几率做出正确判断，那这种算法是不是也挺好。 于是Miller Rabin算法诞生了！ 首先介绍一下**二次探测定理**： 若$p$为素数,$a^2 \equiv 1(mod \ P)$，那么$a \equiv \pm 1(mod \ P)$ 有了之前[二次剩余](https://learnblockchain.cn/article/1524)的基础，这个证明过程简单易懂。 证明 $a^2 \equiv 1(mod \ P)$ $a^2 -1 \equiv 0(mod \ P)$ $(a+1) * (a-1) \equiv 0(mod \ P)$ 那么 $(a+1) \equiv 0(mod \ P)$ 或者 $(a-1) \equiv 0(mod \ P)$ 即 $a \equiv \pm 1(mod \ P)$ 这个定理和素数判定有什么关系呢？ 首先，根据Miller Rabin算法的过程 假设需要判断的数是$p$ 我们把$p-1$分解为$2^k * t$的形式，即 $p-1=2^k * t$ 当$p$是素数，有$a^{2^k * t} \equiv 1(mod \ p)$ 然后随机选择一个数$a$，计算出$a^t(mod \ p)$ 让其不断的自乘，同时结合二次探测定理进行判断。 如果我们自乘后的数$(mod \ p)=1$，但是之前的数 $(mod \ p) \neq \pm 1$ 那么这个数一定是合数(违反二次探测定理) 这样乘$k$次，最后得到的数就是$a^{p-1}$ 如果最后的数不为1，这个数也是合数(费马小定理) ### 正确率： 相关定理可以证明，若$p$通过一次测试，则$p$不是素数的概率为25% 那么可以多次选择不同的a进行测试，经过$t$轮测试, $p$不是素数的概率为$\frac{1}{4^t}$， 当t比较大时候，可以让出错率降得非常非常低。 ## 小结 本节扩展了一般椭圆曲线上密码协商的原理，原理更简单易于理解，接着讨论了大素数判定的方法，这是在密码学实现中普遍使用的方法，给出了简单的论证，并不详细，也许[下一篇](https://learnblockchain.cn/article/1499)可以详细说说相关的内容。 欢迎关注公众号：blocksight

写在前面

上一节说了sm2的密钥协商过程，是针对特定的sm2曲线的， 可以抽象地考虑对于一般的椭圆曲线如何做密钥协商？

从一般意义上讲，反而更加简单，也更能看清本质所在。

一般意义的椭圆曲线密钥协商

用户A的密钥： 私钥$d{A`}$, 公钥$P_A=(x_A,y_A)$

用户B的密钥： 私钥$d{B`}$, 公钥$P_B=(x_B,y_B)$

密钥交换过程

用户A和B要通过协商，产生长度为klen比特的共享密钥数据，用户A是首先发通信，用户B是响应方。

A，B用户实现如下运算步骤：

A用户第一回合：

1. 用随机数发生器产生随机数$r_A \in [1,n-1]$
2. 计算椭圆曲线点$R_A=r_A G=(x_1,y_1)$
3. 将$R_A$发送给用户B

B用户第一回合：

1. 用随机数发生器产生随机数$r_B \in [1,n-1]$
2. 计算椭圆曲线点$R_B=r_B G=(x_2,y_2)$
3. 将$R_B$发送给用户A

A用户第二回合：

1. 计算$K_A=r_A * R_B$

B用户第二回合:

1. 计算:$K_B=r_B * R_B$

于是得到相同的密钥$K_A=K_B$

二者相同验证很简单：

$K_A=r_A R_B =r_A r_B G =r_A G r_B =r_B R_A =K_B$

原理很简单，回想sm2协商过程看起来复杂，本质也是双方产生各自随机数，然后根据随机数相关值计算出一个相同的密钥。

接下来，继续说一个密码学中普通需要考虑的问题，目前我们介绍到的密码学算法，都是要求一个模p的域，p是大素数。看起来没什么问题。实际去实践的时候就会发现：

特别大的素数怎么找？给你一个大的数（比如1000比特位以上的），如何快速判断它是否是素数？

这么大的数，根据素数定义穷举判断是行不通的！下面介绍一种快速的普通使用的大素数判断方法。

Miller Rabin素数判定法

Miller Rabin算法与费马小定理密切相关:

$a^{p-1} \equiv 1 (mod \ P)$

那么是不是当一个数$p$满足任意$a$使得$a^{p-1} \equiv 1 (mod \ P)$成立的时候它就是素数呢？

在费马小定理被证明后的很长一段时间里，人们都觉得这是很显然的，

但是终于有一天，有人给出了反例 ,推翻了这个结论,这样的反例称为伪素数，这里不再展开。

这是否意味着利用费马小定理的思想去判断素数的思想就是错误的呢？

答案是的。

但是如果可以人为的把出错率降到非常小呢，比如万分之一，百万分之一或者更小？

比如，给一个数，我们有$99.99999\%$的几率做出正确判断，那这种算法是不是也挺好。

于是Miller Rabin算法诞生了！

首先介绍一下二次探测定理：

若$p$为素数,$a^2 \equiv 1(mod \ P)$，那么$a \equiv \pm 1(mod \ P)$ 有了之前二次剩余的基础，这个证明过程简单易懂。

证明

$a^2 \equiv 1(mod \ P)$ $a^2 -1 \equiv 0(mod \ P)$ $(a+1) * (a-1) \equiv 0(mod \ P)$

那么

$(a+1) \equiv 0(mod \ P)$

或者

$(a-1) \equiv 0(mod \ P)$

即

$a \equiv \pm 1(mod \ P)$

这个定理和素数判定有什么关系呢？

首先，根据Miller Rabin算法的过程

假设需要判断的数是$p$

我们把$p-1$分解为$2^k t$的形式，即 $p-1=2^k t$

当$p$是素数，有$a^{2^k * t} \equiv 1(mod \ p)$

然后随机选择一个数$a$，计算出$a^t(mod \ p)$

让其不断的自乘，同时结合二次探测定理进行判断。

如果我们自乘后的数$(mod \ p)=1$，但是之前的数

$(mod \ p) \neq \pm 1$

那么这个数一定是合数(违反二次探测定理)

这样乘$k$次，最后得到的数就是$a^{p-1}$

如果最后的数不为1，这个数也是合数(费马小定理)

正确率：

相关定理可以证明，若$p$通过一次测试，则$p$不是素数的概率为25%

那么可以多次选择不同的a进行测试，经过$t$轮测试, $p$不是素数的概率为$\frac{1}{4^t}$， 当t比较大时候，可以让出错率降得非常非常低。

小结

本节扩展了一般椭圆曲线上密码协商的原理，原理更简单易于理解，接着讨论了大素数判定的方法，这是在密码学实现中普遍使用的方法，给出了简单的论证，并不详细，也许下一篇可以详细说说相关的内容。

欢迎关注公众号：blocksight

区块链技术网。

• 发表于 2020-09-01 23:37
• 阅读 ( 913 )
• 学分 ( 4 )
• 分类：入门/理论