Trouble understanding Caesar decryption steps
If we reorder the expression slightly, like this:
d += (((cipher[i] - 65) + (26 - key)) % 26) + 65;
We get a formula for rotating cipher[i] left by key:
-
cipher[i] - 65brings the ASCII rangeA..Zinto an integer range 0..25 -
(cipher[i] - 65 + 26 - key) % 26rotates that value left bykey(subtractskeymodulo 26) -
+ 65to shift the range 0..25 back into ASCII rangeA..Z.
e.g. given a key of 2, A becomes Y, B becomes Z, C becomes A, etc.
Let me give you a detailed explanation about Caesar Cipher for understanding that formular. I will also show ultra simple code examples, but also more advanced one liners.
The biggest problems are potential overflows. So, we need to deal with that.
Then we need to understand what Encryption and decryption means. If encryption will shift everthing one to the right, decryption will shift it back to left again.
- So, with "def" and key=1, the encrpyted string will be "efg".
- And decrpytion with key=1, will shift it to left again. Result: "def"
We can observe that we simply need to shift by -1, so the negative of the key.
So, basically encryption and decryption can be done with the same routine. We just need to invert the keys.
Let us look now at the overflow problematic. For the moment we will start with uppercase characters only. Characters have an associated code. For example, in ASCII, the letter 'A' is encoded with 65, 'B' with 66 and so on. Because we do not want to calculate with such number, we normalize them. We simply subtract 'A' from each character. Then
- 'A' - 'A' = 0
- 'B' - 'A' = 1
- 'C' - 'A' = 2
- 'D' - 'A' = 3
You see the pattern. If we want to encrypt now the letter 'C' with key 3, we can do the following.
'C' - 'A' + 3 = 5 Then we add again 'A' to get back the letter and we will get 5 + 'A' = 'F'
That is the whole magic.
But what to do with an overflow, beyond 'Z'. This can be handled by a simple modulo division.
Let us look at 'Z' + 1. We do 'Z' - 'A' = 25, then +1 = 26 and now modulo 26 = 0 then plus 'A' will be 'A'
And so on and so on. The resulting Formula is: (c-'A'+key)%26+'A'
Next, what with negative keys? This is also simple. Assume an 'A' and key=-1
Result will be a 'Z'. But this is the same as shifting 25 to the right. So, we can simply convert a negative key to a positive shift. The simple statement will be:
if (key < 0) key = (26 + (key % 26)) % 26;
And then we can call our tranformation function with a simple Lambda. One function for encryption and decrytion. Just with an inverted key.
And with the above formular, there is even no need to check for a negative values. It will work for positive and negative values.
So, key = (26 + (key % 26)) % 26; will always work.
Some extended information, if you work with ASCII character representation. Please have a look at any ASCII table. You will see that any uppercase and lowercase character differ by 32. Or, if you look in binary:
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
. . .
So, if you already know that a character is alpha, then the only difference between upper- and lowercase is bit number 5. If we want to know, if char is lowercase, we can get this by masking this bit. c & 0b0010 0000 that is equal to c & 32 or c & 0x20.
If we want to operater on either uppercase or lowercase characters, the we can mask the "case" away. With c & 0b00011111 or c & 31 or c & 0x1F we will get always equivalents for uppercase charcters, already normalized to start with one.
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
. . .
So, if we use an alpha character, mask it, and subtract 1, then we get as a result 0..25 for any upper- or lowercase character.
Additionally, I would like tor repeat the key handling. Positive keys will encrypt a string, negative keys will decrypt a string. But, as said above, negative keys can be transormed into positive ones. Example:
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
So,it is very obvious that we can calculate an always positive key by: 26 + key. For negative keys, this will give us the above offsets.
And for positve keys, we would have an overflow over 26, which we can elimiate by a modulo 26 division:
'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 will eliminate overflows and result in the correct new en/decryptd character.
And, if we combine this with the above wisdom for negative keys, we can write: ((26+(key%26))%26) which will work for all positive and negative keys.
Combining that with that masking, could give us the following program:
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 );
Of course, all the above many statements can be converted into one 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);
}
The last function can also be made more verbose for easier understanding:
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;
}
And if you want to see a solution with only the simplest statements, then see the below.
#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';
}