Bxb0's blog

应用密码学

Posted on In
Symbols count in article: 6.9k Reading time ≈ 6 mins.

记录一下应用密码学课程的代码作业及实验。

Vigenere Cipher

C语言简单实现：

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
#include <stdio.h>

int main(void)
{
	int i = 0;
	char plain[] = "blockchaintechnology", plain_order[100];
	char key[] = "cuitbo", key_order[100];
	char enc[100], enc_order[100];

	for(i = 0; i < sizeof(plain)-1; i++)
	{
		plain_order[i] = plain[i]-97;
		key_order[i] = key[i%6]-97;
		enc_order[i] = (plain_order[i]+key_order[i])%26;
	}
	printf("plain: %s\n", plain);
	printf("enc: %s\n", key);
	
	printf("plain_order: ");
	for(i = 0; i < sizeof(plain)-1; i++)
		printf("%d ", plain_order[i]);
	putchar(10);
	
	printf("enc_order: ");
	for(i = 0; i < sizeof(plain)-1; i++)
		printf("%d ", enc_order[i]);
	putchar(10);
	
	printf("enc: ");
	for(i = 0; i < sizeof(plain)-1; i++)
		printf("%c ", enc_order[i]+97);
	
}

AES 变换操作的实现

用C语言简单实现一下加密的几个过程：

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
#include <stdio.h>

void getData_76(unsigned char (*data_76)[4]);
void printOut_76(unsigned char (*data_76)[4]);
void SubBytes_76(unsigned char (*state_76)[4]);
void AddRoundKey_76(unsigned char (*state_76)[4], unsigned char (*RoundKey_76)[4]);
void ShiftRows_76(unsigned char (*state_76)[4]);
void mix_columns_76(unsigned char (*state_76)[4], unsigned char (*output_76)[4]);
unsigned char gfmultby_76(unsigned char a, unsigned char b);

static unsigned char Sbox_76[256] = {
	// 0     1     2     3     4     5     6     7     8     9     a     b     c     d     e     f
	0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, // 0
	0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, // 1
	0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, // 2
	0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, // 3
	0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, // 4
	0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, // 5
	0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, // 6
	0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, // 7
	0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, // 8
	0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, // 9
	0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, // a
	0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, // b
	0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, // c
	0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, // d
	0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, // e
	0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16};// f


unsigned char mixValue_76[4][4] = {02, 03, 01, 01,
								   01, 02, 03, 01,
								   01, 01, 02, 03,
								   03, 01, 01, 02
};
int main(void)
{
	unsigned char state_76[4][4] = {0};
	unsigned char output_76[4][4] = {0};
	unsigned char RoundKey_76[4][4] = {0};
	
	puts("明文：");
	getData_76(state_76);

	puts("密钥：");
	getData_76(RoundKey_76);
	
	puts("输入明文状态矩阵：");
	printOut_76(state_76);

	puts("输入128比特初始密钥矩阵：");
	printOut_76(RoundKey_76);
	
	puts("轮密钥运算输出：");
	AddRoundKey_76(state_76, RoundKey_76);
	printOut_76(state_76);

	puts("字节替代输出：");
	SubBytes_76(state_76);
	printOut_76(state_76);

	puts("行移位输出：");
	ShiftRows_76(state_76);
	printOut_76(state_76);
	
	puts("列混合输出：");
	mix_columns_76(state_76, output_76);
	printOut_76(output_76);


}

void getData_76(unsigned char (*data_76)[4])
{
	int i_76, j_76;
	unsigned char input_76[32];

	for(i_76 = 0; i_76 < 16; i_76++)
		scanf("%p", input_76+i_76);
	for(i_76 = 0; i_76 < 4; i_76++)
	{
		for(j_76 = 0; j_76 < 4; j_76++)
		{
			data_76[j_76][i_76] = input_76[4*i_76+j_76];
		}
	}

}

void printOut_76(unsigned char (*data_76)[4])
{
	int i_76, j_76;

	for(i_76 = 0; i_76 < 4; i_76++)
	{
		for(j_76 = 0; j_76 < 4; j_76++)
			printf("%02X ", data_76[i_76][j_76]);
		putchar(10);
	}
}

void SubBytes_76(unsigned char (*state_76)[4])
{
	int i_76, j_76;

	for(i_76 = 0; i_76 < 4; i_76++)
	{
		for(j_76 = 0; j_76 < 4; j_76++)
		{
			state_76[i_76][j_76] = Sbox_76[state_76[i_76][j_76]];
		}
	}	
}

void AddRoundKey_76(unsigned char (*state_76)[4], unsigned char (*RoundKey_76)[4])
{
	int i_76, j_76;

	for(i_76 = 0; i_76 < 4 ;i_76++)
	{
		for(j_76 = 0; j_76 < 4; j_76++)
		{
			state_76[i_76][j_76] ^=  RoundKey_76[i_76][j_76];
		}
	}
}

