《应用密码学》第1章笔记

时隔一本《失控》和一本《阐释并守护世界意义的人》,我终于又开始看IT技术书,但这次看的不再是“工程”,而是更为底层(却不像数学那般底层)的《应用密码学》。这一章是基础知识,依旧是边撕边看,所以前半部分有些丢了记不得就算了。

对称算法 vs. 非对称算法

这几页丢了,又一直耿耿于怀,找了篇博文温习《对称加密与非对称加密

对称加密是最快速、最简单的一种加密方式,加密(encryption)与解密(decryption)用的是同样的密钥(secret key)。对称加密有很多种算法,由于它效率很高,所以被广泛使用在很多加密协议的核心当中。”

“所谓对称密钥算法是指如果一个加密算法的加密密钥和解密密钥相同,或者虽然不相同,但是可由其中的任意一个很容易的推导出另一个,即密钥是双方共享的。”

简单异或

异或(XOR)在C语言中是“^”运算:

0^0 = 0
0^1 = 1
1^0 = 1
1^1 = 0
a^a = 0
a^b^b = a (即有结合律)

简单异或的算法变种

“简单异或算法实际上并不复杂,因为他并不比维吉尼亚密码复杂。本书讨论他,因为他在商业软件包中很流行,至少在MS-DOS和Macintosh世界中是这样。不幸的是,如果一个软件保密程序宣称他有一个‘专有’加密算法(该算法比DES更快),其优势在于是下述算法的一个变种。”

/* Usage: crypto key input_file ouput_file */

void main (int argc, char *argv[])
{
    FILE *fi, *fo;
    char *cp;
    int c;
/* C语言语法忘得差不多了,但这段代码的意思大概是对输入的信息0-1进行异或 */
/* 加密与解密是同一套机制,所以是对称算法 */
/* 即一个东西异或两遍等于自身:a^b^b = a */
    if ((cp = argv[1]) && *cp!='\0') {
        if ((fi = fopen(argv[2], "rb")) != NULL) {
            if ((fo = fopen(argv[3], "wb")) != NULL) {
                while ((c = getc(fi)) != EOF) {
                    if (!*cp) cp = argv[1];
                    c ^= *(cp++);
                    putc(c,fo);
                }
                fclose(fo);
            }
            fclose(fi);
        }
    }
}

破解方法简记(以后有空研究):
1. 重合码计数法(counting coincidence)找出重合指数(index of coincidence)大于6%的??
2. 移动密文与自身进行异或,直到得出的明文可读即可。

大数

书中使用了“大数”去描述密码算法中的不同内容,给出了一个表来让读者理解其意义,比如每年淹死的可能性为2**15之一。

加密方法

有很多方式,但是前面的书页扔了,所以只记得以下几点:

  • 隐写术(steganography)
  • 模拟函数(mimic function)
  • 简单代替密码(simple substitution cipher) == 单字母密码(monoalphabetic cipher)
    如著名的Caesar密码,每个字母由右边第三个字母代替。
  • 多名码代替密码(homophonic substitution cipher)

  • 多字母代替密码(polygram substitution cipher)
  • 多表代替密码(polyalphabetic substitution cipher)
    跟简单代替密码一样,只不过每个字母的加密表不同,比如有5张密码表,对每个index mod 5的字母进行相应的加密。

  • 滚动密钥密码(running-key cipher,书本密码)

  • 换位密码
  • 轮转机(rotor machine)
    “最著名的轮转装置是恩尼格玛(Enigma),它在第二次世界大战期间由德国人使用。其基本原理由欧洲的Arthur Scherbius和Arvid Gerhard Damm发明,Arthur Scherbius在美国申请了专利。德国人大大加强了其基本设计。在第二次世界大战期间,由波兰密码小组最早破译(并不是传说中的阿兰-图灵!!),并告诉了英国人。

攻击方式

加密方法,只记得如下:

  • 选择密钥攻击
  • 选择明文攻击
  • 选择密文攻击(选择文本攻击 chosen-text attack)
    之所以有选择明文和选择密文攻击,是因为有些加密方法的加密密钥和解密密钥不一样,两种攻击得到的密钥也是相应不一样的。但是在对称的算法里,两者获得的结果就一样了。
  • 唯明文攻击?

  • 唯密文攻击?
  • 软磨硬泡攻击(rubber-hose cryptanalysis) == 购买密钥攻击(purchase-key attack)

算法的安全性

计算机的加密算法不能依赖于“别人不知道加密方法”,因为这样只要一个组织(公司)中有一个人离职,那么此算法就可能被泄露出去,或者就得整个企业换算法,这样的代价是很大的。所以最好的加密算法是那些经过世界上最聪明的密码分析专家分析后,还无法被破解(或者说有生之年无法被破解)的算法。

Lars Knudsen把破译算法分为不同的类别,安全性递减顺序为:

  • 全部破译 total break (找出密钥)
  • 全盘推导 global deduction (找到代替算法)
  • 实例(局部)推导 instance (local) deduction (从部分密文中找出明文)
  • 信息推导 information deduction (获取出密文的一些信息)

无条件保密 unconditionally secure: 不论密码分析者有多少密文,都没有足够的信息恢复出明文。只有一次一密乱码本不可破(前苏联间谍用的方法,若其密码本已经销毁,则其加密信息现在不可能破译出来,即使破译出来也无法确定就是当时想传达的意思。),其他都可被蛮力破解。

蛮力攻击 brute-force attack: 在唯密文攻击中都是可破的,只要简单地一个接一个地去尝试每种可能的密钥,并且检查所得明文是否有意义。

密码学更关心在计算上不可破译的密码系统,可以用不同方式衡量攻击方法的复杂性:

  • 数据复杂性 data complexity
  • 处理复杂性 processing complexity — 工作因素 work factor
  • 存储需求 storage requirement — 一般存储需求越大,攻击可能越快

计算机算法

  • 数据加密标准(Data Encryption Standard,DES)
    美国和国际标准,对称算法,加密和解密的密钥相同。
  • RSA(根据发明者命名:Rivest、Shamir、Adleman)
    最流行的公开密钥算法,用作加密和数字签名。非对称。

  • 数字签名算法(Digital Signature Algorithm,DSA)
    公开密钥算法,不能加密,只能用于数字签名。

进一步的读物

除了这一本导论式的书之外,想再进一步就是自己研究+逛社区+读文献了。