Caesar cipher

Why this matters

A cipher is a rule for changing text so that a reader without the rule cannot understand it. The Caesar cipher is one of the oldest and simplest. It is named after Julius Caesar, who is said to have used it to send private messages. Nobody uses it to protect data today, because anyone can try all 25 possible shifts in a few seconds. It is still a good teaching tool, because it needs one idea that you will use in many other programs: wrap-around. When a value goes past the end of its range, it starts again at the beginning.

Wrap-around shows up in circular buffers, in clock arithmetic, and in the index math of hash tables. This lesson builds the Caesar cipher one step at a time, and the same method applies to each of those.

The lesson uses the letter-counting work from the previous one. The idea that a lowercase letter is a number from 0 to 25 comes from there.

What the cipher does

Take a message and move every letter forward in the alphabet by the same amount. That amount is called the shift. With a shift of 3, a becomes d, b becomes e, and c becomes f. The word hello becomes khoor.

What happens at the end of the alphabet? With a shift of 3, x should go to a, y to b, and z to c. Moving past z means starting again at a. That is the wrap-around.

To undo the cipher, move every letter back by the same amount. A shift of -3 decodes text that was encrypted with a shift of 3.

Only letters move. Spaces, digits, punctuation and the rest stay the same. A message such as Hello, World! becomes Khoor, Zruog!, and the comma and exclamation mark do not change.

Letters are numbers, so shifting is addition

Give each lowercase letter its position: a is 0, b is 1, up to z at 25. The position of a letter is c - 'a', as in the previous lesson. To shift a letter, add the shift to its position. Then turn the new position back into a letter by adding 'a'.

For x with a shift of 3, the position is 23, and 23 + 3 is 26. Position 26 is past the end, because the last position is 25. The rule needs to bring 26 back to 0, which is a.

The operator % (called modulo, or just "remainder") does that job. It gives the remainder after division. 26 % 26 is 0, because 26 divides into 26 exactly with nothing left over. 27 % 26 is 1. Any number past the end comes back into the range 0 to 25 when you take its remainder by 26.

The first program applies the shift without any remainder step. It handles a correctly and fails for x:

#include <iostream>
 
int main() {
    int shift = 3;
 
    char a = 'a';
    char moved_a = static_cast<char>(a + shift);
    std::cout << "a moved by 3: " << moved_a << '\n';
 
    char x = 'x';
    char moved_x = static_cast<char>(x + shift);
    std::cout << "x moved by 3: " << moved_x << " code " << static_cast<int>(moved_x) << '\n';
}

Output:

