第1章密码学基础
本章主要介绍密码学的一些基础知识，包括双线性映射、数学困难问题、哈希函数、公钥密码体制、数字签名等。这些知识对于读者阅读本书后面章节是非常必要的。
1.1密码学数学基础
定义1.1设F是一个非空集合，是一个二元运算，若对于满足如下四个性质，则称F是一个群[1]，记为。
(1)封闭性：任取元素，满足。
(2)结合律：任取兀素，有。
(3)单位元：任取元素，存在元素，使得。
(4)逆元：任取元素，存在元素，使得。如果群F包含的元素个数是有限的，那么称F为有限群；否则，称F为无
限群。F包含的元素个数称为F的阶，记为。若中的元素满足交换律，即任取元素，满足，则称F是一个交换群[2]。
定义一个群中元素的幂运算为该元素的重复运算，，规定
若对于元素，存在正整数使得，则称满足此要求的*小正整数为元素的阶[3]。
若群F中的每个元素可以表示为一个元素的幂，则称是一个循环群，记为，元素被称为的生成元。
定义1.2设F是一个非空集合，和是两个二元运算，若F对于+和*满足如下三个性质，则称F是一个域[4]，记为。
(1)是一个交换群。
(2)是一个交换群，这里。
(3)分配律：任取元素，满足
和若域F的元素个数是有限的，则称为有限域；否则，称F为无限域[5]。
设q>3是一个素数，集合对于模加法？和模乘法③构成一个有限域[6]，即任取兀素，定义和，其中和分别是整数的普通加法和乘法。
令椭圆*线E由满足方程的解所对应的点构成，其中。一个基于E的椭圆*线加法群定义为，这里O是一个无穷远点；根据弦切(chord-and-tangent)法则[7]，G中加法和倍乘运算分别定义为和。关于椭圆*线及其运算的详细介绍请参阅文献[8]～[10]。
定义1.3假设Q和G2是两个阶为素数q的乘法循环群，是的一个生成元。如果映射:满足以下三个性质，则称e是一个双线性映射或双线性对[11]。
(1)双线性：对于任意，有。
(2)非退化性：其中表示中的单位元。
(3)可计算性：对于，存在有效的算法计算。
双线性映射是设计密码方案(如基于身份的密码方案)的重要工具，可以利用有限域上超椭圆*线中的Tate对或Weil对来构造[12，13]。
可证明安全性理论在一定的安全模型下能够证明一个密码方案达到特定的安全目标，采用“归约”方法将密码方案的安全性关联到某个数学困难问题。由于数学困难问题是公认难以求解的，因此证明攻击者在多项式时间内攻破密码方案的概率是可忽略的。下面给出与本书密码方案相关的数学困难问题[14-16]，密码方案的安全性依赖于这些数学问题的困难性，即无法在多项式时间内以不可忽略的概率解决这些数学困难问题。
定义1.4大整数因子分解问题：给定一个大整数n=pq，计算n的两个素数因子p和q。
定义1.5离散对数(discrete logarithm，DL)问题：令是一个大素数，是一个乘法循环群，是的一个生成元。给定中的一个二元组(g，y)，计算：使得。
定义1.6椭圆*线离散对数(elliptic curve discrete logarithm，ECDL)问题：
给定一个二元组(g，ga)eG1，其中是一个椭圆*线群，计算。
定义1.7计算性Diffie-Hellman(computational Diffie-Hellman，CDH)问题：
给定一个三元组，其中是未知的，计算。
定义1.8判定性Diffie-Hellman(decisional Diffie-Hellman，DDH)问题：给
定一个四元组，其中，是未知的，判定是否成立。
定义1.9Diffie-Hellman逆(Diffie-Hellman inversion，DHI)问题：给定一个
二元组，其中是未知的，计算。
定义1.10双线性Diffie-Hellman(bilinear Diffie-Hellman，BDH)问题：给定一个四元组，其中是未知的，计算。
定义1.11判定双线性Diffie-Hellman(decisional bilinear Diffie-Hellman，DBDH)问题：给定一个四元组和一个元素，其中是未知的，判断是否成立。
定义1.12平方Diffie-Hellman(square Diffie-Hellman，SDH)问题：给定一个二元组，其中；是未知的，计算。
定义1.13q-判定双线性Diffie-Hellman指数(q-decisional bilinearDiffie-Hellman exponent，问题：给定中的一个随机兀素和，中的一个元组，其中未知且，判定与是否相同。
定义1.14判定线性Diffie-Hellman(decisional linear Diffie-Hellman，DLDH)
问题：给定一个六元组；是未知的，判定是否成立。
哈希(Hash)函数是密码学的基本工具，被广泛应用于数字签名、消息完整性验证、区块链等领域。Hash函数是一种将任意长度的消息压缩成一个固定长度消息的函数，其输出值通常被称为Hash值(或哈希值)。Hash函数的功能是为消息产生一个“数字指纹”，其长度通常为丨28～H2bit。Hash函数通常又被称为单向散列函数、杂凑函数或消息摘要，在实际应用中通常采用特定的混合操作来设计Hash函数，而不是基于**的数学困难问题。目前常用的哈希函数有消息摘要算法MD5、安全散列算法SHA-M2、国密杂凑算法SM3等[^6]。
定义1.15Hash函数是将一个任意长度的消息m映射为一个固定长度为、输出值h=H(m)的函数，必须满足如下四个性质。
⑴可计算性：给定消息，能够在多项式时间内计算哈希值h=H(m)。
(2)单向性：给定哈希值，在多项式时间内计算m是不可行的。
(3)弱碰撞性：给定一个消息，寻找另外一个消息，使得H(mx)=hm在计算上是不可行的。
(4)强碰撞性：寻找两个不同的消息和，使得H(mx)=H(m2)在计算上是不可行的。
Hash函数本质上是一个确定性算法，相同的输人消息对应相同的输出值(哈希值)。然而，固定长度的输出意味着所有输人输出组合中一定存在碰撞。例如，MD5的抗碰撞性较差，无法有效抵抗生日攻击[15]。因此，一个安全的Hash函数需要满足以下条件：输人消息中任何一个比特的改变都会导致雪崩效应，产生一个完全不同的哈希值，攻击者很难找到有效的方法计算出哈希函数的碰撞。
如果一个哈希函数H满足以下三个性质，则认为是一个随机预言机[16]。
(1)均勻性：对于任意输人m，对应的输出H(m)在上是均勻分布的。
(2)确定性：对于相同的输人m，输出值H(m)也是相同的。
(3)有效性：对于输人的m，能在有效时间内计算H(m)。
1.3公钥密码体制
密码学的基本安全目标主要包括保密性、完整性、可用性和不可抵赖性。其中，保密性主要确保信息仅被合法用户访问，而不能泄露给非授权用户。根据密钥方式，密码体制分为两大类：对称密码体制和非对称密码体制。对称密码体制又称单钥密码体制，解密密钥和加密密钥相同或从一个密钥很容易推导出另外一个密钥。常用的对称密码算法包括数据加密标准(DES)、三重数据加密算法(3DES)、高级加密标准(AES)、国际数据加密算法（IDEA)、国密分组密码算法(SM4)、祖冲之算法(ZUC)等[17]。对称密码算法的优点是加密和解密的速度快，但存在密钥管理复杂、密钥分发需要安全信道、难以实现不可否认性等问题[18]。
公钥密码体制能够有效解决对称密码体制中的密钥分配和数字签名问题，在加密和解密阶段使用不同的密钥。在公钥密码体制中，每个用户拥有一个公开的公钥和秘密的私钥，私钥被用来签名或解密消息，对应的公钥来验证签名的合法性或加密消息。攻击者很难通过公钥计算出私钥，其难度等价于求解一个数学困难问题[19]。常用的公钥密码算法有国密公钥密码算法(SM2)、国密标识密码算法(SM9)、基于大整数因子分解问题的加密算法(RSA)、基于有限域离散对数问题的加密算法(ElGamal)、基于椭圆*线离散对数问题的加密算法(ECC)等。
基于公钥密码体制的加密消息流程如图1.1所示。
图1.1基于公钥密码体制的加密消息流程
假设消息的发送者和接收者分别为Alice和Bob，Alice利用Bob的公钥pkB和加密算法对消息m进行加密，生成对应的密文。Bob使用自己的私钥skB和解密算法Dec(.)对密文c进行解密，获得消息。
1.3.1RSA公钥密码
1976年，Diffie等[20]发表了New directions in c/tography，提出了公钥密码体制的思想。1978年，Rivest等[21]提出了**个公开的公钥密码方案RSA，该方案成为目前使用*广泛的公钥密码体制之一，其安全性基于大整数因子分解问题。RSA是一个确定性的加密方案，包括如下三个算法。
1.密钥生成
(1)选择两个秘密的大素数p和q。
(2)计算两个素数的乘积和欧拉函数伞。
(3)随机选择一个整数，满足e和咖）互素，即。
(4)计算 e的逆元。
(5)保密私钥。
2.加密
对于消息m，发送者利用公钥(n，e)执行如下的加密操作：
其中，c为消息m的密文。
3.解密
对于密文c，接收者利用私钥d执行如下的解密操作来恢复消息：
1.3.2ElGamal公钥密码
1985年，ElGamal[22]提出了一种基于离散对数问题的公钥密码方案，通常称为ElGamal公钥密码体制。该方案是一个随机化的加密方案，密文依赖于明文和随机数，即同一个消息多次加密后得到的密文不一定相同。ElGamal公钥密码方案主要包括如下三个算法。
1.密钥生成
(1)选择一个大素数p，其中p-1有一个大素数因子。
(2)选择为有限群的一个生成元。
(3)随机选择一个整数，计算。
(4)保密私钥，公开公钥。
2.加密
对于消息m，发送者利用公钥y执行如下的加密操作。
(1)随机选择一个整数。
(2)计算q=gkmodp。
(3)计算c2=ykmmodp。
(4)设置密文。
3.解密
对于密文c，利用私钥x：计算消息。
1.3.3Diffie-Hellman密钥交换协议
1976年，Diffie等提出了一种在两个用户间进行密钥协商的协议，即Diffie-Hellman密钥交换协议，通信双方可以在不安全的公开信道上协商产生一个共享的秘密密钥。该协议的安全性基于有限群上的离散对数问题。这个密钥交换协议只能用于密钥的交换，不能进行消息的加密和解密。通信双方确定共同的
展开
