Grátis: Exercícios Ex. 65 – Quantas tentativas alguém deveria fazer para encontrar uma colisão em uma função de hashing resistente a colisões com saída de ... – Questões Respondidas

Psicologia Jurídica

Outros

Exercícios Ex. 65 – Quantas tentativas alguém deveria fazer para encontrar uma colisão em uma função de hashing resistente a colisões com saída de 256 bits, com probabilidade de sucesso maior ou igual que 3/4?

Testando o Conhecimento

ano passado

Testando o Conhecimento

ano passado

cripto

FMU

Respostas

Ed

ano passado

Para encontrar uma colisão em uma função de hashing resistente a colisões com saída de 256 bits e probabilidade de sucesso maior ou igual a 3/4, alguém deveria fazer aproximadamente 2^128 tentativas. Isso ocorre devido ao fato de que a probabilidade de encontrar uma colisão em uma função de hashing é de aproximadamente 1/2^128.

Essa resposta te ajudou?

0

0

left-side-bubbles-background

right-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

cripto

FMU

Mais perguntas desse material

Qual é a definição de função desprezível?

f : N→ R é desprezível se para todo polinômio p(·) existe um N tal que para todos os inteiros n > N , f(n) < 1 |p(n)| .
f(n) = 1/2n é desprezível, porque para qualquer polinômio p, haverá um N a partir do qual 1/2n < 1/p(n);
g(n) = 1/n^4+100 não é desprezível: seja h(n) = 1/n^5. Há algum N a partir do qual h(n) < 1/n^4.

Qual é a definição de distribuições computacionalmente indistinguíveis?

De acordo com a Definição 4.4, duas distribuições X e Y são computacionalmente indistinguíveis se a probabilidade de sucesso de T neste experimento for próxima de 1/2.
De acordo com a Definição 4.5, duas distribuições X e Y são computacionalmente indistinguíveis se a diferença entre a probabilidade de D(u) = 1 para X e Y for menor ou igual a uma função desprezível negl(n).
De acordo com a Definição 4.6, duas distribuições X e Y são computacionalmente indistinguíveis se para todo algoritmo polinomial D e n suficientemente grande, existe uma função desprezível negl(·) tal que a diferença entre as probabilidades de D(u) = 1 para X e Y seja menor ou igual a negl(n).

O que afirma o Teorema 4.35 (Insegurança de criptossistemas determinísticos) em relação a criptossistemas simétricos determinísticos? Como é proposta a solução para o problema apresentado?

a) Utilizar uma chave diferente a cada encriptação.
b) Inicializar G com uma semente secreta e bits adicionais escolhidos aleatoriamente.
c) Enviar o vetor de inicialização junto com o texto cifrado.
d) Decifrar utilizando G(k, iv)⊕ c.

O que é necessário para que a construção de Lai-Massey tenha a mesma garantia de segurança das redes de Feistel?

A) A permutação σ deve ser um ortomor�smo.
B) A permutação σ deve ser uma função pseudoaleatória.
C) A permutação σ deve ser uma permutação verdadeiramente aleatória.
D) A permutação σ deve ser uma permutação pseudoaleatória.

Qual é o problema do DES em relação ao tamanho de sua chave?

A) O tamanho da chave é muito pequeno.
B) O tamanho da chave é muito grande.
C) É possível percorrer o espaço de chaves em tempo aceitável.
D) A chave não é utilizada corretamente.

