p - Universidade Federal de Uberlândia

PEDRO MOISÉS DE SOUSA
POLÍTICA DE SEGURANÇA DE CONTROLE DE ACESSO
MANDATÁRIO EM AMBIENTE CIFRADO
Dissertação apresentada ao programa de Pósgraduação em Ciência da Computação da
Universidade Federal de Uberlândia, como
exigência para obtenção do grau de Mestre em
Ciência da Computação.
Área de concentração: Banco de Dados.
Orientador: Prof. Dr João Nunes Souza, da
Universidade Federal de Uberlândia.
UBERLÂNDIA
Universidade Federal de Uberlândia – UFU
2003
Pedro Moisés de Sousa
POLÍTICA DE SEGURANÇA DE CONTROLE DE ACESSO
MANDATÁRIO EM AMBIENTE CIFRADO
Dissertação apresentada ao Programa de
Pós-graduação em Ciência da Computação
da Universidade Federal de Uberlândia, para obtenção do grau de Mestre em Ciência
da Computação.
Área de concentração: Banco de Dados.
Banca Examinadora:
Uberlândia, 10 de Dezembro de 2003.
________________________________________________
Prof. Dr. João Nunes de Souza – Orientador - UFU
________________________________________________
Prof. Dr. Ilmério Reis Silva – Coorientador- UFU
_______________________________________________
Prof. Dr. Ricardo Dahab - UNICAMP
_______________________________________________
Prof. Dr. Cícero Fernandes de Carvalho - UFU
AGRADECIMENTOS
A elaboração de uma dissertação, apesar de parecer um trabalho solitário, definitivamente
não o é. Seria uma injustiça creditar os resultados somente a quem assina. Certamente, se este
trabalho teve êxito, deveu-se à valiosa colaboração e dedicação de muitas pessoas que merecem aqui ser lembradas:
A começar por Deus, por conceder-me a vida, força e vontade necessárias para levar este
trabalho até o fim.
A minha mãe Aurora Constantino de Lima e ao Frei Beniamino de Luca, Frei Romeu
Amato e a comunidade Italiana que me deram a base educacional para que eu pudesse aqui
chegar.
O Meu Orientador, Prof. Dr. João Nunes de Souza, e o Coorientador, Prof. Dr. Ilmério
Silva Reis, pelo incentivo durante a elaboração dessa dissertação e pela confiança e apoio nos
momentos decisivos.
Os colegas do grupo de criptografia, que gastaram tantas horas discutindo, estudando juntos, criticando, revendo textos e estimulando.
Os professores, secretários, técnicos do Departamento de Informática, que sempre e em
tudo colaboraram.
A todos estes e aqueles que não foram citados, mas não foram esquecidos, dedico a esperança de que este trabalho não tenha sido em vão e de que bons frutos venham a ser colhidos
dele.
“Comece fazendo o que é necessário, depois o que é possível, e de repente você estará fazendo o impossível.”(São Francisco
de Assis).
RESUMO
Este trabalho apresenta uma extensão da política de segurança de controle de acesso
mandatário do modelo Bell-LaPadula (BLP) em um ambiente cifrado. O modelo BLP é analisado em um ambiente onde as tabelas que determinam o controle de acesso são cifradas. As
regras (axiomas) do modelo BLP são armazenadas na forma cifrada e as consultas a tais regras são executadas sem a necessidade de decifrá-las. Desta forma, o acesso de um intruso à
memória principal do servidor de controle de acesso não compromete a segurança do sistema. É proposto um algoritmo que permite manipular dados cifrados no servidor de controle
de acesso sem a necessidade de decifrá-los, aumentando assim a segurança do controle de
acesso mandatário do modelo BLP.
ABSTRACT
This dissertation presents an extension of the mandatory access control security policies of
the Bell-LaPadula model (BLP model) in a ciphered environment. The BLP model is analyzed
in an environment where the access control tables are ciphered. The BLP model axioms are
stored in the ciphered way and the queries to these axioms are performed without deciphering
them. In this way, the access of an intruder to the access control server main memory, cannot
compromise the whole system security. This article proposes an algorithm to manipulate of
ciphered data on the access control server without deciphering them. This algorithm increases the mandatory access control security of the BLP model.
LISTA DE FIGURAS
Figura 1– Lista de potencialidade(CL) ............................................................................... 21
Figura 2– Lista de controle de acesso (ACL).................................................................... 21
Figura 3– Exemplo de um cavalo de Tróia........................................................................ 24
Figura 4 – Conjunto básico .................................................................................................. 57
Figura 5– Conjunto Básico com mais detalhes................................................................. 57
Figura 6– Criptografia simétrica .......................................................................................... 60
Figura 7– Criptografia assimétrica ...................................................................................... 60
Figura 8– Criptografia Convencional .................................................................................. 61
Figura 9– Criptografia de Chave Pública ........................................................................... 63
Figura 10– Geração de Assinatura Digital de um documento........................................ 67
Figura 11 – Usos básicos da função Hash........................................................................ 69
LISTA DE TABELAS
Tabela 1 – Matriz de acesso................................................................................................ 17
Tabela 2 – Tabela Global de Triplas................................................................................... 20
Tabela 3 – Propriedades da Aritmética Modular .............................................................. 37
Tabela 4 – Euclides ampliado (550, 1769) ........................................................................ 46
Tabela 5 – Potência dos Inteiros, Módulo 19.................................................................... 51
Tabela 6 – Tabelas de Logaritmos Discretos, módulo 19............................................... 53
Tabela 7 - Nível clearance Ts.............................................................................................. 73
Tabela 8- Nível corrente Tc................................................................................................. 73
Tabela 9– Nível do objeto To............................................................................................... 73
Tabela 10– Tabela M ............................................................................................................ 74
Tabela 11– Matriz EM ........................................................................................................... 75
SUMÁRIO
1
INTRODUÇÃO ........................................................................................................................................... 12
1.1.
2
ARTIGOS PUBLICADOS ............................................................................................................................... 14
MODELOS DE SEGURANÇA ................................................................................................................. 16
2.1.
INTRODUÇÃO......................................................................................................................................... 16
2.2.
MODELOS DISCRICIONÁRIOS........................................................................................................... 17
2.2.1.
O MODELO MATRIZ DE ACESSO ................................................................................................... 17
2.2.2.
MODOS DE ACESSO ......................................................................................................................... 18
2.2.3.
ADMINISTRAÇÃO DAS AUTORIZAÇÕES ...................................................................................... 18
2.2.4.
IMPLEMENTAÇÃO DO MODELO ..................................................................................................... 19
2.2.5.
UMA LIMITAÇÃO DOS MODELOS DISCRICIONÁRIOS: PROBLEMA DO CAVALO DE
TRÓIA . ................................................................................................................................................................ 22
2.3.
MODELOS MANDATÁRIOS ................................................................................................................. 24
2.3.1.
MODELO BELL-LAPADULA............................................................................................................... 25
2.3.2.
Modos de Acesso ................................................................................................................................. 26
2.3.3.
Estados do Sistema ............................................................................................................................. 27
2.3.4.
Axiomas ................................................................................................................................................. 28
3
INTRODUÇÃO À TEORIA DOS NÚMEROS ........................................................................................ 32
3.1.
NÚMEROS PRIMOS E NÚMEROS RELATIVAMENTE PRIMOS ...................................................................... 32
3.1.1.
Divisores ................................................................................................................................................ 32
3.1.2.
Números Primos ................................................................................................................................... 33
3.1.3.
Números Relativamente Primos......................................................................................................... 34
3.2.
ARITMÉTICA MODULAR .............................................................................................................................. 35
3.2.1.
Operações da Aritmética Modular...................................................................................................... 35
3.2.2.
Propriedades da Aritmética Modular ................................................................................................. 37
3.3.
TEOREMAS DE FERMAT E DE EULER ......................................................................................................... 38
3.3.1.
Teorema de Fermat.............................................................................................................................. 38
3.3.2.
Função Totiente de Euler .................................................................................................................... 39
3.3.3.
Teorema de Euler................................................................................................................................. 40
3.4.
TESTE DE PRIMALIDADE............................................................................................................................. 42
3.5.
ALGORITMO DE EUCLIDES ......................................................................................................................... 43
3.5.1.
Encontrando o Máximo Divisor Comum............................................................................................ 43
3.5.2.
Encontrando o Multiplicativo Inverso ................................................................................................. 44
3.6.
TEOREMA CHINÊS DO RESTO .................................................................................................................... 46
3.7.
LOGARITMOS DISCRETOS .......................................................................................................................... 49
3.7.1.
Potência de um inteiro, Módulo n ..................................................................................................... 49
3.7.2.
Índices .................................................................................................................................................... 52
3.7.3.
Cálculo dos Logaritmos Discretos...................................................................................................... 54
4
CRIPTOGRAFIA ........................................................................................................................................ 55
4.1.
INTRODUÇÃO......................................................................................................................................... 55
4.1.1.
PRINCIPAIS NOTACÕES................................................................................................................... 55
4.1.2.
CRIPTOANÁLISE ................................................................................................................................. 58
4.1.3.
Tipos de SISTEMAS CRIPTOGRÁFICOS ....................................................................................... 59
4.2.
CRIPTOGRAFIA CONVENCIONAL ................................................................................................................. 61
4.2.1.
INTRODUÇÃO ...................................................................................................................................... 61
4.2.2.
Vantagem da Criptografia convencional ........................................................................................... 62
4.3.
CRIPTOGRAFIA DE CHAVE PÚBLICA............................................................................................................ 62
4.3.1.
INTRODUÇÃO ...................................................................................................................................... 62
4.3.2.
O Criptosistema Elgamal em um grupo multiplicativo g. ................................................................ 64
4.3.3.
Criptografia Simétrica X Criptografia Assimétrica............................................................................ 65
4.4.
ASSINATURA DIGITAL.......................................................................................................................... 66
4.5.
FUNÇÕES CRIPTOGRÁFICAS HASH ............................................................................................................. 67
5
POLÍTICA DE SEGURANÇA DO MODELO BELL-LAPADULA EM AMBIENTE CIFRADO ...... 70
5.1.
INTRODUÇÃO .............................................................................................................................................. 70
5.1.1.
O Esquema de Assinatura de Elgamal em Z p ............................................................................... 71
5.2.
REPRESENTAÇÃO E ARMAZENAMENTO DOS ELEMENTOS DO MODELO BLP........................................... 72
5.3.
POLÍTICA DE SEGURANÇA DO MODELO BELL-LAPADULA EM AMBIENTE CIFRADO ....... 75
6
CONCLUSÃO............................................................................................................................................. 83
REFERÊNCIAS BIBLIOGRÁFICAS ............................................................................................................... 84
12
CAPÍTULO 1
INTRODUÇÃO
Uma meta básica em banco de dados distribuídos ou em aplicações na Internet é proteger
tais sistemas contra intrusos que possam acessar dados secretos. É necessária uma política de
segurança para proteger a informação armazenada no banco de dados. Deve-se ter um conjunto de leis, regras e práticas que regulamentam como uma informação é acessada, gerenciada,
protegida e distribuída.
Como essas regras são escritas em uma linguagem natural, geralmente são suscetíveis a
múltiplas interpretações, o que pode comprometer a segurança do sistema. Para evitar tais
ambigüidades, é necessário estruturar uma política de segurança em uma linguagem formal. O
modelo BLP é um modelo formal para a política de controle de acesso mandatário. Este modelo controla o acesso à informação baseando-se na classificação de sujeitos e objetos do sistema. No contexto do modelo BLP os objetos são entidades passivas que armazenam informação, e os sujeitos são entidades ativas que acessam objetos (BELL; LAPADULA, 1975).
Vários modelos de controle de acesso utilizam o modelo discricionário que controla o acesso através da identidade do usuário e das regras que estabelecem os tipos de acesso para
cada usuário e cada objeto (CASTANO, 1994). O principal objetivo do modelo BLP é aumentar o controle de acesso discricionário, adicionando controles de acesso mandatário. Isto reforça as políticas de fluxo da informação, pois o modelo faz duas verificações, a parte discricionária e a mandatária. Este artigo considera a parte mandatária focalizando as regras (axiomas) do modelo BLP.
Mesmo utilizando um modelo formal, ainda há vulnerabilidades. Qualquer usuário que
tenha acesso à memória principal do servidor de controle de acesso ao banco de dados, duran-
13
te o processo de leitura ou escrita de algum objeto, tem acesso a toda a política de segurança
definida pelo modelo BLP. Isto pode inviabilizar o uso do modelo dado que seu principal objetivo é garantir a confidencialidade das informações. Para aumentar a segurança do servidor
de controle de acesso é proposto um algoritmo criptográfico. Tal algoritmo é diferente dos
algoritmos criptográficos usuais, nos quais em geral para processar uma consulta, os sistemas
de segurança fazem a leitura de blocos de dados na memória secundária e os decifram na
memória principal do servidor. Quando dados são decifrados na memória principal do servidor, o sistema pode ser comprometido se algum intruso tem acesso a esta memória. Neste caso, o intruso tem acesso a blocos de dados decifrados na memória principal.
Em criptografia, normalmente são feitas as seguintes considerações. Os intrusos sabem
qual criptosistema está sendo utilizado, como acessar e ler o conteúdo dos canais de comunicação. Considera-se que os canais de comunicação são vulneráveis. Além disso, considera-se
que a segurança do sistema criptográfico está na chave (STALLINGS, 1999). Neste contexto,
considera-se que o servidor de controle de acesso ao banco de dados é inseguro e intrusos têm
acesso à sua memória. Além disso, o problema de segurança do servidor de controle de acesso
ao banco de dados não é resolvido através de ferramentas como firewall ou técnicas tradicionais de criptografia aplicadas a banco de dados distribuídos. A segurança do servidor de controle de acesso ao banco de dados é obtida considerando um algoritmo criptográfico análogo
aos protocolos check e relational definidos em (SOUZA, 2003a). No caso em que o servidor
de controle de acesso ao banco de dados é protegido através de firewall, a técnica apresentada
adiciona mais um nível de segurança. O controle de acesso do modelo BLP é feito verificando
regras (axiomas) cifradas, sem a necessidade de decifrar os dados na memória principal. Finalmente, esta dissertação não considera a política de consultas ao banco de dados. Consultas
como seleção, projeção etc, podem ser executadas em base de dados cifradas sem decifrá-las.
Este problema é considerado em (SOUZA, 2003a) e também em (COSTA, 2003a), (COSTA,
2003b), (COSTA, 2003c), (VIEIRA, 2003a), (VIEIRA, 2003b).
14
Esta dissertação está estruturada da seguinte forma:
O capítulo 2 apresentará uma visão geral sobre os Modelos de Segurança.
O capítulo 3 apresentará uma visão geral dos conceitos da Teoria dos Números, servindo
de referência para os outros capítulos desta dissertação. O Capítulo 4 apresentará uma visão
geral sobre a criptografia, os tipos de criptosistemas existentes e suas principais características. O Capítulo 5 apresentará o Modelo Bell-LaPadula em ambiente cifrado, onde é proposto
um algoritmo criptográfico que permite manipular dados cifrados no servidor de controle de
acesso, sem a necessidade de decifrá-los, podendo, assim, verificar os axiomas do modelo
BLP em um ambiente cifrado. O capítulo 6 traz a conclusão desta dissertação.
1.1. ARTIGOS PUBLICADOS
Título: Política de Segurança de Controle de Acesso Mandatário em Ambiente Cifrado
Local: SSI 2003 - 5º Simpósio de Segurança em Informática realizado nos dia 4, 5 e 6 de
novembro de 2003, no ITA – São José dos Campos.
Comentários: O SSI é um evento de âmbito nacional, que conquistou o reconhecimento
dos profissionais da área de tecnologia da informação (TI), por ter se constituído no principal
fórum de discussão sobre tecnologias de ponta, relacionadas com Segurança em Informática e
abordagem com ênfase no ponto de vista técnico-científico. O SSI 2003 teve como objetivo,
através de uma grande e ampla oferta temática, que incluiu artigos técnico-científicos, palestrantes, pesquisadores, autoridades nacionais e internacionais, painéis e mesas-redondas,
workshops, microcursos, salão de ferramentas e exposição de produtos, tecnologias e serviços, comerciais e acadêmicos.
Título : Modelo Bell-LaPadula em Ambiente Cifrado
Local: ERI 2003 - XI Escola Regional de Informática SBC, realizada nos dia 22 a 26 de
15
Setembro em Londrina – PR.
Comentários: A Escola de Informática da SBC - Paraná (também conhecida como ERI,
pelo antigo nome Escola Regional de Informática) é um evento da SBC - Sociedade Brasileira
de Computação, que, apesar de sua organização regionalizada, é aberta a participação de estudantes, professores e profissionais de todo o País.
O objetivo geral da ERI é possibilitar aos estudantes e profissionais de informática o contato com tópicos que estão na vanguarda da pesquisa na área de informática, que estejam em
evidência no País e no exterior, integrar a comunidade de informática, além de proporcionar a
divulgação das principais atividades acadêmicas desenvolvidas pelas universidades locais.
16
CAPÍTULO 2
MODELOS DE SEGURANÇA
2.1. INTRODUÇÃO
Segurança é um tema discutido com freqüência e gerador de polêmicas em qualquer área
da computação; a extensão bibliográfica desta área é, por si só, uma prova deste fato. Como
será visto a seguir, os modelos de segurança permitem aos desenvolvedores representar e verificar claramente as propriedades de segurança de um sistema. O objetivo da modelagem de
segurança é produzir um modelo conceitual, independente, de alto nível, partindo das especificações requeridas que descrevem a proteção necessária do sistema. Um modelo de segurança fornece uma rica representação semântica, a qual permite que propriedades funcionais e
estruturais do sistema de segurança sejam descritas.
Na descrição dos modelos da segurança, os seguintes aspectos são examinados para cada
modelo (CASTANO, 1994):
― Sujeitos – são entidades ativas do sistema, que pedem acesso aos objetos;
― Objetos – são entidades passivas do sistema, que contêm as informações a serem protegidas contra acessos/modificações não autorizadas;
― Modos de acesso – representam o tipo de acesso que o sujeito pode exercer sobre um
objeto; a execução causa o fluxo da informação do sujeito ao objeto e vice-versa;
― Políticas – são as leis que controlam os acessos;
― Axiomas – são as regras que devem ser satisfeitas durante o funcionamento do sistema.
17
2.2. MODELOS DISCRICIONÁRIOS
Esta seção considera uma análise dos modelos discricionários de segurança. Estes modelos são caracterizados pelo controle de acesso através da identidade do usuário e das regras
que estabelecem os tipos de acesso para cada usuário e objeto (CASTANO, 1994).Além disso, o criador do objeto pode ceder ou revogar acessos.
A seguir, apresenta-se o modelo matriz de acesso como exemplo de um modelo discricionário.
2.2.1. O MODELO MATRIZ DE ACESSO
O modelo matriz de acesso foi proposto por Harrison et al em 1976 (CASTANO, 1994).
Ele se fundamenta no estado da autorização, que é uma tripla Q=(S, O, A) onde:
•
S – conjunto de sujeitos (usuários, processos, domínios);
•
O – conjunto de objetos (conjunto de entidades que devem ser protegidas: banco de
dados, tabelas, registros);
•
A = é a matriz de acesso, onde as linhas correspondem aos sujeitos e as colunas aos
objetos e a entrada A[s,o] contém o modo de acesso para qual o sujeito s tem autorização sobre o objeto o, conforme a tabela 1.
Tabela 1 – Matriz de acesso
Sujeitos
Objetos
O1
...
Oj
...
Om
S1
A[s1,o1]
...
A[s1,oj]
...
A[s1,om]
...
...
...
...
...
...
si
A[si,o1]
...
A[si,oj]
...
A[si,om]
...
...
...
...
...
...
sn
A[sn,o1]
...
A[sn,oj]
...
A[sn,om]
18
2.2.2. MODOS DE ACESSO
O conjunto de modos de acesso depende dos objetos considerados. Geralmente, eles são:
― Read: ler informação;
― Write: escrever;
― Append: agregar informação;
― Own: proprietário.
Além disso, se a entrada da matriz A[s,o] contém o modo de acesso proprietário, então s é
considerado proprietário de o, e como tal é permitido administrar os modos de acesso sobre o.
2.2.3. ADMINISTRAÇÃO DAS AUTORIZAÇÕES
A inclusão do modo de acesso proprietário permite que a política de propriedade seja reforçada pelo modelo, permitindo que os sujeitos administrem as autorizações sobre os objetos que criaram. O proprietário de um objeto pode conceder/revogar para outros sujeitos algum modo de acesso sobre o objeto (exceto o modo de acesso proprietário, o qual não pode
ser transferido) mesmo se ele não tenha pessoalmente a autorização para esse modo de acesso.
Suponha, por exemplo, que um sujeito s seja proprietário de um objeto o e tenha somente o
modo de acesso de leitura sobre o, então ele pode conceder a outros sujeitos todos os modos
de acesso citados acima, exceto o de proprietário.
Em alguns sistemas, o modo de acesso que permite a propagação de direitos de acesso
sobre um objeto o pode pertencer a sujeitos que não sejam proprietários do objeto o. Esses
sujeitos devem explicitamente estar autorizados a “conceder” algum modo de acesso. O modelo da matriz de acesso representa tais modos de acesso utilizando dois tipos de bandeira:
bandeira da cópia, denotada por *, e a bandeira de transferência, denotada por +. Seja m um
modo de acesso genérico:
19
― Se m* pertence a A[s,o], o sujeito s está autorizado conceder o modo de acesso m sobre o objeto o, para outros sujeitos; tal fato é indicado pelo símbolo * sobre m. Observe que o sujeito s concede m, mas não a bandeira *. No exemplo a seguir, há a transferência do modo de acesso de leitura sobre um objeto:
Command TRANSFERread(subject1,subject2, file)
If R* in A[subject1, file]
Then enter R into A[subject2,file]
End.
― Se m+ pertence a A[s,o], então s pode transferir para outros sujeitos o modo de acesso
m sobre o objeto o. Mas ao fazer isso, ele perde o modo de acesso e a possibilidade de
concedê-lo. O modo de acesso e a habilidade de administrá-lo são transferidos ao donatário. No exemplo a seguir, ocorre a transferência do privilégio leitura, possuída pelo doador com a bandeira de transferência:
Command TRANSFER-Onlyread(subject1,subject2, file)
If R+ in A[subject1, file]
Then delete R+ from A[subject1,file]
enter R+ from A[subject2,file]
End.
2.2.4. IMPLEMENTAÇÃO DO MODELO
O modelo discricionário é implementado utilizando uma matriz de Acesso, conforme indicado na tabela 2.
20
Tabela 2 – Tabela Global de Triplas
S
P1
P1
P1
P1
P2
P2
P3
P3
P3
O
F1
F2
M1
P2
F1
M1
F1
F2
M2
A[s,o]
Own,R,W
E,R+
R,W,E
R
R,W
W
R,W, E+
Own,E
W,E
Os estados da matriz de acesso representam as autorizações contidas no sistema, isto é, os
modos de acesso que cada sujeito pode exercitar sobre cada objeto. No modelo discricionário, cada pedido de um sujeito para acessar um objeto em um dado modo de acesso é mediado pelos mecanismos do controle de acesso. Tais mecanismos permitem o acesso se, e somente se, o sujeito possui o modo de acesso sobre o objeto, isto é, se as entradas correspondentes
na matriz contêm o modo de acesso requisitado. Suponha, por exemplo, um sujeito s, um objeto o e uma entrada em A[s,o] que seja de leitura e escrita. Então, o sujeito s poderá executar
sobre o objeto o somente os modos de acesso de leitura e escrita.
Deve-se notar que armazenar uma matriz com disposição bidimensional é ineficaz. Mesmo no caso em que a matriz é escassa, ela pode ocupar uma grande área de memória. Um método possível do armazenamento consiste em uma tabela global de triplas (Si, Oj, A[si,oj]) com
diversos elementos iguais às entradas não nulas de A (conforme a tabela 2 acima). Entretanto,
esta aproximação tem algumas desvantagens:
― Desperdício da memória, porque pode haver muitos sujeitos/objetos inativos;
― O considerado nível de granularidade para os objetos e sujeitos pode fazer com que a
tabela ocupe muito espaço na memória;
― A busca de informações nesta tabela não fornece uma visibilidade imediata.
Uma alternativa mais comum para a implementação da matriz de acesso é o armazenamento por linhas e o armazenamento por colunas.
21
F1
Own, R
F2
E , R+
M1
R, W, E
P2
R
P1
R, W
P2
W
P1
R, W, E+
P2
Own, E
P3
W, E
P1
P2
P3
Figura 1– Lista de potencialidade(CL)
― Armazenamento por linhas. Neste caso, tem-se uma lista associada a cada sujeito. Cada elemento da lista indica um objeto do sistema e o modo de acesso que esse sujeito
tem sobre o objeto. Para cada sujeito Si na matriz de acesso, a lista associada a Si contém pares (oj,A[si,oj]), tal que A[si,oj] é não nulo. Esta lista é chamada de lista da potencialidade (CL) do sujeito. A figura 1 mostra um exemplo de CL, na qual cada sujeito pertencente à lista [p1, p2, p3] referencia os objetos que podem ser acessados por
eles, bem como seus modos de acesso.
P1
Own, R
P2
R, W
P3
R, W, E+
P1
E, R +
P3
Own, E
P1
P1
R, W, E
P2
P2
W
P3
W, E
P1
R
F1
F2
M1
M2
P3
Figura 2– Lista de controle de acesso (ACL)
22
― Armazenamento por colunas. Neste caso, tem-se uma lista associada a cada objeto.
Cada elemento da lista indica um sujeito e os modos de acesso que este sujeito tem
sobre o objeto que define a lista. Para cada objeto Oj na matriz de acesso, a lista associada a Oj contém pares (Si,A[si,oj]), tal que A[si,oj] não é nulo. A lista associada para
cada objeto é uma lista de autorizações ou Lista de controle de acesso (ACL) do objeto. A figura 2 mostra um exemplo de ACL, na qual cada objeto pertencente à lista [F1,
F2, m1, m2, p1, p2, p3] referencia os sujeitos que podem acessá-los, bem como os
modos pelos quais os sujeitos podem acessar estes objetos.
2.2.5. UMA LIMITAÇÃO DOS MODELOS DISCRICIONÁRIOS: PROBLEMA DO
CAVALO DE TRÓIA.
Uma limitação dos modelos discricionários é o problema do cavalo de Tróia.Um cavalo
de Tróia é um programa de computador com função aparentemente ou realmente útil, mas que
contém funções escondidas. Neste caso, tais funções exploram secretamente as autorizações
legítimas do processo invocado.
O exemplo a seguir descreve um cavalo de Tróia que fornece informação a usuários desautorizados, apesar do controle de acesso discricionário.
Suponha que o usuário x crie um arquivo F1 e escreva alguma informação nele. Suponha,
também, que o usuário y crie um arquivo F2. O usuário y é o proprietário do arquivo F2 e conseqüentemente é permitido a ele executar qualquer operação no arquivo F2. Em particular, y
pode conceder a outros usuários autorizações sobre o arquivo F2. Suponha então que y conceda a x o modo de acesso da escrita no arquivo F2. Considere agora um programa P (um cavalo de Tróia), que executa alguma função de serviço público. Além disso, suponha que o programa P contenha uma parte escondida de código, composto de operações de leitura no arquivo F1 e operações de escrita no arquivo F2 (figura 3a).
23
Suponha que x solicita a execução do programa P. O processo que executa o programa P
funciona com os modos de acesso da chamada do usuário x. Isto é, todos os pedidos do acesso
são verificados conforme as autorizações do usuário x. Considere em particular a execução de
um código escondido contido em P. Suponha que a operação de leitura sobre F1 é requisitada
por este código escondido. Desde que x é o proprietário do arquivo, a operação é concedida.
Suponha também que uma operação de escrita no arquivo F2 seja pedida. Desde que x possua
o modo de acesso de escrita sobre F2, a operação de escrita é concedida. Conseqüentemente,
durante a execução do programa P, foi transferida informação do arquivo F1 para F2. Como y
tem acesso aos dados em F2, a informação transferida de F1 pode ser lida por y. Observe que
o usuário y não tem a autorização de leitura da informação contida em F1, mas após a execução de P, o usuário y consegue ler informação contida em F1, conforme ilustrado na figura
3b. Neste caso, uma transmissão ilegal da informação para um usuário não autorizado y foi
executada, apesar do controle de acesso discricionário.
Este exemplo ilustra como limitações indicadas pelas autorizações discricionárias podem
ser burladas, produzindo, assim, falhas na garantia da satisfação da autorização imposta pela
política discricionária.
A figura 3 ilustra o funcionamento de um cavalo de Tróia, onde a) o programa P contém
um código escondido para acessar os arquivos F1 e F2; y pode conceder “escrita” sobre F2; b)
depois que o usuário x executa o programa, o usuário y tem o acesso à informação transferida
do arquivo F1 (a que usuário y não tem o modo de acesso de leitura) para F2 (que ele pode
ler).
24
a)
b)
Arquivo F 1
Prog rama P
Usuário x → Programa P
AB C D E
Proprietá rio x
Leitur a F1
Leitura F1
Escrita F2
A rqu ivo F1
A BC D E
Ar quivo F 2
Escrit a F2
Proprietário x
A rqu ivo F2
ABCD E
Proprietário y
(x, escrita, F 2)
Proprietário y
( x, esc rita, F 2 )
Figura 3– Exemplo de um cavalo de Tróia
O modelo matriz de acesso fornece um conjunto de regras e mecanismos a fim de modelar um sistema de segurança. Ele pode ser usado tanto para sistemas operacionais quanto para
banco de dados. É um modelo discricionário, e por isso apresenta uma maior flexibilidade se
comparado aos modelos mandatários. Contudo, a principal desvantagem deste é não controlar
a disseminação da informação, ou seja, após a autorização sobre uma dada informação não há
nenhum controle do que será feito com ela, o que o torna vulnerável a ataques do tipo cavalo
de Tróia mencionado anteriormente.
Uma melhoria deste modelo é obtida considerando o modelo mandatário, analisado na
próxima seção.
2.3. MODELOS MANDATÁRIOS
Os modelos mandatários são caracterizados pelo controle de acesso através da classificação dos sujeitos e objetos do sistema. Um acesso é cedido se algum relacionamento é satisfeito entre classificações de sujeitos e objetos.
Esta seção apresenta o modelo Bell-LaPadula como um exemplo de um modelo mandatário.
25
2.3.1. MODELO BELL-LAPADULA
O modelo Bell-LaPadula (BLP) foi proposto por Bell e LaPadula em 1973 para garantir o
controle de acesso em aplicações governamentais e militares (BELL; LAPADULA, 1975). Ele é
uma extensão do modelo de acesso matricial (CASTANO, 1994), no qual os elementos do
sistema são classificados. A confidencialidade é expressa como um conjunto de regras (axiomas) que devem ser satisfeitos durante o funcionamento do sistema. Além disso, o modelo
BLP é atualmente um modelo de referência para proteção de dados sob política mandatária
(CASTANO, 1994).
O modelo BLP é baseado na classificação dos elementos de segurança que definem a política de acesso ao sistema. Esta classificação é expressa por níveis de segurança, onde cada
nível é definido por dois componentes: uma classificação (C) e um conjunto de categorias
(K).
Uma classificação é um elemento que pertence ao conjunto:
{Top Secret(TS), Secret(S) , Confidential(C), Unclassified(U)}.
Além disso, considera-se que estes elementos definem a ordem total a seguir:
TS > S > C > U.
O conjunto de categorias não possui nenhuma hierarquia e os seus elementos são definidos de acordo com o ambiente ou área de aplicação do modelo. Como exemplo, as categorias
podem ser áreas de um sistema ou departamentos de uma organização. Um nível de segurança
é denotado pelo par L = (C ,K), no qual C é uma classificação e K um conjunto de categorias.
O par L1 = ( TS, {gerência, departamento financeiro} ) é um exemplo de nível de segurança que define a classificação da gerência e do departamento financeiro.
O modelo BLP se fundamenta no paradigma sujeito-objeto. Os sujeitos são elementos
ativos do sistema, que podem executar ações, e os objetos são elementos passivos, que contêm informação. A política mandatária controla o acesso à informação através da classificação
26
dos sujeitos e dos objetos do sistema. Esta classificação define níveis de segurança que refletem informações agregadas a sujeitos e objetos, e auxiliam nas decisões do controle que é
utilizado na política mandatária. As decisões de controle se fundamentam na relação de ordem
definida entre os diferentes níveis de segurança. Considere dois níveis de segurança:
― L1 = (C1 ,K1);
― L2 = (C2, K2).
O nível L1 é maior ou igual (domina) o nível de L2, se e somente se:
― C1
≥
C2 (C1 domina C2);
― K1 ⊇ K2 (K1 contém K2).
Observe que no modelo BLP os níveis de segurança são associados a sujeitos e objetos.
Dado um sujeito, seu nível de segurança reflete a autorização que o mesmo tem para acessar
determinada informação. Além disso, no momento da criação de um sujeito, lhe é atribuído o
nível de segurança máximo, denominado clearance (Ls), e um nível de segurança corrente
(Lc), o qual deve ser menor ou igual ao clearance. Logo, tem-se que Lc ≤ Ls.
Dado um objeto, seu nível de segurança o protege de acessos não autorizados, sendo atribuído a cada objeto somente um nível de segurança. Este nível de segurança se fundamenta
na sensibilidade da informação contida no objeto. O nível de segurança do objeto determina
quem pode ler a informação contida no objeto.
A próxima seção apresenta os modos de acesso e as funções de verificação de nível do
modelo BLP.
2.3.2. MODOS DE ACESSO
O modelo BLP considera os seguintes modos de acesso associados a sujeitos e objetos:
― Read-Only: ler informação;
― Append: agregar informação sem ler o conteúdo do objeto;
27
― Execute: executar um objeto (programa);
― Read-Write: ler e escrever.
No modelo BLP os modos de acesso são executados pelos sujeitos sobre os objetos. Isto
significa, por exemplo, que se um sujeito s tem o modo de acesso Execute sobre um objeto o,
então é permitido a s executar o objeto o.
2.3.3. ESTADOS DO SISTEMA
No modelo BLP o mecanismo de segurança é caracterizados pelo estado do sistema. O
estado do sistema no modelo BLP é descrito pela 4-tupla (b,M,f,H), onde:
― b é o conjunto de acesso corrente. Este conjunto é composto por triplas (s,o,m), onde
cada tripla indica que o sujeito s tem direito de acesso corrente no modo m sobre o
objeto o.
― M é a matriz de acesso definida conforme o modelo discricionário. Esta matriz é
composta por entradas M[s,o], que indica um modo de acesso de um sujeito s sobre
um objeto o. Note que b não representa a matriz de controle de acesso. O conjunto b
não identifica todos os acessos possíveis. Ele identifica apenas o acesso corrente.
― f é a função de nível. Esta função associa a sujeitos e objetos o seu nível de segurança no sistema. O domínio da função nível é o conjunto dos sujeitos e objetos e o contradomínio é o conjunto dos níveis do sistema. Uma função de nível f associa a um
sujeito s o seu nível, que é indicado por f(s). Da mesma forma, o nível de um objeto
o é dado por f(o). As funções de nível são usadas para identificar, por exemplo:
•
O nível máximo de um sujeito s. Este nível é denominado por clearence e é determinado pela função de nível fs;
•
O nível corrente de um sujeito. Este nível é determinado pela função de nível fc.
No modelo BLP o nível corrente é aquele que o sujeito utiliza para se conectar ao
28
sistema e acessar objetos. Além disso, o nível corrente deve ser sempre menor ou
igual ao clearance. Logo, para todo sujeito s, deve-se ter fc(s) ≤ fs(s);
•
O nível de segurança de um objeto é determinado pela função de nível fo .
As funções de nível são utilizadas para verificar os axiomas do controle de acesso mandatário do modelo BLP.
― H é a hierarquia corrente dos objetos. A hierarquia é uma árvore que possui os objetos como nó, sendo que os objetos inativos não são incluídos. Esta árvore satisfaz a
propriedade de compatibilidade que estabelece que o nível de segurança de um objeto
deve dominar o nível de segurança de seus pais. Esta propriedade garante que somente
sujeitos de níveis superiores possam descer na árvore para acessar objetos com níveis
de segurança maiores.
2.3.4. AXIOMAS
O modelo BLP contém dois axiomas que devem ser satisfeitos para que a segurança do
sistema seja garantida. Conforme o modelo BLP, um sistema é seguro se e somente se ele satisfaz as seguintes propriedades (axiomas):
― Propriedade de Segurança Simples (ss). Um sujeito pode ter acesso de leitura ou
escrita sobre um objeto se e somente se o clearance do sujeito domina o nível de segurança do objeto.
A propriedade de segurança simples garante que sujeitos não acessem informação acima
do seu nível máximo de segurança, que é o clearence.
No modelo BLP um sujeito é não confiável se ele pode comprometer a segurança do sistema. A propriedade estrela, considerada a seguir, restringe o acesso de sujeitos não confiáveis.
29
― Propriedade Estrela (*):
a) Um sujeito não confiável s pode ter o modo de acesso append sobre um objeto o,
se o nível de segurança do objeto domina o nível corrente de segurança do sujeito.
b) Um sujeito não confiável s pode ter acesso de write a um objeto o, se e somente
se o nível de segurança do objeto é igual ao nível corrente de segurança do sujeito.
c) Um sujeito não confiável s pode ter acesso de read a um objeto o, se e somente se
o nível de segurança do objeto é dominado pelo nível corrente de segurança do sujeito.
No modelo BLP é definida a matriz M dos modos de acesso dos sujeitos sobre os objetos. Uma entrada desta matriz, indicada por M[s,o], representa o conjunto dos modos de acesso do sujeito s sobre o objeto o. Um sistema satisfaz a propriedade * se e somente se:
― append ∈ M[s,o] ⇒ fc (s) ≤ fo (o);
― write ∈ M[s,o] ⇒ fc (s) = fo (o);
― read ∈ M[s,o] ⇒ fc (s) ≥ fo (o).
Além das relações acima, o modelo BLP apresenta outras propriedades:
― Se um sistema satisfaz a propriedade *, então ele também satisfaz a propriedade ss.
― Em um ambiente onde os usuários são confiáveis, basta considerar a propriedade ss
para obter a segurança do sistema. Neste contexto, os usuários não tentam comprometer a segurança revelando informações confidenciais a outros usuários que só têm acesso a informações públicas.Por exemplo: Jim (confidential) pode ler um documento
(unclassified) para avaliar uma decisão salarial (confidential). De acordo com o axioma ss, Jim pode escrever a decisão num documento público (unclassified). Mas um
sujeito confiável não faria isso. Por isso que o axioma ss permite que ele faça, pois ele
confia que o sujeito não irá ferir a segurança do sistema.
30
― A propriedade * é requerida para deter sujeitos não confiáveis, ou seja, de acordo
com o axioma *, um sujeito Jim não-confiável não pode escrever em um documento
público (unclassified). Isto evita que Jim faça pública a decisão salarial que é confidencial. Ou seja, a propriedade * garante que um sujeito não-confiável não irá ferir a
segurança do sistema.
As propriedades * e ss são resumidas em dois princípios:
― No read-up secrecy: um sujeito só pode ler objetos cujos níveis de segurança são
dominados pelo nível do sujeito;
― No write-down secrecy: um sujeito só pode escrever em objetos cujos níveis de segurança dominam o nível de segurança do sujeito.
Esta seção abordou o Modelo Bell-LaPadula, como exemplo da Política Mandatária; verifica-se que as vantagens dos Modelos Mandatários derivam basicamente da conveniência de
se classificar os sujeitos e objetos. Além disso, eles determinam mecanismos de certificação
para segurança. Em relação ao problema do cavalo de Tróia, se uma Política Mandatária é aplicada, aos arquivos F1 e F2, que têm exigências de proteção diferentes, esses terão um nível
de segurança diferente. Assim, se o nível de segurança do programa P é tal que o programa
pode ler arquivo F1, P não poderá escrever F2. O modo de acesso de escrita será bloqueado
então pelas regras da Política Mandatária.
O modelo Bell-LaPadula suporta controle de acesso mandatário determinando direitos de
acessos através dos níveis de segurança associados a sujeitos e objetos, e também suporta
controles de acessos discricionários checando os modos de acesso através da matriz de acesso.
Estabelece os dois princípios No Read-Up e No Write-Down para preservar informações secretas.
O modelo BLP foi o primeiro modelo disponível para a comunidade de segurança em
31
computadores. Este modelo, implementado em ambientes militares, é considerado o modelo
de referência para proteção de dados em políticas mandatárias (CASTANO, 1994).
32
CAPÍTULO 3
INTRODUÇÃO À TEORIA DOS NÚMEROS
Um grande número de conceitos da Teoria dos Números é essencial ao projeto de algoritmos criptográficos de chave pública. Este capítulo disponibiliza uma visão geral destes
conceitos, os quais foram referenciados em outros capítulos desta dissertação.
3.1. NÚMEROS PRIMOS E NÚMEROS RELATIVAMENTE PRIMOS
O objetivo desta seção é oferecer uma visão geral sobre números primos, abordando os
aspectos relevantes ao assunto de que trata esta dissertação.
3.1.1. DIVISORES
Diz-se que b ≠ 0 divide a , se a = mb para algum m , onde a , b e m são inteiros. Isto
é, b divide a se não houver resto na divisão. A notação b a é comumente utilizada para denotar que b divide a . Da mesma forma, se b a , diz-se que b é um divisor de a .
Se b g e b h , então b (mg + nh) para inteiros arbitrários m e n .
Uma prova do fato acima é a seguinte:
Se b g , então g é da forma g = b × g 1 para algum inteiro g 1
Se b h , então h é da forma h = b × h1 para algum inteiro h1
Portanto, mg + nh = mbg 1 + nbn 1 = b × (mg 1 + nh1 ) . Logo, b divide mg + nh .
33
3.1.2. NÚMEROS PRIMOS
Um inteiro p > 1 é um número primo se seus únicos divisores são ± 1 e ± p . Números
primos desempenham um papel fundamental na Teoria dos Números e em criptografia.
Qualquer inteiro a > 1 pode ser fatorado, de uma única maneira, na forma
a = p 1α1 p 2α 2 L p tα t
tal que p 1 > p 2 > L > p t são números primos e α i > 0 , para todo i .
Se P é o conjunto de todos os números primos, então qualquer inteiro positivo pode ser
escrito na seguinte forma:
a=∏ p
ap
onde cada a p ≥ 0
P
O valor de qualquer inteiro positivo pode ser especificado simplesmente listando-se todos
os expoentes, diferentes de zero, presentes na formulação anterior. Dessa forma,
O inteiro 12 é representado por {a 2 = 2, a 3 = 1}
O inteiro 18 é representado por {a 2 = 1, a 3 = 2}
A multiplicação de dois números é equivalente à adição dos expoentes correspondentes
em sua fatoração. Se, k = mn então k p = m p + n p , para todo p .
Exemplo: Considere k = 12 × 18 = 216 .
Neste caso, 216 = 2 3 × 3 3 = 2 2 × 3 × 2 × 3 2 = 12 × 18
O que isto significa, em termos destes fatores primos, é que se a b , então os fatores primos de a dividem os respectivos fatores primos de b
Exemplo: Se a = 12 ; b = 36 ; 12 36 ; 12 = 2 2 × 3 ; 36 = 2 2 × 3 2 .
Neste caso a 2 = 2 = b 2 e a 3 = 1 ≤ 2 = b3
34
3.1.3. NÚMEROS RELATIVAMENTE PRIMOS
A notação gcd (a, b ) é utilizada para denotar o máximo divisor comum de a e b . O inteiro positivo c é denominado máximo divisor comum de a e b se
―
c for um divisor de a e b;
―
qualquer divisor de a e b for um divisor de c.
Uma definição equivalente a esta é a seguinte:
gcd (a, b ) = max [k, tal que k a e k b]
Uma vez que o máximo divisor comum deve ser positivo, tem-se que:
gcd (a, b ) = gcd (a,−b ) = gcd (− a, b ) = gcd (− a,−b ) , ou seja, gcd (a, b ) = gcd ( a, b ) .
Como 0 é divisível por qualquer inteiro diferente de zero, tem-se que gcd (a,0 ) = a .
É fácil determinar o máximo divisor comum de dois inteiros positivos se ambos forem fatorados.
Exemplo: Considere 300 = 2 2 × 3 1 × 5 2 e 18 = 2 1 × 3 2
gcd (18, 300 ) = 2 1 × 3 1 × 5 0 = 6
Em geral, se k = gcd (a, b ) , então k p = min (a p , b p ) , para todo p .
Determinar os fatores primos de um número grande não é uma tarefa fácil. Por isso, o resultado anterior não auxilia diretamente no cálculo do máximo divisor comum.
Dois inteiros a e b são relativamente primos se não tiverem fatores primos diferentes de 1
em comum. Isto é equivalente a dizer que a e b são relativamente primos se gcd (a, b ) = 1 .
Exemplo: 8 e 15 são relativamente primos porque os divisores de 8 são 1, 2, 4 e 8, e os
divisores de 15 são 1, 3, 5 e 15. Portanto, 1 é o único número presente em ambas às listas.
35
3.2. ARITMÉTICA MODULAR
Dado qualquer inteiro positivo n e qualquer inteiro a, se a for dividido por n, obtém-se
um quociente q e um resto r, tal que a = qn + r , 0 ≤ r < n ; q = a/n .
Dados a e um positivo n, sempre é possível encontrar q e r que satisfaçam a relação precedente. O resto r também é denominado resíduo.
Se a é um inteiro e n é um inteiro positivo, define-se a mod n como o resto obtido da divisão
de
a
por
n.
Assim,
para
qualquer
inteiro
a,
pode-se
escrever
que
a = a/n × n + (a mod n ) .
Exemplo: 11 mod 7 = 4 ; − 11 mod 7 = 3 .
Dois inteiros a e b são ditos congruentes módulo n se (a mod n ) = (b mod n ) . Isto é denotado por a ≡ b mod n .
Exemplo: 73 ≡ 4 mod 23 ; 21 ≡ −9 mod 10
Deve-se notar que se a ≡ 0 mod n , então n a .
O operador módulo possui as seguintes propriedades:
1. a ≡ b mod n se n (a − b ) .
2. Se (a mod n ) = (b mod n ) então a ≡ b mod n .
3. Se a ≡ b mod n então b ≡ a mod n .
4. Se (a ≡ b mod n ) e (b ≡ c mod n ) então a ≡ c mod n .
3.2.1. OPERAÇÕES DA ARITMÉTICA MODULAR
Por definição, o operador (mod n ) mapeia todos os inteiros em um conjunto de inteiros
{0, 1, L , (n − 1)} . A questão que esta definição suscita é: seria possível realizar operações a-
36
ritméticas restritas ao universo deste conjunto? A resposta é sim, e isso é possível mediante a
utilização da técnica conhecida por Aritmética Modular.
A Aritmética Modular possui as seguintes propriedades:
1.
[(a mod n) + (b mod n)] mod n = (a + b ) mod n
2.
[(a mod n) − (b mod n)] mod n = (a − b ) mod n
3.
[(a mod n)× (b mod n)] mod n = (a × b) mod n
Para demonstrar a primeira propriedade, considere que (a mod n ) = ra e (b mod n ) = rb .
Logo, a = ra + jn , para algum inteiro j, e b = rb + kn , para algum inteiro k. Assim, tem-se
que
(a + b ) mod n = (ra
+ jn + rb + kn ) mod n
= (ra + rb + (k + j )n ) mod n
= (ra + rb ) mod n
= [(a mod n ) + (b mod n )] mod n
Seguindo o mesmo raciocínio, as demais propriedades podem ser demonstradas.
A exponenciação módulo n é feita através da realização de repetidas multiplicações, como na Aritmética comum. Para encontrar, por exemplo, 117 mod 13 , deve-se proceder da
seguinte maneira:
11 2 = 121 ≡ 4 mod 13 ⇒ 11 4 ≡ 4 2 ≡ 3 mod 13 ⇒ 117 ≡ 11 × 4 × 3 ≡ 132 ≡ 2 mod 13
Como na Aritmética usual, para cada inteiro, existe um aditivo inverso, ou negativo. Neste caso, o negativo de um número x é o número y tal que x + y ≡ 0 mod n .
Na Aritmética usual também existe um multiplicativo inverso, ou recíproco, para cada
número. Na Aritmética Modular, o multiplicativo inverso de x é o número y tal que
x × y ≡ 1 mod n . Deve-se notar que nem todos os números têm um multiplicativo inverso.
Este fato é analisado posteriormente.
37
3.2.2. PROPRIEDADES DA ARITMÉTICA MODULAR
O conjunto Z n como sendo o conjunto de inteiros não negativos menores que n,
Z n = {0, 1, L , (n − 1)} .
Z n é o conjunto de resíduos modulo n. As seguintes propriedades se aplicam aos inteiros
pertencentes a Z n :
Tabela 3 – Propriedades da Aritmética Modular
Propriedade
Leis comutativas
Leis associativas
Lei distributiva
Identidades
Inverso Aditivo (− w )
Expressão
(w + x ) mod n = ( x + w ) mod n
(w × x ) mod n = ( x × w ) mod n
[(w + x ) + y ] mod n = [w + ( x + y )] mod n
[(w × x ) × y ] mod n = [w × ( x × y )] mod n
[w × ( x × y )] mod n = [(w × x ) × (w × y )] mod n
(0 + w ) mod n = w mod n
(1 × w ) mod n = w mod n
Para cada w ∈ Z n , existe um z tal que w + z ≡ 0 mod n
Algumas propriedades da Aritmética usual são mantidas na Aritmética Modular. Tem-se
por exemplo se (a + b ) ≡ (a + c ) mod n então b ≡ c mod n .
A equivalência anterior ocorre devido a existência do inverso aditivo. Adicionando-se ao
inverso aditivo de a nos dois lados da equação, tem-se:
((− a ) + a + b ) ≡ ((− a ) + a + c ) mod n
⇒
b ≡ c mod n
Entretanto, o relacionamento seguir somente é válido se for considerado juntamente com
a condição em anexo:
se (a × b ) ≡ (a × c ) mod n então b ≡ c mod n se a for relativamente primo com n
Exemplo: considere um exemplo onde a condição acima não é válida:
6 × 3 = 18 ≡ 2 mod 8
38
6 × 7 = 18 ≡ 2 mod 8
Mas 3 ≠ 7 mod 8
A explicação para este estranho resultado é que para qualquer inteiro módulo n, um
multiplicador a, quando aplicado aos números de 0 até (n − 1) , não produzirá um conjunto
completo de resíduos se a e n possuírem quaisquer de seus fatores em comum.
Se p é um número primo, então todos os elementos de Z p são relativamente primos com
p. Isto permite adicionar uma propriedade à lista daquelas enunciadas anteriormente:
( )
Multiplicativa inversa w
−1
Se p é primo, então para cada w ∈ Z p , existe um z tal que
w × z ≡ 1 mod p
Assim, a equação a seguir é válida se p é primo e
(a × b ) ≡ (a × c ) mod
p então
b ≡ c mod p . Multiplicando os dois lados da equação anterior pelo multiplicativo inverso,
tem-se que:
((a )× a × b) ≡ ((a )× a × c ) mod n
−1
−1
b ≡ c mod n
3.3. TEOREMAS DE FERMAT E DE EULER
Dois teoremas desempenham papéis importantes na criptografia de chave pública. São os
Teoremas de Fermat e de Euler, que são analisados a seguir.
3.3.1. TEOREMA DE FERMAT
Se p é primo e a é um inteiro positivo não divisível por p, então
a p −1 ≡ 1 mod p
39
Demonstração:
{a mod
Como
p
é
primo,
p, 2a mod p, L , ( p − 1) a mod p},
então
os
correspondem
números
aos
números
do
conjunto
do
conjunto
{1, 2, L , ( p − 1)} em uma ordem, diferente. Multiplicando estes números, tem-se que
a × 2a × L × (( p − 1)a ) ≡ [(a mod p ) × (2a mod p ) × L × (( p − 1)a mod p )] mod p ≡ ( p − 1)! mod p
Como, a × 2a × L × (( p − 1)a ) = ( p − 1)! a p −1
Então, ( p − 1)! a p −1 ≡ ( p − 1)! mod p
O termo ( p − 1)! é relativamente primo com p, logo ele pode ser cancelado. Deste fato
resulta que a p −1 ≡ 1 mod p .
Uma forma alternativa do Teorema de Fermat é a seguinte: Se p é primo e a é qualquer
inteiro positivo, então
a p ≡ a mod p
3.3.2. FUNÇÃO TOTIENTE DE EULER
A função Totiente de Euler é denotada por φ(n ) , onde φ(n ) é o número de inteiros positivos menores do que n e relativamente primos com n.
Logo, se p é primo, então φ( p ) = p − 1 .
Dados dois números primos p e q, para n = pq , tem-se que
φ(n ) = φ( pq ) = φ( p ) × φ(q ) = ( p − 1) × (q − 1)
Para verificar este resultado, observe inicialmente que o conjunto de resíduos em Z n é
{0, 1, L , ( pq − 1)}. Os resíduos que não são relativamente primos com n formam os conjuntos
{p, 2p, L , (q − 1) p} , {q, 2q, L , ( p − 1)q} e 0. Conseqüentemente,
φ(n ) = pq − [(q − 1) + ( p − 1) + 1]
40
= pq − ( p + q ) + 1
= ( p − 1) × (q − 1)
= φ( p ) × φ(q )
3.3.3. TEOREMA DE EULER
Dados dois inteiros a e n, relativamente primos, tem-se que:
a φ(n ) ≡ 1 mod n
Demonstração: A equação a φ(n ) ≡ 1 mod n é verdadeira se n for primo. Neste caso,
φ(n ) = (n − 1) e o Teorema de Fermat asseguram a veracidade da equação. Convém relembrar
que φ(n ) é o número de inteiros positivos, menores que n que são relativamente primos com
n. Considere o conjunto de tais inteiros, descritos como se segue:
R = {x 1 , x 2 , L , x φ(n ) }
Multiplicando-se cada elemento por a, módulo n, obtém-se o conjunto:
S = {(ax 1 mod n ), (ax 2 mod n ), L , (ax φ(n ) mod n )}
Este conjunto é uma permutação de R. Tal fato é demonstrado a seguir.
1. Como a e n são relativamente primos, e x i e n, também são relativamente primos, então ax i e n são relativamente primos com n. Logo, todos os membros de S são inteiros menores que n e relativamente primos com n.
2. Se (a × b ) ≡ (a × c ) mod n então b ≡ c mod n se a é relativamente primo com n. Logo não existem duplicatas em S. Se ax i mod n = ax j mod n , então x i = x j .
Portanto, os elementos de S são diferentes entre si e correspondem a todos os elementos
de R. Logo,
41
φ(n )
∏ (ax i
i =1
φ(n )
mod n ) = ∏ x i
i =1
φ(n )
φ(n )
i =1
i =1
∏ ax i ≡ ∏ x i (mod n)
 φ(n )  φ(n )
