OKlibrary
0.2.1.6

Investigations into the AES Sbox. More...
Go to the source code of this file.
Investigations into the AES Sbox.
cycletype_pmtf(rijn_sbox_pmtf,256); [[2,1],[27,1],[59,1],[81,1],[87,1]] order_element_pmtf(rijn_sbox_pmtf,256); 277182
> cat AES_Sbox_full.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 65280 1044480 0 1044480 1 1 length count 16 65280
> QuineMcCluskeyn16O3DNDEBUG AES_Sbox_full.cnf > AES_PK.cnf > cat AES_PK.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 136253 999896 0 999896 1 1 length count 5 1 6 4148 7 82659 8 48615 9 830
> QuineMcCluskeySubsumptionHypergraphn16O3DNDEBUG AES_Sbox_full.cnf > AES_S.cnf > cat AES_S.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n > AES_S_stat > head 2 AES_S_stat n non_taut_c red_l taut_c orig_l comment_count finished_bool 136253 65280 59122688 0 59122688 1 1
> E=read.table("AES_S_stat",skip=2,header=TRUE) length count Min. : 170.0 Min. : 1.00 1st Qu.: 555.2 1st Qu.: 11.25 Median : 846.5 Median : 38.00 Mean : 845.8 Mean : 55.99 3rd Qu.:1137.8 3rd Qu.:102.00 Max. :1517.0 Max. :173.00 > plot(E)
maxima> oklib_load_all()$ maxima> output_rijnsbox_fullcnf_stdname()$ shell> QuineMcCluskeySubsumptionHypergraphn16O3DNDEBUG AES_Sbox_full.cnf > AES_Sbox_shg.cnf shell> cat AES_Sbox_shg.cnf  MinOnes2WeightedMaxSATO3DNDEBUG > AES_Sbox_shg.wcnf shell> ubcsatokl alg gsat w runs 100 cutoff 40000000 wtarget 294 solve 1 seed 3213901809 i AES_Sbox_shg.wcnf r model AES_Sbox_s294.ass; shell> cat AES_Sbox_full.cnf_primes  FilterDimacs AES_Sbox_s294.ass > AES_Sbox_s294.cnf
shell> F_Sbox_pi : read_fcl_f("AES_Sbox_full.cnf_primes")$ shell> F_Sbox : read_fcl_f("AES_Sbox_s294.cnf")$ shell> hardness_wpi_cs(setify(F_Sbox[2]), setify(F_Sbox_pi[2])); 4
maxima> output_rijnsbox_fullcnf_stdname();
shell> QuineMcCluskeySubsumptionHypergraphn16O3DNDEBUG AES_Sbox_full.cnf > AES_Sbox_shg.cnf shell> cat AES_Sbox_shg.cnf  MinOnes2WeightedMaxSATO3DNDEBUG > AES_Sbox_shg.wcnf
shell> ubcsatokl alg gsat w runs 100 cutoff 40000000 wtarget 294 solve 1 seed 3213901809 i AES_Sbox_shg.wcnf r model AES_Sbox_s294.ass; shell> cat AES_Sbox_full.cnf_primes  FilterDimacs AES_Sbox_s294.ass > AES_Sbox_s294.cnf
shell> cat AES_Sbox_s294.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG c's = 0, n = 16, c = 294, tc = 0, ntc = 294, tl = 1939, l = 1939, finished = 1 6 : 143 7 : 127 8 : 24
> is(rijnsbox_fulldnf_fcs()[2] = all_sat_fcs(Sbox294CNFF)); true
maxima> SboxCNF: fcs2fcl(ss_sbox_fullcnf_fcs(2,4,ss_polynomial_2_4))$ maxima> output_tt2pla(fcl2tt( SboxCNF ),"Sbox.pla")$
shell> espresso2.3 Dexact Sbox.pla
maxima> SboxCNF: fcs2fcl(ss_sbox_fullcnf_fcs(2,4,ss_polynomial_2_4))$ maxima> output_tt2pla(fcl2tt( SboxCNF ),"Sbox.pla")$
shell> espresso2.3 Sbox.pla
maxima> SboxCNF: fcs2fcl(ss_sbox_fullcnf_fcs(2,4,ss_polynomial_2_4))$ maxima> output_tt2table(fcl2tt(SboxCNF),"Sbox.dat")$
R> oklib_load_all() R> library(QCA) R> sbox_tt = read.table("Sbox.dat",header=TRUE) R> eqmcc(sbox_tt, outcome="O", expl.0=TRUE)
Error: Impossible to solve the PI chart (too many possible combinations).
> RUcpGenO3DNDEBUG AES_PK.cnf > AES_gen.cnf > cat AES_gen.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 9050 63306 0 63306 1 1 length count 5 1 6 1373 7 6363 8 1295 9 18 > seed=1; cat AES_gen.cnf  RandomShuffleDimacsO3DNDEBUG ${seed}  RUcpBaseO3DNDEBUG  tee AES_base_${seed}.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4754 32530 0 32530 1 1 length count 5 1 6 1140 7 3223 8 386 9 4 > seed=2; cat AES_gen.cnf  RandomShuffleDimacsO3DNDEBUG ${seed}  RUcpBaseO3DNDEBUG  tee AES_base_${seed}.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4765 32606 0 32606 1 1 length count 5 1 6 1135 7 3245 8 380 9 4 > seed=3; cat AES_gen.cnf  RandomShuffleDimacsO3DNDEBUG ${seed}  RUcpBaseO3DNDEBUG  tee AES_base_${seed}.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4739 32404 0 32404 1 1 length count 5 1 6 1152 7 3205 8 377 9 4
maxima> FF_sbox_ts : ss_sbox_ts_gen(2,8,ss_polynomial_2_8)$ maxima> statistics_fcs(F_sbox_ts); [272,4353,12800,256,2] maxima> ncl_list_full_dualts(16,256); [[2,4096],[17,256],[256,1]]
> RUcpGenO3DNDEBUG AES_PK_sorted.cnf  tee sbox_gen_from_sorted.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 5883 39850 0 39850 1 1 length count 5 1 6 1798 7 3619 8 461 9 4
> cat sbox_gen_from_sorted.cnf  RUcpBaseO3DNDEBUG  tee sbox_base_from_sorted.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4596 31523 0 31523 0 1 length count 5 1 6 1109 7 3028 8 454 9 4
> cat sbox_gen_from_revsorted.cnf  RUcpBaseO3DNDEBUG  tee sbox_base_from_revsorted.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4474 30569 0 30569 0 1 length count 5 1 6 1207 7 2810 8 452 9 4
shell> RandomRUcpBases AES_Sbox_full.cnf <snip> *** Currently trying gs=59,bs=2 n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4401 30169 0 30169 0 1 length count 5 1 6 1155 7 2730 8 511 9 4  CURRENT MINIMUM RBASE: *4401* with gs=59,bs=2  <snip> *** Currently trying gs=103,bs=1 n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4398 30108 0 30108 0 1 length count 5 1 6 1187 7 2703 8 503 9 4  CURRENT MINIMUM RBASE: *4398* with gs=103,bs=1  <snip>
> cat AES_294.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 294 1939 0 1939 0 1 length count 6 143 7 127 8 24 > cat AES_294.cnf  SortByClauseLengthO3DNDEBUG > AES_294_sorted.cnf
> RUcpGenO3DNDEBUG AES_PK_sorted.cnf AES_294_sorted.cnf  tee sbox_gen.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 5967 40615 0 40615 1 1 length count 5 1 6 1638 7 3847 8 476 9 5 > seed=1; cat sbox_gen.cnf  RUcpBaseO3DNDEBUG  tee AES_base_nosort_${seed}.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4735 32492 0 32492 0 1 length count 5 1 6 1106 7 3178 8 445 9 5 > seed=1; cat sbox_gen.cnf  SortByClauseLengthO3DNDEBUG  RUcpBaseO3DNDEBUG  tee AES_base_sorted_${seed}.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4744 32562 0 32562 0 1 length count 5 1 6 1099 7 3194 8 445 9 5 > seed=1; cat sbox_294_gen_revsort.cnf  RUcpBaseO3DNDEBUG  tee AES_base_revsort_${seed}.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 4658 31869 0 31869 0 1 length count 5 1 6 1190 7 3017 8 445 9 5
length(rijnsbox2hittingcnf_fcs(dll_heuristics_first_formal)); 2048 length(rijnsbox2hittingcnf_fcs(dll_heuristics_first_real)); 2048 length(rijnsbox2hittingcnf_fcs(dll_heuristics_first_shortest_clause)); 2048 statistics_cs(rijnsbox2hittingcnf_fcs(dll_heuristics_max_lit)); [16, 1513, 19546, 16, 6] length(rijnsbox2hittingcnf_fcs(dll_heuristics_max_var)); 2048 statistics_cs(rijnsbox2hittingcnf_fcs(dll_heuristics_max_lit_tb(3,3))); [16, 1468, 18925, 16, 6] statistics_cs(rijnsbox2hittingcnf_fcs(dll_heuristics_max_lit_tb(4,4))); [16, 1438, 18536, 16, 6]
id3_entropy_fcs_full(FF) := block([p_0, p_1], p_0 : length(FF[2])/(2^length(FF[1])), p_1 : 1  p_0, if p_0 = 0 or p_1 = 0 then return(0) else return( (p_0 * log(p_0) + p_1 * log(p_1)) / log(2)))$ id3_gain_fcs_full(FF,v) := block([FF_v0, FF_v1, total_space], FF_v0 : apply_pa_fcs({v}, FF), FF_v1 : apply_pa_fcs({v}, FF), total_space : 2^length(FF[1]), id3_entropy_full(FF)  ((length(FF_v0[2])/total_space) * id3_entropy_full(FF_v0) + (length(FF_v1[2])/total_space) * id3_entropy_full(FF_v1)))$ id3_heuristic_fcs_full(FF) := block([max_v, max_gain : minf], for v in FF[1] do block([cur_gain], cur_gain : id3_gain_full(FF,v), if cur_gain > max_gain then (max_v : v, max_gain : cur_gain)), return(max_v))$ F : rijnsbox2hittingcnf_fcs(id3_heuristic_fcs_full)$ statistics_cs(F); [16,2048,25600,16,9]
rijnsbox_cnfp(cs_to_fcs(rijnsbox2hittingcnf_fcs(dll_heuristics_max_lit)));
statistics_cs(rijnsbox2hittingcnf_fcs(johnson_heuristic)); [16, 1516, 19573, 16, 6] statistics_cs(rijnsbox2hittingcnf_fcs(choose_most_sat_literal_h(satprob_dll_simplest_trivial1))); [16, 1516, 19573, 16, 6]
> QuineMcCluskeyn16O3DNDEBUG AES_Sbox_full.cnf > AES_PK.cnf > cat AES_PK.cnf  ExtendedDimacsFullStatisticsO3DNDEBUG n non_taut_c red_l taut_c orig_l comment_count finished_bool 16 136253 999896 0 999896 1 1 length count 5 1 6 4148 7 82659 8 48615 9 830
h_aes : rijnsbox2hittingcnf_fcs(dll_heuristics_max_lit)$ p_aes : replace_by_prime_implicates_hitting(h_aes)$ statistics_cs(p_aes); [16, 1359, 9430, 9, 6] ncl_list_cs(p_aes); [[6, 265], [7, 913], [8, 180], [9, 1]] irredundant_bydef(cs_to_fcs(p_aes), dll_simplest_trivial1); false ip_aes : first_irr_fcs(cs_to_fcs(p_aes), dll_simplest_trivial2)$ statistics_cs(ip_aes[2]); [16, 581, 4006, 8, 6] rijnsbox_cnfp(ip_aes); true h2_aes : rijnsbox2hittingcnf_fcs(dll_heuristics_max_lit_tb(4,4))$ rijnsbox_cnfp(cs_to_fcs(h2_aes)); true p2_aes : replace_by_prime_implicates_hitting(h2_aes)$ statistics_cs(p2_aes); [16, 1303, 9011, 9, 6] ip2_aes : first_irr_fcs(cs_to_fcs(p2_aes), dll_simplest_trivial2)$ statistics_cs(ip2_aes[2]); [16, 559, 3838, 8, 6] rijnsbox_cnfp(ip2_aes); true h0_aes : rijnsbox2hittingcnf_fcs(dll_heuristics_first_formal)$ p0_aes : replace_by_prime_implicates_hitting(h0_aes)$ statistics_cs(p0_aes); [16, 1722, 12118, 9, 5] ip0_aes : first_irr_fcs(cs_to_fcs(p0_aes), dll_simplest_trivial2)$ statistics_cs(ip0_aes[2]); [16, 680, 4784, 9, 5] rijnsbox_cnfp(ip0_aes); true
ir_p_aes : all_irrcl_bydef(cs_to_fcs(p_aes), dll_simplest_trivial2)$ statistics_cs(ir_p_aes); [16, 447, 3087, 8, 6] ncl_list_cs(ir_p_aes); [[6, 99], [7, 291], [8, 57]] oklib_monitor : true; oklib_monitor_level : 1; irrc_p_aes : all_irr_cores_bydef(cs_to_fcs(p_aes), dll_simplest_trivial2)$
Definition in file Sbox_8.hpp.