Grátis: ação de N deve permitir decriptar a mensagem. 3. Alice envia N, c para Bob. 4. Bob escolhe x ∈R Z∗N e envia y = x2 (mod N) para Alice. 5. Alice ca... – Questões Respondidas

Ao vivo

Psicologia Jurídica

Outros

ação de N deve permitir decriptar a mensagem.

3. Alice envia N, c para Bob.
4. Bob escolhe x ∈R Z∗N e envia y = x2 (mod N) para Alice.
5. Alice calcula as quatro raízes quadradas de y (que são x,−x, y,−y). Ela pode fazê-lo e�cientemente porque tem p e q. Alice então escolhe uma das raízes aleatoreamente e envia para Bob.
6. Se Bob recebeu uma das raízes diferentes de ±x ele pode fatorar N e decifrar c em m. Se recebeu uma das outras duas raízes, não conseguirá decifrar c.

Questões para Estudantes

ano passado

Questões para Estudantes

ano passado

cripto

FMU

Respostas

Ed

ano passado

Você tem que criar uma nova pergunta.

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.

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?

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.