安全路透社
当前位置:安全路透社 > 网络转载 > 正文

字符编码发展史和密码算法那些事儿

原标题:《未然看码》

前记

从《易经》开始:

宇宙万物,道法阴阳,阴阳未分为混沌,混沌即无极,演而有序,化为太极。

易有太极,是生两仪,两仪生四象,四象演八卦,八卦演万物。

阴阳术创造了一个世界,炊烟袅袅,鸟语花香。

二进制创造了另一个世界,有一个小男孩,已经醒来。

0×01 编码的故事

ASCII

一个神秘组织为了融入人类的语言符号,将二进制的单元八位一组,建立了一套符号对应关系表(例如 A => 01000001),即 ascii 表,它是符号表的始祖。PS:标准 ascii 表的第一位都是 0,因此只有128 个字符。

一句话总结:所有编码的爸爸。

gb2312/gbk/gb18030

聪明的天朝人民也想融入自己的文字。由于标准 ascii 字符首位为 0,他们用两个首位为 1 的字节(我=> 1100111011010010)组合来表示汉字。为了庆祝这种机智的做法,命名为 gb2312;加入繁体字后,发现还是不够用。让后面一个字节的首位也可以为 0 ,这样又可以多编码一倍的汉字,这种方案叫 gbk;再后来,加入少数民族文字,就有了 gb18030。

天朝另一个小区域一直在用繁体字,他们发明了 Big5 汉字编码。

一句话总结:中国特色的编码。

Unicode

“你们不可能每个人都这么乱搞一套编码吧?你们互不相懂,唧唧歪歪,互相伤害,还能好好做朋友吗?”另一个神秘组织终于忍不住了,“你们不是嫌 ascii 编码不了你们的文字么?那简单,我用 2个字节,把全世界所有的符号都统一编码起来。”这样就出现了 Unicode。最初用 2 个字节想表示所有字符的方案,叫做 UCS-2,这样最多能表示 65536个字符。突然有一天,这位小哥发现 2 个字节根本不可能编码世界上所有的字符,就有了后面的 UCS-4,用 4 个字节来统一编码总够了吧……

一句话总结:别闹了都听哥的。

utf-7/8/16/32

这样编码是好,然而传输呢?按照 UCS-2 方案,所有字符都需要两个字节来传输,例如要发送一个A,就要发送 0000000001000001 这么多位,很浪费有木有?而且在实际传输中,数字和字母这样的字符占绝大多数。机智的人们又想搞事情了,引用哈弗曼编码的思想,出现频率越高的字符用更短的编码传输,频率低的字符就用多一点的编码传输。

utf-8,即每次传输 8 位一组。

所以发送 A,传输时一组就够了,实际传输 01000001。

而发送“汉”,则需要三组才行, 实际传输 111001101011000110001001。其中蓝色 8 位是 Unicode编码的第一个字节,绿色 8 位是第二个字节。

utf-7,utf-16,utf-32 也是一样的道理。utf-7 期初是用于电子邮件,邮件以字母为主,ascii 实质也是7 位一组。后面 16 和 32 这两种分组没有流行起来。

PS:utf-8 传输简体汉字时,是按照 3 个字节传输的,这就有了 utf-8  3 个字节这样的说法。实际上在 UCS-2 下 utf-8 传输字符,用 1-3 都是有可能的哦^_^

另外经常写和字符有关程序的小伙伴,一定有这样一个经验,想要让 gbk  utf-8互转,都是先要转到 Unicode 哦。

一句话总结:按频率传输,节省流量。

0×02 更少的编码

前面这一小段故事讲完了,我们先休息一下,马上进入更有意思的话题。

话说天下大势,分久必合,合久必分。字符的编码由简入繁,势必也会化繁为简。那么如何用更少的字符去表示所有编码呢?

Quoted-printable 编码

