Sistemas Logicos

Criptografia usando Mapas de Karnaugh

Instituto de Computação (IComp) – Universidade Federal do Amazonas (UFAM)

CEP 69077-000 Av. Rodrigo Otávio, 3000 - Coroado – Manaus – AM – Brasil

[e-mail], [e-mail]

Introdução

Circuitos lógicos são construídos utilizando – se entradas, as operações das portas lógicas e técnicas de simplificação que tornam o resultado final mais simples e mais econômico. A álgebra booleana pode ser utilizada simplificação de expressões booleanas. Ela é um conjunto de regras básicas que oferece legitimidade para as operações lógicas usando variáveis binárias. O mapa de Karnaugh é uma técnica baseada em mapeamento, além da álgebra booleana, é utilizada para simplificação de expressões booleanas. Ela usa uma matriz gráfica para representar as funções boolenas.

A tabela ASCII mostra o padrão de representação em binário, hexadecimal e decimal dos caracteres alfabéticos. Circuitos lógicos construídos a partir das representações em binário dos caracteres alfabéticos podem utilizar a técnica do mapeamento (Mapa de Karnaugh) para as eventuais simplificações. O desenvolvimento mostrará primeiramente a criação da tabela verdade em seguida a criação do mapa de Karnaugh e suas operações para se obter a expressão mínima e assim se construir o circuito lógico correto.

Referencial Teórico

Júlio César utilizava uma técnica conhecida como cifra de substituição para esconder o verdadeiro significado das mensagens trocadas entre seus aliados. Essa cifra ficou conhecida como cifra de César. A cifra de César usava o alfabeto original com um deslocamento de três caracteres, de modo que o quarto caractere se tornasse o primeiro e depois do último caractere fossem introduzidos os três primeiros que foram deslocados inicialmente. As mensagens trocadas eram escritas utilizando esse alfabeto deslocado, sofrendo assim uma cifração, ou seja, tornando-se incompreensíveis para quem não soubesse o protocolo. O protocolo para decifragem das mensagens era previamente construído, e no caso da cifra de césar, a verdadeira mensagem era obtida aplicando-se a substituição de forma inversa.

As mensagens escritas utilizadas utilizando as características da cifra de césar podem ter seus reais significados descobertos por algum interceptador não autorizado, bastando o interceptador aplicar análise de frequência ou ataque de força bruta.

A análise de frequência e ataque de força bruta são técnicas utilizadas pela criptanálise para descobrir o significado das mensagens. As mensagens escritas por Júlio possuía um número reduzido de chaves, por isso a técnica de análise de frequência que observa quantas vezes cada letra, digrama ou trigramas aparecem, ou até mesmo a técnica da força bruta podem descobrir a chave e assim deixar a mensagem compreensível.

Metodologia

Primeiramente foram definidas as entradas do circuito conforme os códigos em binário que representam cada caractere minúsculo do alfabeto e as saídas sendo cada bit dos códigos em binário que representam cada caractere maiúsculo do alfabeto. A construção da tabela verdade forma a base para a construção do circuito. Os mapas de Karnaugh foram criados para simplificações de expressões boolenas. Para a criação e testes do circuito foi utilizado o programa Logisim.

Tabela 1. Tabela Verdade Circuito Lógico

Entradas Saídas

x y z a b c D e Sx Sy Sz S4 S3 S2 S1 S0

0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1

0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0

0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1

0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0

0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1

0 1 1 0 0 1 1 0 0 1 0 0 1 1 0 0

0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1

0 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0

0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1

0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0

0 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1

0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 0

0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1

0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 0

0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1

0 1 1 1 0 0 0 0 0 1 0 1 0 1 1 0

0 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1

0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0

0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1

0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 0

0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 1

0 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0

0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1

0 1 1 1 1 0 0 0 0 1 0 0 0 1 0 0

0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1

0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0

Resultados

A entrada sendo feita com o código em binário que representa o caractere “a” minúsculo mostrou na saída do circuito o código em binário do caractere “G” maiúsculo, ou seja o circuito realizou a cifração do caractere “a”. O valor da entrada “e=1” foi mostrado sem mudança na saída “S0=1”, o valor da entrada “d=0” e ”c=0” foram mostrados nas saídas “S1=1” e “S2=1” respectivamente, conclui-se que depois das operações os valores mostrados foram os complementos de “0” e para os valores das entradas de “a=0” e “b=0” foram mostrados sem mudanças nas saídas “S3=0” e “S4=0”.

Tabela 2. Teste usando os binários de "a" na tabela ASCII

Expressões booleanas simplificadas Saídas Booleano

f