ON PROPERTIES OF KNAPSACK SYSTEMS OF INFORMATION PROTECTION WITH THE OPEN KEY IN Zp

Abstract

Full Text

Properties of sequences of numbers expressed through components of a knapsack vector are investigated. Properties of isomorphic and similar knapsack systems of information protection are analyzed. Methods of increasing cryptographic security of knapsack systems of information protection with an open key are presented. Keywords: a knapsack vector, isomorphism, cryptoanalysis, density, injectivity. Let’s express a set of natural numbers {0, 1, …, p–1} through Zp and a set of all numerical sets of length n with components from Zp. through n Z p . A knapsack problem for set w ∈ N and vector A = (а1, а2, …, аn), where аi∈N, I = 1…n, has the solution in Zp if there is an equation solution AxT = w, x∈ n Z p (1) we will call vector А of equations (1) a knapsack vector. A knapsack vector A = (а1, а2, …, аn) is an injective one if for any natural w the equation (1) has not more than one solution. A knapsack vector which has two elements ai = aj, I ≠ j, is not injective. Injectivity of a knapsack vector allows to speak about uniqueness of restoration of the original text according to the cryptogram. Supergrowing knapsack vectors are the simplest injective knapsack vectors from the point of view of understanding and algorithmization. For their components in Zp the following relationships are carried out: 1 1 ( 1) j j i i a p a − >Σ − , j = 2...n (2) A knapsack vector A = (а1, а2, …, аn) is a nondecreasing one if its components are ordered according to the rule ai–1 ≤ аi, I = 2…n. Accordingly, the vector is increasing if its components are ordered according to the rule ai–1 <аi, I = 2…n. Definition. Let’s call vector ΔA = (δ 1, δ2, …, δn) a variation of vector A = (а1, а2, …, аn) (аi ∈ N, I = 1…n) in Zp, For its components the following correlations are carried out: δ1 = a1 , 1