__Keywords:__security analysis of RSA bijective polynomial mappings cycle representation

S.F. Krendelev, E.O. Spitsyna

This research was conducted in order to figure out security of the RSA cryptosystem. Iterative method that is based on the bijectiveness of cryptographic mappings used in the RSA and the fact that the ring is infinite was chosen for breaking cryptosystem (i.e. for recovering the original message from the encrypted one and the encryption function). One of the most valuable advantages of this approach is a possibility of parallelization that accelerates the process of breaking the RSA significantly. Considering that the speed of iterative method depends on the cycle representation of mappings a number of experiments were run. During these experiments cycle representations of mappings used in the RSA were studied. Examples of such representations of mappings over the ring with dimension 667 are provided and detailed explanation is given. As a result of these experiments different approaches to break this algorithm were created and recommendations about how to enlarge its security were made.
In the second part of this work the issue of searching for bijective polynomial mappings over rings is affected. In order to find out a universal scheme of constructing such mappings or at least of speeding up a process of searching for them experiments were run. However, the results of experiments reject the hypothesis of existing of such scheme. That means that the only possible way of searching for required mappings is complete enumeration. Further a problem of constructing an algorithm for public-key cryptography is considered. Since the manual construction of bijective mappings is limited by the dimension of the ring (not more than 24 bytes) two groups of mapping are introduced: diagonal mappings and mappings that are formed by all possible superpositions of Cremona’s mappings. The encryption function (public key) is generated the following way: mappings are chosen from the first group, from the second one and superposition is applied. Unlike methods like HFE (Hidden Field Equations) there is no opportunity of using Gröbner basis for breaking this system. Moreover, this approach is expected to be convenient for White Box Cryptography as a problem of recovering private key from the public key is complicated

References: