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 ...

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