[C++] 유한체 AES 역 행렬, 역 S-box
oolongeya
·2021. 9. 27. 18:27
역 S-box
|
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
|
#include <iostream>
typedef unsigned char byte;
// GF(2^8) add func
byte GF_add(byte gf1, byte gf2) {
return gf1 ^ gf2; // xor
}
// GF(2^8) xtime() func
byte GF_xtime(byte gf) {
int msb; //x^7의 계수 (최고차항)
byte result;
msb = (gf >> 7) & 0x01;
if (msb == 1) {
result = (gf << 1) ^ 0x1b;
}
else {
result = gf << 1;
}
return result;
}
// GF(2^8) xtime() func
byte GF_xtime_simple(byte gf) {
return ((gf >> 7) & 0x01 == 1 ? (gf << 1) ^ 0x1b : gf << 1);
}
// GF(2^8) multi
// f(x) = a0 + a1*x + a2*x^2 + a3*x^3 + ... + a7*x^7
// h(x) = g(x)*f(x)
// = g(x)*a0 + g(x)*a1*x + g(x)*a2*x^2 + g(x)*a3*x^3 + ... + g(x)*a7*x^7
// = g(x)*a0 + x*( g(x)*a1 + g(x)*a2*x + g(x)*a3*x^2 + ... + g(x)*a7*x^6 )
// = g(x)*a0 + x*( g(x)*a1 + x* (g(x)*a2 + g(x)*a3*x + ... + g(x)*a7*x^5 ))
// = g(x)*a0 + x*( ... x*( g(x)*a7 ) )
byte GF_mul(byte f, byte g) {
byte h; // 곱셈 결과 h(x) = f(x) * g(x)
int coef; // 계수
h = 0x00;
for (int i = 7; i >= 0; i--) {
coef = (f >> i) & 0x01; // a7, a6, a5, ... a0
h = GF_xtime(h);
if (coef == 1) {
h = GF_add(h, g);
}
}
return h;
}
// GF(2^8) 역원
// ( a^255 = 1 )임을 이용한다.
// a^(-1) = a^(254) = a^2*a^4*a^8*a^16... *a^128
// = a^(1111 1110) = a^(1000 0000) * a^(0100 0000) ... * a^(0000 0010)
byte GF_inv(byte f) {
byte f_inv; // 역원 (결과값)
byte temp; // 중간에 곱할 값 (a^n) a^2, a^4, a^8, a^16, ... a^128
f_inv = 1;
temp = f;
for (int i = 0; i < 7; i++) {
temp = GF_mul(temp, temp);
f_inv = GF_mul(f_inv, temp);
}
return f_inv;
}
// AES Affine Aw+b (Affine 변화)
// w = x^(-1)
byte AES_Affine(byte w) {
byte A[8][8] =
{
{1, 0, 0, 0, 1, 1, 1, 1},
{1, 1, 0, 0, 0, 1, 1, 1},
{1, 1, 1, 0, 0, 0, 1, 1},
{1, 1, 1, 1, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0, 0},
{0, 0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 1, 1, 1, 1, 1}
};
byte b_vec[8] = { 1, 1, 0, 0, 0, 1, 1, 0 };
byte w_vec[8], y_vec[8], y;
for (int i = 0; i < 8; i++) {
w_vec[i] = (w >> i) & 0x01;
}
for (int i = 0; i < 8; i++) {
y_vec[i] = b_vec[i];
for (int j = 0; j < 8; j++) {
y_vec[i] ^= A[i][j] * w_vec[j]; //b 에다가 행렬곱을 더해준 것
}
}
y = 0;
byte temp_bit;
for (int i = 0; i < 8; i++) {
temp_bit = y_vec[i] << i;
y ^= temp_bit;
}
return y;
}
// AES S-box
void Get_AES_Sbox(byte sbox[256]) {
byte temp;
// 0^(-1) = 0 으로 간주한다.
sbox[0] = AES_Affine(0);
for (int i = 1; i < 256; i++) {
temp = GF_inv(i);
sbox[i] = AES_Affine(temp);
}
}
// AES Inverse S-box
void Get_AES_Inv_Sbox(byte invsbox[256]) {
byte Sbox[256];
Get_AES_Sbox(Sbox);
for (int i = 0; i < 256; i++) {
invsbox[Sbox[i]] = i;
}
}
void Sbox_test() {
byte Sbox[256];
Get_AES_Sbox(Sbox);
std::cout << "Sbox = \n";
printf("-----------------------------------------------");
for (int i = 0; i < 256; i++) {
if ((i % 16) == 0) {
printf("\n");
}
printf("%02x ", Sbox[i]);
}
printf("\n-----------------------------------------------");
printf("\n");
byte invSbox[256];
Get_AES_Inv_Sbox(invSbox);
std::cout << std::endl << "Inverse Sbox = \n";
printf("-----------------------------------------------");
for (int i = 0; i < 256; i++) {
if ((i % 16) == 0) {
printf("\n");
}
printf("%02x ", invSbox[i]);
}
printf("\n-----------------------------------------------");
printf("\n");
}
int main()
{
Sbox_test();
return 0;
}
|
cs |
역 행렬
|
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
|
// matrix_struct.cpp : 구조체를 이용한 행렬
#include <iostream>
#define MAX 10
#define NEARLY_ZERO 1e-10
using namespace std;
struct Matrix {
double M[MAX][MAX];
int row;
int col;
};
void Mat_print(Matrix M) {
for (int i = 0; i < M.row; i++) {
printf("[");
for (int j = 0; j < M.col; j++) {
printf("%7.3f", M.M[i][j]);
}
printf(" ]\n");
}
printf("\n");
}
void Mat_Mul_1(Matrix A, Matrix B, Matrix &AB) { // Matrix &AB : Call by reference
if (A.col != B.row) {
cout << "Matrix size error!\n";
return;
}
AB.row = A.row;
AB.col = B.col;
for (int i = 0; i < AB.row; i++) {
for (int j = 0; j < AB.col; j++) {
AB.M[i][j] = 0.0;
for (int k = 0; k < A.col; k++) {
AB.M[i][j] += A.M[i][k] * B.M[k][j];
}
}
}
}
Matrix Mat_Mul(Matrix A, Matrix B) { // return Matrix
Matrix AB;
if (A.col != B.row) {
cout << "Matrix size error!\n";
}
AB.row = A.row;
AB.col = B.col;
for (int i = 0; i < AB.row; i++) {
for (int j = 0; j < AB.col; j++) {
AB.M[i][j] = 0.0;
for (int k = 0; k < A.col; k++) {
AB.M[i][j] += A.M[i][k] * B.M[k][j];
}
}
}
return AB;
}
Matrix Mat_init() {
Matrix M;
M.row = MAX;
M.col = MAX;
for (int i = 0; i < M.row; i++) {
for (int j = 0; j < M.col; j++) {
M.M[i][j] = (i == j) ? 1.0 : 0.0;
}
}
return M;
}
// 역행렬
// - 행교환
// - 한 행 x k배 (scalar Mul)
// - 행x k배 => 다른행 +
void Mat_Exchange_Row(Matrix &A, int row1, int row2) {
double temp;
for (int i = 0; i < A.col; i++) {
temp = A.M[row1][i];
A.M[row1][i] = A.M[row2][i];
A.M[row2][i] = temp;
}
}
void Mat_Scalar_Mul(Matrix &A, double scalar, int row) {
for (int i = 0; i < A.col; i++) {
A.M[row][i] *= scalar;
}
}
void Mat_Row_Add(Matrix &A, double scalar, int row_src, int row_target) {
for (int i = 0; i < A.col; i++) {
A.M[row_target][i] += scalar * A.M[row_src][i];
}
}
Matrix Mat_inverse(Matrix A) {
Matrix AA; // [A | 1]
AA.row = A.row;
AA.col = A.col * 2;
for (int i = 0; i < A.row; i++) {
for (int j = 0; j < A.col; j++) {
AA.M[i][j] = A.M[i][j];
AA.M[i][A.col + j] = (i == j) ? 1.0 : 0.0;
}
}
int pivot_row;
for (int j = 0; j < A.col; j++) {
pivot_row = -1;
for (int i = j; i < A.row; i++) {
if ( abs(AA.M[i][j]) > NEARLY_ZERO ) {
pivot_row = i;
break;
}
}
if (pivot_row == -1) {
cout << "Not invertible!\n";
return A; // 어차피 무의미
}
if (pivot_row != j) { // j번째 행 <-> pivot 행
Mat_Exchange_Row(AA, j, pivot_row);
}
Mat_Scalar_Mul(AA, 1 / AA.M[j][j], j);
for (int i = 0; i < A.row; i++) {
if ( (i != j) && (abs(AA.M[i][j]) > NEARLY_ZERO)) {
Mat_Row_Add(AA, -AA.M[i][j], j, i);
}
}
}
Matrix Inv;
Inv.row = A.row;
Inv.col = A.col;
for (int i = 0; i < A.row; i++) {
for (int j = 0; j < A.col; j++) {
Inv.M[i][j] = AA.M[i][j + A.col];
}
}
return Inv;
}
void Run_Matrix_Test() {
Matrix MA, MB, MC;
MA.row = 3; MA.col = 3;
MB.row = 3; MB.col = 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
MA.M[i][j] = i + j;
MB.M[i][j] = j;
}
}
//MA = Mat_init();
Mat_print(MA);
Mat_print(MB);
//Mat_Mul_1(MA, MB, MC);
MC = Mat_Mul(MA, MB);
Mat_print(MC);
}
void Run_Matrix_Inverse_Test() {
Matrix A, InvA;
double Data[4][4] = { {2, 3, 5, 1}, {1, 2, 3, 5}, {5, 1, 2, 3}, {3, 5, 1, 2} };
A.row = 4;
A.col = 4;
for (int i = 0; i < A.row; i++) {
for (int j = 0; j < A.col; j++) {
A.M[i][j] = Data[i][j];
}
}
Mat_print(A);
InvA = Mat_inverse(A);
Mat_print(InvA);
}
int main()
{
//Run_Matrix_Test();
Run_Matrix_Inverse_Test();
}
|
cs |
반응형
'암호학 (Cryptology) > code' 카테고리의 다른 글
| [C++] 블록암호 구현 - 패딩 (Padding) (0) | 2021.12.12 |
|---|---|
| [C++] 유한체 연산 & 다항식 연산 (S-box 구현 원리) (0) | 2021.09.14 |
| [Python3] AES-128 암호화 구현 (0) | 2021.08.17 |
| [Python3] 블록 암호 및 스트림 암호 (차분 공격 - DDT 구현) (0) | 2021.08.17 |
