Кіріспе
Криптоанализ түрі Криптографияда сызықтық криптоанализ – шифрдың жұмысына жуықтап келген сызықтық теңдеулерді табуға негізделген криптоанализдің жалпы түрі. Бұл шабуыл блок шифрлары мен ағын шифрларына қатысты жасалған. Сызықтық криптоанализ – блок шифрларына ең көп қолданылатын екі шабуылдың бірі, екіншісі – дифференциалдық криптоанализ. Осы жаңалықты Мицуру Мацуи ашқан, ол алғаш рет FEAL шифріне бұл техниканы қолданды (Мацуи және Ямагиши, 1992). Содан кейін Мацуи Деректерді шифрлеу стандартына (DES) шабуыл жасады, нәтижесінде ашық қауымдастықта хабарланған шифрдің алғашқы тәжірибелік криптоанализі жасалды (Мацуи, 1993; 1994). DES-ке жасалған шабуыл көбінесе практикалық емес, себебі 247 белгілі ашық мәтін қажет. Шабуылды жетілдіру үшін түрлі ұсыныстар жасалды, оның ішінде бірнеше сызықтық жуықтамаларды пайдалану немесе сызықтық емес өрнектерді қосу, бұл жалпыланған бөлік криптоанализіне алып келді. Жаңа шифрлау жобаларында сызықтық криптоанализге қарсы қауіпсіздік көрсету қажет.
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis. The discovery is attributed to Mitsuru Matsui, who first applied the technique to the FEAL cipher (Matsui and Yamagishi, 1992). Subsequently, Matsui published an attack on the Data Encryption Standard (DES), eventually leading to the first experimental cryptanalysis of the cipher reported in the open community (Matsui, 1993; 1994). The attack on DES is not generally practical, requiring 247 known plaintexts. A variety of refinements to the attack have been suggested, including using multiple linear approximations or incorporating non linear expressions, leading to a generalized partitioning cryptanalysis. Evidence of security against linear cryptanalysis is usually expected of new cipher designs.
Шолу
Сызықтық криптоанализдің екі бөлімі бар. Біріншісі – жоғары ықтималдыққа ие, ашық мәтін, шифрланған мәтін және кілт биттерін байланыстыратын сызықтық теңдеулерді құру; яғни, олардың орындалу ықтималдығы (олардың барлық мүмкін мәндері бойынша) 0 немесе 1-ге ең жақын болуы керек. Екіншісі – осы сызықтық теңдеулерді белгілі ашық мәтін-шифрланған мәтін жұптарымен бірге қолданып кілт биттерін анықтау.
Сызықтық теңдеулерді құру
Сызықтық криптоанализ мақсатында сызықтық теңдеу эксклюзивті немесе (XOR) операциясымен біріктірілген екілік айнымалылардан тұратын екі өрнектің теңдігін көрсетеді. Мысалы, гипотетикалық шифрдан алынған келесі теңдеу, блок шифрындағыдай, жай мәтіннің бірінші және үшінші биттерінің XOR қосындысының шифрмәтіннің бірінші битіне кілттің екінші битімен тең екенін көрсетеді:
Идеалдық шифрда жай мәтін, шифрмәтін және кілт биттеріне қатысты кез келген сызықтық теңдеу 1/2 ықтималдығымен орындалады. Сызықтық криптоанализде қарастырылатын теңдеулердің ықтималдығы әртүрлі болғандықтан, оларды сызықтық жуықтамалар деп атау дұрыс. Жуықтамаларды құру процедурасы әр шифр үшін өзгеше болады. Блок шифрдың ең қарапайым түрі – алмастыру-пермутация желісінде талдау көбінесе шифрдың сызықтық емес бөлігі болып табылатын S-қораптарына бағытталған (яғни S-қораптың операциясын сызықтық теңдеумен көрсету мүмкін емес). S-қораптары жеткілікті кішкентай болса, S-қораптың кіріс және шығыс биттеріне қатысты барлық мүмкін сызықтық теңдеулерді санап, олардың бұрмалануын есептеп, ең жақсыларын таңдауға болады. Содан кейін S-қораптары үшін алынған сызықтық жуықтамалар пермутация және кілт араластыру сияқты шифрдың басқа операцияларымен біріктіріліп, бүкіл шифр үшін сызықтық жуықтамалар құрылады. Бұл біріктіру кезеңінде жинақтау леммасы пайдалы құрал болып табылады. Сондай-ақ сызықтық жуықтамаларды итеративті түрде жақсарту тәсілдері бар (Matsui 1994).