Álgebra Abstrata: Teoria e Aplicações

Subseção 7.6.1 Construindo chaves

Suponha que Alice quer enviar uma mensagem secreta para Bob, junto com uma mensagem de verificação (também conhecida como assinatura digital). Começaremos com a construção de um par de chaves (privada e pública) para Alice e para Bob. Primeiro necessitamos de dois primos grandes e seu produto para cada um deles. Na prática, valores de \(n\) teriam centenas de dígitos, no lugar de somente \(21\text{,}\) como fizemos aqui.

Computacionalmente, o valor da função \(\phi\) de Euler do produto de dois primos \(pq\) pode ser obtida como \((p-1)(q-1)\text{,}\) mas podemos igualmente usar a função interna da Sage.

Agora podemos criar os expoentes de encriptação e decriptação. Escolhemos o expoente de encriptação como um número (pequeno) relativamente primo com o valor de \(m\text{.}\) Com Sage pode fatorar \(m\) rapidamente para escolher este valor. Na prática não queremos fazer esse cálculo para valores grande de \(m\text{,}\) assim podemos escolher mais facilmente valores “aleatórios” e verificar até o primeiro valor relativamente primo com \(m\text{.}\) O expoente de decriptação é o inverso multiplicativo, mod \(m\text{,}\) do expoente de encriptação. Se você construir um expoente de encriptação inadequado (não relativamente primo com \(m\)), o cálculo do inverso multiplicativo irá falhar (e a Sage irá te falar). Fazemos isto duas vezes — para Alice e para Bob.

Nesta etapa, cada indivíduo publicaria seus valores de \(n\) e \(E\text{,}\) guardando \(D\) em forma privada e segura. Na prática \(D\) deve estar protegido no disco rígido do usuário por uma chave que só o dono conheça. Para uma maior segurança, uma pessoa poderia ter só duas cópias de sua chave privada, uma em memória USB que sempre leve consigo e uma copia de reserva em sua caixa de segurança na Sage. Cada vez que a pessoa usa \(D\) deverá indicar sua chave. O valor de \(m\) pode ser descartado. Para o registro, aqui estão todas as chaves:

Subseção 7.6.2 Assinando e Encriptando uma Mensagem

Alice construirá uma mensagem que consiste de uma palavra de quatro letras em inglês. A partir destas quatro letras construiremos um número que represente a mensagem na forma que necessitamos para usar no algoritmo RSA. A função ord() converterá uma letra em seu valor ASCII, um número entre 0 e 127. Se usamos esses números como “dígitos” mod 128, podemos estar seguros que a palavra de quatro letras de Alice se codificará como um inteiro menor que \(128^4=268,435,456\text{.}\) O valor particular não tem importância, por mais que seja menor que o nosso valor \(n\) pois toda a aritmética que segue é mod \(n\text{.}\) Escolhemos uma palabra popular de quatro letras, a convertemos em “dígitos” ASCII com uma lista e construímos o inteiro a partir dos dígitos na base correta. Note como podemos tratar a palavra como uma lista e que o primeiro dígito na lista está no lugar das “unidades”.

Primero, Alice assinará sua mensagem para fornecer uma verificação. Para isso ela usa sua chave privada, pois isto é algo que só ela deve ser capaz de fazer.

Logo Alice encripta a mensagem de maneira que só Bob possa ler. Para isso usa a chave pública de Bob. Note que não é necessário que ela conheça Bob — por exemplo, ela poderia ter obtido a chave pública de Bob em sua página Web ou então Bob publicou no New York Times.

A mensagem de Alice está pronta para ser transmitida por qualquer rede, não importando o quão segura a rede seja e não importando quantas pessoas possam estar vigiando-a.

Subseção 7.6.3 Decriptação e Verificação da Mensagem

Agora suponha que o valor de encrypted chegou a Bob. Bob poderia não conhecer Alice nem necessariamente crer que recebeu uma mensagem genuinamente enviada por ela. Um adversário poderia estar tentando confundir Bob enviando mensagens que supostamente vieram de Alice. Primeiro, Bob sabe desfazer a encriptação feita por Alice. Isso é algo que somente Bob, como o receptor intencionado, deve ser capaz de realizar. E pode fazer isso usando sua chave privada, que só ele conhece, e que ele mantém segura.

Neste momento, a mensagem não tem grande significado para Bob. Qualquer um poderia ter enviado uma mensagem encriptada para ele. Mas, esta era uma mensagem assinada pela Alice. Vamos desfazer a assinatura. Note que isso requer a chave pública de Alice. Bob não precisa conhecer Alice — por exemplo, poderia obter a chave pública de Alice de sua página web ou então Alice a publicou no New York Times.

Bob precisa transformar esta representação inteira de volta a uma palavra com letras. A função chr() converte valores ASCII em letras, e usamos uma lista para fazer isso de forma repetida.

Se queremos um resultado mais reconhecível, podemos combinar estas letras em uma string.

Bob está contente em obeter uma mensagem tão informativa quanto a mensagem de Alice. Agora, o que aconteceria se um impostor tivesse enviado a mensagem fingindo ser Alice, ou e se o adversário tivesse interceptado a mensagem original de Alice e adulterado-a? (a segunda pergunta é o que conhecemos como um ataque do “homem no meio”.)

Em qualquer um dos casos, o terceiro não seria capaz de duplicar a primeira ação de Alice — assinar sua mensagem. Se um adversário assina a mensagem de alguma maneira, isso irá alterá-la de alguma forma, o resultado quando Bob desfaz a assinatura produzirá lixo. (Tente!) Como Bob recebeu uma palavra legítima, devidamente capitalizada, pode confiar que a mensagem que obteve é a mesma que foi assinada por Alice. Na prática, se Alice envia centenas de palavras em sua mensagem, a probabilidade de obter um texto coerente a partir da mensagem adulterada, é astronomicamente pequena.

O que foi mostrado?

1. Alice pode enviar mensagens que somente Bob possa ler.

2. Bob pode receber mensagens secretas de qualquer um.

3. Alice pode assinar mensagens, de maneira que Bob sabe que genuinamente vieram de Alice.

Claramente, sem fazer novas chaves, podemos trocar os papéis de Alice e Bob. E se Carol criar um par de chaves, ela pode se comunicar tanto com Alice como com Bob da mesma forma.

Se você deseja usar encriptação RSA de chave pública seriamente, investigue o software GNU Privacy Guard, mais conhecido como GPG, que está livremente disponível em www.gnupg.org/¹. Notemos que só tem sentido usar programas de encriptação que permitam conhecer o código fonte.