一、密码的定义
密码,最初的目的是用于对信息加密,计算机领域的密码技术种类繁多。但随着密码学的运用,密码还被用于身份认证、防止否认等功能上。密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则,变明文为密文,称为加密变换;变密文为明文,称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换,随着通信技术的发展,对语音、图像、数据等都可实施加、脱密变换。
二、密码的分类
最基本的分类是:信息加解密分为对称加密(Sysmmetric Cryptography)和非对称加密(Public-Key Cryptography,Asymmetric Cryptography),这两者的区别是是否使用了相同的密钥。
除了信息的加解密,还有用于确认数据完整性(Integrity)的单向散列(One-Way Hash Function)技术,又称密码检验(Cryptographic Checksum)、指纹 (Fingerprint)、消息摘要 (Message Digest)。
信息的加解密与信息的单向散列的区别是,对称与非对称加密是可以通过密钥解出明文,而单向散列是不可逆的。信息的加解密,密文必定是不定长的,而单向散列可以是定长的。
结合密码学的加解密技术和单向散列技术,又有了用于防止篡改的消息认证码技术,防止伪装的数字签名技术以及认证证书。
三、密码问题的应对策略
威胁问题 | 特征 | 对应技术 |
---|---|---|
窃听 | 机密性 | 对称、非对称加密 |
篡改 | 完整性 | 单向散列、消息认证码、数字签名 |
伪装 | 身份认证 | 消息认证、数字签名 |
否认 | 不可否认 | 数字签名 |
四、信息的加密手段
需要对加密和解密使用相同密钥的加密算法。由于其速度快,对称性加密通常在消息发送方需要加密大量数据时使用。对称性加密也称为密钥加密。
所谓对称,就是采用这种加密方法的双方使用方式用同样的密钥进行加密和解密。密钥是控制加密及解密过程的指令。算法是一组规则,规定如何进行加密和解密。
举个例子来简要说明一下对称加密的工作过程。甲和乙是一对生意搭档,他们住在不同的城市。由于生意上的需要,他们经常会相互之间邮寄重要的货物。为了保证货物的安全,他们商定制作一个保险盒,将物品放入其中。他们打造了两把相同的钥匙分别保管,以便在收到包裹时用这个钥匙打开保险盒,以及在邮寄货物前用这把钥匙锁上保险盒。
因此加密的安全性不仅取决于加密算法本身,密钥管理的安全性更是重要。因为加密和解密都使用同一个密钥,如何把密钥安全地传递到解密者手上就成了必须要解决的问题。
DES全称为Data Encryption Standard,即数据加密标准,是一种使用密钥加密的块算法,1977年被美国联邦政府的国家标准局确定为联邦资料处理标准(FIPS),并授权在非密级政府通信中使用,随后该算法在国际上广泛流传开来。需要注意的是,在某些文献中,作为算法的DES称为数据加密算法(Data Encryption Algorithm,DEA),已与作为标准的DES区分开来。
DES 算法是以 64 bits 明文为一个单位(每隔 7 bits 会有一个 checksum bit,因此实际有效为 56 bits),分组对明文进行加密的,是一种分组密码(Block Cipher)算法。DES 算法原理是通过一个称为 Feistel 网络,并经过 N 轮的轮函数的计算实现的。
DES算法的入口参数有三个:Key、Data、Mode。其中Key为7个字节共56位,是DES算法的工作密钥;Data为8个字节64位,是要被加密或被解密的数据;Mode为DES的工作方式,有两种:加密或解密。
DES设计中使用了分组密码设计的两个原则:混淆(confusion)和扩散(diffusion),其目的是抗击敌手对密码系统的统计分析。混淆是使密文的统计特性与密钥的取值之间的关系尽可能复杂化,以使密钥和明文以及密文之间的依赖性对密码分析者来说是无法利用的。扩散的作用就是将每一位明文的影响尽可能迅速地作用到较多的输出密文位中,以便在大量的密文中消除明文的统计结构,并且使每一位密钥的影响尽可能迅速地扩展到较多的密文位中,以防对密钥进行逐段破译。
DES算法把64位的明文输入块变为64位的密文输出块,它所使用的密钥也是64位(实际用到了56位,第8、16、24、32、40、48、56、64位是校验位, 使得每个密钥都有奇数个1),其算法主要分为两步:
①初始置换:
其功能是把输入的64位数据块按位重新组合,并把输出分为L0、R0两部分,每部分各长32位,其置换规则为将输入的第58位换到第一位,第50位换到第2位……依此类推,最后一位是原来的第7位。L0、R0则是换位输出后的两部分,L0是输出的左32位,R0是右32位,例:设置换前的输入值为D1D2D3……D64,则经过初始置换后的结果为:L0=D58D50……D8;R0=D57D49……D7。
其置换规则见下表:
58,50,42,34,26,18,10,2,
60,52,44,36,28,20,12,4,
62,54,46,38,30,22,14,6,
64,56,48,40,32,24,16,8,
57,49,41,33,25,17,9,1,
59,51,43,35,27,19,11,3,
61,53,45,37,29,21,13,5,
63,55,47,39,31,23,15,7,
②逆置换
经过16次迭代运算后,得到L16、R16,将此作为输入,进行逆置换,逆置换正好是初始置换的逆运算,由此即得到密文输出。
注意:此算法是对称加密算法体系中的代表,在计算机网络系统中广泛使用。DES 于 1977 年公布,现已被破解。
DES(即Triple DES)又称为 TDEA(Triple Data Encryption Algorithm)或 3DES。是DES向AES过渡的加密算法,它使用3条56位的密钥对数据进行三次加密。是DES的一个更安全的变形。它以DES为基本模块,通过组合分组方法设计出分组加密算法。比起最初的DES,3DES更为安全。
该方法使用两个密钥,执行三次DES算法,加密的过程是加密-解密-加密,解密的过程是解密-加密-解密。
3DES加密过程为:C=Ek3(Dk2(Ek1(P)))
3DES解密过程为:P=Dk1(EK2(Dk3(C)))
采用两个密钥进行三重加密的好处有:
①两个密钥合起来有效密钥长度有112bit,可以满足商业应用的需要,若采用总长为168bit的三个密钥,会产生不必要的开销。
②加密时采用加密-解密-加密,而不是加密-加密-加密的形式,这样有效的实现了与现有DES系统的向后兼容问题。因为当K1=K2时,三重DES的效果就和原来的DES一样,有助于逐渐推广三重 DES。
③三重DES具有足够的安全性,目前还没有关于攻破3DES的报道。
AES 是于 2000 年被采用的最新的对称加密标准,采用了 Rijndael 算法。
Rijndael 算法也是一种分组算法,密钥长度规定为 128 bits,192 bits, 256 bits 三种规格。与 DES 不同,Rijndael 算法没有采用 Feistel 网络,而是采用 SPN 结构,并通过多个轮函数实现的。
SPN 结构和轮函数此处不再展开,简单的说,就是对明文数据分组,然后轮函数是进行一系列的平移、翻转、位之间的交换等操作。具体可以参考 Advanced Encryption Standard, Wikipedia。
Rijndael密码的设计力求满足以下3条标准:
① 抵抗所有已知的攻击。
② 在多个平台上速度快,编码紧凑。
③ 设计简单。
当前的大多数分组密码,其轮函数是Feistel结构。Rijndael没有这种结构。Rijndael轮函数是由3个不同的可逆均匀变换。
Rijndael (State, ExpandedKey)
{
AddRoundKey (State, ExpandedKey);
for (i=1; i <Nr; i ++)
Round (State, ExpandedKey+Nb* i);
FinalRound (State, ExpandedKey+Nb*Nr)
}
Round (State, RoundKey)
{
ByteSub (State);
ShiftRow (State);
MixColumn (State);
AddRoundKey (State, RoundKey)
}
FinalRound (State, RoundKey)
{
ByteSub (State);
ShiftRow (State);
AddRoundKey (State, RoundKey)
}
Rijindael 算法,可自由免费使用,安全、快速,暂未被破解。推荐使用。
非对称加密可以用于解决密钥配送问题。
相对于对称密码加解密采用相同的密码,非对称密码加解密采用的是不同的密钥,公钥和私钥成对,公钥加密的信息,只有相应的私钥才可解密。
非对称加密流程
无法解决公钥认证的问题,可能被中间人伪造公钥。
首先这个加密算法的命名,它其实是三个人的名字.早在1977年由麻省理工学院的三位数学家Rivest、Shamir 和 Adleman一起提出了这个加密算法,并且用他们三个人姓氏开头字母命名. RSA加密算法是一种非对称加密算法,其玩法打破了以往所有加密算法的规则.在RSA出现之前,所有的加密方法都是同一种模式:加密解密的规则使用同一种方式.这种长达几个世纪的加密方案有一个致命的缺陷.在传递加密信息时,必须让对方拿到解密的规则才能正常解密.由于加密解密的规则一致,所以保存和传递"密钥",就成了最头疼的问题。
没错,RSA加密使用了"一对"密钥.分别是公钥和私钥,这个公钥和私钥其实就是一组数字!其二进制位长度可以是1024位或者2048位.长度越长其加密强度越大,目前为止公之于众的能破解的最大长度为768位密钥,只要高于768位,相对就比较安全.所以目前为止,这种加密算法一直被广泛使用.
密码强度,默认的 RSA 长度为 2048 bit
AES(bit) | RSA(bit) |
---|---|
128 | 3072 |
192 | 7680 |
256 | 15360 |
混合加密就是对称加密与非对称加密的结合。由于对称加密算法速度快,强度高,而非对称加密算法效率低,但能解决密钥配送问题。因此可以通过非对称加密配送对称密钥,再采用对称密钥用来加密的方式,实现网络的密钥配送与通信加密。
一般实践中,公钥通过证书认证配送,而对称加密用的密钥是每次随机产生。因此公钥密码的强度应该高于对称密码,因为对称密码只对当前一条信息负责,而非对称密码会影响到过完与未来所有的通信。
加密模式是针对密码分组或流加密所采用的迭代模式。
不同的分组加密方式,就有不同的加密模式:
单向散列技术是为了保证信息的完整性,防止信息被篡改的一项技术。
特点:
MD 散列算法分为 MD4, MD5 两套算法,都可计算出 128 bits 的散列。MD 系列算法已经被中国科学家王小云破解(可于有限时间内找出碰撞)。
SHA 是单向散列算法的一个标准的统称,其下又分为 SHA-1, SHA-2, SHA-3 三套算法。
其中 SHA-1 可生成 160 bit 散列值,已被攻破,不推荐使用。
SHA-2 可生成不同长度的散列,如 256 bits (SHA-256), 384 bits (SHA-384), 512 bits (SHA-512),同时对输入的消息长度存在一定限制,SHA-256 上限接近于 2^64-1 比特,SHA-384、SHA512 则接近于 2^128-1比特。
SHA-3,是 2012 年被采用的最新标准,采用了 Keccak 算法。
Keccak 算法的优点:
MD4,5, RIPEMD, RIPEMD-160, SHA-1, SHA-2 均采用 MD 结构(Merkle-Damgard construction)
SHA-3 采用海绵结构
算法 | 散列长度,bit | 输入长度 | |
---|---|---|---|
MD4 (Message Digest 4) | 128 | 已破解 | |
MD5 | 128 | 已破解 | |
SHA-1 | 160 | 2^64 = 2048 | 谨慎使用,不推荐 |
SHA2 (SHA-224) | 224 (32*8 - 32) | 2^64 | - 32 表示截去 32 bit,下同 |
SHA2 (SHA-256) | 256 (32*8) | 2^64 | |
SHA2 (SHA-512/224) | 224 (64*8 - 288) | 2^64 | |
SHA2 (SHA-512/256) | 256 (64*8 - 256) | 2^64 | |
SHA2 (SHA-384) | 384 (64*8 - 128) | 2^128 | |
SHA2 (SHA-512) | 512 | 2^128 | |
SHA-3 | 无限制 | ||
RIPEMD-128 | 已破解 | ||
RIPEMD-160 | 谨慎使用,是比特币采用的 | ||
RIPEMD-256 | |||
RIPEMD-320 |
所谓哈希(hash),就是将不同的输入映射成独一无二的、固定长度的值(又称"哈希值")。它是最常见的软件运算之一。
如果不同的输入得到了同一个哈希值,就发生了"哈希碰撞"(collision)。
黑客攻击的一种方法,就是设法制造"哈希碰撞",然后入侵系统,窃取信息。
防止哈希碰撞的最有效方法,就是扩大哈希值的取值空间。
16个二进制位的哈希值,产生碰撞的可能性是 65536 分之一。也就是说,如果有65537个用户,就一定会产生碰撞。哈希值的长度扩大到32个二进制位,碰撞的可能性就会下降到 4,294,967,296 分之一。
更长的哈希值意味着更大的存储空间、更多的计算,将影响性能和成本。开发者必须做出抉择,在安全与成本之间找到平衡。
哈希碰撞的概率取决于两个因素(假设哈希函数是可靠的,每个值的生成概率都相同)。
这个问题在数学上早有原型,叫做"生日问题"(birthday problem):一个班级需要有多少人,才能保证每个同学的生日都不一样?
答案很出人意料。如果至少两个同学生日相同的概率不超过5%,那么这个班只能有7个人。事实上,一个23人的班级有50%的概率,至少两个同学生日相同;50人班级有97%的概率,70人的班级则是99.9%的概率(计算方法见后文)。
这意味着,如果哈希值的取值空间是365,只要计算23个哈希值,就有50%的可能产生碰撞。也就是说,哈希碰撞的可能性,远比想象的高。实际上,有一个近似的公式。
上面公式可以算出,50% 的哈希碰撞概率所需要的计算次数,N 表示哈希的取值空间。生日问题的 N 就是365,算出来是 23.9。这个公式告诉我们,哈希碰撞所需耗费的计算次数,跟取值空间的平方根是一个数量级。
这种利用哈希空间不足够大,而制造碰撞的攻击方法,就被称为生日攻击(birthday attack)。
给出生日攻击的数学推导。
至少两个人生日相同的概率,可以先算出所有人生日互不相同的概率,再用 1 减去这个概率。
我们把这个问题设想成,每个人排队依次进入一个房间。第一个进入房间的人,与房间里已有的人(0人),生日都不相同的概率是365/365
;第二个进入房间的人,生日独一无二的概率是364/365
;第三个人是363/365
,以此类推。
因此,所有人的生日都不相同的概率,就是下面的公式。
上面公式的 n 表示进入房间的人数。可以看出,进入房间的人越多,生日互不相同的概率就越小。
这个公式可以推导成下面的形式。
那么,至少有两个人生日相同的概率,就是 1 减去上面的公式。
上面的公式,可以进一步推导成一般性的、便于计算的形式。
根据泰勒公式,指数函数 ex 可以用多项式展开。
如果 x 是一个极小的值,那么上面的公式近似等于下面的形式。
现在把生日问题的1/365
代入。
因此,生日问题的概率公式,变成下面这样。
假设 d 为取值空间(生日问题里是 365),就得到了一般化公式。
上面就是哈希碰撞概率的公式。
单向散列可以解决篡改的问题,但消息是来自可信一方,还是来自伪装者,却无法解决。伪装者完全可以发送有害的信息和该信息的散列,而接受者却无法分辨。消息认证码技术可以解决此类问题。
消息认证码(Message Authentication Code),简写为 MAC。通过发送方与接收方共享密钥,通过该共享密钥对计算 MAC 值。
消息认证码使用步骤:
MAC 实现的关键,是获得一串需要与共享密钥相关而且足够有区分度的串。
因此,可以通过多种方式获得 MAC 值,如单向散列、分组密码截取最后一组作为 MAC 值、流密码、非对称加密等。
由于 MAC 无法解决否认的问题是由于采用的相同的密钥,那么采用公私钥对就可以解决啦~
采用非对称加密的消息认证码的技术,就是数字签名。
由于用于解密的是公钥,是公开的。因此任何人都可以验证数字签名。
数字签名的核心,就是非对称加密,在前文已经介绍了一些非对称加密算法,均可用于数字签名之中。
常见的有如下几种:
数字签名由于采用了非对称加密,因此可以防止否认。但发送方怎么能知道所收到的公钥就是接收方私钥所对应的公钥呢?如果不小心采用了攻击者的公钥,然后接收了攻击者私钥签名的信息,公私钥完全匹配,于是信息就被接受了,那么就 GG 了。
因此,业界便推出了证书。由权威机构颁布,认证公钥的合法性,那么就 OK 啦~
对数字签名所发布的公钥进行权威的认证,便是证书。证书可以有效地避免中间人攻击的问题。
PKC
:Public-Key Certificate,公钥证书,简称证书。 CA
:Certification Authority,认证机构。对证书进行管理,负责 1.生成密钥对、2. 注册公钥时对身份进行认证、3. 颁发证书、4. 作废证书。其中负责注册公钥和身份认证的,称为 RA(Registration Authority 注册机构) PKI
:Public-Key Infrastructure,公钥基础设施,是为了更高效地运用公钥而制定的一系列规范和规格的总称。比较著名的有PKCS(Public-Key Cryptography Standards,公钥密码标准,由 RSA 公司制定)、X.509
等。PKI 是由使用者、认证机构 CA、仓库(保存证书的数据库)组成。 CRL
:Certificate Revocation List 证书作废清单,是 CA 宣布作废的证书一览表,会带有 CA 的数字签名。一般由处理证书的软件更新 CRL 表,并查询证书是否有效。下图比较详细的阐述了证书的使用步骤
对于认证机构的公钥,可以由其它的认证机构施加数字签名,从而对认证机构的公钥进行验证,即生成一张认证机构的公钥证书,这样的关系可以迭代好几层,一直到最高一层的认证机构时该认证机构就称为根CA,根CA会对自己的公钥进行数字签名叫做自签名。