密码学基础——古典密码学

目录

一、定义

特点：

二、发展阶段

三、代换密码

1.单表代换密码

1.1恺撒密码

1.2 移位变换  

1.3 仿射变换

2.多表代换密码

维吉尼亚密码

四、置换密码

栅栏密码

---

一、定义

    古典密码学是指在现代密码学出现之前，使用较为简单的数学方法和手工操作来实现信息加密的技术和理论。它主要依靠字符的代换、置换等基本操作来隐藏信息的真实内容。

• 代换（替代）：将明文中的每个字符替换为另一个字符，形成密文。例如，凯撒密码就是一种简单的代换密码，它将明文中的每个字母按照字母表顺序向后移动一定的位数来得到密文。
• 置换（换位）：不改变明文中的字符，而是通过重新排列字符的位置来形成密文。例如，栅栏密码就是将明文按照一定的规则分组，然后将每组中的字符顺序打乱重新排列得到密文。

特点：

        古典密码的优点是算法相对简单，容易理解和实现。缺点是安全性较低，随着计算机技术的发展，很容易被破解。

二、发展阶段

• 起源阶段：

        古典密码学的历史可以追溯到古代。例如，公元前 1900 年左右，古埃及人就使用过一些简单的符号替换方法来加密信息。古希腊人使用一种名为 “天书” 的密码工具，通过将字母写在一条缠绕在木棒上的皮带上，来实现信息的加密和解密。

• 发展阶段：

        在中世纪，密码学得到了进一步的发展。许多国家的政府和军队开始使用密码来传递机密信息。例如，凯撒密码在罗马军队中被广泛使用。

• 成熟阶段：

        文艺复兴时期，密码学技术更加成熟，出现了多种复杂的加密方法，如维吉尼亚密码等。这些密码在当时的政治、军事和商业领域发挥了重要作用。

三、代换密码

        古典密码的加密是将明文的每一字母代换为字母表中的另一字母，代换前首先将明文字母用等价的十进制数字代替，再以代替后的十进制数字进行运算，字母与十进制数字的对应关系如表所示。

字母	a	b	c	d	e	f	g	h	i	j	k	l	m
数字	0	1	2	3	4	5	6	7	8	9	10	11	12
字母	n	o	p	q	r	s	t	u	v	w	x	y	z
数字	13	14	15	16	17	18	19	20	21	22	23	24	25

        根据代换是对每个字母逐个进行还是对多个字母同时进行，古典密码又分为单表代换密码和多表代换密码。  

1.单表代换密码

1.1恺撒密码

凯撒（Caesar)密码是将明文中的每个字母按照字母表顺序向后移动固定的位数（3位），得到密文。密代换和解密代换分别为：          

其中3是加解密所用的密钥，加密时，每个字母向后移3位（循环移位，字母x移到a，y移到b，z移到c）。解密时，每个字母向前移3位（循环移位）。

1.2 移位变换  

移位变换的加解密分别是：

1.3 仿射变换

仿射变换的加解密分别是：    

其中a,b是密钥，为满足0<=a,b<=25和gcd(a,26)=1的整数。其中gcd(a,26)=1表示a和26的最大公因子为1，表示a和26是互素的，a-1表示a的逆元，即  。

【例题1】设仿射变换的加解密分别是： 

对 “security”加密，对 “vlxijh”解密。

解：（1）对 “security”加密：

所以，“security”对应的密文是 “rxjfkzyh”。

（2）对 “vlxijh”解密：

所以，“vlxijh”对应的明文是 “agency”。

2.多表代换密码

多表代换密码首先将明文M 分为由n个字母构成的分组M1,M2,...Mj，对每个分组Mi的加密为：

其中(A,B)是密钥，A是 n×n的可逆矩阵，满足gcd( |A|,N)=1（|A|是行列式).              

对密文分组Ci的解密为：

【例题2】设n=3,N26 ，

明文为 YOUR PIN NO IS FOUR ONE TWO SIX。

（1）加密过程：

将明文分成3个字母组成的分组 “YOU RPI NNO ISF OUR ONE TWO SIX”，如下所示：

由于矩阵B为0，所以

密文为 “WGI FGJ TMR LHH XTH WBX ZPS BRB”。

（2）解密过程：

解密时，先求出

再求

得明文为“YOU RPI NNO ISF OUR ONE TWO SIX”。

维吉尼亚密码

• 简介：维吉尼亚密码是一种多表代换密码，由法国密码学家维吉尼亚于 1586 年提出。它克服了单表代换密码容易被频率分析破解的缺点，安全性相对较高。维吉尼亚密码的核心在于使用一个关键词作为密钥,并通过一张特殊的表格来进行加密。
• 特点：通过使用多个凯撒密码的组合，隐藏了明文中字符的频率分布规律，增加了密码分析的难度。但如果密钥字较短，且明文较长，仍可能通过统计分析等方法被破解。
• 加密原理：
  • 首先有一个密钥，将密钥重复扩展，使其长度与明文相同。
  • 然后，根据密钥字中每个字符对应的字母在26行字母表（这张表格由26行字母表组成,每一行都是上一行向左偏移一位得到的）中的位置，在表格中找到对应的密文。

下面是26行的维吉尼亚密码表：第一行为明文字符，第一列为密钥字符，中间为加密（移位）后的结果。

【例题3】明文为 “SECURITY”，密钥为 “CODE”，

解：明文SECURITY（对应为18 4 2 20 17 8 19 24）一共有8个字符，

因此重复后的密钥为C O D E C O D E(变换为移位的位数为2 14 3 4 2 14 3 4)

S（明文）+C（密钥）=U（密文）即(18 + 2) % 26 = 20

E（明文）+O（密钥）=S（密文）

C（明文）+D（密钥）=F（密文）

U（明文）+E（密钥）=Y（密文）

依次类推，可以得到最终密文为：USFYTWWC

• 解密原理：
  • 与加密过程相反，根据密钥中每个字符对应的字母在字母表中的位置，对密文中相应位置的字符进行逆向的凯撒密码变换。
  • 也可以用密文对应的数字减去密钥对应位置的数字，若结果为负数则加上 26，最后对 26 取模。例如，对于第一个字符，(20 - 2) % 26 = 18

四、置换密码

栅栏密码

• 简介：栅栏密码是一种简单的置换密码，它将明文按照一定的规则重新排列，从而达到加密的目的。
• 特点：加密方法简单，容易实现。但其安全性较低，因为只是对字符的位置进行了置换，字符本身没有改变，攻击者可以通过分析字符的频率分布等特征来尝试破解。
• 加密原理：将明文按照一定的字数分成若干行（栏数），然后将每行的字符按照特定的顺序重新排列（按列读取），形成密文。

【例题4】明文 “SECURITY” ，栏数为2

解：

（1）加密

由于栏数为2，即把明文SECURITY分成上下两行交替放置字符。

第一行：S E C U

第二行：R I T Y

加密后的密文就是将两行字符从上到下，从左到右依次连接起来，

密文S->R->E->I->C->T->U->Y，即SREICTUY

• 解密原理：先根据已知的分组长度，将密文按照相反的顺序重新分组，再将每组的字符按照原来的顺序还原，即可得到明文。

（2）解密：

第一行：S C R T
第二行：E U I Y

明文为S->E->C->U->R->I->T->Y，即SECURITY