seguro, pode ser remediada usando um protocolo para que ambos usem um canal inseguro (aberto) para estabelecer uma chave privada a ser usada em suas comunicações, sem que outros tenham acesso à chave. A comunicação subsequente poderá se dar usando apenas esta chave, e o canal seguro estará, então, estabelecido. De�niremos segurança para protocolos de estabelecimento de chaves antes de apresentar o protocolo de Di�e e Hellman. Começamos com o experimento KE_EAV (�key establishment / eavesdropping�), que identi�ca a probabilidade com que o segredo (chave) comum pode ser capturado por um adversário. Experimento 9.1 (KE_EAV(Π,A, n)). 1. Duas entidades A e B, ambas conhecendo n, executam o protocolo Π. Todas as mensagens trocadas entre A e B são guardadas em uma listaM . Ambos devem calcular uma chave k (que não é incluída na lista M). 2. Um bit aleatório b é escolhido. Se b = 0, k′ é escolhida uniformemente ao acaso. Se b = 1, k′ = k. 3. A lista de mensagens M e a chave k′ são enviadas ao adversário A. 4. A envia um bit b′ 5. O resultado do experimento é um se b = b′ ou zero em caso contrário. � De�nição 9.2 (Segurança para protocolo de estabelecimento de chaves). Um protocolo de estabelecimento de chaves Π é seguro se para todo adversário polinomial A existe uma função desprezível negl tal que Pr[KE_EAV(Π,A, n) = 1] ≤ 1 2 + negl(n). � Esta noção de segurança é adequada a protocolos de estabelecimento de chaves: como há apenas dois atores e presumimos que há con�ança mútua, só temos que nos preocupar com a possibilidade de obtenção da chave por um adversário que não participa do protocolo. 9.3 Protocolo Di�e-Hellman para estabelecimento de chaves O protocolo de estabelecimento de chaves de Di�e e Hellman usa um algoritmo G que, dado um parâmetro n, retorna a descrição de um grupo cíclico G de ordem q tal que q tem n bits, e um gerador g de G. Construção 9.3 (Protocolo de Di�e e Hellman para estabelecimento de chaves). Dois participantes, A e B, estabelecem uma chave simétrica da seguinte maneira: • A usa G para obter (G, q, g) • A escolhe x ∈R Zq e calcula h1 = gx 9.3. PROTOCOLODIFFIE-HELLMAN PARA ESTABELECIMENTODE CHAVES153 • A envia (G, q, g, h1) para B • B escolhe y ∈R Zq e calcula h2 = gy. • B envia h2 para A e determina a chave secreta kB = hy1. • A recebe h2 e determina a chave secreta kA = hx2 . � Ao �nal da execução do protocolo, A como B tem chaves secretas kA e kB . Estas chaves são iguais, porque kA = hx2 = (gy)x = gxy kB = hy1 = (gx)y = gxy. É importante observar que o protocolo não especi�ca nada a respeito do grupo, exceto que q deve ter n bits. Com isso é possível usar diferentes grupos na construção prática do protocolo. Um exemplo é o ECDH (Elliptic Curve Di�e-Hellman), onde são usados pontos em uma curva elíptica. Um requisito evidente do Di�e-Hellman é que o problema do Logaritmo Discreto seja difícil � caso contrário qualquer um que observe as mensagens trocadas poderá inferir a chave. Este é, no entanto, apenas necessário. Podemos identi�car outro problema, relacionado ao logaritmo discreto, que captura a essência da di�culdade do protocolo. Este problema leva o mesmo nome do protocolo. De�nição 9.4 (Problema de Di�e-Hellman). Dados um grupo cíclico G e um gerador g gerados por um algoritmo G(1n), denotamos DHg(a, b) = gab. O problema Di�e-Hellman computacional (ou CDH, �Computational Di�e- Hellman�) consiste em calcular DHg(a, b) dados ga e gb escolhidos ao acaso em G. O problema Di�e-Hellman decisional (ou DDH, �Decisional Di�e-Hellman�) consiste em reconhecer se um elemento x foi escolhido ao acaso em G ou se é igual a DHg(a, b) para algum a e algum b gerados aleatoreamente. Dizemos que CDH e DDH são difíceis com relação a um algoritmo G se não houver algoritmo polinomial que os resolva quando os grupos são gerados por G. � Há algoritmos G para os quais não se conhece algoritmo e�ciente para resolver CDH ou DDH (mas não há tampouco prova de que não existam). O que demonstramos então é que o protocolo de Di�e-Hellman é seguro se o problema é difícil para um algoritmo G. Teorema 9.5. Se o problema Di�e-Hellman decisional é difícil para um algo- ritmo G, o protocolo Di�e-Hellman (Construção 9.3) é seguro de acordo com a De�nição 9.2 quando G é usado. Demonstração. Supomos que o grupo G usado no experimento 9.1 foi gerado por um algoritmo G. O bit b é escolhido ao acaso, então Pr[b = 0] = 1/2. Pr[KE_EAV(Π,A, n) = 1 ] = 1 2 Pr[KE_EAV(Π,A, n) = 1|b = 1 ] + 1 2 Pr[KE_EAV(Π,A, n) = 1|b = 0 ]. No experimento KE_EAV o adversário recebe k′, que pode ser um elemento ale- atório do grupo ou a chave. Assim, A pode ter, com igual probabilidade: • (G, q, g, h1, h2, g xy), ou • (G, q, g, h1, h2, k ′), sendo que k′ foi escolhida aleatoreamente. Distinguir entre ambos é exatamente resolver o problema Di�e-Hellman decisi- onal: Pr[KE_EAV(Π,A, n) = 1 ] = 1 2 Pr[KE_EAV(Π,A, n) = 1|b = 1 ] + 1 2 Pr[KE_EAV(Π,A, n) = 1|b = 0 ] = 1 2 Pr[A(G, q, g, gx, gy, gxy) = 1 ] + 1 2 Pr[A(G, q, g, gx, gy, gz) = 0 ] = 1 2 Pr[A(G, q, g, gx, gy, gxy) = 1 ] + 1 2 1− Pr [A(G, q, g, gx, gy, gz) = 1 ] = 1 2 Pr[A(G, q, g, gx, gy, gxy) = 1 ] + 1 2 1− Pr [A(G, q, g, gx, gy, gz) = 1 ] = 1 2 + 1 2 ( Pr[A(G, q, g, gx, gy, gxy) = 1 ] − Pr [A(G, q, g, gx, gy, gz) = 1 ]) ≤ 1 2 + 1 2 ∣∣∣Pr[A(G, q, g, gx, gy, gxy) = 1 ] − Pr [A(G, q, g, gx, gy, gz) = 1 ]∣∣∣. Como g é gerador de G, gz é distribuído uniformemente no grupo se z for uniformemente distribuído em Zq. Se o problema Di�e-Hellman decisional é difícil para G, então existe negl desprezível tal que∣∣∣Pr[A(G, q, g, gx, gy, gxy) = 1 ] − Pr [A(G, q, g, gx, gy, gz) = 1 ]∣∣∣ ≤ negl(n). Concluímos que Pr[KE_EAV(Π,A, n) = 1 ] ≤ 1 2 + 1 2 negl(n). � Note que esta demonstração parece ter um pequeno problema: quando b = 0, o adversário recebe um elemento aleatório do grupo G, e não uma cadeia alea- tória de bits. Para que a diferença �que clara, suponha que tenhamos escolhido o grupo Zq e que a ordem do grupo seja q = 257, que é representado por 100000001 em binário. Apenas um elemento do grupo tem o primeiro bit igual a um: 256 = 100000000. Este não é um problema com a demonstração, mas um fato a que o implementador deve dar atenção: não se pode usar números diretamente para representar elementos de G; ao invés disso deve

