We previously looked at the Shift Cipher and learned that it has many weaknesses. The Substitution Cipher solves one of those primary weaknesses, key size.

The Substitution cipher works by mapping each input letter to an output letter as in the Shift Cipher, however, the order of the alphabet does not need to be preserved.  For example the following mapping can be used:

Original Value	Encrypted Value
A	J
B	B
C	S
D	Q
E	V
F	E
G	N
H	W
I	F
J	L
K	T
L	G
M	H
N	P
O	U
P	Z
Q	K
R	R
S	M
T	A
U	X
V	Y
W	O
X	I
Y	D
Z	C

Note In this example, B maps to B and R maps to R. This is not recommended but is not prohibited.

As with the Shift Cipher, punctuation and spaces are removed and all letters are set to be upper case.  The input message “Hello, World!” is translated to “HELLOWORLD” and encrypted to the cipher text of: WVGGUOURGQ

Decryption of the Cipher Text is a simple reverse mapping of the substitution. W -> H, V -> E.. etc. resulting in the original text “HELLOWORLD”

The key space for the substitution cipher is much larger than that of the Shift Cipher. The key space can be calculated easily using factorials, or 26!. That is A can be 26 possible characters, B can be 25 possible characters, C can be 24 possible characters. This gives a possible key space of 26! or, 4.0329 * 10^26.

Insecurities of the Substitution Cipher

Key Size: The Key for the substitution cipher is larger then that of the Shift Cipher, it is still considered trivial in today’s computing world to brute force every possible combination.

Also as with the Shift Cipher, Letter’s always encrypt to the same cipher text for a given key. Example, L in the “HELLOWORLD” example always produced the ciphertext Q.  This allows for a frequency analysis to be performed allowing for an attacker to guess the key with high degree of success base on the number of repeated characters.