Utils¶

delete_espresso_dictionary(file_path)¶

espresso_pos_to_constraints(espresso_inequalities, variables)¶

generate_espresso_input(valid_points)¶

generate_product_of_sum_from_espresso(valid_points)¶

EXAMPLES:

sage: from itertools import product
sage: transitions = [(i1, i2, (i1 + i2) % 2) if (i1 < 2 and i2 < 2) else (i1, i2, 2) for i1, i2 in product(range(3),repeat=2)]
sage: from claasp.cipher_modules.models.milp.utils.utils import generate_product_of_sum_from_espresso
sage: bit_transitions = [ZZ(val[2]).digits(base=2, padto=2) + ZZ(val[1]).digits(base=2, padto=2) + ZZ(val[0]).digits(base=2, padto=2) for val in transitions]
sage: valid_points = ["".join(str(_) for _ in bit_transition[::-1]) for bit_transition in bit_transitions]
sage: espresso_inequalities = generate_product_of_sum_from_espresso(valid_points)
...

milp_and(model, a, b)¶: Returns constraints to model a and b, where a and b are binary variables. The binary variable a_and_b = 1 iff a == 1 and b == 1

milp_else(var_if, else_constraints, big_m)¶: Returns a list of variables and a list of constraints to model an else statement.

milp_eq(model, a, b, big_m)¶

Returns constraints to determine whether a == b, where b is a constant. The binary variable a_eq_b = 1 iff a == b

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: from claasp.cipher_modules.models.milp.utils.utils import milp_eq
sage: cipher = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: M = MilpModel(cipher)
sage: M.init_model_in_sage_milp_class()
sage: mip = M._model
sage: x = M._integer_variable; d = M._binary_variable
sage: a = x[0]; b = 2; big_m = 4
sage: dummy, constraints = milp_eq(M, a, b, big_m)
sage: for i in constraints:
....:     mip.add_constraint(i)
sage: dummy
x_3
sage: constraints
[x_0 <= 6 - 4*x_1,
 3 - 4*x_1 <= x_0,
 2 <= 4 + x_0 - 4*x_2,
 1 + x_0 - 4*x_2 <= 2,
 -1 + x_1 + x_2 <= x_3,
 x_3 <= x_1,
 x_3 <= x_2]

milp_generalized_and(model, var_list)¶

Returns constraints to model a_0 and a_1 and … a_n-1, where a_i’s are binary variables in var_list. The binary variable generalized_and = 1 iff a_i == 1 for all i.

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: from claasp.cipher_modules.models.milp.utils.utils import milp_generalized_and
sage: cipher = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: M = MilpModel(cipher)
sage: M.init_model_in_sage_milp_class()
sage: mip = M._model
sage: d = M._binary_variable
sage: var_list = [d[i] for i in range(4)]
sage: general_and, constraints = milp_generalized_and(M, var_list)
sage: for i in constraints:
....:     mip.add_constraint(i)
sage: general_and
x_4
sage: constraints
[-3 + x_0 + x_1 + x_2 + x_3 <= x_4,
 x_4 <= x_0,
 x_4 <= x_1,
 x_4 <= x_2,
 x_4 <= x_3]

milp_generalized_xor(input_var_list, output_bit)¶

Returns constraints to model a_0 xor a_1 xor … xor a_{n-1} = output_bit for binary variables

EXAMPLES:

sage: from claasp.cipher_modules.models.milp.utils.utils import milp_generalized_xor
sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: cipher = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: M = MilpModel(cipher)
sage: M.init_model_in_sage_milp_class()
sage: mip = M._model
sage: x = M._binary_variable
sage: var_list = [x[i] for i in range(2)]; b = x[2]
sage: for i in milp_generalized_xor(var_list, b):
....:     mip.add_constraint(i)
...
sage: var_list
[x_0, x_1]

milp_geq(model, a, b, big_m)¶: Returns constraints to determine whether a >= b, where a and b are integer variables or constants. The binary variable a_geq_b = 1 iff a >= b

milp_greater(model, a, b, big_m)¶: Returns constraints to determine whether a > b, where a and b are integer variables or constants. The binary variable a_greater_b = 1 iff a > b

milp_if_elif_else(model, var_if_list, then_constraints_list, else_constraints, big_m)¶

Returns a list of variables and a list of constraints to model an if-elif…-elif-else statement. When the binary variable var_if[i] == 1, the set ‘then_constraints[i]’ is applied, when all var_if variables are 0, the set ‘else_constraints’ is applied

https://stackoverflow.com/questions/41009196/if-then-elseif-then-in-mixed-integer-linear-programming

milp_if_then(var_if, then_constraints, big_m)¶: Returns a list of variables and a list of constraints to model an if-then statement. When the binary variable var_if == 1, the set ‘then_constraints’ is applied.

milp_if_then_else(var_if, then_constraints, else_constraints, big_m)¶: Returns a list of variables and a list of constraints to model an if-then-else statement. When the binary variable var_if == 1, the set ‘then_constraints’ is applied, when var_if == 0, the set ‘else_constraints’ is applied

milp_leq(model, a, b, big_m)¶: Returns constraints to determine whether a <= b, where a and b are integer variables or constants. The binary variable a_leq_b = 1 iff a <= b

