单表代换/多表代换实验

#单表代换、多表代换实验

一、实验题目

单表代换和多表代换

二、实验目的和要求

通过实验熟练掌握凯撒密码和Hill密码算法原理，编程实现加密算法，熟悉模运算和扩展欧几里德算法，提高C++程序设计和密码运算基本能力。

单表代换
编程实现凯撒密码，输入任意一段明文，对其加密并输出密文。
多表代换
编程实现 Hill 加密算法，输入一段无空格的五个小写字母明文，对其加密并输
出密文。

三、实验环境

Clion、macOS Catalina 10.15.6

四、实验内容

4.1单表代换:

凯撒密码密钥为 3，从文本文件中读取明文，用密钥加密，密文保存于对应密
文数组。

4.2多表代换:

1.密钥生成：Hill 加密的密钥矩阵 K 随机生成，需要进行在模 26 的意义下进行
可逆性检测，这里可以用求行列式模 26 的逆元。
2.读取明文并预处理：输入的明文是 5 个小写字母，彼此之间没有空格，而后
放入 5 个元素的明文数组。
3.加密：将密钥矩阵与明文数组左乘，在模 26 的意义下，生成密文数组。

4.解密：将密钥矩阵的伴随阵 D 求出，左乘密文数组，再乘密钥矩阵行列式的
逆，从而完成逆矩阵左乘，都在模 26 的意义下。

五、算法描述及实验步骤

5.1单表代换

以凯撒密码为例：

加解密原理

$$c=E_{key}(m)\equiv m+key(mod\ 26) , 0\leq m \leq25\ \ \ 加密时，每个字母后移key位$$

$$m=D_{key}(c)\equiv c-key(mod\ 26) , 0\leq c \leq25\ \ \ \ 解密时，每个字母前移key位$$

建立一个plaintext.txt文件，用来存放需要加密的明文m。利用fgets函数，来将文件中的字符读取到message中。逐字读取明文长短，并且复制出明文内容，将其打印出来。输入key。进行逐位循环。加密：c=m+key(mod 26)。将加密结果存储在ciphertext中。并且打印出来。

5.2多表代换

以Hillcipher为例：

加密原理：

将明文M，分成由n个字母构成的分组，对各个分组M加密：

$$C_i \equiv AM_i+B(mod\ N),i=1,2,3..j$$

(A,B)是密钥。A是 n*n的可逆矩阵。

解密：

$$M_i\equiv A^{-1}(C_i-B)(mod\ N),i=1,2,3..j$$

为了满足可逆矩阵的条件：

$$gcd(|A|,N)=1 \ \ \ \ \ \ \ |A|为行列式$$

如果矩阵可逆，那么它的逆矩阵和它的伴随矩阵之间只差一个系数。

定义55的矩阵。用d来表示a、b的最大公约数。其中a代表的是|A|,b代表的是N。为保证A是可逆矩阵。class Hill_Cipher 的目的，生成满足可逆条件的矩阵。根据加密算法对明文进行加密。*

六、调试过程及结果（附截图）

6.1单表代换

6.2多表代换

七、总结体会

7.1单表代换

❓❓代码如何从输入的字符转换为可处理的数字？

‼️通过ascii码的转换：如char A = ‘65’ 加密时，进行逐位的循环操作。字母控制在A～Z

/* 测试代码 */
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
    char message[3]={'A','B','C'};
    if (message[1]>65)
    cout<<message[1]<<endl;
    return 0;
}

测试目的。可以根据char类型ascii来进行大小的比较。若ascii码对应的数值大于int的数字，则输出该字母。 B对应66，所以大于65，会输出B

7.2多表代换

❓❓代码如何进行扩展欧几里德算法求逆元？

‼️给定 a 和b。a 要有逆元，那么gcd（ a ， b ) = 1假设a的逆元为x ，那么就有 a * x mod b = 1也就是 a * x + b * y = 1。其中 x 就是 a的逆元。

#include <iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int x,y,q;
void ex_Eulid(int a,int  b){
	if(b==0){
		x=1;y=0;q=a;
	}
	else{
		ex_Eulid(b,a%b);
		double temp=x;
		x=y;y=temp-a/b*y;
	}
}
int main() {
	int a,b;
	cin>>a>>b;
	if(a<b)swap(a,b);
	ex_Eulid(a,b);
	printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b);
	return 0;
}