ascii 有 127 个字符,而且很多符号甚至是不可打印的,那怎么才能让他们都能显示呢?这个简单,对于不可打印字符,就用“=XX”表示,其中 XX 是该字符的 ascii 编码。例如换页符(ascii 为 0C),就可以表示成 =0C。只需要 =和0-F 这17个字符哦^_^

一句话总结:即使不可打印,也要可见。

Base64/32/16 编解码

Base 家族原理类似,就是用少量字符表示更多字符,但是也不像二进制那么少。Base64 即用64 个字符来表示所有ascii,怎么做到的呢?

大写字母集 W = {A,B,C…Z} 共 26 个

小写字母集 w = {a,b,c…z} 共 26 个

数字集 d = {0,1,2…9} 共 10 个

符号集 s = {+,/}

这 64 个字符对应数字 0-63,转化成二进制则是 6 位。而 ascii 是用 8 位,6 和 8 的最小公倍数是 24 = 3 * 8 = 4 * 6,所以将ascii 字符就能转化成base64 字符

ascii 的 ABC-> 010000010100001001000011 ->010000 010100001001000011 ->QUJD

同理 base32 是用 32 个字符即 5 位表示,5 * 8 = 8 * 5,所以 base32 会把 5 个 ascii 字符变成 8 字符哦。

PS:如果字符数不是3 的倍数,怎么办?看一下操作你就知道了。

A -> 01000001-> 01000001 0000-> QQ== 所以你会看到 base64 串后面有1或2个=

另外有些不专业的销售,会说他们的产品是用 base64 加密的,客户就会立刻质疑他的产品!base64只是一种编码,它的实质还是明文,你说用它来加密,不是掩耳盗铃??

另外依照这种理论,那么我们的二进制是不是可以理解成 base2?ascii 就是 base128 嘛。

一句话总结:用我们常用的字符表示所有字符。

XX 编码,UU 编码

它们实质跟 base64 是一样的,也是用 64 个字符来表示,只是选取的字符和编排方式不同罢了,其实它们才是base64 的前身,慢慢演进,渐渐被base64 取代了。

一句话总结:长江后浪推前浪。

URL,HTML 编码

URL编码

采用“%+ascii”的方式对字符进行编码,比如:

http://www.wr.com?file=../../passwd -> http://www.wr.com?file=%2e%2e%2f%2e%2e%2fpasswd

HTML编码

采用“&#+十进制数字”或“&#x+十六进制数字”的方式对字符进行编码,比如:

<p>ab</p> -> <p>ac</p>

一句话总结:新瓶装旧酒。

说了这么多,下面画个编码家族的家谱图:

编码家谱图.png

0×03 古典密码

从这些编解码演化的过程中,相信各位看官也会感受到劳动人民的智慧。前面的只是热身,下面将进入今天的重头戏,密码学。

还是回到开头那句话,任何一种思想或者想法,都一定是为了解决实际问题而设计的。字符编码的故事,是为了解决字符的表示、显示和传输的问题。那么密码学是为了啥子呢?

相信 BobAlice   Ted  斗智斗勇的故事大家都看过,没有看过的可以百度一下,挺有意思的。数据传输的安全性包括以下三个性质:

机密性:数据被偷了,小偷不知道是啥。

完整性:数据被改了,接受方能够发现。

可用性:纯属废话,不能用还要你何用?

下面主要介绍密码学在前两条性质中的作用。

先来几个不算是密码的密码算法。为啥这样说呢,因为这些算法刚发明时,别人不知道是怎么计算的,因此无法根据“密文”还原出原来的信息,可以算作加密。后来被普及了,大家就都会算了,这时候你还说你加密了,你是不是当我傻?

凯撒密码

引用一句话 I came,I saw, I conquered. 多么霸气啊。这个以帝国霸主名字命名的密码学确实如此朴素。凯撒密码有两种模式:

(1)位移密码,就是讲明文每位都移动特定位数,例如 AbC 右移 4 位就变成 Efg.

那么我(I)想对你说:M pszi csy.

