PCF-3

Questões comentadas, artigos e notícias

Prova de 2002: Criptografia – Questão 48 (5 sentenças C/E)

Posted by papacharliefox3 em 27/03/2009

Salve!

Sabe o que é isso aí do lado? Clique na imagem para ampliar! Perceba o rotor numerado de 01 a 26 na parte superior, muito provavelmente utilizado nas rotinas de substituição do algoritmo de criptografia implementado (26 letras, [A-Z], saca?). Lembrei deste detalhe após tentar escrever um simples script publicado em um post anterior, que, na verdade, é a solução do problema 2.22 da página 39 do Stallings[1].

Os alemães bem que poderiam ter utilizado melhor este histórico objeto durante a guerra, não fosse a preguiça desatenção dos soldados ao mudar a configuração do ‘treco’ em intervalos grandes, sem contar as inúmeras mensagens que continham dados do tempo (que nem sempre mudava), ajudando os adversários na decodificação de mensagens (ataques estatísticos); apenas para citar alguns erros e fragilidades que ocorreram na época.

Ao final, Alan Turing (é ele mesmo, o da máquina), com ajuda – essencial – dos poloneses, quebrou o algoritmo utilizado por aquele maquinário utilizando-se do famoso Colossus. Bom, chega de blá-blá-blá (tem hífen isso?!). Os professores da UNB não querem saber se a gente curte história. Mas se mesmo assim você continua querendo ler mais sobre isso, recomendo os livros abaixo, disponíveis em cleartext no peer mais próximo. :)

Crypto de Stephen Levy
The Code Book de Simon Singh
The Codebreakers de David Kahn

Dando continuidade as 4 questões de Crypto da prova de 2002, segue mais uma.

48

1 Em um determinado sistema criptográfico, para cada mensagem possível m, existe apenas um criptograma possível, c, que será o resultado da cifração de m com determinada chave k. Não obstante, mensagens distintas podem resultar em um mesmo criptograma, se utilizadas chaves distintas.

2 Sistemas criptográficos são ditos simétricos ou de chave secreta quando a chave utilizada para cifrar é a mesma utilizada para decifrar. Sistemas assimétricos ou de chave pública utilizam chaves distintas para cifrar e decifrar. Algoritmos simétricos são geralmente mais eficientes computacionalmente que os assimétricos e por isso são preferidos para cifrar grandes massas de dados ou para operações online.

3 Diz-se que um sistema criptográfico tem segredo perfeito quando, dado um criptograma c, a incerteza que se tem em relação à mensagem m que foi cifrada é a mesma que se tinha antes de conhecer o criptograma. Uma condição necessária para que um sistema criptográfico tenha segredo perfeito é que o espaço de chaves seja pelo menos tão grande quanto o espaço de mensagens, ou seja, |K| • |M|.

4 O único sistema criptográfico matematicamente inviolável é o denominado sistema de chave única. Todos os demais sistemas, para utilização em condições reais de aplicação, são teoricamente violáveis, ou seja, dados recursos e tempo ilimitados e quantidade suficiente de criptograma gerado com uma mesma chave, é possível, sempre, determinar, de forma unívoca, a chave utilizada.

5 Uma técnica eficiente para tornar um sistema criptográfico mais forte é se utilizar um algoritmo de compressão de dados após a cifração.

Comentários:

1 A questão afirma o seguinte: utilizando-se de um mesmo algoritmo de criptografia, dado (M1 + K1 = C1) e  (M2 + K2 = C2), pode C1 ser igual a C2? Ou seja, pode existir (M1 + K1 = C2) ou (M2 + K2 = C1)? Relembrando do César:

K=1 M=A C=B

K=2 M=Z C=B

Captou? :)

2 Mais uma sem tirar nem pôr.

3 Perfeito. Para entender mais, leia sobre one-time-pad ou Vernan.

