Tools
Tools
Novakovic, Dusica (2005) Some aspects of construction and enumeration of good permutations. Doctoral thesis, London Metropolitan University.
Permutations are commonly used in cryptography in order to help protect the confidentiality of data and the problem of the enumeration of permutations of a given class has attracted mathematicians from old times. There is considerable benefit to be had therefore, from studying the characteristics of permutations that render them useful for encryption purposes. A problem, known to be very hard, consists of enumeration of permutations a where i+a(i) are different modulo n, where n is the number of entries in the permutation, 0 ≤ i < n . We call this kind of permutations good permutations. In this thesis we show that there aren't any good permutations of even order n and we tackle the problem of generating, enumerating and denumerating the good permutations for a given odd n. It is not hard to see that, for odd n, the probability of a permutation being good is related to the size of n (inversely proportional for relatively small odd n, definitely up to say n=33). It has been established that it is more difficult to decipher text (at least in a rotor system) encrypted using a good permutation than a 'not-good' permutation [CGKN01]. Consequently, the probability of a permutation being good is an indication of the relative safety of an alphabet of size n. At first, the good permutations were enumerated exactly and the precise results for all odd n ≤ l9 are provided. Later on as the running time of the programs increased rapidly when n increased, a theoretical solution to determining the probability of a good permutation was clearly desirable over an empirical approach. However, greater complexity is introduced in the experimental work, which makes this research challenging. As a result of these experiments algorithms for approximate estimation of the number of good permutations were developed. In summary, this research develops a set of methods for determining the probability of a permutation being good by using techniques from generation of permutations and partitions, and with reference to the characteristics of good permutations presented by Levitskaya in [LEVI01] and Novakovic in [NOVA01I]
 |
View Item |