METHOD FOR DETERMINING A CRYPTOGRAPHIC KEY, COMPUTER PROGRAM, AND DATA PROCESSING SYSTEM

Abstract

A method for determining a cryptographic key is carried out in a data processing system, and comprises: providing a plaintext and a ciphertext determined from the plaintext using a cryptographic key and a cryptographic procedure which comprises cryptographic operations; for each cryptographic operation of the cryptographic procedure, providing at least one intermediate relation which comprises an intermediate equation and/or an intermediate inequality; determining an optimization problem comprising: the plaintext and the ciphertext; at least one optimization expression assigned to a round of the cryptographic procedure; and optimization variables comprising state variables of the cryptographic procedure and a cryptographic key variable; wherein the at least one optimization expression is determined from the at least one intermediate relation and comprises at least one preceding state variable assigned to a preceding round. The method further comprises: solving the optimization problem and determining the cryptographic key from an optimizing value of the cryptographic key variable.

Claims

1. A method for determining a cryptographic key, the method being carried out in a data processing system, the method comprising: providing a plaintext and a ciphertext determined from the plaintext using a cryptographic key and a cryptographic procedure which comprises cryptographic operations; for each cryptographic operation of the cryptographic procedure, providing at least one intermediate relation which comprises an intermediate equation and/or an intermediate inequality; determining an optimization problem comprising the plaintext and the ciphertext, at least one optimization expression assigned to a round of the cryptographic procedure, and optimization variables comprising state variables of the cryptographic procedure and a cryptographic key variable, wherein the at least one optimization expression is determined from the at least one intermediate relation and comprises at least one preceding state variable assigned to a preceding round; and solving the optimization problem and determining the cryptographic key from an optimizing value of the cryptographic key variable.

2. The method according to claim 1, wherein the cryptographic procedure is described in terms of Boolean functions on binary variables and/or is one of AES, IDEA, Salsa20, DES, 3-DES, and an ARX procedure.

3. The method according to claim 1, wherein the cryptographic operations comprise AES operations, preferably at least one of AddRoundKey, SubBytes, ShiftRows, MixColumns, and KeyExpansion.

4. The method according to claim 1, further comprising: determining an elementary operation of at least one of the cryptographic operations; from the elementary operation, determining an elementary relation comprising an elementary equation and/or an elementary inequality; and determining at least one intermediate relation from the elementary relation, wherein, preferably, the elementary operation is one of NOT, AND, OR, and XOR.

5. The method according to claim 4, wherein at least one elementary relation is determined by solving an elementary optimization problem, preferably an unconstrained quadratic problem.

6. The method according to claim 1, wherein at least one intermediate relation is provided by solving an intermediate optimization problem and/or corresponds to a Boolean function with more than one elementary operation.

7. The method according to claim 1, wherein at least one intermediate relation is provided by determining an H-representation of a convex polyhedron for one of the cryptographic operations.

8. The method according to claim 1, wherein at least one intermediate relation is provided by determining, for one of the cryptographic operations acting on a finite field, a further operation acting on a further finite field of lower order.

9. The method according to claim 1, wherein the optimization problem is a mixed-integer linear program, a mixed-integer nonlinear program, or a quadratic unconstrained binary optimization problem.

10. The method according to claim 1, wherein the optimization expression is an optimization constraint, or is contained in an objective function of the optimization problem.

11. The method according to claim 1, wherein the plaintext comprises a first plaintext and a second plaintext, and the ciphertext comprises a first ciphertext and a second ciphertext, wherein the first ciphertext has been determined from the first plaintext using the cryptographic key and the cryptographic procedure, and the second ciphertext has been determined from the second plaintext using the cryptographic key and the cryptographic procedure.

12. The method according to claim 1, wherein the optimization problem is at least partially solved in a quantum processing device of the data processing system, preferably a quantum annealing device.

13. The method according to claim 12, wherein the optimization variables are assigned to a superposition of quantum states.

14. A data processing system configured to determine a cryptographic key by performing the following steps: providing a plaintext and a ciphertext determined from the plaintext using a cryptographic key and a cryptographic procedure which comprises cryptographic operations; for each cryptographic operation of the cryptographic procedure, providing at least one intermediate relation which comprises an intermediate equation and/or an intermediate inequality; determining an optimization problem comprising the plaintext and the ciphertext, at least one optimization expression assigned to a round of the cryptographic procedure, and optimization variables comprising state variables of the cryptographic procedure and a cryptographic key variable, wherein the at least one optimization expression is determined from the at least one intermediate relation and comprises at least one preceding state variable assigned to a preceding round; and solving the optimization problem and determining the cryptographic key from an optimizing value of the cryptographic key variable.

Description

DESCRIPTION OF FURTHER EMBODIMENTS

[0051] In the following, embodiments, by way of example, are described with reference to figures.

[0052] FIG. 1 shows a graphical representation of a method for determining a cryptographic key,

[0053] FIG. 2 shows a graphical representation of a data processing system,

[0054] FIG. 3 shows a graphical representation of the AddRoundKey operation,

[0055] FIG. 4 shows a graphical representation of the SubBytes operation,

[0056] FIG. 5 shows a graphical representation of the MixColumns operation, and

[0057] FIG. 6 shows a graphical representation of the KeyExpansion operation.

[0058] In FIG. 1, a graphical representation of the (computer-implemented) method for determining a cryptographic key is shown. In a first step 11, a plaintext and a ciphertext by encrypting the plaintext using a cryptographic procedure are provided.

[0059] In a second step 12, at least one intermediate relation is provided for each cryptographic operation of the cryptographic procedure. In case of the cryptographic procedure being AES, the cryptographic operations are AddRoundKey, SubBytes, Shiftows, MixColumns, and KeyExpansion. Each intermediate relation can be an intermediate equation, or alternatively, an intermediate inequality. The intermediate equations can be determined by solving elementary optimization problems.

[0060] In a third step 13, after providing, in particular determining, the intermediate relations, an optimization problem such as a mixed-integer linear programming problem (MILP) or a quadratic unconstrained binary optimization (QUBO) problem is determined.

[0061] The optimization problem comprises a plurality of optimization expressions established from the intermediate relations and assigned to each round of the cryptographic procedure. An optimization expression can be an optimization constraint, in particular of a MILP. Alternatively, the optimization expression is contained in a summand of the objective function of the optimization problem, in particular of a QUBO problem.

[0062] The optimization problem further comprises the state variables of the cryptographic procedure. A plurality of optimization expressions assigned to a certain round each comprise at least one state variable assigned to a preceding round.

[0063] After determining the optimization problem, the optimization problem is solved, and the cryptographic key is determined from an optimizing set of optimization variables (optimizer) of the optimization problem, in particular from an optimizing value of the cryptographic key variable (fourth step 14).

