|
With the MD4, MD5, SHA-1 is compromised and SHA-collection plan to carry out the attack of the hash function and design is a hot topic in recent years, research into cryptography. Wang Xiaoyun inspired by Dobbertin, differential attack proposed algorithm can effectively attack MDx series HASH algorithm, and received wide attention. Wang Xiaoyun, however, did not give the idea of ??the algorithm, and Wang Xiaoyun differential collision attack can be found in the MD5 message collision, but the the collision news for her to find a set of random bits characters, collision message semantics. Based on the results of Wang Xiaoyun, 2007 Marc Stevens and other select prefix collision attack and apply it to the structure of the pseudo-CA certificate. Marc Stevens makes use of 215 CELL processor spent 20 days to find the needed collision in 2009, Marc Stevens on the algorithm has been improved, saving time, has greatly increased the length of the message. In this paper, a detailed study the select prefix collision attack on a number of key technologies, the main results are as follows: the first part of the study \To control the spread of the differential principle, \The second part to make good use of differential design adaptive the MD5 differential path search algorithm. First conducted an in-depth analysis of the cyclic shift, given the results of the four shift and the corresponding probability, in particular compare the size of the four probability is 1 when the differential weight. Boolean function 27 differential output and input variables, the binary nature of the diffusion and tunneling principle. Finally, adaptive the MD5 differential path search algorithm and some experimental results. The third part with Pollard's rho algorithm, designed serial delta b (0, △ C △ C) - message search algorithm, parallel (delta b, △ C △ C) - Message search algorithms and to search multiple (0 , δb, δc, δc) - news parallel search algorithm and analyze the correctness and complexity of the three algorithms. Design serial delta b (0, △ C, △ C) - when the message search algorithm, combining Floyd loop search algorithm Thought, reduce the storage space required by the algorithm, the complexity is about. With M-processor parallel search algorithm to search for a (0, δb, δc, δc) - message about its complexity, and M-processor search alone (0, delta b, △ C △ C) - on the news its complexity is about the πN M; parallel search algorithm search n (0, δb, δc, δc) - a message on the average complexity about, which is the size of the search space. The results show that while searching delta b (0, △ C △ C) - the number of news is more, the complexity of the algorithm is relatively more stable, average to each delta b (0, △ C △ C) - news on the complexity of is lower. Finally, the three algorithms implemented in the CPU, GPU (Graphic Processing Unit) and FPGA platform, to obtain a test result.
|