八、源程序附录

8.1单表代换

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int main(int argc, char *argv[])
{
    FILE *file1; //FILE* 指针作为文件句柄，是文件访问的唯一标识，它由fopen函数创建
    char message[50],plaintext[50],ciphertext[50];  //定义字符数组，fgets读入数据。message明文
    int i,lenthofmessage,key;

    file1=fopen("plaintext.txt","r"); //fopen打开文件成功，则返回一个有效的FILE*指针，否则返回空指针NULL
    //FILE *fopen（文件名字符串，打开方式串）"r"或"rt":正文文件只读方式打开
    fgets(message,50,file1); //读入数据到message，指针指到file1，以执行打开file1的动作

    printf("length of plaintext: %lu", strlen(message));   //定义为long unsigned类型，显示字符串的长度
    lenthofmessage=strlen(message);  //将上一步得到的message的长度赋值给int型的lenthofmessage

    strcpy(plaintext,message);  //strcpy的用法，将str2的字符串复制到str1中。 将message复制到plaintext中
    printf("\nplaintext is:");
    for (i=0;i<lenthofmessage;i++)   printf("%c",plaintext[i]);  //按message的长度，逐字输出

    printf("\nPlease input the key:");   //输入凯撒密码的密钥

    scanf("%d",&key);

    i=0;
    while (i<lenthofmessage)     //逐位循环
    {
        if (plaintext[i]>='A'&&plaintext[i]<='Z')       //字母控制在A～Z
            ciphertext[i]='A'+(plaintext[i]-'A'+key)%26;   //加密：c=m+key(mod 26)

        else if (plaintext[i]>='a'&&plaintext[i]<='z')
            ciphertext[i]='a'+(plaintext[i]-'a'+key)%26;

//			else if (plaintext[i]==' ')    ciphertext[i]=' ';
        else ciphertext[i]=plaintext[i];
        i++;
    }
    ciphertext[i]='\0';

    printf("\n");
    printf("ciphertext:");
    i=0;
    for (i=0;i<=lenthofmessage;i++)   printf("%c",ciphertext[i]);
    fclose(file1);
    getchar();
    return 0;
}

8.2多表代换

#include <iostream>
#include <string>
#include <memory.h>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cmath>
using namespace std;

//定义一些常变量
const int M = 26;   //定义集合{a,b,...,z}的26个英文字母

//行和列均为5
const int ROW = 5;
const int COL = 5;

//定义5*5的加密矩阵
int K[ROW][COL];

//定义5*5的解密矩阵
int D[ROW][COL];

int P[ROW];  //明文单元
int C[ROW];  //密文单元
int F[ROW];  //密文解密后的单元

//三元组gcd(a,b) = ax + by = d
struct GCD
{
    int x;
    int y;
    int d;
};

class Hill_Cipher
{
public:
    //产生随机矩阵
    void random_Matrix();
    //求矩阵的行列式
    int Det(int matrix[ROW][ROW],int row);

    //求两个数的最大公约数
    int gcd(int a,int b);

    /*
     *判断矩阵K是否在模26的情况下可逆
     *因为矩阵在模26的情形下存在可逆矩阵的充分必要条件是
     *gcd(det K,26) = 1
     */
    bool Inverse(int matrix[ROW][ROW]);

    //矩阵相乘
    void multiphy(int matrix[ROW][ROW],int p[ROW],int row);

    //求出伴随矩阵
    void adjoint_matrix(int matrix[ROW][ROW],int row);

    //将明文加密为密文
    string encryption(string plaintext);

    //将密文解密为明文(为了辨识清楚,我们统一以小写字母作为明文,大写字母作为密文)
    string deciphering(string ciphertext);

    //欧几里得算法求模的逆
    GCD extended_Euclid(int a,int b);

    //模逆运算
    int inverse(int a,int m);

    //由于C++不存在负数取模的内置函数,现在自己设定一个
    //定义一个模M的值
    int Mod(int a);
};

