密码学学习笔记（一）——凯撒密码及简单替换密码

2024-02-02 20:35:10

文章目录

1. 凯撒密码
2. 简单替换密码

1. 凯撒密码

1.1 加解密方式

凯撒密码是通过将明文中所使用的字母表按照一定的字数偏移建立映射，从而对明文进行加密的。

1.1.1 加密

这里，我们假设要对“zicheng”这个字符串进行加密，让字母表的偏移字数为3。显然这个字符串包含‘z’‘i’‘c’‘h’‘e’‘n’‘g’这七个字母，按照之前说的方法，我们逐一对其进行加密：

z -> c
i -> l
c -> f
h -> k
e -> h
n -> q
g -> j

这样，明文“zicheng”就转成了密文“clfkhqj”，可读性有了明显的降低。
在刚才的操作中，我们将字母转换的过程称为密码算法，而偏移字数就相当于密钥。下面是C语言程序：

#include <stdio.h>
#include <stdlib.h>


int main()
{
	int key;
	char plain[100] = {0},cipher[100] = {0};
	int i;
	char a;
	printf("Input the key:");
	scanf("%d",&key); 
	while(1)
	{
		i = 0;
		printf("Input the plaintext:");
		scanf("%c",&a);
		while(a != '\n')
		{
			plain[i] = a;
			i++;
			scanf("%c",&a);
		}
		i--;
		while(i >= 0)
		{
			if((plain[i] + key > 90 && plain[i] < 97) || plain[i] + key > 122)
				cipher[i] = plain[i] + (key - 26);
			else
				cipher[i] = plain[i] + key;
			i--;
		}
		printf("The ciphertext is:");
		while(cipher[i+1] != 0)
		{
			i++;
			printf("%c",cipher[i]);
		}
		printf("\n");
	}
	system("pause");
	return 0;
}

1.1.2 解密

现在，接收者已经收到了字符串“clfkhqj”，由于可读性极低，所以我们必须将他解密成明文。解密方法同加密，只不过密钥变为了26-3=23，将收到的密文解密：

c -> z
l -> i
f -> c
k -> h
h -> e
q -> n
j -> g

这样我们就可以得到明文“zicheng”。下面是C语言程序：

#include <stdio.h>
#include <stdlib.h>


int main()
{
	int key;
	char plain[100] = {0},cipher[100] = {0};
	int i;
	char a;
	printf("Input the key:");
	scanf("%d",&key); 
	key = 26 - key;
	while(1)
	{
		i = 0;
		printf("Input the ciphertext:");
		scanf("%c",&a);
		while(a != '\n')
		{
			cipher[i] = a;
			i++;
			scanf("%c",&a);
		}
		i--;
		while(i >= 0)
		{
			if((cipher[i] + key > 90 && cipher[i] < 97) || cipher[i] + key > 122)
				plain[i] = cipher[i] + (key - 26);
			else
				plain[i] = cipher[i] + key;
			i--;
		}
		printf("The plaintext is:");
		while(plain[i+1] != 0)
		{
			i++;
			printf("%c",plain[i]);
		}
		printf("\n");
	}
	system("pause");
	return 0;
}

1.2 暴力破解

由于在凯撒密码中字母表只有26位，故其密钥只有0~25共26种，所以我们将这26种密钥全部代入解密尝试一遍就可得到我们想要的明文，这就是最简单的暴力破解法，根据操作原理，又称穷举搜索法，如下：

#include <stdio.h>
#include <stdlib.h>


int main()
{
	int key,k;
	char plain[100] = {0},cipher[100] = {0};
	int i = 0,j;
	char a;
	printf("Input the ciphertext:");
	scanf("%c",&a);
	while(a != '\n')
	{
		cipher[i] = a;
		i++;
		scanf("%c",&a);
	}
	j = i;
	k = 0;
	while(k < 26)
	{
		key = 26 - k;
		i = j - 1;
		while(i >= 0)
		{
			if((cipher[i] + key > 90 && cipher[i] < 97) || cipher[i] + key > 122)
				plain[i] = cipher[i] + (key - 26);
			else
				plain[i] = cipher[i] + key;
			i--;
		}
		printf("Key = %2d,The plaintext is:",k);
		while(plain[i+1] != 0)
		{
			i++;
			printf("%c",plain[i]);
		}
		printf("\n");
		k++;
	}
	system("pause");
	return 0;
}

