Patent ID: 7499541

Claim:
A cipher strength evaluation apparatus for evaluating strength on ciphertext outputted by a block encryption apparatus having a plurality of steps of accepting unstirred text, stirring with an extended key, and outputting stirred text for encrypting plaintext step by step, the cipher strength evaluation apparatus comprising: a receiving part for accepting decryption condition information about the number of plaintext available for cipher strength evaluation; a decryption equation information storing part for storing decryption equation information expressing a decryption equation that has a value of extended key forming bits to form an extended key as an unknown, the decryption equation holding when an unstirred text is at a first step of the plurality of steps and a stirred text is at a second step of the plurality of steps subsequent to the first step; a linearizing part for converting the decryption equation to a linearized decryption equation that has a value expressing higher-order terms of the extended key forming bits of the decryption equation as an independent unknown and outputting linearized decryption equation information expressing the linearized decryption equation, the linearized decryption equation being linear simultaneous equations; an estimating part for selecting a predetermined number of bits expressed by the decryption condition information from unknowns of the linearized decryption equation, estimating the value of bits selected from unknowns of the linearized decryption equation for temporary determination, and outputting an estimated unknown value expressing the estimated value of bits selected from unknowns of the linearized decryption equation; an optimizing part for outputting optimized decryption equation information, the optimized decryption equation information being information expressing an optimized linearized decryption equation, the optimized linearized decryption equation being an equation obtained by reducing unknowns by inputting the estimated unknown value to the linearized decryption equation and by reducing an element equation number, the element equation number being the number of element equations based on linear dependence between the element equations, the element equations being equations contained in the linearized decryption equation; an operation part for outputting evaluation information, the evaluation information being information expressing whether the optimized linearized decryption equation holds or not, and outputting extended key forming bit value information expressing a value of the unknown of the decryption equation when the optimized linearized decryption equation holds; and a control part for allowing the estimating part to calculate a new estimated unknown value when the evaluation information indicates that the optimized linearized decryption equation does not hold.