Method and apparatus for data permutation/division and recording medium with data permutation/division program recorded thereon

A substitution-permutation apparatus which, by the following substitution-permutation over a ring R [ y 1 y 2 ⋮ y m ] = P ⁡ [ s 1 ⁡ ( x 1 ) s 2 ⁡ ( x 2 ) ⋮ s n ⁡ ( x n ) ]

• where P = [ p 11 p 12 ⋯ p 1 ⁢ n p 21 p 22 p 2 ⁢ n ⋮ ⋮ p m1 p m2 ⋯ p mn ] pijεR, sj:R→R
• i=1, 2, . . . , m
• j=1, 2, . . . , n
• performs a substitution-permutation operation of an input data sequence (Xj) to calculate a data sequence (yi), said apparatus comprising:
• storage means for storing:
• a precalculated value of the following equation with rows of a matrix P rearranged SP lj ⁡ ( x j ) = [ p t ⁡ ( ql ) ⁢ j ⁢ s j ⁡ ( x j ) p t ⁡ ( ql + 1 ) ⁢ j ⁢ s j ⁡ ( x j ) ⋮ p t ⁡ ( rl ) ⁢ j ⁢ s j ⁡ ( x j ) ]
• where b(j) is a natural number equal to or greater than 1 but equal to or smaller than n, 1=1,2, . . . ,b(j), t:{1, 2, . . . , m}→{ 1, 2, .. ., m} is a permutation, and ql and rl are natural numbers greater than 1 but smaller than m+1, where ql≦rl;
• precalculated values of n vectors wkεRm;
• and an integer k;
• input means for storing said input data sequence (xj) in said storage means;
• k-initialization means for setting said integer k to 0;
• k-updating means for updating said k stored in said storage means to k+1;
• SPk calculating means for reading out input data xk and SPlj(xk) from said storage means, for calculating said SPlj(xk) for each l and concatenating the calculated results in correspondence to a k-th column of said rearranged matrix P to obtain an m-dimensional vector, and for updating said wk stored in said storage means with said m-dimensional vector as wk, where l=1, 2, . . . , b(j);
• control means for reading out said k stored in said storage means and for actuating said SPk calculating means and said k-updating means one after the other until k=n;
• and
• output means for reading out each wk stored in said storage means and for calculating and outputting their sum.

A recording medium having recorded thereon a program for the execution by a computer of a substitution-permutation apparatus which, by the following substitution-permutation over a ring R [ y 1 y 2 ⋮ y m ] = P ⁡ [ s 1 ⁡ ( x 1 ) s 2 ⁡ ( x 2 ) ⋮ s n ⁡ ( x n ) ]

• where P = [ p 11 p 12 ⋯ p 1 ⁢ n p 21 p 22 p 2 ⁢ n ⋮ ⋮ p m1 p m2 ⋯ p mn ] pijεR, sj:R→R
• i=1, 2, . . . , m
• j=1, 2, . . . , n
• performs a substitution-permutation operation of an input data sequence (xj) to calculate a data sequence (yi) and in which storage means has stored therein:
• precalculated values of vi (whose dimensions are up to m and may differ individually) over said ring R necessary for said substitution-permutation, obtained by swapping rows or columns of said matrix P for which some of pij or sj are the same values;
• a precalculated value of a function Sk:R→Rm;
• precalculated values of n vectors wkεRm;
• and an integer k;
• said program comprising the steps of:
• (a) storing said input data sequence xj in said storage means;
• (b) initializing said integer k to 0;
• (c) updating said k in said storage means to k+1;
• (d) reading out each Sk and input data (xk) from said storage means to obtain the result of calculation of a vector Sk (xk) and storing said vector as a vector wk in said storage means;
• (e) reading out of said storage means a set of vectors {v1} necessary for forming a k-th column of said matrix P and generating a vector uk;
• (f) reading out said wk from said storage means and calculating the product for each element and updating said wk with the calculation result;
• (g) reading out said k stored in said storage means and performing said Sk calculating step, said wk updating steps and said k-updating step one after another until k=n;
• and
• (h) reading out each wk stored in said storage means and calculating;
• and outputting their sum.

A recording medium having recorded thereon a program for the execution by a computer of a substitution-permutation apparatus which, by the following substitution-permutation over a ring R [ y 1 y 2 ⋮ y m ] = P ⁡ [ s 1 ⁡ ( x 1 ) s 2 ⁡ ( x 2 ) ⋮ s n ⁡ ( x n ) ]

• where P = [ p 11 p 12 ⋯ p 1 ⁢ n p 21 p 22 p 2 ⁢ n ⋮ ⋮ p m1 p m2 ⋯ p mn ] pijεR, sj:R→R
• i=1, 2, . . . , m
• j=1, 2, . . . , n
• performs a substitution-permutation operation of an input data sequence (xj) to calculate a data sequence (yi) and in which storage means has recorded therein a precalculated value of the following equation with rows of a matrix P rearranged SP lj ⁡ ( x j ) = [ p t ⁡ ( ql ) ⁢ j ⁢ s j ⁡ ( x j ) p t ⁡ ( ql + 1 ) ⁢ j ⁢ s j ⁡ ( x j ) ⋮ p t ⁡ ( rl ) ⁢ j ⁢ s j ⁡ ( x j ) ]
• where b(j) is a natural number equal to or greater than 1 but equal to or smaller than n, l=1,2, . . . ,b(j), t:
• {1, 2, . . . , m}→{1, 2, . . . , m} is a permutation, and ql and rl are natural numbers equal to or greater than 1 but equal to or smaller than m, where ql≦rl, together with;
• precalculated values of n vectors wkεRm and an integer k, said program comprising the steps of;
• (a) storing said input data sequence (xj) in said storage means;
• (b) initializating said integer k to 0;
• (c) updating said k stored in said storage means to k+1;
• (d) reading out input data xk from said storage means, calculating SPlj(xk) for each l, concatenating the calculated results in correspondence to a k-th column of said rearranged matrix P to obtain an m-dimensional vector, and updating said wk stored in said storage means with said m-dimensional vector as wk, where l=1, 2, . . . , b(j);
• (e) reading out said k stored in said storage means and performing said SPk calculating step and said k-updating step one after the other until k=n;
• and
• (f) reading out each wk stored in said storage means and calculating and outputting their sum.