OKlibrary  0.2.1.6
Mul_13_8.hpp File Reference

Investigations into AES field multiplication by 13 for the 8-bit field. More...

Go to the source code of this file.


Detailed Description

Investigations into AES field multiplication by 13 for the 8-bit field.

Todo:
Basic data
  • The CNF-file "AES_byte_field_mul_full_13.cnf" is created by the Maxima-function output_rijnmult_fullcnf_stdname(13); in ComputerAlgebra/Cryptology/Lisp/Cryptanalysis/Rijndael/FieldOperationsAnalysis.mac, which is a full clause-set with 16 variables and 2^16 - 2^8 = 65280 clauses:
    > cat AES_byte_field_mul_full_13.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG 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
       
  • Computing the prime implicates:
    maxima> output_rijnmult_fullcnf_stdname(13);
       
    and then
    shell> QuineMcCluskey-n16-O3-DNDEBUG AES_byte_field_mul_full_13.cnf > AES_byte_field_mul_pi_13.cnf
       
    yields a CNF with:
    shell> ExtendedDimacsFullStatistics-O3-DNDEBUG < AES_byte_field_mul_pi_13.cnf
    c's = 1, n = 16, c = 15312, tc = 0, ntc = 15312, tl = 122816, l = 122816, finished = 1
    4 : 80
    5 : 192
    6 : 1152
    7 : 2368
    8 : 5632
    9 : 5888
       
  • The smallest known CNF representation is of size 60 (see "Using weighted MaxSAT to compute small CNFs").
  • The minimum size CNF representation is *not* known.
Todo:
r_1-bases : mincl_r1 <= 1040
  • Computing an r_1-base:
    shell> QuineMcCluskey-n16-O3-DNDEBUG AES_byte_field_mul_full_13.cnf > AES_byte_field_mul_pi_13.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_byte_field_mul_pi_13.cnf | SortByClauseLength-O3-DNDEBUG > AES_byte_field_mul_13_sortedpi.cnf
    shell> RUcpGen-O3-DNDEBUG AES_byte_field_mul_13_sortedpi.cnf > AES_byte_field_mul_13_gen.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_byte_field_mul_13_gen.cnf | SortByClauseLengthDescending-O3-DNDEBUG | RUcpBase-O3-DNDEBUG > AES_byte_field_mul_13_base.cnf
    shell> cat AES_byte_field_mul_13_base.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
     n non_taut_c red_l taut_c orig_l comment_count finished_bool
    16 1040 6016 0 6016 0 1
     length count
    4 80
    5 192
    6 640
    7 128
       
Todo:
Using weighted MaxSAT to compute small CNFs : mincl_rinf <= 60
  • Computing the weighted MaxSAT problem:
    shell> QuineMcCluskeySubsumptionHypergraph-n16-O3-DNDEBUG AES_byte_field_mul_full_13.cnf > AES_byte_field_mul_shg_13.cnf
    shell> cat AES_byte_field_mul_shg_13.cnf | MinOnes2WeightedMaxSAT-O3-DNDEBUG > AES_byte_field_mul_13_shg.wcnf
       
  • Running then:
    shell> ubcsat-okl -alg gsat -w -cutoff 1000000 -runs 100 -i AES_byte_field_mul_13_shg.wcnf
       
    yields:
           sat  min     osteps     msteps       seed
          1 0    60               286294              1000000  673057735
    <snip>
    TotalLiterals = 5323728
    FlipsPerSecond = 25097
    BestStep_Mean = 336474.79
    Steps_Mean = 1000000
    Steps_Max = 1000000
    PercentSuccess = 0.00
    BestSolution_Mean = 64.99
    BestSolution_Median = 66
    BestSolution_Min = 60
    BestSolution_Max = 73
       

Definition in file Mul_13_8.hpp.