Inverse polynomial backdoors search example for Bivium
An example of inverse polynomial backdoors searching to assess the cryptographic security of cryptographic functions using the example of the Bivium key stream generator.
1from os import cpu_count
2
3# algorithm module imports
4from algorithm.impl import Elitism
5from algorithm.module.mutation import Doer
6from algorithm.module.crossover import TwoPoint
7from algorithm.module.selection import Roulette
8
9# function module imports
10from function.impl import InversePolynomialSets
11from function.module.measure import Propagations
12
13# satprob lib imports
14from lib_satprob.encoding import CNF
15from lib_satprob.variables import Range
16from lib_satprob.problem import SatProblem
17from lib_satprob.solver import Py2SatSolver
18
19# core submodule imports
20from core.impl import Optimize
21from core.model.point import Point
22from core.module.sampling import Const
23from core.module.limitation import WallTime
24from core.module.comparator import MinValueMaxSize
25
26# other imports
27from space.impl import BackdoorSet
28from util.work_path import WorkPath
29from output.impl import OptimizeLogger
30from executor.impl import ProcessExecutor
31
32
33def run_bivium_search() -> Point:
34 root_path = WorkPath('examples')
35 data_path = root_path.to_path('data')
36
37 logs_path = root_path.to_path('logs', 'bivium')
38 cnf_file = data_path.to_file('bivium_200.cnf')
39 problem = SatProblem(
40 encoding=CNF(from_file=cnf_file),
41 solver=Py2SatSolver(sat_name='g3'),
42 input_set=Range(start=1, length=177),
43 output_set=Range(start=1838, length=200),
44 )
45
46 workers = min(cpu_count(), 16)
47 executor = ProcessExecutor(
48 max_workers=workers
49 )
50 print(f'Running on {workers} threads')
51
52 return Optimize(
53 problem=problem,
54 executor=executor,
55 space=BackdoorSet(
56 variables=Range(length=177)
57 ),
58 sampling=Const(
59 size=8192,
60 split_into=2048
61 ),
62 function=InversePolynomialSets(
63 measure=Propagations(),
64 ),
65 algorithm=Elitism(
66 elites_count=2,
67 population_size=6,
68 mutation=Doer(),
69 crossover=TwoPoint(),
70 selection=Roulette(),
71 min_update_size=6
72 ),
73 comparator=MinValueMaxSize(),
74 logger=OptimizeLogger(logs_path),
75 limitation=WallTime(from_string='12:00:00'),
76 ).launch()[0]
Other examples: