We introduce an irrational factor of order <i>k</i> defined by I k ( n ) = i = 1 l p i i , where I k ( n ) = i = 1 l p i i is the factorization of <i>n</i> and $${\beta_{i} = \left\{\begin{array}{ll}\alpha_i, \quad \quad {\rm if} \quad \alpha_i &lt; k \\ \frac{1}{\alpha_i},\quad \quad {\rm if} \quad \alpha_i \geqq k \end{array}\right.}$$. It turns out that the function I k ( n ) = i = 1 l p i i well approximates the characteristic function of <i>k</i>-free integers. We also derive asymptotic formulas for I k ( n ) = i = 1 l p i i and I k ( n ) = i = 1 l p i i .

In 2004, the inventors of TTM cryptosystems proposed a new scheme that could resist the existing attacks, in particular, the Goubin-Courtois attack [GC00] and the Ding-Schmidt attack [DS03]. In this paper, we show the new version is still insecure, and we find that the polynomial components of the cipher (F_i) satisfy nontrivial equations of the special form ∑_{i=0}^{n−1} a_i x_i + ∑_{0≤j≤k≤m−1} b_{jk} F_j F_k + ∑_{j=0}^{m−1} c_j F_j + d = 0, which could be found with 2^{38} computations. From these equations and consequently the linear equations we derive from these equations for any given ciphertext, we can eliminate some of the variables x_i by restricting the functions to an affine subspace, such that, on this subspace, we can trivialize the "lock" polynomials, which are the key structure to ensure its security in this new instance of TTM. Then with method similar to Ding-Schmidt [DS03], we can find the corresponding plaintext for any given ciphertext. The total computational complexity of the attack is less than 2^{39} operations over a finite field of size 2^8. Our results are further confirmed by computer experiments.

We show all the existing TTM implementation schemes have a defect that there exist linearization equations \sum_{i=1,j=1}^{n,m} a_{ij} x_i y_j(x_1,...,x_n) + \sum_{i=1}^n b_i x_i + \sum_{j=1}^m c_j y_j(x_1,...,x_n) + d = 0, which are satisfied by the components y_i(x_1,...,x_n) of the ciphers of the TTM schemes. We further demonstrate that, for the case of the most recent two implementation schemes in two versions of the paper \cite{CM}, where the inventor of TTM used them to refute a claim in \cite{CG}, if we do a linear substitution with the linear equations derived from the linearization equations for a given ciphertext, we can find the plaintext easily by an iteration of the procedure of first search for linear equations by linear combinations and then linear substitution. The computation complexity of the attack on these two schemes is less than 2^{35} over a finite field of size 2^8.

No abstract uploaded!

No abstract uploaded!