4 Acredito que ‘sistema de chave única’ seja o one-time-pad, assim, este tem o número de elementos do conjunto de chaves igual ao número do conjunto de mensagens, que é igual ao número de criptogramas; caso aplicado de forma correta. É o único caso de segurança perfeita. O restante deverá possuir número finito de chaves, logo, dispondo de tempo infinito qualquer algoritmo aqui será quebrável, teoricamente.

5 Comprimir dados não adiciona segurança, mas relaciona-se com a eficiência das rotinas do algoritmo.

Gabarito

48: C C C C E

Referências

[1] Criptografia e Segurança de Redes, Stallings

* Escrito ouvindo Eric Clapton – Clapton Chronicles (também disponível no peer mais próximo)

6 Respostas to “Prova de 2002: Criptografia – Questão 48 (5 sentenças C/E)”

  1. foxtrote said

    5) Uma técnica eficiente para tornar um sistema criptográfico mais forte é se utilizar um algoritmo de compressão de dados após a cifração.

    papacharliefox3, repare que a compressão de dados, após a cifração, não torna a criptografia mais forte. Entretanto, uma compressão de dados ANTES do processo criptográfico melhora a segurança da cifra, uma vez que padrões de comportamento do texto são perdidos com a compactação. Isso já foi questão de prova.

  2. papacharliefox3 said

    Fox, acredito que possa influenciar realmente. Tem esta questão aí? Se for entendimento do CESPE, eu marco C, sem dúvida. Mas ainda não me convenci, se puder passar uma referência, será mais uma que irei aprender. :)

    Concorda que se a mesma rotina de compactação é aplicada ao cleartext antes da encriptação, essa – também – irá gerar um padrão de comportamento? Ou seja, o padrão será propagado no resultado final idependente das rotinas (fixas) de compactação aplicadas.

    O algoritmo de criptografia em si é um dos desafios da criptoanálise. Eu exergo da seguinte forma: se o criptoanalista consegue quebrar o algoritmo, qual seria o esforço para quebrar um algoritmo de compactação?

  3. foxtrote said

    Vou postar este pacote de questões. Caiu na prova da Abin 2004, se não me engano.

  4. Felipeel said

    Vamos ver se isso ajuda: Stallings, pág. 23

    “Se a linguagem do texto claro for desconhecida, então a saída de texto claro pode não ser reconhecível. Além disso, a entrada pode ser abreviada ou compactada de alguma maneira, novamente dificultando o reconhecimento. A figura…mostra uma parte de um arquivo de texto compactada usando um algoritmo chamado ZIP. Se esse arquivo for então criptografado com uma cifra de substituição simples, então o texto claro não poderá ser reconhecido quando for descoberto na criptoanálise pela força bruta.”

    Ao meu ver, a COMPRESSÃO ANTES DA CRIPTOGRAFIA aumenta a segurança do processo. Pois esta compressão elimina os padrões do texto claro. Ou seja, todas as repetições são abreviadas. Se pegarmos dois textos cifrados, um foi utilizado esta técnica e outro não, talvez o texto compactado cifrado seja mais difícil de fazer a criptoanálise.

  5. Paulo de Tarso said

    concordo com o Felipeel!

  6. Logusmao said

    Eu sei que faz tempo que a discussão terminou, mas um detalhe: o item 1 está errado… Um exemplo claro é o criptosistema Rabin, no qual uma mensagem m cifrada pela equação c=m² (mod n), com n=p.q, sendo p=q=3 (mod 4). Ao decifrar o texto c, são geradas 4 soluções, sendo apenas uma a mensagem original. Ou seja, 4 mensagens geram o mesmo texto c, o que demonstra que o item 1 está errado.

    no item 4, a expressão “sistema de chave única” está mal colocada. One Time Pad é violável por ataques de tabela de frequência se o tamanho da chave é pequeno, o que não foi definido no item… Para que o One Time Pad seja inviolável, o tamanho da chave deve ser o tamanho da mensagem.

    No item 5, a compressão deve ocorre antes da cifração. Esse processo é utilizado por exemplo, no IPsec… A compactação após o texto já cifrado não melhora em nada a segurança, uma vez que os algoritmos de compactação são conhecidos.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

 
%d blogueiros gostam disto: