密码技术手段:数据指纹,身份证明,消息的可信度和不可抵赖性,数据加密

信息安全(机密性,完整性,可用性,不可抵赖性)


Hash函数

hash可以用于校验文件是否完整,数字签名的摘要信息等等

hash函数是将任意大小的输入映射成固定大小的哈希值的函数

hash函数具备抗原像性(无法通过哈希值求到输入的值,是具备单相性的),抗次原像性(很难得到两个不同输入内容确得到相同的hash值),雪崩效应(原文的改变会导致hash值发生变化),抗碰撞性(很难得到可以生成相同hash值的输入内容)

常见的哈希函数:md4,md5,sha1,sha224,SM3(国密发布),sha256,sha384,sha512等等

md5发布于于1992年,摘要长度为128个比特,hash值为16位字节(128/8=16),块大小512个比特(每一次计算都以512个比特来分组处理),轮计算4(16 step)(一共进行4轮的计算,每一轮计算16步,一共计算64步)

简单的来说就是hash值长度是16位字节,计算过程中每个512比特的数据块都会进行64步的计算

sha1发布于1995年,摘要长度为160个比特,块大小512个比特,轮计算4(20 step)

md5和sha1的计算过程:

先将原消息作为一个头部,然后填充一个64位的尾部(这个尾部是说明了原消息有多长),然后中间填充一个经过计算得到的多少个位的数据(确保头部和尾部大小,以及中间的大小的和是512的倍数,这个中间会在开头填1,然后填0,直到头部和中间,以及尾部的bit是512的倍数为止),这个目的是将任意大小的原信息计算切成多个512的块,计算完成后是没有余的

也就是输入信息长度除于512不等于512-64时,进行填充,填充1和n个0,让其总长度等于(512-64)+512的倍数,这个填充是必须进行的,即便输入信息长度等于512-64,也要进行填充一个512bit的数据,确保填充位数是1到512之间

确保这个消息的长度=输入消息+64+填充 = 512的整倍数

md5会初始化4个32bit的值,sha1会初始化5个32bit的值

md5将512的块数据进行分组,分成16个32bit的子分组,然后对4个初始值进行循环计算

每个512块数据都需要进行4轮处理,每一轮64步的计算,然后得到128的结果,这个128位的结果将作为下一组的初始值,一直计算到最后的一组,得到就是128位md5哈希值

计算过程:在1到16步计算时,顺序获得16个子分组进行计算(即第几步就获取第几个分组的数据,例如第3步计算,使用第3组子分组进行计算),在17步到32步计算时,将跳跃获取16个子分组进行计算(跳跃的长度取决于当前的步数+5,即第18步时,获取2+5,第7组的数据),在33步到48步计算时获取当前步数+3,在49步到64步计算时获取当前步数+7,计算完成时,得到的数就是md5哈希值

如果有多个区块的数据,计算的步数就是n*64了,只是初始值变成了上一个区块计算完成的结果

mod 模计算

sha1原理和md5差不多,只是变成了80个步。并且将在20,40,60,80步用不同的计算方式

注意:md5和sha1都不安全了

md5

cryptographically broken and unsuitable for further use

users should avoid using the MD5 algorithm in any capacity. As previous research has demonstrated, it should be considered cryptographically broken and unsuitable for further use

sha1

谷歌SHA1碰撞实验

结论:应该放弃md5,sha1,改用sha2,sha3,BLAKE2等更安全的哈希函数


对称加密

AES,发布于1997年,其是迭代类型的加密,分组长度128bit,密钥长度有128,192,256,轮数分别10,12,14

计算过程:

AES加密计算会进行4种操作,轮密钥加(AddRoundKey),字节替代(SubBytes),行移位(ShiftRows),列混淆(MixColumns)

128位的明文和128位的密钥被分组成16个子节,变成4*4的正方形矩阵

