A transposition processing unit having a k-partition generalized Feistel structure transposes Yb,u into Za,t if Ya,t (t=0, 1, . . . , s−1) is transposed into Zb,u (u=0, 1, . . . , s−1, u≠t), in a case where input data entered into the transposition processing unit is Y0, Y1, . . . , Yk−1 (n bits×k); output data from the transposition processing unit is Z0, Z1, . . . , Zk−1; Yi (i=0, 1, . . . , k−1) divided into s blocks (s=2, 4, . . . , n) is Yi, 0, Yi, 1, . . . , Yi, s−1; Zi divided into s blocks is Zi, 0, Zi, 1, . . . , Zi, s−1.