古代密码

• 数据的保密基于加密算法的保密。

Scytale密码

• 使用一条纸袋作为载体，环绕在一根固定半径的圆柱上。
• 

加密

• 在绕好的纸带上写上明文。
• 解开缠绕后，就是加密好的、无序的密文。
• 圆柱的半径就是密钥。

解密

• 找到相同大小的圆柱，将纸带缠绕在援助上，即得到密文。

棋盘密码

• 将26个字母放进一个5x5的表格中（ij放在一起）。
• 

加密

• 将明文对照表格找到横纵坐标，横坐标+纵坐标即为单个字符的密文。
• 其中这个表格就是密钥。

解密

• 对照表格，将密文以2个数字一组，找到对应的字母。

凯撒密码

• 是一种移位密码，将字母对应到相应的数字（A对应为0）后，通过循环移位，改变对应的字母。

加密

• 先将每个字母对应到0~25的数字。
• 再进行移c位，这里的c就是密钥。

c = ( m + k ) % 26 c=(m+k)\%26 c=(m+k)%26

凯撒密码的c为3。

解密

• 对移位操作反向执行，即可恢复原文。

m = ( c − k ) % 26 m=(c-k)\%26 m=(c−k)%26

古典密码

• 两种构造方式：
  • 代替密码
  • 置换密码

置换密码

• 字或者字母本身不变，位置发生改变，形成密文。
• 又称为易位密码。
• 下面举出报文倒置法的例子。

加密

• 将明文倒置输出得到密文。

解密

• 将密文倒置输出得到明文。

单表代替密码——加法密码

• 同凯撒密码，不多赘述。

加密

• 代码

//m is message, k is key,l is the length of message
void f(int*m, int k,int l){
    for(int i=0;i<l;i++){
        printf("%c",(m[i]+k)%26+97);
    }
}

解密

• 代码

//m is message, k is key,l is the length of message
void f(int*c, int k,int l){
    for(int i=0;i<l;i++){
        printf("%c",(c[i]-k+26)%26+97);
    }
}

单表代替密码——乘法密码

加密

• 密钥k与26互素，保证k的逆存在。

c = k × m ( m o d 26 ) c=k\times m(mod26) c=k×m(mod26)

• 代码

//m is message, k is key,l is the length of message
void f(int *m,int k,int l){
    for(int i = 0;i < l;i++){
        printf("%c",m[i]*k%26+97);
    }
}

解密

• 利用扩展欧几里得得到k的逆。

m = k − 1 × c ( m o d 26 ) m=k^{-1}\times c(mod26) m=k−1×c(mod26)

• 代码

int prim[12] = {1,3,5,7,9,11,15,17,19,21,23,25};
//m is message, k is key,l is the length of message
void f(int *c,int k,int l){
    int d;
    for(int i = 0;i < 12;i++){
        if(k*prim[i]%26 == 1){
            d = prim[i];
        }
    }
    for(int i = 0;i < l;i++){
        printf("%c",c[i]*d%26+97);
    }
}

这里由于集合中素数只有12个，依次枚举即可得到密钥的逆。

int prim[12] = {1,3,5,7,9,11,15,17,19,21,23,25};
//decode with exgcd
void exgcd(int a,int b,int*yp){
    int x;
    if(!b){
        x = 1;
        *yp = 0;
        return;
    }
    int x1=0,x2=1,y1=1,y2=0,q,r;
    while(b>0){
        q = a/b;
        r = a-q*b;
        x = x2-q*x1;
        *yp = y2-q*y1;
        a = b;
        b = r;
        x2 = x1;
        x1 = x;
        y2 = y1;
        y1 = *yp;
    }
    *yp = y2;
}

void f(int *c,int k,int l){
    int d;

    exgcd(26,k,&d);
    
    for(int i = 0;i < l;i++){
        printf("%c",c[i]*d%26+97);
    }
}

单表代替密码——仿射密码

• 结合加法密码和乘法密码就得到仿射密码。

加密

c = a × m + b ( m o d 26 ) c=a\times m+b(mod26) c=a×m+b(mod26)

解密

• 分别使用加法密码和乘法密码的逆过程即可得到。

m = a − 1 ( c − b ) ( m o d 26 ) m=a^{-1}(c-b)(mod26) m=a−1(c−b)(mod26)

单表代替密码——密钥短语代替

• 这种密码选用一个英文短语或者单词串作为密钥，称为密钥字或密钥短语。

加密

• 构造乱序字母表作为密钥，将明文中的字符进行映射。
• 例如下表（一三行为明文表，二四行为对应密文）。

a	b	c	d	e	f	g	h	i	j	k	l	m
H	A	P	Y	N	E	W	R	B	C	D	F	G
n	o	p	q	r	s	t	u	v	w	x	y	z
I	J	K	L	M	O	Q	S	T	U	V	X	Z

解密

• 得到字母表之后进行一一替换即可。

通过大量密文统计每个字符出现概率，在单一密文里面找到对应概率的字符进行替换尝试，可能导致在没有字母表时密文被破解。

多表代换密码

• 每一位字符对应不同的加密方法，构造二维表作为密钥。

加密

• 构造可逆模26互素矩阵，利用它和明文串相乘得到密文串。

C i = A M i + B ( m o d N ) C_i=AM_i+B(mod N) Ci​=AMi​+B(modN)

• 由于在构造二维表时，我太懒了难以找到满足条件的表，这里代码只给出3阶密钥（老师给的）。

int key[NUM][NUM] = {{11,2,19},{5,23,25},{20,7,17}};

void f(int *m,int l){
    char c;
    for(int i = 0;i < l;i++){
        c = 0;
        for(int j = 0;j < l;j++){
            c += key[i][j]*m[j]%26;
        }
        printf("%c",c%26+97);
    }
}

解密

• 利用矩阵可逆的条件，构造逆矩阵作为乘法矩阵。
• 密文串和逆矩阵做乘法之后便得到明文串。

M i = A − 1 ( C i − B ) ( m o d N ) M_i=A^{-1}(C_i-B)(modN) Mi​=A−1(Ci​−B)(modN)

• 代码

int dkey[NUM][NUM] = {{10,23,7},{15,9,22},{5,9,21}};

void f(int *c,int l){
    char m;
    for(int i = 0;i < NUM;i++){
        m = 0;
        for(int j = 0;j < NUM;j++){
            m += dkey[i][j]*c[j]%26;
        }
        printf("%c",m%26+97);
    }
}

• 代码

int dkey[NUM][NUM] = {{10,23,7},{15,9,22},{5,9,21}};

void f(int *c,int l){
    char m;
    for(int i = 0;i < NUM;i++){
        m = 0;
        for(int j = 0;j < NUM;j++){
            m += dkey[i][j]*c[j]%26;
        }
        printf("%c",m%26+97);
    }
}

实际上统一密文以l为单位长度