Szyfrowanie algorytmem RSA - bezpieczeństwo i aspekty obliczeniowe

• Autorzy: Jan Madej

Warianty tytułu

Coding with RSA Algorithms - Safety and Computational Aspects

• Języki publikacji: PL

Abstrakty

Celem mniejszego opracowania jest przedstawienie algorytmu RSA, najpopularniejszego i mającego coraz większe zastosowanie w praktyce, algorytmu szyfrującego z kluczem publicznym. Opisano wykorzystanie i sposób działania algorytmu - szyfrowanie tekstu jawnego, deszyfrowanie kryptogramów oraz generowanie kluczy publicznych i prywatnych. Dużo uwagi poświęcono tworzeniu kluczy, ponieważ jest to najważniejsze ogniwo zabezpieczające szyfr przed złamaniem - przedstawiono szczegółowo etapy ich generowania, zamieszczając schematy losowania liczb pierwszych, probabilistycznych testów pierwszości oraz wyszukiwania liczb odwrotnych modulo (test Fermata, test Millera-Rabina, rozszerzony algorytm Euklidesa). Algorytmy zamieszczono w postaci możliwie najprostszej koncepcyjnie i nadającej się do natychmiastowej implementacji. Ponadto zwrócono uwagę na problemy związane z wykonywaniem operacji arytmetycznych wymaganych przy szyfrowaniu i deszyfrowaniu algorytmem RSA (szczególnie wymagające dużych nakładów obliczeniowych operacje potęgowania) oraz przedstawiono sposób ich rozwiązania na podstawie własności arytmetyki modulo. Opracowanie zapoznaje także z najważniejszymi twierdzeniami teorii liczb wykorzystywanymi w kryptografii, na których opiera się funkcjonowanie wielu różnych algorytmów. Omówione zostały również możliwe podejścia do kryptoanalizy szyfrów RSA, ze zwróceniem szczególnej uwagi na metodę rozkładu liczb na czynniki pierwsze oraz problemy obliczeniowe, jakie niesie ona ze sobą. Na koniec przedstawiono zasady bezpiecznego doboru kluczy RSA, od których w ogromnej mierze zależy bezpieczeństwo szyfrów, oraz wymieniono sytuacje, w których szyfry te podatne są na złamanie. (abstrakt oryginalny)

EN

In this paper the author discusses the RSA algorithm, which is the most popular and increasingly applicable algorithm for public key coding. The utilisation and functioning of the algorithm are described, i.e. the coding of open texts, the decoding of cryptograms, and the generation of public and private keys. The author devotes much attention to the issue of keys creation, as it is the most important factor preventing a code from being broken - the different stages of key generation are described in detail, including schemes of: prime number drawing, number primarity probability tests, and modulo-inverted number searches (the Fermat test, the Miller-Rabin test, and the extended Euklides algorithm). These algorithms have been submitted in the simplest possible form which is ready for immediate implementation. The author also focuses on problems connected with the performance of arithmetic operations (in particular, raising to a power operations requiring many computations) necessary in the coding/decoding process involving the RSA algorithm. The author looks at the method of solving these problems, based on modulo arithmetic properties. The paper also provides the reader with information about the most important theorems of number theory which are utilised in cryptography and which are essential for many algorithms. The author also discusses possible approaches to the cryptoanalysis of RSA codes, paying particular attention to the method of number factorisation onto prime factors and to corresponding computational problems. Finally, the author describes the principles of safe RSA key selection, which are fundamental to code safety, and looks at situations when such codes are susceptible to being broken. (original abstract)

Słowa kluczowe

PL

System operacyjny; Algorytmy; Ochrona danych komputerowych

EN

Operating system; Algorithms; Computer data protection

• Czasopismo: Zeszyty Naukowe / Akademia Ekonomiczna w Krakowie
• Rocznik: 2000
• Numer: nr 551
• Strony: 87--104

Twórcy

autor

Jan Madej

Bibliografia

• Adamski A. [1997], Prawna reglamentacja kryptografii, "Netforum", nr 1.
• Adamski A. [1998], Prawo do bezpiecznej sieci, Computerworld Raport - Bezpieczeństwo Sieci, IDG Poland SA, Warszawa, wrzesień.
• Cormen T.E., Leiserson C.E., Rivest R.R. [1997], Wprowadzenie do algorytmów, WNT, Warszawa.
• Denning D.E. [1993], Kryptografia i ochrona danych, WNT, Warszawa.
• Diffie W., Hellman M. [1976], Multiuser Cryptographic Techniques, Proceedings of the AFIPS National Computer Conference, lipiec.
• Diffie W., Hellman W. [1976], New Directories in Cryptography, IEE Transactions on Information Theory, listopad.
• Diffie W. [1988], The First Ten Year of Public-Key Cryptography, Proceedings of IEEE, maj.
• Gardner M. [1977], A New Kind of Cipher that Would Take Millions of Years to Break. Scientific American, sierpień.
• Jarski M., [1998] Publiczna Prywatność - Prywatna Publiczność, Computerworld Raport - Bezpieczeństwo Sieci, IDG Poland SA, Warszawa, wrzesień.
• Kutyłowski M., Strothmann W.B. [1998], Kryptografia - teoria i praktyka zabezpieczania systemów komputerowych, Oficyna Wydawnicza Read Me, Warszawa.
• Ribenboim P. [1997] , Mała księga wielkich liczb, WNT, Warszawa.
• Rivest R., Shamir A., Adleman L. [1978], A Method for Obtaining Digital Signatures on Public Key Cryptosy stems, Communications of the ACM, luty.
• Schneier B. [1996], Ochrona poczty elektronicznej, WNT, Warszawa.
• Simmons G.J., Norris J.N. [1977], Preliminary Comments on the MIT. Public Key Cryptosystem, Cryptologia, październik.
• Stallings W. [1997], Ochrona danych w sieci i intersieci, WNT, Warszawa.
• Wiener M. [1990], Cryptanalysis of Short RSA Secret Exponents, IEEE Transactions on Information Theory.