2. 简单替换密码

凯撒密码可以说是一种特殊的简单替换密码，它是将所有的对应关系作了一个归一化处理。但若将这种对应关系以“随机”的方式建立，那么这种加密方式的保密性就又会有一个提升，暴力破解的方法就不能再适用了。

2.1 加解密方式

2.1.1 加密

依次将明文按替换表替换成另一个字母，密钥为替换表。我们这里将替换表用easy-key.txt文件记录，放在同一文件夹下,每两位数字与其位置表示一组替换，如01放在第7、8位，则表示将“d”替换为“a”，代码如下：

#include<stdio.h>
#include<stdlib.h>

int main()
{
	struct node
	{
		int a;
		int b;
	};
	typedef struct node key;
	key k[26];
	char plain[100] = {0},cipher[100] = {0};
	FILE *p;
	int i,m;
	char c1,c2,ch;
	for(i = 0;i < 26;i++)
		k[i].a = i + 1;
	if((p = fopen("easy-key.txt","r")) == NULL)
	{
		printf("\nOpen easy-key.txt Fail,Close!");
		getchar();
		exit(1);
	}
	for(i = 0;i < 26;i++)
	{
		//读取密钥到c1,c2 
		c1 = fgetc(p);
		c2 = fgetc(p);
		m = (c1 - 48) * 10 + (c2 - 48);
		k[i].b = m;
	}
	fclose(p);
	while(1)
	{
		i = 0;
		printf("Input the plaintext:");
		scanf("%c",&ch);
		while(ch != '\n')
		{
			plain[i] = ch;
			i++;
			scanf("%c",&ch);
		}
		i--;
		while(i >= 0)
		{
			if(plain[i] < 96)
			{
				plain[i] -= 65;
				cipher[i] = k[plain[i]].b + 64;
			}
			else
			{
				plain[i] -= 97;
				cipher[i] = k[plain[i]].b + 96;
			}
			i--;
		}
		printf("The ciphertext is:");
		while(cipher[i+1] != 0)
		{
			i++;
			printf("%c",cipher[i]);
		}
		printf("\n");
	}
	system("pause");
	return 0;
}

2.1.2 解密

依次将密文按替换表反向替换成另一个字母。

#include<stdio.h>
#include<stdlib.h>

int main()
{
	struct node
	{
		int a;
		int b;
	};
	typedef struct node key;
	key k[26];
	char plain[100] = {0},cipher[100] = {0};
	FILE *p;
	int i,m;
	char c1,c2,ch;
	for(i = 0;i < 26;i++)
		k[i].b = i + 1;
	if((p = fopen("easy-key.txt","r")) == NULL)
	{
		printf("\nOpen easy-key.txt Fail,Close!");
		getchar();
		exit(1);
	}
	for(i = 0;i < 26;i++)
	{
		//读取密钥到c1,c2 
		c1 = fgetc(p);
		c2 = fgetc(p);
		m = (c1 - 48) * 10 + (c2 - 48);
		k[i].a = m;
	}
	fclose(p);
	while(1)
	{
		i = 0;
		printf("Input the ciphertext:");
		scanf("%c",&ch);
		while(ch != '\n')
		{
			plain[i] = ch;
			i++;
			scanf("%c",&ch);
		}
		i--;
		while(i >= 0)
		{
			if(plain[i] < 96)
			{
				plain[i] -= 65;
				cipher[i] = k[plain[i]].a + 64;
			}
			else
			{
				plain[i] -= 97;
				cipher[i] = k[plain[i]].a + 96;
			}
			i--;
		}
		printf("The plaintext is:");
		while(cipher[i+1] != 0)
		{
			i++;
			printf("%c",cipher[i]);
		}
		printf("\n");
	}
	system("pause");
	return 0;
}

2.2 频率分析法破解

统计密文中每个字母出现的频率；
对比英语文章中字母与单词出现的频率；
以文章中频率最高的替换密文中频率最高的字母；
寻找反复出现的字符串，对比文章中频率较高的单词，得到其他对应；
重复3，4步，直到不能再确定出对应关系，转而对比频率较低的字母，或根据已知字母猜其组成的单词，直到获得完整的替换表。

码农公寓