这节课的难度有点大,一开始听得是一头雾水啊,很多专有名字。

上来就是讲了考核内容,实验等等。考核内容,还是一上来第一篇critical report,四选一的话题,开头结尾500字,中间 critical 1000字,discussion1000字。

然后四个实验,每个实验10分。

最后一个考试,价值20分。

那么知道了考核内容,就要知道所有的专业术语。

Key 密钥:由数字和字母甚至符号组成。也就是所谓的密码,但是一般都不用password来称呼,因为很容易混淆,我们之后默认都是用key

Plaintext,明文:也就是没有加密的文本 unencrypted text

Ciphertext,密文或者密码文本:就是加密后的文本 encrypted text

Algorithm,算法:也就是加密的方法或者步骤 the steps used to encrypt text and to decrypt text

Symmetric,对称的,匀称的:也就是加密和解密都使用一样的key,这里注意对称不是字面意思,加密key是1234,解密是4321,不是这样的,加密解密都是1234.

Symmetric encryption, Symmetric key则是延伸概念。

Asymmetric encryption 非对称加密:和上面对称的相反,这里需要公钥和密钥,public key & Private key,即加密用一个key,解密另外一个key。

敲诈勒索软件就是典型的非对称加密。

Keyspace 密码空间:即可能的密码的数量或者可能是密码的总量。举例来说,一个门禁,可以输入0-9,然后四位数的密码。密码空间是多少?10 * 10 * 10 * 10 = 10000

Cryptography 密码术:即研究加密理论和实操

Cryptanalysis 密码分析学或者密码翻译学:即密码破解,在不知道key的情况下去破解

Cryptology 密码学:就是上述两门的综合。

密码学或者密码术的目的是啥:

Confidentiality 保密 机密:保证信息的私密性,只有授权人才可以查看该信息。

这个单词从confident 可以发展为confidential 就有了秘密的 机密的 可信赖的意思,然后继续变成名词或者副词。

Data integrity 数据的完整性:确保信息收到的和发出去的是一样的,不能被篡改。

Authentication 验证或者鉴定:可以鉴定该信息是由谁发出的,发出了什么

Non repudiation 不可否认性:防止某人拒绝承认发送了什么信息

然后整张图没看懂啥意思,primitive(原始的,基元的)

然后开始讲一些基础,

比如helloworld 加密后变成了 ifmmpxpsme,这个就是把每一个字母向右平移一位的算法。这样别人看到了这个就不知道你发了什么。这种称之为以下两个名字。

Classical Substitution(替换) Ciphers

Caesar Cipher 凯撒密码

原理就是把字母向右平移, 由于字母的限制,因此最多26(25)种可能性。那么强制破解的原理就是尝试每一种,最多25次就得到了结果。这里其实应该是25种,因为A平移了26次还是A。
c = E(k, p ) = (p + k) mod (26)
p = D(k, c) = (c – k ) mod (26)

如果我们知道了算法或者Key,破解这个是轻而易举的。trivial 不重要的,琐碎的

这里讲了一战和二战的英军和德军的密码破解案例。

第二种介绍的算法是异或算法,一般这种算法用于扩展加密解密,或者二次加密解密。

XOR 或者符号是一个圈圈中间一个十字。

那么方法是将未加密的text转为二进制,然后key也是二进制,然后使用XOR相加

比如Hello 在ACSII 就是 72 101 108 108 111,然后转为二进制是

01001000 01100101 01101100 01101100 01101111

然后key选择为00110110,然后叠加,两个1或者两个0等于0,而一个1一个0等于1. 还是以H为例,

01001000 XOR 00110110 = 01111110 in binary = 126 in Decim = ~ in ACSII

同理可以把其他的ello转换,Hello就变成了~SZZY

反过来破解也一样。

但是这个算法的缺点也一样很明显,一旦重复的字母够多,那么也容易被发现key。为了加强难度,这个算法进一步发展,把字母分成一组一组的,比如五个字母一组,不足的用某个字母比如F补齐,比如

heyei osllb epago effff

