image.png

    1. #include<bits/stdc++.h>
    2. using namespace std;
    4. //int key[3][3];
    5. int key[3][3] = {
    6.     17,17,5,
    7.     21,18,21,
    8.     2,2,19
    9. };       //加密密钥
    11. int mod26(int x)    //取模
    12. {
    13.     return x >= 0 ? (x % 26) : 26 - (abs(x) % 26);
    14. }
    16. /* 求矩阵的|A| */
    17. int findDet(int m[3][3], int n)   
    18. {
    19.     int det;
    20.     if (n == 2)       //2阶矩阵
    21.     {
    22.         det = m[0][0] * m[1][1] - m[0][1] * m[1][0];
    23.     }
    24.     else if (n == 3)  //3阶矩阵
    25.     {
    26.         det = m[0][0] * (m[1][1] * m[2][2] - m[1][2] * m[2][1])
    27.             - m[0][1] * (m[1][0] * m[2][2] - m[2][0] * m[1][2]) 
    28.             + m[0][2] * (m[1][0] * m[2][1] - m[1][1] * m[2][0]);
    29.     }
    30.     else det = 0;     // 无效输入
    31.     return mod26(det);
    32. }
    35. int findDetInverse(int R, int D = 26)   // R=|A|
    36. {
    37.     int i = 0;
    38.     int p[100] = { 0,1 };
    39.     int q[100] = { 0 };     //商
    41.     while (R != 0)
    42.     {
    43.         q[i] = D / R;
    44.         int oldD = D;
    45.         D = R;
    46.         R = oldD % R;
    47.         if (i > 1)
    48.         {
    49.             p[i] = mod26(p[i - 2] - p[i - 1] * q[i - 2]);
    50.         }
    51.         i++;
    52.     }
    53.     if (i == 1) 
    54.         return 1;
    55.     else 
    56.         return p[i] = mod26(p[i - 2] - p[i - 1] * q[i - 2]);
    57. }
    60. //矩阵乘法
    61. void multiplyMatrices(int a[1000][3], int a_rows, int a_cols, int b[1000][3], int b_rows, int b_cols, int res[1000][3])
    62. {
    63.     for (int i = 0; i < a_rows; i++)
    64.     {
    65.         for (int j = 0; j < b_cols; j++)
    66.         {
    67.             for (int k = 0; k < b_rows; k++)
    68.             {
    69.                 res[i][j] += a[i][k] * b[k][j];
    70.             }
    71.             res[i][j] = mod26(res[i][j]);
    72.         }
    73.     }
    74. }
    77. /* findInverse(输入矩阵 , 阶数 , 输出矩阵) */
    78. //矩阵的逆 
    79. void findInverse(int m[3][3], int n, int m_inverse[3][3])
    80. {
    81.     int adj[3][3] = { 0 };
    83.     int det = findDet(m, n);                  // key矩阵的行列式
    84.     int detInverse = findDetInverse(det);
    86.     if (n == 2)          //二阶矩阵的逆
    87.     {
    88.         adj[0][0] = m[1][1];
    89.         adj[1][1] = m[0][0];
    90.         adj[0][1] = -m[0][1];
    91.         adj[1][0] = -m[1][0];
    92.     }
    93.     else if (n == 3)     //三阶矩阵的逆
    94.     {
    95.         int temp[5][5] = { 0 };
    96.         //填充 5x5 矩阵
    97.         for (int i = 0; i < 5; i++)
    98.         {
    99.             for (int j = 0; j < 5; j++)
    100.             {
    101.                 temp[i][j] = m[i % 3][j % 3];
    102.             }
    103.         }
    104.         /* 除第一行和第一列外，沿行乘元素，并沿列放置元素*/
    105.         for (int i = 1; i <= 3; i++)
    106.         {
    107.             for (int j = 1; j <= 3; j++)
    108.             {
    109.                 adj[j - 1][i - 1] = temp[i][j] * temp[i + 1][j + 1] - temp[i][j + 1] * temp[i + 1][j];
    110.             }
    111.         }
    112.     }
    114.     for (int i = 0; i < n; i++)
    115.     {
    116.         for (int j = 0; j < n; j++)
    117.         {
    118.             m_inverse[i][j] = mod26(adj[i][j] * detInverse);
    119.             /* Inverse = (matrix * detInverse) mod 26 */
    120.         }
    121.     }
    122. }
    124. // C = PK
    125. string encrypt(string pt, int n)
    126. {
    127.     int P[1000][3] = { 0 };  // 明文 , 3列矩阵
    128.     int C[1000][3] = { 0 };  // 密文
    129.     int ptIter = 0;
    131.     while (pt.length() % n != 0)
    132.     {
    133.         pt += "x";       // 用x填补
    134.     }
    135.     int row = (pt.length()) / n;   // P的行数=字母个数/3(n)
    137.     for (int i = 0; i < row; i++)   
    138.     {
    139.         for (int j = 0; j < n; j++)
    140.         {
    141.             P[i][j] = pt[ptIter++] - 'a';   //明文矩阵
    142.         }
    143.     }
    145.     // multiplyMatrices(输入矩阵 , 行数 , 列数 , 密钥, 密钥行数, 密钥列数 , 结果矩阵)
    146.     //矩阵乘法
    147.     multiplyMatrices(P, row, n, key, n, n, C);    // C = PK
    149.     string ct = "";               //密文
    150.     for (int i = 0; i < row; i++)
    151.     {
    152.         for (int j = 0; j < n; j++)
    153.         {
    154.             ct += (C[i][j] + 'a');
    155.         }
    156.     }
    157.     return ct;
    158. }
    160. // P = C*(k_inverse)
    161. string decrypt(string ct, int n)
    162. {
    163.     int P[1000][3] = { 0 }; // 明文矩阵
    164.     int C[1000][3] = { 0 }; // 密文矩阵
    165.     int ctIter = 0;
    167.     int row = ct.length() / n; // 密文的行数
    169.     for (int i = 0; i < row; i++)
    170.     {
    171.         for (int j = 0; j < n; j++)
    172.         {
    173.             C[i][j] = ct[ctIter++] - 'a';
    174.         }
    175.     }
    177.     int k_inverse[3][3] = { 0 };     //密文的逆矩阵
    179.     findInverse(key, n, k_inverse);
    181.     // P = C*(k_inverse)
    182.     multiplyMatrices(C, row, n, k_inverse, n, n, P);
    184.     string pt = "";
    185.     for (int i = 0; i < row; i++)
    186.     {
    187.         for (int j = 0; j < n; j++)
    188.         {
    189.             pt += (P[i][j] + 'a');
    190.         }
    191.     }
    192.     return pt;
    193. }
    195. int main(void)
    196. {
    197.     string pt="rlx";
    199.     /*cout << "请输入要加密的明文:  ";
    200.     cin >> pt;*/
    202.     /*cout << "请输入加密矩阵的阶数: ";
    203.     cin >> n;
    205.     cout << "请输入加密矩阵(必须可逆): " << endl;
    206.     for (int i = 0; i < n; i++)
    207.     {
    208.         for (int j = 0; j < n; j++)
    209.         {
    210.             cin >> key[i][j];
    211.         }
    212.     }*/
    214.     cout << "\n明文  : " << pt << endl;
    216.     string ct = encrypt(pt, 3);
    217.     cout << "密文 : " << ct << endl;
    219.     string dt = decrypt(ct, 3);
    220.     cout << "解密t : " << dt << endl;
    221. }