Desde os idos do fim do Império Romano até perto da época do descobrimento do Brasil, esta é a chamada Idade Média. Classicamente o período medieval vai de 476, data da queda do Império Romano, até 1453, data da queda de Constantinopla. O início da Idade Média na Europa é considerado como o "período das trevas" por ter sido a época das grandes proibições. Infelizmente a criptologia também não escapou desta "recessão". Muito do conhecimento sobre o assunto foi perdido porque era considerado magia negra ou bruxaria.

Nesta época, a contribuição árabe-islâmica foi significativa, principalmente com a invenção da criptanálise para a substituição monoalfabética. A denominação "Cifra", "Chiffre", "Ziffer", etc, como também "zero", utilizada em muitas línguas, vem da palavra árabe "sifr", que significa "nulo".

A Itália foi a primeira a acordar do pesadelo medieval, iniciando o movimento renascentista ao redor de 1300. Foi responsável pelos primeiros grandes avanços e, como não podia deixar de ser, também na criptografia. Veneza criou uma organização especializada em 1452, cujo único objetivo era lidar com os segredos, as cifras e as decifrações. Esta organização possuía três secretarias que quebravam e criavam cifras que eram usadas pelo governo.

			Substituição Simples e Criptoanálise
		718-786	al-Khalil, cujo nome completo era Abu Abd al-Rahman al-Khalil ibn Ahmad ibn Amr ibn Tammam al Farahidi al-Zadi al Yahmadi, escreveu o livro Kitab al Mu'amma (O livro das mensagens criptográficas), em grego, para o imperador bizantino. Infelizmente este livro foi perdido. Além disso, al-Khalil decifrou um criptograma bizantino muito antigo. Sua solução baseou-se no início do texto original, que ele supôs corretamente como sendo "Em nome de Deus" - modo comum de começar qualquer texto naquela época. Este método criptanalítico, conhecido como método da palavra provável, tornou-se padrão. Foi usado até na decifração de mensagens cifradas pela máquina Enigma, durante a Segunda Guerra Mundial. (Pommerening)
		801-873	al-Kindi, cujo nome completo era Abu Yusuf Yaqub ibn Is-haq ibn as Sabbah ibn 'omran ibn Ismail Al-Kindi, escreveu Risalah fi Istikhraj al Mu'amma (Escritos sobre a decifração de mensagens criptográficas). Este livro está conservado, sendo o mais antigo sobre criptologia. Nele, o autor faz análises de frequência, razão pela qual Al-Kindi pode ser considerado o bisavô da Matemática Estatística.
		855	Abu Bakr Ahmad ben Ali ben Wahshiyya an-Nabati publicou vários alfabetos cifrantes, os quais eram tradicionalmente usados para mágicas. (Kahn)
		século 1000	O Emirado Ghaznavida foi fundado por Sebük-Tigin, um governador de Ghazni, no Afeganistão. Revoltando-se contra o Emirado Samanida, ele estabeleceu um estado que controlava o Afeganistão, partes da Pérsia e do norte da Índia. O emirado existiu de 977 até 1186. "Alguns documentos com textos cifrados do governo Ghaznavida na Pérsia conquistada sobrevivem e um cronista relata que altos oficiais recebiam cifras pessoais antes de serem enviados para ocupar novos postos. Mas a falta de continuidade dos estados islâmicos e a consequente falha em desenvolver um serviço civil e em criar embaixadas permanentes em outros países acabou por restringir o uso da criptografia." (Kahn)
		1119-1311	O Templo era uma ordem de monges combatentes fundada em 1119 pelos cavaleiros Ugo dei Pagani e Geoffrey de Saint-Omer para proteger os peregrinos na Terra Santa. Logo após a fundação da ordem em Jerusalém, Balduíno II, imperador de Constantinopla, concedeu-lhe um palácio nas proximidades do templo de Salomão, donde se originou o nome Templários. A ordem enriqueceu rapidamente graças a numerosas doações e se tornou uma organização internacional que, por muito tempo, teve uma influência notável, rivalizando com a do rei da França e a do próprio Papa. A organização cifrava suas letras de crédito utilizando um método próprio. Em 1291, os templários foram obrigados a abandonar a Terra Santa, fugindo para a ilha de Chipre. Em 1311, a ordem dos templários foi dissolvida por Felipe, o belo. Em sérias dificuldades financeiras, Felipe mandou prender e torturar os templários, fazendo com que lhe entregassem suas riquezas. Um ano mais tarde, em 1312, um decreto do Concílio de Viena aboliu a ordem.
		1187-1229	Ibn DUNAINIR ou Ibrahim ibn Mohammad ibn Dunainir, é autor do livro redescoberto em 1987, Maqasid al-Fusul al-Mutarjamah an Hall at-Tarjamah (Explicações claras para a solução de mensagens secretas). O livro contém uma inovação importante: cifras algébricas, ou seja, a substituição de letras por números que podem ser transformados aritmeticamente. (Pommerening)
		1187-1268	Ibn ADLAN ou Afif ad-Din ibn Adlan ibn Hammad ibn Ali al-Mousili an-Nahwi al-Mutarjim, é autor do livro redescoberto em 1987, Al-Mu'allaf lil-Malik al-Ashraf (Escrito para o Rei al-Ashraf) com explicações detalhadas de criptoanálise. (Pommerening)
		1226	Em 1226, uma criptografia política discreta apareceu nos arquivos de Veneza, onde "pontos e cruzes substituíam as vogais em algumas palavras esparsas". (Kahn)
		± 1250	O frade franciscano inglês Roger Bacon (1214-1294), conhecido como "Doctor mirabilis", possuía vastos conhecimentos linguísticos, sobre física e as ciências naturais. Corrigiu o calendário Juliano, aperfeiçoou diversos instrumentos de ótica e antecipou várias invenções modernas, tais como máquinas a vapor, telescópios, microscópios, aeroplanos, etc. Descreveu sete métodos de cifras e escreveu: "Um homem é louco se escrever um segredo de qualquer outra forma que não seja a de o dissimular do vulgar." (Kahn)
		anos 1300	`Abd al-Rahman Ibn Khaldun escreveu o Muqaddimah, um importante relato da história que cita o uso de "nomes de perfumes, frutas, pássaros ou flores para indicar letras, ou [...] sobre formas diferentes das formas das letras aceitas" como um código usado entre escritórios militares e de controle de impostos. Ele também inclui uma referência à criptanálise, observando que "escritos conhecidos sobre o assunto estão em poder do povo". (Kahn)