Portanto, a φ(n ) × ∏ x i  ≡ ∏ x i (mod n ) e a φ(n ) ≡ 1(mod n )
 i =1  i =1
φ(n )
Pois
∏x
i
e n são primos entre si.
i =1
Uma forma alternativa, também útil, de enunciar o teorema é a seguinte:
a φ(n )+ 1 ≡ a (mod n )
Um corolário do Teorema de Euler que é útil na demonstração da validade do algoritmo
RSA, é o seguinte: Dados dois números primos, p e q, e inteiros n = pq e m, com 0 < m < n ,
tem-se que:
m φ(n )+ 1 = m ( p −1 )(q −1 )+ 1 ≡ m mod n
Se gcd (m, n ) = 1 , isto é, se m e n forem relativamente primos, então a equação anterior é verificada pelo Teorema de Euler. Suponha que gcd (m, n ) ≠ 1 . Como n = pq , a
igualdade gcd (m, n ) = 1 é equivalente à expressão lógica (m não é um múltiplo de p) E
(m não é um múltiplo de q). Se m é um múltiplo de p, então n e m compartilham o fator
primo p e não são relativamente primos, e se m for um múltiplo de q, então n e m compartilham o fator primo q e não são relativamente primos. Portanto, a expressão
gcd (m, n ) ≠ 1 é equivalente à expressão lógica (m é um múltiplo de p) OU (m é um
múltiplo de q).
No caso em que m é um múltiplo de p, a igualdade m = cp é válida para algum inteiro
positivo c. Neste caso, gcd (m, q ) = 1 , pois m e n são relativamente primos entre si. Logo,
pelo Teorema de Euler tem-se que m φ(q ) ≡ 1 mod q .
Além disso, pelas regras da Aritmética Modular,
42
[m ( ) ]
φq
φ( p )
≡ 1 mod q
m φ(n ) ≡ 1 mod q
Portanto, existe algum inteiro k tal que
m φ(n ) ≡ 1 + kq
Multiplicando-se cada lado por m = cp ,
m φ(n )+ 1 = m + kcpq = m + kcn
m φ(n )+ 1 ≡ m mod n
Um raciocínio similar é utilizado para o caso em que m é um múltiplo de q. Assim, a equação m φ(n )+ 1 = m ( p −1 )(q −1 )+ 1 ≡ m mod n está provada. Uma forma alternativa deste corolário, também útil, é a seguinte:
[m ( ) ]
φ n
k
≡ 1 mod n
m kφ(n ) ≡ 1 mod n
m kφ(n )+ 1 ≡ m k ( p −1 )(q −1 )+ 1 ≡ m mod n
3.4. TESTE DE PRIMALIDADE
Não existem formas simples que determinam se um número grande é primo. Esta subseção apresenta uma abordagem para tratar este problema. Primeiramente, é preciso derivar
alguns resultados. O primeiro deles é o que se segue:
Se p é um primo ímpar, então a equação, x 2 ≡ 1 (mod p ) possui apenas duas soluções, a
saber, x ≡ 1 e x ≡ −1 .
Demonstração: Tem-se que x 2 − 1 ≡ 0 (mod p ) . Logo ( x + 1)( x − 1) ≡ 0 (mod p ) .
Pelas regras da Aritmética Modular, a última igualdade requer que p divida ( x + 1) ou
que p divida ( x − 1) ou ambos. Supondo que p divida tanto ( x + 1) quanto ( x − 1) , então, po-
43
de-se dizer que ( x + 1) = kp e ( x − 1) = jp para inteiros k e j, k, j < p . Subtraindo-se as duas
equações, obtém-se 2 = (k − j ) p . Esta equação pode ser verdadeira somente se p = 2 , pois k,
j < p . Pelo enunciado do teorema, p é um número ímpar. Portanto, para uma dada solução x,
tem-se p ( x + 1) ou p ( x − 1) , mas não ambos. Suponha que p ( x − 1) , então,
x − 1 = kp para algum k
Portanto, x ≡ 1 mod p . Utilizando raciocínio similar, se p ( x − 1) chega-se à outra solução: x ≡ −1 mod p .
O teorema pode ser enunciado de outra forma: Se existem outras soluções para a equação
x 2 ≡ 1(mod n ) além de ± 1 , então n não é um número primo.
3.5. ALGORITMO DE EUCLIDES
O algoritmo de Euclides consiste em procedimento que determina o máximo divisor comum de dois números inteiros positivos. Uma forma ampliada do algoritmo de Euclides determina outro fato. Além do máximo divisor comum de dois números inteiros positivos, dados
dois números relativamente primos entre si, o algoritmo de Euclides ampliado calcula o multiplicativo inverso de um com relação ao outro.
3.5.1. ENCONTRANDO O MÁXIMO DIVISOR COMUM
O algoritmo de Euclides é baseado no resultado a seguir: Para qualquer inteiro não negativo a e qualquer inteiro positivo b,
gcd (a, b ) = gcd (b, a mod b )
Considere d = gcd (a, b ) . Pela definição de gcd , d a e d b . Para qualquer inteiro positivo b, a pode ser expresso na forma
44
a = kb + r ≡ r modb
a mod b = r
Dessa forma, (a mod b ) = a − kb para algum inteiro k. Mas, como d b , d também divide
kb . Tem-se também que d a . Assim, d (a mod b ) . Isto mostra que d é um divisor comum de
b e de a mod b . Reciprocamente, se d for um divisor comum de b e de a mod b , então d kb e
também d [kb + (a mod b )] , o que equivale a d a . Dessa forma, o conjunto dos divisores comuns de a e b é igual ao conjunto de divisores comuns de b e a mod b . Portanto, o gcd de
um é igual ao gcd do outro, o que prova o resultado acima.
A equação gcd (a, b ) = gcd (b, a mod b ) pode ser utilizada repetitivamente para determinar o máximo divisor comum de dois inteiros.
O algoritmo de Euclides faz repetidos usos da equação gcd (a, b ) = gcd (b, a mod b ) para
determinar o máximo divisor comum, o algoritmo assume que d > f > 0 . É aceitável restringir a aplicação do algoritmo a inteiros positivos porque gcd (a, b ) = gcd ( a , b ).
Euclides (d, f )
1 X ← f ; Y ←d
2. if Y = 0 return X = gcd (d, f
)
3. R = X mod Y
4. X ← Y
5. Y ← R
6. goto 2
3.5.2. ENCONTRANDO O MULTIPLICATIVO INVERSO
Se gcd (d, f ) = 1 , então d possui um multiplicativo inverso módulo f. Isto é, para inteiros
positivos d < f , existe um d −1 < f tal que dd −1 = 1 mod f . O algoritmo de Euclides é am-
45
pliado para retornar o multiplicativo inverso de d, se gcd (d, f ) é igual a 1.
Euclides ampliado (d, f )
( X1, X2, X3 ) ← (1, 0, f ) ; (Y1, Y2, Y3 ) ← (0, 1, d )
2. if Y3 = 0 return X3 = gcd (d, f ) ; não existe multiplicativo
−1
3. if Y3 = 1 return Y3 = gcd (d, f ) ; Y2 = d mod f
1
inverso
 X3 
