Algoritmo RSA

Alice dá sua chave pública ( n ndisplaystyle n,} & e e {\i1}) a Bob e mantém sua chave privada em segredo. Bob quer enviar a mensagem M para Alice.

Primeiro, ele transforma M em um número m menor do que n n, usando um protocolo reversível acordado, conhecido como um esquema de estofamento. Em seguida, ele calcula o texto cifrado ao qual corresponde o estilo de exibição c:

c = m e mod n {\i1}displaystyle c=m^{e}mod {n}}

Isto pode ser feito rapidamente usando o método de exponenciação por quadratura. Bob então envia c {\i1}displaystyle c{\i} para Alice.

Alice pode recuperar o meu estilo de jogo m, usando sua chave privada d, no seguinte procedimento:

m = c d mod n {\i1}m=c^{d}{\i}{bmod {n}}}

Dado o meu estilo de apresentação, ela pode recuperar os números primos originais distintos, aplicando o teorema do restante chinês a esses dois congruentes rendimentos

m e d ≡ m mod p q {\i1}displaystyle m^{ed}}equiv m{\i}bmod {pq}}} .

Assim,

c d ≡ m mod n ^{displaystyle c^{d}}equiv m mbmod {n}} .

Um exemplo de trabalho

Aqui está um exemplo de criptografia e decodificação da RSA. Os parâmetros usados aqui são artificialmente pequenos, mas você também pode usar o OpenSSL para gerar e examinar um par de chaves real.

1. Escolha dois números primos aleatórios.
2.  p = 61 {\i1} e q = 53 ; {\i1}estilo de exibição q=53; {\i1} Compute n = p q {\i1}displaystyle n=pq,}
3.  n = 61 ∗ 53 = 3233 {\i1}displaystyle n=61*53=3233}
4. Calcular o totient ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\i (n)=(p-1)(q-1)}
5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\i (n)=(61-1)(53-1)=3120}
6. Escolha e > 1 {\i1} coprime até 3120
7.  e = 17 {\a10} e = 17 {\a10}
8. Escolher d d ddisplaystyle d,} para satisfazer d e mod ϕ ( n ) ≡ 1 displaystyle de{\i1}bmod {\i(n)}equiv 1,}
9.  d = 2753 {\i1}displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\i1}displaystyle 17*2753=46801=1+15*3120} .

A chave pública é ( n = 3233 {\\displaystyle n=3233} , e = 17 {\displaystyle e=17} ) Para uma mensagem almofadada m {\i1}, a função de encriptação c = m e mod n {\i1}c=m^{e}{\i1}{\i1}bmod {n}} torna-se a função de encriptação c = m e mod n {\i}displaystyle c=m^{e}{\i}{\i1}:

c = m 17 mod 3 233 c=m^{17}{\bmod {3}}233,}

A chave privada é ( n = 3233 {\\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ) A função de decriptação m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} torna-se:

m = c 2753 mod 3 233 {\i1}displaystyle m=c^{2753}{\i1}bmod {3}233,}

Por exemplo, para encriptar m = 123 {\displaystyle m=123} calculamos

c = 123 17 mod 3 233 = 855 c=123^{17}{\bmod {3}}233=855}

Para decifrar c = 855 {\displaystyle c=855} calculamos

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123}

Ambos os cálculos podem ser computados eficientemente usando o algoritmo de quadrado e múltiplo para exponenciação modular [pt].

A RSA pode ser facilmente derivada usando o teorema de Euler e a função totient do Euler.

Começando com o teorema de Euler,

m ϕ ( n ) ≡ 1 ( mod n ) {\i1}displaystyle m^{\i (n)}equiv 1{\i1}displaystyle m^{\i (n){\i}

devemos mostrar que decifrar uma mensagem criptografada, com a chave correta, dará a mensagem original. Dada uma mensagem m almofadada, o texto cifrado c, é calculado por

c ≡ m e ( mod n ) c=equiv m ^{e}{npmod {n}}}

Substituindo no algoritmo de decifração, temos

c d ≡ ( m e ) d ≡ m e d ( mod n ) c^{displaystyle c^{d}{displaystyle c^{d}(m^e})^equiv (m^d})^equiv m^{ed}{\i}{\i}

Queremos mostrar este valor também é congruente com m. Os valores de e e e d foram escolhidos para satificar,

e d ≡ 1 ( mod ϕ ( n ) ) eequiv 1pmod (n)phi (n)}}

Ou seja, existe algum k inteiro, de tal forma que

e d = k × ϕ ( n ) + 1 {\i1}displaystyle ed=k=k=times \phi (n)+1}

Agora nós substituímos na mensagem criptografada e descriptografada,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\i1}displaystyle {\i}m^{ed}&\eqüiv mphi (n)+1}&equiv m vezes mphi (n)}equiv m vezes mphi (n)}equiv m vezes esquerda(mphi (n)}direita){k

Nós aplicamos o teorema de Euler e obtemos o resultado.

m × ( 1 ) k ≡ m ( mod n ) {\i1}mmmodalidades (1)^{k}}equiv m{\i}mod {n}}