加解密的每一轮的密钥都是通过密钥扩展算法得到的,因此轮密钥也是4*4的正方形矩阵

先进行轮密钥加,每轮输入与轮密钥异或,得到的值,当解密的时候,只需要再异或该轮密钥即可得到输入,原理就是相同的两个数进行异或,结果为0,异或计算就是不带进位的二进制加法,1异或1,等于0,0异或1,等于1

然后字节替换(subbytes),经过轮密钥加每个字节通过十六进制进行表示,十六进制的第一个数为行,第二个数字为列,通过s盒找到对应十六进制进行替换,这个s盒是16x16的正方形矩阵,还有逆s盒,用来解密

s盒的16*16的十六进制是通过计算得到的,计算过程:

先进行16*16初始化,然后对每个元素计算其乘法逆元

以11为例(这个11是十六进制的),二进制为10001

10001的多项式为f(x) = x的5次方+1

意思为第1位和第五位为1

AES使用了不可约多项式m(x)=x8+x4+x3+x+1

行移位变换:就是将4*4的正方形矩阵的行都向左移动,例如第二行左移2位,第一行不变

列混淆变换:将4*4的正方形矩阵的取一列乘以C(X)矩阵,得到一个新的值,放回原来的位置

正方形矩阵的列和C(X)矩阵的行进行计算,就可以得到4*4的经过列混淆变换的新矩阵

列混淆变换计算过程:

假设取了A1,0B,BD,C1的一列数据

即(02*A1),(03*0B),(01*AF),(01*C1)

通过十六进制转二进制,然后通过多项式表达式

02为10,为x

A1为10100001,为x的7次方+x的5次方+1

x乘以(x的7次方+x的5次方+1)= x的八次方+x的六次方+x

得到10100010,为A2

以此类推,得到四个二进制的值。然后这四个二进制进行异或相加,得到的值就是该列的新值

密钥扩展算法

将密钥编排成4个32位的初始密钥,最后一个32位的密钥通过G函数得到的结果,与第一个32位的密钥进行异或计算得到下一轮的第一个32位的密钥,下一轮的第一个32位的密钥和初始密钥的第二个的32位初始密钥进行异或,得到下一轮的第二个32位的密钥,一直计算到第11轮(轮密钥加需要进行10次,算上第0轮,也就是第11轮,也就是需要进行44次异或处理(4x11))


分组密码(分块加密,块密码)

将明文分成多个等长的块,并且使用确定的加密算法和密钥对每一个分组的块分别加密或者解密

工作模式,分组密码的解决方案(避免密钥长度,输入文长度,重放,完整度等问题及隐患)

初始化向量(Initialization Vector):随机初始化向量,生成一个随机的值,并且不会复用,确保其唯一性

填充方式(Padding):在特定工作模式中对输入报文进行填充操作,来达到报文的加密要求(避免输入报文长度不一)

填充方式有补0位(zero),ANSI X9.23(补0位,并且在填充内容最后一个字节为填充内容的长度),ISO 10126(填充随机数,并且在填充内容最后一个字节为填充内容的长度),PKCS 7(需要填充多长数据,就填充多少,需要填充n个,就填充n,取决于需要填充多长,PKSC 5是PKCS 7的子集,PKCS 5只支持8个字节的补齐)

常见的工作模式:电子密码本(ECB模式),密码分块链接(CBC模式),密文反馈(CFB模式),输出反馈(OFB模式),计数器(CTR模式),伽罗瓦计数(GCM模式)

电子密码本:直接将明文进行分块加密,加密完成后就成为输出的密文分组,一个明文分组对于着一组密文分组,解密时也是直接将密文块解成对于的明文

密码分块链接:明文分组后,将一个明文块与上一个密文块进行异或计算,在进行对其进行加密处理,因为其每个密文块都依赖于前面的明文块,并且将在第一个块使用初始化向量作为上一个密文结果进行处理