4. Q = 
 Y3 
5. (T1, T2, T3 ) ← ( X1 − QY1, X2 − QY2, X3 − QY3 )
6. ( X1, X2, X3 ) ← (Y1, Y2, Y3 )
7. (Y1, Y2, Y3 ) ← (T1, T2, T3 )
8. goto 2
A correção deste algoritmo decorre dos seguintes fatos:
Observe inicialmente que as equação a seguir são válidas
fT1 + dT2 = T3
fX1 + dX2 = X3
fY1 + dY2 = Y3
O algoritmo retorna o gcd (d, f ) , pois se X e Y , do algoritmo de Euclides, são equiparados a X3 e Y3 do algoritmo de Euclides ampliado, respectivamente, então o tratamento das
duas variáveis é idêntico. A cada iteração do algoritmo de Euclides, o valor prévio de Y é
atribuído a X e o valor prévio de X mod Y é atribuído a Y . Analogamente, a cada passo do
algoritmo de Euclides ampliado, o valor prévio de Y3 é atribuído a X3 e Y3 recebe o valor
prévio de X3 menos o quociente de X3 dividido por Y3 . Este último valor é simplesmente é
o resto da divisão de X3 por Y3 , é igual a X3 mod Y3 . Se gcd (d, f ) = 1 , então no passo
final, tem-se Y3 = 0 e X3 = 1 . Portanto, no passo precedente, Y3 = 1 .
Como fY1 + dY2 = Y3
Logo, se Y3 = 1 , então fY1 + dY2 = 1 e dY2 = 1 + (− Y1) × f
Isto é, dY2 = 1 mod f
Portanto, Y2 é o inverso multiplicativo de d, módulo f.
46
A tabela a seguir mostra um exemplo da execução deste algoritmo, que mostra que
gcd (550, 1769 ) = 1 e que o inverso multiplicativo de 550 é ele mesmo, ou seja,
550 × 550 ≡ 1 mod 1769 .
Tabela 4 – Euclides ampliado (550, 1769)
Q
X1
X2
X3
Y1
Y2
Y3
–
1
0
1769
0
1
550
3
0
1
550
1
-3
119
4
1
-3
119
-4
13
74
1
-4
13
74
5
-16
45
1
5
-16
45
-9
29
29
1
-9
29
29
14
-45
16
1
14
-45
16
-23
74
13
1
-23
74
13
37
-119
3
4
37
-119
3
-171
550
1
3.6. TEOREMA CHINÊS DO RESTO
O Teorema Chinês do Resto – CRT1, afirma que é possível reconstruir inteiros pertencentes a um intervalo a partir de seus resíduos módulo um conjunto de n-uplas, cujos elementos
forem relativamente primos com o módulo.
O CRT é considerado a seguir. Seja
k
M = ∏ mi
i =1
onde m 1 , L , m k é uma k-tupla relativamente prima; isto é gcd (m i , m j ) = 1 para 1 ≤ i ,
j ≤ k e i ≠ j . Qualquer inteiro A pertencente a Z M pode ser representado por uma k-tupla
(a 1 , a 2 , L , a k ) , tal que a i ∈ Z m
1
i
e a i = A mod m i para 1 ≤ i ≤ k .
O Teorema Chinês do Resto é assim conhecido porque acredita-se que ele tenha sido descoberto pelo
matemático chinês Sun-Tse, por volta do ano 100 a.C.
47
O CRT faz duas asserções:
1. o mapeamento A ↔ (a 1 , a 2 , L , a k ) estabelece uma correspondência um-para-um.
Tem-se uma bijeção, entre Z M e o produto cartesiano Z m1 × Z m 2 × L × Z mk . Ou seja,
para todo inteiro A tal que 0 ≤ A ≤ M , existe uma única k-tupla (a 1 , a 2 , L , a k ) com
0 ≤ a i ≤ m i que o represente e para toda k-tupla (a 1 , a 2 , L , a k ) existe um único A
pertencente a Z M .
2. Operações realizadas sobre os elementos de Z M pode ser realizadas de forma equivalente nas k-tuplas mediante a realização das operações independentemente sobre cada
coordenada posicionada no sistema apropriado.
O enunciado acima pode ser representado como se segue:
Se
A ↔ (a 1 , a 2 , L , a k ) ; B ↔ (b1 , b2 , L , bk )
então
( A + B ) mod
M ↔ ((a 1 + b1 ) mod m 1 , L , (a k + bk ) mod m k )
( A − B ) mod
M ↔ ((a 1 − b1 ) mod m 1 , L , (a k − bk ) mod m k )
( A × B ) mod
M ↔ ((a 1 × b1 ) mod m 1 , L , (a k × bk ) mod m k )
A seguir é demonstrada a primeira asserção. A transformação de A para (a 1 , a 2 , L , a k )
é obviamente única; basta considerar a i = A mod m i . Calcular A para (a 1 , a 2 , L , a k ) pode
ser feito da forma que se segue. Seja
M i = M m i , para 1 ≤ i ≤ k . Note que
M i = m 1 × m 2 × L × m i −1 × m i + 1 × L × m k , então M i ≡ 0 (mod m j ) para todo j ≠ i . Seja
também
(
)
c i = M i × M i−1 mod m i , para 1 ≤ i ≤ k
Por definição, M i e m i são relativamente primos. Portanto, M i possui um único inver-
48
(
)
so multiplicativo mod m i . Assim, c i = M i × M i−1 mod m i , para 1 ≤ i ≤ k é bem definido
e produz um único valor c i . Dessa forma, pode-se calcular
 k

