Apostila7 Criptografia

“cripto”
2009/6/30
✐ page 1
Estilo OBMEP

✐
✐

✐

Criptografia
S. C. Coutinho

✐

✐
✐

✐

“cripto”
2009/6/30
✐ page 2
Estilo OBMEP

✐
✐

✐

Texto já revisado pela nova ortografia.

✐

✐
✐

✐

“cripto”
2009/6/30
✐ page i
Estilo OBMEP

✐
✐

✐

Antes de Começar
Estas notas tratam de uma aplicação da matemática à criptografia.
Embora algumas pessoas ainda associem mensagens codificadas a 007 ou outros agentes igualmente secretos, há mais de uma década que esta não é a aplicação mais importante da criptografia. Isto porque, hoje em dia, uma grande variedade de transações que envolvem dinheiro são feitas de maneira eletrônica, desde compras por cartão de crédito via internet a saques em caixas eletrônicos. A informação referente a estas transações segue por linha telefônica ou redes de alta-velocidade e, em ambos os casos, está facilmente sujeita a escutas.
Se a história acabasse aí, eu seria o primeiro a desejar que os bancos regridissem à era do papel! Felizmente, estas informações não trafegam em aberto pela rede telefônica, elas são codificadas, de modo que só o banco, empresa de cartão de crédito ou loja que você está utilizando consegue ler a informação. Assim, mesmo que alguém intercepte a informação com a intenção de esvaziar sua conta, ele não conseguirá interpretar suas informações, que continuarão seguras.
Os processos pelos quais informações enviadas eletronicamente são codificadas depende, de maneira crucial, do uso da matemática. O i ✐

✐
✐

✐

“cripto”
2009/6/30
✐ page ii
Estilo OBMEP

✐
✐

✐

ii mais curioso é que até os anos 1960, a teoria dos números, que é a parte da matemática mais utilizada nas aplicações à criptografia, era considerada quase que destituída de utilidade prática.
O que os matemáticos entendem como teoria dos números é o estudo das propriedades dos números inteiros, e não de quaisquer tipos de números. Por exemplo, questões referentes à fatoração de inteiros, ao cálculo do máximo divisor comum e ao estudo dos números primos, fazem