注意:因为CBC模式加密是依赖于上一个密文块的,因此加密过程是无法并行处理的,并且明文的小小的改动,都会导致全部密文块的改变,但是在解密过程在,是可以通过两个相邻的密文块得到一个明文块的,所以是可以并行处理解密的,而且因为密文只依赖于对应的明文块和下一个明文块,所以密文某个组的密文发生改变,不会影响其他明文组的,简单的来说就是加密依赖于上一个,解密不依赖,只依赖其对于的明文块,因为加密过程是通过上一个密文块处理得到的,因此也依赖于上一个密文块,其他都是不会受影响的

密文反馈:使用前一次密文结果继续加密操作,再和当前的明文进行异或计算,得到本次的密文,在第一次加密处理时,使用初始化向量IV进行加密处理,再通过于当前的明文进行异或计算,得到本次的密文,解密过程中将上一段的密文块进行加密,再通过与本次密文块进行异或计算,得到本次的明文块,第一次解密时通过初始化向量IV进行加密,再通过本次的密文块进行异或计算,得到第一次的明文块,解密过程是依赖于第一次的密文块和上一次的密文块的

输出反馈:使用初始化向量IV进行加密处理,再通过明文进行异或,得到密文,操作和密文反馈是类似的,但是输出反馈进行下一次加密处理是依赖于对明文进行异或计算之前的密文,密文反馈是依赖于对明文进行异或计算后得到密文,解密过程也是一样

计数器:在初始化向量IV的基础上设置一个计数器,通过加密器得到密文块,这个密文块与明文块进行异或计算,得到本次的密文结果,下一个加密时计数器自增,设置到那个初始化向量IV上,解密时也是通过初始化向量IV的基础上设置一个计数器进行加密,得到密文,和当前密文进行异或,得到当前的明文

注意:明文分组之间以及密文分组之间是不依赖,每一次加密解密过程,都是独立的,一个明文块对于一个密文块

CFB,OFB,CTR都是使用加密器来完成加密和解密工作的

伽罗瓦计数:将附加信息,明文,以及初始化向量IV进行加密工作,得到一个密文和一个附加信息认证标签(保护附加信息),然后整合附加信息,初始化向量IV,密文,附加信息认证标签,得到一个完整的密文,该模式能解决无法对加密信息进行完整性检查的缺点

使用一个自增的计数器,进行加密,得到的结果与明文进行异或得到密文

附加信息通过GMAC后,与密文进行异或计算,得到附加信息认证标签

GMAC通过伽罗瓦域的有效域乘法计算,来得到附加信息的标签值

伽罗瓦计数会先对128位的0进行加密得到结果1,通过初始化向量IV进行判断,判断其是否等于96位(后面拼接31位0,再拼一个1,就是128位),如果等于就直接使用iv,如果不是,则进行GHASH函数处理,将上面得到结果1和IV,以及一个空集合,得到一个128位的数

GHASH函数是在GF(2的128次方)的伽罗瓦域中的计算,GHASH函数会根据计数器来执行不同的计算方式,其是在有限域中的加法与乘法,其中是依赖于计数器上一次的结果的,输出结果是128位的

这个GCM模式,如果学过http协议的,应该感觉很熟悉,因为GCM模式作为TLS可选算法之一,全程叫AES128-GCM,使用AES256对称算法,128位长度,分组就采用了这个GCM模式

而源IP,源端口,目的ip等等信息作为附加信息(也就是头部)进行加密。得到认证标签,不但可以进行信息的加密,还可以确保完整性


非对称加密(公钥加密,私钥解密)

Public Key Cryptography

RSA算法(Rivest,Shamir,Adleman于1977年在MIT提出的通用公钥加密算法)

RAS算法依靠欧拉函数和模反元素来完成

给一个n数,求在n以内中与n互质的数的数目,计算这个数目的叫欧拉函数,以φ(n)表示,与n互质的数不一定是质数,例如8和9,互质的意思是两个互质的数之间的最大公因数是1,就是互质(没有其它公因数)

