Monografia sobre Criptografia baseada em Identidade.

Uma breve Introdução

O que é criptografia?

Utilizada desde a Antiguidade (embora sem tanta sofisticação) passando pelas duas grandes guerras até chegar ao homebanking, a criptografia é a ciência de segurança de informações. O nome deriva do grego kryptós, 'oculto, secreto, obscuro, initeligível' e -graphía, 'escrita'. 
Utilizando um forte embasamento matemático, a criptografia permite a você ocultar informação de tal forma que ela não possa ser recuperada por ninguém além do destinatário designado.
Dois são os principais esquemas criptográficos atualmente utilizados:

Na Criptografia Simétrica - também chamada de Criptografia de Chave Secreta - a chave que transforma o texto claro em texto cifrado é a mesma que será usada mais tarde, pelo destinatário, para converter o texto cifrado de volta em texto claro.
 

Nesse esquema, deve haver uma chave para cada par de usuários. Não é difícil notar que o número de chaves cresce bem mais rápido que o número de usuários (para ser exato, são necessárias n(n - 1)/2 chaves para n usuários. Além disso, estas chaves devem ser trocadas por algum canal seguro.

 2 usuários - 1 chave
3 usuários - 3 chaves
4 usuários - 6 chaves
5 usuários - 10 chaves

Já na Criptografia Assimétrica - ou Criptografia de Chave Pública - cada usuário deve possuir duas chaves: uma pública, usada para criptografar, e outra privada, utilizada na decriptografia. Embora o número de chaves necessárias seja bem menor que no esquema anterior (2n chaves para n participantes), é necessário um repositório centralizado que esteja sempre on-line para gerenciar todas elas.
 

Por que criptografia baseada em identidade?

Em 1985, Adi Shamir sugeriu um esquema similar ao sistema postal, em que a chave de um usuário seria função de sua identidade, evitando assim a necessidade de um diretório de chaves públicas, trocas de chaves ou uma autoridade superior que esteja sempre presente. Como num sistema postal, se você souber o nome e o endereço de alguém você pode enviar mensagens que apenas essa pessoa consiga ler e pode verificar as assinaturas que somente ela possa ter produzido.
Desde então, vários criptossistemas baseados em identidades têm sido propostos, mas este esquema tem se mostrado difícil de encontrar implementações que sejam práticas e ao mesmo tempo seguras.

Sistema De Criptografia Baseada Em Identidade Fundamentada Em Resíduos Quadráticos - Clifford Cocks

1. Visão Geral

O sistema possui uma autoridade, chamada de Private Key Generator, que calcula e publica o produto M de dois primos P e Q (escolhidos em segredo). Esses primos são ambos congruentes a 3 mod 4. O sistema também faz uso de uma função hash conhecida e segura.
Assim, se um usuário deseja se registrar para ser capaz de receber dados codificados ele envia sua identidade (p.ex. endereço de e-mail) para a autoridade, que lhe devolve uma chave privada. Quando um outro usuário deseja enviar informação criptografada para outro, ele faz isso conhecendo a chave pública do destinatário e os parâmetros globais. Não há necessidade de nenhum diretório de chaves públicas.
Repare que pode ser difícil para o PKG verificar se a identidade apresentada é mesmo do usuário que a manifestou.

2. Detalhes Sobre O Funcionamento

Quando um usuário apresenta sua identidade ao PKG, a função de hash é aplicada para produzir um valor a mod M tal que (a / M) = +1 (lê-se "a Jacobiano M"). Isso significa que a é resíduo quadrático módulo M, ou seja, existe um r Î Z*M tal que r2 = a mod M. Esse processo pode ser repetido por quem quiser. No entanto, há, tipicamente, vários candidatos "a". A escolha da raiz r, que depende de a, e que vai ser passado ao usuário é próprio do PKG, obviamente, mas há uma sugestão de como calcular uma das raízes de a  com pouco processamento . Esse valor "r" é usado pelo usuário para recuperar mensagens enviadas a ele. Além disso, não sabemos se r2 = a mod M ou -a mod M.

3. Como assim?

Como (a / M) = +1, pela propriedade desse símbolo, (a / M) = (a / P)(a / Q). Dado que os valores assumidos são apenas +1, -1 e 0, segue que:

4. Como enviar mensagens?

Seja x o bit a ser enviado (usar -1 se o bit for 0 e +1 se o bit valer 1);
O remetente escolhe um valor t aleatório mod M, tal que (t / M) = x;
Ele então envia s = (t + a / t) mod M. Repare que a / t significa a * t-1 mod M.
Esses passos devem ser repetidos para cada bit que se deseja transmitir. Caso o remetente não saiba se o destinatário recebeu a raiz quadrada de a ou -a, ele deve enviar, para o mesmo valor x, s = (t - a / t) mod M, usando diferentes valores para t.

5. E como recuperar as mensagens?

Para recuperar x, o destinatário calcula s + 2r, pois:
s + 2r = (t + a / t) + 2r
= (t + r2 / t) + 2r, pois r2 = a mod M
= t (1 + r2 / t2 + 2r / t)
= t (1 + r / t) (1 + r / t)
Como o símbolo de Jacobi de (1 + r / t) sobre M é igual a  +1 ou -1, temos que ( [1 + r / t] / M )( [1 + r / t] / M ) = +1 em todo caso. Daí resulta que ( s + 2r / M ) = ( t / M ) = x.  

6. Um exemplo didático

Suponha M = 21. E que o destinatário tenha recebido o valor 19.
Para enviar o bit 1, o remetente primeiramente mapeia o valor para +1. Em seguida, escolhe o valor t = 10 ao acaso - mas respeitando ( t / 21 ) = +1.
t-1 vale 19. Finalmente o remetente calcula s = 10 + 4 * 19 = 86 mod 21 = 2 e envia esse valor.
O destinatário recebe s e calcula:
( 2 + 38 / 21 ) = ( 40 / 21 )

= ( 20 / 21 )( 2 /21 )
= (-1)(-1)
= +1
= x

7. Problemas

Como os bits são enviados individualmente, sem nenhum teste de integridade, cada bit pode ser alterado independentemente. Além disso, a segurança desse esquema está baseada na dificuldade de fatoração de números inteiros. Se um mal-intencionado conseguir descobrir a fatoração de M, ele pode calcular todos os possíveis valores a e suas raízes quadradas.
Outro inconveniente, desta vez sem ser relacionado a segurança, é a quantidade de informação enviada para se criptografar um único bit.
Um último problema é quando s + 2r for múltiplo de algum dos primos P ou Q. Quando o destinatário for calcular o jacobiano ( s + 2r / M ) irá obter o valor zero e não conseguirá recuperar o valor daquele bit. A descrição do algoritmo não especifica o que fazer nesse caso (na verdade, sequer menciona esta falha).

8. Implementação

Programei este esquema de criptografia em C++, na plataforma WindowsT. 
Util é uma classe estática que contém funções utilizadas por todo o programa, como o algoritmo para calcular o jacobiano (cedido pelo professor Routo), a função de hash (retirada do livro 'Programming Pearls') e outras como o cálculo do inverso multiplicativo ou para descobrir se um número é primo. Por estarmos tratando de uma implentação didática do algoritmo, esta classe (assim como todas as outras) não foi escrita com a finalidade de ser eficiente.
A classe singleton PKG representa a autoridade geradora das chaves.
User é a classe que denota os usuários do sistema. É nesta classe que estão programadas as funções de criptografia e decriptografia. Coloquei nesta classe um método que diz se o usuário recebeu a raiz de a ou de -a, para que o remetente não precise dobrar a quantidade de dados enviados (isso foge à especificação do algoritmo).
Para que o destinatário consiga recuperar todos os bits recebidos, tive que permitir que o remetente tenha acesso à sua chave privada para impedir que gere valores que caiam no terceiro problema comentado acima. Isso inutiliza o algoritmo mas garante a corretude do programa. Como alternativa, o destinatário poderia pedir que o remetente enviasse novamente o bit, calculado de maneira diferente. Mas essa informação pode facilitar que um mal-intencionado descubra o valor da chave secreta do destinatário.

Esquema De Assinatura Baseada Em Identidade - Adi Shamir

1. Visão Geral

Este esquema também é inspirado em criptosistemas de chave pública onde ao invés de gerar um par de chaves pública/privada e publicar uma delas, o usuário escolhe sua identidade (comumente e-mail) como sua chave pública.
Desta vez também temos uma autoridade confiável, chamada de Trusted Authority, cujo único propósito é definir os parâmetros globais do sistema e dar a cada usuário uma chave que será usada para a assinatura de mensagens.
Um usuário, após apresentar sua identidade, tem sua chave gerada. A partir deste momento a autoridade não é mais necessária. Repare que, ao contrário da criptografia de chave pública no sentido habitual, para um usuário verificar a assinatura de outro usando sua chave pública ele também deve verificar a autenticidade desta. Torna-se inevitável a presença da autoridade certificadora.

2. Detalhes Sobre O Funcionamento

Antes de oferecer o serviço de geração de chaves, a TA deve configurar os seguintes parâmetros do sistema:

Os valores n, e e a descrição da função h são conhecidos por todos os usuários. Uma vez tendo estes valores definidos, já é possível gerar as chaves dos usuários.
Ao apresentar sua identidade, o usuário tem sua chave g calculada pela TA através da fórmula g ≡ f(ID)d mod n, onde f é uma função de hash segura (podendo ser a mesma função h).

3. Geração da assinatura

Para assinar uma mensagem m um usuário escolhe aleatoriamente um inteiro r pertencente a Z*n e calcula t = re mod n e s = grh(t,m) mod n.
A assinatura é o par (s, t).

4. Verificação da assinatura

Ao receber uma mensagem m e uma assinatura (s, t), o receptor usa a identidade ID do rementente para verificar a autenticidade dos dados.
A assinatura é válida se se ≡ f(ID)th(t,m) mod n, pois nesse caso se verifica que o remetente têm em sua posse f(ID)th(t,m) além da única e-ézima raiz módulo n (a unicidade é garantida pelo fato de e e φ(n) serem primos entre si).
Isso significa que neste esquema a verificação da assinatura confirma (ou nega) duas coisas ao mesmo tempo:

Portanto, não há necessidade de se realizar uma apuração separada.

5. Um exemplo didático

Suponha novamente n = 21.
φ(21) = φ(3)φ(7)
= (3 - 1)(7 - 1)
= 12

e = 11

d = 11

f(ID) = 9

O remetente apresenta sua identidade à TA, que calcula sua chave:
g = f(ID)d mod n
= 911 mod 21
= 18

Em seguida o remetente assina uma mensagem:
r = 8

h(t, m) = 2
t = re mod n
= 811 mod 21
= 8

s = grh(t,m) mod n
= 18.82 mod 21
= 18

Finalmente, o destinatário verifica a autenticidade da assinatura recebida:
se ≡f(ID)th(t,m) mod n
1811 ≡9.82 mod 21
9  9

E confirma que é uma assinatura válida.

6. Problemas

Este esquema não permite a revogação de chaves (necessária quando a chave privada do usuário torna-se comprometida), já que há unicidade de chaves para cada identidade.
Também precisamos lembrar que a autoridade confiável pode não ser confiável (ela pode forjar qualquer chave de qualquer usuário). Isso restringe o uso desse esquema a sistemas fechados onde há total convicção na integridade da autoridade.

7. Implementação

Usando da mesma linguagem e plataforma, este programa tem estrutura muito parecida com o anterior.
A classe Util é a mesma do projeto anterior, onde encontramos funções como a que calcula m.d.c. de dois números ou o inverso multiplicativo módulo n de um número
TA é a classe que faz o papel da autoridade. Sua única função é gerar os valores globais e criar as chaves dos usuários.
User representa os usuários do esquema. Aqui estão implementadas as funções de geração e verificação de assinatura.
Este programa, mesmo utilizando primos muito maiores do que o de criptografia, executa muito mais rapidamente que o primeiro. Não por estar melhor implementado, apenas por ter um algoritmo mais simples.

Glossário

Chave: valor aplicado utilizando-se um algoritmo sobre informação não criptografada para produzir informação encriptada. Quanto maior o comprimento da chave, maior é também a dificuldade de se conseguir recuperar a informação original por força bruta - se o algoritmo de criptografia for seguro.

Texto claro: também chamado de texto comum, texto normal ou texto legível. É a informação (tipicamente texto, daí o nome) antes de ser criptografada (ou após ser decriptografada). 

Texto cifrado: ou texto ilegível. A informação após passar pelo processo de criptografia.

Função de hash: também denominada função espalhamento. Transforma um dado texto legível em uma cadeia de caracteres de tamanho fixo relativamente menor que o comprimento do texto legível. Uma função hash é dita segura se os elementos do domínio são distribuídos uniforme e aleatoriamente pela imagem, de modo que textos legíveis muito parecidos tenham alta probabilidade de possuírem valores hash diferentes. Grosseiramente falando, queremos que H("Cauda") ≠ H("Calda").

Símbolo de Jacobi: este símbolo, escrito como ( n / m ) é definido para valores m ímpares positivos como ( n / m ) = ( n / p1 )a1 ( n / p2 )a2 ... ( n / pk )ak, onde m = p1a1p2a2...pkak é a fatoração prima de m e ( n / pi ) é o símbolo de Legendre (o símbolo de Legendre é igual a +1 ou -1 dependendo se n é ou não resíduo quadrático mod m e vale 0 se os dois termos não são primos entre si - isto é, mdc(n, p) ≠ 1).

Z*M: é o conjunto de todos os números inteiros mod M relativamente primos a M. No caso particular de M ser primo,  Z*M = ZM - {0}

Experiência pessoal

Já sabia desde o ano anterior o tipo de trabalho de formatura que tentaria desenvolver. Tendo feito estágio desde o primeiro ano de curso, era hora de tentar outro desafio. Dado o meu interesse pela área de segurança, era natural que optasse pela iniciação científica em Criptografia.
Como nunca havia participado de uma iniciação, confesso que subjulguei sua dificuldade. Mesmo tendo acertado com meu orientador já no primeiro semestre, foi só a partir do segundo que comecei efetivamente a procurá-lo para tratar dos assuntos que me havia indicado para estudo.
Isso foi um problema, pois no segundo semestre fui monitor e também passei a cursar muitas disciplinas, tanto no IME, quanto em outras unidades (FE, FFLCH), como optativas livres ou eletivas. Tive uma falsa impressão que mesmo com a quantidade absurda de créditos, seria fácil o semestre pois apenas em duas disciplinas teria provas para fazer.
Não é preciso ser muito observador para perceber o quanto isso atrapalhou minha iniciação (que poderia ter terminado ainda no primeiro semestre), de forma que ao final do ano eu só trabalhava em "deadline".
Apesar dos tropeços, gostei de ter aprendido essa "nova" idéia de criptografia, que apesar de seus problemas, tem uma abordagem inédita e interessante, além de parecer uma área de estudo bem promissora. E também confirma meu interesse nessa área da computação.
Além disso decidi que programaria os algoritmos usando C++. Pela qualidade do código é fácil ver que ainda tenho muito o que aprender, mas serviu como um ótimo pontapé inicial (e também serviu para que eu começasse a desenvolver uma classe para representar inteiros módulo M de maneira eficiente e limpa).

Não quero cair no óbvio dizendo que as matérias introdutórias da computação foram importantes. Vamos para o que fez diferença: 
MAT123 - Álgebra I: essa disciplina não é realmente da computação, mas deveria, pois além de ser legal, é a base de metade dos conceitos usados em criptografia.
MAT213 - Álgebra II: aqui está a base da outra metade dos conceitos. Muito mais difícil, mas também garante criptossistemas mais seguros.
MAC336 - Criptografia para Segurança de Dados: obviamente não poderia ficar de fora. Aqui estudamos os principais algoritmos de criptografia e suas aplicações. Embora vejamos muitos algoritmos durante o curso, hoje sei que são apenas uma pequena parte.

Referências

Wenbo Mao - A textbook of non-textbook cryptography

Adi Shamir - Identity-based cryptosystems and signature schemes 

Clifford Cocks - An identity based encryption scheme based on quadratic residues

Aram Khalili - Notes on identity-based encryption by Clifford Cocks

Routo Terada - Segurança de dados - criptografia em redes de computador

Shawna M. Meyer e Jonathan P. Sorenson - Efficient algorithms for computing the Jacobi Symbol

Network Associates - An introduction to cryptography (fonte também de "inspiração" das imagens usadas neste texto)

Whatis?com - Dicionário de tecnologia

Wikipedia - the free encyclopedia (http://www.wikipedia.org)

Mathworld - the web´s most extensive mathematics resource (http://mathworld.wolfram.com)

Planetmath.org - math for the people, by the people (http://planetmath.org)