Segurança do bit menos significativo no RSA e em curvas elípticas
Abstract
The security of the least significant bit of the secret key in the Elliptic Curve Diffie-Hellman (and of the message in the RSA) is related to the security of the whole key (message). In this paper, algorithms are presented to invert these cryptographic systems making use of oracles that predict the LSB. We implement two of them, critical parameters are identified and the original sampling is changed. With the modified sampling we achieve an improvement in the execution times.
References
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.
Published
2012-11-19
How to Cite
NAKAMURA, Dionathan; TERADA, Routo.
Segurança do bit menos significativo no RSA e em curvas elípticas. In: BRAZILIAN SYMPOSIUM ON CYBERSECURITY (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.