费马欧拉定理:

a的φ(n)次方 = 1(mod n),a的φ(n)次方 mod n = 1

φ(n)中的n 的计算方法:

假如n = i乘以q,并且和i乘以q互质时,φ(n) = (i-1)×(q-1)

当然n=1时,φ(1) 就是1,因为1和任何数(包括其自己)都为互质

如果n为质数时,φ(n) = n-1,因为小于质数n的数都与质数n互质

模反元素:假设两个整数a和b互质,那么可以找到一个整数c,让(a×c-1) mod b = 0或者(a×c)/ b = 1成立,这个时候c就是a的模反元素

RSA算法生成公钥和私钥的过程:

选择两个互质的不相等的数i和q,然后得到i和q的乘积,这个乘积就是n,再计算出n的欧拉函数

选择一个整数a,要求是大于1,并且小于φ(n),还要与φ(n)互质,再计算a对φ(n)的模反元素b

然后将n和a封装成公钥,n和b封装成私钥

这时不难看出,n是互相都公开的,破解RSA需要通过n和a计算出私钥的b,通过a获取到b,需要找到φ(n),因为b是a对φ(n)的模反元素

只要得到这个φ(n),就能获得私钥,但是这个φ(n) = (i-1)×(q-1),只通过i×q的乘积n来求出φ(n),当i和q是非常大的质数时,从其的乘积来分解出i和q是很困难的,因此i×q的乘积越大,破解的难度越大,因此建议使用1024位以及2048位以上的密钥

加解密过程:

明文的a次方,对n求模,余数就是密文 密文的b次方,对n求模,余数就是明文

椭圆曲线密码学(Elliptic Curve Cryptography,ECC,基于椭圆曲线数学的公开密钥加密算法)

比特币使用256位的椭圆曲线加密算法(secp256k1)

椭圆曲线基础知识

y的2次方 = (x的3次方 + a*x + b)mod p

椭圆曲线的相反数

P+(-P) = 0,P和-P是在x轴对称的点,P和-P的连线和椭圆曲线在无穷远处相交

椭圆曲线的加法

取P和Q两个点,P和Q的直线会与曲线的第三点相交,这个点即-R,-R的相反数为R

因为P+Q+(-R) = 0,因此P+Q = R

椭圆曲线的标量乘法(倍乘)

2P = P + P = R

可以基于该运算得到3P,4P,5P,6P等等的点,组成的就是一条椭圆曲线,在有限域中是离散的,因为其不是在无限大的实数域

nP = P+P+ … +P

椭圆曲线的除法

x / y = x * y 的乘法逆元

y * y 的乘法逆元 = 1 = y * y的负一次方

当n/P=0时,这时n是点P的阶,nP = 0∞,表示子集的大小(点的数量)

加解密过程:

Q = nP

P为基点Base point,n为私钥(这个n小于P的阶),Q为公钥

加密:

在椭圆曲线Z中选择一个点作为G点,G的阶为n,n是质数

选择一个私钥a生成公钥b,b =aG,将公钥b,G点,椭圆曲线Z发送给对方

明文Y,Y是椭圆曲线Z上的一个点,然后选择一个随机数W(W小于G的阶)

C1 = Y + W * b C2 = WG

将C1和C2发送,计算C1 - aC2,得到椭圆曲线Z上Y点,解码得到明文Y

因此C1 - aC2 = Y + W * b - a(WG) = M +WbG - bWG = M

ECC的安全性是建立在Q = nP的,已知n和P这两点是很容易得到Q的,相乘就可以了,但是已知Q和P两点,是很难推出n点的,因为椭圆曲线的点是随机的,没有规律的(离散)

ECDLP(椭圆曲线离散对数问题)的难度是高于RSA的因子分解问题


数字签名和消息完整性

密钥的交换和数字信任链

编码和解码