OKlibrary  0.2.1.6
Mul_14_8.hpp File Reference

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

Go to the source code of this file.


Detailed Description

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

Todo:
Basic data
  • The CNF-file "AES_byte_field_mul_full_14.cnf" is created by the Maxima-function output_rijnmult_fullcnf_stdname(14); 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_14.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(14);
       
    and then
    shell> QuineMcCluskey-n16-O3-DNDEBUG AES_byte_field_mul_full_14.cnf > AES_byte_field_mul_pi_14.cnf
       
    yields a CNF with:
    shell> ExtendedDimacsFullStatistics-O3-DNDEBUG < AES_byte_field_mul_pi_14.cnf
    ExtendedDimacsFullStatistics-O3-DNDEBUG < AES_byte_field_mul_pi_14.cnf
    c's = 1, n = 16, c = 14300, tc = 0, ntc = 14300, tl = 114252, l = 114252, finished = 1
    3 : 4
    4 : 56
    5 : 288
    6 : 960
    7 : 2496
    8 : 5120
    9 : 5376
       
  • The smallest known CNF representation is of size 56 (see "Using weighted MaxSAT to compute small CNFs").
  • The minimum size CNF representation is *not* known.
Todo:
r_1-bases : mincl_r1 <= 1052
  • Computing an r_1-base:
    shell> QuineMcCluskey-n16-O3-DNDEBUG AES_byte_field_mul_full_14.cnf > AES_byte_field_mul_pi_14.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_byte_field_mul_pi_14.cnf | SortByClauseLength-O3-DNDEBUG > AES_byte_field_mul_14_sortedpi.cnf
    shell> RUcpGen-O3-DNDEBUG AES_byte_field_mul_14_sortedpi.cnf > AES_byte_field_mul_14_gen.cnf
    shell> RandomShuffleDimacs-O3-DNDEBUG 1 < AES_byte_field_mul_14_gen.cnf | SortByClauseLengthDescending-O3-DNDEBUG | RUcpBase-O3-DNDEBUG > AES_byte_field_mul_14_base.cnf
    shell> cat AES_byte_field_mul_14_base.cnf | ExtendedDimacsFullStatistics-O3-DNDEBUG n
     n non_taut_c red_l taut_c orig_l comment_count finished_bool
    16 1052 6348 0 6348 0 1
     length count
    3 4
    4 56
    5 224
    6 384
    7 384
       
Todo:
Using weighted MaxSAT to compute small CNFs : mincl_rinf <= 56
  • Computing the weighted MaxSAT problem:
    shell> QuineMcCluskeySubsumptionHypergraph-n16-O3-DNDEBUG AES_byte_field_mul_full_14.cnf > AES_byte_field_mul_shg_14.cnf
    shell> cat AES_byte_field_mul_shg_14.cnf | MinOnes2WeightedMaxSAT-O3-DNDEBUG > AES_byte_field_mul_14_shg.wcnf
       
  • Running then:
    shell> ubcsat-okl -alg gsat -w -cutoff 1000000 -runs 100 -i AES_byte_field_mul_14_shg.wcnf
       
    yields:
    <snip>
         27 0    64               500386              1000000 2630623820
         28 0    62               184936              1000000  978348806
         29 0    64               432908              1000000 1970436541
         30 0    56               237214              1000000 3535520173
         31 0    62               388161              1000000 2840264849
    <snip>
    TotalLiterals = 5126108
    FlipsPerSecond = 25499
    BestStep_Mean = 346536.54
    Steps_Mean = 1000000
    Steps_Max = 1000000
    PercentSuccess = 0.00
    BestSolution_Mean = 62.38
    BestSolution_Median = 62
    BestSolution_Min = 56
    BestSolution_Max = 72
       

Definition in file Mul_14_8.hpp.