CRYPTANALYSIS OF AN IMPLEMENTATION SCHEME OF THE TAMED TRANSFORMATION METHOD CRYPTOSYSTEM

摘要

A Tamed Transformation Method (TTM) cryptosystem was proposed by T. T. Moh in 1999. We describe how the first implementation scheme of the TTM system can be defeated. The computational complexity of our attack is 2~(33) computations on the finite field with 2~8 elements. The cipher of the TTM systems are degree 2 polynomial maps derived from composition of invertible maps of either total degree 2 or linear maps which can be easily calculated and can be easily inverted. To ensure the system to be of degree two, the key construction of the implementation schemes of the TTM systems is a multivariable polynomial Q_8(x_1,…,x_n) and a set of linearly independent quadratic polynomials q_i(x_1,…,x_m), i=1,…,n such that Q_8(q_1,…,q_n) is again a degree 2 polynomials of x_1,…,x_m. In this paper, we study the first implementation scheme of the TTM systems [6]. We discovered that in this implementation scheme the specific polynomial Q_8 can be decomposed further into a factorization in terms of composition. By taking powers of the equality satisfied by the new composition factors, we can actually derive a set of equations, that can produce linear equations satisfied by the plaintext. These linear equations lead us to find a way to defeat this implementation scheme.