1.1单向散列算法
单向散列函数算法也称 Hash(哈希)算法,是一种将任意长度的消息压缩到某一固定长度(消 息摘要)的函数(该过程不可逆)。Hash 函数可用于数字签名、消息的完整性检测、消息起源的认 证检测等。常见的散列算法有MD5 、SHA 、RIPE-MD 、HAVAL 、N-Hash等。
在软件的加密保护中, Hash 函数是经常用到的加密算法。但是,由于 Hash 函数为不可逆算 法,软件只能使用Hash 函数作为加密的一个中间步骤。例如,对用户名进行 Hash变换,再对这个 结果进行可逆的加密变换(例如对称密码),变换结果为注册码。从解密的角度来说, 一般不必了 解 Hash 函数的具体内容(变种算法除外),只要能识别出是何种 Hash 函数,就可以直接套用相关 算法的源码来实现。
单向散列算法常用于密码学、数据完整性验证和数字签名等领域。一些常见的单向散列算法包括:
1. MD5(Message Digest Algorithm 5):
- 输出长度:128位(32个十六进制字符)。
- 已经被认为不安全,因为存在碰撞攻击的可能性。
2. SHA-1(Secure Hash Algorithm 1):
- 输出长度:160位(40个十六进制字符)。
- 由于存在碰撞攻击的漏洞,不再被广泛使用。
3. SHA-256、SHA-384、SHA-512:
- SHA-256输出长度:256位。
- SHA-384输出长度:384位。
- SHA-512输出长度:512位。
- 这些算法属于SHA-2家族,目前被广泛使用,提供了更高的安全性。
4. bcrypt、scrypt、Argon2:
- 这些算法是专门设计用于密码哈希和密码存储的。
- 具有抗暴力破解和抗硬件攻击的特性。
1.1.1 MD5 算法
MD5 消息摘要算法(Mesage Digest Algorithm) 是由 R.Rivest 设计的。它对输入的任意长度的 消息进行运算,产生一个128位的消息摘要。近年来,随着穷举攻击和密码分析的发展,曾经应用 最为广泛的MD5算法已经不那么流行了。
1. 算法原理
(1)数据填充
填充消息使其长度与448模512同余(即长度=448 mod 512)。也就是说,填充后的消息长度 比512的倍数仅小64位。即使消息长度本身已经满足了上述长度要求也需要填充,填充方法是:附一个1在消息后面,然后用0来填充,直到消息的长度与448模512同余。至少填充1位,至多填充512位。
(2)添加长度
在上一步的结果之后附上64位的消息长度。如果填充前消息的长度大于2“,则只使用其低64 位。添加填充位和消息长度之后,最终消息的长度正好是512的整数倍。令M[O…N-1]表示最终的消息,其中N 是16的倍数。
(3)初始化变量
用4个变量 (A 、B 、C 、D) 来计算消息摘要。这里的A 、B 、C 、D都是32位的寄存器。这些
寄存器以下面的十六进制数来初始化
A=01234567h,B=89abcdefh,C=fedcba98h,D=76543210h
而且,在内存中是以低字节在前的形式存储的,即如下格式。
(4)数据处理
以512位分组为单位处理消息。首先定义4个辅助函数,每个都是以3个32位双字作为输入, 输出1个32位双字。
F(X,Y,Z)=(X&Y|((~X)&Z)
G(X,Y,Z)=(X&Z)|(Y&(~Z))
H(X,Y,Z)=X^y^Z
I(X,Y,Z)=Y^(X)(~Z))
其中,“&”是与操作,“|”是或操作,“~”是非操作,“^”是异或操作。
这4轮变换是对进人主循环的512位消息分组的16个32位字分别进行如下操作:将A、B、C、 D 的副本a、b、c、d 中的3个经F、G、H、I 运算后的结果与第4个相加,再加上32位字和一个 32位字的加法常数,并将所得之值循环左移若干位,最后将所得结果加上a 、b 、c 、d 之一,并回 送至A 、B 、C 、D, 由此完成一次循环。
所用的加法常数由表 TI1]来定义,其中 i 为 1 至64之中的值。7[i] 等于4294967296 乘以 abs(sin(①))所得结果的整数部分,其中i 用弧度来表示。这样做是为了通过正弦函数和幂函数来进一 步消除变换中的线性。
( 5 ) 输 出
当512位分组都运算完毕, A 、B 、C 、D 的级联将被输出为 MD5散列的结果。
以上是 MD5算法的简单描述,更为详细的实现程序请参考随书文件中的源代码。
2.MD5 算法在加解密中的应用
MD5算法将任意长度的字符串变换成一个128位的大整数,而且是不可逆的。换句话说,即便 MD5算法的源代码满天飞,任何人都可以了解MD5算法,也绝对没有人可以将一个经 MD5算法加 密的字符串还原为原始的字符串。
1.1.2 SHA算法
安全散列算法 (Secure Hash Algorithm,SHA)包括 SHA-1 、SHA-256 、SHA-384 和 SHA-512, 共4种,分别产生160位、256位、384位和512位的散列值。下面以 SHA-1 为例,对 SHA系列散 列函数进行简要介绍。
1. 算法描述
SHA算法(Secure Hash Algorithm)是一系列密码散列函数的家族,设计用于计算数据的哈希值。哈希函数是一种将输入数据映射为固定长度输出的函数,输出通常称为哈希值或散列值。SHA算法的哈希值通常用于数据完整性验证、数字签名、密码存储和身份验证等安全应用中。
SHA-1:
SHA-1是SHA家族中的一员,产生160位(20字节)的哈希值。它在1995年由美国国家安全局(NSA)设计,并于1995年发布。然而,由于存在碰撞攻击的漏洞,SHA-1已经被证明不再安全,不建议在新的应用中使用。
SHA-2:
SHA-2系列包括多个标准,如SHA-256、SHA-384和SHA-512,分别产生256位、384位和512位的哈希值。这些算法是SHA-1的后续版本,由美国国家标准技术研究所(NIST)发布。SHA-256是其中最常用的算法之一,提供了较高的安全性和性能。SHA-2系列算法目前被广泛应用于许多安全领域。
SHA-3:
SHA-3是SHA家族的最新成员,是由NIST举办的密码竞赛中选出的一个候选算法。它基于Keccak算法,提供了与之前的SHA标准不同的设计和性能特性。SHA-3算法提供了更好的抵抗碰撞攻击和预映像攻击的安全性。尽管SHA-3在安全性和性能方面提供了一些优势,但目前在实际应用中使用的仍然是SHA-2系列算法。
安全性和选择:
在选择SHA算法时,需要考虑安全性、性能和实际应用场景。SHA-1由于存在安全漏洞已经被淘汰,不再建议使用。SHA-2系列算法提供了良好的安全性和性能,是目前大多数应用的首选。而SHA-3虽然提供了一些新的设计和优势,但在实际应用中还没有完全取代SHA-2系列算法。
1.1.3 SM3密码杂凑算法
SM3密码杂凑算法是由中国国家密码管理局于2010年制定的一种密码杂凑算法,用于计算数据的哈希值。它是中国政府规定的国家密码算法标准之一,旨在保护信息安全和数据完整性。
SM3算法特点:
1. 固定长度输出:SM3算法产生的哈希值长度为256位,即32字节。
2. 安全性:SM3算法被设计为抗碰撞(collision-resistant)的,即在合理的时间内,找到两个不同的输入数据生成相同的哈希值的概率很低。
3. 性能:SM3算法在软硬件实现上都具有较高的性能表现,能够在不同平台上高效地计算哈希值。
4. 设计简洁:SM3算法的设计相对简单,易于理解和实现。
SM3算法结构:
SM3算法采用了Merkle-Damgård结构,将输入数据分割为512位的数据块,并在每个数据块上进行一系列的运算,最终生成256位的哈希值。
SM3算法的主要运算包括:
初始化:初始化算法状态,包括初始向量和常量。
填充:对输入数据进行填充,使其长度满足512位的整数倍。
消息扩展:将512位的数据块扩展为132个字,以便进行后续的压缩函数运算。
压缩函数:对扩展后的消息进行压缩,产生下一个消息摘要的中间结果。
迭代:重复应用压缩函数和消息扩展,直到处理完所有的数据块。
输出:将最后一次压缩的结果作为最终的哈希值输出。
SM3算法安全性:
SM3算法在设计上考虑了一些安全性要求,包括:
抗碰撞性:SM3算法被设计为抗碰撞的,即使输入数据稍作修改,也应该显著地改变其哈希值。
预映像抗性:对于给定的哈希值,很难找到一个对应的原始数据。
二阶抗碰撞性:即使攻击者可以选择两个不同的输入数据,也很难使它们生成相同的哈希值。
使用SM3算法:
SM3算法在中国被广泛应用于数字签名、消息认证码、身份验证等安全领域。在实际使用中,可以使用专门的密码库或者加密工具来计算数据的哈希值,并应用在相应的安全协议和应用中。
1.1.4 小结
以上简要介绍了常见的单向散列函数加密算法MD5 和 SHA-1。 此外,密码学中的 Hash 算法还 有很多种,例如 RIPEMD 、HAVAL 、Tiger 等,对此感兴趣的读者可以参考相关资料。
需要引起重视的是,随着密码分析技术的发展,现有的散列算法都是不安全的,例如 SHA-160、 MD5、RIPEMD、HAVAL 、Tiger 在某些条件下能够构造出碰撞。软件保护人员在使用散列算法进行 保护时,建议选择SHA-256/384/512或者 Whirlpool。
如果在解密时碰到 Hash 算法, 一般只要根据每种 Hash 算法的特征搞清楚是哪一种 Hash 算法 及该算法是否变形,就可以通过该 Hash 算法的源代码写出注册机了。
1.2 对称加密算法
对称加密算法是一种加密技术,使用同一个密钥(也称为对称密钥)来进行加密和解密操作。这种密钥既可以用于加密原始数据,也可以用于解密密文,因此被称为对称密钥
特点:
1. 简单快速:对称加密算法的加密和解密速度通常比非对称加密算法快得多,因为其使用的是单一密钥。
2. 效率高:适用于大量数据的加密和解密,因为加密和解密过程的计算量较小。
3. 密钥管理相对容易:由于只需管理一个密钥,因此密钥的生成、存储、传输和更新相对简单。
4. 适用范围广泛:对称加密算法被广泛应用于网络通信、数据存储、加密文件等领域。
常见的对称加密算法:
1. DES(Data Encryption Standard)
DES是一种早期的对称加密算法,使用56位密钥对数据进行加密。由于DES的密钥长度较短,已经容易受到暴力破解攻击,因此现在很少在实际应用中使用。
2. 3DES(Triple DES)
3DES是对DES的改进,通过对数据应用三次DES算法,增强了安全性。但随着计算机性能的提升,3DES的加密速度相对较慢,逐渐被更先进的算法取代。
3. AES(Advanced Encryption Standard)
AES是目前最常用的对称加密算法之一,取代了DES和3DES。AES支持128位、192位和256位三种密钥长度,安全性高且性能优秀,被广泛应用于各种安全领域。
4. RC4
RC4是一种流密码算法,适用于加密通信和数据传输。然而,由于存在一些安全漏洞,如密钥流的可预测性和相关密钥攻击等,RC4已经不再被推荐使用。
5. IDEA(International Data Encryption Algorithm)
IDEA是一种快速且安全的对称加密算法,使用128位密钥和64位数据块。虽然IDEA在安全性上较为可靠,但由于专利限制和AES的普及,目前使用较少。
安全性考量:
尽管对称加密算法具有高效、简单等优点,但在密钥管理、密钥分发和密钥存储等方面存在一些挑战。此外,由于加密和解密使用相同的密钥,密钥的安全性显得尤为重要。
1.2.1 RC4 流密码
RC4是一种流密码(stream cipher)算法,也被称为Ron's Code或者Rivest Cipher 4。它是一种对称加密算法,使用同一个密钥来进行加密和解密,并且在加密和解密过程中以流的形式逐个处理数据。
RC4算法原理:
RC4算法基于一个伪随机生成器(PRNG),该生成器会生成一个伪随机的密钥流(keystream),然后将原始数据与密钥流进行按位异或(XOR)运算,以实现加密和解密操作。
1. 初始化阶段:在初始化阶段,RC4算法会根据所提供的密钥生成一个密钥流,这个密钥流通常是一个伪随机的序列。密钥流的生成过程是RC4算法的核心,它使用了密钥调度算法(Key Scheduling Algorithm,KSA)和伪随机生成算法(Pseudo-Random Generation Algorithm,PRGA)。
2. 密钥调度算法(KSA):KSA阶段通过对一个长度为256的数组进行初始化,并根据所提供的密钥对数组进行置换,从而生成初始的密钥流。
3. 伪随机生成算法(PRGA):PRGA阶段利用KSA阶段生成的初始密钥流,在每一轮加密或解密过程中进一步生成伪随机的密钥流,并与原始数据进行按位异或运算,实现数据的加密或解密。
### RC4算法特点:
1.简单快速:RC4算法的加密和解密速度通常非常快,适用于对实时数据进行加密处理。
2.灵活性:由于RC4算法使用的是流密码,可以对任意长度的数据进行加密和解密操作,而不需要像分组密码那样对数据进行分块处理。
3. 适用范围广泛:RC4算法被广泛应用于网络通信、数据传输等领域,例如在SSL/TLS协议中用于加密通信数据。
4. 内存占用小:RC4算法的实现通常所需的内存占用相对较小,适用于资源受限的环境。
RC4算法安全性考虑:
尽管RC4算法在实现上简单且效率高,但它也存在一些安全性上的问题,包括:
1. 密钥流偏置问题:RC4算法的初始密钥流可能存在偏置,使得密钥流的部分内容不够随机,这可能导致一些安全漏洞。
2. 密钥重用问题:如果同一个密钥在不同的通信会话中被重复使用,可能会导致密钥流的重复使用,从而使得攻击者更容易破解密文。
3. 相关密钥攻击:RC4算法存在一些与密钥相关的攻击方法,例如对密钥流的预测和相关密钥攻击,这些攻击可能会破坏算法的安全性。
4. 算法漏洞:RC4算法本身存在一些设计上的漏洞,例如密钥调度算法中的一些问题,可能会被攻击者利用来破解密文。
1.2.2 TEA算法
TEA(Tiny Encryption Algorithm)是一种对称加密算法,设计简单但效率高,适用于轻量级应用和资源受限环境。TEA算法是一种分组密码,它将明文数据分成64位(通常为8字节)的块,并使用128位(通常为16字节)的密钥进行加密。TEA算法以迭代轮次的方式对数据进行加密,每轮加密包括两个主要步骤:轮密钥加(Round Key Addition)和轮运算(Round Operation)。
TEA算法原理:
1. 密钥扩展:TEA算法使用128位的密钥,首先将密钥扩展为轮密钥数组。这个过程中,密钥被分成32位的子密钥,并且每个轮次需要使用其中的一部分子密钥。
2. 轮密钥加:每轮加密过程开始时,明文数据和当前轮所需要的子密钥进行异或运算。这个步骤旨在增加算法的混淆性,使得密钥的影响在每轮加密中都得到体现。
3. 轮运算:轮运算是TEA算法的核心步骤,它由一系列简单的位运算组成,包括移位、加法和异或运算。这些运算在每轮加密中都会根据明文数据和当前轮所使用的子密钥进行操作,以生成加密后的数据。
4. 迭代加密:TEA算法会对数据进行多轮加密,每轮加密中都会使用不同的轮密钥和轮运算。通常情况下,TEA算法会进行多轮迭代,以增强加密的安全性。
TEA算法特点:
1. 简单高效:TEA算法的设计非常简单,算法实现起来效率高,适用于资源受限的环境和轻量级应用。
2. 安全性较高:虽然TEA算法的设计简单,但其密钥长度较长(128位),并且采用多轮迭代加密,使得攻击者难以对其进行破解。
3. 适用范围广泛:TEA算法被广泛应用于嵌入式系统、传感器网络、智能卡等资源受限的场景,以提供数据的机密性和完整性。
4. 密钥长度固定:TEA算法的密钥长度固定为128位,这使得密钥管理更加简单,并且可以减少由于密钥长度不足而导致的安全隐患。
1.2.3 IDEA 算法
IDEA(International Data Encryption Algorithm,国际数据加密算法)于1991年由XueJia Lai( 来 学嘉)和L.Massey 提出。
1. 算法原理
分组密码 IDEA明文和密文的分组长度为64位,密钥长度为128位。该算法的特点是使用3种 不同代数群上的操作。
(1)生成子密钥
IDEA共使用52个16位子密钥,该密钥由输入的128位密钥生成,过程如下。
① 输入的128位密钥被分成8个16位的分组,并直接作为前8个子密钥使用。
② 128位密钥循环左移25位,生成的128位密钥被分成8个16位的分组,作为接下来的8个 子密钥。
③ 重复上一步,直至52个子密钥全部生成。
(2)IDEA 加密算法
IDEA 算法的加密过程由8个相同的加密步骤(称为加密轮函数)和1个输出变换组成,整体结构如图
表示按位异或操作;田表示定义在模216(=mod 65536)的模加法运算,其操作数都可以表示 成16位整数;O 表示定义在模216+1(=mod 65537)的模乘法运算。
64位明文被分成4个16位分组。每一轮加密需要6个子密钥,最后的输出变换只需要4个子 密钥,所以共需8×6+4=52个子密钥。如图6.3所示,在第1轮加密中,4个16位的子密钥分别 通过2个模2'⁶+1的乘法运算和2个模2'°的加法运算与明文进行混合。在对结果进行进一步处理 时,又用到了2个16位的子密钥及按位异或操作。第1轮加密的结果在进行部分交换后作为第2 轮加密的输人。照此重复进行7轮。在接下来的输出变换(Output Transform)中,使用52个子密钥 中的后4个,通过模加与模乘运算与第8轮的结果进行混合,产生最终的密文。
(3)IDEA 解密算法
对密文的解密过程与对明文的加密过程是一样的,如图6.3所示。解密与加密唯一不同的地方 就是使用了不同的子密钥。第一,解密所用的52个子密钥是加密的子密钥相对于不同操作运算的 逆元。第二,解密时子密钥必须以相反的顺序使用。
IDEA 中加法与乘法逆元的规则定义如下。
x+addinv(x)=0(mod 65536)
x×mulinv(x)=1(mod 65537)
其中,模2'°+1的乘法逆元计算可以使用欧几里德扩展算法求出
IDEA 加密运算的逆过程即为使用用户名160位散列的前128位作为 IDEA 的密钥,对散列的 32位和卷序列号进行IDEA 解密运算,再转换成其ASCIⅡ 码形式,得到最终的序列号。IDEA 解密 密钥的生成过程
1.2.4 BlowFish 算法
BlowFish算法是一个64位分组及可变密钥长度的分组密码算法,该算法是非专利的。
1. 算法原理
BlowFish算法基于Feistel 网络(替换/置换网络的典型代表),加密函数迭代执行16轮。分组长 度为64位 (bit), 密钥长度可以从32位到448位。算法由两部分组成,分别是密钥扩展部分和数 据加密部分。密钥扩展部分将最长为448位的密钥转换成4168字节的子密钥数组。其中,数据加密 由一个16轮的 Feistel 网络完成,每一轮由一个密钥相关置换和一个密钥与数据相关的替换组成。
(1)子密钥
BlowFish 使用大量的子密钥。这些密钥必须在加密前通过预计算产生。
● P数组由18个32位字的子密钥组成: P[1],P[2],…,P[18]。
● 4个8×32的包含1024个32位字的S-box:
S₁o,Si₄,…,Si,25: S₂o,S₂₁,…,S₂,255
S₃o,S₃,₁,…,S₃,2ss
S₄,o,S₄1,…,S4,255
子密钥扩展算法的计算步骤如下。
① 按顺序使用常数π的小数部分初始化P 数组和S-hox, 示例如下。
P[1]=0x243f6a88
P[2]=0x85a308d3
P[3]=0x13198a2e
P[4]=0x03707344
② 对P 数组和密钥进行逐位异或,在需要时重用密钥。
③ 使用当前的 P 数组和 S-box 对全0的64位分组使用 BlowFish 算法进行加密,用输出代替
P[1] 、P[2]。
④ 使用当前的 P 和S 对第③步的输出进行加密,并用输出分别代替P[3] 、P[4]。
⑤ 继续上面的过程,直到按顺序替代所有的P 数组和 S-box 中的元素为止。
(2)加密
BlowFish是由16轮的 Feistel 网络组成的。其输入是一个64位的数据元素x, 将 x 分成2个32 位部分,分别是xL 和xR 。
1.2.5 AES算法
ES(Advanced Encryption Standard, 高级加密标准)是 NIST(National Institute of Standards Technology)从1997年开始向全世界征集的加密算法,用于代替 DES作为新一代的加密标准。1997 年9月, NIST发布了AES需要符合的标准,要求 AES具有128比特的分组长度,支持128比特、 192比特和256比特的密钥长度,而且要求AES 能在全世界范围内免费得到。AES的评选工作一 共进行了3轮。第1轮共有15个算法入选,分别为CAST-256 、CRYPTON 、DEAL 、DFC 、E2、
FROG 、HPC 、LOKI97 、MAGENTA 、MARS 、RC6 、RIJNDAEL 、SAFER+ 、SERPENT 、TWOFISH 。 在第2轮公开评选后,NIST宣布共有5个算法进入决赛,分别是 MARS 、RC6 、Rijndael 、Serpent、 Twofish。2000年10月, NIST宣布, Rijndael 由于在各方面的表现十分优秀而当选AES。
Rijndacl 算法由比利时的两位著名的密码学家Joan Daemen 和 Vincent Rijmen 设计,读作 “Rain Doll”。实际上, Rijndael 算法本身和 AES算法的唯一区别在于支持的分组长度和密码密钥长度的范 围不同。Rijndael 是一种具有可变分组长度和可变密钥长度的分组密码,其分组长度和密钥长度均
可独立设定为32比特的任意倍,最小为128比特,最大为256比特。而AES算法将分组长度固定 为128位,仅支持128位、192位和256位的密钥长度,分别称作AES-128、AES-192 和AES-256。 本书中提到的AES算法,如无特别说明,专指FIPS-197中规定的AES算法。
1. 基本术语
(1)字节
AES算法的基本处理单元叫作字节,它由8比特序列组成,被看成一个整体。在AES算法中, 这些字节以有限域(Finite Field)上的多项式 (polynomial)表示。
其中,b;(O≤i≤7)分别代表一个字节的8个比特位。例如,字节{01100011},即0x63,代表相应 的有限域元素x⁶+x⁵+x+1。
(2)状态(State)
AES算法的所有操作都是在一个名为状态(State)的二维字节数组上进行的。状态由4行字节 组成,每行包括Nb字节,Nb为分组长度除以32的值。 s 表示状态,状态数组中的每个字节有2个 坐标,行号r的范围为O≤r<4, 列号c 的范围为O≤c<Nb。这样就可以用S, 或者s[r,c]来引用状 态中的每一个字节了。在AES算法的加密和解密过程的开始,将输人字节数组ino,iny,…,in;s复制 到状态数组中,然后对状态数组中的元素进行加密或解密操作,最后将结果复制到输出字节数组 out,out₁ ,…,out,s中,如图
在实际的软件实现中,将每一列的4字节作为一个32位字。例如, 一个长度为128位的分组 数据块在内存中的形式如下:
其他具体细节参考《加密与解密》---><----