(2)查表密码,指定一张明文和密文对应的关系表,然后对着这个表进行加解密。例如:

明文与密文对照表.png

Hello加密之后就变成 Axeeh,那么Ixkyxvm.

维吉尼亚密码

我理解它是一种升级版的凯撒密码,它引入一张 26*26 的密码表盘,可以设定一个密钥,然后按照查表的方式进行加解密。由于操作简单,不过多叙述。

ROT5/13/18/47

ROT13 就是右移 13 位的凯撒密码,后面的数字是移动位数,这种加密方法不限定在数字或字母上,也可以拓展到所有 ascii。

摩尔斯密码

.. … – .. .-.. .-.. .-.. — …- . -.—– ..-

当铺密码

这种密码感觉还是很有意思的,就是看汉字露出的笔画数,决定这个数字是几,例如“十”,上下左右四处漏出,所有他就是数字 4 。

告诉你一句表白:大中口由人甲工

猪圈密码,栅栏密码等,其原理差不多,就是通过一张事先约定好的密码表,然后将明文进行查表加解密

PS :这些密码算法实现简单,只是对原始字符做了一种替换编码,想到即解决。因此这些算法深受考脑洞的 CTF 赛友的青睐,也只适合出现在比赛和游戏中。

 0×04 现代密码算法

好了终于把这一段朴素的古典密码啰嗦完了,下面这一段介绍现代密码学。还是从机密性和完整性这两条性质展开,来介绍一下密码学算法是如何解决这些问题的。

先来说说机密性,密码学的机密性算法,都是含有密钥的理论上来讲,一份数据在网络上传播,被谁获取都是有可能的,如果它的主人只希望“对的人”才能理解它,所以必须有密钥机制才能保障。

含有密钥的加密算法有两类,对称加密和非对称加密。

对称加密算法

加解密的双方使用同一个密钥,一般是加解密双方以一种不可告人的方式偷偷约定好一个密钥。所有需要传递的消息都用这个密钥加密成暗号,接收方用这个密钥解密得到原始消息。

目前的对称加密有“流加密”和“分组加密”。

流密码算法:将明文按字符逐位(逐比特)地、对应地进行加密的一类对称密码算法。

分组密码算法:将明文分成固定长度的分组,如64bit 或 128bit 一组,用同一密钥和算法对每一个分组加密,输出也是固定长度的密文。

流加密算法相对简单,你可以把明文串和密钥串看成两条长长的水管,遇到对齐的位就做一个约定好的运算。目前有代表性的算法有RC4和 GSM。

举个栗子,一个异或的流加密过程如下:

异或的流加密过程.png

 知道了加密过程,解密也自然思路清晰:

解密过程.png

由于流加密原理简单,其算法结构存在着弱点,另外密钥流有一般会多次重用,泄露局部的明文就可能让攻击者嗅探出密钥。另外,由于流加密是按位进行加密的,攻击者如果只是修改了密文中几个bit,不会破坏原消息的结构,这样接受者就会接受错误的信息。

PS :目前所有的流机密算法,都被认为是不安全的,重要消息不要用流加密哦^_^

分组加密算法内部实现复杂,每一块加密,都有几十轮运算,这里我不打算过多地介绍其实现过程。其代表算法有DES  AES

目前 DES 已经被证明是不安全的,但是 3 重 DES 当三次的密钥都不相等时,是安全的。AES 密钥长度在 128 以上的算法,目前都是安全的

分组模式其实还有很多,我主要介绍一下 ECB 和 CBC 模式。

ECB 模式:每组是独立和密钥进行运算的:

ECB分组模式.png

CBC 模式:每组先和上一组密文运算后,再跟密钥运算:

CBC分组模式.png

我们拍拍脑袋想想就知道CBC 模式更加安全,因此强烈建议使用 CBC 模式,下面再来张图,看看两种模式加密之后的效果:

加密结果.png

一句话总结:对称加密就是用同一把密钥进行加解密。 

