Msc-Seminaries in Cryptography:
  • Publishing Upper Half of RSA Decryption Exponent (31-05-2011)
  • No criptosistema RSA, dado um expoente pequeno de encriptação 'e', a metade superior de bits do expoente de desencrptação 'd' é facilmente calculado. No seminário vamos expor alguns esquemas onde utiliza este fato para conseguir uma desencriptação eficiente do RSA.
  • Correção de Erros nas Chaves Privadas RSA (30-08-2011)
  • Seja pk = (N , e) a chave pública RSA e a correspondente chave secreta sk(p, q, d, dp, dq, qp-1). Sabemos que podemos obter um sk' (sk com erros) usando um ataque "side-channel". Neste seminário apresentaremos um algoritmo probabilístico capaz de corrigir erros em sk' para obter o sk original.
  • Ataques Cold-Boots e Reconstrução da Chave Privada RSA (28-03-2012)
  • Em 2008, J. A. Halderman publicou um artigo onde mostra que é possível a recuperação da informação (bits) graças à propriedade de remanência da memória DRAM. Esse conhecimento é usado para recuperar uma versão degradada da chave secreta RSA. Na qual N. Heninger e H. Shacham apresentam um algoritmo de reconstrução que faz uso da redundância da chave secreta RSA segundo ao padrão PCKS #1 para corrigir a chave privada, e assim, obter o seu valor correto.
  • Reconstrução da Chave Privada RSA Multi-primo (04-09-2012) (1 parte)
  • Em 2008, J. A. Halderman publicou um artigo onde mostra que é possível a recuperação da informação (bits) graças à propriedade de remanência da memória DRAM. Esse conhecimento é usado para recuperar uma versão degradada da chave secreta RSA. Na qual N. Heninger e H. Shacham apresentam um algoritmo de reconstrução que faz uso da redundância da chave secreta RSA segundo ao padrão PCKS #1 para corrigir a chave privada, e assim, obter o seu valor correto. O padrão PCKS #1 a partir da versão 2.0 tem suporte também para a variante RSA multi-primo, onde também é especificado a mesma fraqueza "redundância na chave privada". Neste seminário, vamos estudar o algoritmo de Reconstrução de chave privada de Heninger para o RSA multi-primo.
  • Fatoração do Inteiro N multi-primo com Bits Aleatórios (03-04-2013)
  • Em 2008, J. A. Halderman publicou um artigo onde mostra que é possível a recuperação da informação (bits) graças à propriedade de remanência da memória DRAM. Esse conhecimento pode ser usado para recuperar alguns bits corretos dos fatores primos de N e da chave privada RSA multi-primo. No Seminário será apresentado uma variação do algoritmo de reconstrução de bits de Heninger e Shacham que permite fatorar N multi-primo em tempo polinomial tendo uma determinada porcentagem de bits corretos dos seus fatores primos.
  • Reconstrução da chave secreta do RSA multi-primo (23-09-2013) (Completo)
  • Em 2009, N. Heninger e H. Shacham apresentaram um algoritmo de reconstrução que permite recuperar a chave secreta sk do criptossistema RSA básico em tempo polinomial tendo em forma aleatória 27 % dos seus bits. Baseados nesse algoritmo foi implementado seu análogo para o criptossistema RSA multi-primo onde os resultados obtidos mostram que para reconstruir uma chave secreta sk do criptossistema RSA u-primos é preciso ter uma porcentagem de bits corretos maior a 27%, portanto o criptossistema RSA multi-primo oferece uma segurança maior com relação ao criptossistema RSA básico.
    Msc-Publications:
  • Factoring a multi-prime modulus N with random bits
  • (paper) (slides)
    In 2009, Heninger and Shacham presented an algorithm using the Hensel’s lemma for reconstructing the prime factors of the modulus N=r1r2 . This algorithm computes the prime factors of N in polynomial time, with high probability, assuming that a fraction greater than or equal to 59 % random bits of its primes r1 and r2 is given. In this paper, we present the analysis of Hensel’s lemma for a multiprime modulus N=∏ui=1ri (for u>=2 ) and we generalise the Heninger and Shacham’s algorithm to determine the minimum fraction of random bits of its prime factors that is sufficient to factor N in polynomial time with high probability.
    Msc-Dissertation:
  • Reconstrução da chave secreta do RSA multi-primo
  • Em 2009, N. Heninger e H. Shacham apresentaram um algoritmo de reconstrução que permite recuperar a chave secreta sk do criptossistema RSA básico em tempo polinomial tendo em forma aleatória 27 % dos seus bits. Sabemos que podemos obter uma versão com erros (bits modicados) da chave secreta RSA graças aos ataques cold boot. O algoritmo apresentado por Heninger-Shacham corrige esses erros fazendo uso das relações matemáticas que existe entre as chaves pública e secreta do criptossistema RSA básico. O objetivo deste trabalho é estudar esse algoritmo para implementar e analisar seu análogo para o criptossistema RSA multi-primo. Os resultados obtidos mostram que para reconstruir a chave secreta sk do criptossistema RSA u-primos é preciso ter uma fração de bits corretos maior a 2 - 2((u+2)/(2u+1)), mostrando assim que a segurança oferecida pelo criptossistema RSA multi-primo (u>3) é maior com relação ao criptossistema RSA básico (u = 2).

    reynaldo at ime dot usp dot br

    reynaldocv at gmail dot com