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

这篇文章主要介绍了区块链中的数学-抽象的椭圆曲线密钥协商 & Miller Rabin素数判定法 ,文中通过代码以及文档配合进行讲解,很详细,它对在座的每个人的研究和工作具有很经典的参考价值。 如果需要,让我们与区块链资料网一起学习。

https://www.interchains.cc/17725.html

区块链中的数学-抽象的椭圆曲线密钥协商 & Miller Rabin素数判定法是很好的区块链资料,他说明了区块链当中的经典原理,可以给我们提供资料,区块链中的数学-抽象的椭圆曲线密钥协商 & Miller Rabin素数判定法学习起来其实是很简单的,

不多的几个较为抽象的概念也很容易理解,之所以很多人感觉区块链中的数学-抽象的椭圆曲线密钥协商 & Miller Rabin素数判定法比较复杂,一方面是因为大多数的文档没有做到由浅入深地讲解,概念上没有注意先后顺序,给读者的理解带来困难

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

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

写在前面

上一节说了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

部分转自网络,侵权联系删除www.interchains.cchttps://www.interchains.cc/17725.html

区块链毕设网(www.interchains.cc)全网最靠谱的原创区块链毕设代做网站 部分资料来自网络,侵权联系删除! 最全最大的区块链源码站 !
区块链知识分享网, 以太坊dapp资源网, 区块链教程, fabric教程下载, 区块链书籍下载, 区块链资料下载, 区块链视频教程下载, 区块链基础教程, 区块链入门教程, 区块链资源 » 区块链中的数学-抽象的椭圆曲线密钥协商 & Miller Rabin素数判定法

提供最优质的资源集合

立即查看 了解详情