void Hill_Cipher::random_Matrix()
{
    int i,j;
    for(i = 0;i < ROW;i++)
    {
        for(j = 0;j < COL;j++)
        {
            K[i][j] = rand() % 26;  //产生一个5*5模26的矩阵
        }
    }
    cout << "随机产生5*5的矩阵:" << endl;
    for(i = 0;i < ROW;i++)
    {
        for(j = 0;j < COL;j++)
        {
            printf("%2d  ",K[i][j]);
        }
        cout << endl;
    }
}

//求矩阵的行列式
int Hill_Cipher::Det(int matrix[ROW][ROW],int row)
{
    int i,j;
    int cofa[ROW][ROW];            //用于存放余子阵
    int l;   //l为所递归的余子阵的行
    int p = 0,q = 0;
    int sum=0;

    //由于行和列相同(方阵),所以行列式的值一定存在,故不需要判断是否为方阵

    //递归基
    if(row == 1)
        return matrix[0][0];
    for(i = 0;i < row; i++)
    {
        for(l = 0;l < row - 1;l++)
        {
            if(l < i)
                p=0;
            else
                p=1;
            for(j = 0;j< row - 1;j++)
            {
                cofa[l][j] = matrix[l + p][j + 1];
            }
        }
        //相当于(-1)^i
        if(i % 2 == 0)
            q=1;
        else
            q=(-1);
        sum = sum + matrix[i][0] * q * Det(cofa,row - 1);
    }
    return sum;
}

//求两个数的最大公约数
int Hill_Cipher::gcd(int a,int b)
{
    int temp;
    //交换两个数的大小,使得a为较大数
    if(a < b)
    {
        temp = a;
        a = b;
        b = temp;
    }
    while(a % b)
    {
        temp = b;
        b = a % b;
        a = temp;
    }
    return b;
}

/*
 *判断矩阵K是否在模26的情况下可逆
 *因为矩阵在模26的情形下存在可逆矩阵的充分必要条件是
 *gcd(det K,26) = 1
 */
bool Hill_Cipher::Inverse(int matrix[ROW][ROW])
{
    if(gcd(Det(matrix,ROW),M) == 1)
        return true;
    else
        return false;
}

void Hill_Cipher::multiphy(int matrix[ROW][ROW],int p[ROW],int row)
{
    int i,j;
    //先将密文单元清零
    memset(C,0,sizeof(C));
    for(i = 0;i < ROW;i++)
    {
        for(j = 0;j < ROW;j++)
        {
            C[i] += P[j] * K[j][i];
        }
    }
}

//将明文加密为密文
string Hill_Cipher::encryption(string plaintext)
{
    int i;
    string ciphertext;
    //将字符串转化为明文数组
    for(i = 0;i < ROW;i++)
    {
        P[i] = plaintext[i] - 'a';
    }
    multiphy(K,P,ROW);
    //将密文数组转化为密文
    for(i = 0;i < ROW;i++)
        //这里先将其模26,再翻译为对应的字母
    {
        C[i] =Mod(C[i]);
        ciphertext += C[i] + 'A';
    }
    return ciphertext;
}

//求出伴随矩阵
void Hill_Cipher::adjoint_matrix(int matrix[ROW][ROW],int row)
{
    int i,j,k,l;
    int p,q;
    p = q = 0;
    int temp[ROW][ROW];
    for(i = 0;i < ROW;i++)
    {
        for(j = 0;j < ROW;j++)
        {
            for(k = 0;k < ROW - 1;k++)
            {
                if(k < i)
                    p = 0;
                else
                    p = 1;
                for(l = 0;l < ROW - 1;l++)
                {
                    if(l < j)
                        q = 0;
                    else
                        q = 1;
                    temp[k][l] = matrix[k+p][l+q];
                }
            }
            D[j][i] = (int)pow(-1,(double)i+j)*Det(temp,ROW-1);
            D[j][i] = Mod(D[j][i]);
        }
    }
}

