0rj
0rj
8天前 · 6 人阅读

1.计算机出现以前的密码

这篇文章旨在浅显易懂的介绍标题所述的各个算法概念与应用,文中没有数学公式。在主要概念出现之前,先简谈一下密码发展史的几个重要时期。

计算机出现之前,加密算法主要有“替换加密”,“移位加密”,“维吉尼亚密码”等。

著名的凯撒密码就是最简单的“替换加密”,密文每个字母相对原文向后移动3位,例如:

ATTACK AT THREE AM TOMORROW

加密后就变成了

DWWDFN DW WKUHH DP WRPRUURZ

复杂的替换加密会将26个字母都替换成另一个不同字母。解密时需要知道加密进行的操作,即字母是如何替换的。在这里,字母替换表称为密钥,可能的替换方案越多,密钥空间越大,则越不易被破解,对于26个字母,不重复的替代方案有26! 大约4×1026种!

替换加密尽管有很大的密钥空间,但存在一个致命弱点:一种语言中每个字母出现的频率是固定的。例如英语中e是最常见的字母,如果使用替换加密,那密文里最常见的字母很可能原文就是e!此外,单词首字母频率最高的是t;th,he,in等组合字母出现次数也要比其他字母组合频繁的多。所以当时经验丰富的密码师可以很容易破译这类加密。1587年,苏格兰玛丽女王使用这种方法加密“暗杀英格兰伊丽莎白女王计划”,但不幸内容被破译引来处刑。

二战时期德军著名密码机“谜团”(Enigma)将“替换加密”发展到极致,是计算机出现前最复杂的加密方式。这种机器类似打字机,敲入明文可以直接显示密文(通过亮灯);反之,如果知道密钥能正确连线和摆放转轮,敲入密文也可以直接还原明文。Enigma的复杂之处在于机器上的3-4个转轮,每输入一个字母,其中一个转轮就会旋转一格,类似汽车里程表。当转动一圈后,第二个转轮会转动一格,第二个转轮转动一圈后,第三个转轮再转动一格。而替换方案由全部转轮的位置来决定。这表示,虽然本质仍是替换加密,但替换方案是变化的。原文中出现第一个e和第二个e加密后不一定相同。但即使是这样,对岸的英国破译小组,在几百个数学家努力下(其中包括计算机之父--艾伦·图灵),仍然破译了大量密码,从而提前结束了战争。

二战德军4转轮谜团机,图片来源于wikipedia

2.编码(Hex,Base64,Urlencode)

这些算法不能算作加密,只能称之为“编码”。因为编码和解码算法都是公开一致的,编码后的文本只是人类不熟悉的计算机语言而已。

计算机出现后,信息保存在磁盘中。由于计算机只能识别二进制0和1,需要制定一套方案用来保存文字信息。ASCII码表,雏形形成于1963年,用7 bit,一共27=128种编码表示数字,英文,和标点符号,随后扩展到8 bit,新增了ä, ö, ü, ß等西欧字符。早期IBM推崇的1字节=8 bit 概念此时已经根深蒂固,因为对大部分欧美国家,1字节就是1个字母或1个标点。

对非英语国家,如中国,在1980颁布GB2312编码规格,用两字节216=65535种编码,表示七千多个简体字和字符。1995年又颁布了GBK,在兼容前者基础上,新增了繁体字和部分日韩文字。

世界上常用的几十种语言,如果每个国家都有一套自己的编码方案,跨国通信是很困难的,这时Unicode出现。Unicode选择4字节 232=4294967296 这么多种编码,足够保存世界上所有语言还绰绰有余。四字节直接保存的结果是UTF-32,名称源于4字节=32 bit。虽然编码统一问题解决了,但这对于大部分英语国家而言是极其浪费空间的。本来人家1个字母1字节就够,现在要扩大到4倍!于是又有了UTF-8,可以理解为UTF-8是Unicode存储时压缩后的“可变长”编码。英语部分不变,UTF-8完全兼容ASCII;非英语字符占2-4个字符,达到了统一与节省的平衡。

二进制01序列为了表示方便,书写时通常选择16进制,即Hex。

以中文为例,“你好”在经过utf-8编码后是,

二进制111001001011110110100000111001011010010110111101
Hexe4bda0e5a5bd

由于图片,文件等格式的二进制文件源码无法转为字符串(ASCII包含了大量不可见字符),直接用Hex与原文件相比又整整多占用一倍空间!因为Hex仅仅用到了数字0到9,字母abcdef(不区分大小写)加起来才16个,浪费了大量可视字符。 Base64编码算的上是“折衷”方案,它模仿ASCII,用到的字符有:全字母大小写52个,数字0到9,外加+和/ 两个符号。

二进制111001001011110110100000111001011010010110111101
Base645L2g5aW9

Base64相比Hex,实际只是将二进制流从4 bit分组,变为6 bit分组。26=64,即6 bit选择64个符号来表示,这就是Base64名字的由来,Hex也可以被称为Base16。

1字节= 8 bit,3字节 = 24 bit = 4个Base64字符,这意味着Base64只能对3的整数倍字节数进行编码,如果字节数不是3的倍数,会通过在末尾补一或两个全0字节使其变成3的倍数,并在密文后加同样数量的“=”,解码时侯,末尾有几个“=”,就需要在解码后末尾原文去掉几个全0字节

同样是中文“你好”,在GBK编码规则下:

二进制11000100111000111011101011000011
Hexc4e3bac3

上面 4 Byte不能被3整除,需要补2个全0字节,即 0 × 16 bit

二进制110001001110001110111010110000110000000000000000
Base64xOO6ww==

Base64的出现实现了任何二进制流到可视字符串的转换,进而方便添加进XML,JSON这类数据格式中。对于不需要可视的文件,完全可以直接通过Stream的方式传输。毕竟原来的3字节现在要用4个字符表示,字符传递时仍占一字节,这导致Base64编码后,所占空间将增大4/3倍。

上面也看出,一个汉字在utf8中通常占3字节,在gbk中占2字节,这使得不少中国企业当初选择数据库编码时选择了gbk,但如今硬盘越来越便宜,国际化却越来越重要。由于utf8可以正确处理全球语言,▲ ★ 甚至包括Emoji

收藏 0
评论