密码学
香农对密码学的贡献
●评价密码体制的安全性：计算安全性、完善完全性
●混乱和扩散
●乘积密码体制思想
评价密码体系的安全性
●计算安全性：从计算量上衡量密码体系的安全性
●可证明安全性：通常使用归约的方法来证明所定义的安全性
●无条件安全性：即使无限资源也无法攻破
实际中广泛使用的算法
●二次筛法
●椭圆曲线算法：适用于素因子长度不同的合数
●数域筛法：适用于更大的数，目前分解的世界记录RSA-768 768位二进制数
信息量
对信息的直观认识：
●信道上传送的是随机变化的值
●事件发生概率与信息量的关系
●消息间的依赖关系与相互之间的信息量I(xi)=log2(1/p(xi))=-log2(P(xi))
密码体制中熵的性质
定理设(P,C,K,E,D)是一个密码体制，那么有H(K|C)=H(K)+H(P)-H(C)(密钥含混度)
含义：截获密文后，密钥的未知信息量等于明文和密钥总的未知信息量减去从已知密文中获得的信息量。
证明：
●H（KPC）=H（C|KP）+H(KP)
●明文和密钥可确定密文，即H（C|KP）=0，因此H（KPC）=H（KP）
●P和K是统计独立的，因此H（KP）=H（K）+H（P）
●同理H（KPC）=H（P|KC）+H（KC）=H（KC）
●因此H（KC）=H（KP）
●H（K|C）=H（KC）-H（C）=H（KP）-H（C）=H（K）+H（P）-H（C）
一般密码体制
●|P|=<|C|（单射）明文空间小于等于密文空间
●H(P|KC)=H(C|KP)=0已知密钥和密文条件下密文的熵等于已知密钥和明文条件下密文的熵
●H(PK)=P(P)+P(K)明文和密钥是统计独立的
●H(K|C)=H(P)+H(K)-H(C)
●H(P)=<H(C)=<H(P)+H(K)
●H(P|C)=<H(K|C)
密码学中的熵关系
●H(K|C)=H(P)+H(K)-H(C)
●H(P|C)=<H(K|C)
伪密钥
获得同一密钥加密的密文越长，存在伪密钥的可能性越小
现代分组密码设计原理
●混乱（Confusion）：密钥和明文以及密文之间的依赖关系复杂
●扩散（Diffusion）：单个密钥或明文位的影响尽可能扩大到更多的密文位中
大整数因式分解
●整数分解问题隐含了RSA的破译问题
●试除法是最简单和直接的方法，即用直到sqrt（n）的每个素数去整除n
●n<10^20基本可行
●如果n有小的因子比较有效
费马定理
假定可找到a，b满足a^2-b^2=n，若（最大公约数）gcd（a+-b，n）是n的非平凡因子，那么可找到n的两个非平凡因子。
小加密指数攻击
使用一个较小的e值（比如e=3），则进行RSA签名验证和加密会很快。
避免使用小的加密指数，e=2^16+1=65537
短消息加密前填充，PKCS标准
离散对数
离散对数问题
已知：乘法群（G，·），一个n阶元素α属于G和元素β属于<α>
问题：找到唯一整数i，0=>i=<n-1,满足α^i=β
我们将整数i记为ind（α）（β），称为α为底的β的离散对数
●D-H密钥交换
●只能交换密钥
●存在中间人攻击
●ElGamal体制
●加密依赖随机数
椭圆曲线
●椭圆曲线多倍点运算构成单项函数
●椭圆曲线离散对数问题求解难度大于大整数分解及有限域熵的离散对数问题
●相同安全程度要求下，椭圆曲线密码所需要的密钥规模要小的多
●有限域上的椭圆曲线在点加运算下构成有限交换群，其阶与基域规模相近
椭圆曲线离散对数问题
有限域Fq上的椭圆曲线E（Fq）由点组成，其上点的数目记为#E（Fq），称为椭圆曲线E（Fq）的阶
给定有限域Fq上的椭圆曲线E（Fq）上一点P，P+P称为点P的倍点运算
椭圆曲线上同一点多次加称为该点的多倍点运算。设k是正整数，P是椭圆曲线上一点，称点P的k次加为点P的k倍点运算，记为Q=kP，kP=（k-1）P+P，k倍点可递归求得
椭圆曲线离散对数问题ECDLP。已知椭圆曲线E（Fq）、阶为n的点P属于E（Fq）及Q属于
，椭圆曲线离散对数问题是指确定整数k∈[0,n-1]，使得Q=kP成立
SM2
国密关于椭圆曲线的标准算法集
●有限域Fq选择素域Fp（p>2^191）或二元扩域F2m(m>2^192)
●Fp的椭圆曲线方程：y^2=x^3+ax+b a,b∈Fp，(4a^3+27b^2)mod（p）≠0
●F2m的椭圆曲线方程：y^2+xy=x^3+ax^2+b a,b∈F2m,b≠0
●推荐椭圆曲线参数：使用素域256位椭圆曲线曲线方程y^2=x^3+ax+b
数据类型和数据类型之间的转换
比特串、字节串、域元素、椭圆曲线上的点
椭圆曲线的解是域上的元素，消息处理时候是比特流。通过类型转换函数进行相应的类型，
再进行操作
参数：公私钥对（d，P），P=（x，y）=dG（G为基点，n为其阶，n、G公开）记（dA，PA）为A的公私钥对，阶位n的基点G=（xG，yG），h余因子h=#E（Fq）/n
d是私钥，P是公钥，d是一个整数，P是椭圆曲线上的一个点
使用的函数
密码杂凑函数Hv（国密SM3标准）
密钥派生函数KDF（调用Hv）
伪随机数发生器（国家密码管理局批准的）
SM2数字签名
A对消息M进行签名，计算ZA=H256（ENTL||ID||a||b||xG||yG||xA||yA）阶位n的基点G=（xG，yG）（dA，PA）为A的公私钥对，PA=dA·G=（xA，yA）
签名算法：
验证算法（M`,(r`,s`)）：
s`=((1+dA)-1(l-r`dA))mod(n)
s`(1+dA)+r`dA=k mod(n)
s`G+(s`+r`)dAG=kG可推导出s`G+tPA=kG=(x1`,y1`)
R=e`+x1`mod(n)=r`
V1:r`∈[1,n-1]?
V2:s`∈[1,n-1]?
V3:M``=ZA||M`
V4:e`=Hv(M``)
V5:t=(r`+s`)mod(n)若t=0则验证不通过
V6:(x1`,y1`)=s`G+tPA
V7:R=e`+x1`,R=r`?
A1：M`=ZA||M
A2：e=Hv（M`）
A3：产生随机数k∈[1,n-1]
A4：（x1，y1）=kG
A5：r=（e+x1）mod（n）若r=0或r+k=n返回A3
A6：s=（（1+dA）^-1（k-rdA））mod（n）若s=0返回A3
A7：返回M的签名（r，s）
SM2密钥交换协议
SM2公钥加密算法
A发送长为klen的消息比特串M给B
阶为n的基点G=（xG,yG），h余因子，（dB,PB）为B的公私钥对
加密算法：
产生随机数k∈[1,n-1]
C1=kG=(x1,y1)
S=hPB若S是无穷远点则报错并退出
kPB=（x2，y2）
t=KDF（x2||y2，klen）若t全0返回1
C2=M异或t
C3=Hash（x2||M||y2）
输出M的密文C=C1||C2||C3
解密算法：
验证C1是否满足椭圆曲线方程
S=hC1若S是无穷远点则报错并退出
dBC1=（x2，y2）
t=KDF（x2||y2，klen）若t全0报错并退出
M`=C2异或t
u=Hash（x2||M`||y2）若u≠C3则报错并退出
输出明文M`
C1=kG=(x1,y1),kPB=(x2,y2)=>dBC1=dBkG=kdBG=kPB=(x2,y2)
数字签名体制
公钥密码的使用和优势
远程密钥分配
数字签名
一个数字签名体制是一个五元组（P，A，K，S，V），满足：
P是所有可能的消息组成的有限集
A是所有可能的签名组成的有限集
K是所有可能的密钥组成的有限集（密钥空间）
对每个k∈K，有一个秘密的签名函数sig（k）属于S和一个相应的公开验证函数ver（k）∈v，等于每个消息x∈P和每个签名y∈A，，满足：
称（x,y）为带签名的消息
签名和公钥加密结合的方案
●第一种方案：先签名再加密：
●第二种方案：先加密再签名：
●第二种方案可能存在伪造签名混淆发送者的问题，建议使用第一种方案
数字签名
符号：
A：消息签名者
B：消息验证者
：用户A的标识，可以唯一确定A的公钥
：用户A的签名私钥
：签名主公钥
：签名主私钥
M：待签名消息，任意长度比特串
：待验证消息，任意长度比特串
：生成的消息的数字签名
：接收的消息的数字签名
：双线性对的三个循环群
：循环群的阶，素数
：元素个数为N的有限域，mod N运算
：的生成元
：的生成元，
：中的元素，生成元
：一个字节，表示签名私钥生成函数识别符，KGC（密钥生成中心）选择并公开
、
：调用，将比特串Z转换程一个的整数
数字签名流程
数字签名验证
数据完整性
信息安全的三个要点
机密性：不能被没有授权的人看到
完整性：在存储过程中，不能被非法篡改，传统加密算法可以解决机密性问题，不能解决完整性问题----结合区块链技术，提高信息安全等级
可用性
加密算法解决了机密性问题，能否解决完整性问题
数据完整性是抗击对消息未授权修改的安全服务
有些应用不需要机密性，比如电子交易信息
如何解决完整性问题：附加冗余
对称技术：Hash函数（散列函数）、报文鉴别码（MAC）
非对称技术：数字签名
Hash函数
Hash函数H（M）作用于一任意长度的消息M，它返回一固定长度（通常超过128位）的散列值h：h=H（M）
有时也称“摘要函数”、“散列函数”或“杂凑函数”
h也被称为消息或数据的“摘要”或“指纹”
带密钥的Hash函数：可将h和消息M一起在不安全的信道中传，被称为MAC（消息鉴别码）
不带密钥的Hash函数：h必须安全存放、确保h不被篡改
随机预言机ROM（Random Oracle Machine）
Bellare和Rogaway提出
提供“理想”Hash函数的数学模型
确定性，有效性和均匀输出
令是为所有从的函数集合，假定，随机从中选出一个Hash函数，对于任意的输入，其输出值是均匀的，且计算的唯一方法是询问随机预言机。
原像问题
Find-Rreimage(h,y,Q)
选择任意的
for each
return(failure)
SSL协议
功能：
身份鉴别
传输加密
完整性保护
密钥交互
层次结构
握手协议
改变密码格式协议
警告协议
应用数据协议
记录层协议
分段：每个上层应用数据被分成字节或更小的数据块
压缩：压缩是可选的，并且是无损压缩，压缩后内容长度的增加不能超过1024字节
完整性：再压缩数据上计算消息鉴别MAC
加密：对压缩数据及MAC进行加密
打包：增加ssl记录头（内容类型、主版本、次版本、数据长度）
握手协议
第一阶段：版本、算法协商
（1）：Support Version，RC，Session id，Supported Cipher suite，Supported Compress method，分别表示支持的最高版本、客户端随机数（4+28字节）、会话ID、支持的密码套件名称（SSL_DHE_RSA_WITH_DES_CBC_SHA）、支持的压缩方法
（2）：Version，RS，Session ID，Cipher suit，Compression method，分别表示选择的版本、服务器端随机数（4+28字节）、会话ID、选择的密码套件名称、选择的压缩方法
第二阶段：服务器发送证书给客户端
（3）：Certs of Server，表示服务器的相关证书RSA或者DSA证书等。
（4）（可选）：将用在密钥交换过程的相关公钥参数，以及这些参数的数字签名（公钥参数）发送给客户端。仅当（3）中已提供，则可省；如果选择DH协议，则会发送以及它们的数字签名。再选择RSA方式交换密钥的时候，也可以选择重新生成一个临时的、不同于签名的RSA加密密钥发送给客户端。
（5）（可选）：Request of Client Certs，请求客户端发送证书进行验证，仅当服务器强制客户端认证时，服务器端才发送此消息，消息中会包含服务器端支持的证书类型和所有Server端信任的证书发行机构的DN（Distinguished Name）列表。
第三阶段：由客户端发送证书给服务器端
（6）（可选）：Certs of Client，表示客户端的相关证书，仅当服务器强制客户端认证时，客户端才发送此消息。
（7）：或者，例如，若选择RSA认证，则用服务器的公钥加密预备主密钥PM给服务器；若选择DH认证，则发送给服务器，服务器可以根据自己生成PM。
（8）（可选）：（已发送接收的握手信息+主密钥M的MD5和SHA1摘要），客户端的签名，仅当服务器强制客户端认证时，客户端才发送此消息。
第四阶段：密钥生成
客户端和服务器端分别生成HMAC消息鉴别码密钥Auth.Key，分组加密初始向量IV，分组加密密钥Enc.Key
以后，客户端用客户端的Auth.Key，IV，Enc.Key加密消息发送给服务器端，而服务器端则用服务器端的Auth.Key，IV，Enc.Key加密消息发送给客户端，加密是单向的。
第五阶段：分别发表握手协议结束申明
使用HMAC算法计算收到和发送的所有握手消息、主密钥M和常数串“client/server finished”的摘要，然后通过一个伪随机函数PRF计算出结果，用对称加密算法机密后发送给对方，对方收到验证其正确性。
