On the efficient implementation of RSA

Abstract

Modüler üst alma RSA gibi şifreleme ve şifre çözmenin modüler üst almaya dayandığıbirçok asimetrik anahtarlı kriptosistemler için temel işlemdir. Bu nedenle sisteminverimliliği modüler üst alma algoritmasının çalışma süresinden etkilenir. Aynı zamandaanahtar boyutları da algoritmanın verimliliğini etkilemektedir. Yıllar geçtikçegüvenliği sağlamak için anahtar boyutları artırılmak zorundaydı. RSA'yi kullanışlıyapmak için elverişli çözümlerden birisi modüler üst alma algoritmasını hızlandırmaktır.Hızlı modüler üst almak için birçok yöntem var, ancak onların hepsi RSA için uygundeğil. En uygun olanını bulmak için algoritmaların çalışma sürelerini irdelemeyeihtiyacımız var. Bu tezde biz önerilen bazı hızlı modüler üst alma yöntemleriniçalıştık. Bu yöntemler MPIR kütüphanesi kullanarak uygulandı ve onların çalışmasüreleri tekrarlayan kare alma ve çarpma algoritması ile karşılaştırıldı. Dahası, RSAiçin bazı verimli yöntemler önerildi. Bu yöntemlerde, her bir anahtar boyutu için en az%23 iyileştirme elde edildi.

Modular exponentiation is an essential operation for many asymmetric key cryptosystemssuch as RSA in which encryption and decryption are based on modular exponentiation.Therefore, efficiency of the system is effected with running time of the modularexponentiation algorithm. At the same time, key sizes also influence the efficiency ofthe algorithm. Over the years key sizes had to be increased to provide security. Tomake RSA practical, one of usable choices is acceleration of the modular exponentiationalgorithm. There are many methods for fast modular exponentiation, but allof them are not suitable for RSA. To find the most suitable one, we need to examinerunning time of the algorithms. In this thesis, we have studied some of the proposedfast modular exponentiation methods. They were implemented with using MPIR libraryand their running time results were compared with the repeated squaring andmultiplication algorithm. Moreover, some efficient methods were recommended forRSA. In these methods, at least 23% improvement was obtained for each key sizes ondecryption.