非对称加密算法

座山雕:天王盖地虎!

杨子荣:宝塔镇河妖!

众金刚:么哈?么哈?

杨子荣:正晌午时说话,谁也没有家!

座山雕:脸红什么?

杨子荣:精神焕发!

座山雕:怎么又黄啦?

众匪持刀枪逼近杨子荣。

杨子荣(镇静地):哈哈哈哈!防冷涂的蜡!

这个故事就用到了多组非对称密钥,环环相扣,一组密钥错误,就会丢了小命。

非对称加密相比对称加密就都要复杂的多,虽然对称加密背后也有一套数学理论,但是非对称加密背后的数学理论就更加深厚。小编不才,只能请了一个密码学专业的童鞋用一句描述了两个算法背后的数学难题:

RSA:大数分解问题。

ECC:椭圆曲线上的离散对数问题。

言多必失,为了不误导大家,我就不分析具体算法了。我只讲讲这两个算法的效果。

经过一系列复杂运算后,非对称密码算法会产生一对密钥:

公钥:一般较短,可以公开。

私钥:一般较长,作者保留。

这两个密钥有如下性质:

(1)       公钥和私钥都能进行加密和解密。

(2)       用公钥加密后的内容,只有用对应的私钥才能解开。

(3)       用私钥加密后的内容,也只有用对应的公钥才能解开。

(4)       以上三条其实都是废话。

除了用在加解密用来保证数据的机密性,那么这种非对称密码算法,还有什么作用呢?

签名:用私钥加密一条消息发出去,证明是我。

