Optimization Of Matsui Algorithm Based On CUDA

Cryptanalysis is a subject that studies the use of special means to decrypt unknown crypto-graphic information.Among them,differential analysis is a way by selecting plaintext.Since 1995,Matsui algorithm,invented by Matsui,a Japanese Cryptologist,has been the main method of differential analysis automation for a long time.Its main contribution is to break through 16 rounds of DES encryption algorithm.Compared with the current mainstream search methods such as MILP(mixed integer linear programming),which rely on mathe-matical analysis tools,Matsui algorithm pays more attention to the structural characteristics of the encryption algorithm itself.Because Matsui algorithm is closer to the encryption algorithm itself,its accuracy will be higher than MILP and other tools.Matsui algorithm estimates the approximate probabil-ity of each round in advance as the empirical value as the branch boundary condition,and then deduces the maximum difference probability of the last round from the calculated ac-tual value to update the empirical value.In other words,the actual difference characteristic probability of the nth round is based on the actual maximum difference characteristic proba-bility of the first n-1 round.The updating of empirical value is used to improve the condition of branch definition,so as to reduce the number of exhaustive branches.MILP models the linear and nonlinear parts of the encryption algorithm,and selects the branches according to the constraints of the linear programming model.The biggest difference between the two is the dynamic and static shear support.Dynamic pruning can accelerate the search on the premise of ensuring the correctness.Static requires a balance between accuracy and speed.This thesis will optimize the Matsui algorithm as follows:(1)Because the combination of Matsui algorithm and cryptographic algorithm is too close.Compared with MILP,the algorithm construction for different structures is more complex.For example,Matsui algorithm is very suitable for SPN structures with S-boxes,but it is not friendly for other nonlinear structures.Therefore,we extract the core part of the algo-rithm like MILP,and separate the framework and the core to apply to most cryptographic algorithms.(2)This thesis parallelizes Matsui algorithm and combines it with GPU to ensure the ef-ficiency of computation.In order to adapt to different algorithmic frameworks,parallel methods are mainly divided into global parallel optimization and local parallel optimiza-tion.Because of the limitation of CUDA,it can not achieve the best optimization.(3)In this thesis,the branch definition conditions of parallel Matsui algorithm are studied to ensure that the dynamic pruning of the algorithm can be kept to the maximum under the con-dition of parallel restriction,and a certain static pruning is added to improve the calculation speed.In addition,several factors that affect the computing speed of the algorithm are an-alyzed,and the hybrid computing is used to improve the computing speed from small-scale data to large-scale data.(4)Replacing the first input of PRESENT,taking the output of S-box as the input,the cal-culation speed can be greatly improved while ensuring the accuracy.Therefore,the general work of this thesis includes:(1)The Matsui algorithm is analyzed and studied.(2)Five algorithm models and their theories(3)Algorithm implementation and experiment based on PRESENTWe will introduce the specific content in this article,mainly focusing on the optimization of Matsui algorithm.The PRESENT optimization model includes the following features:1)dy is used as input;2)local parallel model using general algorithm;3)optimal pruning conditions with accuracy guaranteed;4)hybrid computing is used.The final result is that the calculation speed of most rounds has been greatly improved.Among them,parallelization and using dy as input have the greatest impact on speed.Finally,we look forward to the future.Out of strictness,we should do more experiments.Each model is applied to different encryption algorithms for comparative experiments.And it can be made into a tool similar to MILP,which is more convenient for password analysts to use.