milp_less(model, a, b, big_m)¶

Returns constraints to determine whether a < b, where ‘a’ is an integer variables and ‘b’ is an integer variable or a constant. The binary variable a_less_b = 1 iff a < b

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: from claasp.cipher_modules.models.milp.utils.utils import milp_less
sage: cipher = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: M = MilpModel(cipher)
sage: M.init_model_in_sage_milp_class()
sage: mip = M._model
sage: x = M._integer_variable; d = M._binary_variable
sage: mip.set_max(x,2); mip.set_min(x,0)
sage: a = x[0]; b = x[1]; big_m = 4
sage: dummy, constraints = milp_less(M, a, b, big_m)
sage: for i in constraints:
....:     mip.add_constraint(i)
sage: dummy
x_2
sage: constraints
[x_0 <= 3 + x_1 - 4*x_2, x_1 - 4*x_2 <= x_0]

milp_neq(model, a, b, big_m)¶

Returns constraints to determine whether a != b, where b is a constant. The binary variable a_neq_b = 1 iff a != b

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: from claasp.cipher_modules.models.milp.utils.utils import milp_neq
sage: cipher = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: M = MilpModel(cipher)
sage: M.init_model_in_sage_milp_class()
sage: mip = M._model
sage: x = M._integer_variable; d = M._binary_variable
sage: a = x[0]; b = 2; big_m = 4
sage: dummy, constraints = milp_neq(M, a, b, big_m)
sage: for i in constraints:
....:     mip.add_constraint(i)
sage: dummy
x_3
sage: constraints
[x_0 <= 5 - 4*x_1,
 2 - 4*x_1 <= x_0,
 2 <= 3 + x_0 - 4*x_2,
 x_0 - 4*x_2 <= 2,
 x_3 <= x_1 + x_2,
 x_1 <= x_3,
 x_2 <= x_3]

milp_or(model, a, b)¶: Returns constraints to model a or b, where a and b are binary variables. The binary variable a_or_b = 1 iff a == 1 or b == 1

milp_xor(a, b, c)¶

Returns constraints to model a xor b = c for binary variables

EXAMPLES:

sage: from claasp.ciphers.block_ciphers.simon_block_cipher import SimonBlockCipher
sage: from claasp.cipher_modules.models.milp.utils.utils import milp_xor
sage: cipher = SimonBlockCipher(block_bit_size=32, key_bit_size=64, number_of_rounds=2)
sage: from claasp.cipher_modules.models.milp.milp_model import MilpModel
sage: M = MilpModel(cipher)
sage: M.init_model_in_sage_milp_class()
sage: mip = M._model
sage: x = M._binary_variable
sage: a = x[0]; b = x[1]; c = x[2]
sage: for i in milp_xor(a,b,c):
....:     mip.add_constraint(i)
sage: a
x_0

milp_xor_truncated(model, input_1, input_2, output)¶

Returns a list of variables and a list of constraints for the XOR for two input bits in the deterministic truncated XOR differential model.

This method uses a binary encoding (where each variable v is seen as a binary tuple (v0, v1), where v0 is the MSB) to model the result c of the truncated XOR between inputs a and b.

a | b | c

0 | 0 | 0 0 | 1 | 1 0 | 2 | 2 1 | 0 | 1 1 | 1 | 0 1 | 2 | 2 2 | 0 | 2 2 | 1 | 2 2 | 2 | 2

The table can be obtained with the following lines:

sage: from itertools import product sage: transitions = [(i1, i2, (i1 + i2) % 2) if (i1 < 2 and i2 < 2) else (i1, i2, 2) for i1, i2 in product(range(3),repeat=2)]

Espresso was used to reduce the number of constraints to 10 inequalities:

sage: from claasp.cipher_modules.models.milp.utils.utils import generate_product_of_sum_from_espresso sage: bit_transitions = [ZZ(val[2]).digits(base=2, padto=2) + ZZ(val[1]).digits(base=2, padto=2) + ZZ(val[0]).digits(base=2, padto=2) for val in transitions] sage: valid_points = [“”.join(str(_) for _ in bit_transition[::-1]) for bit_transition in bit_transitions] sage: espresso_inequalities = generate_product_of_sum_from_espresso(valid_points)

milp_xor_truncated_wordwise(model, input_1, input_2, output)¶

Returns a list of variables and a list of constraints for the XOR for two input bytes in deterministic truncated XOR differential model.

This method uses a binary encoding (where each variable v is seen as a binary tuple (v0, v1), where v0 is the MSB) to model the result c of the truncated XOR between inputs a and b.

a | b | c

0 | 0 | 0 0 | 1 | 1 0 | 2 | 2 0 | 3 | 3 1 | 0 | 1 1 | 1 | 0 1 | 1 | 1 1 | 2 | 3 1 | 3 | 3 2 | 0 | 2 2 | 1 | 3 2 | 2 | 3 2 | 3 | 3 3 | 0 | 3 3 | 1 | 3 3 | 2 | 3 3 | 3 | 3

Espresso was used to reduce the number of constraints to 91 inequalities.

output_espresso_dictionary(file_path)¶

Utils¶

Previous topic

Next topic

This Page