a moved by 3: d
x moved by 3: { code 123

The result for x is {, which has code 123. That is the character right after z in the ASCII table. It is not a letter, so the cipher has broken. The fix is to take the remainder by 26 before adding 'a' back.

Step 2: shift lowercase letters with modulo

For a lowercase letter, the whole rule fits on one line:

char shift_lower(char c, int shift) {
    return static_cast<char>('a' + (c - 'a' + shift) % 26);
}

The expression c - 'a' + shift is the new position before wrapping. The % 26 brings it back into 0 to 25. Adding 'a' turns the position into a letter.

Try it on x with a shift of 3. The position is 23, plus 3 is 26, and 26 % 26 is 0. The result is a. Try it on z with a shift of 3. The position is 25, plus 3 is 28, and 28 % 26 is 2. The result is c.

This works for positive shifts. It fails for negative ones, which is the next problem.

Step 3: the negative remainder trap

To decode, we shift by a negative amount. Take the letter a and shift it by -3. The correct answer is x. The next program uses the same formula with a negative shift:

#include <iostream>
 
int main() {
    char c = 'a';
    int shift = -3;
    int position = (c - 'a' + shift) % 26;
    std::cout << "position: " << position << '\n';
    char wrong = static_cast<char>('a' + position);
    std::cout << "naive result: " << wrong << " code " << static_cast<int>(wrong) << '\n';
}

Output:

position: -3
naive result: ^ code 94

The position should be 23, which is x. The program got -3 instead. In C++, the sign of a remainder follows the number on the left side of %. Here the left side is -3, so the remainder is -3. Then 'a' + -3 is code 94, which is the caret symbol ^.

The fix is to reduce the shift first, so it sits between 0 and 25 before it is added to the letter. A negative shift gets 26 added to it once:

int k = shift % 26;   // -3 % 26 is -3, so k is -3
if (k < 0) {
    k += 26;          // k is now 23
}

Now (c - 'a' + k) % 26 has a positive left side for every letter, so the remainder is always in 0 to 25.

Step 4: the full cipher

The complete version handles capitals and leaves every other character alone. The function shift_char works on one character. The function caesar applies it to every character of a string.

#include <iostream>
#include <string>
 
// Moves one letter position by shift. The shift is first reduced to 0..25.
char shift_char(char c, int shift) {
    int k = shift % 26;      // now between -25 and 25
    if (k < 0) {
        k += 26;             // now between 0 and 25
    }
 
    if (c >= 'a' && c <= 'z') {
        return static_cast<char>('a' + (c - 'a' + k) % 26);
    }
    if (c >= 'A' && c <= 'Z') {
        return static_cast<char>('A' + (c - 'A' + k) % 26);
    }
    return c;
}
 
std::string caesar(const std::string& text, int shift) {
    std::string result = text;
    for (char& c : result) {
        c = shift_char(c, shift);
    }
    return result;
}
 
int main() {
    std::cout << caesar("Hello, World!", 3) << '\n';
    std::cout << caesar("Khoor, Zruog!", -3) << '\n';
    std::cout << caesar("xyz", 3) << '\n';
    std::cout << caesar("Hello", 29) << '\n';
    std::cout << caesar("Hello", 0) << '\n';
    std::cout << caesar("abc-123", 2147483647) << '\n';
    std::cout << caesar(caesar("Round trip", 7), -7) << '\n';
}

Output:

Khoor, Zruog!
Hello, World!
abc
Khoor
Hello
xyz-123
Round trip

Each line of the output checks one rule:

• Hello, World! with a shift of 3 gives Khoor, Zruog!. Letters move, and the comma, space and exclamation mark stay.
• Khoor, Zruog! with a shift of -3 gives the original text. This is decoding.
• xyz with a shift of 3 gives abc. This is wrap-around.
• A shift of 29 gives the same result as a shift of 3, because 29 % 26 is 3. Any shift can be reduced this way.
• A shift of 0 changes nothing.
• The shift 2147483647 is the largest int in C++. The line abc-123 becomes xyz-123. This works because shift_char reduces the shift to 0 to 25 before adding it to a letter. If it added the raw shift to the letter position, a letter at position 25 plus that shift would go past the largest int, which is undefined behaviour.
• The last line encrypts Round trip with a shift of 7 and decrypts it with -7. The text comes back unchanged.

The line if (c >= 'a' && c <= 'z') runs before the capital test. Each branch returns its own result, so a lowercase letter never reaches the capital branch. The last return c; covers every other character.

The function caesar takes its input as const std::string&. The const promises the function will not change the caller's string. The function copies the text into result first, and changes only the copy. This is why the caller's "Hello" is still Hello after the call.

Common mistakes

Forgetting the wrap-around

If you add the shift and skip the remainder, a letter near the end of the alphabet goes past z. The first program in this lesson showed the result: x moved by 3 gave {. Characters with codes above z are not letters. Every letter-shifting function needs the % 26 step.

Negative remainders

The second program showed (c - 'a' + shift) % 26 with a shift of -3 giving -3 instead of 23. The result was ^. Reducing the shift to 0 to 25 first, as shift_char does, avoids this.

Changing only lowercase letters

If the function uses only the lowercase base, capitals come out wrong. This version treats both cases with the lowercase base 'a':

#include <iostream>
#include <string>
 
// Wrong on purpose: treats capitals as if they used the lowercase base.
char wrong_shift(char c, int shift) {
    int k = shift % 26;
    if (k < 0) {
        k += 26;
    }
    if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
        return static_cast<char>('a' + (c - 'a' + k) % 26);
    }
    return c;
}
 
int main() {
    std::string text = "ABC";
    for (char& c : text) {
        c = wrong_shift(c, 1);
    }
    std::cout << text << '\n';
}

Output:

\]^

For A, the position is 'A' - 'a', which is -32, not 0. The remainder of -31 by 26 is -5, so the result is code 92, which is a backslash. The correct answer is B. Each capital needs its own base, 'A', as shift_char uses.

Changing the text that was passed in

A string passed as const std::string& cannot be changed. The next program tries to change its input in place:

#include <iostream>
#include <string>
 
char shift_char(char c, int shift) {
    return static_cast<char>('a' + (c - 'a' + shift % 26 + 26) % 26);
}
 
std::string caesar(const std::string& text, int shift) {
    for (char& c : text) {
        c = shift_char(c, shift);
    }
    return text;
}
 
int main() {
    std::cout << caesar("abc", 1) << '\n';
}

Compiler message from g++ -std=c++20 -Wall:

m09_err_const.cpp: In function ‘std::string caesar(const std::string&, int)’:
m09_err_const.cpp:9:20: error: binding reference of type ‘char&’ to ‘const char’ discards qualifiers
    9 |     for (char& c : text) {
      |                    ^~~~

The loop asks for a char&, which means "a changeable character". The string is const, so the loop cannot change it. The fix is to copy the text into a local std::string result = text; and change result, as the full version does.

Narrowing into braces

Braces {} in C++ refuse some conversions that parentheses allow. Here an int result is put into a char inside braces:

#include <iostream>
 
int main() {
    int shift = 3;
    char letter = 'a';
    char moved{letter + shift};
    std::cout << moved << '\n';
}

g++ -std=c++20 -Wall reported this warning:

m09_err_narrow.cpp: In function ‘int main()’:
m09_err_narrow.cpp:6:23: warning: narrowing conversion of ‘(((int)letter) + shift)’ from ‘int’ to ‘char’ [-Wnarrowing]
    6 |     char moved{letter + shift};
      |                ~~~~~~~^~~~~~~

The letter + shift expression is an int, which can hold numbers that a char cannot. The fix is to say what you mean with static_cast<char>(...), as the rest of this lesson does.

Practice

Exercise 1. ROT13. ROT13 is a Caesar cipher with a shift of 13. Write std::string rot13(const std::string& text) that uses caesar. Test it with Hello (expected Uryyb), then apply it again to Uryyb (expected Hello). A shift of 13 is its own reverse because 13 + 13 is 26.

Show the answer

#include <iostream>
#include <string>
 
char shift_char(char c, int shift) {
    int k = shift % 26;
    if (k < 0) {
        k += 26;
    }
    if (c >= 'a' && c <= 'z') {
        return static_cast<char>('a' + (c - 'a' + k) % 26);
    }
    if (c >= 'A' && c <= 'Z') {
        return static_cast<char>('A' + (c - 'A' + k) % 26);
    }
    return c;
}
 
std::string caesar(const std::string& text, int shift) {
    std::string result = text;
    for (char& c : result) {
        c = shift_char(c, shift);
    }
    return result;
}
 
std::string rot13(const std::string& text) {
    return caesar(text, 13);
}
 
int main() {
    std::string once = rot13("Hello");
    std::cout << once << ' ' << rot13(once) << '\n';
}

Output:

Uryyb Hello

The function rot13 only calls caesar with the shift 13. Applying it twice adds 13 twice, which is 26, so every letter returns to where it started.

Exercise 2. Count the moved letters. Write int count_changed(const std::string& before, const std::string& after) that returns how many positions hold different characters. Use it to count the changed characters in Hi, there! after a shift of 3, and again after a shift of 26. Predict both numbers first.

Show the answer

#include <iostream>
#include <string>
 
char shift_char(char c, int shift) {
    int k = shift % 26;
    if (k < 0) {
        k += 26;
    }
    if (c >= 'a' && c <= 'z') {
        return static_cast<char>('a' + (c - 'a' + k) % 26);
    }
    if (c >= 'A' && c <= 'Z') {
        return static_cast<char>('A' + (c - 'A' + k) % 26);
    }
    return c;
}
 
std::string caesar(const std::string& text, int shift) {
    std::string result = text;
    for (char& c : result) {
        c = shift_char(c, shift);
    }
    return result;
}
 
int count_changed(const std::string& before, const std::string& after) {
    int changed = 0;
    for (size_t i = 0; i < before.size(); i++) {
        if (before[i] != after[i]) {
            changed++;
        }
    }
    return changed;
}
 
int main() {
    std::cout << count_changed("Hi, there!", caesar("Hi, there!", 3)) << '\n';
    std::cout << count_changed("Hi, there!", caesar("Hi, there!", 26)) << '\n';
}

Output:

7
0

The text Hi, there! has seven letters: H, i, t, h, e, r and e. The comma, the space and the exclamation mark never change. A shift of 26 is the same as a shift of 0, so nothing moves.

Exercise 3. Find the shift. The cipher text Khoor was made with an unknown shift. Try all 26 shifts from 0 to 25 and print the shift that turns Khoor into Hello. Use the caesar function from Step 4.

Show the answer

#include <iostream>
#include <string>
 
char shift_char(char c, int shift) {
    int k = shift % 26;
    if (k < 0) {
        k += 26;
    }
    if (c >= 'a' && c <= 'z') {
        return static_cast<char>('a' + (c - 'a' + k) % 26);
    }
    if (c >= 'A' && c <= 'Z') {
        return static_cast<char>('A' + (c - 'A' + k) % 26);
    }
    return c;
}
 
std::string caesar(const std::string& text, int shift) {
    std::string result = text;
    for (char& c : result) {
        c = shift_char(c, shift);
    }
    return result;
}
 
int main() {
    for (int shift = 0; shift < 26; shift++) {
        if (caesar("Khoor", shift) == "Hello") {
            std::cout << "shift " << shift << '\n';
        }
    }
}

Output:

shift 23

The shift 23 is the same as -3, because 23 + 3 is 26. Trying every shift is called a brute-force search. With only 26 possibilities for a Caesar cipher, it is enough to break one.

Exercise 4. Predict, then run. Before you run the code, predict the result of caesar("zebra", 1). Then run std::cout << caesar("zebra", 1) << '\n'; with the caesar function from Step 4.

Show the answer

The output is:

afcsb

Each letter moves forward by one. z wraps to a, e becomes f, b becomes c, r becomes s, and a becomes b.

Exercise 5. Write it yourself. Without looking at the Step 4 code, write shift_char for lowercase letters only. Check it on a with a shift of -1 (expected z), z with a shift of 1 (expected a), and m with a shift of 26 (expected m).

Show the answer

#include <iostream>
 
char shift_lower(char c, int shift) {
    int k = shift % 26;
    if (k < 0) {
        k += 26;
    }
    return static_cast<char>('a' + (c - 'a' + k) % 26);
}
 
int main() {
    std::cout << shift_lower('a', -1) << '\n';
    std::cout << shift_lower('z', 1) << '\n';
    std::cout << shift_lower('m', 26) << '\n';
}

Output:

z
a
m

The reduction of the shift to 0 to 25 comes first, and the remainder with % 26 comes second. Both steps are needed. A shift of 26 reduces to 0, so the letter stays the same.

Summary

• A Caesar cipher moves each letter forward by a fixed shift, and decodes by moving it back.
• Letter positions run from 0 to 25, so the new position is (c - 'a' + shift) % 26.
• A negative remainder in C++ keeps the sign of the left side, so reduce the shift to 0 to 25 before using it.
• Keep capitals and non-letters unchanged, and use a separate base for capitals.
• Copy a const std::string& into a local string before changing it.