1.实验目的
(1)了解常见数据编码方法、原理;
(2)掌握Base64编码基本原理和应用;
(3)了解古典密码常用的加密方法,如替换、置换;
(4)实践部分典型的古典加密,掌握通信加密的基本过程;
(5)理解密码分析中的频率分析原理及一般方法。
2.实验内容
(1)查阅资料,整理总结ASCII、URL、Base64编码的产生背景和应用场景;
(2)base64编解码实践
(3)单表加密、多表加密和验证
3.实验指导
(1)ASCII产生背景、原理及应用:
背景:
在计算机中,所有的数据在存储和运算时都要使用二进制数表示。例如,a、b、c、d这样的52个字母(包括大写)以及0、1等数字还有一些常用的符号(例如*、#、@等)在计算机中存储时也要使用二进制数来表示。互相通信而不造成混乱,美国有关的标准化组织就出台了ASCII编码,统一规定了上述常用符号的二进制数表示。
原理:
ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256 种可能的字符。标准ASCII 码也叫基础ASCII码,使用7 位二进制数(剩下的1位二进制为0)来表示所有的大写和小写字母,数字0 到9、标点符号,以及在美式英语中使用的特殊控制字符。其中: 0~31及127(共33个)是控制字符或通信专用字符(其余为可显示字符),如控制符:LF(换行)、CR(回车)、FF(换页)、DEL(删除)、BS(退格)、BEL(响铃)等;通信专用字符:SOH(文头)、EOT(文尾)、ACK(确认)等;ASCII值为8、9、10 和13 分别转换为退格、制表、换行和回车字符。它们并没有特定的图形显示,但会依不同的应用程序,而对文本显示有不同的影响。 32~126(共95个)是字符(32是空格),其中48~57为0到9十个阿拉伯数字。 65~90为26个大写英文字母,97~122号为26个小写英文字母,其余为一些标点符号、运算符号等。 同时还要注意,在标准ASCII中,其最高位(b7)用作奇偶校验位。所谓奇偶校验,是指在代码传送过程中用来检验是否出现错误的一种方法,一般分奇校验和偶校验两种。奇校验规定:正确的代码一个字节中1的个数必须是奇数,若非奇数,则在最高位b7添1;偶校验规定:正确的代码一个字节中1的个数必须是偶数,若非偶数,则在最高位b7添1 。 后128个称为扩展ASCII码。许多基于x86的系统都支持使用扩展(或“高”)ASCII。扩展ASCII 码允许将每个字符的第8 位用于确定附加的128 个特殊符号字符、外来语字母和图形符号
应用:
ASCII码 A 对应的是数值是 65 ,那么在内存里面,‘A’ 和 65是完全没有区别的,就是存放的是 65 的二进制。当把 65 当作数据时,那么它就是 65 ;如果把它当作字符,计算机就会调用计算机图形学的编程,将 A 的图形绘制到屏幕上,这时候就能看到 A
(2)URL编码产生背景、原理及应用:
背景:
一般开发中,如果一个东西需要被编码,其原因有多种:由于私密信息传输需要被编码、由于传输时内容过大需要编码压缩等等;而URL编码则是为了解决url中可能存在的字符歧义。
原理:
当在浏览器中输入一个URL时,浏览器会将输入到地址栏的非数字字母转化为URI编码。URI编码是一个字符的ASCII码,它的ACSII码的十六进制式,在前面加上"%",就是它的URL编码。 比如"/“的ASCII码是92,92的十六进制是5c, 所以”/"的URI编码就是 %5c,"胡"的ASCII码是-17670, 它的十六进制是BAFA, 所以它的URI编码就是 "%BA%FA"IE会自动将输入到地址栏的非数字字母转换为URI编码。所以对于浏览器来说 http://blog.csdn.net/g%75%6fq%75a%6ey%6f%75 和http://blog.csdn.net/guoquanyou 是一样的
应用:
url编码是一种浏览器用来打包表单输入的格式。浏览器从表单中获取所有的name和其中的值 ,将它们以name/value参数编码(移去那些不能传送的字符,将数据排行等等)作为URL的一部分或者分离地发给服务器。
(3)Base64编码产生背景、原理及应用:
背景:
base64 最早就是用来邮件传输协议中的,原因是邮件传输协议只支持 ascii 字符传递,因此如果要传输二进制文件,如:图片、视频是无法实现的。因此 base64 就可以用来将二进制文件内容编码为只包含 ascii 字符的内容。
原理:
Base64可以将ASCII字符串或者是二进制编码成只包含A—Z,a—z,0—9,+,/ 这64个字符( 26个大写字母,26个小写字母,10个数字,1个+,一个 / 刚好64个字符)。这64个字符用6个bit位就可以全部表示出来,一个字节有8个bit 位,那么还剩下两个bit位,这两个bit位用0来补充。其实,一个Base64字符仍然是8个bit位,但是有效部分只有右边的6个 bit,左边两个永远是0。Base64的编码规则是将3个8位字节(3×8=24位)编码成4个6位的字节(4×6=24位),之后在每个6位字节前面,补充两个0,形成4个8位字节的形式,那么取值范围就变成了0~63。又因为2的6次方等于64,所以每6个位组成一个单元。
应用:
X.509公钥证书、文本传输、HTTP协议、电子邮件(SMTP协议)、图片base64编码
多表加密及其频率分析
(1)使用Vigenere或playfair加、解密一小段英文字符,实现验证
Vigenere:
Playfair:
(2)分析多表加密明文、密文字符频率关系,并查阅资料简述多表加密密码攻击思路
单表替代密码表现出明文中单字母出现的频率分布与密文中相同, 多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现 的频率分布,每个映射是简单替代密码中的一对一映射多表替代密码将 明文字母划分为长度相同的消息单元,称为明文分组,对明文成组地进 行替代,同一个字母有不同的密文,改变了单表替代密码中密文的唯一 性,使密码分析更加困难。多表替代密码的特点是使用了两个或两个以上的替代表。著名的维吉尼亚密码和Hill密码等均是多表替代密码。
多表加密密码攻击思路:
- 多表古典密码分析
我们以Vigenere密码为例来说明多表古典密码的分析方法。确定密钥字长度的方法有Kasiski测试法(Kasiski Test)和重合指数法(index of coincidence). - Vigenere密码
Vigenere(维吉尼亚)密码是使用一系列凯撒密码组成密码字母表的加密算法,属于多表密码的一种简单形式。 - 凯撒密码:一种替换加密的技术,明文中的所有字母都在字母表上向后(或向前)按照一个固定数目进行偏移后被替换成密文。例如,当偏移量是3的时候,所有的字母A将被替换成D,B变成E,以此类推。
欧几里得算法及其扩展算法
编程实现计算两个数最大公约数、求指定数的模逆元(包括算法源代码文本及其测试截图)。
欧几里得算法求两个数最大公约数:
#include <iostream>
using namespace std;
int gcd(int a, int b){
if (a%b == 0) {
return b;
}
return gcd(b, a%b);
}
int main(int argc, const char * argv[]) {
int a = 14, b = 18;
cout<<gcd(a,b);
return 0;
}
欧几里得算法求指定数的模逆元:
#include <iostream>
using namespace std;
void Ex_gcd(int a, int b, int &x, int &y)
{
if(b == 0)//递归出口
{
x = 1;
y = 0;
return;
}
int x1, y1;
Ex_gcd(b, a%b, x1, y1);
x = y1;
y = x1-(a/b)*y1;
}
int MOD(int &n,int &f)
{
return (n%9973)*(f%9973)%9973;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,B;
cin>>n>>B;
int x,y;
Ex_gcd(B,9973,x,y);
if (x<0)
x+=9973;
int f=x;
int result=MOD(n,f);
cout<<result<<endl;
}
return 0;
}
欧几里得扩展算法求两个数的最大公约数:
#include<iostream>
#include<stdio.h>
using namespace std;
int x,y,q;
void extend_Eulid(int a,int b)
{
if(b==0)
{
x=1;
y=0;
q=a;
}
else
{
extend_Eulid(b,a%b);
int temp=x;
x=y;
y=temp-a/b*y;
}
}
int main()
{
int a,b;
cout<<"请输入a"<<endl;
cin>>a;
cout<<"请输入b"<<endl;
cin>>b;
if(a<b)
{
int temp=a;
a=b;
b=temp;
}
extend_Eulid(a,b);
printf("最大公约数=%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b);
return 0;
}
扩展欧几里得算法求指定数的模逆元:
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
typedef long long LL;
const int N = 10005;
const int MOD = 9901;
bool prime[N];
int p[N];
int cnt;
void isprime()
{
cnt = 0;
memset(prime,true,sizeof(prime));
for(int i=2; i<N; i++)
{
if(prime[i])
{
p[cnt++] = i;
for(int j=i+i; j<N; j+=i)
prime[j] = false;
}
}
}
LL power(LL a,LL b)
{
LL ans = 1;
a %= MOD;
while(b)
{
if(b & 1)
{
ans = ans * a % MOD;
b--;
}
b >>= 1;
a = a * a % MOD;
}
return ans;
}
LL sum(LL a,LL n)
{
if(n == 0) return 1;
LL t = sum(a,(n-1)/2);
if(n & 1)
{
LL cur = power(a,(n+1)/2);
t = (t + t % MOD * cur % MOD) % MOD;
}
else
{
LL cur = power(a,(n+1)/2);
t = (t + t % MOD * cur % MOD) % MOD;
t = (t + power(a,n)) % MOD;
}
return t;
}
void Solve(LL A,LL B)
{
LL ans = 1;
for(int i=0; p[i]*p[i] <= A; i++)
{
if(A % p[i] == 0)
{
int num = 0;
while(A % p[i] == 0)
{
num++;
A /= p[i];
}
ans *= sum(p[i],num*B) % MOD;
ans %= MOD;
}
}
if(A > 1)
{
ans *= sum(A,B) % MOD;
ans %= MOD;
}
cout<<ans<<endl;
}
int main()
{
LL A,B;
isprime();
while(cin>>A>>B)
Solve(A,B);
return 0;
}