Mosquitoの世界
首页 标签 归档 分类 友链 关于

两种古典密码：Hill和Affine密码 —— 基于Java实现

2022-04-10 密码学
文章目录
  1. Hill密码
  2. Affine密码

本文最后更新于 <span id="expire-date"></span> 天前，文中部分描述可能已经过时。

Hill密码

阶数增加到5会导致逆矩阵难以用整数精确表示，故姑且暂用3阶矩阵

若有原矩阵与逆矩阵皆为整数的矩阵对，亦可行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
import java.util.HashMap;
import java.util.Scanner;

public class Hill {
    public static Scanner in = new Scanner(System.in);
    public static final HashMap<Integer, Character> map1 = new HashMap<>();
    public static final HashMap<Character, Integer> map2 = new HashMap<>();
    public static final int[][] EncryptKey = new int[][]{{1, 2, 3}, {1, 1, 2}
    , {0, 1, 2}};
    public static final int N = 3; //阶数
    public static final int k = modInverse(determinantOfMatrix(EncryptKey, N)); //求行列式关于26的模逆
    public static final int[][] adj = adjoin(EncryptKey); //伴随矩阵
    public static final int[][] DecryKey = getDecryptKey(adj, k);// 解密密钥

    public static void main(String[] argv) {
        match();//数字字母转换
        System.out.println("==========================加密过程==========================");
        System.out.println("加密密钥矩阵为：");
        printMatrix(EncryptKey);
        System.out.println("请输入明文：");
        String plain;
        plain = in.nextLine();
        plain = upper(plain);
        encrypt(plain);
        System.out.println("==========================解密过程==========================");
        System.out.println("解密密钥矩阵为");
        printMatrix(DecryKey);
        System.out.println("请输入密文：");
        String cipher = in.nextLine();
        while (cipher.length() % N != 0) {
            System.out.println("密文长度不正确，请重新输入：");
            cipher = in.nextLine();
        }
        cipher = upper(cipher);
        decrypt(cipher);

    }




    //数字和字母相互转换
    public static void match() {
        for (int i = 0; i < 26; i++) {
            map1.put(i, (char) (i + 65));
        }
        for (char i = 'A'; i <= 'Z'; i++) {
            map2.put(i, i - 'A');
        }
    }

    public static String upper(String s) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ')
                continue;
            ch = Character.toUpperCase(ch);
            res.append(ch);
        }
        return res.toString();
    }

    public static void encrypt(String s) {
        int n = s.length() % N == 0 ? s.length() / N : s.length() / N + 1;
        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            StringBuilder temp = new StringBuilder();
            for (int j = N * i; j < s.length() && j < N * i + N; j++) {
                temp.append(s.charAt(j));
            }
            while (temp.length() % N != 0) {
                temp.append("X");
            }
            arr[i] = temp.toString();
        }
        StringBuilder res = new StringBuilder();
        for (String i : arr) {
            int[] nums = new int[N];
            for (int j = 0; j < N; j++) {
                char ch = i.charAt(j);
                nums[j] = map2.get(ch);
            }
            int[] result = new int[N];
            for (int j = 0; j < N; j++) {
                result[j] = nums[0] * EncryptKey[0][j] + nums[1] * EncryptKey[1][j] +
                        nums[2] * EncryptKey[2][j] ;
                result[j] %= 26;
                res.append(map1.get(result[j]));
            }

        }
        System.out.println("密文为：");
        System.out.println(res);
    }

    public static void decrypt(String s) {
        int n = s.length() / N;
        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            StringBuilder temp = new StringBuilder();
            for (int j = N * i; j < s.length() && j < N * i + N; j++) {
                temp.append(s.charAt(j));
            }
            arr[i] = temp.toString();
        }
        StringBuilder res = new StringBuilder();
        for (String i : arr) {
            int[] nums = new int[N];
            for (int j = 0; j < N; j++) {
                nums[j] = map2.get(i.charAt(j));
            }
            int[] result = new int[N];
            for (int j = 0; j < N; j++) {
                result[j] = nums[0] * DecryKey[0][j] + nums[1] * DecryKey[1][j] +
                        nums[2] * DecryKey[2][j] ;
                result[j] %= 26;
                res.append(map1.get(result[j]));
            }

        }
        System.out.println("明文为：");
        System.out.println(res);
    }

    public static void printMatrix(int[][] a) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.printf("%-5d", a[i][j]);
            }
            System.out.println();
        }
    }

    public static void getCofactor(int[][] mat, int[][] temp, int p, int q, int n) {
        int i = 0, j = 0;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (row != p && col != q) {
                    temp[i][j++] = mat[row][col];
                    if (j == n - 1) {
                        j = 0;
                        i++;
                    }
                }
            }
        }
    }

    //求矩阵的行列式
    public static int determinantOfMatrix(int[][] mat, int n) {
        int D = 0;
        if (n == 1)
            return mat[0][0];
        int[][] temp = new int[N][N];
        int sign = 1;
        for (int f = 0; f < n; f++) {
            getCofactor(mat, temp, 0, f, n);
            D += sign * mat[0][f]
                    * determinantOfMatrix(temp, n - 1);
            sign = -sign;
        }
        return D;
    }

    //求26的模逆
    public static int modInverse(int a) {
        for (int x = 1; x < 26; x++)
            if (((a % 26) * (x % 26)) % 26 == 1)
                return x;
        return 1;
    }

    //求伴随矩阵
    public static int[][] adjoin(int[][] A) {
        int[][] adj = new int[N][N];
        int sign = 1;
        int[][] temp = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                getCofactor(A, temp, i, j, N);
                sign = ((i + j) % 2 == 0) ? 1 : -1;
                adj[j][i] = (sign) * (determinantOfMatrix(temp, N - 1));
            }
        }
        return adj;
    }

    //求解密密钥矩阵
    public static int[][] getDecryptKey(int[][] matrix, int det) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = -matrix[i][j] * det;
                matrix[i][j] = (matrix[i][j] + 2600) % 26;
            }
        }
        return matrix;
    }
}

