-
Notifications
You must be signed in to change notification settings - Fork 54
/
Affine.c
149 lines (127 loc) · 2.7 KB
/
Affine.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
/*
* Affine Cipher
*
* @author lellansin <lellansin@gmail.com>
* @website http://www.lellansin.com/tutorials/ciphers
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define WIDTH 26
int gcd(int a, int b);
char shift(int *key, char ch);
char unshift(int *key, char ch);
int modInverse(int a, int m);
/*
* 加密
*
* @param key 密钥 { a, b }
* @param src 待加密的字符串
* @param dest 经过加密后的字符串
*/
char * encrypt(int* key, char* src, char* dest)
{
char *pSrc = src;
char *pDest = dest;
if (gcd(key[0], WIDTH) != 1)
{
printf("Error: a 与 m 不互素");
exit(-1);
}
for (int i = 0; *pSrc; ++i, ++pSrc, ++pDest)
{
if (!isalpha(*pSrc))
continue;
*pDest = shift(key, toupper(*pSrc));
}
return dest;
}
/*
* 解密
*
* @param key 密钥 { a, b }
* @param src 待解密的字符串
* @param dest 经过解密后的字符串
*/
char * decrypt(int* key, char* src, char* dest)
{
char *pSrc = src;
char *pDest = dest;
int arr[2] = { modInverse(key[0], WIDTH), -key[1] };
for (int i = 0; *pSrc; ++i, ++pSrc, ++pDest)
{
if (!isalpha(*pSrc))
continue;
*pDest = unshift(arr, toupper(*pSrc));
}
return dest;
}
int main(int argc, char const *argv[])
{
// 本例推算见 http://en.wikipedia.org/wiki/Affine_cipher
int key[] = { 5, 8 }; // 密匙
char text[] = "AFFINECIPHER"; // 明文
char ciphertext[1024], result[1024];
// 加密
encrypt(key, text, ciphertext);
printf("%s\n", ciphertext);
// 解密
decrypt(key, ciphertext, result);
printf("%s\n", result);
return 0;
}
/*
* E(x) = (ax + b) mod m
*/
char shift(int *key, char ch)
{
int offset = ch - 'A';
return (key[0] * offset + key[1]) % WIDTH + 'A';
}
/*
* D(x) = a^{-1}(x - b) mod m
*/
char unshift(int *key, char ch)
{
int offset = ch - 'A';
return (((key[0] * (offset + key[1])) % WIDTH + WIDTH) % WIDTH) + 'A';
}
/*
* 判断 a 与 b 是否互素
*/
int gcd(int a, int b)
{
int tmp;
while (a != 0)
{
tmp = a;
a = b % a;
b = tmp;
}
return b;
}
/*
* 求 a 在密表中的乘法逆
*/
int modInverse( int a, int m)
{
int x1, x2, x3, y1, y2, y3, t1, t2, t3, q;
x1 = y2 = 1, x2 = y1 = 0;
x3 = ( a >= m ) ? a : m;
y3 = ( a >= m ) ? m : a;
while ( 1 )
{
if ( y3 == 0 )
{
return x3;
}
else if ( y3 == 1 )
{
return y2;
}
q = x3 / y3;
t1 = x1 - q * y1, t2 = x2 - q * y2, t3 = x3 - q * y3;
x1 = y1, x2 = y2, x3 = y3;
y1 = t1, y2 = t2, y3 = t3;
}
}