A ≡  ∑ a i c i  mod M
 i =1

 k

Para mostrar que o valor de A produzido por A ≡  ∑ a i c i  mod M é correto, é preciso
 i =1

mostrar que a i = A mod m i , para 1 ≤ i ≤ k . Note que c j ≡ M j ≡ 0 (mod m i ) se j ≠ i e que
c i ≡ 1 (mod m i ) . Disso resulta que a i = A mod m i .
A segunda asserção do CRT, referente às operações aritméticas, deriva das regras da Aritmética Modular.
Uma das funcionalidades mais úteis do CRT é que ele provê uma maneira para manipular
números mod M , potencialmente muito grandes, em termos de tuplas de números menores.
Isto pode ser útil quando M possui 150 dígitos ou mais.
Exemplo: Para representar 973 mod 1813 como um par de números mod 37 e 49, define-se:
m 1 = 37
m 2 = 49
M = 1813
A = 973
Tem-se que M 1 = 49 e M 2 = 37 . Utilizando o Teorema de Euclides ampliado, calculase M 1−1 = 34 mod m 1 e M 2−1 = 4 mod m 2 . É importante ressaltar que é necessário calcular
cada M i e cada M i−1 apenas uma vez. Pegando-se os resíduos módulo 37 e 49, a representação de 973 é (11, 42 ) , uma vez que 973 mod 37 = 11 e 973 mod 49 = 42 .
Supondo que se queira adicionar 678 a 973, primeiramente deve-se calcular
49
(678 ) ↔ (678 mod
37, 678 mod 49 ) = (12, 41) . Em seguida, adiciona-se e se reduz os ele-
mentos da tupla (11 + 12 mod 37, 42 + 41 mod 49 ) = (23, 34 ) . Para verificar que este resultado está correto, calcula-se:
(23, 34 ) ↔ a 1 M 1 M 1−1 + a 2 M 2 M 2−1 mod
M
= [(23 )(49 )(34 ) + (34 )(37 )(4 )] mod 1813
= 43350 mod 1813
= 1651
e verifica a igualdade (973 + 678 ) mod 1813 = 1651 .
Supondo que se queira multiplicar 1651(mod1813 ) por 73: multiplica-se (23, 24 ) por 73
e reduz para obter (23 × 73 mod 37, 34 × 73 mod 49 ) = (14, 32 ) . Pode ser verificado que
(14,32 ) ↔ ((14 )(49 )(34 ) + (32 )(37 )(4 )) mod1813
= 865
= 1651 × 73 mod 1813
3.7. LOGARITMOS DISCRETOS
Logaritmos discretos são fundamentais para vários algoritmos de chave pública, inclusive
para a troca de chaves de Diffie-Hellman e para o algoritmo de assinatura digital – DSA. Esta
seção apresenta uma visão geral da teoria de logaritmos discretos.
3.7.1. POTÊNCIA DE UM INTEIRO, MÓDULO n
Conforme o Teorema de Euler, para inteiros a e n, relativamente primos,
a φ(n ) ≡ 1 mod n , onde φ(n ) – função Totiente de Euler –, é o número de inteiros positivos
menores que n que são relativamente primos com n. Considerando a expressão mais geral
50
a m ≡ 1 mod n , se a e n são relativamente primos, então existe pelo menos um inteiro m que
satisfaça a equação a m ≡ 1 mod n , ou seja, m = φ(n ) . O menor expoente positivo m para o
qual a m ≡ 1 mod n se verifica é referenciado de diversas maneiras:
― A ordem de a (mod n ) ;
― o expoente para o qual a pertence a (mod n ) ;
― o comprimento do período gerado por a .
Exemplo: Considere as potências de 7, módulo 19:
71 =
7 mod 19
7 2 = 49 = 2 × 19 + 11 =
11 mod 19
7 3 = 343 = 18 × 19 + 1 =
1 mod 19
7 4 = 2401 = 126 × 19 + 7 =
7 mod 19
7 5 = 16807 = 884 × 19 + 11 =
11 mod 19
A partir daí, não existe razão para continuar, porque a seqüência se repete. Isto pode ser
provado notando que 7 3 = 1 (mod 19 ) e portanto, 7 3 + j = 7 37 j = 7 j (mod 19 ) . Logo quaisquer duas potências de 7 cujos expoentes diferem em 3 (ou por um múltiplo de 3) são congruentes reciprocamente (mod 19 ) . Em outras palavras, a seqüência é periódica e o comprimento
do período é o menor expoente positivo m tal que 7 m = 1 (mod 19 ) .
A próxima tabela mostra todas as potências de a, modulo 19 para todos os positivos
a < 19 . O comprimento da seqüência para cada valor da base encontra-se sombreado. Com
relação aos dados constantes da tabela, é importante notar o seguinte:
1. Todas as seqüências terminam em 1, o que é consistente com o raciocínio dos parágrafos imediatamente anteriores.
2. Os comprimentos das seqüências dividem φ(19 ) = 18 . Ou seja, um número inteiro de
seqüências ocorre em cada linha da tabela.
51
3. Algumas das seqüências possuem comprimento 18. Neste caso, diz-se que a base inteira a gera, via potências, o conjunto dos inteiros módulo 19 diferentes de zero. Cada
um destes inteiros é denominado raiz primitiva do módulo 19.
Tabela 5 – Potência dos Inteiros, Módulo 19
a
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
4
8
16
13
7
14
9
18
17
15
11
3
6
12
5
10
1
3
9
8
5
15
7
2
6
18
16
10
11
14
4
12
17
13
1
4
16
7
9
17
11
6
5
1
4
16
7
9
17
11
6
5
1
5
6
11
17
9
7
16
4
1
5
6
11
17
9
7
16
4
1
6
17
7
4
5
11
9
16
1
6
17
7
4
5
11
9
16
1
7
11
1
7
11
1
7
11
1
7
11
1
7
11
1
7
11
1
8
7
18
11
12
1
8
7
18
11
12
1
8
7
18
11
12
1
9
5
7
6
16
11
4
17
1
9
5
7
6
16
11
4
17
1
10
5
12
6
3
11
15
17
18
9
14
7
13
16
8
4
2
1
11
7
1
11
7
1
11
7
1
11
7
1
11
7
1
11
7
1
12
11
18
7
8
1
12
11
18
7
8
1
12
11
18
7
8
1
13
17
12
4
14
11
10
16
18
6
2
7
15
5
8
9
3
1
14
6
8
17
10
7
3
4
18
5
13
11
2
9
12
16
15
1
15
16
12
9
2
11
13
5
18
4
3
7
10
17
8
6
14
1
16
9
11
5
4
7
17
6
1
16
9
11
5
4
7
17
6
1
17
4
11
16
6
7
5
9
1
17
4
11
16
6
7
5
9
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
Considerando o grupo multiplicativo Zn, o maior expoente ao qual um número pode ser
elevado, obtendo-se resultados distintos é φ(n ) . Se a ordem de um número é φ(n ) , ele é denominado raiz primitiva de n. A importância desta noção é que se a for uma raiz primitiva de
n, então suas potências a, a 2 , L , a φ(n ) são distintas (mod n ) e todas são relativamente primas com n. Particularmente, para um número primo p, se a é uma raiz primitiva de p, então
a, a 2 , L , a p −1 serão distintas (mod n ) . Para o número primo 19, suas raízes primitivas são 2,
3, 10, 13, 14 e 15.
Nem todos os inteiros possuem raízes primitivas. Os únicos inteiros que possuem raízes
52
primitivas são aqueles que podem ser escritos na forma 2, 4, p α e 2p α onde p é qualquer número ímpar (STALLINGS, 1999).
3.7.2. ÍNDICES
Com números reais positivos, a função logaritmo é o inverso da exponenciação. Uma
função análoga existe na Aritmética Modular.
Antes de abordar esta função, é necessário fazer uma breve revisão das propriedades dos
logaritmos comuns. O logaritmo de um número é definido como sendo: para uma base x e
um número y , y = x log x ( y ) .
Dentre as propriedades dos logaritmos, as principais são
log x (1) = 0
log x ( x ) = 1
log x ( yz ) = log x ( y ) + log x (z )
( )
log x y r = r × log x ( y )
Considere uma raiz primitiva a de algum número primo p (o argumento pode ser desenvolvido para números não primos da mesma forma). Sabe-se que as potências de a, de 1 até
( p − 1)
resultam em cada inteiro de 1 até ( p − 1) uma única vez. Sabe-se, também, pela defi-
nição de Aritmética Modular, que qualquer inteiro b pode ser expresso na forma
b ≡ r mod p , onde 0 ≤ r ≤ ( p − 1) .
Disto resulta que, para qualquer inteiro b e uma raiz primitiva a do número primo b, pode-se encontrar um único expoente i tal que b ≡ a i mod p , onde 0 ≤ r ≤ ( p − 1) .
O expoente i é denominado como o indexador do número b para a base a (mod p ) . Este
valor é denotado por ind a, p (b ) .
53
Notando que:
ind a, p (1) = 0 , pois a 0 mod p = 1
ind a, p (a ) = 1 , pois a 1 mod p = a
Considerando que x = a
ind a, p ( x )
mod p e y = a
ind a, p ( y )
mod p , e XY = a
ind a, p ( XY )
mod p .
Utilizando as regras da multiplicação modular,
a
ind a, p ( xy )
(
= (a
mod p = a
ind a, p ( x )
)(
mod p a
ind a, p ( x )+ ind a, p ( y )
ind a, p ( y )
mod p
)
) mod p
Considerando o Teorema de Euler, se a e n são relativamente primos, então
a φ(n ) ≡ 1 mod n .
Qualquer inteiro positivo z pode ser expresso na forma z = q + kφ(n ) . Então, pelo Teorema de Euler, a z = a q mod n , se z ≡ q mod φ(n ) .
Aplicando isto à igualdade antecedente, tem-se que
[
]
ind a, p ( x, y ) ≡ ind a, p ( x ) + ind a, p ( y ) mod φ( p )
[
]
A relação acima também pode ser expressa por ind a, p ( y r ) = r × ind a, p ( y ) mod φ( p ) .
Isto demonstra a analogia entre logaritmos reais e indexadores. Por esta razão, os indexadores são considerados logaritmos discretos.
Não se pode esquecer que os logaritmos discretos mod m , para alguma base a, somente
existem se a for uma raiz primitiva de m.
A tabela a seguir mostra os conjuntos de logaritmos discretos Módulo 19.
Tabela 6 – Tabelas de Logaritmos Discretos, módulo 19
a
Ind 2, 19 (a )
a
Ind 3, 19 (a )
1
2
3
18
1
13
1
2
3
18
7
1
(a) Logaritmos Discretos para base 2, módulo 19
4
5
6
7
8
9
10 11 12 13
2
16
14
6
3
8
17
12
15
5
14
15
16
17
18
7
11
4
10
9
15
16
17
18
5
10
16
9
(b) Logaritmos Discretos para base 3, módulo 19
4
5
6
7
8
9
10 11 12 13 14
14
4
8
6
3
2
11
12
15
17
13
54
a
Ind 10, 19 (a )
a
Ind 13, 19 (a )
A
Ind 14, 19 (a )
A
Ind 15, 19 (a )
1
2
3
18
17
5
1
2
3
18
11
17
1
2
3
18
13
7
1
2
3
18
5
11
(c) Logaritmos Discretos para base 10, módulo 19
4
5
6
7
8
9
10 11 12 13 14
16
2
4
12
15
10
1
6
3
13
11
(d) Logaritmos Discretos para base 13, módulo 19
4
5
6
7
8
9
10 11 12 13 14
4
14
10
12
15
16
7
6
3
1
5
(e) Logaritmos Discretos para base 14, módulo 19
4
5
6
7
8
9
10 11 12 13 14
8
10
2
6
3
14
5
12
15
11
1
(f) Logaritmos Discretos para base 15, módulo 19
4
5
6
7
8
9
10 11 12 13 14
10
8
16
14
15
4
13
6
3
7
17
15
16
17
18
7
14
8
9
15
16
17
18
13
8
2
9
15
16
17
18
17
16
14
9
15
16
17
18
1
2
12
9
3.7.3. CÁLCULO DOS LOGARITMOS DISCRETOS
Considerando-se a equação y ≡ g x mod p , se são dados g, x e p, então o cálculo de y é
imediato. No pior caso, é preciso realizar x multiplicações, o que pode ser efeito mediante a
utilização de algoritmos, com grande eficiência.
No entanto, dados y, g e p, em geral é difícil calcular x (empregando-se logaritmos
discretos). A dificuldade parece ser da mesma ordem de magnitude de se decompor em
fatores primos os números requeridos pelo RSA. O algoritmo mais rápido conhecido que pode
ser empregado para obter os logaritmos discretos, módulo um número primo, é da ordem de
e
1
2

 ( ln p ) 3 ln ( ln p ) 3