[0064] FIG. 2 shows a graphical representation of a data processing system 20. The data processing system 20 comprises at least one classical processing device 21. Additionally, the data processing system 20 may comprise a quantum processing device 22, for example a quantum annealing device. Data may be exchanged between the at least one classical processing device 21 and the quantum processing device 22.

[0065] In particular, in case of employing a D-Wave quantum annealing device, a D-Wave Python API may be used for data exchange.

[0066] Steps 11 to 13 are preferably carried in out in the classical processing device 21. The fourth step 14 of solving the optimization problem may be carried out in the classical processing device 21 or the quantum processing device 22. In the latter case, the fourth step 14 is significantly accelerated.

DETAILED DESCRIPTION OF THE METHOD

[0067] In the following, the steps of the method are laid out in detail with particular reference to AES.

[0068] a. AES Structure

[0069] In AES, the cryptographic key may have one of three different sizes, namely 128, 192, and 256 bits, while the input, the plaintext, has a fixed block size of 128 bits. For larger input data to be encrypted, the input data is split into data blocks of 128 bits each and the AES algorithm is applied to each data block, making use of a block cipher mode of operation.

[0070] Depending on the cryptographic key size, AES comprises a different number of rounds/iterations in which cryptographic operations are successively carried out, namely 10, 12, or 14—respectively corresponding to 128, 192, or 256 bits.

[0071] AES acts on 4×4 data blocks/arrays. In the AES regime, these data blocks are called states, each comprising in total 16 state entries (bytes). For instance, the plaintext b with 128 bits or equivalently 16 bytes b.sub.0, b.sub.1, . . . , b.sub.15 is represented by the two-dimensional array

[00001]$\begin{array}{cc}\left[\begin{array}{cccc}{b}_0& b_4& b_8& b_{12}\\ b_1& b_5& b_9& b_{13}\\ b_2& b_6& b_{10}& b_{14}\\ b_3& b_7& b_{11}& b_{15}\end{array}\right].& \left(1\right)\end{array}$

[0072] AES comprises the following cryptographic operations: [0073] I. KeyExpansion—round keys are derived from the cryptographic key using an AES key schedule. AES requires a separate 128-bit round key block for each round plus an additional round key block. [0074] II. Key addition round: [0075] a. AddRoundKey—each state entry is combined with a byte of the round key using bitwise XOR. [0076] III. Subsequent rounds (9, 11, or 13 rounds): [0077] a. SubBytes—a non-linear substitution step in which each byte is replaced with another according to a lookup table. [0078] b. ShiftRows—a transposition step in which the last three rows of the state are shifted cyclically by a certain number of steps. [0079] c. MixColumns—a linear mixing operation which operates on the columns of the state, combining the four bytes in each column. [0080] d. AddRoundKey [0081] IV. Final round: [0082] a. SubBytes [0083] b. ShiftRows [0084] c. AddRoundKey

[0085] The final state corresponds to the ciphertext.

[0086] Within the context of the present disclosure, the KeyExpansion operation can be understood as being contained in an initial round.

[0087] a. Determining the Elementary Relations

[0088] The cryptographic operations comprise Boolean functions with binary variables. For example, the cryptographic operation SubBytes comprises successively applying XOR operations. In the method, intermediate relations are determined for each cryptographic operation based on the Boolean functions. The intermediate relations may correspond to (intermediate) equations (equation representation) or to systems of (intermediate) inequalities (inequality representation).

[0089] Each Boolean function of a cryptographic operation can be further divided into elementary operations such as x∧y, x∨y, or x⊕y (AND, OR, XOR). For each elementary operation, at least one elementary relation, i.e., an elementary equation or an elementary inequality, can be determined. From the established elementary relations, the intermediate relations can be determined. In the following, determining the elementary relations will be illustrated before treating the intermediate relations in the subsequent section.

[0090] In order to determine a linear equation corresponding to an elementary operation, a respective (elementary) optimization problem is solved. The vector {right arrow over (x)} is defined as joint vector {right arrow over (x)}=({right arrow over (y)}, q({right arrow over (y)})) for elementary operation q, set of input variables {right arrow over (y)}, and output q({right arrow over (y)}). Further, f denotes a set of feasible configurations. The elementary equation to be determined has the form

{right arrow over (c)}.sup.T{right arrow over (x)}+{right arrow over (e)}.sup.T{right arrow over (a)}=b,  (2)

[0091] wherein {right arrow over (a)} is an auxiliary vector of binary coefficients, b is a continuous coefficient, {right arrow over (c)}, {right arrow over (e)} are vectors of continuous coefficients, and {right arrow over (x)}=({right arrow over (y)}, q({right arrow over (y)})) is a vector of binary variables. The transpose of a vector is denoted with (•).sup.T. Notably, Eq. (2) is linear in {right arrow over (c)}.

[0092] The linear system must satisfy:

