EXPLORING A NON FACTOR METHOD OF DECRYPTING THE RSA CODE

Abstract

Breaking of the RSA cryptosystem remains an unsolved intriguing mathematical problem. The security of the RSA code rests on the fact that factoring large integers is a hard problem. These are numbers having exactly two large prime factors. Several such numbers with 129 digits or more, known as RSA numbers, have been factored. In spite of this achievement, no progress in breaking the code seems to be forthcoming from the factoring approach. This difficulty arises from availability of a prime number greater than n, where n is a natural number. In this work, we explore a method that is independent of factoring methods. With the RSA code, a public key (e, n) is given to the public. We set pe ≡ c(mod n) where p is a plaintext word and c is its corresponding ciphertext word. Some secret key (d,f (n) (where f (n) is the Euler phi function of n) is held by the receiver and is unknown to anybody else. It is known that ed = 1modf (n) So by letting the non-reduced value of c be c + nx , x∈$!+ pe = c + nx ( ) (mod ) 1 p = c + nx e n We develop mathematical algorithm for calculating the first integral eth root of c + nx .This integer is the required value of p. Using the algorithm we successfully deciphered messages of plaintexts sent in blocks of up to five. This method requires that the block size is determinable by the decoder. There is need however to develop a system of inferring the length of the blocks used in the plaintext before applying the encryption algorithm in which case the method can be extended to decrypting messages sent in any block length. In the paper we also have two results regarding the choice of the public key in this code. 1. If p = q , then n and f (n) are both perfect squares and computing the secret key d becomes trivial. 2. If both p and q are twin primes, that is p = q ± 2 , n is of the form q 2q 2 ± . The integer k = n +1 is therefore a perfect square and can be used to estimate the factors of n, hence reducing to the first case. Key words: Cryptography, cryptanalysis, cryptology, encryption, plaintext, ciphertext, decryption, key, public key cryptography