数字证书(CA:将签名和公钥一起打包发出去,任何人都可以通过公钥解密签名的方式来证明是我。

PS :一般非对称加密算法速度慢,对于大文件或长消息的加密都用对称加密

一句话总结:非对称加密有两把不同的钥匙哦。

哈希算法

以上加密算法,主要是保证消息的机密性,那如果消息被修改了,该怎么办呢?

下面再介绍几个算法,使得消息一旦被篡改,接受者就能察觉到。

这时你可能会想到几个名词:

消息摘要,数字指纹,单向散列

额,他们的实质都是一样的,他们用到的技术,都是密码学中的 Hash 算法。Hash 算法有以下几个美好的特性:

(1)       固定长:不管你输入多长,输出都是固定的,而且很短

(2)       唯一性:对于不同的输入,基本可以认为输出是不同的

(3)       不可逆:正向运算可行,反向运算不可能

上面这些名词只是对 Hash算法某个特性的偏重。消息摘要,就是利用固定长的性质;数字指纹用到的是唯一性,单向散列则用到不可逆性。不管一个人长得啥样,都可以用一个小小的指纹来代表他,消息的摘要也是一样,这就是 Hash 算法的魅力。目前用的最多的hash 算法是 MD5,SHA-1 和 SHA-2。

尽管 MD5  SHA-1 已经被碰撞了,证明是不安全的,但是这几年他们还不会消失;SHA-2 其实不是某一种算法,它是一个大家族, SHA224/256/384/512 全部属于 SHA-2。当你下载软件时,是不是经常会看到以下信息?它们就是该软件的指纹。

MD5 指纹:

MD5 指纹.png

SHA-1 指纹:

SHA-1 指纹.png

SHA-2 指纹:

SHA-2 指纹.png

Hash 算法里的“唯一性”并不是真正唯一的,找到两条不同的消息,使得他们有相同的指纹,叫做碰撞。Hash 算法之所以管用,是因为它们碰撞的概率极低的。现在的科技也说明人类的指纹也存在碰撞,所以要引入虹膜。其实虹膜也存在碰撞,只是它碰撞的概率比指纹要更低。

Hash 算法里的“不可逆”是真正的不可逆。从算法本身的数学原理来讲,通过 Hash 值来直接倒推原始输入,是不可能的。要分清两个概念,碰撞和可逆是不一样的哦。既然不可逆,那么我们有没有方法来复原明文呢?

方法有是有,不过这是概率性的,就跟之前一些公司宣传“概率性”恢复被加密的文件是一个概念,下面我介绍完,大家自然就明白“概率性”是啥意思了。

第一种方案是爆破,通过循环来构造不同字符的组合,然后正向计算 Hash 值,如果发现跟目标值一样,就认为找到了。这种方法对于那些简单且很短字符串 Hash 值的爆破是非常有效的,因此设置密码要长一点,且多弄几种奇奇怪怪的字符哦。

另一种方案就是彩虹表,它的实质跟第一种方案是一样的。它会实现计算好很多“常规”字符串的Hash 值,然后建立一张很大的表把它们存起来,这种表就叫做“彩虹表”,对于要破解的目标值,只需要查一下表就可以了。它的特点是速度快,有则有,无则无,不啰嗦,不挣扎。

那么怎么应对这些蛮不讲理的破解呢?还是有两种方法,我只说说它们是怎么做的,相信大家就知道防爆破的原理了。

加盐:计算 Hash 值时,加入一个随机数,叫做盐值。

PBKDF2迭代多来几轮 Hash ,味道不好也可以加点盐。

当然为了防止被消息被篡改,还有一部分较弱的校验算法,它们一般把校验码直接放到消息中,它们的保护能力很弱,攻击者只需要跟着把校验位修改,即可绕过

Luhn 校验算法

我们知道,公民的身份证是18 位,而最后一位就是校验位。喜欢玩游戏的小伙伴一定都有这样的经历,游戏需要实名认证,而有时候也不想泄露自己的身份证信息。有时候就会随便输入一个身份证,系统就能马上判断出你的身份证是无效的。怎么做到的呢?

把前 17 位分别乘上以下系数,然后相加:

校验系数.png

然后把相加的结果模除 11,得到的余数只可能是0-10。余数再按照下表做一次变换,就可以得到最后一位:

校验结果.png

当余数是2时,经过上面变换后就是X,这也说明了为什么有些人的身份证最后一位是 X。如果当时是模除 10,是不是就能避免出现 X 这样的数字了呢^_^

一些银行卡、社保卡等也都是用的 Luhn算法,只是系数表不一样而已。

CRC 校验(BCC,LRC

当然身份证校验码相对简单,系数也都是固定的。CRC 校验码原理其实也相似,只是去乘以一个多项式而已,在此就不过多叙述。

一句话总结:你可以改,但我也可以拒收。

MAC 算法(带密钥的摘要算法)

看到这里,消息的机密性和完整性,也算是差不多说完了。聪明的小伙伴可能会有这样的想法:如果攻击者在修改了密文消息的同时,把后面的消息摘要也相应修改了。那么接受方是不是还是无法判断?

没错,想法很好,实际这种做法之前就发生了,为了解决这个问题,就又要引入下一个更加牛逼的完整性算法。有问题就总有对策,技术就是在解决问题的基础上发展的。

回忆一下我们怎么保证机密性的?就是通过密钥嘛。那么我在做消息摘要时,也带上一个密钥,这样攻击者就没办法修改消息摘要了嘛。基于这种思想实现的算法,就是MAC 算法。当然,如果其中的摘要算法是用 Hash 函数实现的,那么就叫 HMAC 啦。 HMAC 算法一般是采用对称密钥,事先约定好。至于摘要那种算法倒是可选的,所有就有了 HMAC-MD5,HMAC-SHA1 等等。

一句话总结:密钥 + 指纹,更安全。

DH,ECDH(密钥协商算法)

最后一个问题了,说到消息传输,可以用密钥来加密,那么问题来了,密钥怎么传输呢?你可能会想到用另一个密钥加密,那么另一个密钥怎么传输呢?如果是周围的朋友,你可以直接去他家里,然后告诉他。既然你都可以去他家里了,消息你也可以直接告诉他,干嘛还要通过网络呢,呵呵。

所以最后一个算法是关于密钥协商的,这跟密钥传输还不是一个概念。

以前看了一篇小说,里面有个情节:在一个小玻璃瓶里,有一根比瓶口粗得多的树干,大家都不明白这根树干是怎么放进去的。小伙伴也可以想想哦。

其实在刚开始的时候,在玻璃瓶里种了一棵树种子,里面有水有土壤,种子就一直在玻璃瓶里生长。当它长出树枝时,小主人就把剪刀伸入瓶口剪掉树枝,移出瓶外。就这样当树干长到一定粗度,小主人就倒出水和土壤,让树木干死。就形成了如今这个局。这是一篇不错的推理小说,这个谜的原理就跟我们今天的主角 DH 算法有点类似。DH 算法并非事先产生一个密钥,而是在双方的对话中,根据对方的信息,来生成密钥。密钥期初是一棵种子,在双方的交互中不断生长。即使攻击者收集了双方所有的对话内容,也无法知道密钥是啥

通过两个人说一堆奇奇怪怪的话,然后密钥就在这些奇怪的暗语中产生了,怎么做到的呢?

一次密钥协商,涉及到 2 个人和 7  个数据

人物:男主角1,女主角2

公开数据:质数a,质数p,y1,y2

私密数据:x1x2

密钥:Key

场景1

质数 a,p 是公开的,可以随便确定,p 需要是大质数。

场景2

然后男1和女2 各想一个幸运数字 x1和x2。

男1计算 y1 = a^x1 mod p,并把 y1 告诉女2;

女2计算 y2 = a^x2 mod p,并把 y2 告诉男1;

场景3

男1计算 Key = y2^x1 mod p

女2计算 Key = y1^x2 mod p

下面简单证明一下男1计算得到 Key1 和女2计算得到的 Key2 是相等的。

Key1 =y2^x1 mod p = (a^x2)^x1 mod p = a^(x2*x1)mod p

Key2 = y1^x2mod p = (a^x1)^x2 mod p = a^(x1*x2) mod p:

这个算法的神奇之处在于,即使对方也无法知道自己手里的幸运数字,但能计算出共同的密钥。它的数学原理是基于离散对数问题和求模公式,也涉及到一些质数的性质。

ECDH 算法就是将 ECC 算法和 DH 算法一起使用协商密钥。

一句话总结:谈笑间,密钥应运而生。

加密的最佳实践—信封加密:

信封加密.png

将对称密钥加密后放到消息中,一起发生。是不是与 WannaCry 勒索病毒加密方式类似?

0×05 结语

终于可以长吁一口气了,辛苦各位看官了。下面总结一下都讲了啥:

(1)编码的故事讲了字符编码的发展史

ASCII捏造了常规字符;

gb系列融入了汉字;

Unicode统一编码;

UTF进行省流量传输;

XXUUBase定义更少字符编码

(2)密码学系列介绍了密码算法的作用:

古典密码算法思路简单,以查表加解密为主,安全性弱。

现代密码学旨在保证数据的机密性完整性

机密性算法涉及到密钥,对称首选AES,非对称有RSA和 ECC

完整性算法优选是哈希,定长唯一不可逆,MD5SHA-1不安全,SHA-2家族杠杠的。

校验算法计算简单,校验位存留在信息自身,Luhn和 CRC应用广泛。

为防止数字指纹被修改,引入带密钥的哈希算法HMAC,带密码的指纹更安全。

高冷的简短的对话,密钥应运而生,密钥协商我只认DH

文中若有不足之处,请大家斧正。如果想和作者交流,请关注我们的微信公众号WeiRanLabs或通过电子邮件与我们联系,邮箱地址weiran.labs@huawei.com

*本文作者:华为未然实验室

未经允许不得转载:安全路透社 » 字符编码发展史和密码算法那些事儿

赞 (1)
分享到:更多 ()

评论 0

评论前必须登录!

登陆 注册