o que não é viável para números primos grandes. (STALLINGS, 1999)
55
CAPÍTULO 4
CRIPTOGRAFIA
4.1. INTRODUÇÃO
A criptografia já estava presente no sistema de escrita hieroglífica dos egípcios. Desde
então vem sendo muito utilizada, principalmente para fins militares e diplomáticos. No âmbito da computação, a criptologia é importante para que se possa garantir a segurança em todo
o ambiente computacional que necessite de sigilo em relação à informação manipulada. Pode
ser usada para cifrar dados e mensagens antes que esses sejam enviados por vias de comunicação. Após o envio da mensagem, mesmo que a ela seja interceptada, dificilmente pode ser
decifrada.
Este Capítulo analisa os fundamentos da criptografia, sua nomenclatura e principais características; são considerados também os principais tipos de ataques aos criptosistemas e suas
classificações.
4.1.1. PRINCIPAIS NOTACÕES
As principais notações de criptografia consideradas a seguir seguem a referência (STALLINGS, 1999) e serão utilizadas neste trabalho. Deve ser enfatizado que esta terminologia é
variável e não há uma notação universalmente aceita.
56
― Cifrar é o ato de transformar dados em alguma forma ilegível. Seu propósito é o de
garantir a privacidade, mantendo a informação oculta a qualquer pessoa não autorizada, mesmo que esta consiga visualizar os dados cifrados;
― Decifrar é ato de transformar os dados cifrados na sua forma original, inteligível;
― Chave ou Senha é uma informação secreta utilizada para cifrar ou decifrar uma mensagem, dependendo do método de criptografia empregado. A mesma chave pode ser
utilizada tanto para cifrar como para decifrar mensagens. Entretanto, há mecanismos
que utilizam chaves ou senhas diferentes para cifrar e decifrar;
― Criptografia ( Kriptós = escondido, oculto; grápho = grafia) é a arte ou ciência de escrever em cifra ou em código, de forma a permitir que apenas o destinatário a decifre e
compreenda. Quase sempre o deciframento requer uma chave, uma informação secreta disponível ao destinatário;
― Criptoanálise (kriptós; análysis = decomposição) é a arte ou ciência de determinar a
chave ou decifrar mensagens sem conhecer a chave. Uma tentativa de criptoanálise é
chamada ataque;
― Criptologia (kriptós; logo = estudo, ciência) é a ciência que reúne a criptografia e a
criptanálise.
A criptografia computacional é usada para garantir (Imaster, 2003):
― Confidencialidade: somente os usuários autorizados têm acesso à informação;
― Integridade: garantia oferecida ao usuário de que a informação correta, original, não
foi alterada, nem intencionalmente, nem acidentalmente;
― Não-repudiação: previne que alguém negue o envio e/ou recebimento de uma mensagem.
A figura 4 a seguir descreve a relação entre o remetente, o destinatário e o intruso. Uma
mensagem é enviada através de um canal inseguro, onde ela pode ser interceptada por um espião ou intruso. Não é possível garantir a segurança do canal, logo a interceptação é possível.
57
O principal objetivo dos intrusos é violar o segredo de comunicação e se beneficiar da informação secreta que está sendo transmitida. Objetivos mais sofisticados também podem ser alcançados pelo intruso. Ele pode, por exemplo, alterar a mensagem e confundir o receptor. Um
exemplo desta situação é a alteração da identidade do remetente.
Remetente
Destinatário
Intruso
Figura 4 – Conjunto básico
A mensagem em sua forma original é chamada de texto original que é cifrada pelo remetente. O resultado é referido como texto cifrado. O texto cifrado é então enviado via canal
inseguro. Finalmente, o receptor decifra o texto cifrado, obtendo assim o texto original.
A função do remetente é: cifrar o texto original obtendo o texto cifrado. Por outro lado,
a função do destinatário é o inverso. Ele deve decifrar o texto cifrado e obter o texto original.
As expressões a seguir também são utilizadas. Ek(to) = tc e Dk(tc) = to, onde k é a chave
utilizada para cifrar e decifrar, a Figura 5 ilustra essas notações:
E k(to)=tc
Dk(tc)= to
R emete nte
Esc olhe texto origin al, to
Destinatário
I ntruso ou Cr iptoa nalista
Figura 5– Conjunto Básico com mais detalhes
58
As operações de cifragem e decifragem acontecem em uma estrutura denominada criptosistema. Um criptosistema é uma tupla (P,C,K,E,D) com as seguintes propriedades(BUCHMANN, 2002):
1. P é o conjunto de textos originais. O conjunto P é o espaço dos textos originais
(plaintext);
2. C é o conjunto dos textos cifrados. O conjunto C é o espaço dos textos cifrados (ci-
phertext);
3. K é o conjunto das chaves. O conjunto K é o espaço das chaves;
4. E={Ek:k∈K} é uma família de funções Ek:P-->C. Seus elementos são chamados de
funções de cifragem;
5. D={Dk:k∈K} é uma família de funções Dk:C-->P. Seus elementos são chamados de
funções de decifragem.
4.1.2. CRIPTOANÁLISE
A criptoanálise trata dos ataques aos criptosistemas. Nesta seção, estes ataques são
classificados.
Para tornar mais difíceis os ataques aos criptositemas, pode-se mantê-los secretos. Entretanto, não está claro quanto se ganha realmente em segurança dessa forma, porque um atacante tem muitas formas de descobrir qual criptosistema está sendo usado. Ele pode induzir que
sistema está sendo usado, a partir de textos cifrados interceptados. Ele também pode tentar
obter informações de pessoas que tenham acesso ao sistema de cifragem em uso.
Portanto, a criptoanálise moderna parte do pressuposto de que o intruso conhece qual
criptosistema está sendo usado. É pressuposto que apenas a chave e o texto original são secretos. O Intruso ou o criptoanalista tenta recuperar os textos originais a partir dos textos ci-
59
frados, ou mesmo tenta descobrir quais chaves estão sendo usadas. A descoberta da chave
que está sendo utilizada pode ser feita pelos seguintes tipos de ataque (BUCHMANN, 2002):
― Ataque somente ao texto cifrado. O Intruso conhece os textos cifrados e tenta recuperar os textos originais correspondentes ou a chave;
― Ataque a texto original conhecido. O intruso conhece um texto original e o texto cifrado correspondente ou diversos de tais pares. Ele tenta descobrir a chave usada ou
decifrar outros textos cifrados ;
― Ataque a texto original selecionado. O intruso é capaz de cifrar textos originais,
mas não conhece a chave. Ele tenta descobrir a chave usada ou decifrar outros textos
cifrados;
― Ataque a texto original adaptável selecionado. O intruso é capaz de cifrar textos originais. Ele é capaz de escolher novos textos originais como uma função de textos
cifrados obtidos, mas não conhece a chave. Ele tenta descobrir a chave ou decifrar outros textos cifrados;
― Ataque a texto cifrado selecionado. O intruso pode decifrar, mas não conhece a chave. Ele tenta descobrir a chave.
Existem muitas maneiras de montar esses ataques. Um ataque simples somente ao texto
cifrado consiste na decifragem desse usando todas as chaves possíveis. Esse ataque é chamado de busca exaustiva.
4.1.3. TIPOS DE SISTEMAS CRIPTOGRÁFICOS
Os criptosistemas podem ser tanto simétricos quanto assimétricos. Num criptosistema
simétrico a cifragem e a decifragem são feitas com uma única chave, ou seja, tanto o remetente quanto o destinatário usam a mesma chave, conforme a figura a seguir:
60
Cha ve
PIZZA
Cifrar
Texto Original
ZAIZP
D ecifr ar
Texto Cifrado
PIZZA
Texto Original
Figura 6– Criptografia simétrica
Em um criptosistema assimétrico, ao contrário, duas chaves são empregadas. Uma chave
pública para cifrar e uma chave secreta para decifrar. A figura 7 ilustra tais fatos.
Cha ve Privada
Chave Pública
PIZZA
Texto Original
Cifrar
ZAIZP
Decifr ar
Texto Cifrado
P IZZA
Texto Original
Figura 7– Criptografia assimétrica
Esta seção abordou os conceitos, a nomenclatura e as principais características da criptografia em geral.
Os criptosistemas são classificados em dois tipos: Criptosistema Simétrico, também chamado de criptografia convencional, que utiliza somente uma chave para cifrar e decifrar; e o
Criptosistema Assimétrico, também chamado de criptografia de chave pública, que utiliza
duas chaves, uma para cifrar e outra para decifrar.
Esses dois criptosistemas serão discutidos nas próximas seções.
61
4.2. CRIPTOGRAFIA CONVENCIONAL
4.2.1. INTRODUÇÃO
A criptografia convencional é também denominada codificação convencional ou simétrica. Neste método, uma chave é usada para ambos os processos: cifragem e decifragem.
A criptografia convencional tem algumas vantagens em relação aos outros tipos de criptografia. Ela é rápida e também é útil para cifrar dados que serão armazenados. Entretanto, a
criptografia convencional, utilizada como ferramenta para a transmissão segura de dados, pode ser inadequada. Isto ocorre devido à dificuldade de distribuição segura da chave. Neste método, a segurança do dado cifrado é inteiramente dependente de dois fatores: a força do algoritmo criptográfico, e o segredo da chave.
Para o remetente e o destinatário se comunicarem seguramente usando a criptografia
convencional, eles devem concordar sobre a utilização de uma determinada chave e mantê-la
secreta. Caso estejam em locais físicos diferentes, eles devem obter um meio de comunicação
seguro para transmissão da chave. Qualquer pessoa que escute ou intercepte a chave em trânsito pode perfeitamente ler, modificar e forjar toda informação cifrada ou autenticada com tal
chave.
Na criptografia convencional é utilizada uma única chave para cifrar e decifrar uma mensagem, conforme mostra a figura 8.
Algoritmo Simétrico
Decodificação
Codificaç ão
Texto Original
Texto Cifrado
Figura 8– Criptografia Convencional
Texto Original
62
4.2.2. VANTAGEM DA CRIPTOGRAFIA CONVENCIONAL
Uma das vantagens da criptografia convencional é que ela é rápida, embora apresente alguns problemas:
•
Cada par necessita de uma chave secreta para se comunicar de forma segura. Portanto,
estas chaves devem ser trocadas entre as partes e armazenadas de forma segura, o que
nem sempre é possível de se garantir;
•
A criptografia convencional não garante a identidade de quem enviou ou recebeu a
mensagem;
•
A quantidade de usuários em uma rede pode dificultar o gerenciamento das chaves. Isto pode gerar um alto custo para a distribuição segura da chave.
Como exemplo de algoritmo criptográfico convencional, pode-se citar o Data Encryp-
tion Standard (DES) criado pelo National Bureau of Stantards e adotado como padrão os
EUA em 1977 (STALLINGS, 1999), (BUCHMANN, 2002).
Desde a sua invenção, a segurança do DES tem sido estudada com muita intensidade. Foram inventadas técnicas especiais como a criptoanálise diferencial e linear para atacar o DES
(BUCHMANN, 2002). Mas o ataque mais bem sucedido tem sido uma pesquisa exaustiva do
espaço da chave. Com hardware especial ou grande rede de micros, é possível decifrar textos
cifrados com o DES em poucos dias ou mesmo horas (STALLINGS, 1999).
4.3. CRIPTOGRAFIA DE CHAVE PÚBLICA
4.3.1. INTRODUÇÃO
Criptografia de chave pública é um esquema assimétrico (é também chamada de criptografia assimétrica) que utiliza um par de chaves: uma pública, que cifra o dado, e uma privada
ou secreta, para a decifragem. O usuário disponibiliza a sua chave pública para todas as pes-
63
soas, enquanto mantém em segredo a sua chave de decifragem (a privada). Qualquer indivíduo com uma cópia da chave pública de um usuário A, pode codificar uma informação que
somente o usuário A poderá ler. Isto ocorre porque somente o usuário A possui a chave privada (de decifragem).
Computacionalmente, é intratável deduzir a chave privada a partir da chave pública.
Qualquer pessoa que tenha uma chave pública pode cifrar uma determinada informação, porém não poderá decifrá-la. Apenas a pessoa com a chave privada correspondente pode decifrar a informação.
Portanto, na criptografia de chave pública é utilizado um par de chaves: uma pública
(KU), que cifra o texto original, e uma privada (KR), utilizada para decifrar o texto cifrado ,
conforme mostra a figura 9.
A lgoritmo Assimétrico
Texto Original
KU
Chave Pública
KR
Chav e Priv ada
Codificaç ão
Decodificação
Texto Cifrado
Texto Original
Figura 9– Criptografia de Chave Pública
Como Exemplo de algoritmo criptográfico de chave pública, pode –se citar o criptosistema RSA batizado em homenagem a seus inventores Ron Rivest, Adi Shamir e Len Adleman.
O RSA foi o primeiro criptosistema de chave pública e ainda é o mais importante. Sua segurança está relacionada à dificuldade de encontrar a fatoração de um número inteiro positivo,
que é o produto de dois números primos grandes (BUCHMANN, 2002).
O algoritmo RSA foi publicado pela primeira vez em 1978 (STALLINGS, 1999). Tratase de um dos algoritmos mais importantes da criptografia e o seu uso é muito variado. Serve
64
de base para esquemas de assinaturas digitais, em mecanismos de segurança de E-mail, como
o PEM e o PGP. O RSA é também utilizado em sistemas de autenticações.
O RSA foi patenteado em 1983 e até hoje não revelou qualquer falha importante. É possível que um dia alguém descubra uma forma de quebrar o RSA sem usar a força bruta. Tal
achado revolucionaria a atual Teoria dos Números e garantiria fama e fortuna para o descobridor.
A segurança oferecida por este algoritmo baseia-se no seguinte fato: encontrar dois primos grandes e efetuar seu produto é relativamente fácil. Por outro lado, fatorar um grande
número é difícil. Se os números utilizados forem suficientemente grandes, os recursos necessários para resolver o problema da fatoração podem ser considerados de solução difícil.
Entretanto, dado que o poder de cálculo dos computadores e o conhecimento científico
sobre números primos têm avançado continuamente, a dimensão dos primos a serem utilizados com segurança no RSA deve ser cada vez maior (STALLINGS, 1999).
A seguir, apresenta-se o criptosistema Elgamal em um grupo multiplicativo G. Este criptosistema é outro exemplo de um algoritmo de chave pública.
4.3.2. O CRIPTOSISTEMA ELGAMAL EM UM GRUPO MULTIPLICATIVO G.
Seja G um grupo finito com a operação multiplicação, e g um elemento de G, o qual é gerador do subgrupo H, tal que o Problema do Logaritmo Discreto é considerado como sendo
intratável em H.
No Criptosistema de ElGamal, os textos originais são elementos de G e os textos cifrados são pares em GxG. Seja h ∈ H, tal que:
ga = h
onde os elementos h e g são públicos e a é secreto. Para um número aleatório secreto
k∈Z
H
, define-se a codificação de um elemento m, como:
65
E a (m, k ) = ( y 1 , y 2 ) ,
onde:
y1 = hk
y2 = m g k
Dado o texto cifrado y = ( y 1 , y 2 ) , define-se:
( )
Da ( y ) = y 2 y 1b
−1
onde b = a −1 . tem-se que:
y 1b = h kb = g akb = g k .
onde:
( )
Da ( y ) = y 2 y 1b
−1
( )
Da ( y ) = m g k g k
−1
Da ( y ) = m .
No Criptosistema de ElGamal a chave privada é a e a chave pública são os valores g, h
e o grupo G multiplicativo. O texto original m é cifrado usando unicamente elementos públicos. O par ( y 1 , y 2 ) é decifrado usando a chave secreta a.
4.3.3. CRIPTOGRAFIA SIMÉTRICA X CRIPTOGRAFIA ASSIMÉTRICA
Uma das principais vantagens dos sistemas criptográficos de chave pública é a distribuição de chaves. Na criptografia por chave secreta, há a necessidade do compartilhamento de
uma chave secreta e, portanto, de um pré-acordo entre as partes interessadas. Tal fato não ocorre nos sistemas criptográficos de chave pública. Neste sentido, a vulnerabilidade do sistema de chave pública é menor. Por outro lado, a principal vantagem da criptografia por chave
66
secreta é a velocidade dos processos de cifragem/decifragem. Em geral, os sistemas criptográficos de chave secreta são mais rápidos que os de chave pública.
Devido a tais fatos, geralmente os sistemas de chave pública são utilizados para a distribuição de chaves secretas. Em seguida, estas chaves secretas são utilizadas por sistemas simétricos na cifragem dos dados a serem transmitidos.
4.4. ASSINATURA DIGITAL
Uma assinatura digital é o resultado da cifragem de um determinado bloco de dados (documento) pela utilização da chave privada de quem assina. Por outro lado, a verificação da
assinatura é feita com a chave pública correspondente. Se o resultado da decifragem corresponde ao texto original , a assinatura é considerada “válida”, ou seja, autêntica. Isto ocorre
porque apenas o detentor da chave privada, que corresponde à chave pública utilizada, poderia
ter gerado aquela mensagem cifrada. A figura 10 ilustra este procedimento. O usuário B cifra
e envia o texto original M para o usuário A. O usuário A recebe o texto cifrado C e o decifra
com a chave pública de B, provendo assim a autenticação e a integridade de que o texto cifrado foi enviado pelo usuário B.
Portanto, algoritmos criptográficos de chave pública podem ser utilizados para gerar as-
sinaturas digitais. Obviamente, esta forma de uso não assegura a confidencialidade da mensagem, uma vez que qualquer um pode decifrar a mensagem, dado que a chave-pública é de
conhecimento público. Entretanto, se esta operação resulta na “mensagem esperada” tem-se a
certeza de que somente o detentor da correspondente chave privada realizou a operação de
cifragem.
67
KRB = Chave privada de B
M
Cifragem C
KU B = Chave pública B
C
Decifragem D
M
Usuá rio B
Usuá rio A
Figura 10– Geração de Assinatura Digital de um documento
4.5. FUNÇÕES CRIPTOGRÁFICAS HASH
Funções criptográficas hash são também conhecidas como Message Digest, One-Way
Hash Function, Função de Condensação ou Função de Espalhamento Unidirecional. A função
Hash funciona como uma impressão digital de uma mensagem, gerando, a partir de uma entrada de tamanho variável, um valor fixo: o digest ou valor hash. Após o valor hash de uma
mensagem ter sido calculado, qualquer modificação em seu conteúdo será detectada, pois o
valor hash da nova mensagem será diferente do valor hash da mensagem original.
Alguns exemplos de funções hash são:
― MD5: É uma função de espalhamento unidirecional inventada por Ron Rivest, do
MIT. A sigla MD significa Message Digest. Este algoritmo produz um valor hash de
128 bits, para uma mensagem de entrada de tamanho arbitrário.
― SHA-1: O Secure Hash Algorithm é uma função de espalhamento unidirecional inventada pela NSA. Ela gera um valor hash de 160 bits, a partir de um tamanho arbitrário
de mensagem. Atualmente não existe nenhum ataque de criptoanálise conhecido contra o SHA-1. Mesmo um ataque de força bruta é difícil, devido ao seu valor hash ser
de 160 bits.
― MD2 e MD4: O MD4 é o precursor do MD5, tendo sido inventado por Ron Rivest.
Após terem sido descobertas algumas fraquezas no MD4, Rivest escreveu o MD5. O
68
MD4 não é mais utilizado. O MD2 é uma função de espalhamento unidirecional simplificada e produz um hash de 128 bits. A segurança do MD2 é dependente de uma
permutação aleatória de bytes. Não é recomendável sua utilização, pois em geral, é
mais lento do que as outras funções hash citadas e acredita-se que seja menos seguro.
A figura 11 apresenta algumas formas de se usar o código hash para autenticação de
mensagens:
a) A mensagem M concatenada com o código hash produzido por H é cifrada utilizando
cifragem convencional. Neste caso, A e B compartilham uma chave secreta K. O
código hash produzido por H provê a estrutura ou redundância requerida para efetuar
a autenticação. Neste esquema tem-se a autenticação, pois o código hash é cifrado e
enviado juntamente com M; tem-se também a confiabilidade da mensagem M, pois
somente A e B conhecem a chave K.
b) Neste caso, somente o código hash é cifrado usando cifragem convencional. O valor
hash resultante desta cifragem é protegido contra intrusos, pois esses não conhecem a
chave secreta compartilhada por A e B. Este esquema provê somente a autenticação
de M, visto que somente o código hash é cifrado.
c) Neste caso, somente o código hash H é cifrado usando cifragem de chave pública.
Como no item (b), isto provê autenticação (pois o código hash é cifrado). Este esquema também provê assinatura digital, pois somente o remetente pode produzir o
código hash cifrado. Observa-se que esta é a essência da técnica de assinatura digital.
d) Se a confiabilidade e a assinatura digital são desejadas, pode-se combinar a criptografia convencional com a criptografia de chave púbica. Neste caso, a mensagem
M é concatenada com o código hash produzido por H e cifrado pela chave privada
KRa; em seguida, o resultado é cifrado, usando a chave secreta K.
69
a)
Remetente
Destinatário
E
M
D
M
K
Ek [M || H(M)]
H
M
Com par ar
K
H(M)
H
b)
Remetente
Dest inatário
M
H
M
E
H
Comparar
K
K
D
EK [H(M)]
c)
Reme tente
Destinatário
H
M
M
KUa
KRa
E
H
Com parar
D
EK Ra[H(M)]
d)
Reme tente
Destinatário
E
M
KRa
H
E
M
D
M
K
K
E k [M || E KRa [H(M)] ]
E KRa [H(M)]
Figura 11 – Usos básicos da função Hash
H
KUa
D
Comp arar
70
CAPÍTULO 5
POLÍTICA DE SEGURANÇA DO MODELO BELL-LAPADULA
EM AMBIENTE CIFRADO
5.1. INTRODUÇÃO
Este capítulo apresenta uma extensão do Modelo Bell-Lapadula em um ambiente cifrado,
onde é proposto um algoritmo criptográfico de chave pública, que verifica a Política de Controle de Acesso do Modelo Bell-LaPadula sem a necessidade de decifrar os dados armazenados no servidor.
A implementação da maioria dos sistemas criptográficos de chave pública (RSA, ElGamal etc.) é baseada no grupo multiplicativo Zp, mas outros grupos também são candidatos
apropriados (KOBLITZ, 1999), (MENEZES, 1997), (ROSING, 1999), (SCHNEIER, 1996),
(STALLINGS, 1999), (STINSON, 1995). O Criptosistema das curvas elípticas de MenzesVanstone, por exemplo, usa os grupos elípticos que são definidos em curvas elípticas (MENEZES et al, 1993), (MENEZES, 1993). O criptosistema da Mochila de Merkle-Hellman é
baseado no problema da Mochila (MERKLE, 1978) e o criptosistema de McEliese é baseado
na teoria dos códigos corretores de erros (STINSON, 1995). Em geral, a segurança destes sistemas é baseada na intratabilidade do problema do logaritmo discreto, o qual foi objeto de
grande estudo (GORDON, 1993).
A política de segurança do Modelo Bell-Lapadula em ambiente cifrado se fundamenta no
esquema de assinatura Elgamal em Zp. Este esquema se fundamenta em grupos finitos multiplicativos, onde o problema do logaritmo discreto é intratável.
A subseção 5.1.1 apresenta o esquema de Assinatura Elgamal em Zp . A seção 5.2 apre-
71
senta uma proposta de representação e o armazenamento de dados, tendo como objetivo principal a representação e armazenamento dos sujeitos e objetos do modelo BLP. Em seguida,
na seção 5.3 é apresentado o algoritmo criptográfico, onde este permite manipular dados cifrados no servidor de controle de acesso, sem a necessidade de decifrá-los, aumentando assim
a segurança do controle de acesso mandatário do modelo BLP.
5.1.1. O ESQUEMA DE ASSINATURA DE ELGAMAL EM Z p
Seja p um número primo, tal que o problema do logaritmo discreto seja intratável em Z p
e g um gerador de Z *p . No esquema de assinatura ElGamal, um texto original m é um elemento de Z p e a assinatura de m é um par em Z p × Z *p −1 . Dado h ∈ H , tal que:
h = g a mod p
onde os elementos h e g são públicos e a é secreto. Para um número aleatório secreto
k ∈ Z *p −1 , a assinatura de m é definida por:
sig a (m, k ) = (z 1 , z 2 )
onde:
z1 ≡
g k (mod p ) ;
z2 ≡
(m − a z 1 )k −1 (mod ( p − 1)) .
Dada a assinatura z = (z 1 , z 2 ) de m, a sua verificação é feita utilizando a função de verificação:
ver (m, z ) = true
⇔ h z ( z 1 )z ≡
1
2
g m (mod p )
A correção da verificação da assinatura é demonstrada a seguir:
h z1 (z 1 ) 2 ≡
g az1 g hz2 (mod p )
h z1 (z 1 ) 2 ≡
g az1 + kz2 (mod p )
z
z
72
h z1 (z 1 ) 2 ≡
z
g m (mod p )
onde é utilizado que:
az 1 + kz 2 ≡ m (mod ( p − 1))
e o teorema de Fermat (KOBLITZ, 1994).
5.2. REPRESENTAÇÃO E ARMAZENAMENTO DOS ELEMENTOS
DO MODELO BLP
Os elementos do modelo BLP são representados em um ambiente cifrado, utilizando o
grupo finito Z p . Seja I uma instância de relação sobre um esquema (Q1 ,L , Qv ) (ELMASRI,
2000), (Silberschatz, 1997). Na primeira linha de I, os nomes dos atributos definem o esquema do banco de dados. Estes nomes são representados como elementos de Z p , ou seja, são
representados por números que pertencem ao conjunto:
{0,1,L , p − 1}
A primeira linha em I é uma lista e tem a forma:
[q1 ,L , qv ]
onde q i ∈ Z p , 1 ≤ i ≤ v e q i representa o atributo Q i .
No modelo BLP, cada atributo representa um sujeito ou um objeto, e os elementos de
uma tupla I representam suas classificações. De forma análoga aos sujeitos e objetos, os elementos que os classificam são representados por elementos de Z p , como será visto adiante,
o grupo Z p , é público. Isto significa que os termos TS, S, C, U são representados por elementos do grupo Z p . Seja T j a j-ésima tupla em I. A tupla T j é dada por.
Ti = [c 1 ,L , c v ] ,
onde para 1 ≤ i ≤ v , c i ∈ Z p .
73
Neste caso, ci é a representação da classificação de um sujeito ou objeto. Na tupla Ti, ci
representa a classificação do i-ésimo sujeito ou objeto.
No modelo BLP são consideradas três tabelas que armazenam as classificações dos sujeitos e objetos. Estas tabelas são indicadas a seguir:
Tabela 7 - Nível clearance Ts
Sujeitos
S1
K
Sm
f s1
K
f sm
onde f s1 ,L , f sm são as classificações máximas dos sujeitos ( clearance ).
Tabela 8- Nível corrente Tc
Sujeitos
S1
K
Sm
f c1
K
f cm
onde f c1 ,L , f cm são as classificações correntes dos sujeitos.
Tabela 9– Nível do objeto To
Objetos
o1
K
om
f o1
K
f om
onde f o1 ,L , f om são as classificações dos objetos.
Para cada tabela acima, tem-se a sua versão cifrada, que é denotada por ETs, ETc, ETo.
Estas tabelas são armazenadas no servidor de controle de acesso DCA. Dado um sujeito
Si, ele é cifrado pela equação:
a i = g hash ( si ) modp
74
Da mesma forma, um objeto Oi é cifrado por:
b i = g hash(oi ) modp
As classificações f si , f ci , f oi , são cifradas pelas equações:
x si = g f si modp
x ci = g f ci modp
x oi = g f oi modp
Nas equações acima, hash(q i ) representa a aplicação de uma função hash ao valor qi.
Portanto, um sujeito s i é cifrado por g hash( si ) modp e um objeto o i por g hash(oi ) modp . Da
mesma forma, uma classificação é cifrada por g ci modp . Os dados em ETs , ETc e ETo são
armazenados no servidor de controle de acesso. Observe que tais dados são cifrados utilizando os parâmetros públicos g e p, onde o elemento g é um gerador do grupo Z *p .
No modelo BLP também é definida a matriz M dos modos de acesso
{append, read, write, execute} dos sujeitos sobre os objetos. Uma entrada desta matriz, indicada por M [s, o] , representa o conjunto dos modos de acesso do sujeitos s sobre o objeto o,
conforme é mostrado na tabela 10:
Tabela 10– Tabela M
Objetos
Sujeitos
o1
K
on
s1
K
M [s 1 , o1 ]
K
K
M [s 1 , o n ]
K
sm
M [s m , o1 ]
K
K
M [s m , o n ]
Para cada matriz M, tem-se a sua versão cifrada, que é denotada por EM. Em EM são
armazenadas as versões cifradas apenas dos sujeitos e objetos, conforme indicado tabela 11:
75
Tabela 11– Matriz EM
Objetos cifrados
Sujeitos cifrados
b1
K
bn
a1
M [a 1 , b1 ]
K
M [a 1 , bn ]
K
K
K
K
am
M [a m , b1 ]
K
M [a m , bn ]
onde, para todo i, tem-se:
ai ≡
g hash( si ) (mod p )
bi ≡
g hash(oi ) (mod p )
Observe que as entradas da tabela não são cifradas.
M [a 1 , b1 ] ⊇ {append, read, write, execute}.
5.3. POLÍTICA DE SEGURANÇA DO MODELO BELL-LAPADULA
EM AMBIENTE CIFRADO
Um dos objetivos do modelo BLP é incrementar o controle de acesso discricionário adicionando uma política mandatária. Isto reforça a política de controle de fluxo da informação.
Na análise que se segue, é considerada inicialmente a parte discricionária do modelo BLP, e,
em seguida, a parte mandatária. Inicialmente, são definidas as tabelas cifradas ETs, ETc, ETo
e EM.
Seja s w um sujeito e DCA um servidor de controle de acesso em ambiente cifrado. Suponha que o sujeito s w queira executar um modo de acesso m sobre um objeto o. Para isto, é
necessário que s w envie para o DCA, de forma cifrada, a sua identificação e a do objeto. O
modo de acesso requerido também é enviado ao DCA de forma não cifrada. Portanto, s w en-
76
via ao DCA os dados E (s w ) , E (o ) e o modo de acesso m. A partir destes dados, o servidor
DCA deve verificar os axiomas do BLP em um ambiente cifrado, sem a necessidade de decifrar E (s w ) , E (o ) e os dados armazenados na sua memória principal ou secundária.
O algoritmo a seguir é uma solução para este problema. Neste algoritmo é considerada a
notação usual utilizada em inúmeras referências (STALLINGS,1999 ), onde || significa
concatenação.
Algoritmo para controle de acesso cifrado.
1.
DCA → s w
g p
2.
s w → DCA
z1 z2 z3 m h
3.
DCA
Calcula chs , cho
4.
DCA
M ∈ EM
5.
DCA
Verifica axiomas
Passo 1 - DCA → s w
g p
O sujeito s w recebe do servidor de controle de acesso DCA os parâmetros públicos g e
p . O número g é um gerador do grupo Z *p , onde p é primo.
77
Passo 2 - s w → DCA
z1 z 2 z 3 m h
O sujeito s w representa a sua identificação e a do objeto o como um elemento de Z p . Para cifrar s w e o, o sujeito s w calcula no grupo Z p :
z1 ≡
g k (mod p )
z 2 ≡ (hash(s w ) − γ z 1 )k −1 (mod ( p − 1))
z 3 ≡ (hash(o ) − γ z 1 )k −1 (mod ( p − 1))
h≡
g γ (mod p )
Os valores γ e k são números randômicos secretos em Z *p −1 , escolhidos pelo sujeito s w .
Após esses cálculos, o sujeito agrega o modo de acesso m ao conjunto acima e envia
z 1 z 2 z 3 m h para o servidor de controle de acesso DCA.
É importante ressaltar que a cada seção z 1 , z 2 e z 3 e h são diferentes, pois é utilizado
um valor aleatório k para cada requisição do sujeito s w . Desta forma, o intruso não consegue
deduzir qual sujeito está solicitando e qual objeto é solicitado. Esta estratégia impede, por
exemplo, o ataque do meio (STALLINGS, 1999).
Passo 3 – DCA
Calcula chs , cho
O servidor de controle de acesso DCA calcula os valores de verificação do sujeito s w e
do objeto o, denominados respectivamente por chs e cho . Tais cálculos são efetuados sem
revelar que sujeito e objeto estão sendo considerados na operação.
78
chs = h z1 (z 1 ) 2
z
cho = h z1 (z 1 ) 3
z
Observe que:
chs = h z1 (z 1 ) 2
z
h z1 (z 1 ) 2 ≡
g az1 g hz2 (mod p )
h z1 (z 1 ) 2 ≡
g az1 + kz2 (mod p )
h z1 ( z 1 ) 2 ≡
g hash( sw ) (mod p )
z
z
z
e,
cho = h z1 (z 1 ) 3
z
h z1 ( z 1 ) 3 ≡
g az1 g hz3 (mod p )
h z1 ( z 1 ) 3 ≡
g az1 + kz3 (mod p )
h z1 ( z 1 ) 3 ≡
g hash(o ) (mod p )
z
z
z
Em seguida, o DCA verifica se:
{
}
{
}
chs ∈ g hash( s1 ) (mod p ),L , g hash ( sm ) (mod p ) , e
cho ∈ g hash(o1 ) (mod p ),L , g hash(on ) (mod p )
Identificando i, j tais que:
ch s ≡
g hash( si ) (mod p ) , e
cho ≡
g
( )
hash o j
(mod p ) .
79
Neste caso, s i = s w , se o sujeito s w está cadastrado no DCA. Da mesma forma, o j = o ,
se o objeto o está cadastrado no DCA. Observa-se que o DCA calcula chs e cho , sem ter
conhecimento de s w e o.
Passo 4 – DCA
m ∈ EM
A partir de chs e cho o servidor DCA identifica a entrada na matriz EM correspondente a
M [s w , o] . Na parte discricionária, o servidor DCA verifica se o modo de acesso m está contido em M [s w , o] . Caso haja sucesso, o passo 5 é executado; caso contrário, o modo de acesso
m, requisitado pelo sujeito s w sobre o objeto o,é negado.
Passo 5 – DCA
Verifica axiomas
Na parte mandatária, o servidor DCA busca as classificações cifradas do sujeito s w e do
objeto o, utilizando chs e cho nas suas respectivas bases de dados cifradas. Utilizando chs e
as tabelas ETs, ETc, o DCA identifica x sw , tal que x sw ≡
x cw ≡
g
fcw
x o , tal que x o ≡
(mod p ) . Da mesma forma, utilizando
g
f sw
(mod p ) e
x cw , tal que
cho e a tabela ETo , o DCA identifica
g fo (mod p ) . De posse das classificações cifradas, o servidor DCA compa-
ra estas classificações, sem decifrá-las na memória principal ou secundária. Estas comparações são necessárias para verificar os axiomas do modelo Bell-LaPadula que devem ser satisfeitos para garantir a segurança do sistema.
Para efetuar as comparações, definidas pela propriedade estrela, o servidor de controle de
acesso DCA calcula chy , tal que:
80
( )
chy = x o x cw
−1
Observe que:
( )
chy = x o x cw
−1
( )
( )
≡ g fo g
( )
≡g
x o x cw
x o x cw
−1
−1
f c w −1
f o − fcw
(mod p )
(mod p ) ,
onde f o , f cw são as classificações em claro do objeto e sujeito respectivamente.
Se chy ∈ {g −1 ,L , g − max }, onde max <
g −c ≡
g
fo − fcw
p−1
, então existe c tal que:
2
(mod p ) , para algum c, tal que 1 ≤ c ≤ max .
Neste caso,
f cw > f o
Tal fato ocorre pois se max <
{g
−1
} {
,L , g − max ≠ g 1 ,L , g max
p−1
, então
2
}
logo,
g − x ≠ g x (mod p ) , para 1 ≤ x ≤ max .
Suponha por absurdo que
g−x ≡
g x (mod p )
logo,
g 2 x ≡ 1(mod p )
2x ≡ 0 (mod ( p − 1))
81
x=0
Isto é um absurdo pois 1 ≤ x ≤ max . Portanto, g − x ≠
g x (mod p )
Por outro lado, se Ch y ∈ {g 1 ,L , g max } então existe c, tal que:
gc ≡
fo − fcw
g
(mod p ) , para algum c, tal que 1 ≤ c ≤ max .
Logo:
f cw < f o
.
Finalmente se Ch y = 1 então f cw = f o
Para verificar os axiomas da propriedade estrela é necessário verificar as implicações.
•
append ∈ EM [s w , o] ⇒ chy = g c ;
•
write ∈ EM [s w , o] ⇒ chy = 1 ;
•
read ∈ EM [s w , o] ⇒ chy = g − c .
Para algum c, tal que 1 ≤ c ≤ max .
A propriedade ss é verificada observando-se a desigualdade f s (s w ) ≥ f o (o ) é satisfeita.
Para verificar esta desigualdade em um ambiente cifrado o servidor de controle de acesso
DCA calcula chr tal que:
( )
chr = x o x sw
−1
Neste caso:
( )
chr = x o x sw
−1
( )
( )
≡ g fo g
( )
≡g
x o x sw
x o x sw
−1
−1
f s w −1
f o − f sw
Portanto, chr ≡ g
(mod p )
(mod p ) ,
f o − f sw
(mod p ) , onde
f o , f sw são as classificações em claro do objeto e
82
sujeito respectivamente.
{
}
Se chr ∈ g −1 ,L , g − max , então existe c, tal que:
g −c ≡
g
fo − f sw
Logo:
f sw > f o .
(mod p ) , para algum c, tal que 1 ≤ c ≤ max .
83
CAPÍTULO 6
CONCLUSÃO
Nesta dissertação, a política de segurança do modelo Bell-LaPadula (BLP) é reforçada,
cifrando os sujeitos e os objetos do sistema, juntamente com suas classificações. Isto impede
que um intruso tenha acesso a dados através de algum tipo de monitoramento da memória do
servidor de controle de acesso (DCA).
Esta dissertação propõe um algoritmo criptográfico que verifica os axiomas do modelo
Bell-Lapadula em um ambiente cifrado. Deste modo, incrementa-se a segurança da política de
controle de acesso mandatário, pois um intruso tem acesso somente às informações cifradas.
Esta estratégia impede alguns tipos de ataque, como por exemplo, o ataque do meio. Isto
ocorre porque caso o intruso consiga acessar e ler o conteúdo dos canais de comunicação, ele
não consegue deduzir qual sujeito está solicitando e qual objeto é solicitado.
No algoritmo apresentado, a segurança do sistema ainda é mantida, mesmo no caso em
que as classificações de sujeitos e objetos não são cifradas. Observa-se que o processamento
necessário na execução do algoritmo apresentado refere-se apenas aos cálculos de chs, cho, chy
e chr. Os outros cálculos para cifragens das tabelas podem ser feitos antecipadamente.
Esta dissertação considera também uma apresentação dos fundamentos da Teoria dos
Números e da criptografia necessários à definição e compreensão do algoritmo proposto.
84
REFERÊNCIAS BIBLIOGRÁFICAS
AGRAWAL, M.; KAYAL, N.; NITIN, S. Primes is in P India: Indian Institute of Technology
Kanpur, 2002.
BELL, D. E.; LAPADULA, L. J. Secure Computer System: Unified Exposition and Multics
Interpretation (1975).
BUCHMANN, J. A. Introdução à Criptografia. São Paulo: Berkeley, 2002.
CASTANO, S.; FUGINI, M.; MARTELLA, G.; SAMARATI, P Database Security Reading.
Addison-Wesley, 1994.
COSTA, R., V., S.; SOUZA, J. N. Gerenciamento de Banco de dados em Ambiente Cifrado.
In:Jornadas Iberoamericanas de Informática, 9., 2003a, Colômbia.
COSTA, R., V., S. ; SOUZA, J. N.; SILVA, I. R. Criptografia aplicada a Banco de Dados In:
Regional de Informática, 11., 2003b, Londrina.
COSTA, R., V., S. ; SOUZA, J. N.; SILVA, I. R. Banco de Dados Relacionais em Ambiente
Cifrado. In:Simpósium de Segurnaça em Informática, 5., 2003c, São José dos Campos.
ELGAMAL, T. A Public Key Cryptosystem and a Signature Scheme based on Discrete Logarithms. IEEE Transactions on Information Theory, 31, 1985.
ELMASRI, R.; NAVATHE, S. B. Fundamentals of Database Systems. 3 ed. Addison-Wesley,
2000.
85
GORDON, D. M., MCCURLEY, K.S., Massively parallel computation of discret logarithms.
LNCS, 740, 1993.
KOBLITZ, N., A Course in Number Theory and Cryptography. Springer Verlag, 1994.
KOBLITZ, N. Algebraic Aspects of Cryptography. Springer Verlag, 1999.
MENEZES, A. J. Elliptic Curve Public Key Cryptosystem. Kluwer Academic Publishers,
1993.
MENEZES, A. J.; OKAMOTO, T.; VASTONE, S. A., Reducing Elliptic Curve Logarithms
to Logarithms in a Finite Field. IEEE Transaction on Information Theory, 39, 1993.
MENEZES, A. J., VAN OORSHOT, P. C., VASTONE, S. A., Handbook of Applied Cryptography, CRC Press, 1997.
MERKLE, R. C., HELLMAN, M. E., Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Transaction on Information Theory, 24, 1978.
ROSING, M. Implementing Elliptic Curve Cryptography, Manning, 1999.
SCHNEIER, B. Applied Cryptography. John Willey, 1996.
SOUZA, J. N., SILVA, I. R., MOREIRA, M. A Multi-User Key and Data Exchange Protocol
to Manage a Secure Database. In: Simpósio Brasileiro de Banco de Dados, 17., 2002.
SOUZA, J. N., SILVA, I. R., Protocols to Manage Encrypted Data in a Database Without the
Need to Decipher, Technical Report, Universidade Federal de Uberlândia, 2003a.
86
SOUZA, J. N., SILVA, I. R. Secury Manipulation of Encrypted Passwords. Uberlândia: Universidade Federal de Uberlândia, 2003b, Technical Report.
STALLINGS, W. Cryptography and Network Security: Principles and Practice. 2. ed. New
Jersey: Prentice-Hall, 1999.
STINSON, D. R. Cryptography, Theory and Practice. CRC Press, 1995.
VIEIRA, F., J.; SOUZA, J., N. Uma Extensão do Protocolo SET Para Acesso a Base de Dados Cifrados. In:Jornadas Iberoamericanas de Informática, 9., 2003a, Colômbia.
VIEIRA, F., J.; SOUZA, J., N., SILVA, I. R. Transação Eletrônica Segura com Acesso a Base
de Dados Cifrados. In:Simpósium de Segurnaça em Informática, 5., 2003b, São José dos
Campos.