void ShiftRows_76(unsigned char (*state_76)[4])
{
	int i_76, j_76, cnt_76, tmp_76;

	for(i_76 = 1; i_76 < 4; i_76++)
	{
		cnt_76 = 0;
		while(cnt_76++ < i_76)
		{
			tmp_76 = state_76[i_76][0];
			for(j_76 = 1; j_76 < 4; j_76++)
			{
				state_76[i_76][j_76-1] = state_76[i_76][j_76];
			}
			state_76[i_76][j_76-1] = tmp_76;
		}
	}
}

unsigned char gfmultby_76(unsigned char a_76, unsigned char b_76)
{
	unsigned char tmp_76 = a_76 > 0x80 ? (unsigned char)((a_76<<1)^0x1b):(unsigned char)(a_76 << 1);
	if(b_76 == 1)
		return a_76;
	else if(b_76 == 2)
		return tmp_76;
	else
		return tmp_76^a_76;
}


void mix_columns_76(unsigned char (*state_76)[4], unsigned char (*output_76)[4])
{
	int i_76, j_76, k_76;

	for(i_76 = 0; i_76 < 4; i_76++)
	{
		for(j_76 = 0; j_76 < 4; j_76++)
		{
			for(k_76 = 0; k_76 < 4; k_76++)
			{
				output_76[i_76][j_76] ^= gfmultby_76(state_76[k_76][j_76], mixValue_76[i_76][k_76]);
			}
		}
		
	}
}

RSA 模幂运算的实现

按照平方乘算法和模重复平方法，分别计算a^n mod n

1.平方乘算法。

计算整体思想：先平方再乘。

  • 先将指数转化为二进制形式。
  • 从指数的二进制高位到低位依次计算。
  • 初始化设置，b1 == 1 ,扫描第一个bit时不需要做其他操作。
  • 随后若bi == 1，则平方上一次的结果后再乘x（底数）；若bi == 0，只需要对上一次的结果平方一次即可。

理解：一次平方操作会让指数向左移一位，并在最右边添加0，而与x（底数）相乘的操作即在指数的最右边位置上填上 1，这样完成后也是得到指数的二进制位了。

这里贴一下网上看到一张图：

image-20210417144224324

C语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int LRFun_76(int a_76, int m_76, int n_76)
{
	int ans_76 = 1, s_76[100] = {0}, cnt_76 = 0, i_76 = 0;
	
	while(m_76)
	{
		s_76[cnt_76++] = m_76&1;
		m_76 >>= 1;
	}

	while(--cnt_76 >= 0)
	{
		ans_76 = (ans_76*ans_76*(int)pow(a_76, s_76[cnt_76]))%n_76;
		printf("i = %d, b = %d, ans_76 = ans_76*ans_76*a_76^%d(mod %d) = %d\n", i_76++, s_76[cnt_76], s_76[cnt_76], n_76, ans_76);
	}
	
	printf("结果为：%d\n", ans_76);
	return ans_76;

}

2.模重复平方法。

计算整体思想：将指数分为多个2次方相加的形式，然后重复平方。

也是先将指数转化位二进制的形式，然后从低位开始，依次计算，下面的n1是每个二进制位，表示是0或者1。

image-20210417163737881

其中的重复重复平方是每轮都要进行的，只是根据指数的二进制位的0来决定是否将其乘到结果中去。

C语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int powerMod_76(int a_76, int m_76, int n_76)
{
	int ans_76 = 1, s_76[100] = {0}, i_76 = 0;

	for(; m_76; m_76 >>= 1, i_76++)
	{
		int tmp_76 = m_76&1;
		ans_76 = (ans_76*(int)pow(a_76, tmp_76))%n_76;
		printf("i = %d: b = %d, ans_76 = ans_76*a_76^%d(mod %d) = %d\n", i_76, tmp_76, tmp_76, n_76, ans_76);

		a_76 = (a_76*a_76)%n_76;
		printf("i = %d: a_76 = a_76*a_76(mod %d) = %d\n", i_76, n_76, a_76);
	}

	printf("结果为：%d\n", ans_76);

	return ans_76;	
}

最后，main函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main(void)
{
	int a_76, m_76, n_76;

	printf("请输入数字（a, m, n）:");
	scanf("%d %d %d", &a_76, &m_76, &n_76);
	
	puts("用平方乘算法的计算过程为：");
	LRFun_76(a_76, m_76, n_76);
	putchar(10), putchar(10);
	
	puts("用模重复平方法的计算过程为：");
	powerMod_76(a_76, m_76, n_76);

	return 0;
}
-------------本文结束感谢您的阅读-------------