221
Teorema Fundamental da Aritmética e Números de Gödel
Aplicados à Criptografia
Vilson Vieira da Silva, Jr.1 , Claudio Cesar de Sá1 , Rafael Stubs Parpinelli1 ,
Charles Christian Miers1
1
Universidade do Estado de Santa Catarina (Udesc) – Centro de Ciências Tecnológicas
Campus Universitário Prof. Avelino Marcante s/n – Bairro Bom Retiro
CEP 89223-100 – Joinville – SC – Brasil
[email protected], {claudio, parpinelli, charles}@joinville.udesc.br
Resumo. Através da união do Teorema Fundamental da Aritmética e do conceito formal de número de Gödel, proposto pelo mesmo matemático que lhe dá
nome, busca-se o desenvolvimento de um algorı́tmo criptográfico e sua posterior análise. Para isso é criada uma aplicação real, que demonstra os princı́pios
teóricos nos quais soluções práticas e populares são desenvolvidas, como o algorı́tmo de criptografia para geração de chaves públicas RSA1 .
1. Introdução
A criptografia moderna utiliza de diversos métodos para a criação de algorı́tmos cada vez
mais confiáveis na codificação de dados.
Em sua maioria, tais métodos estão baseados em propriedades de teoremas matemáticos. Desta forma, propôe-se analisar a aplicação de um destes teoremas, o Teorema Fundamental da Aritmética, que usado como axioma em um conceito formal, criado pelo matemático Kurt Gödel [Hintikka 1999], revela-se como base para algorı́tmos
criptográficos.
Permite-se ainda analisar tal algorı́tmo na forma de uma aplicação prática, com o
desenvolvimento de um software de codificação de dados.
O artigo está organizado da seguinte forma: na sessão 2 é apresentado o Teorema
Fundamental da Aritmética, a sessão 3 apresenta os números de Gödel, assim como sua
definição matemática. A sessão 4 une os conceitos dos teoremas apresentados em uma
aplicação prática ligada à criptografia e conclui o artigo através de sua análise.
2. O Teorema Fundamental da Aritmética
O Teorema Fundamental da Aritmética (TFA) [Mollin 1998], inicialmente provado por
Euclides2 enuncia:
Para todo número natural n maior que 1, ou este é um número primo, ou pode
ser escrito como um produto de números primos, de maneira unı́voca.
1
2
Iniciais do sobrenome de seus criadores: Ron Rivest, Adi Shamir e Len Adleman
A prova foi generalizada e tornada correta posteriormente pelo matemático Carl Friederich Gauss
Grahl, E. A; Hübner, J. F. (Eds.). Anais do XV Seminário de
Computação, Blumenau, 20-22 de Novembro, 2006. p 221-228.
222
Por exemplo:
2100 = 22 × 31 × 52 × 71
(1)
A ordem dos fatores, pela propriedade comutativa da multiplicação, é irrelevante.
O que torna tal teorema interessante é a garantia de obtenção de uma representação
única para todo e qualquer número natural. Isso abre diversas possibilidades de aplicação,
como em criptografia, onde um texto pode ser codificado como uma sequência de números
primos.
3. Os Números de Gödel
Kurt Gödel, em 1931, deu um grande passo para para a evolução da matemática com seu
Teorema da Incompletude [Gödel 1931]. Para a prova de tal teorema, Göedel precisou de
uma abstração, uma formalização que o possibilitasse trazer ao seu campo de domı́nio –
a teoria dos números [Andrews 1995] – toda e qualquer sistema formal. Desta maneira,
poderia “operar” sobre tais sistemas com regras aritméticas, botando-os em prova, analisando suas caracterı́sticas, testando portanto sua completude, o objetivo primordial de
sua tese.
Este propôs então os Números de Gödel [Hofstadter 1989], um conceito formal
a partir da teoria dos números.
3.1. Definição
Os Números de Gödel (NG) são definidos por uma função que designa um número natural
a cada sı́mbolo ou fórmula de alguma linguagem formal e a potência destes números
primos seguindo a posicionalidade na palavra ou texto. A estes números naturais dá-se o
nome de Números de Gödel.
Portanto, tendo um conjunto contável S, pode-se definir a função de geração de
Números de Gödel (função de numeração de Gödel) por:
f : S → N
Como para S pode-se ter qualquer conjunto de elementos contáveis, toda e qualquer linguagem formal pode ser convertida para uma representação no domı́nio dos
números naturais.
Para exemplificar, deseja-se criar um Número de Gödel para a palavra abba.
Definindo-se o conjunto S por S = { a, b } pode-se ter a seguinte função de mapeamento
223
aos números naturais:
f (a) = 1
f (b) = 2
(2)
(3)
Agora, como método de concatenação de sı́mbolos, Gödel utilizou a estratégia
de usar os sı́mbolos (já convertidos para números naturais) como expoentes de uma
seqüência de números primos, onde cada sı́mbolo ocupa o expoente de um único número
primo. Portanto, para a palavra abba se tem a representação numérica dada por:
N Gabba = 21 × 32 × 52 × 71 = 3150
Define-se assim uma relação entre o alfabeto de S com os números naturais, onde
a palavra abba constitui o NG 3150, de forma unı́voca.
Os NG são portanto únicos e representam numericamente uma palavra de um sistema formal qualquer. Haja visto que esta representação se faz por produto de números
primos, que por si só são de difı́cil busca por métodos computacionais, têm tal dificuldade
aumentada pelo fato desta representação ter grande complexidade espacial, fazendo crescer o tamanho do NG de maneira exponencial, devido ao produto dos números primos
desta sequência.
4. TFA e NG Aplicados à Criptografia
4.1. Criptografia
Sempre foi desejo do homem manter em segurança certas informações. A criptografia [Schneier 1995] é uma das mais importantes disciplinas por trás desta segurança. Esta,
através da matemática e da ciência da computação, pode criar métodos muito eficientes
de codificação e decodificação, com alto grau de confiabilidade.
Um destes métodos baseia-se no aproveitamento de certas caracterı́sticas encontradas em teoremas matemáticos. Tal estratégia é usada como base, por exemplo, para
um dos sistemas criptográficos mais populares da atualidade: a criptografia por chaves
públicas [Choudhury and Choudhury 2002].
Nesta técnica, são usados números primos e fórmulas matemáticas para a geração
de uma chave pública e privada, únicas para cada indivı́duo. Ao se comunicar, os indivı́duos trocam suas chaves públicas. A partir daı́, uma mensagem codificada pelo dono
da chave pública só poderá ser aberta com a chave privada deste. Assim, se um indivı́duo
deseja enviar uma mensagem ao destinatário, deverá usar a chave pública do destinatário
224
para codificar a mensagem, que só poderá ser aberta pelo destinatário e ninguém mais,
nem mesmo o próprio emissor.
Um exemplo de algorı́tmo gerador de chaves públicas e privadas é o popular
RSA [Rivest et al. 1978], criado em 1978 por Ronald Rivest, Adi Shamir e Len Adleman, e utilizado na codificação em protocolos seguros como SSL 3 [Rescorla 2000] e na
criação de certificados de segurança para serviços de risco como as redes virtuais privadas,
VPN 4 [Holden 2003].
4.2. Formulação
As caracterı́sticas dos Números de Gödel e do Teorema Fundamental da Aritmética possibilita a criação de um algorı́tmo de criptografia baseado em chaves. Dos NG, tal algorı́tmo
herda a função numeradora, que unida com a propriedade da univocacidade garantida pelo
TFA, proporciona a geração de números naturais únicos para cada sı́mbolo ou combinação
destes. Além disso, garante-se também a operação inversa, onde tais números gerados podem ser convertidos novamente aos seus sı́mbolos originais, haja visto que a fatoração é
dada pela sequência 2i × 3j × 5k × 7l × ....
Assim a proposta é fazer uma codificação usando os NG e uma decodificação
através da fatoração destes. Portanto, define-se o algorı́tmo que implementa estas
operações:
Codificação
1. Tendo-se como entrada h w, C i sendo w ∈ L( S ) e C = { ( x , y ) | x ∈ S, y ∈
N, f ( x ) = y } (a chave codificadora), onde L( S ) = { x+ | x ∈ S } e S =
{ a, b } (alfabeto da palavra a codificar);
2. Para cada elemento i da palavra w, toma-se seu par ( i , yi ) da relação definida na
chave C;
3. Encontra-se o NG pela multiplicação da seqüência de números primos dado por
N G = 2y1 × 3y2 × 5y3 × ... × pynn , onde p é o consecutivo número primo n
válido e n o tamanho da palavra w.
Decodificação
1. Tendo-se como entrada h g, C i sendo g ∈ N (um número de Gödel) e C a chave
criptográfica usada na codificação;
2. Fatora-se g (aqui aplicando o método recursivo):
(a) Se g é um primo, retorna-o. Senão, g 0 = pgi sendo pi um número primo i
consecutivo;
(b) Se a divisão não gerar resto, adiciona pi à lista Lg e fatora g 0 . Caso
g
contrário, g 0 = pi+1
e assim sucessivamente, até obter uma divisão sem
resto.
3
4
Secure Sockets Layer
Virtual Private Network
225
3. A lista Lg contém g fatorado. Conta-se, para cada elemento j de Lg , a quantidade
de elementos iguais a j. O valor desta contagem valora kj ;
4. Para cada kj encontrado, toma-se seu par ( j, kj ) da relação definida na chave C;
5. Encontra-se a palavra w, formada pela concatenação dos kj calculados.
4.3. Aplicação
A partir dos algorı́tmos de codificação e decodificação por TFA, pôde-se desenvolver
um software que implementa tal sistema criptográfico. O aplicativo foi desenvolvido
buscando-se certa eficiência, mesmo que somente para a demonstração do método. Para
tal, utilizou-se a linguagem de programação C [Kernighan and Ritchie 1978]. Ainda, para
as operações de fatoração e multiplicação de números naturais, utilizou-se a biblioteca
PARI, componente do sistema de computação algébrica PARI/GP 5 .
Optou-se pelo uso desta biblioteca devida à necessidade da computação de grandes valores numéricos.
Para a execução do software necessita-se, para a codificação, de duas entradas: o
arquivo texto contendo a chave (chave.txt, neste exemplo) e uma palavra que será codificada (original.txt). Para a decodificação, ainda é necessária a chave e o número natural
que será fatorado (criptografado.txt).
O arquivo texto que abriga a chave possui o formato hsı́mbolo códigoi, onde
sı́mbolo é qualquer caractere ASCII e código um número natural maior ou igual a zero.
Como exemplo:
a 1
b 2
As codificações são realizadas pelo parâmetro -c e as decodificações por -d. Um
exemplo de execução seria:
./goedel -c chave.txt < original.txt > criptografado.txt
Ainda, o parâmetro -s leva à execução do show mode, que apresenta todos os
passos realizados na codificação e decodificação de uma palavra dada. Por exemplo:
5
PARI/GP: http://pari.math.u-bordeaux.fr
226
./goedel -s chave.txt < original.txt
*** CODIFICACAO
entrada = aaba
fatoracao = 2ˆ1 3ˆ1 5ˆ2 7ˆ1
codificado = 1050
*** DECODIFICACAO
saida = aaba
A aplicação está disponı́vel no repositório (http://mov.void.cc/archives/goedel0.2.tar.bz2) sobre a licença pública GPL 6 . Maiores informações sobre sua instalação e
uso encontram-se no arquivo README do pacote distribuı́do.
4.4. Análise
A criptografia moderna considera eficiente os algorı́tmos de codificação/decodificação
cujo tempo computacional requerido para sua execução é impraticável por computadores
pessoais e até mesmo por super-computadores [Mao 2003].
Pensando desta forma, o método utilizado fornece uma demonstração do poder
dado pelos números primos no desenvolvimento de algorı́tmos de criptografia.
O software produzido não suporta a codificação de uma palavra de entrada muito
grande, haja visto que para cada elemento desta palavra, é necessário um número primo
que o “represente”, tendo-se portanto alta complexidade espacial. Além disso, para uma
quantidade grande de sı́mbolos, os expoentes de tais números primos serão compostos
por valores de vários dı́gitos, o que aumentará ainda mais o tempo de processamento, alta
complexidade temporal.
Se por um lado isto lembra errôneamente ineficiência, por outro leva à
comprovação de que a quebra de uma chave criptográfica gerada por estratégias semelhantes à empregada, é praticamente impossı́vel, somente conseguida pelo uso de novas
técnicas de processamento [Ord 2002], e ainda não comprovadas.
6
GNU General Public License:http://www.fsf.org/licensing/licenses/gpl.txt
227
5. Conclusões
O Teorema Fundamental da Aritmética revelou fatos interessantes. Aplicá-lo como axioma para os Números de Gödel, fez propor um método criptográfico, que apesar de pouco
eficiente, demonstra a base na qual algorı́tmos de criptografia massivamente usados atualmente são desenvolvidos.
Ainda, descobriu-se que a propriedade da incompletude dos sistemas formais,
descoberta e provada por Kurt Gödel dos Números de Gödel, não é somente uma caracterı́stica de ineficiência de algorı́tmos. Nota-se que se vista de um novo ângulo, o
da criptografia moderna, revela-se como um identificador não da ineficiência, mas da
eficiência de segurança de algorı́tmos criptográficos. Quanto mais os computadores são
incapazes de quebrar as chaves criadas por estes algorı́tmos, mais tempo estes perdurarão
como padrões de codificação.
O software desenvolvido permitiu analisar de maneira prática a teoria aqui desenvolvida. Comprovou-se a dificuldade da decodificação de uma mensagem criptografada,
pela fatoração em termos de números primos de um número natural de milhares de casas
decimais.
Enfim, de axioma para aplicação em novos teoremas, à base para o desenvolvimento de soluções práticas, o Teorema Fundamental da Aritmética prova que as teorias
podem ser usadas para uma gama de aplicações, e não somente destinadas a hipóteses não
implementadas.
Referências
Andrews, G. E. (1995). Number Theory. Dover Publications, 1st edition.
Choudhury, S. and Choudhury, S. (2002). Public Key Infrastructure and Implementation
and Design. Wiley, 1st edition.
Gödel, K. (1931). Uber formal unentscheidbare satze der principia mathematica und
verwandter systeme, i. Mathematik und Physik, 38.
Hintikka, J. (1999). On Gödel. Wadsworth Publishing, 1st edition.
Hofstadter, D. R. (1989). Gödel, Escher, Bach: An Eternal Golden Braid. Vintage Books,
1st edition.
Holden, G. (2003). Guide to Firewalls and Network Security: Intrusion Detection and
VPNs. Course Technology, 1st edition.
Kernighan, B. and Ritchie, D. (1978). The C Programming Language. Prentice Hall, 1st
edition.
Mao, W. (2003). Modern Cryptography: Theory and Practice. Prentice Hall, 1st edition.
Mollin, R. A. (1998). Fundamental Number Theory with Applications. CRC-Press, 1st
edition.
Ord, T. (2002). Hypercomputation: computing more than the turing machine. Honours
Thesis, University of Melbourne.
Rescorla, E. (2000). SSL and TLS: Designing and Building Secure Systems. AddisonWesley Professional, 1st edition.
228
Rivest, R., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures
and public-key cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120-126.
Schneier, B. (1995). Applied Cryptography: Protocols, Algorithms, and Source Code in
C. Wiley, 2nd edition.