[00002]$\begin{array}{cc}\{\begin{array}{c}{\stackrel{.fwdarw.}{c}}^T\stackrel{.fwdarw.}{x}+{\stackrel{.fwdarw.}{e}}^T\stackrel{.fwdarw.}{a_x}=b\left(\forall x\in f\right)\\ {\stackrel{.fwdarw.}{c}}^T\stackrel{.fwdarw.}{x}+{\stackrel{.fwdarw.}{e}}^T\stackrel{.fwdarw.}{a}\ne b\left(\forall x.Math.f\forall \stackrel{.fwdarw.}{a}\in {\left\{0,1\right\}}^{N_a}\right)\end{array}& \left(3\right)\end{array}$

[0093] The sought-after coefficients to be determined by the elementary optimization problem are the continuous variables {right arrow over (c)}, {right arrow over (e)}, and b. The elementary optimization problem can be formulated as a MILP and is determined from Eq. (3) as follows. First, a number N.sub.a of ancillaries {right arrow over (a)} in Eq. (3) is chosen. The number of variables in the original problem is denoted by N.sub.x. The MILP consists of a set of auxiliary constraints and an objective function. Each vector from the feasible configurations yields one of the auxiliary constraints with continuous variables {right arrow over (c)}, {right arrow over (e)}, and b and N.sub.a new binary variables d:

{right arrow over (c)}.sup.T{right arrow over (x)}+{right arrow over (e)}.sup.Ta{right arrow over (=)}b  (4)

[0094] For each vector {right arrow over (x)} from the infeasible configurations, 2.sup.N.sup.a new of the auxiliary constraints are added:

∀{right arrow over (a)}ε{0,1}.sup.N:{right arrow over (c)}.sup.T{right arrow over (x)}+{right arrow over (e)}.sup.T{right arrow over (a)}≠b  (5)

[0095] As a result, a MILP with |f|+2.sup.N.sup.a|f*| auxiliary constraints (|f| and |f*| being the number of the feasible and the infeasible configurations, respectively) and N.sub.x+N.sub.a+1+|f|.Math.N.sub.a variables is established. Such a homogeneous MILP has a plurality of solutions (multiplying all coefficients by the same number also results in a solution). Hence, the first coefficient c.sub.1 of {right arrow over (c)} is set to 1, yielding the additional auxiliary constraint or corresponding penalty term c.sub.1=1.

[0096] The elementary optimization problem then reads:

[00003]$\begin{array}{cc}{\underset{\stackrel{.fwdarw.}{a_x},b,\stackrel{.fwdarw.}{c},\stackrel{.fwdarw.}{e}}{\min }\left(c_1-1\right)}^2\mathrm{subject}\mathrm{to}\{\begin{array}{c}{\stackrel{.fwdarw.}{c}}^T\stackrel{.fwdarw.}{x}+{\stackrel{.fwdarw.}{e}}^T\stackrel{.fwdarw.}{a_x}=b\left(\forall x\in f\right)\\ {\stackrel{.fwdarw.}{c}}^T\stackrel{.fwdarw.}{x}+{\stackrel{.fwdarw.}{e}}^T\stackrel{.fwdarw.}{a}\ne b\left(\forall x.Math.f\forall \stackrel{.fwdarw.}{a}\in {\left\{0,1\right\}}^{N_a}\right)\end{array}& \left(6\right)\end{array}$

[0097] with b, {right arrow over (c)}, {right arrow over (e)} comprising real-valued variables and {right arrow over (a)}.sub.x comprising binary variables.

[0098] As an example, determining the elementary equation for the elementary operation z=x∧y is described below.

[0099] The feasible configurations and the infeasible configurations of the elementary operation are as follows:

TABLE-US-00001 x y z 0 0 0 feasible 0 1 0 feasible 1 0 0 feasible 1 1 1 feasible 0 0 1 infeasible 0 1 1 infeasible 1 0 1 infeasible 1 1 0 infeasible

[0100] Eq. (4) is simplified to c.sub.xx+c.sub.yy+c.sub.zz+c.sub.aa=b and the coefficients c.sub.x, c.sub.y, c.sub.z, c.sub.a, b are to be determined such that:

z=x∧y⇔(∃a∈{0,1}:c.sub.xx+c.sub.yy+c.sub.zz+c.sub.aa=b).  (7)

[0101] The elementary optimization problem then reads

[00004]${\underset{c_x,c_y,c_z,c_a,b,a_0,a_1,a_2,a_3}{\min }\left(c_x-1\right)}^2$

[0102] subject to:

c.sub.x.Math.0+c.sub.y.Math.0+c.sub.z.Math.0+c.sub.aa.sub.0=b,

c.sub.x.Math.0+c.sub.y.Math.1+c.sub.z.Math.0+c.sub.aa.sub.1=b

c.sub.x.Math.1+c.sub.y.Math.0+c.sub.z.Math.0+c.sub.aa.sub.2=b

c.sub.x.Math.1+c.sub.y.Math.1+c.sub.z.Math.1+c.sub.aa.sub.3=b

c.sub.x.Math.0+c.sub.y.Math.0+c.sub.z.Math.1+c.sub.a.Math.0≠b,

c.sub.x.Math.0+c.sub.y.Math.0+c.sub.z.Math.1+c.sub.a.Math.1≠b,

c.sub.x.Math.0+c.sub.y.Math.1+c.sub.z.Math.1+c.sub.a.Math.0≠b,

c.sub.x.Math.0+c.sub.y.Math.1+c.sub.z.Math.1+c.sub.a.Math.1≠b,

c.sub.x.Math.1+c.sub.y.Math.0+c.sub.z.Math.1+c.sub.a.Math.0≠b,

c.sub.x.Math.1+c.sub.y.Math.0+c.sub.z.Math.1+c.sub.a.Math.1≠b,

c.sub.x.Math.1+c.sub.y.Math.1+c.sub.z.Math.0+c.sub.a.Math.0≠b,

c.sub.x.Math.1+c.sub.y.Math.1+c.sub.z.Math.0+c.sub.a.Math.1≠b,

c.sub.x,c.sub.y,c.sub.z,c.sub.{a},b∈,a.sub.0,a.sub.1,a.sub.2,a.sub.3∈{0,1}.  (8)

[0103] Analogously, the elementary equations for further Boolean elementary operations can be determined, yielding the following Table 1:

TABLE-US-00002 TABLE 1 Elementary operation Elementary equation AND x ∧ y = z E.sub.∧(x, y, a, z) ≐ {x + y − 2z − a = 0} OR x ∨ y = z E.sub.∨(x, y, a, z) ≐ {x + y − 2z + a = 0} XOR x ⊕ y = z [00005]$E_{\oplus }\left(x,y,a,z\right)\stackrel{.}{=}\left\{x+y-z-2a=0\right\}$ NOR x ∨ y = z E.sub.∨(x, y, a, z) ≐ {x + y + 2z − a = 1} NAND x ∧ y = z E.sub.∧(x, y, a, z) ≐ {x + y + 2z − a = 2}

[0104] Instead of elementary equations, systems of elementary inequalities can be established for each elementary operation, according to Table 2:

TABLE-US-00003 TABLE 2 El. operation Systems of elementary inequalities AND x ∧ y = z S.sub.∧(x, y, z) ≐ {z ≤ x, z ≤ y, z ≥ x + y − 1, z ≥ 0} OR x ∨ y = z S.sub.∨(x, y, z) ≐ {x ≤ z, y ≤ z, z ≤ x + y, z ≤ 1} XOR x ⊕ y = z S.sub.⊕(x, y, z) ≐ {z ≤ x + y, z ≥ x − y, z ≥ y − x, z ≤ 2 − x − y} NOR x ∨ y = z S.sub.∨(x, y, z) ≐ {x ≤ 1 − z, y ≤ 1 − z, 1 − z ≤ x + y, −z ≤ 0} NAND x ∧ y = z S.sub.∧(x, y, z) ≐ {1 −z ≤ x, 1 − z ≤ y, −z ≥ x + y − 2, 1 − z ≥ 0}

[0105] The equivalence may be verified directly of the respective elementary operation and system of elementary inequalities. Systems S.sub.∧(x, y, z) and S.sub.∨ (x, y, z) may be derived from S.sub.∧(x, y, z), S.sub.∨(x, y, z) by change of variable from z to 1−z. If variables x, y, z satisfy the corresponding system of elementary inequalities and x and y are binary-valued then z will be binary-valued as well.

[0106] a. Determining the Intermediate Relations

[0107] Having established the elementary relations corresponding to the elementary Boolean operations underlying the cryptographic operations, the respective intermediate relations are determined as follows.

[0108] c.1 Rijndael's Finite Field

[0109] Several cryptographic operations in AES are based on Rijndael's finite field, the Galois field GF(2.sup.8)=GF(2)[x]/(x.sup.8+x.sup.4+x.sup.3+x+1). In AES, inverse operations and multiplications by 1, 2, and 3 are carried out in GF(2.sup.8). The calculation of the inverse operation is a hard problem in GF(2.sup.8), but an easy problem in GF(2), where multiplication is carried out using AND operations. Therefore 1.sup.−1=1 in GF(2). Further 0.sup.−1 is defined as 0. These relations are valid for any GF(2P), p≥1. The inversion in GF(2.sup.8) may be sequentially reduced into multiplication and inversion in GF(2.sup.4), then GF(2.sup.2), and GF(2) (cf. Canright, Cryptographic Hardware and Embedded Systems, CHES 2005, pp. 441-455). For example, an element G in GF(2.sup.8) can be represented as G=γ.sub.1γ+γ.sub.0 with multiplication modulo an irreducible polynomial r(y)=y.sup.2+τy+v and γ.sub.0, γ.sub.1∈GF(2.sup.4). Similar transformations to GF(2.sup.2) and GF(2) may be carried out. As a result, the inversion in GF(2.sup.8) can be represented by the Boolean elementary operations XOR, NAND, and NOR. As laid out above, the elementary operations are transformed into the corresponding elementary relations, cf. tables 1 and 2. For one byte/state entry, 180 elementary operations (XOR, NAND, NOR) are required. Each elementary operation requires one additional equation and two additional bits (z and a). The resulting intermediate equation for inversion, as determined from the elementary equations, is denoted with E.sub.inv({right arrow over (x)}, {right arrow over (a)}, {right arrow over (z)}) with (vector-valued) variables {right arrow over (x)}, {right arrow over (a)}, and {right arrow over (z)}.

[0110] Intermediate equations for the multiplication by 1, 2, and 3 in GF(2.sup.8) can be determined as follows. Multiplying by 1 simply yields the same number, i.e., a×1=a with a∈GF(2.sup.8). Multiplying a number by 2 is equivalent to shifting the number left by one, and subsequently, if the highest bit of the number is one, additionally applying XOR to the result and the value 0x1B (in hexadecimal representation, corresponding to 00011011 in binary representation).

[0111] In particular, starting with {right arrow over (x)}=[x.sub.0, x.sub.1, . . . , x.sub.7], shifting and applying XOR with 0x1B yields {right arrow over (z)}=[z.sub.0, z.sub.1, . . . , z.sub.7]. As 0x1B is constant, the XOR operation can be simplified using a⊕0=a and a⊕1=ā. Hence, after shifting, the result is flipped if the highest bit of x and the corresponding bit of 0x1B are both equal to 1. Therefore, full multiplication by 2 results in the following equation system of intermediate equations: [0112] (9)

[00006]$E_2\left(\stackrel{.fwdarw.}{x},\stackrel{.fwdarw.}{a},\stackrel{.fwdarw.}{z}\right)=\{\begin{array}{c}{z}_0=x_7\\ z_1=x_7+x_0-2a_0\\ z_2=x_1\\ z_3=x_7+x_2-2a_1\\ z_4=x_7+x_3-2a_2\\ z_5=x_4\\ z_6=x_5\\ z_7=x_6\end{array}$

[0113] The intermediate equations with two variables correspond to substitution and can thus be eliminated. As a result, multiplication by 2 requires three additional equations and six additional bits.

[0114] Multiplication by 3 can be reformulated as follows:

x×3=x×(2⊕1)=x×2⊕x  (10)

[0115] The employed XOR operation requires one additional equation and one additional auxiliary bit per state bit. Hence, multiplication by 3 requires 3+8=11 additional equations and 22 additional bits. The corresponding intermediate equations are denoted with E.sub.3({right arrow over (x)},{right arrow over (a)},{right arrow over (z)}).

[0116] c.2 AddRoundKey

[0117] In the AddRoundKey operation, the state is combined with a round key, which is determined from the cryptographic key for each round using the AES key schedule. Each round key has the same size as the state. The round key is added to the state by combining each byte of the state with the corresponding byte of the round key via bitwise XOR (see FIG. 3 for an illustration with exemplary byte values). For each of the 128 bits of the state and the round key, a bitwise XOR operation is applied. The AddRoundKey operation therefore requires 128 XOR operations corresponding to 128 additional equations and 256 additional bits.

[0118] The intermediate equations E.sub.addroundkey({right arrow over (state)},{right arrow over (subkey)},{right arrow over (ancilla)},{right arrow over (newstate)}) thus can be written as

E.sub.addroundkey({right arrow over (state)},{right arrow over (subkey)},{right arrow over (ancilla)},{right arrow over (newstate)})={E.sub.⊕(state[i][j],subkey[i][j],ancilla[i][j],newstate[i][j]) for i in 0-15 for j in 0 . . . 7}  (11)

[0119] c.3 SubBytes

[0120] FIG. 4 shows graphical representation of the SubBytes operation. In the SubBytes operation, each byte a.sub.i,j of the state is replaced with S(a.sub.i,j) using an 8-bit substitution box (S-box) S. This cryptographic operation provides non-linearity in the encryption procedure. The S-box used is derived from the multiplicative inverse over GF(2.sup.8), which comprises suitable non-linearity properties. The SubBytes operation can be decomposed into two parts.

[0121] First, each input byte is mapped to its multiplicative inverse in Rijndael's finite field GF(2.sup.8). Second, the following affine transformation is applied:

[00007]$\begin{array}{cc}\left[\begin{array}{c}{s}_0\\ s_1\\ s_2\\ s_3\\ s_4\\ s_5\\ s_6\\ s_7\end{array}\right]=\left[\begin{array}{cccccccc}1& 0& 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 0& 1& 1\\ 1& 1& 1& 1& 0& 0& 0& 1\\ 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 1\end{array}\right]\left[\begin{array}{c}{b}_0\\ b_1\\ b_2\\ b_3\\ b_4\\ b_5\\ b_6\\ b_7\end{array}\right]\oplus \left[\begin{array}{c}1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0\end{array}\right]& \left(12\right)\end{array}$

[0122] where b is the multiplicative inverse of the input byte.

[0123] Determining the multiplicative inverse can be carried out as described in section c.1. Thus, 180 additional equations and 360 bits for each byte are required, resulting in 16 180=360 additional linear equations and bits.

[0124] The affine transformation comprises an XOR operation with 5 input bits (corresponding to five matrix entries with value 1 per matrix row). The right-hand side vector does not have any variables. Hence, if its i-th bit has value zero, then s.sub.i is a flipped value (in the corresponding equation, s.sub.i is replaced by 1−s.sub.i). The XOR operation with 5 input values can be evaluated sequentially, i.e., x.sub.1 ⊕x.sub.2 ⊕x.sub.3 ⊕x.sub.4 ⊕x.sub.s=(((x.sub.1 ⊕x.sub.2)⊕x.sub.3) ⊕x.sub.4)⊕x.sub.5). This requires several additional auxiliary variables.

[0125] In an alternative approach, an intermediate optimization problem is determined and solved as detailed above with respect to the elementary optimization problems. The optimization problem yields the following intermediate equation:

E.sub.5⊕≐{x.sub.1+x.sub.2−x.sub.3+x.sub.4−x.sub.5−y+2a.sub.0−2a.sub.1=0}  (13)

[0126] Hence, each bit of the cryptographic operation SubBytes requires one equation and three auxiliary bits. For the entire state, 128 equations and 384 auxiliary bits are required. In total, the SubBytes operation requires 2880+128=3008 (intermediate) equations and 5760+384=6144 auxiliary bits.

[0127] For the cryptographic operation SubBytes, the following intermediate equations are thus provided:

[00008]$\left(14\right)$$E_{\mathrm{subbytes}}\left(\stackrel{.Math.}{\mathrm{state}},\stackrel{.Math.}{\mathrm{ancilla}},\stackrel{.Math.}{\mathrm{nextstate}}\right)=\{\begin{array}{c}{E}_{\mathrm{inv}}\left(\stackrel{.Math.}{\mathrm{state}}\left[0\right],\stackrel{.Math.}{\mathrm{ancilla}}\left[0\right]\left[0\right],\stackrel{.Math.}{\mathrm{invstate}}\left[0\right]\right)\\ E_{5\oplus }\left(\stackrel{.Math.}{\mathrm{invstate}}\left[0\right],\stackrel{.Math.}{\mathrm{ancilla}}\left[0\right]\left[1\right]\left[i\right],\mathrm{nextstate}\left[0\right]\left[i\right]\right)\mathrm{for}i\mathrm{in}0.\text{.7}\\ .Math.\\ E_{\mathrm{inv}}\left(\stackrel{.Math.}{\mathrm{state}}\left[15\right],\stackrel{.Math.}{\mathrm{ancilla}}\left[15\right]\left[0\right],\stackrel{.Math.}{\mathrm{invstate}}\left[15\right]\right)\\ E_{5\oplus }\left(\stackrel{.Math.}{\mathrm{invstate}}\left[15\right],\stackrel{.Math.}{\mathrm{ancilla}}\left[15\right]\left[1\right]\left[i\right],\mathrm{nextstate}\left[15\right]\left[i\right]\right)\mathrm{for}i\mathrm{in}0.\text{.7}\end{array}$

[0128] c.4 ShiftRows

[0129] The ShiftRows operation acts on the rows of the state by cyclically shifting the bytes in each row by a certain offset. For AES, the first row is left unchanged. Each byte of the second row is shifted one to the left. Similarly, the third and fourth rows are shifted by offsets of two and three, respectively. Hence, the ShiftRows operation just rearranges bits and does not require additional linear equations with auxiliary variables.

[0130] The corresponding intermediate relation therefore comprises a permutation function

S({right arrow over (state)})={right arrow over (newstate)},  (15)

[0131] which represents the bit rearrangements.

[0132] c.5 MixColumns

[0133] FIG. 5 shows a graphical representation of the MixColumns operation, by which the four bytes of each column of the state are combined using an invertible linear transformation. Each column j is transformed using a fixed matrix by left-multiplying the fixed matrix with the column j:

[00009]$\begin{array}{cc}\left[\begin{array}{c}{b}_{0,j}\\ b_{1,j}\\ b_{2,j}\\ b_{3,j}\end{array}\right]=\left[\begin{array}{cccc}2& 3& 1& 1\\ 1& 2& 3& 1\\ 1& 1& 2& 3\\ 3& 1& 1& 2\end{array}\right]\left[\begin{array}{c}{a}_{0,j}\\ a_{1,j}\\ a_{2,j}\\ a_{3,j}\end{array}\right]0\le j\le 3& \left(16\right)\end{array}$

[0134] Multiplication and addition are carried out in the Galois field GF(2.sup.8). Addition in GF(2.sup.8) corresponds to the XOR operation. Using four input bits for each output bit b.sub.i,j(i=0, . . . 3), the corresponding intermediate equation reads:

x.sub.1+x.sub.2−x.sub.3+x.sub.4+y−2a.sub.0−2a.sub.1=0  (17)

[0135] Hence, addition in GF(2.sup.8) requires one additional equation and 3 auxiliary bits per state bit, resulting in 128 additional equations and 384 auxiliary bits per state in total. Multiplication by 2 requires three equations and six auxiliary bits per byte and 48 equations and 96 bits per state, while multiplication by 3 requires 176 equations and 352 auxiliary bits per state. In total, the MixColumns operation requires 128+48+176=352 intermediate equations and 384+96+352=832 auxiliary bits.

[0136] Denoting the MixColumns input state with {right arrow over (state)}≐{a.sub.i,j for i in 0 . . . 3 for j in 0 . . . 3} and the output state with {right arrow over (newstate)}≐{a.sub.i,j for i in 0 . . . 3 for j in 0 . . . 3}, the intermediate equations for the MixColumns operation read:

E.sub.mixcolumns({right arrow over (state)},{right arrow over (ancilla)},{right arrow over (newstat)}e)={E.sub.2(a.sub.i,j,ancilla.sub.i,j,2,aa.sub.i,j),E.sub.3(a.sub.i,j,ancilla.sub.i,j,3,aaa.sub.i,j),E.sub.4⊕(aa.sub.0,j,aaa.sub.1,j,a.sub.2,j,a.sub.3,j,ancilla.sub.0,j,ancilla.sub.1,j,b.sub.0,j),E.sub.4⊕(a.sub.0,j,aa.sub.1,j,aaa.sub.2,j,a.sub.3,j,ancilla.sub.0,j,ancilla.sub.1,j,b.sub.1,j),E.sub.4⊕(a.sub.0,j,a.sub.1,j,aa.sub.2,j,aaa.sub.3,j,ancilla.sub.0,j,ancilla.sub.1,j,b.sub.2,j),E.sub.4⊕(aaa.sub.0,j,a.sub.1,j,a.sub.2,j,aa.sub.3,j,ancilla.sub.0,j,ancilla.sub.1,j,b.sub.3,j), for i in 0 . . . 3, for j in 0 . . . 3}  (18)

[0137] c.6 KeyExpansion

[0138] FIG. 6 shows a graphical representation of the KeyExpansion operation, which expands the cryptographic key into a plurality of separate round keys. The three AES variants AES-128, AES-192, and AES-256 (with the cryptographic key having 128, 192, and 256 bits, respectively) comprise different numbers of rounds. Each AES variant requires a separate 128-bit round key for each round plus an additional round. The AES key schedule produces the round keys from the cryptographic key. Denoting the number of 32-bits words in the cryptographic key with N (i.e., N=4 for AES-128, N=6 for AES-192, and N=8 for AES-256), the cryptographic key with [K.sub.0, K.sub.1, . . . , K.sub.N−1] the number of rounds plus one with R (i.e., R=11 for AES-128, R=13 for AES-192, and R=15 for AES-256), and the 32-bit words of the expanded key with W.sub.0, W.sub.1, . . . , W.sub.4R−1, the round key at round r (with r<R) is [W.sub.4r, W.sub.4r+1, W.sub.4r+2, W.sub.4r+3]. The 32-bit words W.sub.i for each round key are determined as follows:

[00010]$\begin{array}{cc}{W}_i=\{\begin{array}{cc}{K}_i& \mathrm{if}i<N\\ W_{i-N}\oplus \mathrm{SubWord}\left(\mathrm{RotWord}\left(W_{i-1}\right)\right)\oplus {\mathrm{rcon}}_{i/N}& \mathrm{if}i\ge N\mathrm{and}i\equiv 0\left(\mathrm{mod}N\right)\\ W_{i-N}\oplus \mathrm{SubWord}\left(W_{i-1}\right)& \mathrm{if}i\ge N,N>6,\mathrm{and}i\equiv 4\left(\mathrm{mod}N\right)\\ W_{i-N}\oplus W_{i-1}& \mathrm{otherwise}\end{array}.& \left(19\right)\end{array}$

[0139] The operation RotWord corresponds to a one-byte left circular shift and does not require additional linear equations as it just rearranges state bits. The operation SubWord represents an application of the AES S-box as described in Section c.3 to each of the four bytes of the word:

SubWord([b.sub.0b.sub.2b.sub.3])=[S(b.sub.0)S(b.sub.1)S(b.sub.2)S(b.sub.3)].  (20)

[0140] Further, rcon is an array of given numbers. Therefore, applying XOR does not involve additional linear equations and auxiliary bits. Both operations W.sub.i−N⊕SubWord(RotWord (W.sub.i−1))⊕rcon.sub.i/N and W.sub.i−N⊕SubWord (W.sub.i−1) are equivalent in terms of additional equations and auxiliary bits. Hence, the 32-bit words W.sub.i of the round key are calculated using three different operations: [0141] I. W.sub.i is determined as K.sub.i, which is just part of the cryptographic key. Hence, no additional equations and only 32 bits are required (each K.sub.i has a bit length of 32). This type of operation is carried out N times. [0142] II. W.sub.i is determined as W.sub.i−N⊕SubWord(RotWord (W.sub.i−1))⊕rcon.sub.i/N or as W.sub.i−NδSubWord (W.sub.i−1). The corresponding S-box requires 188 equations and 384 auxiliary bits per byte. With 4 bytes and additional XOR, in total 188.Math.4+8=760 equations and 384.Math.4+2.Math.8=1552 auxiliary bits are required. This type of operation is carried out 10 times for AES-128, 8 times for AES-192 and 13 times for AES-256. [0143] III. W.sub.i is determined as W.sub.i−N⊕W.sub.i−1, which corresponds to XOR acting on a 32-bit word, thus requiring 32 equations and auxiliary 64 bits. This type of operation is carried out 30 times for AES-128, 38 times for AES-192 and 39 times for AES-256.

[0144] In total, the KeyExpansion operation requires 8560 intermediate equations and 17568 auxiliary bits for AES-128, 7296 intermediate equations and 15040 auxiliary bits for AES-192, and 11128 intermediate equations and 22928 auxiliary bits for AES-256.

[0145] The intermediate equations corresponding to the KeyExpansion operation are denoted with E.sub.keyexpansion({right arrow over (K)},{right arrow over (ancillca)},{right arrow over (W)}).

[0146] c.7 Obtaining the Intermediate Inequalities Via Convex Polyhedron Representations

[0147] The intermediate inequalities for the respective cryptographic procedures can also be determined by making use of the fact that any Boolean function F({right arrow over (x)}) can be represented as a system of linear inequalities. For a set B.sup.n≐{(x.sub.1, x.sub.2, . . . , x.sub.n): x.sub.k∈{0,1}}∈R.sup.n of all vertices of an n-dimensional unit cube, which corresponds to the set of all 0-1 arguments of the Boolean function F: B.sup.n.fwdarw.{0,1}, there exists a system of linear inequalities with n+1 variables ({right arrow over (x)}, x.sub.n+1)

S({right arrow over (x)},x.sub.n+1)={a.sub.i+l.sub.i({right arrow over (x)})+b.sub.ix.sub.n+1≥0:1=1, . . . ,m},  (21)

[0148] (wherein a.sub.i, b.sub.i, b.sub.i≠0 are scalars, and l.sub.i({right arrow over (x)}) are linear functions of n variables) such that the following holds:

∀{right arrow over (x)}∈B.sup.n:{F({right arrow over (x)})=x.sub.n+1}⇔{a.sub.i+l.sub.i({right arrow over (x)})+b.sub.ix.sub.n+1≥0:i=1, . . . ,m}  (22)

[0149] I.e., for any {right arrow over (x)}∈B.sup.n, F({right arrow over (x)})=x.sub.n+1 if and only if S({right arrow over (x)}, x.sub.n+i) holds. Importantly, it is not required to assume x.sub.n+1 to be a binary-values variable. For any binary-valued vector {right arrow over (x)}, the system S({right arrow over (x)}, x.sub.n+1) has only a solution ({right arrow over (x)}, x.sub.n+1) where x.sub.n+1=F({right arrow over (x)}).

[0150] Transforming Boolean functions to linear equations or inequalities is a known challenge in computing science, in particular with regard to connections between the Boolean satisfiability (SAT) problem and integer linear programming (ILP) problems. Treating the SAT-problem corresponds to checking the satisfiability of a large Boolean function that is represented mainly in one of two special forms: CNF (conjunctive normal form) or DNF (disco junctive normal form). If a Boolean function has DNF or CNF representation, then the generation of corresponding linear inequalities may be done directly on the base of Table 2 since DNF and CNF representations are compositions of elementary bi-variant Boolean operations. This (first) approach may be applied to any Boolean functions because any Boolean function may be converted to a DNF or CNF representation.

[0151] Such an approach may have two drawbacks: First, a corresponding CNF or DNF representation has to be determined for a given Boolean function and, second, the system of linear inequalities to be generated may comprise a substantial amount of redundant inequalities.

[0152] In an alternative second approach, DNF or CNF representations are not required, and irreducible systems of linear inequalities may be obtained. Any Boolean function F of n variables can be represented by a convex hull of appropriate 2.sup.n vertices of the unit hypercube B.sup.n+1⊂.sup.n+1. The Boolean function F may be represented by a set of vectors in .sup.n+1: V[F]≐{({right arrow over (x)}, F(x)):{right arrow over (x)}∈B.sup.n}, which can be understood as a graph of the Boolean function F. V[F] is a subset of the unit hypercube, i.e., V [F]⊂B.sup.n+1. It can be shown that all vectors in V[F] are vertices of the corresponding convex polyhedron conv(V[F]), a convex hull of V [F]. Therefore, the Boolean function F may be treated as a convex polyhedron V [F] (using the same symbol for polyhedron and the set of its vertices). Any polyhedron may be represented either by the set of all its vertices, the V-representation, or by the system of linear inequalities (corresponding to the set of the facets of the polyhedron), the H-representation (cf. Avis and Fukuda, Discrete & Computational Geometry, 8(3):295-313, 1992). The H-representation of the polyhedron V [F] (given by V-representation) represents the sought-after system of linear inequalities.

[0153] V- and H-representations of convex hulls of finite set of points in Euclidean spaces may e.g., be determined via polyhedral computation codes such as CDD or LRS. Notably, irreducible H-representations can be produced, i.e., redundant linear inequalities are eliminated. Thus, the complexity of the resulting optimization problem for determining the cryptographic key can be reduced. LRS further allows for a parallel implementation of reverse search algorithms. Moreover, in LRS computations regarding polyhedra with integral-valued vertices (as is the case with V [F]) may be carried out without loss of accuracy.

[0154] All linear systems for elementary Boolean bi-variant functions listed in Table 2 may be obtained via determining a corresponding H-representation. As an example, for the Boolean function J with

J(x.sub.1,x.sub.2,x.sub.3)=(x.sub.1∧x.sub.2)∨(x.sub.1∧x.sub.3)∨(x.sub.2∧x.sub.3)=x.sub.4,  (23)

[0155] systems of inequalities as MILP constraints are determined using both the first and the second approach.

[0156] Determining the H-representation (e.g., with LRS) yields a system with 10 inequalities,

[00011]$\begin{array}{cc}\left[\begin{array}{c}1\\ 0\\ 1\\ 1\\ 1\\ 0\\ 1\\ 0\\ 0\\ 0\end{array}\right]+\left[\begin{array}{cccc}0& 0& 0& -1\\ 0& 0& 0& 1\\ -1& -1& 0& 1\\ -1& -1& -1& 2\\ 0& -1& -1& 1\\ 1& 0& 1& -1\\ -1& 0& -1& 1\\ 1& 1& 0& -1\\ 0& 1& 1& -1\\ 1& 1& 1& -2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right]\ge \stackrel{.Math.}{\left[0\right]}& \left(24\right)\end{array}$

[0157] while using the first approach with DNF/CNF representation, a system of 17 inequalities and 4 continuous ancillaries is established. The larger number in the latter case results from the successive construction of the system from elementary bi-variant Boolean functions and continuous ancillary variables, while the former approach allows for treating the Boolean function J as a whole.

[0158] In a second example, a Boolean expression comprising 5 binary variables x.sub.1, x.sub.2, x.sub.3, x.sub.4, x.sub.5, x.sub.6 and

x.sub.1⊕x.sub.2⊕x.sub.3⊕x.sub.4⊕x.sub.5=x.sub.6,  (25)

[0159] is equivalent to the following system of linear inequalities:

[00012]$\begin{array}{cc}\left[\begin{array}{c}1\\ 0\\ 4\\ 4\\ 4\\ 4\\ 4\\ 2\\ 2\\ 2\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 2\\ 4\\ 2\\ 2\\ 2\\ 2\end{array}\right]+\left[\begin{array}{cccccc}0& 0& 0& 0& 0& -1\\ 0& 0& 0& 0& 0& 1\\ -1& -1& -1& -1& -1& 1\\ -1& -1& -1& -1& 1& -1\\ -1& 1& -1& -1& -1& -1\\ 1& -1& -1& -1& -1& -1\\ -1& -1& 1& -1& -1& -1\\ 1& -1& -1& 1& 1& -1\\ -1& 1& -1& 1& 1& -1\\ 1& 1& -1& -1& -1& 1\\ 1& -1& 1& 1& 1& 1\\ 1& 1& 1& 1& 1& -1\\ 1& 1& 1& 1& -1& 1\\ 1& 1& 1& -1& 1& 1\\ 1& 1& -1& 1& 1& 1\\ -1& 1& 1& 1& 1& 1\\ 1& 1& 1& -1& -1& -1\\ 1& 1& -1& -1& 1& -1\\ 1& 1& -1& 1& -1& -1\\ 1& -1& 1& 1& -1& -1\\ -1& 1& 1& 1& -1& -1\\ -1& -1& 1& 1& 1& -1\\ 1& -1& 1& -1& 1& -1\\ -1& 1& 1& -1& 1& -1\\ -1& 1& 1& -1& -1& 1\\ 1& -1& 1& -1& -1& 1\\ -1& 1& -1& -1& 1& 1\\ 1& -1& -1& -1& 1& 1\\ -1& -1& 1& -1& 1& 1\\ -1& -1& -1& 1& -1& -1\\ -1& 1& -1& 1& -1& 1\\ 1& -1& -1& 1& -1& 1\\ -1& -1& 1& 1& -1& 1\\ -1& -1& -1& 1& 1& 1\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\end{array}\right]\ge \stackrel{.Math.}{\left[0\right]}& \left(26\right)\end{array}$

[0160] Since x.sub.1, x.sub.2, x.sub.3, x.sub.4, x.sub.5 are all binary-valued, redundant trivial inequalities (0≤x.sub.1≤1) could be excluded as well as inequalities with zero coefficients for the variable x.sub.6. The output value x.sub.6 will automatically be binary.

[0161] a. Determining the Optimization Problem

[0162] Having established all intermediate relations, the optimization problem to be solved can be determined. Table 3 shows the number of employed intermediate equations and auxiliary bits.

TABLE-US-00004 TABLE 3 Number of intermediate equations Auxiliary bits AES-128 43216 89312 AES-192 2 .Math. 48928 2 .Math. 101248 AES-256 2 .Math. 59736 2 .Math. 123600

[0163] The optimization expressions of the optimization problem are determined from the set of intermediate relations, in case of intermediate equations from

[00013]$\begin{array}{cc}\{\begin{array}{c}{E}_{\mathrm{keyexpansion}}\left(\stackrel{.Math.}{K},{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{key}},\stackrel{.Math.}{W}\right)\\ E_{\mathrm{addroundkey}}\left(\stackrel{.Math.}{\mathrm{initstate}},\stackrel{.Math.}{W_0{W}_1{W}_2{W}_3},{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{add}0},{\stackrel{.Math.}{\mathrm{state}}}_0\right)\\ E_{\mathrm{subbytes}}\left({\stackrel{.Math.}{\mathrm{state}}}_0,{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{sub}0},{\stackrel{.Math.}{\mathrm{boxstate}}}_0\right)\\ E_{\mathrm{mixcolumns}}\left(S\left({\stackrel{.Math.}{\mathrm{boxstate}}}_0\right),{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{mix}0},{\stackrel{.Math.}{\mathrm{mixstate}}}_0\right)\\ E_{\mathrm{addroundkey}}\left({\stackrel{.Math.}{\mathrm{mixstate}}}_0,\stackrel{.Math.}{W_4{W}_5{W}_6{W}_7},{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{add}1},{\stackrel{.Math.}{\mathrm{state}}}_1\right)\\ .Math.\\ E_{\mathrm{subbytes}}\left({\stackrel{.Math.}{\mathrm{state}}}_{R-2},{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{subR}-2},{\stackrel{.Math.}{\mathrm{boxstate}}}_{R-2}\right)\\ E_{\mathrm{mixcolumns}}\left(S\left({\stackrel{.Math.}{\mathrm{boxstate}}}_{R-2}\right),{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{mixR}-2},{\stackrel{.Math.}{\mathrm{mixstate}}}_{R-2}\right)\\ E_{\mathrm{addroundkey}}\left({\stackrel{.Math.}{\mathrm{mixstate}}}_{R-2},\stackrel{.Math.}{W_{4\left(R-2\right)}{W}_{4\left(R-2\right)+1}{W}_{4\left(R-2\right)+2}{W}_{4\left(R-2\right)+3}},{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{addR}-1},{\stackrel{.Math.}{\mathrm{state}}}_{R-1}\right)\\ E_{\mathrm{subbytes}}\left({\stackrel{.Math.}{\mathrm{state}}}_{R-1},{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{subR}-1},{\stackrel{.Math.}{\mathrm{boxstate}}}_{R-1}\right)\\ E_{\mathrm{addroundkey}}\left({\stackrel{.Math.}{\mathrm{mixstate}}}_{R-1},\stackrel{.Math.}{W_{4\left(R-1\right)}{W}_{4\left(R-1\right)+1}{W}_{4\left(R-1\right)+2}{W}_{4\left(R-1\right)+3}},{\stackrel{.Math.}{\mathrm{ancilla}}}_{\mathrm{addR}},{\stackrel{.Math.}{\mathrm{state}}}_R\right)\end{array}& \left(27\right)\end{array}$

[0164] where {right arrow over (initstate)} corresponds to the plaintext, {right arrow over (state)}.sub.R corresponds to the ciphertext and {right arrow over (K)} denotes the cryptographic key variable. The cryptographic key is determined from an optimizing value of the cryptographic key variable {right arrow over (K)}. The state variables {right arrow over (state)}.sub.r correspond to the states of the AES procedure for different rounds r. Notably, several optimization expressions each comprise at least one preceding state variable assigned to a preceding round, in particular a directly preceding round. e.g., the optimization expression E.sub.subbytes({right arrow over (state)}.sub.R−2, {right arrow over (ancilla)}.sub.subR−2,{right arrow over (boxstate)}.sub.R−2) comprises the state variable {right arrow over (state)}.sub.R−2 assigned to the preceding round R−2.

[0165] For the optimization problem being a MILP, the optimization expressions are optimization constraints. Hence, the intermediate equations in Eq. (27) constitute the constraints of a MILP. A MILP can also be determined with the optimization expressions as constraints being the intermediate inequalities instead of the intermediate equations. To this end, the corresponding inequalities for each cryptographic operation and round have to be determined.

[0166] For the optimization problem being a QUBO problem, the optimization expressosions are determined from the intermediate equations by moving all terms of each intermediate equation to one side and squaring the resulting terms. The objective function of the QUBO problem then comprises a sum of all squared terms. Determining the optimization expressions this way can be formally described as follows. Representing the intermediate equations as a linear system

A{right arrow over (x)}≈{right arrow over (b)},  (28)

[0167] where {right arrow over (x)}∈{0,1}.sup.N, A∈.sup.N×N, {right arrow over (b)}∈.sup.N and a.sub.ij is the matrix entry of the matrix A in the i-th row and the j-th column, the linear system in Eq. (28) is equivalent to:

[00014]$\begin{array}{cc}\{\begin{array}{c}\underset{j}{.Math.}{a}_{0j}{x}_j-b_0=0\\ \underset{j}{.Math.}{a}_{1j}{x}_j-b_1=0\\ .Math.\\ \underset{j}{.Math.}{a}_{N-1,j}{x}_j-b_{N-1}=0\end{array}& \left(29\right)\end{array}$

[0168] Summing up the left-hand sides of Eq. (29) yields the objective function

min((Σ.sub.ja.sub.0jx.sub.j−b.sub.0).sup.2+(Σ.sub.ja.sub.1jx.sub.j−b.sub.1).sup.2+ . . . +(Σ.sub.ja.sub.N−1,jx.sub.j−b.sub.N−1).sup.2).  (30)

[0169] The minimum of the objective function in Eq. (30) is reached if and only if {right arrow over (x)} is a solution of the linear systems in Eqs. (28), (29).

[0170] Both equation representation and inequality representation may be used for determining MILPs.

[0171] In case of using equations, each Boolean function of the cryptographic procedures may be reduced to a single equation with binary ancillaries. A CPLEX-solver may be used to obtain coefficients of the equation. Using intermediate equations with binary ancillaries/auxiliary variables further allows for determining QUBOs specifically suited for Quantum Annealers.

[0172] Both MILP and QUBO problems may also in principle be solved by classical generic solvers such as CPLEX, Gurobi, SCIP, or CBC. However, the additional binary ancillaries may substantially increase the computing complexity, posing a challenge for classical solvers. In this regard, QUBO problems may considered to be more promising since they may be solved by a quantum annealing device such as D-Wave.

[0173] In case of inequalities without binary ancillaries, each Boolean function is reduced to a system of linear inequalities without any additional binary variables. The inequalities may explicitly be determined using polyhedra applications such as LRS. This approach is mainly, but not exclusively, suitable for classical solvers.

[0174] AES variants may use cryptographic keys which are longer than plaintext (AES-256 has 256 bits for the cryptographic key and 128 bits for the plaintext). Therefore, one plaintext block with 128 bits and its ciphertext are not sufficient to determine the full cryptographic key. However, two known plaintext blocks of 128 bits each (together with their corresponding ciphertexts) comprise sufficient information.

[0175] In order to treat the variants AES-192 and AES-256, two copies of the plurality/system of intermediate relations (equations or inequalities) are determined. A first system comprises a first plaintext and a first ciphertext generated from the first plaintext using the cryptographic key, and a second system comprises a second plaintext and a second ciphertext generated from the second plaintext using the (same) cryptographic key. The first and the second system can also be considered forming a (total) system of intermediate relations. From the first and the second system, a common optimization problem is determined and solved analogously to the case of AES-128.

[0176] The described method steps are not only suitable for AES, but also for other cryptographic procedures. Any cryptographic procedure which comprises a defined protocol and non-linear functions and which either has a limited amount of inputs bits or can be decomposed into the elementary operations XOR, AND etc. can be approached as well. Namely, the method can be adapted for IDEA, Salsa20, or ARX.

[0177] The features disclosed in this specification, the figures and/or the claims may be material for the realization of various embodiments, taken in isolation or in various combinations thereof.