难以理解凯撒解密步骤
Trouble understanding Caesar decryption steps
以下代码将根据密文和密钥解密凯撒加密字符串：
#include <iostream>
std::string decrypt(std::string cipher, int key) {
std::string d = "";
for(int i=0; i<cipher.length();i++) {
d += ((cipher[i]-65-key+26) %26)+65;
}
return d;
}
int main()
{
std::cout << decrypt("WKLVLVJRRG", 3) << std::endl; // THISISGOOD
std::cout << decrypt("NBCMCMAIIX", 20) << std::endl; // THISISGOOD
}
我无法理解在这一行计算新字符 ASCII 代码所执行的操作：
d += ((cipher[i]-65-key+26) %26)+65;
- 第一次减法应该移动数字范围
- 然后我们将减去密钥，因为凯撒解密是如何定义的
- 我们加26来处理负数(?)
- 模块会限制输出，因为ASCII码的范围是26位长度
- 我们通过在末尾添加 65 回到原来的范围
我错过了什么？
如果我们稍微重新排序表达式，如下所示：
d += (((cipher[i] - 65) + (26 - key)) % 26) + 65;
我们得到旋转cipher[i]左的公式key:
cipher[i] - 65 将 ASCII 范围 A..Z 转换为整数范围 0..25(cipher[i] - 65 + 26 - key) % 26 将该值向左旋转 key（减去 key 模 26）+ 65 将范围 0..25 移回 ASCII 范围 A..Z.
例如假设 key 为 2，A 变为 Y，B 变为 Z，C 变为 A，等等
让我详细解释一下凯撒密码，以帮助您理解该公式。我还将展示超简单的代码示例，但也会展示更高级的代码示例。
最大的问题是潜在的溢出。所以，我们需要处理这个问题。
然后我们需要了解加密和解密是什么意思。如果加密会将所有内容向右移动一位，那么解密会将其再次向左移动。
- 因此，使用“def”和 key=1，加密后的字符串将为“efg”。
- 然后使用 key=1 解密，将再次向左移动。结果：“def”
我们可以观察到我们只需要移动-1，所以密钥的负值。
所以，基本上加密和解密可以用相同的套路完成。我们只需要反转密钥。
现在让我们看看溢出问题。目前，我们将仅从大写字符开始。字符具有关联代码。例如，在 ASCII 中，字母 'A' 编码为 65，'B' 编码为 66，依此类推。因为我们不想用这样的数字来计算，所以我们将它们归一化。我们只需从每个字符中减去 'A'。然后
- 'A' - 'A' = 0
- 'B' - 'A' = 1
- 'C' - 'A' = 2
- 'D' - 'A' = 3
你看到规律了。如果我们现在想用密钥 3 加密字母 'C'，我们可以执行以下操作。
'C' - 'A' + 3 = 5 然后我们再次添加 'A' 来取回字母，我们将得到 5 + 'A' = 'F'
这就是全部魔法。
但是如何处理超出 'Z' 的溢出。这可以通过简单的模除法来处理。
让我们看看 'Z' + 1。我们做 'Z' - 'A' = 25，然后 +1 = 26 现在模 26 = 0 然后加上 'A' 将是 'A'
等等等等。结果公式为：(c-'A'+key)%26+'A'
接下来，负键呢？这也很简单。假设 'A' 和 key=-1
结果将是 'Z'。但这与向右移动 25 是一样的。因此，我们可以简单地将负键转换为正键。简单的语句将是：
if (key < 0) key = (26 + (key % 26)) % 26;
然后我们可以用一个简单的 Lambda 调用我们的转换函数。一个函数用于加密和解密。只是用一个倒置的钥匙。
并且使用上面的公式，甚至不需要检查负值。它适用于正值和负值。
因此，key = (26 + (key % 26)) % 26; 将始终有效。
一些扩展信息，如果您使用 ASCII 字符表示。请查看任何 ASCII table。你会看到任何大写和小写字符相差 32。或者，如果你查看二进制：
char dez bin char dez bin
'A' 65 0100 0001 'a' 97 0110 0001
'B' 66 0100 0010 'b' 98 0110 0010
'C' 67 0100 0011 'b' 99 0110 0011
. . .
所以，如果你已经知道一个字符是alpha，那么大写和小写之间的唯一区别就是第5位。如果我们想知道，如果char 是小写，我们可以得到这个通过屏蔽这一点。 c & 0b0010 0000 等于 c & 32 或 c & 0x20.
如果我们想对大写或小写字符进行操作，我们可以将“大小写”屏蔽掉。使用 c & 0b00011111 或 c & 31 或 c & 0x1F 我们将始终获得大写字符的等价物，已经标准化为以一个开头。
char dez bin Masking char dez bin Masking
'A' 65 0100 0001 & 0x1b = 1 'a' 97 0110 0001 & 0x1b = 1
'B' 66 0100 0010 & 0x1b = 2 'b' 98 0110 0010 & 0x1b = 2
'C' 67 0100 0011 & 0x1b = 3 'b' 99 0110 0011 & 0x1b = 3
. . .
因此，如果我们使用字母字符，将其屏蔽并减去 1，那么对于任何大写或小写字符，我们都会得到 0..25。
此外，我想重复一下按键处理。正密钥将加密字符串，负密钥将解密字符串。但是，如上所述，负键可以转换为正键。示例：
Shifting by -1 is same as shifting by +25
Shifting by -2 is same as shifting by +24
Shifting by -3 is same as shifting by +23
Shifting by -4 is same as shifting by +22
所以，很明显我们可以通过26 + key计算出一个总是肯定的密钥。对于否定键，这将为我们提供上述偏移量。
对于正键，我们会溢出超过 26，我们可以通过模 26 除法来消除：
'A'--> 0 + 26 = 26 26 % 26 = 0
'B'--> 1 + 26 = 27 27 % 26 = 1
'C'--> 2 + 26 = 28 28 % 26 = 2
'D'--> 3 + 26 = 29 29 % 26 = 3
--> (c + key) % 26 将消除溢出并生成正确的新 en/decryptd 字符。
而且，如果我们将其与上述关于否定键的智慧结合起来，我们可以写成：((26+(key%26))%26) 这将适用于所有肯定键和否定键。
将它与那个掩码结合起来，可以得到以下程序：
const char potentialLowerCaseIndicator = c & 0x20;
const char upperOrLower = c & 0x1F;
const char normalized = upperOrLower - 1;
const int withOffset = normalized + ((26+(key%26))%26);
const int withOverflowCompensation = withOffset % 26;
const char newUpperCaseCharacter = (char)withOverflowCompensation + 'A';
const char result = newUpperCaseCharacter | (potentialLowerCaseIndicator );
当然，上面的很多语句都可以转换成一个Lambda：
#include <string>
#include <algorithm>
#include <cctype>
#include <iostream>
// Simple function for Caesar encyption/decyption
std::string caesar(const std::string& in, int key) {
std::string res(in.size(), ' ');
std::transform(in.begin(), in.end(), res.begin(), [&](char c) {return std::isalpha(c) ? (char)((((c & 31) - 1 + ((26 + (key % 26)) % 26)) % 26 + 65) | (c & 32)) : c; });
return res;
}
int main() {
std::string test{ "aBcDeF xYzZ" };
std::cout << caesar(test, 5);
}
最后一个函数也可以更详细一些以便于理解：
std::string caesar1(const std::string& in, int key) {
std::string res(in.size(), ' ');
auto convert = [&](const char c) -> char {
char result = c;
if (std::isalpha(c)) {
// Handling of a negative key (Shift to left). Key will be converted to positive value
if (key < 0) {
// limit the key to 0,-1,...,-25
key = key % 26;
// Key was negative: Now we have someting between 0 and 26
key = 26 + key;
};
// Check and remember if the original character was lower case
const bool originalIsLower = std::islower(c);
// We want towork with uppercase only
const char upperCaseChar = (char)std::toupper(c);
// But, we want to start with 0 and not with 'A' (65)
const int normalized = upperCaseChar - 'A';
// Now add the key
const int shifted = normalized + key;
// Addition result maybe bigger then 25, so overflow. Cap it
const int capped = shifted % 26;
// Get back a character
const char convertedUppcase = (char)capped + 'A';
// And set back the original case
result = originalIsLower ? (char)std::tolower(convertedUppcase) : convertedUppcase;
}
return result;
};
std::transform(in.begin(), in.end(), res.begin(), convert);
return res;
}
如果您想查看仅包含最简单语句的解决方案，请参阅下文。
#include <iostream>
#include <string>
using namespace std;
string caesar(string in, int key) {
// Here we will store the resulting encrypted/decrypted string
string result{};
// Handling of a negative key (Shift to left). Key will be converted to positive value
if (key < 0) {
// limit the key to 0,-1,...,-25
key = key % 26;
// Key was negative: Now we have someting between 0 and 26
key = 26 + key;
};
// Read character by character from the string
for (unsigned int i = 0; i < in.length(); ++i) {
char c = in[i];
// CHeck for alpha character
if ((c >= 'A' and c <= 'Z') or (c >= 'a' and c <= 'z')) {
// Check and remember if the original character was lower case
bool originalIsLower = (c >= 'a' and c <= 'z');
// We want to work with uppercase only
char upperCaseChar = originalIsLower ? c - ('a' - 'A') : c;
// But, we want to start with 0 and not with 'A' (65)
int normalized = upperCaseChar - 'A';
// Now add the key
int shifted = normalized + key;
// Addition result maybe bigger then 25, so overflow. Cap it
int capped = shifted % 26;
// Get back a character
char convertedUppcase = (char)capped + 'A';
// And set back the original case
result += originalIsLower ? convertedUppcase + ('a' - 'A') : convertedUppcase;
}
else
result += c;
}
return result;
}
int main() {
string test{ "aBcDeF xYzZ" };
string encrypted = caesar(test, 5);
string decrypted = caesar(encrypted, -5);
cout << "Original: " << test << '\n';
cout << "Encrpyted: " << encrypted << '\n';
cout << "Decrpyted: " << decrypted << '\n';
}
以下代码将根据密文和密钥解密凯撒加密字符串：
#include <iostream>
std::string decrypt(std::string cipher, int key) {
std::string d = "";
for(int i=0; i<cipher.length();i++) {
d += ((cipher[i]-65-key+26) %26)+65;
}
return d;
}
int main()
{
std::cout << decrypt("WKLVLVJRRG", 3) << std::endl; // THISISGOOD
std::cout << decrypt("NBCMCMAIIX", 20) << std::endl; // THISISGOOD
}
我无法理解在这一行计算新字符 ASCII 代码所执行的操作：
d += ((cipher[i]-65-key+26) %26)+65;
- 第一次减法应该移动数字范围
- 然后我们将减去密钥，因为凯撒解密是如何定义的
- 我们加26来处理负数(?)
- 模块会限制输出，因为ASCII码的范围是26位长度
- 我们通过在末尾添加 65 回到原来的范围
我错过了什么？
如果我们稍微重新排序表达式，如下所示：
d += (((cipher[i] - 65) + (26 - key)) % 26) + 65;
我们得到旋转cipher[i]左的公式key:
cipher[i] - 65将 ASCII 范围A..Z转换为整数范围 0..25(cipher[i] - 65 + 26 - key) % 26将该值向左旋转key（减去key模 26）+ 65将范围 0..25 移回 ASCII 范围A..Z.
例如假设 key 为 2，A 变为 Y，B 变为 Z，C 变为 A，等等
让我详细解释一下凯撒密码，以帮助您理解该公式。我还将展示超简单的代码示例，但也会展示更高级的代码示例。
最大的问题是潜在的溢出。所以，我们需要处理这个问题。
然后我们需要了解加密和解密是什么意思。如果加密会将所有内容向右移动一位，那么解密会将其再次向左移动。
- 因此，使用“def”和 key=1，加密后的字符串将为“efg”。
- 然后使用 key=1 解密，将再次向左移动。结果：“def”
我们可以观察到我们只需要移动-1，所以密钥的负值。
所以，基本上加密和解密可以用相同的套路完成。我们只需要反转密钥。
现在让我们看看溢出问题。目前，我们将仅从大写字符开始。字符具有关联代码。例如，在 ASCII 中，字母 'A' 编码为 65，'B' 编码为 66，依此类推。因为我们不想用这样的数字来计算，所以我们将它们归一化。我们只需从每个字符中减去 'A'。然后
- 'A' - 'A' = 0
- 'B' - 'A' = 1
- 'C' - 'A' = 2
- 'D' - 'A' = 3
你看到规律了。如果我们现在想用密钥 3 加密字母 'C'，我们可以执行以下操作。
'C' - 'A' + 3 = 5 然后我们再次添加 'A' 来取回字母，我们将得到 5 + 'A' = 'F'
这就是全部魔法。
但是如何处理超出 'Z' 的溢出。这可以通过简单的模除法来处理。
让我们看看 'Z' + 1。我们做 'Z' - 'A' = 25，然后 +1 = 26 现在模 26 = 0 然后加上 'A' 将是 'A'
等等等等。结果公式为：(c-'A'+key)%26+'A'
接下来，负键呢？这也很简单。假设 'A' 和 key=-1
结果将是 'Z'。但这与向右移动 25 是一样的。因此，我们可以简单地将负键转换为正键。简单的语句将是：
if (key < 0) key = (26 + (key % 26)) % 26;
然后我们可以用一个简单的 Lambda 调用我们的转换函数。一个函数用于加密和解密。只是用一个倒置的钥匙。
并且使用上面的公式，甚至不需要检查负值。它适用于正值和负值。
因此，key = (26 + (key % 26)) % 26; 将始终有效。
一些扩展信息，如果您使用 ASCII 字符表示。请查看任何 ASCII table。你会看到任何大写和小写字符相差 32。或者，如果你查看二进制：
char dez bin char dez bin
'A' 65 0100 0001 'a' 97 0110 0001
'B' 66 0100 0010 'b' 98 0110 0010
'C' 67 0100 0011 'b' 99 0110 0011
. . .
所以，如果你已经知道一个字符是alpha，那么大写和小写之间的唯一区别就是第5位。如果我们想知道，如果char 是小写，我们可以得到这个通过屏蔽这一点。 c & 0b0010 0000 等于 c & 32 或 c & 0x20.
如果我们想对大写或小写字符进行操作，我们可以将“大小写”屏蔽掉。使用 c & 0b00011111 或 c & 31 或 c & 0x1F 我们将始终获得大写字符的等价物，已经标准化为以一个开头。
char dez bin Masking char dez bin Masking
'A' 65 0100 0001 & 0x1b = 1 'a' 97 0110 0001 & 0x1b = 1
'B' 66 0100 0010 & 0x1b = 2 'b' 98 0110 0010 & 0x1b = 2
'C' 67 0100 0011 & 0x1b = 3 'b' 99 0110 0011 & 0x1b = 3
. . .
因此，如果我们使用字母字符，将其屏蔽并减去 1，那么对于任何大写或小写字符，我们都会得到 0..25。
此外，我想重复一下按键处理。正密钥将加密字符串，负密钥将解密字符串。但是，如上所述，负键可以转换为正键。示例：
Shifting by -1 is same as shifting by +25
Shifting by -2 is same as shifting by +24
Shifting by -3 is same as shifting by +23
Shifting by -4 is same as shifting by +22
所以，很明显我们可以通过26 + key计算出一个总是肯定的密钥。对于否定键，这将为我们提供上述偏移量。
对于正键，我们会溢出超过 26，我们可以通过模 26 除法来消除：
'A'--> 0 + 26 = 26 26 % 26 = 0
'B'--> 1 + 26 = 27 27 % 26 = 1
'C'--> 2 + 26 = 28 28 % 26 = 2
'D'--> 3 + 26 = 29 29 % 26 = 3
--> (c + key) % 26 将消除溢出并生成正确的新 en/decryptd 字符。
而且，如果我们将其与上述关于否定键的智慧结合起来，我们可以写成：((26+(key%26))%26) 这将适用于所有肯定键和否定键。
将它与那个掩码结合起来，可以得到以下程序：
const char potentialLowerCaseIndicator = c & 0x20;
const char upperOrLower = c & 0x1F;
const char normalized = upperOrLower - 1;
const int withOffset = normalized + ((26+(key%26))%26);
const int withOverflowCompensation = withOffset % 26;
const char newUpperCaseCharacter = (char)withOverflowCompensation + 'A';
const char result = newUpperCaseCharacter | (potentialLowerCaseIndicator );
当然，上面的很多语句都可以转换成一个Lambda：
#include <string>
#include <algorithm>
#include <cctype>
#include <iostream>
// Simple function for Caesar encyption/decyption
std::string caesar(const std::string& in, int key) {
std::string res(in.size(), ' ');
std::transform(in.begin(), in.end(), res.begin(), [&](char c) {return std::isalpha(c) ? (char)((((c & 31) - 1 + ((26 + (key % 26)) % 26)) % 26 + 65) | (c & 32)) : c; });
return res;
}
int main() {
std::string test{ "aBcDeF xYzZ" };
std::cout << caesar(test, 5);
}
最后一个函数也可以更详细一些以便于理解：
std::string caesar1(const std::string& in, int key) {
std::string res(in.size(), ' ');
auto convert = [&](const char c) -> char {
char result = c;
if (std::isalpha(c)) {
// Handling of a negative key (Shift to left). Key will be converted to positive value
if (key < 0) {
// limit the key to 0,-1,...,-25
key = key % 26;
// Key was negative: Now we have someting between 0 and 26
key = 26 + key;
};
// Check and remember if the original character was lower case
const bool originalIsLower = std::islower(c);
// We want towork with uppercase only
const char upperCaseChar = (char)std::toupper(c);
// But, we want to start with 0 and not with 'A' (65)
const int normalized = upperCaseChar - 'A';
// Now add the key
const int shifted = normalized + key;
// Addition result maybe bigger then 25, so overflow. Cap it
const int capped = shifted % 26;
// Get back a character
const char convertedUppcase = (char)capped + 'A';
// And set back the original case
result = originalIsLower ? (char)std::tolower(convertedUppcase) : convertedUppcase;
}
return result;
};
std::transform(in.begin(), in.end(), res.begin(), convert);
return res;
}
如果您想查看仅包含最简单语句的解决方案，请参阅下文。
#include <iostream>
#include <string>
using namespace std;
string caesar(string in, int key) {
// Here we will store the resulting encrypted/decrypted string
string result{};
// Handling of a negative key (Shift to left). Key will be converted to positive value
if (key < 0) {
// limit the key to 0,-1,...,-25
key = key % 26;
// Key was negative: Now we have someting between 0 and 26
key = 26 + key;
};
// Read character by character from the string
for (unsigned int i = 0; i < in.length(); ++i) {
char c = in[i];
// CHeck for alpha character
if ((c >= 'A' and c <= 'Z') or (c >= 'a' and c <= 'z')) {
// Check and remember if the original character was lower case
bool originalIsLower = (c >= 'a' and c <= 'z');
// We want to work with uppercase only
char upperCaseChar = originalIsLower ? c - ('a' - 'A') : c;
// But, we want to start with 0 and not with 'A' (65)
int normalized = upperCaseChar - 'A';
// Now add the key
int shifted = normalized + key;
// Addition result maybe bigger then 25, so overflow. Cap it
int capped = shifted % 26;
// Get back a character
char convertedUppcase = (char)capped + 'A';
// And set back the original case
result += originalIsLower ? convertedUppcase + ('a' - 'A') : convertedUppcase;
}
else
result += c;
}
return result;
}
int main() {
string test{ "aBcDeF xYzZ" };
string encrypted = caesar(test, 5);
string decrypted = caesar(encrypted, -5);
cout << "Original: " << test << '\n';
cout << "Encrpyted: " << encrypted << '\n';
cout << "Decrpyted: " << decrypted << '\n';
}