凯撒加密
简述
在密码学中，恺撒密码是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。例，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。这个加密方法是以恺撒的名字命名的，当年恺撒曾用此方法与其将军们进行联系。恺撒密码通常被作为其他更复杂的加密方法中的一个步骤。恺撒密码还在现代的ROT13系统中被应用。但是和所有的利用字母表进行替换的加密技术一样，凯撒密码的密度是很低的，只需简单地统计字频就可以破译。
需要注意的是，凯撒加密只对二十六个字母（要么都是大写，要么都是小写）有效。
描述
设 \(k\) 为密钥 (key)，字符串 \(m\) 为明文，\(c\) 为密文，则加密算法为 \[
c_i=E(m_i,k)
\] 其中函数 \(E\) 的算法为，令
\(m_i\) 向右偏移 \(k\) 位，在
ABCDEFGHIJKLMNOPQRSTUVWXYZ 字母环中移动，即 \[
E(m_i,k)=(m_i+k)\ mod\ 26
\] 解密算法为 \[
m_i=D(c_i,k)
\] 其中函数 \(D\) 的算法为，令
\(c_i\) 向左偏移 k 位，在
ABCDEFGHIJKLMNOPQRSTUVWXYZ 字母环中移动，即 \[
D(c_i,k)=(c_i-k)\ mod\ 26
\]
实现
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
|
char CaesarChar(char ch, int k)
{
return (ch - 'A' + k) % 26 + 'A';
}
string CaesarEncoder(const string& plain, int key)
{
string result(plain);
for (char& i : result)
{
i = CaesarChar(i, key);
}
return result;
}
string CaesarDecoder(const string& code, int key)
{
string result(code);
for (char& i : result)
{
i = CaesarChar(i, -key);
}
return result;
}
|
对于凯撒加密有十分简单的爆破方法：
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
|
int CaesarCharKeyCracker(char plainChar, char codeChar)
{
int diff = codeChar - plainChar;
return diff < 0 ? diff + 26 : diff;
}
int CaesarStringKeyCracker(const string& plain, const string& code)
{
int diff = CaesarCharKeyCracker(plain[0], code[0]);
for (size_t i = 0; i < plain.size(); ++i)
{
if (diff != CaesarCharKeyCracker(plain[i], code[i]))
{
return -1;
}
}
return diff;
}
vector<string> CaesarCracker(const string& code)
{
vector<string> result;
for (int i = 1; i < 26; ++i)
{
result.push_back(CaesarDecoder(code, i));
}
return result;
}
|
爆破算法使用 python 编写则是：
1
2
3
| def CaesarCracker(code:str):
for i in range(1, 26):
yield ''.join(map(lambda x : chr((ord(x) - ord('A') - i) % 26 + ord('A')) if str.isalpha(x) else x, code))
|
维吉尼亚加密
简述
在单一恺撒密码的基础上，法国外交家布莱斯·德·维吉尼亚（Blaise de
Vigenère）发明了一种方法来对同一条信息中的不同字母用不同的密码进行加密。这样，同样的E在一个位置可能被M所取代，而在另一个位置的E则有可能以K的面目出现。这样，就可以防止任何人利用频率分析法解密该条信息。
维吉尼亚密码引入了“密钥”的概念，即根据密钥来决定用哪一行的密表来进行替换，以此来对抗字频统计。
vigenere table
描述
与凯撒加密不同，维吉尼亚的密钥是一个只含有二十六个字母的字符串 \(key\)，同理明文为 \(m\)，密文为 \(c\)，则加密算法为 \[
c_i=E(m_i,key_i)
\] 其中函数 \(E\)
的算法为，在维吉尼亚表中，横行为 \(m_i\) 的字符，纵行为 \(key_i\)
的字符，选择对应的表中字符为加密字符。
解密算法为 \[
m_i=D(c_i,key_i)
\] 其中函数 \(D\)
的算法为，在维吉尼亚表中，纵行为 \(key_i\) 的字符，查找 \(key_i\) 对应横行中的字符 \(c_i\)，所对应的上方横行字符即为明文字符。
实际上就相当于每一个字符都拥有自己的 key 进行凯撒加密
实现
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
|
char CaesarChar(char ch, int k)
{
return (ch - 'A' + k) % 26 + 'A';
}
char VigenereCharEncoder(char ch, char k)
{
return CaesarChar(ch, k - 'A');
}
char VigenereCharDecoder(char ch, char k)
{
return CaesarChar(ch, -(int)(k - 'A'));
}
string VigenereStringEncoder(const string& plain, const string& key)
{
string result(plain);
size_t c = 0;
for (char& i : result)
{
i = VigenereCharEncoder(i, key[c]);
++c;
if (c == key.size())
{
c -= key.size();
}
}
return result;
}
string VigenereStringDecoder(const string& code, const string& key)
{
string result(code);
size_t c = 0;
for (char& i : result)
{
i = VigenereCharDecoder(i, key[c]);
++c;
if (c == key.size())
{
c -= key.size();
}
}
return result;
}
|
其中对维吉尼亚密钥的爆破算法为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int CaesarCharKeyCracker(char plainChar, char codeChar)
{
int diff = codeChar - plainChar;
return diff < 0 ? diff + 26 : diff;
}
string VigenereKeyCracker(const string& plain, const string& code)
{
string key(plain);
for (size_t i = 0; i < plain.size(); ++i)
{
key[i] = CaesarCharKeyCracker(plain[i], code[i]) + 'A';
}
return key;
}
|
爆破密钥的算法使用 python 编写则是：
1
2
| def VigenereKeyCracker(plain:str, code:str):
return ''.join(chr((ord(i) - ord(j)) % 26 + ord('A')) if str.isalpha(i) else '' for i, j in zip(plain, code))
|