Questões Comentadas - Segurança
(CESPE 2008 TST) 116 O criptossistema RSA é seguro caso o problema da fatoração de números inteiros seja intratável, ou seja, não exista um algoritmo de fatoração de tempo polinomial.
Gabarito: E
(CESPE - CGAAC 2005)117 A segurança do algoritmo RSA reside no fato de que não são
conhecidos algoritmos suficientemente rápidos de fatoração de números inteiros.
Gabarito:C
Comentários:
Resumo RSA
_______________________________________________
Encaminhar uma mensagem de forma segura é uma preocupação que remonta aos primeiros estrategistas que se têm notícia, na Grécia Antiga.
O algoritmo RSA
Um dos algoritmos mais seguros de encriptação de informações atuais originou-se dos estudos de Ronald Rivest, Adi Shamir e Leonard Adleman, um trio de Matemáticos brilhantes que mudaram a história da Criptografia.
O princípio do algoritmo é construir chaves públicas e privadas utilizando números primos.
Uma chave é uma informação restrita que controla toda a operação dos algoritmos de criptografia. No processo de codificação uma chave é quem dita a transformação do texto puro (original) em um texto criptografado.
Chave Privada
É uma informação pessoal que permanece em posse da pessoa - não publicável.
Chave Pública
Informação associada a uma pessoa que é distribuída a todos.
Uma analogia amplamente conhecida no meio acadêmico é a transmissão de mensagens entre Alice e Bob.
Alice e Bob são personagens fictícios que precisam trocar mensagens seguras sem interceptação. O algoritmo RSA permite essa troca segura de mensagens pela utilização de chaves públicas e privadas:
Alice cria seu par de chaves (uma pública e outra privada) e envia sua chave pública para todos, inclusive Bob;
Bob escreve sua mensagem para Alice. Após escrita, Bob faz a cifragem do texto final com a chave pública de Alice, gerando um texto criptografado;
Alice recebe o texto criptografado de Bob e faz a decifragem utilizando a sua chave privada.
O procedimento é realizado com sucesso porque somente a chave privada de Alice é capaz de decifrar um texto criptografado com a sua chave pública.
É importante destacar que se aplicarmos a chave pública de Alice sobre o texto critografado não teremos a mensagem original de Bob. Dessa forma, mesmo que a mensagem seja interceptada é impossível decifrá-la sem a chave privada de Alice.
Funcionamento
Conforme mencionado, o algoritmo RSA é baseado na construção de chaves públicas e privadas utilizando números primos. Inicialmente devem ser escolhidos dois números primos quaisquer P e Q. Quanto maior o número escolhido mais seguro será o algoritmo.
A título de exemplificação, serão escolhidos números primos pequenos, para permitir um acompanhamento de todo o processo de cifragem e decifragem.
P = 17
Q = 11
A seguir são calculados dois novos números N e Z de acordo com os números P e Q escolhidos:
N = P * Q
Z = (P - 1) * (Q - 1)
No caso obtêm-se como resultado:
N = 17 * 11 = 187
Z = 16 * 10 = 160
Agora define-se um número D que tenha a propriedade de ser primo em relação à Z. No caso, opta-se pela escolha:
D = 7
De posse desses números começa o processo de criação das chaves públicas e privadas. É necessário encontrar um número E que satisfaça a seguinte propriedade:
(E * D) mod Z = 1
Se forem feitos os testes com 1, 2, 3... teremos:
E = 1 => (1 * 7) mod 160 = 7
E = 2 => (2 * 7) mod 160 = 14
E = 3 => (3 * 7) mod 160 = 21
...
E = 23 => (23 * 7) mod 160 = 1
...
E = 183 => (183 * 7) mod 160 = 1
...
E = 343 => (343 * 7) mod 160 = 1
...
E = 503 => (503 * 7) mod 160 = 1
...
Logo até o momento os números 23, 183, 343, 503 satisfazem a propriedade indicada.
Para efeito de simplificação de cálculos, será tomado como referência:
E = 23.
Com esse processo definem-se as chaves de encriptação e desencriptação.
para encriptar: utilizar E e N - esse par de números será utilizado como chave pública.
para desencriptar: utilizar D e N - esse par de números utilizado como chave privada.
As equações são:
TEXTO CRIPTOGRAFADO = (TEXTO ORIGINAL ^ E) mod N
TEXTO ORIGINAL = (TEXTO CRIPTOGRAFADO ^ D) mod N
Caso prático para o exemplo
Seja a necessidade de se encaminhar uma mensagem bem curta de forma criptografada, como o número 4 por exemplo, tendo por base as chaves aqui estabelecidas.
Para criptografar:
TEXTO ORIGINAL = 4
TEXTO CRIPTOGRAFADO = (4 ^ 23) mod 39
TEXTO CRIPTOGRAFADO = 70.368.744.177.664 mod 39
TEXTO CRIPTOGRAFADO = 64
Para desencriptar:
TEXTO RECEBIDO = 64
TEXTO ORIGINAL = (64 ^ 7) mod 39
TEXTO ORIGINAL = 4.398.046.511.104 mod 39
TEXTO ORIGINAL = 4
A questão das escolhas dos números primos envolvidos é fundamental para o algoritmo. Por essa razão escolhem-se números primos gigantescos para garantir que a chave seja inquebrável.
Assim como o exemplo apresentado, existem outras combinações que podem ser feitas rapidamente para confirmação, sem que se exija uma aplicação especial para os cálculos envolvidos.
P Q D E
11 17 7 23
5 7 11 35
3 13 7 31
3 13 7 7
3 5 17 9
A segurança do RSA é baseada em dois problemas:
1) Fatorar um inteiro grande. Se resolvermos esse problema podemos encontrar a chave privada e então decifrar qualquer mensagem. Esse é o problema mais falado e conhecido. Não foi encontrado nenhum algoritmo de tempo polinomial para resolver esse problema, mas ainda não há prova de que ele não exista. Porém, mesmo que se prove que esse algoritmo não exista, ainda há outro problema em que a segurança do RSA é baseada:
2) Inverter a função do RSA. Se esse problema for resolvido, não é preciso conhecer a chave privada para decifrar uma mensagem. Explicando: Para CIFRAR uma mensagem com o RSA fazemos: E(M) = C = M^e mod n; onde C é a mensagem cifrada, M é a mensagem clara e o par (e,n) é a chave pública. Se conseguirmos achar a inversa da função E(M), podemos desencriptar a mensagem sem ter a chave privada.
Método pra inverter a função: Eu consigo achar M sem ter a chave privada da seguinte maneira, com força bruta: Eu sou o atacante, e conheço a mensagem cifrada C, e a chave pública (e,n), então eu testo todos os M possíveis até que M^e mod n = C; Porém, força bruta é inviável se n for suficientemente grande.
Não existe método eficiente para achar a inversa de E, porém também não provaram que ele não exista.
Então, mesmo que provem que não é possível fatorar inteiros em tempo polinomial, o RSA só vai ser seguro mesmo se não houver como inverter a função de cifragem. Por isso a questão está errada.
(CESPE TST 2008) 116 - Na verdade a intratabilidade da fatoração em tempo polinomial não garante a segurança do RSA. Para que ele seja seguro existe uma outra condição: "Ainda que se possua o texto criptografado e a hash, não se pode alcançar o texto original". Quem matar esse problema, mata o RSA mesmo sem possuir um algoritmo que fatore em tempo polinomial.
(CESPE - CGAAC 2005)117 Um dos fatores da segurança do algoritmo RSA reside no fato de que não são conhecidos algoritmos suficientemente rápidos de fatoração de números inteiros.
Gabarito: E
(CESPE - CGAAC 2005)117 A segurança do algoritmo RSA reside no fato de que não são
conhecidos algoritmos suficientemente rápidos de fatoração de números inteiros.
Gabarito:C
Comentários:
Resumo RSA
_______________________________________________
Encaminhar uma mensagem de forma segura é uma preocupação que remonta aos primeiros estrategistas que se têm notícia, na Grécia Antiga.
O algoritmo RSA
Um dos algoritmos mais seguros de encriptação de informações atuais originou-se dos estudos de Ronald Rivest, Adi Shamir e Leonard Adleman, um trio de Matemáticos brilhantes que mudaram a história da Criptografia.
O princípio do algoritmo é construir chaves públicas e privadas utilizando números primos.
Uma chave é uma informação restrita que controla toda a operação dos algoritmos de criptografia. No processo de codificação uma chave é quem dita a transformação do texto puro (original) em um texto criptografado.
Chave Privada
É uma informação pessoal que permanece em posse da pessoa - não publicável.
Chave Pública
Informação associada a uma pessoa que é distribuída a todos.
Uma analogia amplamente conhecida no meio acadêmico é a transmissão de mensagens entre Alice e Bob.
Alice e Bob são personagens fictícios que precisam trocar mensagens seguras sem interceptação. O algoritmo RSA permite essa troca segura de mensagens pela utilização de chaves públicas e privadas:
Alice cria seu par de chaves (uma pública e outra privada) e envia sua chave pública para todos, inclusive Bob;
Bob escreve sua mensagem para Alice. Após escrita, Bob faz a cifragem do texto final com a chave pública de Alice, gerando um texto criptografado;
Alice recebe o texto criptografado de Bob e faz a decifragem utilizando a sua chave privada.
O procedimento é realizado com sucesso porque somente a chave privada de Alice é capaz de decifrar um texto criptografado com a sua chave pública.
É importante destacar que se aplicarmos a chave pública de Alice sobre o texto critografado não teremos a mensagem original de Bob. Dessa forma, mesmo que a mensagem seja interceptada é impossível decifrá-la sem a chave privada de Alice.
Funcionamento
Conforme mencionado, o algoritmo RSA é baseado na construção de chaves públicas e privadas utilizando números primos. Inicialmente devem ser escolhidos dois números primos quaisquer P e Q. Quanto maior o número escolhido mais seguro será o algoritmo.
A título de exemplificação, serão escolhidos números primos pequenos, para permitir um acompanhamento de todo o processo de cifragem e decifragem.
P = 17
Q = 11
A seguir são calculados dois novos números N e Z de acordo com os números P e Q escolhidos:
N = P * Q
Z = (P - 1) * (Q - 1)
No caso obtêm-se como resultado:
N = 17 * 11 = 187
Z = 16 * 10 = 160
Agora define-se um número D que tenha a propriedade de ser primo em relação à Z. No caso, opta-se pela escolha:
D = 7
De posse desses números começa o processo de criação das chaves públicas e privadas. É necessário encontrar um número E que satisfaça a seguinte propriedade:
(E * D) mod Z = 1
Se forem feitos os testes com 1, 2, 3... teremos:
E = 1 => (1 * 7) mod 160 = 7
E = 2 => (2 * 7) mod 160 = 14
E = 3 => (3 * 7) mod 160 = 21
...
E = 23 => (23 * 7) mod 160 = 1
...
E = 183 => (183 * 7) mod 160 = 1
...
E = 343 => (343 * 7) mod 160 = 1
...
E = 503 => (503 * 7) mod 160 = 1
...
Logo até o momento os números 23, 183, 343, 503 satisfazem a propriedade indicada.
Para efeito de simplificação de cálculos, será tomado como referência:
E = 23.
Com esse processo definem-se as chaves de encriptação e desencriptação.
para encriptar: utilizar E e N - esse par de números será utilizado como chave pública.
para desencriptar: utilizar D e N - esse par de números utilizado como chave privada.
As equações são:
TEXTO CRIPTOGRAFADO = (TEXTO ORIGINAL ^ E) mod N
TEXTO ORIGINAL = (TEXTO CRIPTOGRAFADO ^ D) mod N
Caso prático para o exemplo
Seja a necessidade de se encaminhar uma mensagem bem curta de forma criptografada, como o número 4 por exemplo, tendo por base as chaves aqui estabelecidas.
Para criptografar:
TEXTO ORIGINAL = 4
TEXTO CRIPTOGRAFADO = (4 ^ 23) mod 39
TEXTO CRIPTOGRAFADO = 70.368.744.177.664 mod 39
TEXTO CRIPTOGRAFADO = 64
Para desencriptar:
TEXTO RECEBIDO = 64
TEXTO ORIGINAL = (64 ^ 7) mod 39
TEXTO ORIGINAL = 4.398.046.511.104 mod 39
TEXTO ORIGINAL = 4
A questão das escolhas dos números primos envolvidos é fundamental para o algoritmo. Por essa razão escolhem-se números primos gigantescos para garantir que a chave seja inquebrável.
Assim como o exemplo apresentado, existem outras combinações que podem ser feitas rapidamente para confirmação, sem que se exija uma aplicação especial para os cálculos envolvidos.
P Q D E
11 17 7 23
5 7 11 35
3 13 7 31
3 13 7 7
3 5 17 9
A segurança do RSA é baseada em dois problemas:
1) Fatorar um inteiro grande. Se resolvermos esse problema podemos encontrar a chave privada e então decifrar qualquer mensagem. Esse é o problema mais falado e conhecido. Não foi encontrado nenhum algoritmo de tempo polinomial para resolver esse problema, mas ainda não há prova de que ele não exista. Porém, mesmo que se prove que esse algoritmo não exista, ainda há outro problema em que a segurança do RSA é baseada:
2) Inverter a função do RSA. Se esse problema for resolvido, não é preciso conhecer a chave privada para decifrar uma mensagem. Explicando: Para CIFRAR uma mensagem com o RSA fazemos: E(M) = C = M^e mod n; onde C é a mensagem cifrada, M é a mensagem clara e o par (e,n) é a chave pública. Se conseguirmos achar a inversa da função E(M), podemos desencriptar a mensagem sem ter a chave privada.
Método pra inverter a função: Eu consigo achar M sem ter a chave privada da seguinte maneira, com força bruta: Eu sou o atacante, e conheço a mensagem cifrada C, e a chave pública (e,n), então eu testo todos os M possíveis até que M^e mod n = C; Porém, força bruta é inviável se n for suficientemente grande.
Não existe método eficiente para achar a inversa de E, porém também não provaram que ele não exista.
Então, mesmo que provem que não é possível fatorar inteiros em tempo polinomial, o RSA só vai ser seguro mesmo se não houver como inverter a função de cifragem. Por isso a questão está errada.
(CESPE TST 2008) 116 - Na verdade a intratabilidade da fatoração em tempo polinomial não garante a segurança do RSA. Para que ele seja seguro existe uma outra condição: "Ainda que se possua o texto criptografado e a hash, não se pode alcançar o texto original". Quem matar esse problema, mata o RSA mesmo sem possuir um algoritmo que fatore em tempo polinomial.
(CESPE - CGAAC 2005)117 Um dos fatores da segurança do algoritmo RSA reside no fato de que não são conhecidos algoritmos suficientemente rápidos de fatoração de números inteiros.
Comentários