密码学复习笔记（二）

1、经典的简单密码：

   移位密码、一次一密乱码本、仿射密码。

2、移位密码：这是最简单的一种加密方式，早期的Caesar密码就是移位密码，这种密码很简单就是约定

把第个字母的位数往后移动3位，改进后的Caesar密码是发送方和接收方协商一个密钥k，1≤k≤25，代表移

动位数。下面写一个简单的程序展示一下：

#include<iostream>
#include <ctype.h> 
using namespace std;

#define CNT 5 //移动的位数
#define MAXLEN 100 //要加密的字符串可能的最大长度

int main()
{
	char str[MAXLEN];
	scanf("%s",str);
	for(int i = 0; i < strlen(str); i ++)
	{
              if(str[i]-' ' != 0)
		{
			str[i] = toupper(str[i])+CNT;
			if(str[i] > 'Z') str[i] -= 26;
		}
	}
	printf("%s\n",str);
	return 0;
}

 

可以想像，这种密码很容易攻击，穷举25种可能就行了。

特点：

  1）是对称密码：加密密钥和解密密钥相同；

  2）是单表代替密码：所有的明文字母用同一种方法 

                   加密，即子密钥相同。

 

3、乘法逆

   n模m的乘法逆t满足：n×t%m=1，记作：t=n-1%m

   乘法逆是复杂点的密码学算法的基础。

举例：

2-1%5的值为：3，因为 3×2%5=1

3-1%100的值为：67，因为 67×3%100=1

乘法逆的计算可以用

1）穷举法：

技巧：若t×n%m=-1，则n-1%m=m-t。

如：33×3%100=-1，所以3-1%100的值为67。

 

2）欧几里德算法：

原理：辗转求余

　　gcd(a,b)=gcd(b,a mod b)这个公式是欧几里德算法的基础，gcd就是最大公约数。

把公式变形后得：

ax+by=gcd(x,y) 当等号右边等于1时，这个式子就是我们用来求的乘法逆的关键式子了。

下面是我写的一个程序，用来模仿这个计算过程：

#include<iostream>
#include<stack>
using namespace std;

stack<int> s;

int cfn(int n, int m)
{
	bool flag = false;
	int cnt,a,b,t=1;
	if(n > m)
	{
		flag = !flag;
		a = n;
		n = m;
		m = a;
	}
	while(t)
	{
		cnt = 1;
		while(m-n >= n)
		{
			cnt++;
			m-=n;
		}
		m -= n;
		s.push(-cnt);
		t = m;
		m = n;
		n = t;
	}

	a = 0,b=1;
	s.pop();
	while(!s.empty())
	{
		t = b;
		b = a + b*s.top();
		a = t;
		s.pop();
	}
	return flag?a:b;
}

int main()
{
	int m,n;
	while(scanf("%d%d",&n,&m) == 2)
		printf("%d\n",cfn(n,m));
	return 0;
}