On Cryptographic Properties Of T-Functions And Their Generating Sequences

T-functions are mappings which mix the algebraic operations and logical operations.They have many advantages in function implementation and sequences generation sincethey are based on the details of the target platform. Especially, T-functions which aresingle cycle can have initial value, and can generate the longest periodical sequence. Theycan be implemented easier and can have lower linear relation than the traditional generatorLFSR. A single cycle T-function has wide application in stream ciphers, block ciphersand Hash function design. This dissertation investigates the basic theory of T functions;concludes some properties of single cycle T functions and cryptographic properties ofsequences generated by single cycle T-functions. The author obtains main results asfollows:(1). A kind of T-function which is similar to the Klimov-Shamir T-function is studiedand an application of it is proposed. Aimed at the nonlinear property in T-function,Walsh spectra and nonlinearity of single cycle T-functions are studied by utilizingthe algebraic structure of invertible T-function and single cycle T-function. Rela-tionship between nonlinearity of coordinate function and its composing function isanalyzed.(2). The shift autocorrelation function of the kth coordinate sequence is discussed by thespecial property of the kth coordinate sequence. The upper bound and lower boundof autocorrelation function are given when the shift is small. The result shows thatthe kth coordinate sequence have large value when given a small shift. This impliesthat a single cycle T-function has its cryptographic weakness, and it does not satisfythe Golomb pseudorandom Postulate3.(3). Autocorrelation of the state output sequence of a single cycle T-function is studiedby the above result of the kth coordinate sequence, and the upper bound and lowerbound are got separately. By using the maximum sidelobe ratio, it is discussed thatthe state output sequence also has poor autocorrelation and is not pseudorandomsequence. Similarly, the truncated sequences of a single cycle T-function are dis-cussed. Autocorrelation of the coordinate output sequence is discussed too. All theresults show that these single cycle T-function sequences can not be pseudorandom.(4). Linear complexity of sequences generated by single cycle T-function is studied. Lin-ear complexity of the kth coordinate sequence, concatenated sequence, and stateoutput sequence is got when word size n is an odd number or the production ofpower of odd number and power of2. These values show T-function sequences are quite good in the linear complexity concern. Meanwhile, comparison of the valueindicates that the coordinate output sequence has better linear complexity.(5).2-Adic complexity of sequences generated by single cycle T-function is studied. Val-ues or upper bounds of these sequences are given. Examples are found to illustratethe bound we get is tight. The results show that the kth coordinate sequence,state output sequence and truncated sequence can not get their maximum2-adiccomplexity as the m sequence, while the coordinate sequence can.(6). T-function theory is discussed under the algebraic dynamic. Distribution pairsmethod is used to verify whether the newly proposed T function has good linearcomplexity. And some point of design of single cycle T-function is suggested.