但是只要重复的够多,其实还是可以破解。这里举了一个例子是二战美军 intercept (截获)了一条信息,AF is about to be attacked。其实美军部分破解了日军的purple密码,然后猜测AF是某个岛屿,因此发送了一条假消息,然后得到了日军回复,因此也确定了信息。

Type of encryption technique

包括刚才讲的,substitution 替换, transposition 转换等等

还有使用单个key symmetric 算法或者两个key asymmetric 算法

加密明文的方式也分为block块式或者stream 流式,流式用于流媒体比如音视频。

Type of attack

cryptanalytic 密码分析学:就是攻击破解算法,比如根据现有的密文,统计大量的重复信息。或者已知密文和明文,然后对比两者找出算法。

那么一般来说有两种情况, unconditional security和conditional security

无条件安全就是就算有无限的电脑和时间也无法破解,因为没有足够的信息

有条件安全就是在有限的电脑下,需要大量的时间才能破解,可能多少多少亿年

Brute force 暴力破解:就是从第一个开始,一个一个尝试

直到算法或者key的改变,临时key可能很脆弱

暴力破解最运气好的情况就是第一个密码就对,最差就是尝试到最后一个,而average则是尝试了一半。不过这个不是数学意义上的一半。只要记住average就是一半

Kerckhoff’s Principle:加密方案的security 安全性是key management,而不是 secrecy 保密性 of the algorithm。

比如下面的例子,即使是最难得加密方式,假如key是一堆0,依然是一上来就被破解,所以精选key很重要

接下来的话题是算法是否应该被公开,这个要看情况,比如前面讲过的几个算法非常简单,一旦公开后所有人就知道算法的工作原理,那么就可以轻松的破解。但是像比较复杂的算法,公开后即使大家知道原理也依然无法破解或者需要大量时间。

PC运算速度越来越快,可能过去的某些算法很强大,但是在计算机面前不堪一击。那么假如不用英语加密,而是使用其他语言,那么无疑安全性又会提高。

monoalphabetic cipher 单字母跳跃加密:假如key有26位长,每一个字母都可能跳跃1-25次中的一个可能性,那么该key最多的可能性就是26的阶乘,factorial 阶乘 公式就是N * (N-1)*(N-2)… *1

一共是 26!= 4* 10的26次方,应该是25次方才对。这个key值很大,但是依靠计算机还是很容易被猜测到,假如使用英文的话。有些字母很常用,因此很容易破解。

上图是字母的出现规律,所以假设密文足够长,那么越多的尝试就很容易破解密码,并且提高密码的准确性。

polyalphabetic substitution cipher 多字母替换加密法:选一个单词,然后补足其他位置,这样可以大大提高加密性

Playfair Cipher 是其中的一个案例:找个不带重复字母的单词写到矩阵内,然后补充其他字母,然后计算,后续实验课会有。

这种方法在一战大量应用,但是依然是有限的每一个字母都只有26个可能性,因此最多就是26 * 26 =676个表格。

Autokey Cipher自动密钥加密:理想情况下,key和messge一样长。

举例是Vigenere Cipher,使用Tabula Recta,但是仍然有概率被破解

例如下面的,知道关键词deceptive就很容易破解,在表格中找到交叉点。不过这个安全系统也很高,因为重复的字母可能使用不同的字母替换。

Kasiski Method利用重复出现的字母,比如上面例子里VTW去尝试解密。按照下面的例子算,就是找到重复的内容,然后尝试abcdef,一般是3-9位尝试。然后看一下重复的内容中对应的尝试abcdef并不一样,那么就无法解析出东西,但是假如尝试5位abcde,发现是一样的,那么就说明解密这几位成功。

Vernam Cipher,又是一个利用异或公式计算的。

One Time Pad

Transposition Ciphers Transposition or Permutation 移位 置换 换位密码。就是重新排序字母。

如下例子,先来个数字,然后把明文按顺序按组写好,然后根据数字的顺序重新给字母排序。

当然,更加复杂的就是把上述若干方法混合使用。

后面就是一些例子,比如二战常用的密码机器-转子机器。移一个位置,整个密码机器都不一样。

Steganography隐写术

上一节课讲过这个知识,把明文暗藏在一大段内容中。

