The attack on the RSA algorithm with the application of Euler's function

• Autorzy: Kotlarz P. , Żmudziński P. , Dunajewski I.
• Języki publikacji: EN

Abstrakty

EN

The security of present-day asymmetric encryption algorithms is based on certain limitations of modern mathematics. A wide range of applications of asymmetric cryptography in commonly and widely used network protocols poses a question as to what degree such solutions, in a situation where the security of the used algorithm is not given once and for all, are really safe? In the vast majority of instances, a discussion on security involves considerations on the problem of factorization. The attack, derived almost from the definition, is an attack that involves trying many different options to intercept the private key, indispensable for decryption of the encrypted message, on the basis of the intercepted public key. The present work discusses possibilities and the feasibility of an attack on the RSA algorithm using two given methods, factorization and the method that implements Euler's function. The paper presents an analysis of potential costs (time and computational) for both presented methods. The article also includes a discussion on strong and weak keys for the RSA encryption. The quality of the keys is discussed taking into account the aforementioned two algorithms carrying out an attack against the encryption algorithm.

Słowa kluczowe

EN

RSA; encryption algorithms; network topology; factorization

PL

algorytm szyfrowania; topologia sieci; rozkładanie na czynniki pierwsze

• Wydawca: Instytut Telekomunikacji i Informatyki Uniwersytetu Technologiczno-Przyrodniczego w Bydgoszczy
• Czasopismo: Image Processing & Communications
• Rocznik: 2006
• Tom: Vol. 11, no 1
• Strony: 25--31
• Opis fizyczny: Bibliogr. 12 poz., wykr.

Twórcy

autor

Kotlarz P.

autor

Żmudziński P.

autor

Dunajewski I.

• Institute of Environmental Mechanics and Applied Computer Science, Kazimierz Wielki University, Chodkiewicza 30, 85-072 Bydgoszcz, Poland,

Bibliografia

• [1] Diffe W., Hellman M. E., “New directions in cryptography”, IEEE Trans. Inform. Theory, IT-22:G44-654, November 1976.
• [2] Rivest R., Shamir A., Adieman L. M., “A method for obtaining digital signatures and public key cryptosystems”, Communications of the ACM, 21:120-126, 1978.
• [3] Catalano D., Gennaro R., Halevi S., “Computing inverses over a shared secret modulus”, IBM T.J. Watson Research Center, 2000.
• [4] Frankel Y, Desmedt Y. G., “Parallel reliable threshold multisignature”, Tech. Report: Department of E.E. and C.S. University of Wisconsin-Milwaukee, WI 53201, TR-92-04-02, 1992.
• [5] Miller G. L., “Riemann's hypothesis and tests for primality”, Journal of Computer and System Science, 13(3):300-317, 1976.
• [6] Rabin M., "Probabilistic algorithms for testing primality", J. Number Theory, 12:128-138, 1980.
• [7] Pieprzyk J., Hardjono T., Seberry J., “Fundamentals of Computer Security”, Springer- Verlag, Berlin 2003.
• [8] Simmons G. J., Norris M. J., “Preliminary comments on 1,1m MIT public-key cryptosystem”, Cryptologia, 1(4):406-414, October 1977.
• [9] Boneh D., “Twenty years of attacks on the RSA cryptosystems”, Notices of the AMS, 46(2):203-213, 1999.
• [10] Gordon D. M., “A survey of fast exponentiation methods”, Center for Communications Research, December 30, 1997.
• [11] Cavallar S., Lioen W., te Riele H., “Factorizing of a 512 bit RSA modules”, MAS-R0007, February 29, 2000.
• [12] Kocher P. C., “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems”, Advances in Cryptology - CRYPTO'96, volume 1109 of LNCS, Springer-Verlag, 1996.