• home > theory > CST > blockchain >

    区块链之非对称加密算法与密码学随机数

    Author:zhoulujun Date:

    非对称加密,在现在网络应用中,有这非常广泛的场景,更是加密货币的基础。本文主要介绍非对称加密、解密的原理和过程,以及在区块链中的使

    非对称加密,在现在网络应用中,有这非常广泛的场景,更是加密货币的基础。本文主要介绍非对称加密、解密的原理和过程,以及在区块链中的使用。

    一、非对称加密解密过程

    1. A要向B发送信息,A和B都要产生一对用于加密、解密的公钥和私钥

    2. A保管自己的私钥,把公钥告诉B;B保管自己的私钥,把公钥告诉A

    3. A要给B发送信息时,A用B的公钥加密信息,因为A知道B的公钥。

    4. A将这个消息发给B(已经用B的公钥加密消息)。

    5. B收到这个消息后,B用自己的私钥解密A的消息。其他所有收到这个报文的人都无法解密,因为只有B才有B的私钥。

    二、如何理解公钥和私钥

      非对称加密算法需要两个密钥:公开密钥(public key)和私有密钥(private key)。公开密钥与私有密钥是一对,如果用公开密钥对数据进行加密,只有用对应的私有密钥才能解密;如果用私有密钥对数据进行加密,那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥,所以这种算法叫作非对称加密算法。
      非对称加密算法实现机密信息交换的基本过程是:甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开;得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方;甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。
      非对称密码的特点:算法强度复杂、安全性依赖于算法与密钥,但是由于其算法复杂,而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥,并且是非公开的,如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全,而非对称密钥体制有两种密钥,其中一个是公开的,这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。

    三、非对称加密解密原理

    非对称加密算法中,常用的就是RSA算法了,以下就以RSA算法为例来讲解非对称加密算法的实现原理。

    RSA算法的基于这样的数学事实:两个大质数相乘得到的大数难以被因式分解。

    RSA加密过程

    解释:也就是说RSA加密是对明文的E次方后除以N后求余数的过程。也就是说只要知道E(Encryption)和N(Number),任何人都可以进行RSA加密了。其中E、N是RSA加密的密钥,E和N的组合就是公钥,我们用(E,N)来表示公钥

    不过E和N不并不是随便什么数都可以的,它们都是经过严格的数学计算得出的

    RSA解密过程

    也就是说对密文进行D次方后除以N的余数就是明文,这就是RSA解密过程。知道D和N就能进行解密密文了,所以D和N的组合就是私钥

    从上述可以看出RSA的加密方式和解密方式是相同的,加密是求”E次方的mod N”,解密是求”D次方的mod N”

    知道上述的几个简单公式后,剩下就是计算各个参数对应的值了

    1. 求N。准备两个质数p,q,这两个数不能太小,太小则会容易破解,将p乘以q就是N。

    1. 求L。L为中间数,是 (p-1) 和 (q-1) 的最小公倍数,可用如下表达式表示

    1. 求E。E必须满足两个条件:E是一个比1大比L小的数,E和L的最大公约数为1,用gcd(X,Y)来表示X,Y的最大公约数则E条件如下之所以需要E和L的最大公约数为1是为了保证一定存在解密时需要使用的数D。现在我们已经求出了E和N也就是说我们已经生成了密钥对中的公钥了。

    1. 求D。D是由数E计算出来的。D、E和L之间必须满足以下关系:

    至此,公钥和私钥都都计算出来了,大家可以自己试着计算下

    四、为何非对称加密难以破解

      破解RSA算法的关键就是计算N、p、q的值,给出两个很大的质数p、q,可以计算N,但知道N,去很难算出p、q,只能不停的尝试,这就是为什么当前RSA很难破解。
      RSA算法的破解与密钥的长度有关,如果密钥的长度小于等于256位,一台较快的电脑可以在几个小时内成功分解其因子。位数越高因式分解所需时间也越长。例如破解RSA-2048(2048-bit)的密钥需要耗费传统电脑10亿年的时间,而量子计算机只需要100秒就可以完成。所以随着科技的发展,算法也会更新换代。

    区块链之随机数

    一、随机数分类

    1. 真随机数
      其定义为随机样本不可重现。实际上只要给定边界条件,真随机数实际上并不存在,可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉,可以认为用这个方法演算出来了真随机数。例如骰子、转轮、噪音等。

    2. 伪随机数,通过一定算法和种子得出,例如计算机软件中实现的就是伪随机数。

      • 强伪随机数:难以预测的随机数,常用于密码学

      • 弱伪随机数:易于预测的随机数

    二、随机数特性

    随机数有3个特性,具体如下:

    1. 随机性:不存在统计学偏差,是完全杂乱的数列,即分布均匀性和独立性

    2. 不可预测性:不能从过去的数列推测出下一个出现的数

    3. 不可重现性:除非将数列本身保存下来,否则不能重现相同的数列

    随机数的特性和随机数的分类有一定的关系,比如,弱伪随机数只需要满足随机性即可,而强位随机数需要满足随机性和不可预测性,真随机数则需要同时满足3个特性。

    三、随机数生成器

    由于真随机数是不存在的,在程序中使用的都是伪随机数。那么生成伪随机数的生成器又称为密码学伪随机数生成器(英文:Cryptographically secure pseudorandom number generator,通称CSPRNG),是一种能够通过运算得出密码学安全伪随机数的伪随机数生成器。相较于统计学伪随机数生成器和更弱的伪随机数生成器,CSPRNG所生成的密码学安全伪随机数具有额外的伪随机属性。

    介绍两种不同场景下常用的伪随机数生成器:

    1.线性同余法

    因为通过线性同余方法构建的伪随机数生成器的内部状态可以轻易地由其输出演算得知,所以此种伪随机数生成器属于统计学伪随机数生成器。设计密码学的应用必须至少使用密码学安全伪随机数生成器,故需要避免由线性同余方法获得的随机数在密码学中的应用。

    线性同余算法

    参数取值需要满足三个标准:函数在重复前应该产生0-M之间的所有数;产生的序列应该显得随机;生成函数可以用计算机方便地实现,满足条件的参数选择如下:

    1. M一般取素数,且要求很大,对于32位机一般取值为       

    2. A的可取值不多,当        时满足以上标准。

    这个算法的缺点是,在参数确定后,伪随机序列只与N0相关,容易被破解。有一种改进的办法就是每隔n个数就以时钟值对M取模作为新的种子来产生新的序列。还有一种方法是直接将随机数加上时钟值再对M取模。
    比较常用的一般是线性同余法,比如我们熟知的C语言的rand库和Java的java.util.Random类,都采用了线性同余法生成随机数。
    一般来说,各大编程语言提供的伪随机数通用实现出于效率方面的考量,都达不到密码学强度的要求。
    请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现。

    2. ANSI X9.17

    该伪随机数发生器是密码学意义上最强的伪随机数发生器之一,应用在金融安全和PGP上。它使用了3DES来加密,算法流程如下图

    dd6d786b4e66ea6c33addee0a61890c9.jpg

    DTi:算法第i轮开始时的日期/时间值,64位,每一轮都被更新。
    Vi:算法第i轮开始时的种子值,64位,每一轮都被更新。
    Ri: 算法第i轮所产生的伪随机数。
    K1,K2:各阶段算法所用的DES密钥,各56位。
    可用以下表达式描述该算法:
      Ri = EDE([K1,K2],[Vi⊕EDE([K1,K2],DTi)])
      Vi+1 = EDE([K1,K2],[Ri⊕EDE([K1,K2],DTi)])
    该方法的密码强度来自几个方面,包括112位密钥和3个EDE共计9次DES加密。

    三、随机数在区块链中的使用

      随机数有很多的应用场景,例如抽奖活动、验证码、Token、密码应用场景(生成秘钥、生成盐)等。
      而随机数的生成是一个由来已久的问题。一个广泛的原则是:随机性的生成最好不被任何个体所控制。因此譬如从比特币的未来某区块的数据来获取随机性的方式是不能使人信服的,因为这些随机性最终实际上是由某个个体决定的,无法证明这个相关人没有作恶。
      区块链中常用的是一种分布式的随机数生成算法,使用了DPOS结构中的受托人来提供随机性。受托人事先成私密的种子数据,然后生成区块时公布该种子数据的哈希值,在下一次生成区块时再公布该种子数据 。最终外部过程所使用的随机数由连续的多个(至少应大于等于 101)种子数据来确定。这样只要有一位受托人是诚实的并将他们的信息保密,那么其他人就无法预测结果。那么我们可以很放心地假设受托人中至少其中有一个是诚实的。这样产生的随机数可信程度是非常高的。

    转载内容源文链接:

    区块链之非对称加密算法 http://www.jouypub.com/2018/b6b465541400d28455747730ce19e42f/

    区块链之密码学随机数 www.jouypub.com/2018/7665609b0126606e2ae90ad7cfcdce8b/


    转载本站文章《区块链之非对称加密算法与密码学随机数》,
    请注明出处:https://www.zhoulujun.cn/html/theory/ComputerScienceTechnology/blockchain/8258.html