//将密文解密为明文(为了辨识清楚,我们统一以小写字母作为明文,大写字母作为密文)
string Hill_Cipher::deciphering(string ciphertext)
{
    //求出矩阵的逆
    string text;
    int determinant = Det(K,ROW);
    int inver = inverse(determinant,26);
    adjoint_matrix(K,ROW);   //伴随矩阵
    cout << "行列式的值: " << determinant << endl;
    int i,j;
    memset(F,0,sizeof(F));
    for(i = 0;i < ROW;i++)
    {
        for(j = 0;j < ROW;j++)
        {
            F[i] += C[j] * D[j][i];
        }
        F[i] *= inver;
        F[i] = Mod(F[i]);   //算到的结果要模去26
    }
    for(i = 0;i < ROW;i++)
        text += F[i] + 'a';
    return text;
}

GCD Hill_Cipher::extended_Euclid(int a,int b)
{
    GCD aa,bb;
    if(b == 0)
    {
        aa.x = 1;
        aa.y = 0;
        aa.d = a;
        return aa;
    }
    else
    {
        bb = extended_Euclid(b,a%b);
        aa.x = bb.y;
        aa.y = bb.x - (a / b) * bb.y;
        aa.d = bb.d;
    }
    return aa;
}

int Hill_Cipher::inverse(int a,int m)
{
    GCD aa;
    aa = extended_Euclid(a,m);
    return aa.x;
}

int Hill_Cipher::Mod(int a)
{
    return a >= 0 ? a % M : (M + a % M);
}

int main()
{
    int i,j;
    Hill_Cipher hh;
    cout << "使用希尔密码进行消息的加解密:" << endl;

    //srand()函数产生一个以当前时间开始的随机种子.以保证每次产生的随机数矩阵都不相同
    srand((unsigned)time(0));
    hh.random_Matrix();
    while(!hh.Inverse(K))
    {
        cout << "该矩阵模26不可逆,不可以作为密钥!" << endl;
        cout << endl;
        hh.random_Matrix();
    }
    cout << "该矩阵模26可逆,因此可以作为密钥." << endl;
    cout << endl;

    //利用所选密钥，对给定的5元明文信息进行加解密
    string plaintext,ciphertext;
    cout << "请输入5元明文信息，仅支持小写字母，无空格:" << endl;
    cin >> plaintext;
    ciphertext = hh.encryption(plaintext);
    cout << endl;
    cout << "该明文通过希尔密码法加密过后,输出的密文消息以大写方式输出为:" << endl;
    cout << ciphertext << endl;
    cout << endl;

    cout << "***输入0:退出          ***" << endl;
    cout << "***输入1:查看明文空间对***" << endl;
    cout << "***输入2:查看密文空间对***" << endl;
    cout << "***输入3:查看密钥      ***" << endl;
    cout << "***输入4:将消息解密    ***" << endl;
    cout << "***输入5:查看菜单      ***" << endl;

    char c;
    while(cin >> c)
    {
        if(c == '0')
        {
            cout << endl;
            cout << "退出" << endl;
            break;
        }
        else if(c == '1')
        {
            cout << "明文空间:" << endl;
            for(i = 0;i < ROW;i++)
                cout << P[i] << "  ";
            cout << endl;
            cout << endl;
        }
        else if(c == '2')
        {
            cout << "密文空间:" << endl;
            for(i = 0;i < ROW;i++)
                cout << C[i] << "  ";
            cout << endl;
            cout << endl;
        }
        else if(c == '3')
        {
            cout << "密钥:" << endl;
            for(i = 0;i < ROW;i++)
            {
                for(j = 0;j < ROW;j++)
                {
                    printf("%2d  ",K[i][j]);
                }
                cout << endl;
            }
            cout << endl;
        }
        else if(c == '4')
        {
            hh.adjoint_matrix(K,ROW);
            string ss;
            ss = hh.deciphering(ciphertext);
            cout << "该密文解密过后,显示的原来的明文消息:" << endl;
            cout << ss << endl;
            cout << endl;
        }
        else
        {
            cout << "***输入0:退出          ***" << endl;
            cout << "***输入1:查看明文空间对***" << endl;
            cout << "***输入2:查看密文空间对***" << endl;
            cout << "***输入3:查看密钥      ***" << endl;
            cout << "***输入4:将消息解密    ***" << endl;
            cout << "***输入5:查看菜单      ***" << endl;
        }
    }
    return 0;
}