Affine密码

in.nextInt()和in.nextLine()之间必须要有in.nextLine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import java.util.HashMap;
import java.util.Scanner;

public class Affine {
    public static final HashMap<Integer, Character> map1 = new HashMap<>();
    public static final HashMap<Character, Integer> map2 = new HashMap<>();
    public static Scanner in = new Scanner(System.in);
    /*
    * k1 ∈ {1, 3, 5, 7, 9, 11, 15, 17, 19 , 21, 23, 25},与26互素
    *k2 ∈ [0, 25]
    */
    public static void main(String[] args) {
        match();
        System.out.println("请输入密钥K1:");
        int k1 = in.nextInt();
        while(gcd(k1, 26) != 1){
            System.out.println("该数与26不互素,请重新输入");
            k1 = in.nextInt();
        }
        in.nextLine();
        System.out.println("密钥K1为: " + k1);
        int k1_reverse = modInverse(k1);
        System.out.println("密钥K1的逆为: " + k1_reverse);
        int k2 = (int) (Math.random() * 26);
        k2 %= 26;
        System.out.println("随机生成的密钥K2为: " + k2);
        System.out.println("==========================加密过程==========================");
        System.out.println("请输入明文: ");
        String plain = in.nextLine();
        plain = upper(plain);

        encrypt(plain, k1, k2);
        System.out.println("==========================解密过程==========================");
        System.out.println("请输入密文: ");
        String cipher = in.nextLine();
        decrypt(cipher, k1_reverse, k2);

    }

    public static void match() {
        for (int i = 0; i < 26; i++) {
            map1.put(i, (char) (i + 65));
        }
        for (char i = 'A'; i <= 'Z'; i++) {
            map2.put(i, i - 'A');
        }
    }

    //Euclid算法求最大公因数
    public static int gcd(int n1, int n2) {
        if (n2 == 0) {
            return n1;
        }
        return gcd(n2, n1 % n2);
    }
    //求26的模逆
    public static int modInverse(int a) {
        for (int x = 1; x < 26; x++)
            if (((a % 26) * (x % 26)) % 26 == 1)
                return x;
        return 1;
    }

    public static String upper(String s) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ')
                continue;
            ch = Character.toUpperCase(ch);
            res.append(ch);
        }
        return res.toString();
    }

    public static void encrypt(String s,  int k1,  int k2){
        int[] nums = new int[s.length()];
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            nums[i] = map2.get(ch);
            nums[i] = (k1 * nums[i] + k2 + 2600) % 26;
            res.append(map1.get(nums[i]));
        }
        System.out.println("密文为:");
        System.out.println(res);
    }

    public static void decrypt(String s, int k1, int k2){
        int[] nums = new int[s.length()];
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            nums[i] = map2.get(ch);
            nums[i] = ((nums[i] - k2) * k1 + 2600 ) % 26;
            res.append(map1.get(nums[i]));
        }
        System.out.println("明文为:");
        System.out.println(res);
    }
}

本文作者：Mosquito

本文链接： http://example.com/2022/04/10/%E5%8F%A4%E5%85%B8%E5%AF%86%E7%A0%81/

Mosquito 天使之吻手打

文章默认使用 CC BY-NC-SA 4.0 协议进行许可，使用时请注意遵守协议。

更新于 2022-08-05

# 密码学
上一篇
背包问题
下一篇
SQL语言笔记