A criptografia de chave pública ou criptografia assimétrica é um método de criptografia que utiliza um par de chaves: uma chave pública e uma chave privada. A chave pública é distribuída livremente para todos os correspondentes via e-mail ou outras formas, enquanto a chave privada deve ser conhecida apenas pelo seu dono.

Num algoritmo de criptografia assimétrica, uma mensagem cifrada com a chave pública pode somente ser decifrada pela sua chave privada correspondente.

Os algoritmos de chave pública podem ser utilizados para autenticidade e confidencialidade:

• Confidencialidade: A chave pública é usada para cifrar mensagens, com isso apenas o dono da pode decifrá-la.chave privada
• Autenticidade: A chave privada é usada para cifrar mensagens, com isso garante-se que apenas o dono da chave privada poderia ter cifrado a mensagem que foi decifrada com a 'chave pública', e que a mensagem não foi forjada.

Sistemas de criptografia de chave pública

Os algoritmos assimétricos contam com uma chave para criptografia e uma chave diferente, porém relacionada, para decriptografia. Esses algoritmos têm a seguinte característica importante:

• É computacionalmente inviável determinar a chave de decriptografia dado apenas o conhecimento

do algoritmo de criptografia e da chave de criptografia.

• Além disso, alguns algoritmos, como o RSA, também exibem a seguinte característica:
• Qualquer uma das duas chaves relacionadas pode ser usada para criptografia, com a outra usada

para a decriptografia.

Um esquema de criptografia de chave pública possui seis ingredientes:

• Texto claro: essa é a mensagem ou dados legíveis que são alimentados no algoritmo como

entrada.

• Algoritmo de criptografia: o algoritmo de criptografia realiza várias transformações no texto claro.

• Chaves pública e privada: esse é um par de chaves que foi selecionado de modo que,

se uma for usada para criptografia, a outra será usada para decriptografia. As transfor- mações exatas realizadas pelo algoritmo dependem da chave pública ou privada que é fornecida como entrada.

• Texto cifrado: essa é a mensagem codificada produzida como saída. Ela depende do texto claro e

da chave. Para uma determinada mensagem, duas chaves diferentes produzirão dois textos cifrados diferentes.

• Algoritmo de decriptografia: esse algoritmo aceita o texto cifrado e a chave correspondente

e produz o texto claro original.

As etapas essenciais são as seguintes:

• Cada usuário gera um par de chaves a ser usado para a criptografia e a decriptografia das mensagens.
• Cada usuário coloca uma das duas chaves em um registro público ou outro arquivo acessível.

Essa é a chave pública. A outra chave permanece privada, cada usuário mantém um conjunto de chaves públicas obtidas de outros usuários.

• Se Bob deseja enviar uma mensagem confidencial para Alice, Bob criptografa a mensagem usando a chave pública de Alice.
• Quando Alice recebe a mensagem, ela a decriptografa usando sua chave privada. Nenhum outro destinatário pode decriptografar a mensagem, pois somente Alice conhece a sua chave privada.

Com essa técnica, todos os participantes têm acesso às chaves públicas, as chaves privadas são geradas localmente por cada participante e, portanto, nunca precisam ser distribuídas. Desde que a chave privada de um usuário permaneça protegida e secreta, a comunicação que chega está protegida. A qualquer momento, um sistema pode alterar sua chave privada e publicar a chave pública correspondente para substituir sua antiga chave pública.

Ideia inicial de criptografia de chave pública

Foi proposto um modelo de criptossistema chamado modelo de chave pública (Diffie e Hellman, 1978) em que cada usuário possui um par de chaves (S, P) sendo S a sua chave particular, secreta, e P a sua chave pública. As chaves S e P são relacionadas matematicamente de tal forma que:

• Se x denota um texto legível, e S() denota a aplicação da chave S, transforma x em S(x) =y então P(y) =x onde P() denota a aplicação da chave P, ou seja, S é a chave inversa da chave P onde, P(S(x)) =x;
• O cálculo do par de chaves (S, P) é computacionalmente fácil.
• É computacionalmente difícil calcular S a partir do conhecimento de P.
• Os cálculos de P() e S() são computacionalmente fáceis para quem conhece as chaves.
• É computacionalmente difícil calcular S() sem conhecer a chave S.

Estas possibilidades levam ao seguinte cenário:

• Cada usuário calcula o seu par de chaves (S, P) no seu computador.
• A chave S é guardada de forma segura no seu computador.
• A chave P é distribuída a todos de forma pública.

Complexidade de Algoritmo

Seja no comprimento de entrada para um algoritmo A. Um algoritmo A é de tempo polinomial se a função f(n) do tempo de execução no pior caso de A é tal que f(n) = O (n ) para um constante k. Um algoritmo A é de tempo exponencial se não existe constante k tal que f(n) = O (n ). Algoritmos de tempo polinomial são computacionalmente eficientes (ou viáveis ou fáceis), e os algoritmos de tempo exponencial são computacionalmente ineficientes (ou inviáveis ou difíceis). Diz-se que um problema é computacional inviável ou difícil se não se conhece qualquer algoritmo de tempo polinomial para resolvê-lo.

Programas para criptografia

• Gnupg
• Pgp
• RSA