On the efficient implementation of RSA

Download
2015
Güner, Hatice Kübra
Modular exponentiation is an essential operation for many asymmetric key cryptosystems such as RSA in which encryption and decryption are based on modular exponentiation. Therefore, efficiency of the system is effected with running time of the modular exponentiation algorithm. At the same time, key sizes also influence the efficiency of the algorithm. Over the years key sizes had to be increased to provide security. To make RSA practical, one of usable choices is acceleration of the modular exponentiation algorithm. There are many methods for fast modular exponentiation, but all of them are not suitable for RSA. To find the most suitable one, we need to examine running time of the algorithms. In this thesis, we have studied some of the proposed fast modular exponentiation methods. They were implemented with using MPIR library and their running time results were compared with the repeated squaring and multiplication algorithm. Moreover, some efficient methods were recommended for RSA. In these methods, at least 23% improvement was obtained for each key sizes on decryption.

Suggestions

Modular exponentiation methods in cryptography
Yünüak, Hasan Bartu; Cenk, Murat; Department of Cryptography (2017)
Modular exponentiation has an important role in many cryptographic algorithms. These exponentiation methods differ in the bases used and their representations, the repeating aspect, and for which algorithms they are used for: fixed or variable base. Our research aims to compare the efficiencies and implementation timings for some selected algorithms. Also, we look at the options for using a dedicated cubing algorithm, and compare them with the current algorithms.
On provable security of some public key encryption schemes
Hanoymak, Turgut; Akyıldız, Ersan; Selçuk, Ali Aydın; Department of Cryptography (2012)
In this thesis, we analyse the security criteria of some public key encryption schemes. In this respect, we present the notion of adversarial goals and adversarial capabilities. We give the definition of provably security by means of several games between the challenger and the adversary in some security models, namely the standard model and the random oracle model. We state the main differences between these two models and observe the advantage of the success probability of the adversary in breaking the cr...
A Randomness test based on postulate r-2 on the number of runs
Şeker, Okan; Doğanaksoy, Ali; Department of Cryptography (2014)
Random values are considered as an indispensable part of cryptography, since they are necessary for almost all cryptographic protocols. Most importantly, key generation is done by random values and key itself should behave like a random value. Randomness is tested by statistical tests and hence, security evaluation of a cryptographic algorithm deeply depends on statistical randomness tests. In this thesis we focus on randomness postulates of Solomon W. Golomb in particular, second postulate which is about r...
A Survey on the provable security using indistinguishability notion on cryptographic encryption schemes
Ayar, Emre; Doğanaksoy, Ali; Koçak, Onur; Department of Cryptography (2018)
For an encryption scheme, instead of Shannon's perfect security definition, Goldwasser and Micali defined a realistic provable security called semantic security. Using indistinguishability notion, one can define security levels according to the polynomial time adversaries' capabilities such as chosen plaintext attacks (CPA) and chosen ciphertext attacks (CCA) for both symmetric and asymmetric encryption schemes in addition to the hard mathematical problems the algorithms based on. Precautions to prevent the...
Mutual correlation of randomness test and analysis of test outputs of transformed and biased sequences
Akcengiz, Ziya; Doğanaksoy, Ali; Department of Cryptography (2014)
Randomness is one of the most important parts of the cryptography because key generation and key itself depend on random values. In literature, there exist statistical randomness tests and test suites to evaluate randomness of the cryptographic algorithm. Although there exist randomness tests, there is no mathematical evidence to prove that a sequence or a number is random. Therefore, it is vital to choose tests in the test suites due to independency and coverage of the tests used in the suites. Sensitivity...
Citation Formats
H. K. Güner, “On the efficient implementation of RSA,” M.S. - Master of Science, Middle East Technical University, 2015.