Queremos 1 < b < 200 coprimo com 200 = 2352, e escolhemos b = 7 (que não é divisível por 2 nem por 5, e portanto pertence a Z∗200). Assim, a = 7−1 (mod φ(N)) = 7−1 (mod 200) = 143. Temos então pk = (N, b) = (303, 7) sk = (N, a) = (303, 143) Para encriptar 53 (que pertence a Z∗303), fazemos Encpk(53) = 537 (mod 303) = 275. Para decriptar 37, Decsk(275) = 275143 (mod 303) = 53. Da mesma forma que identificamos a essência da dificuldade do protocolo Diffie-Hellman, também o faremos com o RSA, definindo o problema RSA. Definição 9.21. Seja N o produto de dois primos, ambos com n bits. Seja e > 0 tal que gcd(e,N) = 1 e x ∈ Z∗N. O problema RSA computacional consiste em calcular y = x1/e (mod N). Não se conhece qualquer algoritmo eficiente para resolver o problema RSA. Sabemos que o RSA deve ser pelo menos tão difícil quanto a fatoração de inteiros: se for possível fatorar N, basta então calcular φ(N) = (p − 1)(q − 1), calcular d = e−1 (mod φ(N)) e y = xd (mod N) (é importante observar que φ(N) e e−1 não são públicos, e devem ser calculados por um adversário que pretenda quebrar o RSA). Aspectos de segurança do RSA. Esta Seção descreve alguns ataques ao RSA. Estes ataques não caracterizam qualquer fraqueza do criptossistema, e somente são possíveis quando o RSA é usado de maneira ingênua (ou incorreta). Fatoração do módulo n em p, q. A fatoração do módulo em p e q deve ser mantida em segredo. Se um atacante obtiver estes dois números, ele pode usar o algoritmo estendido de Euclides para calcular o exponente de decriptação d. De acordo com a identidade de Bézout, existem X e Y tais que mdc (e, φ(n)) = eX + φ(n)Y 1 = eX + φ(n)Y (Identidade de Bézout) eX ≡ 1 (mod φ(n)) (def. de congruência) Evidentemente, X = d. O valor φ(n). O valor de φ(n) também deve ser mantido em segredo. Vemos o que um atacante poderá fazer tendo φ(n). φ(n) = (p− 1)(q − 1) φ(n) = pq − p− q + 1 φ(n) = (n+ 1)− (p+ q) (p+ q) = (n+ 1)− φ(n) q = (n+ 1)− φ(n)− p. Conseguimos uma descrição de q em função de n, φ(n) e p (que o atacante conhece). Observe que n = pq n = p [ (n+ 1)− φ(n)− p ] n = −p2 + p(n+ 1− φ(n)) Rearranjando, vemos que p é solução de uma equação do segundo grau, p2 − (n+ 1− φ(n))p+ n = 0, com a = 1, b = −(n+ 1− φ(n)) e c = n. Módulo comum. Suponha que ao distribuir chaves para um grupo de pessoas usemos sempre o mesmo módulo N: a i-ésima pessoa recebe (ai, N) e (bi, N). Como aibi ≡ 1 (mod φ(N)), qualquer uma destas pessoas pode fatorar N e consequentemente calcular aj a partir de bj. Ainda que se suponha que no grupo com estas chaves haja confiança mútua e que o fato de um conhecer as chaves privadas de todos os outros não seja um problema, o módulo comum permite que um adversário externo ao grupo decifre mensagens sem precisar de qualquer chave privada. Suponha que m é enviada a duas pessoas com chaves (b1, N) e (b2, N): c1 = mb1 (mod N) c2 = mb2 (mod N). Como b1 e b2 são co-primos com N, são também co-primos entre si, e existem x, y tais que xb1 +yb2 = 1, facilmente computáveis. Um adversário que conheça c1, c2 e N pode decifrar a mensagem porque cx1c y 2 = mxb1myb2 = mxb1+yb2 = m1 = m (mod N). b e m pequenos. Se b usado na chave pública e m são pequenos um adversário pode decriptar m. Por exemplo, se b = 5 e m < N1/5, não há redução modular na encriptação porque m5 < N. Observando c = m5 (mod N), e sabendo que b e m são pequenos, um adversário pode calcular c1/5 em Z (sem aritmética modular) e obter m. Versão segura do RSA: OAEP. Da mesma forma que tornamos cifras de fluxo seguras inserindo nelas elementos de aleatoriedade, tornaremos o RSA seguro modificando-o para que passe a ser um algoritmo probabilístico. A modificação que fazemos é adicionar uma cadeia de bits aleatórios à mensagem antes de encriptá-la. Descrevemos a seguir o OAEP (Optimal Asymmetric Encryption Padding). Se trocarmos o algoritmo Enc da Construção 9.19 pelo algoritmo Enc′ a seguir obteremos uma versão do RSA com segurança IND-CCA-2. O algoritmo Enc′ usa duas funções de hash, G e H. Zeros são adicionados à mensagem m para que tenha tamanho fixo; r é escolhido aleatoriamente. Enc′pk(m) = Encpk(m⊕G(r)||r ⊕H(m⊕G(r))) Observe que o algoritmo original é usado pelo novo. A próxima figura ilustra o algoritmo e deixa claro também que sua estrutura é a de uma rede de Feistel, para que possamos calcular a inversa ao decriptar a mensagem. Notamos também que a função G deve ser usada de forma a expandir os k bits de r para n bits, e que H deve comprimir n bits em k bits. A segurança IND-CCA-2 do esquema depende de tratarmos as duas funções de hash como oráculos aleatórios. Informalmente, podemos fazer algumas observações: se as duas funções de hashing G e H tem saída indistinguível de bits aleatórios e resistência de segunda pré-imagem, então m ⊕ G(r) deveria ter o mesmo efeito que o one-time pad. Mas usar apenas este valor (m⊕G(r)) não daria certo, porque não seria possível decriptar. Por isso usamos também a segunda função H. Goldwasser-Micali. O criptossistema de Goldwasser-Micali fundamenta-se na dificuldade do problema do resíduo quadrático. Teorema 9.22. Seja p primo. Se y é resíduo quadrático módulo p, então y tem exatamente duas raízes quadradas módulo p. Demonstração. Seja x tal que (±x)2 = y. Suponha que x ≡ −x (mod p). Teríamos 2x ≡ 0 (mod p), e p|2x. Como p é primo, teríamos que p|2 ou p|x. Mas p > 2 e p > x, e portanto x ≠ −x (mod p). Consequentemente y deve ter necessariamente duas raízes quadradas distintas módulo p. Teorema 9.23. Seja n = pq, com p e q primos. Então y é resíduo quadrático módulo n se e somente se y (mod p) é resíduo quadrático módulo p e y (mod q) é resíduo quadrático módulo q. Demonstração. O resultado segue imediatamente do Teorema B.16. Teorema 9.24. Seja n = pq, com p e q primos. Se y é resíduo quadrático módulo n, então y tem exatamente quatro raízes quadradas módulo n. Demonstração. Sejam a, b as raízes quadradas de y módulo p, e c, d as raízes quadradas de y módulo q. Pelo Teorema B.16, temos que y (mod p) ≡ y (mod q) ≡ y (mod pq). As raízes de y módulo p devem ser distintas das raízes de y módulo q, porque p e q são primos. Definição 9.25. O conjunto J+ n cont

Qual é a construção do esquema de assinaturas RSA apresentado no texto?

Gen (o mesmo do criptossistema RSA) gera pk = (b,N) e sk = (a,N).
Signsk(m) = ma (mod N).
Vrfpk(m,σ) = 1 se e somente se m = σb (mod N).
Todas as alternativas anteriores estão corretas.

Veri�camos agora o efeito desta medida nos ataques descritos. Fraude #1: o adversário precisaria computar m′ = σb (mod N) e depois tentar encontrar m tal que H(m) = m′. Se a função de hashing H for difícil de inverter, a di�culdade do ataque será a mesma; Fraude #2: para obter 1 nalgum dos experimentos que descrevemos, o adversário precisaria encontrar três mensagensm,m1,m2 tais queH(m) = H(m1)H(m2) (mod N). Este ataque também deve ser difícil se H for difícil de inverter.