IA012:2014 1S:Lista VI

De DCA-Wiki

IA012 A - Segurança em Comunicação de Dados

FEEC - UNICAMP

Lista de Exercícios VI

Sorteados: 1 e 15

(1) Woo e Lam propuseram um protocolo de chave pública para distribuição de chaves de sessão baseado em nonces e que não requer sincronização entre relógios. Logo em seguida, os próprios autores publicaram uma atualização do protocolo a qual incluia o identificador de A (IDA) nos passos 5 e 6. Esta alteração no protocolo visou protegê-lo contra algum ataque? Qual? Por quê?


(2) Para minimizar os riscos envolvidos no sistema de senhas tradicional do Unix, recomenda-se a substituição do arquivo público de senhas por um arquivo público contendo as chaves pública (Kpu) e privada (Kpr) de cada usuário. A chave Kpr estaria cifrada por DES utilizando a senha (S) do usuário. Quando o mesmo fornecesse a senha, a chave Kpr seria decifrada e ficaria pronta para uso. Neste caso pergunta-se:

  • (a) Como o sistema verifica que a senha S está correta?
  • (b) Como um invasor, que só conhece o novo arquivo público de senhas, tentaria entrar no sistema? Descreva todos os passos que ele seguiria.


(3) O sistema de senhas tradicional do Unix faz uso de 12 bits extras (conhecidos como sal).

  • Explique como o sal é gerado e usado.
  • Explique qual é a sua vantagem.
  • Dobrar o triplicar o número de bits do sal usado no esquema de senhas do Unix não aumenta significativamente a dificuldade de invasores em quebrar senhas (considerando que o invasor possui o arquivo de senhas). Por quê?
  • Explique os efeitos de se aumentar o número de bits do sal em um sistema com poucos usuários.
  • Explique os efeitos de se aumentar o número de bits do sal em um sistema com muitíssimos usuários.


(4) O Filtro de Bloom é considerado um método eficiente para verificação prévia de senhas ruins. Explique como é o seu funcionamento e quais as vantagens que o mesmo oferece em relação a outras abordagens com o mesmo objetivo, como as Cadeias de Markov, por exemplo.


(5) Resolva as seguintes questões relativas ao Filtro de Bloom.

  • (a) Mostre que, neste filtro, a probabilidade de bits zero na tabela hash é dado por z = (1 - k/N)D, onde k é o número de funções hash, N é o número de bits na tabela hash e D é o número de palavras no dicionário de senhas ruins.
  • (b) Mostre que a probabilidade de se ter alarmes falsos neste filtro (indicação de que uma senha está no dicionário quando na verdade não está) é dada por (1 - z)k.
  • (c) Mostre que a expressão do item (b) pode ser aproximada por (1 - e-kD/N)k.


(6) Para filtros de Bloom de ordem 2, 4, 8 e 16, determine as condições em que um filtro de ordem r tem melhor desempenho que um filtro de ordem 2r.


(7) Faça a expansão do Modelo de Markov apresentado nos slides do curso para ordem r=2, mostrando como ficam os parâmetros M = [m, A, T, r] e o grafo de transições. Cuide para que a soma de probabilidades de um determinado caso seja exatamente 1, como ocorre com cada linha de T apresentada nos slides. Em seguida, mostre exemplos de sequências de caracteres que seriam aceitas e rejeitadas pelo modelo. Dica: faça o grafo de transições com dois tipos de estados: o conjunto dos estados iniciais com r caracteres e o conjunto de estados finais com 1 caractere.


(8) Verifique se o número 341 satisfaz o Teorema de Fermat e avalie sua primalidade usando as ferramentas técnicas apresentadas em aula (Teoremas de Fermat e Euler).


(9) Utilize o teorema de Fermat para determinar o resto da divisão de 11123 por 7.


(10) Calcule φ(1991) e φ(1993) e discuta a diferença entre os dois valores.


(11) Demonstre que o conjunto de números primos é infinito.


(12) Usando-se diferentes valores aleatórios de a (1 < a < n – 1) pelo menos quantos testes de Miller-Rabin sobre um inteiro n precisam ser executados e retornar "inconclusivo" para que a taxa de erro resultante seja no máximo 2-100?

  • Nota: taxa de erro é a probabilidade de n não ser primo apesar do algoritmo de Miller-Rabin retornar repetidas vezes "inconclusivo" sobre ele.


(13) Demonstre que, se n inteiro e n > 1, então -1 mod n = n – 1 .


(14) Em média quantos números escolhidos aleatoriamente se espera que precisem passar por um teste de primalidade para se selecionar um número primo aleatório de 1024 bits?

  • Dica: você vai precisar de uma “big number calculator“. Procure por uma no Google.

(15) Calcule o inverso multiplicativo de 2 em GF(11) usando o teorema de Fermat.

Ferramentas pessoais