同样,和上一节课一样,可以藏在歌曲,图片里,现在利用软件更加难以破解。
Steganographic attacks

 Steganography-only attack: The steganography medium is the only item available for analysis.
 Known-carrier attack: The carrier and steganography media are both available for analysis.
 Known-message attack: The hidden message is known.
 Chosen-steganography attack: The steganography medium and algorithm are both known.
 Chosen-message attack: A known message and steganography algorithm are used to create steganography media for future analysis and comparison.
 Known-steganography attack: The carrier and steganography medium, as well as the steganography algorithm, are known.

总结部分

下面开始实验课部分,详细讲解上述的各种算法

Lab Practical Tasks:
Binary encoding
Exclusive Or (XOR)
Probability theory


Basic Cryptographic Algorithms

其中算法会讲解四种

Caesar Cipher
Playfair Cipher (Monoalphabetic)
Vigenère Cipher (Polyalphabetic)
Vigenère Autokey Cipher (Polyalphabetic)

首先是binary encoding

这个又是一个老生常谈的技能,几个进制的转换,除了2进制,10进制,这次要多练习16进制,未来不确定是不是需要练习8进制。

这个需要配合ASCII表格来把字母转换,然后继续使用XOR计算,最后得出结果。

American Standard Code for Information Interchange (ASCII) table

然后是XOR 或者exclusive

There are 4 basic techniques for calculating the result from 2 binary numbers that are useful in computing. This is not a mathematical result, but a result of comparing the 2 numbers.

这里提到了除了这节课用到的XOR计算,还有另外三种计算。应该都是属于布尔计算的方式。
And: both the first and second number is 1
Not: Neither the first nor second number is 1
Or: Either the first or second number or both is 1
Xor: Either the first or second number is 1 but not both.

下面是一个例子,综合了上述两个点

原始信息 是Misdf,

然后根据ASCII 代码表找到每一个字母的值,转换为十进制

M=77

i=105

s=115

d=100

f=102

把这几个十进制转为二进制,变成

然后随机使用key,假设为55. 55同样是一个十进制。转换为二进制是00110111

然后呢就可以执行XOR计算,

M XOR后 成为01111010 转为十进制 122 转为ASCII z

i XOR后 成为 01011110 转为十进制 94 转为ASCII ^

s XOR后 成为01000100 转为十进制 68 转为ASCII D

d XOR后 成为01010011 转为十进制 83 转为ASCII S

f XOR后 成为01010001 转为十进制 81 转为ASCII Q

所以Misdf最后变成了z^DSQ

当然也可以转为十六进制,

比如M=77 in dec = 4D in Hex

当然原始值或者加密后的值都可以转为十六进制。

然后是Probability Theory:

我们这里要注意,并不是纯逻辑或者纯数学思路,比如一共有四个密码,理论上你尝试了三个就知道第四个是正确的。但是在这里不适用,这节课要求就是四个全部尝试过。同理,平均值也简单的认为是除以2,不考虑数学或者逻辑情况。

比如 4 possible keys (2的2次方),那么总共就是4个keys,保证破解需要的次数是4,平均获取的次数是2. 假如一共1000个keys,总共就是10000个keys,保证破解需要的次数是10000,平均获取的次数是5000. 假如一秒可以尝试10个keys,那么保证破解就需要1000秒,平均破解就是500秒。

这里再次提到了 提高加密性的方法是密码的选择和管理,比如下面例子,看上去位数很多,很难破解,但是假如key选的是一堆0,依然是一秒内破解。

Key = 00000000 00000000 00000000 00000000 00000000 00000000 00000000
The keyspace is 7 bytes or 56 bits. 2的56次方 (2 to the power 5) = 7.2057594e+16 or 72,057,594,037,900,000.

下面是例子练习题

Our computer can try 100 000 keys per second. The key we are using is 8 bytes.
Example 1: The key can only be lowercase letters and repetition is permitted. (eg helloooo)
Keyspace = …. 26的八次方 即26 to the power 8 which is:…… 计算值即可
Brute force time required in seconds is:… 除以100000即可
Brute force time required in days is:…除以60变成分钟,再除以60变成小时,再除以24变成天

combination and permutation 组合和排列

这里就是我疑惑的点,combination意味着顺序没所谓,即123, 132,213,231巴拉巴拉都是1 2 3的组合,所以key是一样的。假如key有三位,那么最大的可能性就是3的阶乘 3! = 3 * 2 *1 = 6。假如Key有6位,那么每组值最大的可能性就是6!= 6* 5* 4* 3* 2* 1 =720

而permutation就是顺序有所谓,123和321是两回事。

举例如下,这里保险柜100个数字,0-99,但是0不能用,并且不可以重复。所以问这里有多少种组合

所以可以用的就是1-99,那么就是99 * 98 * 97种combination可能性。

随机扩展题,9月30天,10月31天,3月31天。

所以应该30 * 30 * 29,这里从天数少的开始计算更好计算。

再来一个例题

第一个题很简单 10 * 10 * 10 * 10 = 10,000个可能性codes

这个就是一万个codes 除以4 就是 2500,然后问的是average所以除以2是1250,然后每秒尝试3个再乘以3即可。

继续升级难度,不允许重复,一共有六个codes。总数变成了10 * 9 *8 *7,然后除以6 再除以2.

继续升级,顺序没所谓,所以一个组合就是 4!=24,所以就是总数 除以24 组合数 除以2 average

Basic Encryption Ciphers:

The Caesar Cipher: 上文提到过,就是字母向右平移。破解就是向左平移,一共就25个可能性,所以暴力破解即可。

所以town 就是qltk

The Playfair Cipher:

上文也提到了,写一个不带重复字母的单词,然后补齐其他字母。

Step 1: Choose a word without repeating letters to be the ‘key’. In this case the key is ‘MONARCHY’. Fill in the 5×5 matrix with the keyword and then continue the alphabet from the first missing letter of the alphabet. The letters i/j are considered 1 letter as the matrix is 25 spaces and the alphabet has 26 letters.

然后明文有连续重复的字母就补充X

Step 2: If a word has a repeating letter, put an ‘X’ between the repeating letters. For example, with ‘HELLO’ it would begin with ‘HELXLO’.

然后两两一组划分,
Step 3: All letters should be written in pairs with gaps between them, so the ‘HELXLO’ would be written as ‘HE LX LO’.

同一行的向右平移
Step 4: If both letters are in the same row, then replace each with the letter to the right. The row wraps around to the start of the same row, so ‘AR’ would be replaced with ‘RM’.

同一列的向下平移
Step 5: If both letters are in the same column, then each letter is replaced with the letter below it. The columns wrap around from the bottom of the column to the top of the column, so ‘MU’ would be replaced with ‘CM’. (M is replaced with the C below it. U is replaced with the M below it)

然后其余的不是同一行或者同一列的就用交叉点替换,首字母先行再列

Step6: If none of these apply, then each letter is replaced by the one in its row in the column of the other letter of the pair. (first letter row first) For example, HS encrypts to ‘BP” and ‘EA’ encrypts to ‘IM’.

There are 2 problems with the cipher. The first, as with many ciphers, require the key to be securely exchanged before decoding the message can be successful and the second is that trial and error with the key length may give some correct letters and therefore lead to ‘educated’ guessing of the correct letters. This becomes much simpler when computers can be employed. You may also notice that there are only 676 possible digrams – 26 letters that can have 1 of 26 other letters next to it. A computer could try all 676 possibilities quite simply. 我这里没搞懂IJ怎么办,但是老实说他给我们指定单词,因此他会尽量避免这种情况,好吧。除此之外,X的出现会导致两种情况,破解了后要删掉X还是说找原字母呢?这个需要再问问。

The Vigenère Cipher:

最初是这样,不断重复某个key word,让其和明文一样长,然后找交叉点

The Vigenère Autokey Cipher:

这个就是在刚才的基础上把key word 改primer word 印子单词 然后是信息,这样就不会不断重复,也就不容易破解。

最后就是练习题。


Chao

一个三天打鱼两天晒网的博主 拖延症严重患者 干啥啥不行,学啥啥不会