Segurança do bit menos significativo no RSA e em curvas elípticas
Resumo
A segurança do bit menos significativo da chave secreta no Diffie-Hellman sobre Curvas Elípticas (e da mensagem no RSA) está relacionada à segurança de toda a chave (mensagem). Neste artigo são apresentados algoritmos que conseguem inverter os criptossistemas citados fazendo uso de oráculos que predizem o LSB. Fazemos a implementação de dois desses algoritmos, identificamos parâmetros críticos e mudamos a amostragem do formato original. Com a modificação na amostragem conseguimos uma melhora nos tempos de execução.
Referências
Alexi, W., Chor, B., Goldreich, O., and Schnorr, C.-P. (1988). RSA and Rabin functions: Certain parts are as hard as the whole. SIAM Journal on Computing, 17(2):194–209.
Aranha, D. F. and Gouvêa, C. P. L. RELIC is an Efficient LIbrary for Cryptography. http://code.google.com/p/relic-toolkit/.
Ben-Or, M., Chor, B., and Shamir, A. (1983). On the cryptographic security of single RSA bits. In ACM Symposium on Theory of Computing (STOC ’83), pages 421–430, Baltimore, USA. ACM Press.
Blum, Blum, and Shub (1986). A simple unpredictable pseudo-random number generator. SICOMP: SIAM Journal on Computing, 15.
Blum, M. and Micali, S. (1984). How to generate cryptographically strong sequence of pseudo-random bits. SIAM Journal Computing, 13:850–864.
Boneh, D. and Shparlinski, I. (2001). On the unpredictability of bits of the elliptic curve Diffie-Hellman scheme. In Kilian, J., editor, CRYPTO 2001, volume 2139 of LNCS, pages 201–212. Springer.
Boneh, D. and Venkatesan, R. (1996). Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In CRYPTO ’96, volume 1109 of LNCS, pages 129–142. IACR, Springer, Berlin.
Brent and Kung (1984). Systolic VLSI arrays for polynomial GCD computation. IEEE Transactions on Computers, 33.
Buhler, J. P., Lenstra, H. W., and Pomerance, C. (1993). Factoring integers with the number field sieve. In The development of the number field sieve, volume 1554 of LNM, pages 50–94. Springer-Verlag, Berlin.
Chevalier, C., Fouque, P.-A., Pointcheval, D., and Zimmer, S. (2009). Optimal randomness extraction from a Diffie-Hellman element. In Joux, A., editor, EUROCRYPT 2009, volume 5479 of LNCS, pages 572–589. Springer-Verlag.
Diffie, W. and Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654.
Fischlin, R. and Schnorr, C.-P. (2000). Stronger security proofs for RSA and Rabin bits. Journal of Cryptology, 13(2):221–244.
Goldwasser, S., Micali, S., and Tong, P. (1982). Why and how to establish a private code on a public network (extended abstract). In FOCS, pages 134–144, Chicago, Illinois. IEEE.
Hofheinz, D. and Kiltz, E. (2009). Practical chosen ciphertext secure encryption from factoring. In Joux, A., editor, EUROCRYPT 2009, volume 5479 of LNCS, pages 313–332. Springer.
Jetchev, D. and Venkatesan, R. (2008). Bits security of the elliptic curve Diffie-Hellman secret keys. In Wagner, D., editor, CRYPTO 2008, volume 5157 of LNCS, pages 75–92. Springer.
Knuth, D. E. (1981). The Art of Computer Programming, volume 2, Seminumerical Algorithms. Addison-Wesley, Reading, MA, 2 edition.
Menezes, A. J., Vanstone, S. A., and Oorschot, P. C. V. (1996). Handbook of Applied Cryptography. CRC Press, Boca Raton, FL, USA.
Rabin, M. (1979). Digitalized signatures as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science.
Rivest, R. L., Shamir, A., and Adleman, L. M. (1978). A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 21(2):120–126.
Roh, D. and Hahn, S. G. (2010). On the bit security of the weak Diffie–Hellman problem. Information Processing Letters, 110:799–802.
Ross, S. M. (2006). A First Course in Probability. Prentice Hall, New Jersey, 7 edition.
Shoup, V. (1997). Lower bounds for discrete logarithms and related problems. In Fumy, W., editor, EUROCRYPT ’97, volume 1233 of LNCS, pages 256–266, Berlin Germany. Springer-Verlag.
Stein, J. (1967). Computational problems associated with Racah algebra. Journal of Computational Physics, 1(3):397 – 405.
Aranha, D. F. and Gouvêa, C. P. L. RELIC is an Efficient LIbrary for Cryptography. http://code.google.com/p/relic-toolkit/.
Ben-Or, M., Chor, B., and Shamir, A. (1983). On the cryptographic security of single RSA bits. In ACM Symposium on Theory of Computing (STOC ’83), pages 421–430, Baltimore, USA. ACM Press.
Blum, Blum, and Shub (1986). A simple unpredictable pseudo-random number generator. SICOMP: SIAM Journal on Computing, 15.
Blum, M. and Micali, S. (1984). How to generate cryptographically strong sequence of pseudo-random bits. SIAM Journal Computing, 13:850–864.
Boneh, D. and Shparlinski, I. (2001). On the unpredictability of bits of the elliptic curve Diffie-Hellman scheme. In Kilian, J., editor, CRYPTO 2001, volume 2139 of LNCS, pages 201–212. Springer.
Boneh, D. and Venkatesan, R. (1996). Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In CRYPTO ’96, volume 1109 of LNCS, pages 129–142. IACR, Springer, Berlin.
Brent and Kung (1984). Systolic VLSI arrays for polynomial GCD computation. IEEE Transactions on Computers, 33.
Buhler, J. P., Lenstra, H. W., and Pomerance, C. (1993). Factoring integers with the number field sieve. In The development of the number field sieve, volume 1554 of LNM, pages 50–94. Springer-Verlag, Berlin.
Chevalier, C., Fouque, P.-A., Pointcheval, D., and Zimmer, S. (2009). Optimal randomness extraction from a Diffie-Hellman element. In Joux, A., editor, EUROCRYPT 2009, volume 5479 of LNCS, pages 572–589. Springer-Verlag.
Diffie, W. and Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654.
Fischlin, R. and Schnorr, C.-P. (2000). Stronger security proofs for RSA and Rabin bits. Journal of Cryptology, 13(2):221–244.
Goldwasser, S., Micali, S., and Tong, P. (1982). Why and how to establish a private code on a public network (extended abstract). In FOCS, pages 134–144, Chicago, Illinois. IEEE.
Hofheinz, D. and Kiltz, E. (2009). Practical chosen ciphertext secure encryption from factoring. In Joux, A., editor, EUROCRYPT 2009, volume 5479 of LNCS, pages 313–332. Springer.
Jetchev, D. and Venkatesan, R. (2008). Bits security of the elliptic curve Diffie-Hellman secret keys. In Wagner, D., editor, CRYPTO 2008, volume 5157 of LNCS, pages 75–92. Springer.
Knuth, D. E. (1981). The Art of Computer Programming, volume 2, Seminumerical Algorithms. Addison-Wesley, Reading, MA, 2 edition.
Menezes, A. J., Vanstone, S. A., and Oorschot, P. C. V. (1996). Handbook of Applied Cryptography. CRC Press, Boca Raton, FL, USA.
Rabin, M. (1979). Digitalized signatures as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science.
Rivest, R. L., Shamir, A., and Adleman, L. M. (1978). A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 21(2):120–126.
Roh, D. and Hahn, S. G. (2010). On the bit security of the weak Diffie–Hellman problem. Information Processing Letters, 110:799–802.
Ross, S. M. (2006). A First Course in Probability. Prentice Hall, New Jersey, 7 edition.
Shoup, V. (1997). Lower bounds for discrete logarithms and related problems. In Fumy, W., editor, EUROCRYPT ’97, volume 1233 of LNCS, pages 256–266, Berlin Germany. Springer-Verlag.
Stein, J. (1967). Computational problems associated with Racah algebra. Journal of Computational Physics, 1(3):397 – 405.
Publicado
19/11/2012
Como Citar
NAKAMURA, Dionathan; TERADA, Routo.
Segurança do bit menos significativo no RSA e em curvas elípticas. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 12. , 2012, Curitiba.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 112-125.
DOI: https://doi.org/10.5753/sbseg.2012.20540.