Quando usado na prática, o RSA deve ser combinado com algum tipo de esquema de estofamento, de modo que nenhum valor de M resulte em textos criptografados inseguros. A RSA usada sem estofamento pode ter alguns problemas:

• Os valores m = 0 ou m = 1 produzem sempre textos cifrados iguais a 0 ou 1 respectivamente, devido às propriedades de exponenciação.
• Ao criptografar com pequenos expoentes de criptografia (por exemplo, e = 3) e pequenos valores do m, o resultado (não-modular) do m e ^{e}} pode ser estritamente menor que o módulo n. Neste caso, os textos criptográficos podem ser facilmente descriptografados tomando a raiz eth do texto criptográfico sem levar em conta o módulo.
• A criptografia RSA é um algoritmo de criptografia determinista. Ele não tem componente aleatório. Portanto, um atacante pode lançar com sucesso um ataque de texto plano escolhido contra o criptosistema. Eles podem fazer um dicionário criptografando prováveis plaintextos sob a chave pública e armazenando os textos criptográficos resultantes. O atacante pode então observar o canal de comunicação. Assim que eles virem os textos cifrados que correspondem aos do seu dicionário, os atacantes podem então usar este dicionário para aprender o conteúdo da mensagem.

Na prática, os dois primeiros problemas podem surgir quando mensagens ASCII curtas são enviadas. Em tais mensagens, m pode ser a concatenação de um ou mais caracteres codificados em ASCII. Uma mensagem composta de um único caractere ASCII NUL (cujo valor numérico é 0) seria codificada como m = 0, o que produz um texto cifrado de 0, não importando quais valores de e e e N são usados. Da mesma forma, um único caractere ASCII SOH (cujo valor numérico é 1) produziria sempre um texto cifrado de 1. Para sistemas que utilizam convencionalmente pequenos valores de e, como 3, todas as mensagens de um único caractere ASCII codificadas usando este esquema seriam inseguras, uma vez que o maior m teria um valor de 255, e 2553 é menor do que qualquer módulo razoável. Tais plaintexts poderiam ser recuperados simplesmente tomando a raiz cúbica do texto cifrado.

Para evitar estes problemas, as implementações práticas de RSA normalmente incorporam alguma forma de estofamento estruturado e randomizado no valor m antes de codificá-lo. Este acolchoamento garante que m não caia na faixa de plaintexto inseguro, e que uma determinada mensagem, uma vez acolchoada, será criptografada em um de um grande número de diferentes possíveis criptografados. Esta última propriedade pode aumentar o custo de um ataque de dicionário para além das capacidades de um atacante razoável.

Padrões como o PKCS foram cuidadosamente projetados para armazenar com segurança as mensagens antes da criptografia RSA. Como estes esquemas acolhem o texto em quadrado m com algum número de bits adicionais, o tamanho da mensagem M não acolchoada deve ser um pouco menor. Os esquemas de preenchimento RSA devem ser cuidadosamente projetados de forma a evitar ataques sofisticados. Isto pode ser facilitado por uma estrutura de mensagem previsível. As primeiras versões do padrão PKCS usavam construções ad-hoc, que mais tarde foram consideradas vulneráveis a um prático ataque de texto criptografado escolhido adaptável. As construções modernas utilizam técnicas seguras como o Padding de Criptografia Assimétrica Ideal (OAEP) para proteger as mensagens enquanto previne estes ataques. O padrão PKCS também tem esquemas de processamento projetados para fornecer segurança adicional para assinaturas RSA, por exemplo, o Probabilistic Signature Scheme for RSA (RSA-PSS).

Suponha que Alice use a chave pública de Bob para enviar-lhe uma mensagem criptografada. Na mensagem, ela pode afirmar ser Alice, mas Bob não tem como verificar se a mensagem era realmente de Alice, já que qualquer um pode usar a chave pública de Bob para lhe enviar mensagens criptografadas. Assim, a fim de verificar a origem de uma mensagem, a RSA também pode ser usada para assinar uma mensagem.

Suponha que a Alice deseje enviar uma mensagem assinada para Bob. Ela produz um valor hash da mensagem, eleva-a ao poder de d mod n (como quando decifrando uma mensagem), e a anexa como uma "assinatura" à mensagem. Quando Bob recebe a mensagem assinada, ele eleva a assinatura ao poder de e mod n (assim como ao encriptar uma mensagem), e compara o valor de hash resultante com o valor de hash real da mensagem. Se os dois concordarem, ele sabe que o autor da mensagem estava de posse da chave secreta de Alice, e que a mensagem não foi adulterada desde então.

Observe que esquemas de preenchimento seguro como o RSA-PSS são tão essenciais para a segurança da assinatura de mensagens quanto para a criptografia de mensagens, e que a mesma chave nunca deve ser usada tanto para fins de criptografia quanto de assinatura.