密码学复习笔记(二)
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;
}