Abstract: Based on quicksort theory, this paper presents a basic plaintext pair sieve algorithm and an improved algorithmone, and the computational complexity of improved algorithm is O(nlogn), which is less than O(n2) of the method by checking each pairs. It analyzes the computational complexity of plaintext pair sieve in impossible differential attacks on ARIA etc with the new algorithm, and proves that the computational complexity is higher remarkably than that in the key solving process for the one impossible differential attack on ARIA presented in ICISA 2008.

Key words: cryptology, cryptanalysis, impossible differential attack, plaintext pair sieve, computational complexity, ARIA algorithm

摘要： 基于快速排序原理，提出用于筛选明文对的基本算法和改进算法，改进算法的计算复杂性可以将由直接检测方法的O(n2)降为O(nlogn)。基于上述结果以改进算法分析对ARIA等分组密码算法的几个不可能攻击的计算复杂性，证明ICISA2008上发表的某个针对对ARIA的不可能攻击的数据筛选过程的计算复杂性远高于密钥求解过程的计算复杂性。

关键词: 密码学, 密码分析, 不可能差分攻击, 明文对筛选, 计算复杂性, ARIA算法

CLC Number: 

• TN918.1