| Abstract [eng] |
Cryptanalysis might seem to be a natural opposition of cryptography but very commonly these two subjects are complementary. Good understanding of cryptanalysis helps to create better cryptographic methods. The most straightforward method of secret key cryptosystem attack is brute-force search. But there is also the easiest way to protect against it by choosing the large enough key space. Other ways of breaking the cryptosystems are more complex and by proving that they are not more efficient than brute-force attacks may prove the security of the cryptosystem. In this paper we analyze matrix equations over the finite ring. These equations were derived from the simple matrix cipher relating unknown secret key with given plaintext and corresponding ciphertext. We had few goals: to check whether there is more than one solution of the key with fixed plaintext and cypher text information by brute-force search and to create a more efficient, algebraic equations solving algorithm. Simple matrix cipher (SMC) – is a typical symmetric secret key cryptosystem and has three main steps: key generation, encryption, decryption. SMC works in multiplicative semigroup of square matrices over the finite ring. By performing known-plaintext attack with matrix brute-force search algorithm in this system, we found that when increasing the plaintext and ciphertext (number of input and output matrices) the numer of solutions decreses. It is clear, that using 7 input and output matrices pairs with each of checked rings, we reach such limit, that solutions number stabilizes. Moreover, we proved the number of true solutions theoretically. Number of true solutions is always equal to the number of inverse elements in the ring. Alternatively, it is possible to find SMC keys in algebraic way, solving nonlinear systems of equations. Theoretically this leads us to quite hard problem of solving systems of multivariate quadratic (MQ) equations. The associated MQ-problem is known to be NP-complete. Fortunately, linearization methods to solve such systems effectively exists and we found the true solutions with an algebraic equations solving algorithm. Algebraic equations solving algorithm had more constrains and chosen-plaintext attack was performed over the finite field, but such algorithm is considerably more effective than matrix brute-force search. |
