Ignore:
Timestamp:
Sep 8, 2009, 11:13:15 AM (12 years ago)
Author:
oruba
Message:

Implementation of algorithm RandomWalk to find maxterms.

Location:
trunk/CrypPlugins/CubeAttack
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/CubeAttack/CubeAttack.cs

    r471 r472  
    3030
    3131        private CubeAttackSettings settings;
    32         //private int inputBlackBox;
    3332        private string outputMaxterm;
    3433        private string outputKeyBits;
    35         //private bool[] outputPublicBit = new bool[3];
    36         //private bool[] outputSecretBit = new bool[3];
    3734        private enum CubeAttackMode { findMaxterms, setPublicBits };
    3835        private List<CryptoolStream> listCryptoolStreamsOut = new List<CryptoolStream>();
     36        private bool stop = false;
     37
     38        #endregion
     39
     40
     41        #region Properties (Inputs/Outputs)
    3942       
    40         #endregion
    41 
    42         #region Public Variables
    43         public bool lastEventwasInputBB = false;
    44         public bool inputBBFlag = true;
    45         //public bool inputBBFlag = false;
    46         #endregion
    47 
    48         #region Properties (Inputs/Outputs)
    49 
    50         /*[PropertyInfo(Direction.Input,
    51             "Black box input",
    52             "The output bit from the black box",
    53             "",
    54             false,
    55             false,
    56             DisplayLevel.Beginner,
    57             QuickWatchFormat.Text,
    58             null)]
    59         public int InputBlackBox
    60         {
    61             get {
    62                 return this.inputBlackBox; }
    63             set
    64             {
    65                
    66                     this.inputBlackBox = value;
    67                     OnPropertyChanged("InputBlackBox");
    68             }
    69         }*/
    70 
    71         /*[PropertyInfo(Direction.Output,
    72             "Public bits",
    73             "Array of public bits",
    74             "",
    75             false,
    76             false,
    77             DisplayLevel.Beginner,
    78             QuickWatchFormat.Text,
    79             null)]
    80         public bool[] OutputPublicBit
    81         {
    82             get { return this.outputPublicBit; }
    83             set
    84             {
    85                 outputPublicBit = value;
    86                 OnPropertyChanged("OutputPublicBit");
    87             }
    88         }
    89 
    90         [PropertyInfo(Direction.Output,
    91             "Secret bits",
    92             "Array of secret bits",
    93             "",
    94             false,
    95             false,
    96             DisplayLevel.Beginner,
    97             QuickWatchFormat.Text,
    98             null)]
    99         public bool[] OutputSecretBit
    100         {
    101             get { return this.outputSecretBit; }
    102             set
    103             {
    104                 outputSecretBit = value;
    105                 OnPropertyChanged("OutputSecretBit");
    106             }
    107         }
    108         */
    10943        [PropertyInfo(Direction.OutputData,
    11044            "Maxterm output",
     
    16599        #endregion
    166100
     101
    167102        #region Public interface
    168103
     
    203138        #endregion
    204139
     140
    205141        #region IPlugin members
    206142
     
    211147        public void Dispose()
    212148        {
     149            stop = false;
     150            this.stop = false;
    213151            foreach (CryptoolStream stream in listCryptoolStreamsOut)
    214152            {
     
    250188        public void Stop()
    251189        {
     190            this.stop = true;
    252191        }
    253192
     
    275214            try
    276215            {
    277                     switch (settings.Action)
    278                     {
    279                         case 0:
    280                             int result = TestProperty.SolveFunction(null, null, 1);
    281                             CubeAttack_LogMessage("Rückgabewert innerhalb der Execute 1: " + result, NotificationLevel.Info);
    282                             result = TestProperty.SolveFunction(null, null, 2);
    283                             CubeAttack_LogMessage("Rückgabewert innerhalb der Execute 2: " + result, NotificationLevel.Info);
    284                             //FindMaxterms();
    285                             break;
    286                         case 1:
    287                             SetPublicBits();
    288                             break;
    289                     }
     216                switch (settings.Action)
     217                {
     218                    case 0:
     219                        FindMaxterms();
     220                        break;
     221                    case 1:
     222                        SetPublicBits();
     223                        break;
     224                }
    290225            }
    291226            catch (Exception ex)
     
    299234        }
    300235
    301         // Returns the output bit of the master polynomial P
     236        /// <summary>
     237        /// Returns the output bit of the master polynomial p
     238        /// </summary>
     239        /// <param name="v">Public bits.</param>
     240        /// <param name="x">Secret bits.</param>
     241        /// <returns>Returns the output bit of the master polynomial, either 0 or 1.</returns>
    302242        public int Blackbox(int[] v, int[] x)
    303243        {
     
    310250                for (int i = 0; i < v.Length; i++)
    311251                {
    312                     vBool[i] = Convert.ToBoolean(v[i]); //v[i] > 0 ? true : false;
    313                     xBool[i] = x[i] > 0 ? true : false;
     252                    vBool[i] = Convert.ToBoolean(v[i]);
     253                    xBool[i] = Convert.ToBoolean(x[i]);
    314254                }
    315255
     
    318258                System.Buffer.BlockCopy(xBool, 0, vx, vBool.Length, xBool.Length);
    319259
    320                 bool[] temp1 = new bool[6];
    321                 temp1[0] = true;
    322                 temp1[1] = false;
    323                 temp1[2] = false;
    324                 temp1[3] = true;
    325                 temp1[4] = false;
    326                 temp1[5] = false;
    327 
    328                 int[] temp = new int[6];
    329                 temp[0] = 1;
    330                 temp[3] = 1;
    331 
    332                 string function = "i_0.0 + i_0.1 + i_0.3 * i_0.0 + i_0.1 + i_0.5 * i_0.2 + i_0.3 + i_0.4 * i_0.0 + i_0.3 * i_0.0 + i_0.4 * i_0.1 + i_0.5 * i_0.2 + i_0.4 * i_0.3 + i_0.5 * i_0.0 * i_0.1 * i_0.3 * i_0.4 * 1";
    333 
    334                 string fnc = "i_0.0 + i_0.1 + i_0.3";
    335                 //CubeAttack_LogMessage("Parser = " + TestProperty.SolveFunction(function, temp1).ToString(), NotificationLevel.Info);
    336                 //CubeAttack_LogMessage("Intern = " + (temp[0] & temp[1] & temp[3] ^ temp[0] & temp[1] & temp[5] ^ temp[2] & temp[3] & temp[4] ^ temp[0] & temp[3] ^ temp[0] & temp[4] ^ temp[1] & temp[5] ^ temp[2] & temp[4] ^ temp[3] & temp[5] ^ temp[0] ^ temp[1] ^ temp[3] ^ temp[4] ^ 1), NotificationLevel.Info);
    337 
    338                 result = TestProperty.SolveFunction(function, vx, 1);
    339                
     260                result = TestProperty.SolveFunction(null, vx);
    340261            }
    341262            catch (Exception ex)
     
    350271            else
    351272                return result;
    352 
     273           
    353274            // ****** Beispiel Master Polynome ******
    354             //return v[0] & x[0] ^ v[0] & x[1] ^ v[1] & x[1] ^ v[0] ^ x[1] ^ v[0] & v[1] ^ v[1] & x[0] & x[1] ^ 1;
    355             //return v[0] & x[0] ^ v[0] & x[1] ^ v[1] & x[1] ^ v[0] ^ x[1] ^ v[0] & v[1] ^ v[1] & x[0] & x[1] ^ 1;
    356 
     275
     276            //       i_0.0 * i_0.2 + i_0.0 * i_0.3 + i_0.1 * i_0.3 + i_0.0 + i_0.3 + i_0.0 * i_0.1 + i_0.1 * i_0.2 * i_0.3 + 1
     277            //return v[0]  & x[0]  ^ v[0]  & x[1]  ^ v[1]  & x[1]  ^ v[0]  ^ x[1]  ^ v[0]  & v[1]  ^ v[1]  & x[0]  & x[1]  ^ 1;
     278           
     279            //i_0.0 * i_0.1 * i_0.3 + i_0.0 * i_0.1 * i_0.4 + i_0.2 * i_0.3 * i_0.5 + i_0.1 * i_0.5 + i_0.0 * i_0.3 + i_0.0 * i_0.1 + i_0.3 * i_0.5 + i_0.1 + i_0.5 + 1
    357280            //return v[0] & v[1] & x[0] ^ v[0] & v[1] & x[1] ^ v[2] & x[0] & x[2] ^ v[1] & x[2] ^ v[0] & x[0] ^ v[0] & v[1] ^
    358281              //   x[0] & x[2] ^ v[1] ^ x[2] ^ 1;
    359282
     283            // i_0.0 * i_0.1 * i_0.3 + i_0.0 * i_0.1 * i_0.5 + i_0.2 * i_0.3 * i_0.4 + i_0.0 * i_0.3 + i_0.0 * i_0.4 + i_0.1 * i_0.5 + i_0.2 * i_0.4 + i_0.3 * i_0.5 + i_0.0 + i_0.1 + i_0.3 + i_0.4 + 1
    360284            //return v[0] & v[1] & x[0] ^ v[0] & v[1] & x[2] ^ v[2] & x[0] & x[1] ^ v[0] & x[0] ^ v[0] & x[1] ^ v[1] & x[2] ^
    361                //  v[2] & x[1] ^ x[0] & x[2] ^ v[0] ^ v[1] ^ x[0] ^ x[1] ^ 1;
    362 
     285              //         v[2] & x[1] ^ x[0] & x[2] ^ v[0] ^ v[1] ^ x[0] ^ x[1] ^ 1;
     286
     287            //i_0.0 * i_0.1 * i_0.7 + i_0.2 * i_0.4 * i_0.6 + i_0.0 * i_0.3 * i_0.8 + i_0.0 * i_0.3 * i_0.7 + i_0.1 * i_0.2 * i_0.6 + i_0.3 * i_0.4 * i_0.9 + i_0.2 * i_0.4 * i_0.8 + i_0.2 * i_0.4 * i_0.9 + i_0.2 * i_0.4 * i_0.5 + i_0.2 * i_0.4 * i_0.7 + i_0.0 * i_0.1 * i_0.2 + i_0.0 * i_0.1 + i_0.3 * i_0.6 + i_0.3 * i_0.4 + i_0.6 * i_0.7 + i_0.6 * i_0.8 + i_0.4 + i_0.7 + i_0.6 + i_0.5 + i_0.1 * i_0.9
    363288            /*return v[0] & v[1] & x[2] ^ v[2] & v[4] & x[1] ^ v[0] & v[3] & x[3] ^ v[0] & v[3] & x[2] ^
    364289                v[1] & v[2] & x[1] ^ v[3] & v[4] & x[4] ^ v[2] & v[4] & x[3] ^ v[2] & v[4] & x[4] ^
     
    446371
    447372        /// <summary>
    448         /// Searches for the free term and the coefficients in the superpoly
    449         /// </summary>
    450         /// <param name="secVarElement">Secret values.</param>
    451         /// <param name="pubVarElement">Public values.</param>
    452         /// <param name="cube">Cube I.</param>
     373        /// The function derives the algebraic structure of the superpoly from the maxterm.
     374        /// The structure is derived by computing the free term and the coefficients in the superpoly.
     375        /// </summary>
     376        /// <param name="cube">The summation cube I.</param>
    453377        /// <returns>Returns the superpoly of I in p.</returns>
    454378        public List<int> ComputePSI(List<int> cube)
     
    491415
    492416        /// <summary>
    493         /// Outputs the maxterms.
     417        /// The function outputs a superpoly and its corresponding maxterm.
    494418        /// </summary>
    495419        /// <param name="cube">The summation Cube I.</param>
     
    533457
    534458        /// <summary>
    535         /// Outputs the key bits.
    536         /// </summary>
    537         /// <param name="res">Vector with the secret bits.</param>
    538         public void OutputKB(Vector res)
     459        /// The function outputs the key bits.
     460        /// </summary>
     461        /// <param name="res">Result Vector</param>
     462        public void OutputKey(Vector res)
    539463        {
    540464            StringBuilder output = new StringBuilder(string.Empty);
     
    550474        /// <param name="matrix">An n x n matrix whose rows contain their corresponding superpolys.</param>
    551475        /// <returns>A boolean value indicating if the superpoly is in the matrix or not.</returns>
    552         public bool IsInMatrix(List<int> superpoly, Matrix matrix)
     476        public bool InMatrix(List<int> superpoly, Matrix matrix)
     477
    553478        {
    554479            bool isEqual = true;
     
    565490        }
    566491
    567         public bool IsCubeKnown(List<int> cube, Matrix mCube)
     492        /// <summary>
     493        /// Test if cube is already known.
     494        /// </summary>
     495        /// <param name="mCube">A list of cubes.</param>
     496        /// <param name="cube">The summation cube I.</param>
     497        /// <returns>A boolean value indicating if the cube is in the list of cubes or not.</returns>
     498        public bool CubeKnown(List<List<int>> mCube, List<int> cube)
    568499        {
    569500            bool isEqual = true;
    570             for (int i = 0; i < mCube.Rows; i++)
     501            for (int i = 0; i < mCube.Count; i++)
    571502            {
    572503                isEqual = true;
    573                 for (int j = 0; j < cube.Count; j++)
    574                     if (mCube[i, j] != cube[j])
    575                         isEqual = false;
    576                 if (isEqual)
    577                     return true;
     504                if (mCube[i].Count == cube.Count)
     505                {
     506                    for (int j = 0; j < cube.Count; j++)
     507                        if (!mCube[i].Contains(cube[j]))
     508                            isEqual = false;
     509                    if (isEqual)
     510                        return true;
     511                }
    578512            }
    579513            return false;
     
    681615        /// Generates a random permutation of a finite set—in plain terms, for randomly shuffling the set.
    682616        /// </summary>
    683         /// <param name="cube">A List of values.</param>
     617        /// <param name="ilist">A List of values.</param>
    684618        public static void Shuffle<T>(List<int> ilist)
    685619        {
     
    696630        }
    697631
     632        /// <summary>
     633        /// Test if an n x m matrix contains n linearly independent vectors.
     634        /// </summary>
     635        /// <param name="A">n x m matrix.</param>
     636        /// <returns>A boolean value indicating if the matrix is regular or not.</returns>
    698637        public bool IsLinearIndependent(Matrix A)
    699638        {
    700             double[,] a = new double[A.Cols, A.Rows];
    701 
    702             for (int i = 0; i < A.Cols; i++)
    703                 for (int j = 0; j < A.Rows; j++)
    704                     a[i, j] = A[j, i];
    705 
    706639            double maxval;
    707640            int maxind;
    708641            double temp;
    709642            int Rang = 0;
    710             int zeilen = A.Cols;
    711             int spalten = A.Rows;
    712 
    713             for (int j = 0; j < spalten; j++)
     643            double[,] a = new double[A.Cols, A.Rows];
     644
     645            for (int i = 0; i < A.Cols; i++)
     646                for (int j = 0; j < A.Rows; j++)
     647                    a[i, j] = A[j, i];
     648
     649            for (int j = 0; j < A.Rows; j++)
    714650            {
    715651                // Find maximum
    716652                maxval = a[j, j];
    717653                maxind = j;
    718                 for (int k = j; k < zeilen; k++)
     654                for (int k = j; k < A.Cols; k++)
    719655                {
    720656                    if (a[k, j] > maxval)
     
    734670                    Rang++;
    735671                    // Swap_Rows(j, maxind)
    736                     for (int k = j; k < spalten; k++)
     672                    for (int k = j; k < A.Rows; k++)
    737673                    {
    738674                        temp = a[j, k];
     
    742678
    743679                    // Gauss elimination
    744                     for (int i = j + 1; i < zeilen; i++)
    745                         for (int k = j + 1; k < spalten; k++)
     680                    for (int i = j + 1; i < A.Cols; i++)
     681                        for (int k = j + 1; k < A.Rows; k++)
    746682                            a[i, k] = a[i, k] - (a[i, j] / a[j, j] * a[j, k]);
    747683                }
     
    754690
    755691        /// <summary>
    756         /// Preprocessing Phase of the cube attack. The main challenge is to find maxterms.
     692        /// Preprocessing Phase of the cube attack. Implementation of the algorithm RandomWalk to find maxterms.
    757693        /// </summary>
    758694        public void FindMaxtermsPhase()
     
    764700            List<int> chooseIndexI = new List<int>();
    765701            Matrix mSuperpoly = new Matrix(settings.SecretVar, settings.SecretVar + 1);
    766             Matrix mCube = new Matrix(settings.SecretVar, settings.SecretVar);
    767702            Matrix mCheckLinearity = new Matrix(0, settings.SecretVar);
    768703            List<int> superpoly = new List<int>();
     
    770705            Vector freeTerms = new Vector(settings.SecretVar);
    771706            List<List<int>> cubeIndex = new List<List<int>>();
     707            List<List<int>> mCube = new List<List<int>>();
    772708            int countRuns = 0;
    773709
     
    783719                    break;
    784720                countRuns++;
    785                
     721
    786722                cube = new List<int>();
    787723                superpoly.Clear();
     
    790726                numberOfVariables = rnd.Next(1, settings.MaxCube + 1);
    791727                Shuffle<int>(chooseIndexI);
    792                
     728
    793729                for (int i = 0; i < numberOfVariables; i++)
    794730                    cube.Add(chooseIndexI[i]);
     
    814750                    else
    815751                    {
    816                         if(cube.Count > 0) // brauche Funktion IsCubeKnown(cube, mCube), mCube muss n x n Matrix sein
    817                             //if (!IsCubeKnown(cube, mCube))
     752                        if (cube.Count > 0)
     753                        {
     754                            string bla = string.Empty;
     755                            for (int i = 0; i < cube.Count; i++)
     756                                bla += cube[i].ToString();
     757                            //CubeAttack_LogMessage("cube values: " + bla, NotificationLevel.Error);
     758                            if (!CubeKnown(mCube, cube))
    818759                            {
    819                                 //for (int i = 0; i < cube.Count; i++)
    820                                     //mCube[countMaxterms, i] = cube[i];
    821                                 superpoly = ComputePSI(cube);
     760                                mCube.Add(cube);
     761                                superpoly = ComputePSI(cube);
    822762                            }
    823                     }
    824                 }
    825                
    826                 if (!IsInMatrix(superpoly, mSuperpoly))
     763                        }
     764                    }
     765                }
     766
     767                if (!InMatrix(superpoly, mSuperpoly))
    827768                {
    828769                    List<int> superpolyWithoutConstant = new List<int>();
     
    842783                    }
    843784                    else
    844                         mCheckLinearity = mCheckLinearity.DeleteLastRow();     
     785                        mCheckLinearity = mCheckLinearity.DeleteLastRow();
    845786                }
    846787            }
     
    865806            }
    866807            else
    867                 CubeAttack_LogMessage(countMaxterms.ToString() + " maxterms have been found !", NotificationLevel.Info);
     808                CubeAttack_LogMessage("Only " + countMaxterms.ToString() + " maxterms have been found !", NotificationLevel.Info);
    868809        }
    869810
     
    876817        public void OnlinePhase(Matrix mSuperpoly, Vector b, List<List<int>> cubeIndex)
    877818        {
    878             int[] secretBits = new int[settings.SecretVar];
    879             secretBits[0] = 1; secretBits[1] = 1; //secretBits[2] = 0; secretBits[3] = false; secretBits[4] = true;
    880819            int[] secVarElement = new int[settings.SecretVar];
     820            secVarElement[0] = 1; secVarElement[1] = 1; //secVarElement[2] = 0; secVarElement[3] = 0; secVarElement[4] = 0;
    881821            int[] pubVarElement = new int[settings.PublicVar];
    882822           
    883823            for (int i = 0; i < settings.SecretVar; i++)
    884                 secVarElement[i] = secretBits[i];
    885             for (int i = 0; i < settings.SecretVar; i++)
    886824            {
    887825                for (int j = 0; j < settings.PublicVar; j++)
     
    894832                }
    895833            }
    896             OutputKB(mSuperpoly * b);
     834            OutputKey(mSuperpoly * b);
    897835            OnPropertyChanged("OutputKeyBits");
    898836        }
     
    944882                        }
    945883                        else
    946                             CubeAttack_LogMessage("The corresponding superpoly is not a linear polynomial !", NotificationLevel.Info);
     884                          CubeAttack_LogMessage("The corresponding superpoly is not a linear polynomial !", NotificationLevel.Info);
    947885                    }
    948886                    else
     
    1027965        #endregion
    1028966
     967
    1029968        #region INotifyPropertyChanged Members
    1030969
  • trunk/CrypPlugins/CubeAttack/CubeAttackSettings.cs

    r446 r472  
    125125            set
    126126            {
     127                if (value != this.publicVar) HasChanges = true;
    127128                publicVar = value;
    128129                OnPropertyChanged("PublicVar");
     
    146147            set
    147148            {
     149                if (value != this.secretVar) HasChanges = true;
    148150                secretVar = value;
    149151                OnPropertyChanged("SecretVar");
     
    167169            set
    168170            {
     171                if (value != this.maxcube) HasChanges = true;
    169172                maxcube = value;
    170173                OnPropertyChanged("MaxCube");
     
    188191            set
    189192            {
     193                if (value != this.linTest) HasChanges = true;
    190194                linTest = value;
    191195                OnPropertyChanged("LinTest");
     
    213217            set
    214218            {
     219                if (value != this.setPublicBits) HasChanges = true;
    215220                setPublicBits = value;
    216221                OnPropertyChanged("SetPublicBits");
Note: See TracChangeset for help on using the changeset viewer.