La codificazione per sostituzione consiste nel sostituire una o più entità (solitamente delle lettere) di un messaggio con altre entità diverse.
Si distinguono generalmente più tipi di criptosistemi per sostituzione :
Questa codificazione è una delle più antiche, considerato che era utilizzata anche da Giulio Cesare. Il principio della codifica si basa sull'aggiunta di un valore costante all'insieme dei caratteri del messaggio, o più esattamente al loro codice ASCII (per una versione "informatica" di questa codifica).
Si tratta quindi semplicemente di spostare l'insieme dei valori dei caratteri del messaggio di un certo numero di posizioni, cioè in un certo qual modo di sostituire ogni lettera con un'altra. Ad esempio, spostando il messaggio "KIOSKEA" di 3 posizioni si ottiene "FRPPHQW FD PDUFKH". Quando l'aggiunta del valore da una lettera che passa la Z, basta continuare partendo da A, cosa che porta ad effettuare un modulo 26.
A titolo esemplificativo, nel film 2001: Odissea nello spazio, il computer è chiamato HAL. Questo soprannome è in effetti IBM spostato di una posizione verso il basso…
Il carattere corrispondente al valore che si aggiunge al messaggio per effettuare il criptaggio viene detta chiave. Nel nostro caso la chiave è C, dato che è la terza lettera dell'alfabeto.
Questo sistema di criptaggio è sicuramente semplice da realizzare, ma ha come inconveniente di essere totalmente simmetrico, il che significa che basta fare una sottrazione per conoscere il messaggio iniziale. Un metodo primario può consistere in una semplice sottrazione dei numeri da 1 a 26 per vedere se uno di questi numeri da un messaggio comprensibile.
Un metodo più evoluto consiste nel calcolare le frequenze di apparizione delle lettere nel messaggio codificato (ancora più facile quanto più lungo è il messaggio). Effettivamente, a seconda della lingua, alcune lettere sono più ricorrenti di altre (in francese, ad esempio, la lettera più usata è la E), inoltre la lettera che appare più di frequente in un testo criptato dalla codificazione di Cesare corrisponderà verosimilmente alla lettera E, e quindi con una semplice sottrazione si avrà la chiave del criptaggio...
Nel caso specifico della codificazione di Giulio Cesare dove la chiave di criptaggio è N (tredicesima lettera dell'alfabeto), chiamiamo questo criptaggio ROT13 (il numero 13, la metà di 26, è stato scelto per poter codificare e decodificare facilmente i messaggi di testo).