下载掌阅APP，畅读海量书库
立即打开
非对称加密与公钥密码体制在区块链的交易构建和签发数字证书等场景中发挥着重要作用。以RSA公钥密码算法、ECC椭圆曲线加密为代表的非对称加密算法是区块链技术的核心之一。
（1）非对称加密的提出背景：非对称加密算法的提出是为了解决当时传统的对称加密算法中密钥分发和管理的问题。传统的对称加密算法可以保证消息在双方通信信道中的保密性，但是在加密通信之前，通信双方如何在不安全的通信信道中商量出一个加密密钥，是一个非常严峻的问题。
（2）非对称加密的特点：与传统的密码学方案不同，非对称加密算法并不依靠同一个密钥，通过替换或置换等方式进行加解密，而是通过构造一些难解的数学问题来实现，如大整数因数分解、离散对数问题等。非对称加密拥有两个密钥——公钥和私钥，公钥可以公开，而私钥必须妥善保管。两个密钥中的任何一个都可用来加密，另一个用来解密。知道公钥并不能推导出私钥，因此公钥是可以公开的。由于加解密采用不同的密钥，这种密码算法也被称为非对称加密算法。非对称加密是密码学发展史上的重大里程碑。
基于非对称加密算法的思想建立的密码体制，被称为公钥密码体制，如表4-2所示。
表4-2 公钥密码体制
一个典型的利用公钥密码体制进行加解密的过程如图4-3所示。
图4-3 公钥加密
（1）Alice产生一对公私钥，Alice将公钥公开，而对私钥进行妥善保管。
（2）Bob想要给Alice发送一段加密的消息，那么Bob需要用Alice的公钥对消息进行加密，并将加密后的密文信息发送给Alice。
（3）Alice收到密文消息后，使用自己的私钥对密文进行解密，得出明文信息。
Alice的私钥是未公开的，因此只有Alice可以将密文消息还原成明文，保证了通信的保密性。
可见，公钥密码算法很好地解决了密钥分发和管理的问题，只要用户保证本地存储的私钥是安全且未泄露的，那么通信的过程就是保密的。
前面说到，构造非对称加密算法的实现方式是基于一些数学问题的难解性，下面我们以RSA公钥密码算法为例，介绍大整数因数分解的难解性是如何被应用到非对称加密算法中的。
RSA算法是由麻省理工学院的罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼于1978年发表的公钥密码算法，如今已被业界普遍接受并得到了广泛的应用。RSA算法是一种分组的加解密算法，它的明文和密文均为0至n-1的整数，一般来说，n小于2 1024 。
RSA算法的明文通过n来进行分组，假设每个分组的二进制位数是i，那么有，2 i ＜n≤2 i+ 1
RSA算法的数学原理在于构造了在模运算的整数域下的等式：
在模运算的整数域下，若e和d互为模ϕ(n)的乘法逆元，上述等式成立，其中ϕ(n)是欧拉函数。同时，对于上述等式来说，基于大数分解的计算困难性，由n、e来推算d是不可行的。因此RSA算法的构造者找到合适的e、d两个参数后，即可构造一个可以用于加解密的变换。
RSA算法的加解密变换如下：
设明文分组为M，密文分组为C，e为公钥，d为私钥，则加密过程为
相应地，解密过程：
接下来，我们来介绍RSA算法中如何生成e、d公私密钥对，以及n是如何选取的。
首先，选择两个互不相等的素数p、q，相乘计算得到
计算欧拉函数
然后选择一个整数e，使
然后相应地计算出d，
其中，p、q、d是保密的，n、e是公开的，而且由n和公钥e推算不出来私钥d，所以保证了RSA算法的安全性。
随着计算机算力的不断增强，为了保证RSA算法的安全性，只能不断地增加其密钥的长度。过长的密钥、繁重的存储成本和处理负荷，也影响了RSA加密标准的应用性。密码学家希望找到一种效率上优于质因子分解而密钥长度可以更短的算法。近年来，出现了一种新的密码学算法，名为椭圆曲线密码学算法。椭圆曲线密码学算法凭借它更短的密钥长度，赢得了很多学术界和工业界人士的青睐。
在研究探讨椭圆曲线密码学算法时，首先将会介绍Abel群，随后会介绍实数域和有限域上的椭圆曲线，在了解数学原理之后将介绍椭圆曲线的加解密算法过程。
在大部分公钥密码学算法中，Abel群的概念十分重要。
Abel群G由元素集合及其上的二元运算符“⋅”组成，也可以记为{ }G，⋅，将G中元素的序偶( )a,b 与G中元素( )a ， b 对应，同时满足封闭性、结合性、单位元、逆元、交换性等公理。
椭圆曲线密码学中定义了两种运算规则：点加法与点乘法，乘法是重复的点进行加法运算，例如
其中右式为k个a进行椭圆曲线上的加法运算，密码攻击者要从给出的a和a× k的结果来确定k是困难的。
椭圆曲线密码学的方程形式与计算椭圆周长的方程十分类似，因此取名为椭圆曲线，其三次方程为
其中a、b、c、d和e为实数，x和y也在实数集上取值。进一步的，我们将方程限制为以下形式：
值得注意的是，椭圆曲线的定义中还包含着一个无穷远点或称为零点的元素，我们将这个点记作O。
其中的参数a，b，如果满足条件
那么就能够根据给定的a 、b ，在集合E ( a,b )（包含整个椭圆曲线上的点和一个无穷远点O ）上定义一个群。
为了在E (a,b )上定义一个群，首先要定义一个加法运算，用“+”表示。在几何意义上对加法的运算规则进行定义：如果椭圆曲线上有3个点在同一条直线上，那么它们的和为O。
由该定义延伸出去，我们可以继续定义椭圆曲线中加法的运算规则。
（1）O是加法的单位元。这样有O=-O；对椭圆曲线上的任何一点P，有P+O=P。
（2）点P负元的x坐标是相同的，y坐标是相反的，即若P=（x，y），则-P=（x,-y），此时易知这两个点可用一条垂直于x轴的直线进行连接，并且P+(-(-P))=P+P=O。
（3）要计算x坐标不相同的两点P、Q之和，需要在P和Q之间作一条直线，并且可以找出第三个交点R，存在有唯一一个交点R（如果这条直线在P或Q处与该椭圆曲线相切，此时分别取R=P或R=Q），如果要形成一个群，则需要定义如下3个点上的加法：P+Q=-R。
（4）要计算Q的两倍时，则在Q处作一条切线，找出与椭圆曲线的另一个交点S，有Q+Q=2Q=-S。
利用以上所述的运算规则，易证明集合E ( a,b )是一个Abel群。
在椭圆曲线密码体制上，采用的是变元和系数均为有限域中元素的椭圆曲线。进一步来说，椭圆曲线密码体制应用的椭圆曲线是定义在Z p 上的素曲线和在GF ( 2 m )上构造的二元椭圆曲线。
关于Z p 上的素曲线问题，其涉及的变元和系数均从集合{0,1,⋯， p- 1}中取值，涉及的运算全部为模p运算。关于GF(2 m )上的二元曲线问题，其中涉及的变量和系数在GF(2 m )中取值，并且涉及的运算全部为GF ( 2 m )中的运算。下面简单介绍Z p 上的椭圆曲线问题。
对于Z p 上的椭圆曲线，类似实数域上的椭圆曲线一样，方程如下：
可以证得，如果( x 3 + ax+ b ) modp无重复因子，则基于集合E p ( a,b )可定义一个有限的Abel群。这也等价于
这种形式类似于上文中定义在实数域中的椭圆曲线上关于a和b的限制条件，且对任何点P, Q∈E p ( a,b )，有
（1）P+O=P。
（2）若P =( x p ,y p ) ，则点 ( x p ，- y p )是P的负元，记为-P，例如，对E 23 (1,1)上的点P=（13,7），有-P=（13,-7），而-7 mod 23=16。因此，-P=（13,16），该点也在E 23 (1,1)上。
（3）若P =( x p ， y p ) ，Q=( x Q ， y Q ) ，且P≠-Q则R= P + Q=( x R ， y R )由下列规则确定：
其中
（4）乘法定义为重复相加，如4P=P+P+P+P。
考虑方程Q=kP，其中Q，P∈E p ( a, b )，对给定的k和P计算Q比较容易，而对给定的Q和P要计算k则十分困难，这就是椭圆曲线上的离散对数问题。
下面介绍利用椭圆曲线实现的加解密方法。
首先，我们必须将要发送的消息明文m编码为形如（x,y）的点P m 对点P m 行加密和解密。注意，不能简单地将消息m编码为点的x坐标或y坐标，因为并不是所有的坐标都在E p ( a,b )。将消息m编码为点P m 的方法有很多种，这里不做详细介绍。
椭圆曲线的加解密算法需要一个点G和椭圆群E p (a,b)的参数。点G是在椭圆群E p (a,b)上自行挑选的一个基点G =（x 1 ,y 1 ）。
每个用户选择一个私钥n ，并产生公钥P=nG ，例如，对于通信双方A 、B来说，B的私钥就是n B ，公钥就是P B = n B G。
若A要将消息P m 加密后发送给B，则A随机选择一个正整数k，并使用B的公钥产生密文C m ，该密文是一个点对：
B要对密文解密，只需用第二个点减去第一个点与自身的私钥之积，即可恢复消息P m ，过程如下：
数字签名是密码学的重要应用。签名意味着授权，具有法律效力。在数字时代，数字签名就是电子数据形式的“签字画押”。数字签名基于之前提到的“公钥密码体制”，恰好是之前的Alice&Bob例子的逆过程，用私钥生成数据而用公钥进行验证，用以确保数据真实性、完整性与抗抵赖性。
除保密性外，数据传输的真实、完整与抗抵赖性也是密码学关心的重点。数字签名是一种用于保证数据或消息的真实性和完整性的加密机制，同时数字签名与传统的手写签名方式一样，具有高度的抗抵赖性。在形式上，数字签名是附加到消息中，作为证明消息在传输过程中没有被篡改的凭证，数字签名通常使用基于非对称加密的数字签名算法。
数字签名为何重要呢？举个例子，Bob向Alice发送“520”的消息，附带了Bob的数字签名，Alice在验证签名后就可以知道消息是Bob发送的且没有被修改过，Bob也无法抵赖是自己发送了这条消息。如果没有数字签名，“520”在传输过程中可能被篡改成了“250”，Alice又无法验证，表白就变成了悲剧了。如图4-4所示，数字签名一般包括3个基本流程：散列、签名和验证。
图4-4 数字签名流程
ECDSA算法又称椭圆曲线数字签名算法，它采用的是Z p 上的素数域椭圆曲线。其算法流程与其他签名算法类似，首先数字签名所有参与方需要使用共同的全局域参数，用于选定椭圆曲线上的基点。签名者产生一个随机数作为私钥，然后利用随机数和基点，计算出椭圆曲线上的另一解点，作为公钥。
ECDSA算法中涉及的全局域参数如下所示：
q为素数；
a,b为Z q 上的整数，通过二元方程y 2 = x 3 + ax+ b来定义一个椭圆曲线；
G为椭圆曲线上选取的基点；
n为点G的阶。
数字签名生成的具体过程如下。
（1）选择一个随机数k，k∈[ 1,n- 1 ]。
（2）根据k和G ，计算椭圆曲线上的解点，P =( x,y )= kG ，以及r = x mod n ，若r=0，则回到第一个步骤。
（3）计算t= k -1 modn。
（4）计算e= H (m )，这里使用SHA-1哈希函数，可以生成160位的哈希结果。
（5）计算s= k -1 ( e+ dr ) modn，如果s=0，则回到第一个步骤。
（6）消息m的签名是（r,s）对。
消息的接收者和发送者共享全局域参数信息及签名者的公钥信息，因此消息的接收方对于消息和签名的验证过程如下。
（1）检验r和s是否为1到n-1的整数。
（2）计算消息的哈希值，e=H（m）。
（3）计算w= s -1 modn。
（4）计算u 1 = ew和u 2 = rw 。
（5）计算解点X =( x 1 ,y 1 )= u 1 G + u 2 Q。
（6）若X=0，拒绝该签名，否则计算v= x 1 modn。
（7）当且仅当v=r时，接收该签名。
以上是签名和认证的整个过程。下面我们针对该过程，给出相应的证明和解释。
如果签名是有效的，则有以下变换：
s=k -1 (e+dr)modn
k=s-1(e+dr)modn
k=(s-1e+s-1dr)modn
k=(we+wdr)modn
k=(u1+u2d)modn
注意到解点X有
x 1 是解点X的x坐标，P =( x ,y )= kG中，x是kG的x坐标，因为r=xmod n及v=x 1 mod n，所以当v=r时，即证明该签名有效。