Source: http://www.google.com/patents/US6850960?dq=7350717
Timestamp: 2014-12-29 00:58:33
Document Index: 474464112

Matched Legal Cases: ['art 13', 'art 22', 'arts 22', 'art) 22', 'arts 22', 'art 22', 'art 30', 'art 31', 'art 13', 'art 33', 'art 32', 'art 13', 'art 13', 'art 13', 'art 13']

Patent US6850960 - Inverse calculation apparatus and recording medium having stored thereon a ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsIn an inverse calculation, x is road out of a storage means, [x/2] is calculated and stored therein as b, a lent significant bit of b is stored as a, [(ax+b)/2] is calculated and stored as updated b, and low-order two bits of x are stored as y. Then, for i=1, 2, . . . , n−1, by is calculated, a is...http://www.google.com/patents/US6850960?utm_source=gb-gplus-sharePatent US6850960 - Inverse calculation apparatus and recording medium having stored thereon a program for executing inverse calculationAdvanced Patent SearchPublication numberUS6850960 B2Publication typeGrantApplication numberUS 10/419,241Publication dateFeb 1, 2005Filing dateApr 21, 2003Priority dateJan 19, 1999Fee statusPaidAlso published asUS6578061, US6859818, US20030195915, US20040008841Publication number10419241, 419241, US 6850960 B2, US 6850960B2, US-B2-6850960, US6850960 B2, US6850960B2InventorsKazumaro Aoki, Hiroki Ueda, Masayuki KandaOriginal AssigneeNippon Telegraph And Telephone CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (9), Non-Patent Citations (7), Referenced by (1), Classifications (14), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetInverse calculation apparatus and recording medium having stored thereon a program for executing inverse calculationUS 6850960 B2Abstract In an inverse calculation, x is road out of a storage means, [x/2] is calculated and stored therein as b, a lent significant bit of b is stored as a, [(ax+b)/2] is calculated and stored as updated b, and low-order two bits of x are stored as y. Then, for i=1, 2, . . . , n−1, by is calculated, a is updated with −by, [(b+ax)/(2^(2i))] is calculated and stored as updated b, and y+a2^(2i) is calculated and stored as updated y, where y is road out as the result of inverse calculation.
1. An inverse calculating apparatus comprising:
input means for storing an input x in storage means; storage means for staring integers n and i and 2n-bit integer x, y, a and b, where said integers n and i are equal to or greater than 1; first b-initializing means for calculating [x/2] using said x stored in said storage means and storing the calculation result as said b in said storage means, where [x] is the maximum integer not exceeding x; a-initializing means for storing the least significant bit of said b as a in said storage means; second b-initializing means for calculating [(ax+b)/2] using said a, x and b stored in said storage means and updating said b stored in said storage means with the calculation result; y-initializing means for acquiring low-order two bits of said x stored in said storage means and storing them as said y in said storage means; i-initializing means for setting said i in said storage means to 1; a-updating for calculating −by using said b and y stored in said storage means and updating said a stored in said storage means with the calculation result; b-updating means for calculating [(b+ax)/(2^(2i))] using said a, b, x and i stored in said storage means and updating said b stored in said storage means with the calculation result, where p^q represents the q-th power of p; y-updating means for calculating y+ax2^(2i) using said a, y and i stored in said storage means and updating said y stored in said storage means with the calculation result; i-updating means for updating said i stored in said storage means to i+1; control means for reading out said i and n from said storage means and actuating said a-updating means, said b-updating means, said y-updating means and said i-updating means one after another until i=n; and output means for outputting said y stored in said storage means. 2. A recording medium having recorded thereon a program for the execution by a computer of an inverse calculating apparatus, said program comprising the steps of:
(a) storing an input 2n-bit integer x in storage means, n being an integer equal to or greater than 1; (b) reading out said x from said storage means, calculating [x/2] and storing the calculation result as a 2n-bit integer b in said storage means, where [x] is the maximum integer not exceeding x; (c) reading out said b from said storage means and storing the least significant bit of said b as a 2n-bit integer a in said storage means; (d) reading out said a, x and b from said storage means, calculating [(ax+b)/2], and storing the calculation result as said b in said storage means; (e) reading out said x from said storage means, acquiring low-order two bits of said x, and storing said low-order two bits as a 2n-bit integer y in said storage means; (f) initializing an integer i to 1 and storing it in said storage means; (g) reading out said b and y from said storage means, calculating −by, and updating said a stored in said storage means with the calculation result; (h) reading out said a, b, x and i from said storage means, calculating [(b+ax)/(2^(2i))], and updating said b stored in said storage means with the calculation result, p^q representing the q-th power of p; (i) reading out said a, y and i from said storage means) calculating y+ax2^(2i), and updating said y stored in said storage means with the calculation result; (j) reading out said i from said storage means and updating said i to i+1; (k) reading out said i and n from said storage means and performing said a-updating step, said b-updating step, said y-updating step and said i-updating step one after another until i=n; and (l) reading out said y from said storage means for output.
CROSS-REFERENCE APPLICATION The present is a Divisional application of Ser. No. 09/487,597 filed Jan. 19, 2000, now U.S. Pat. No. 6,578,061, which claims priority from Japanese Applications JP10788/99 filed Jan. 19, 1999; JP15525/99 filed Jan. 25, 1999; JP16238/99 filed Jan. 25, 1999; and JP71255/99 filed Mar. 17, 1999.
The public key cryptosystem uses different keys for data encryption and for decryption; usually, the encryption key is made public and the decryption key is held by a user in secrecy. It is believed that the description key could not be derived from the encryption key within a practical amount of time even with modern mathematical theories and the computing power- of the present-day computer.
There have also been studied schemes that would not allow easy application of the cryptanalysis methods, and it can be expected that such preventive schemes will increase the security of the common key encryption algorithm. According to one of such preventive schemes, a value of some kind available from an encryption key is exclusive ORed with input and output data so as to protect the input and output data for the basic encryption algorithm from an attacker. This scheme is described in �Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, pp.366-367, 1996.� Many of common key encryption algorithms proposed in recent years are designed using this scheme.
X=(x 1 , x 2 , x 3 , x 4) Y=(y 1 , y 2 , y 3 , y 4) Z=(z 1 , z 2 , z 3 , z 4)
z i =y i(K i1(hex)) mod 232 for i=1, 2, 3, 4 (3)
The operation symbol ab represents the OR of a and b for every corresponding bit. Setting ( z i ( 1 ) , z i ( 2 ) , z i ( 3 ) , z i ( 4 ) ) = z i for i = 1 , 2 , 3 , 4 Z ′ = ( z 1 ′ , z 2 ′ , z 3 ′ , z 4 ′ ) ( 4 ) The operation processing of the BP function part 13 is expressed by the following equation: z i ′ = ( z i ′ ( 1 ) , z i + 1 ′ ( 2 ) , z i + 2 ′ ( 3 ) , z i + 3 ′ ( 4 ) ) , i = 1 , 2 , 3 , 4 ( 5 ) where z i + 4 ′ ( j ) = z i ′ ( j ) , j = 1 , 2 , 3 , 4 ( 6 ) where i represents the subblock number for each 32 bits and j the data number of each byte in the subblock. In FIG. 3 there are shown permutations expressed by Eqs. (5) and (6). The four bytes of each piece of data z1, z2, z3 and z4 are distributed to four different output data groups.
R i =L i−1 ⊕F(R i−1 , k i) (7) L i =R i−1 , i=1, 2, . . . , 12 (8)
Each round function part 22 comprises, as depicted in FIG. 2, eight XOR operation parts 22X1, eight S-boxes (S function) 22S1, a linear permutation part (a P function part) 22P, eight XOR operation parts 22X2, and eight S-boxes 22S2. 64-bit right data R is input to the i-th round processing stage RNDi. In the round function part 22, setting the input Ri−1 R i−1=(r 1 , r 2 , r 3 , r 4 , r 5 , r 6 , r 7 , r 8) k i=(K (1) , K (2))=(K 1 (1) , K 2 (1) , . . . , K 8 (1) , K 1 (2) , K 2 (2) , . . . , K 8 (2))
(u 1 , u 2 , . . . , u 8)=(s(r 1 ⊕K 1 (1)), s(r 2 ⊕K 2 (1)), . . . , s(r 8 ⊕K 8 (1))) (9)
u′ 1 =u 2 ⊕u 3 ⊕u 4 ⊕u 5 ⊕u 6 ⊕u 7 u′ 2 =u 1 ⊕u 3 ⊕u 4 ⊕u 6 ⊕u 7 ⊕u 8 u′ 3 =u 1 ⊕u 2 ⊕u 4 ⊕u 5 ⊕u 7 ⊕u 8 u′ 4 =u 1 ⊕u 2 ⊕u 3 ⊕u 5 ⊕u 6 ⊕u 8 u′ 5 =u 1 ⊕u 2 ⊕u 4 ⊕u 5 ⊕u 6 u′ 6 =u 1 ⊕u 2 ⊕u 3 ⊕u 6 ⊕u 7 u′ 7 =u 2 ⊕u 3 ⊕u 4 ⊕u 7 ⊕u 8 u′ 8 =u 1 ⊕u 3 ⊕u 4 ⊕u 5 ⊕u 8 (10)
(v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 8)=(s(u′ 1 ⊕K 1 (2)), s(u′ 2 ⊕K 2 (2)), . . . , s(u′ 8 ⊕K 8 (2))) (11)
The final transformation part 30 obtains, as a ciphertext X=C, X=FT(Z′, k15, k16) from the input thereto Z′=(z1′, z2′, z3′, z4′) and keys k15, k16. More specifically, the BP−1 function part 31 performs inverse processing of the BP function part 13 by the following equation to obtain the output Z. ( z i ′ ( 1 ) , z i ′ ( 2 ) , z i ′ ( 3 ) , z i ′ ( 4 ) ) = z i ′ , i = 1 , 2 , 3 , 4 z i = ( z i ′ ( 1 ) , z i - 1 ′ ( 2 ) , z i - 2 ′ ( 3 ) , z i - 3 ′ ( 4 ) ) i = 1 , 2 , 3 , 4 ( 12 ) where
z′ i−4 (j) =z′ i (j) j=1, 2, 3, 4 Z=(z 1 , z 2 , z 3 , z 4) (13)
y i =z i(K i1(hex))−1 mod 232 , i=1, 2, 3, 4 (14)
A variable in Eq. (14) is zi alone. Hence, it is possible to provide increased efficiency of calculation to precalculate and prestore the value of an inverse element Gi=(Ki1(hex))−1 mod 232 in a memory, since the stored value can be used to calculate yi=ziGi mod 232 for each input data zi. The calculation result Y=(y1,y2,y3,y4) is exclusive ORed with a subkey k16 in an XOR operation part 33 by the following equation, and the resulting output X is provided as the ciphertext C.
z 1′=(z 1ff000000)(z 200ff0000)(z 30000ff00)(z 4000000ff) z 2′=(z 2ff000000)(z 300ff0000)(z 40000ff00)(z 1000000ff) z 3′=(z 3ff000000)(z 400ff0000)(z 10000ff00)(z 2000000ff) z 4′=(z 4ff000000)(z 100ff0000)(z 20000ff00)(z 3000000ff) (16)
where the symbol represents the AND for each bit and the symbol the OR for each bit and �f� and �0� are hexadecimal values. This operation is performed as depicted in FIG. 4. For the sake of brevity, the entire data Z=zi (j) (where i=1, 2, 3, 4; j=1, 2, 3, 4) is represented by a sequence of data a0, a1, . . . , a15. For example, 4-byte data z1 of a register RG1 and 4-byte mask data MD1 of a mask register MRG1 are ANDed to obtain z1ff000000, which is stored in a register RG1′. Then, the AND of data z2 and mask data MD2, z200ff0000, is calculated and is ORed with the data read out of the register RG1′, and the OR thus obtained is overwritten on the register RG1′. By performing the same processing for mask data MD3 and MD4 as well, the data z1′ is provided in the register RG1′. The same calculation processing as described above is also carried out for the data z2′, z3′ and z4′ by Eq. (16). Thus the byte permutation results are obtained in registers RG1′ to RG4′. In the implementation of this calculation scheme, there have been pointed out such problems as mentioned below. That is, the processing by the BP function is byte-byte permutation processing, but a one-word register built in recent CPUs involves masking and shift operations, and hence it consumes much processing time. And, even if the permutation can be made after the ORs are once copied to a memory, the time for memory access inevitably increases, resulting in the processing time increasing. These problems constitute an obstacle to the realization of high-speed performance of the common key cryptosystem.
In the division part 32 in FIG. 1 a precalculated inverse element can be used. In general, it is possible to utilize, for the execution of an inverse element calculation to modulus N, an extended Euclidian algorithm set forth, for instance, in Okamoto and Ohta, coeditors, �Cipher/Zero Knowledge Proof/Number Theory,� Kyouritsu Shuppan, 1995, pp. 120-121. In the case of Eq. (14), however, since the modulus has a special form of 2m, the inverse element can efficiently be calculated by the use of a Hensel Lifting method (a natural method of raising the root of a polynomial from mod bm to mod bm+1). In the calculation of the inverse element with software, when m is about one word length, a Zassenhaus's proposed method which is a quadratic version of the Hensel Lifting (H. Zassenhaus, �On Hensel Factorization, I,� Journal of number theory, vol. 1, pp.291-311, 1969) is effective because the word multiplication is relatively fast on recent CPUs.
1. Set a as low-order 2i bits of y�(22 i −(low-order 2i bits of b)). 2. Pad 2i-th to (2i+1−1)-th bits of y with low-order 2i bits of a. 3. Store 2i-th to (2n−2i−1)-th bits of xa+b in b. Step 4: Output y.
The substitution-permutation is a concept of a considerably broad meaning. To meet a demand for software implementation in recent years, there has widely been used the substitution-permutation in the following form: [ y 1 y 2 ⋮ y m ] = P [ s 1 ( x 1 ) s 2 ( x 2 ) ⋮ s n ( x n ) ] ( 17 ) In this instance, operations are all performed over the ring R. The permutation is given by P = [ p 11 p 12 ⋯ p 1 n p 21 p 22 ⋯ p 2 n ⋮ ⋮ ⋱ ⋮ p m1 p m2 ⋯ p mn ] ( 18 ) and the substitution is set to sj:R→R (j=1, 2, . . . , n). That is, the product of the matrix is considered as permutation.
The substitution-permutation expressed by Eq. (17) is also used in the cipher SHARK that is defined in V. Rijmen, et al. �The Cipher SHARK,� Fast Software Encryption-Third International Workshop, Lecture Notes in Computer Science 1039, pp. 99-111, Springer-Verlag 1996 (hereinafter referred to simply as Literature S). In Literature S there is also described a method in which the following modified equation is used [ p 11 p 12 ⋯ p 1 n p 21 p 22 ⋯ p 2 n ⋮ ⋮ ⋱ ⋮ p m1 p m2 ⋯ p mn ] [ s 1 ( x 1 ) s 2 ( x 2 ) ⋮ s n ( x n ) ] = [ p 11 s 1 ( x 1 ) p 21 s 1 ( x 1 ) ⋮ p m1 s 1 ( x 1 ) ] + [ p 12 s 2 ( x 2 ) p 22 s 2 ( x 2 ) ⋮ p m2 s 2 ( x 2 ) ] + � + [ p 1 n s n ( x n ) p 2 n s n ( x n ) ⋮ p mn s n ( x n ) ] ( 19 ) and the output value of the function SPi expressed by the following equation (20) is precalculated corresponding to every xj and prestored, for example, in a memory to thereby efficiently calculate Eq. (17). SP j : R → R m ; SP j ( x j ) = [ p 1 j s j ( x j ) p 2 j s j ( x j ) ⋮ p mj s j ( x j ) ] ( 20 ) (j=1, 2, . . . , n)
In the cipher utilizing the substitution-permutation scheme, there is a case where no permutation is performed at the end of processing but only substitution is used. That is, the following processing is also necessary for cipher implementation. [ y 1 y 2 ⋮ y n ] = [ s 1 ( x 1 ) s 2 ( x 2 ) ⋮ s n ( x n ) ] ( 21 ) When the size of the element in R is smaller than the word length that is the operation unit in the computer used, it is necessary in straightforward implementation that the calculation of individual values of sj(xj) be followed by shifting them to their correct vector positions. In this instance, the necessity for the data position adjustment process can be avoided by Modifying Eq. (21) to [ y 1 y 2 ⋮ ⋮ y n ] = [ s 1 ( x 1 ) 0 ⋮ ⋮ 0 ] + [ 0 s 2 ( x 2 ) 0 ⋮ 0 ] + � + [ 0 ⋮ ⋮ 0 s n ( x n ) ] ( 22 ) as is the case with Eq. (17) and by precalculating a table in which the positions of vector elements have been adjusted so that 0s would be provided except at the j-th position.
a5 = u5 + u1 b1 = u1 + a7 u5′ = a5 + b4 u1′ = b1 + u5′ a6 = u6 + u2 b2 = u2 + a8 u6′ = a6 + b4 u2′ = b2 + u6′ a7 = u7 + u3 b3 = u3 + a5 u7′ = a7 + b4 u3′ = b3 + u7′ a8 = u8 + u4 b4 = u4 + a6 u8′ = a8 + b4 u4′ = b4 + u8′ The computational complexity of this scheme is as follows:
According to a first aspect of the present invention, there is provided a data permutation method by which, letting one byte be k-bit, k being an integer equal to or greater than 1, input data of 16 bytes set, in units of four bytes, in 4 k-bit long first to fourth registers is permutated, the method comprising the steps of:
Alternatively, according to a first aspect of the present invention, there is provided a data permutation method by which, letting one byte be k-bit, k being an integer equal to or greater than 1, input data of 16 bytes set, in units of four bytes, in 4 k-bit long first to fourth registers is permutated, the method comprising the steps of:
y-updating means for calculating y+a�2^(2i) using said a, y and i stored in said storage means and updating said y stored in said storage means with the calculation result (where p^q represents the q-th power of p);
a-updating means for calculating −by by using said b and y stored in said storage means and for updating said a stored in said storage means with the calculation result;
b-updating means for calculating [(b+ax)/(2^(2i))] by using a, b, x and i stored in said storage means and for updating said b stored in said storage means;
y-updating means for calculating y+a�2^(2i) by using said a, y and i stored in said storage means and for updating said y stored in said storage means with the calculation result;
According to a third aspect of the present invention, there is provided 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 ] p ij εR, s j :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:
uk*Sk calculating means for reading out said wk from said storage means and calculating the product for each element and for updating said wk with the calculation result;
Alternatively, according to a third aspect of the present invention, 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 ] p ij εR, s j :R→R
i=1, 2, . . . , m j=1, 2, . . . , n performs a substitution-permutation operation of an input data sequence (xj) to produce a data sequence (yi), comprisies:
storage means for storing a precalculated value of the following equation with rows of a matrix P rearranged SP 1 j ( x j ) = [ p t ( q1 ) j s j ( x j ) p t ( q1 + 1 ) j s j ( x j ) ⋮ p t ( r1 ) j s j ( x j ) ] (where b(j) is a natural number equal to or greater than 1 but equal to or smaller than m, l=1, 2, . . . , b(j), t:{1, 2, . . . , m}→{1, 2, . . . , m} is permutation, and ql and rl are natural numbers equal to or greater than 1 but equal to or smaller than n, ql≦rl) together with precalculated values of n vectors wkεRm and an integer k;
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 (where l=1, 2, . . . , b(j)) 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;
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.
According to a fourth aspect of the present invention, there is provided a permutation method in which an operating apparatus including an accumulator type CPU and registers is used to permute input data u1, u2, . . . , un by the following equation using an m by n matrix P of predetermined {0, 1} elements to obtain permuted data (u1′, u2′, . . . , um′) [ u 1 ′ u 2 ′ ⋮ u n ′ ] = P [ u 1 u 2 ⋮ u n ] said method comprising the steps of:
u j ′=u i ′+D i where j≠i, i and j are integers equal to or greater than 1 and equal to or smaller than n, n is an integer equal to or greater than 2 and Di is given by the difference Di=uj′−ui′ between said permuted data uj′ and ui′ defined by said matrix P using said input data u1, u2, . . . , un; and
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiment 1 A description will be given first of the procedure by the present invention which facilitates the operation in the byte permutation part, that is, the BP function part 13 in FIG. 1 in the cipher E2. In the following description, 16 pieces of input k-bit byte data will be identified as a0, a1, . . . , a15, and permutated output data as A1, A2, A3, A4. The BP function part 13 is supplied with 16 pieces of 1-byte input data a0, a1, . . . , a15 and outputs byte-permutated data as right and left data. In this embodiment the arrangement of output data is appropriately chosen and the permutation for rearranging the data as chosen is performed by a procedure involving a smaller number of steps than in the prior art.
In this embodiment, the four pieces of data {a4i+j} (where 0≦j≦3) are stored as a4i+0, a4i+1, a4i+2, a4i+3 in each 4 k-bit register Ti (where i=0, 1, 2, 3) shown in FIG. 8; the four pieces of data are included in 16 pieces of k-bit data {a4i+j} (where 0≦i≦3, 0≦j≦3) which are input into the BP function part 13 (FIG. 1). The data stored in this form will hereinafter be described as follows:
The left data set [L] and the right data set [R] at the output of the BP function part 13 are defined in the cipher E2 as follows: [ L ] = { a 4 ( i + j mod 4 ) + j  0 ≤ i ≤ 1 , 0 ≤ j ≤ 3 } = { a 0 , a 3 , a 4 , a 5 , a 9 , a 10 , a 14 , a 15 } ( 25 A ) [ R ] = { a 4 ( i + j mod 4 ) + j  2 ≤ i ≤ 3 , 0 ≤ j ≤ 3 } = { a 1 , a 2 , a 6 , a 7 , a 8 , a 11 , a 12 , a 13 } ( 25 B ) This embodiment also performs the permutation and division of data accordingly. Incidentally, in the specification of the cipher E2, it does not matter even if the right and left data sets differ in the order of 8-byte data; hence, in the present invention, the order of data in either of the right and left data sets is chosen as to achieve the intended reduction of the computational complexity in the permutation using masking operations and in the permutation using shift operations.
The input 16-byte data a0, a1 . . . , a15 is rearranged not on such a byte-by-byte basis as depicted in FIG. 3 but, for example, every two bytes as depicted in FIG. 6 or 7. This permits reduction of procedure steps as described below.
FIG. 8 depicts the procedure by which the byte permutation shown in FIG. 6 is performed using mask data. The registers T0, T1, . . . , T3 are 4 k-bit long registers, which are used to permute and divide 16 pieces of k-bit data {a4i+j} (0≦i≦3, 0≦j≦3) into a set {a4(i+j mod 4)+j} (0≦i≦1, 0≦j≦3) and a set {a4(i+j mod 4)+j} (2≦i≦3, 0≦j≦3) as described below.
Step 3: Data (a0, O, O, a3) obtained by ANDing the value (a0,a1,a2,a3) of the register T0 and mask data (24k−23k+2k−1)=(I, O, O, I) of a mask register MRG0′ is stored in a register T0″; data (O, a9, a10, O) obtained by ANDing the value (a8,a9,a10,a11) of the register T2 and mask data (23k−2k)=(O, I, I, O) of a mask register MRG2′ is stored in a register T2″; and the OR (a0, a9, a10, a3) of the values of the registers T0″ and T2″ is stored in a register T6.
A 1=(z 1ff0000ff)(z 300ffff00) A 2=(z 2ffff0000)(z 40000ffff) A 3=(z 3ff0000ff)(z 100ffff00) A 4=(z 4ffff0000)(z 20000ffff) (26)
As is evident from the above equation, the numbers of AND and OR operations using mask data involved in obtaining the permuted outputs A1, A2, A3, A4 are eight and four, which are smaller than in the prior art example described previously with reference to Eq. (16).
Each register Ti is 4 k-bit long and k=8 in this example, too. This is a data permutation-division method which permute and divide 16 pieces of k-bit data {a4i+j} (0≦i≦3, 0≦j≦3) into a set {a4(i+j mod 4)+j} (0≦i≦1, 0≦j≦3) and a set {a4(i+j mod 4)+j} (2≦i≦3, 0≦j≦3).
Step 2: The values of (a0,a1,a2,a3) and (a8, a9, a10, a11) of the registers T0 and T2 are rotated k-bit in one direction, in this example, to right.
Step 3: The registers T0 and T2 are concatenated into an apparently 8 k-bit long register T0′; its data is shifted left 2 k bits and then 4 k-bit data (a1,a2,a11,a8) extracted from the register at the end in the shift direction is stored in the register T4. The registers T1 and T3 are concatenated into an apparently 8 k-bit long register T2′; its data is shifted left 2 k bits and then 4 k-bit data (a6,a7,a12,a13) extracted from the register at the end in the shift direction is stored in the register T5.
Step 4: The registers T2 and T0 are concatenated into an apparently 8 k-bit long register T0″; its data is shifted right 2 k bits and then 4 k-bit data (a9,a10,a3,a0) extracted from the register at the end in the shift direction is stored in the register T6. The registers T3 and T1 are concatenated into an apparently 8 k-bit long register T2″; its data is shifted right 2 k bits and then 4 k-bit data (a14,a15,a4,a5) extracted from the register at the end in the shift direction is stored in the register T7.
x<<b: b-bit left shift of x x>>b: b-bit right shift of x ROL(x,y)=(x<<b)(x>>(w−k)), where w is the number of bits of x. ROR(x,b)=(x>>b)(x<<(w−b)), where w is the number of bits of x. SHLD(x,y,b)=(x<<b)(y>>(w−b)), where w is the number of bits of y. SHRD(x,y,b)=(x>>b)(y<<(w−b)), where w is the number of bits of y. A 1 =SHRD(ROR(z 3 , k),ROR(z 1 , k),2k) A 2 =SHRD(z 4 ,z 2,2k) A 3 =SHLD(ROR(z 1 ,k),ROR(z 3 ,k),2k) A 4 =SHLD(z 2 ,z 4,2k) (27)
With this method, the permuted results A1, A2, A3, A4 obtained by two cyclic shifts and four concatenated shifts.
A 2 =SHRD(z 4 , z 2, 2k) A 4 =SHLD(z 2 , z 4, 2k) (28)
A 1 =SHRD(ROR(z 3 ,k), ROR(z 1 ,k),2k) A 3 =SHLD(ROR(z 1 ,k), ROR(z 3 ,k),2k) (29)
A 2=(z 40000ffff)(z 2ffff0000)=(a 4 ,a 5 ,a 14 ,a 15) A 4=(z 20000ffff)(z 4ffff0000)=(a 12 ,a 13 ,a 6 ,a 7) (30)
A 1=(z 300ffff00)(z 1ff0000ff)=(a 0 ,a 9 , a 10 ,a 3) A 3=(z 100ffff00)(z 3ff0000ff)=(a8 ,a 1 ,a 2 , a 11) (31)
z 1=(A 1ff0000ff)(A 300ffff00) z 2=(A 2ffff0000)(A 40000ffff) z 3=(A 3ff0000ff)(A 100ffff00) z 4=(A 4ffff0000)(A20000ffff) (32)
z 1 =ROL(SHLD(A 1 ,A 3,2k),k) z 2 =SHLD(A 2 ,A 4,2k) z 3 =ROL(SHRD(A 1 ,A 3,2k),k) z 4 =SHRD(A 2,A4,2k) (33)
In an MPU on which such instructions are not concretely implemented, they can be substituted with two masking instructions and one ORing instruction. That is, while in the above the permuted data A1 in Eq. (27) has been described to be calculated by the processing in which the registers T2 and T0 after the cyclic shift are concatenated into a virtually 8 k-bit long register T0″ and the data of the rightmost 4 k-bit data of the register T0″ after the 2 k-bit right shift is stored as the data A1 of the register T6, the permuted data A1 can also be obtained by such processing as indicated by Eq. (31), in which data (O, a9, a10, O) obtained by ANDing data z3 of the register T2 and mask data (23k−2k)=(00ffff00) is stored in a register T1″ (not shown), data (a0, O, O, a3) obtained by ANDing data z1 of the register T0 and mask data (24k−23k+2k−1)=(ff0000ff) is stored in a register T3″ (not shown) and the value (a0, a9, a10, a3) obtained ORing the data of the register T1″ and the data of the register T3″ is stored in the register T6. The operation for the data A3 in Eq. (31) can also be made in a similar way. The operation does not involve the execution of any cyclic shift instruction, and hence it can be described by a total of 12 instructions, ensuring faster operation of the BP function than does the prior art.
That is, this embodiment calculates an inverse element y=x−1 mod 2m of the input x. Let a and b be temporary variables, m=2n (n≧1) and m be bit lengths of x, y, a and b. According to this embodiment, x is input and stored in storage means, followed by an initial process which: reads out x; calculates [x/2]; stores the calculated result as b in the storage means; stores the least significant bit as a in the storage means; reads out a, x and b; calculates [(ax+b)/2]; updates b with the calculated result; reads out x; and stores low-order two bits of x as y in the storage means.
2-1. b:=[x/2] 2-2. a:=the least significant bit of b (S2 in FIG. 11) 2-3. b:=[(ax+b)/2] 2-4. y:=low-order two bits of x (S3 in FIG. 11) 2-5. i:=1(S4 in FIG. 11) Step 3: Perform the following calculations for i=1, 2, . . . , n−1
3-1. a:=−by 3-2. b:=[(b+ax)/(2^(2i))] 3-3. y:=y+a�2^(2i) (S5 in FIG. 11) 3-4. i:=i+1 (S6 in FIG. 11) Step 4: Output y.
In Step 2, substeps 2-1, 2-2 and 2-3 are performed in this order. Substeps 2-4 and 2-5 may be performed at arbitrary timing in Step 2. Step 3 may be performed in the order 3-1→3-2→3-3 or 3-1→3-3→3-2, but on recent computers it is preferable from their data dependency to perform step 3 in the order 3-1→3-2→3-3. When i=n−1, b is not necessary, and hence substep 3-2 need not be carried out. The loop of the algorithm may be described in a developed from of its interations in advance. (The number of iterations of the loop comes into play only on the order of the logarithm of the bit count of the inverse element to be calculated.) With the loop described in advance, it is possible to make the inverse calculation faster by precalculating i-dependent constants. On ordinary processors divisions and multiplications by 2n can be made faster by shift operations. The validity of the above inverse calculation algorithm is described in the Appendix to this specification
By y-updating means 32A8 the stored data a, y and i in the storage device 32B are read out therefrom, and y+a�2^(2i) is calculated, with which the stored data y in the y-storage area 32B2 is updated. By i-updating means 32A9 the stored data i in the storage device 32B is read out therefrom, and i+1 is calculated, with which the stored data i in the i-storage area 32B5 is updated.
(1) Some of pieces of data pij or sj are equal. (2) Even if columns of the input or output are swapped or exchanged, the swap can be accommodated at a different part without decreasing the processing speed, and hence it can be transformed equivalently in terms of algorithm. (3) The element of Rn is stored in a register for storing a word that is the calculation unit on a computer, and can be calculated for each element. Since the property (3) is implemented on recent processors as typified by an MMX instruction implemented on Intel processors, and since R is widely used which permits the element-by-element calculation of Rn by and AND operation feasible on almost all processors, the property is considered to be a practical assumption.
That is, according to this embodiment, when some of pieces of data pij or sj are equal to one another in the afore-mentioned equations (17) and (18) expressing the substitution and permutation on the ring R [ y 1 y 2 ⋮ y m ] = P [ s 1 ( x 1 ) s 2 ( x 2 ) ⋮ s n ( x n ) ) ( 17 ) where P = [ p 11 p 12 ⋯ p 1 n p 21 p 22 ⋯ p 2 n ⋮ ⋮ ⋱ ⋮ p m1 p m2 ⋯ p mn ] ( 18 ) p ij εR, s j :R→R
i=1, 2, . . . , m j=1, 2, . . . , n rows of the matrix P expressing the permutation are rearranged, then vector v1εRr (The dimension r is up to m and the vectors may differ in dimension.) on the ring R and the function Sk:R→Rr (where k=1, 2, . . . , n, r≦m), which are necessary for the substitution and permutation, are precalcuated for each xi, and the precalculated values are stored in storage means. For the input xi: Sk is read out of the storage means, and a vector Sk(xi) is calculated; a set of vectors {vi} necessary for forming a k-th column of the matrix P is read out of the storage means and a vector uk is generated; then uk*Sk(xi) (where * is the product for each vector element) is calculated, and these values are added together to obtain a data sequence yi.
Consider the case of calculating Eq. (17). When all pieces of data sj are the same s, setting v j = [ p 1 j p 2 j ⋮ p mj ] j = 1 , 2 , � , n ( 32 ) S : R → R m ; S ( x ) = [ s ( x ) s ( x ) ⋮ s ( x ) ] ( 33 ) enables Eq. (20) to be written as follows: SP : R → R m ; SPj ( x ) = [ p 1 j s ( x j ) p 2 j s ( x j ) ⋮ p mj s ( x j ) ] = v j * S ( x j ) , j = 1 , 2 , � , n ( 34 ) where * is the product for each element of the vector.
From the above it will be understood that, by precalculating S and prestoring the calculated value in a memory, Eq. (17) can be calculated with n memory references for x1 to xn, n multiplications to obtain the product * for each vector element and n−1 additions of n column vectors. The prior art stores SP1 to SPn, but this embodiment stores only S and hence reduces the amount of data stored down to 1/n.
Consider the case of calculating Eq. (17) in an environment where the calculation unit is smaller than R[(m+1)/2] (where [(m+1)/2] is the maximum integer not exceeding (m+1)/2). The following example is applicable to ordinary matrices P. To facilitate a better understanding of the invention, consider the application of the invention to the case of the following matrix (Eq. 35) used in the cipher E2, that is, to the substitution and permutation (Eq. 36). P = [ 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 ] ( 35 ) [ y 0 y 1 y 2 y 3 y 4 y 5 y 6 y 7 ] = [ 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 ] [ s ( x 0 ) s ( x 1 ) s ( x 2 ) s ( x 3 ) s ( x 4 ) s ( x 5 ) s ( x 6 ) s ( x 7 ) ] ( 36 ) The horizontal line in the matrix of Eq. (36) is intended only to make it easy to see. It should be noted that a substitution with no permutation is also needed at the end of the operation in the cipher E2.
Required memory capacity: 10 Number of table references: 12 Number of additions: 11 As compared with the method described in Literature S, the method of this embodiment permits reduction of all of the memory capacity, the number of table references and the number of additions. It must be noted here that the arrangement of yi(0≦i≦7) on the left-hand side of Eq. (37) does not impair performance.
As is the case with Embodiment 3-2, the order of calculation is changed by swapping rows of the matrix P as follows: [ y 0 y 1 y 3 y 2 y 6 y 7 y 5 y 4 ] = [ 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 0 0 ] [ s ( x 0 ) s ( x 1 ) s ( x 2 ) s ( x 3 ) s ( x 4 ) s ( x 5 ) s ( x 6 ) s ( x 7 ) ] ( 39 ) In the processing for x4, x5, x6, x7: as regards y0, y1, y3, y2, memory-stored reference tables are used intact; and as for y6, y7, y5 and y4, values read out of the memory-stored reference tables for y0, y1, y3 and y2 are shifted down one element, down two elements, up one element and up two elements, respectively. That is, the leftmost column vector of the upper right submatrix of the matrix P is shifted down one element to obtain the leftmost column vector of the lower right submatrix, then the column vector second from the left-hand side of the upper right submatrix is shifted down two elements to obtain the column vector second from the left-hand side of the lower right submatrix, and thereafter the column vectors third and fourth from the left-hand side of the upper right submatrix are shifted up one element and two elements, respectively, to obtain the column vectors third and fourth from the left-hand side of the lower right submatrix.
T←SP 0(x 0)+SP 1(x 1)+SP 3(x 2)+SP 2(x 3) U 0 ←SP 1(x 4) U 1 ←SP 3(x 5) U 2 ←SP 2(x 6) U 3 ←SP 0(x 7) (40)
the following calculations can be conducted: [ y 0 y 1 y 3 y 2 ] ← T + U 0 + U 1 + U 2 + U 3 ( 41 ) [ y 6 y 7 y 5 y 4 ] ← T + SD 1 ( U 0 ) + SD 2 ( U 1 ) + SU 1 ( U 2 ) + SU 2 ( U 3 ) ( 42 ) Accordingly, this embodiment also reduces the computation cost as compared with the method of Literature S in terms of the memory capacity, the number of memory references and the number of additions as follows:
Required memory capacity: 8 Number of table references: 8 Number of additions: 11 Number of shifts: 4
In this embodiment, too, it should be noted that the arrangement of yi(0≦i≦7) on the left-hand side does not incur performance degradation.
As is the case with Embodiment 3-3, respective rows of the matrix P are swapped to obtain [ y 0 y 1 y 2 y 3 y 6 y 7 y 4 y 5 ] = [ 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 ] [ s ( x 0 ) s ( x 1 ) s ( x 2 ) s ( x 3 ) s ( x 4 ) s ( x 5 ) s ( x 6 ) s ( x 7 ) ] ( 43 ) Note the upper right and lower right submatrices of the above matrix. Q U = [ 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 ] , Q D = [ 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 0 ] ( 44 ) In this instance, the following equation holds: Q U - Q D = [ 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 ] = SD 1 ( Q U ) + SU 3 ( Q U ) ( 45 ) It must be noted here that a ring of a character 2 is considered as R.
T←SP 0(x 0)+SP 1(x 1)+SP 2(x 2)+SP 3(x 3)
U←SP 1(x 4)+SP 2(x 5)+SP 3(x 6)+SP 0(x 7) [ y 0 y 1 y 2 y 3 ] ← T + U [ y 6 y 7 y 4 y 5 ] ← [ y 0 y 1 y 2 y 3 ] - SD 1 ( U ) - SD 3 ( U ) ( 46 ) In this case, the computation cost is as follows:
Number of additions/subtractions (for calculation of +):9
Thus, this embodiment permits further reduction of the number of additions/subtractions and the number of shifts than does embodiment 3-3.
RD k(x)=SD k(x)+SU n−k(x)
In this instance, by using the downward shift for the calculation of Eq. (46) in Embodiment 3-4, the following equation can be conducted. [ y 6 y 7 y 4 y 5 ] ← [ y 0 y 1 y 2 y 3 ] - RD 1 ( U ) ( 47 ) The computation cost in this case is as follows:
Number of table references (for calculation of SPj): 8 Number of additions (for � calculation): 8 Number of rotations (for calculation of RD): 1
FIG. 14 there is depicted the functional configuration of Embodiment 3-2, in which the parts corresponding to those in FIG. 13 are denoted by the same reference numerals. The vk-storage area 32B14 and the Sk-storage area 32B1 in FIG. 13 are substituted with SPk-storage area 32B31, in which SPk is stored. By SPk calculating means 32A32 SPk(xi) is calculated in accordance with the input data xi, and the calculated value is stored as the vector wk in the wk-storage area 32B16. Embodiment 3-2 is identical in construction with Embodiment 3-1 except the above.
Embodiment 4 With the calculation scheme as defined by Eq. (10), upon each calculation of ui′, the calculated value is discarded and the next ui′ is calculated by newly conducting an addition and a subtraction. However, since the defining equation for calculating each ui′ contains two or more components common to those of the defining equation for calculating another ui′, that is, since the both defining equations are similar to some extent, it is possible to utilize the previous calculated value by expressing the current value ui′ as ui′=uj′+Di using its difference Di from the previous calculated value uj′. This embodiment is intended to reduce the number of times the memory is read.
u 1 ′=u 2 +u 3 +u 4 +u 5 +u 6 +u 7 u 2 ′=u 1 ′+u 1 −u 2 −u 5 +u 8 u 3 ′=u 2 ′+u 2 −u 3 +u 5 −u 6 u 4 ′=u 3 ′+u 3 −u 4 +u 6 −u 7 u 5 ′=u 4 ′−u 3 +u 4 −u 8 u 6 ′=u 5 ′+u 3 −u 4 −u 5 +u 7 u 7 ′=u 6 ′−u 1 +u 4 −u 6 +u 8 u 8 ′=u 7 ′+u 1 −u 2 +u 5 −u 7 (48)
u 6 ′=u 1 +u 2 +u 3 +u 6 +u 7 u 4 ′=u 6 ′+u 5 −u 7 +u 8 u 5 ′=u 4 ′−u 3 +u 4 −u 8 u 3 ′=u 5 ′−u 6 +u 7 +u 8 u 8 ′=u 3 ′−u 2 +u 3 −u 7 u 2 ′=u 8 ′−u 5 +u 6 +u 7 u 7 ′=u 2 ′−u 1 +u 2 −u 6 u 1 ′=u 7 ′+u 5 +u 6 −u 8 (49)
Number of additions/subtractions: 25 Number of memory reads: 26 Number of memory writes: 8
On the other hand, when the total number of �1� component in the matrix P is large, it is expected to provide an order of calculation that decreases the difference between ui′ and u′j as a whole, and in almost all cases it is implemented with the minimum number of memory reads. For example, in the case of Embodiment 4-2, there is such a method that uj′ can be derived from ui′ by three pieces of uk are read out of memories. In general, the number of memory reads necessary for obtaining ui 40 from σ by the conventional Scheme 3 may be considered to be equal to or larger than the minimum number of memory reads in Embodiment 4-2. It can be safely said, therefore, that this embodiment is smaller, in almost all cases, than Scheme 3 in the total number of memory reads necessary for obtaining all ui′ (where i=1, 2, . . . , 8)
Letting C be a natural number and n be a natural number equal to or greater than 1, C = c 0 + ∑ i = 1 n c i 2 2 i - 1 In the following each variable has a bit size of 2n; therefore, mod 22 n will be omitted unless any particular problems arise. In principle, numbers themselves will be written in uppercase alphabetic characters and individual digits in the development will be in lower-case alphabetic characters (with some exceptions).
Algorithm 1 is shown below: mod inv1(X) {
a0 = x0 −1 mod 2;
B0 = [Xa0 mod 22 n /2];
for(i = 0; i ≦ n − 1;i ++){
βi = Bimod 22 i ;
ai+1 = −β1Yi mod 22 i ;
Yi+1 = Yi + ai+1 � 22 i; Bi+1 = [(Xai+1 + Bi)mod 22 n −2 i /22 i ];
XY n≡1 (mod22 n )
z=[x/y]x=yz+x mody (2)
(Xa k+1 +B k)mod 22 n −2 k =B k+122 k +(Xa k+1 +B k) mod 22 k Multiplying the both sides by 22 k , we have
22 k (Xa k+1 +B k)mod 22 n =B k+122 k+1 +22 k (Xa k+1 +B k) mod 22 k+1 (3)
(XY k+1 −R)mod 22 n =B k+122 k+1 +(XY k+1 −R)mod 22 k+1 (4)
XY k+1 mod 22 n −R=B k+122 k+1 +XY k+1 mod 22 k+1 −R and eliminate R from either side. Noting that
Proof. It is sufficient to prove that XYi=1 mod 22 i for each i. For i=0, the answer is evident from the algorithm. For each k≧0 assume that the statement is true for i=k. For i=k+1, we have XY k + 1 mod2 2 k + 1 = X ( a k + 1 2 2 k + Y k ) mod2 2 k + 1 = ( X ( - β k Y k mod2 2 k ) 2 2 k + Y k ) mod2 2 k + 1 = ( - X β k Y k mod2 2 k ) 2 2 k + XY k mod2 2 k + 1 We have XYk=1 mod 22 k using the induction hypothesis, and (Bk mod 22 k )22 k =βk22 k using Bk=[XYk mod 22 n /22 k ] from the lemma.
Therefore, XYk mod 22 k+1 =βk22 k +1 holds. Finally we obtain X Y k + 1 m o d 2 2 k + 1 = ( - X β k Y k m o d 2 2 k ) 2 2 k + β k 2 2 k + 1 = ( ( β k ( 1 - X Y k ) ) m o d 2 2 k ) 2 2 k + 1 = ( ( β k ( 1 - 1 ) ) m o d 2 2 k ) 2 2 k + 1 = 1 2. Algorithm 2
B1 [(XA1 + B0)/2];
for(i = 1;i ≦ n − 1;i++){
Yi+1 = Yi + Ai+1 � 22 i ;
XY n≡1(mod 22 n )
C i=0 mod 22 i−1 (5) B i = B i ( 0 ) + X � C i 2 2 i - 1 ( 6 ) Y i =Y i (0) +C i �2 2 i−1 (7)
A k+1 =−B k Y k is calculated. As the calculation continues, we have A k + 1 = - ( B k ( 0 ) + X C k 2 2 k - 1 ) ( Y k ( 0 ) + C k � 2 2 k - 1 ) = - B k ( 0 ) Y k ( 0 ) - Y k ( 0 ) X C k 2 2 k - 1 - B k ( 0 ) C k � 2 2 k - 1 - X C k C k = a k + 1 ( 0 ) + D k + 1 - Y k ( 0 ) X C k 2 2 k - 1 - B k ( 0 ) C k � 2 2 k - 1 - X C k C k From Algorithm 1, a k + 1 ( 0 ) = - β k Y k m o d 2 2 k = - β k Y k m o d 2 2 k and D k + 1 = [ - β k Y k / 2 2 k ] � 2 2 k That is, low-order 2k bit portion of −BkYk is expressed by a k + 1 ( 0 ) , and the high order is expressed by Dk+1. Note that Dk+1 is Dk+1=0 mod 22 k like Ck.
From the above, we have Y k + 1 = Y k + A k + 1 � 2 2 k = Y k ( 0 ) + C k � 2 2 k - 1 + ( a k + 1 ( 0 ) + D k + 1 - Y k ( 0 ) X C k 2 2 k - 1 - B k ( 0 ) C k � 2 2 k - 1 - X C k C k ) � 2 2 k = Y k ( 0 ) + a k + 1 ( 0 ) � 2 2 k + ( C k 2 2 k - 1 D k + 1 - Y k ( 0 ) X C k 2 2 k - 1 - B k ( 0 ) C k � 2 2 k - 1 - X C k C k ) � 2 2 k = Y k + 1 ( 0 ) + ( C k 2 2 k - 1 D k + 1 - Y k ( 0 ) X C k 2 2 k - 1 - B k ( 0 ) C k � 2 2 k - 1 - X C k C k ) � 2 2 k Now, set C k + 1 = ( C k 2 2 k - 1 + D k + 1 - Y k ( 0 ) X C k 2 2 k - 1 - B k ( 0 ) C k � 2 2 k - 1 - X C k C k ) mod 2 2 n - 2 k Since each of individual variables has a bit size of 2n and since the second term on the right-hand side of the above has been multiplied by 22 k , we see that even if Ck+1 is calculated under modulo 22 n −2 k , the following equation holds: Y k + 1 = Y k + 1 ( 0 ) + C k + 1 � 2 2 k ( 8 ) Next we wll show that Ck+1 satisfies Eq. (5), that Ck+1 satisfied Eq. (5), that is, Ck+1 is a multiple of 22 k . Since Ck=0 mod 22 k−1 , it is clear that XCkCk=0 mod 22 k and that Bk (0)Ck�22 k−1 =0 mod 22 k . And, as mentioned previously, Dk+1=0 mod 22 k . Now, C k 2 2 k - 1 - Y k ( 0 ) X C k 2 2 k - 1 = C k 2 2 k - 1 ( 1 - Y k ( 0 ) X ) but since XYk (0)=1 mod 22 k from the lemma, we have
(1−Y k (0) X)=0 mod 22 k Using Ck=0 mod 22 k−1 , we have C k 2 2 k - 1 ( 1 - Y k ( 0 ) X ) = 0 m o d 2 2 k . Thus it is proved that
XA k+1 +B k =B k+1�22 k +(XA k+1 +B k)mod 22 k Since the bit size of each variable is 2n, and since Bk+1 is multiplied by 22 k , there exist no problem even if the both sides are calculated under modulo 22 n −2 k . Accordingly, we have
(XA k+1 +B k)mod 22 n −2 k =B k+1�22 k +(XA k+1 +B k) mod 22 k (10)
Then we have X A k + 1 + B k = X ( a k + 1 ( 0 ) + D k + 1 - Y k ( 0 ) X C k 2 2 k - 1 - B k ( 0 ) C k � 2 2 k - 1 - X C k C k ) + B k ( 0 ) + X � C k 2 2 k - 1 = X a k + 1 ( 0 ) + B k ( 0 ) + X ( C k 2 2 k - 1 + D k + 1 - Y k ( 0 ) X C k 2 2 k - 1 - B k ( 0 ) C k � 2 2 k - 1 - X C k C k ) Hence the left-hand side of Eq. (10) becomes as follows:
(XA k+1 +B k)mod 22 n −2 k =(Xa k+1 (0) +B k (0))mod 22 n −2 k +XC k−1 Furthermore, using Eq. (9), the second term on the right-hand side of Eq. (10) becomes as follows: ( X A k + 1 + B k ) m o d 2 2 k = ( X a k + 1 ( 0 ) + B k ( 0 ) + C k + 1 ) m o d 2 2 k = ( X a k + 1 ( 0 ) + B k ( 0 ) ) m o d 2 2 k Therefore, we have ( X a k + 1 ( 0 ) + B k ( 0 ) ) m o d 2 2 n - 2 k + X C k + 1 = B k + 1 � 2 2 k + ( X a k + 1 ( 0 ) + B k ( 0 ) ) m o d 2 2 k and ( X a k + 1 ( 0 ) + B k ( 0 ) ) m o d 2 2 n - 2 k = ( B k + 1 - X C k + 1 2 2 k ) � 2 2 k + ( X a k + 1 ( 0 ) + B k ( 0 ) ) m o d 2 2 k And the following equation holds: B k + 1 - X C k + 1 2 2 k = [ ( X a k + 1 ( 0 ) + B k ( 0 ) ) m o d 2 2 n - 2 k / 2 2 k ] B k + 1 ( 0 ) Thus the following is proved: B k + 1 = B k + 1 ( 0 ) + X C k + 1 2 2 k ( 11 ) From the above, Eqs. (5), (6) and (7) hold also when i=k+1. For i=n, since the �garbage� Cn�22 n becomes a multiple of 2{overscore (2)} k , and each variables has a bit size of 2n, we obtain Yn=Yn (0); from the proposition
XY n=1 mod 22 n holds. Thus the proposition is proved. (Q.E.D.)
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5519647 *May 11, 1994May 21, 1996U.S. Philips CorporationApparatus for and method of generating an approximation functionUS5539827Apr 5, 1995Jul 23, 1996Liu; ZunquanDevice and method for data encryptionUS5687238Dec 21, 1995Nov 11, 1997Nec CorporationSmall size product cipher apparatusUS5825886Dec 5, 1996Oct 20, 1998Entrust Technologies Ltd.Construction symmetric ciphers using the cast design procedureUS5928310 *Aug 28, 1997Jul 27, 1999Unisys CorporationDigital device control method and system via linear function generator implementation using adder for interceptUS6298136May 20, 1997Oct 2, 2001U.S. Philips CorporationCryptographic method and apparatus for non-linearly merging a data block and a keyUS6408075Mar 14, 2000Jun 18, 2002Hitachi, Ltd.Information processing equipment and IC cardJPH1171255A Title not availableJPS60167062A Title not available* Cited by examinerNon-Patent CitationsReference1Aoki, Kazumaro et al., "Optimized Software Implementations of E2" Presented at the AES, pp. 1-11, undated.2Aoki, Kazumaro et al., "Software Implementations for E2", Proceedings of the 1999 Symposium on Cryptography and Information Security, vol. 2, Jan. 26-29, 1999, pp. 801-806.3Hans Zassenhaus, "On Hensel Factorization, I," Journal of Number Theory, vol. 1, pp. 291-311, 1969.4Kanda, Masayuki et al., "A New 128-bit Block Cipher E2", Technical Report of IEICE, The Institute of Electronics, Information and Communication Engineers, Jul. 1998.5Rijimen, Vincent et al., "The Cipher Shark", Fast Software Encryption, Dieter Gollmann, Ed., Springer, pp. 99-110, undated.6Schneiter, Bruce, Applied Crptography, 2nd Edition, John Wiley & Sons, Chapters 12.4-12.5, 14.10, and 15.5-15-6, pp. 285-293, 347, and 366-367, undated.7The Ciper Shark, Lecture Notes in Computer Science, Vincent Rijmen et al., vol. 1039, pp. 99-111, undated.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7680272 *Dec 23, 2004Mar 16, 2010Samsung Electronics Co., Ltd.Inverse calculation circuit, inverse calculation method, and storage medium encoded with computer-readable computer program code* Cited by examinerClassifications U.S. Classification708/270, 708/491International ClassificationG06F7/72, H04L9/06Cooperative ClassificationH04L2209/122, H04L2209/046, H04L9/0625, G06F7/726, G06F7/721, G06F7/728European ClassificationG06F7/72A, H04L9/06, H04L9/06B, H04L9/06R3Legal EventsDateCodeEventDescriptionJul 5, 2012FPAYFee paymentYear of fee payment: 8Jul 21, 2008FPAYFee paymentYear of fee payment: 4May 24, 2005CCCertificate of correctionRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google