密码学(cryptography),源于希腊语kryptós“隐藏的”,和gráphein“书写”,是研究信息安全保密的学科,涉及密码编码与密码分析。密码学历史久远,它的起源可以追溯到几千年前的古埃及、古巴比伦、古罗马和古希腊。根据中国古代兵书《六韬》,我国更是早在周朝时期就出现了“阴符”和“阴书”两种保密方式。阴符就是事先制作一些长度不同的竹片,并约定每个长度的竹片代表的内容,如,三寸表示溃败,四寸表示将领阵亡,五寸表示请求增援,六寸表示坚守……一尺表示全歼敌军等。由于阴符传递的信息有限,后又出现了“阴书”,即把信息以明文写在竹简上,然后将竹简随机分为三份,由三名传令兵各执一份进行传递。收件人收齐后把三份“阴书”拼合起来,就可以得到完整内容了。
密码学的发展一般分为传统密码学和现代密码学两个阶段,分界标志就是1949年香农(C.E.Shannon)发表的经典论文《保密系统的通信理论》。在此之前几千年历史的传统密码阶段,密码主要采用代换(Substitution)和置换(Permutation)的方式来实现,仅是一种文字变换的艺术(创造性的方法)。香农通过将信息理论引入到密码学中,为密码学奠定了坚实的理论基础,形成了科学的密码学体系。
1.传统密码
1.1 古典密码
古典密码阶段从古代到19世纪末,长达上千年,主要采用代换及置换的方式,并通过手工或简单器械实现的。
(1)斯巴达棒
公元前约700年,古希腊的斯巴达人使用一种叫做scytale的棍子(斯巴达棒)来传递加密信息。斯巴达人在scytale螺旋形地缠绕一条羊皮纸。发信人在缠绕的羊皮纸上横着写下信息,然后将羊皮纸取下,这样羊皮纸上就是一些无意义的字符排列。收件人要解密这条信息,只需将羊皮纸再次缠绕在相同直径的棍棒上,就可以读出信件的内容了。斯巴达棒使用改变文本中字母的阅读顺序,即置换(换位)的方法达到加密的目的。
(2)棋盘密码
公元前2世纪,希腊人Polybius设计了一种将字母编码成符号的方法,称为棋盘密码。该密码通过Polybius矩阵进行加密,该矩阵是一个5*5的网格,通过Polybius矩阵将每个字母转换成两个数字,第一个数字是该字母的行数,第二个数字是该字母的列数。
\ | 1 | 2 | 3 | 4 | 5 |
1 | A | B | C | D | E |
2 | F | G | H | I/J | K |
3 | L | M | N | O | P |
4 | Q | R | S | T | U |
5 | V | W | X | Y | Z |
(3)凯撒密码
公元前约50年,罗马皇帝朱利尤斯·凯撒(Julius Caesar)发明了一种用于战时秘密通信的方法,后来称之为凯撒密码。他将字母按字母表的顺序构成一个字母序列链,然后将最后一个字母与第一个字母相连成环。凯撒加密的方法是将明文中的每个字母用其后的第k kk个字母代替。
1.2 近代密码
近代密码时期从20世纪初到20世纪50年代,工业革命为复杂密码的实现提供了先决条件,而战争对于保密通信的需求加速了密码技术的发展。这段时期,加解密一般通过机械或电动设备实现,虽然技术上有了很大进步,但并未形成理论体系,加密仍然依靠替代及置换的方式。典型的密码体制主要是单表代换密码(如仿射密码)、多表代换密码(如Vigenère 密码和Hill 密码等)。
(1)代换密码
代换密码是将明文中的字符替换为其他字符的密码体制。通过代换表(即密钥)将明文字符代换为对应的密文字符。代换密码分为单表代换和多表代换。单表代换密码,明文消息相同的字母,在加密时被统一固定字母代换;多表代换密码,明文消息的相同字母,在加密时根据其出现的位置不同,被不同的字母代换,可以隐藏单字母出现的统计特性。
(2)转轮密码机
20世纪20年代,随着机电技术的成熟,转轮密码机应运而生,极大促进了传统密码学的发展。转轮密码机是一种长周期的多表代换密码机,其核心是转轮加密算法,通过转的转动实现复杂的多表代换,打破明文与秘文之间固定的替代关系。转轮机由一个键盘和一系列转轮组成,每个转轮是26个英文字母的任意组合,转轮被齿轮连接起来。当一个转轮转动时,可以将一个字母转换为另一个字母,直至最后一个转轮处理完后就可得最终的加密后的字母。
世界上第一台转轮机在1918年由美国加州的EdwardHebern由一台打字机改造而成。随后,Edward Hebern设计出一系列的转轮机,并为美国海军采用,在长达50年左右时间成为美军主要密码设备。而历史上最著名的的转轮机莫过于德国人亚瑟·谢尔比乌斯(Arthur Scherbius)在1919年设计出的“谜”,即Enigma转轮机。
二战中的德军认为Enigma密码是不可破译的,但波兰人马里安·雷杰夫斯基(Marian Rejewski)通过密码分析实现了Enigma的部分破译,而以英国人阿兰·图灵(Alan Turing)为代表的科学家们,利用德国人的加密失误,并使用先进的译码计算机——图灵炸弹机(Turing Bomba)在1942年成功破解Enigma,可以说密码学的发展直接影响了二战的战局。
2.现代密码
1949年香农发表论文 《保密系统的通信理论》(Communication Theory of Secrecy System),标志着现代密码学的开端。香农将信息论引入到密码学研究中,利用概率统计的观点和熵的概念对信息源、密钥源、传输的密文和密码系统的安全性进行了数学描述和定量分析,并提出了对称码体制的模型,为现代密码学奠定了数学基础,这是密码学的第一次飞跃。
1976年,Diffie和Hell man 在《IEEE Transactions on Information Theory》发表的经典论文《密码学的新方向》(New Directions in Cryptography)提出了著名的公钥密码体制思想。在此之前所有密码系统均属于对称密码学范畴,密钥是不能公开的。而在公钥密码体制中,不仅加密算法本身可以公开,甚至加密用的密钥也可以像电话簿一样公开,任何用户向其他用户传送加密信息时,就可以从这本密钥簿中查到接收方公开的加密密钥,并用它来加密。接收方用户用他所独有的解密密钥得到明文,任何第三者因为没有解密密钥,无法获得明文。公钥密码体制的诞生为现代密码学的发展开辟了一个崭新的方向,带来了密码学的第二次飞跃。
1978年,美国麻省理工学院的Rivest、Shamir 和 Adleman提出RSA公钥密码体制。这是第一个成功的公钥密码体制,其安全性是基于数论中的大整数因子分解困难问题。
密码技术产生以来,直到二战结束,其主要应用军事、政府、外交等重要部门,相关研究也处于一种不公开的状态,充满着神秘感。随着信息技术的发展,尤其是互联网的广泛应用,使得密码学逐渐揭开了它的神秘面纱,走进寻常百姓的日常工作与生活。密码学不仅具有保证信息保密的功能,而且具有数字签名、身份验证、秘密共享、信息认证等功能,使用密码技术不仅可以保证信息的机密性,而且可以保证信息的完整性、不可否认性,防止信息被篡改、伪造、假冒、否认。
密码学已成为与数学、通信、电子、计算机、物理等领域相互联系、相互渗透的交叉学科。近年来,DNA密码、混沌密码和量子密码等新的密码技术都是受其他相关学科的发展所产生的。从密码学的发展历史可以看出,整个发展过程是从简单到复杂、从不完善到较为完善、从具有单一功能到具有多种功能的过程,符合人类对客观事物的认知规律。可以预见,随着密码学日新月异的发展,其必将在我们未来生活中扮演越来越重要的角色。