Кіріспе

Сызықтық криптоанализде қолданылатын принцип. Криптоанализде үйілу леммасы – блок шифрлерінің әрекетін жақындастыру үшін сызықтық криптоанализде қолданылатын принцип. Мицуру Мацуи (1993) оны сызықтық криптоанализ үшін талдау құралы ретінде ұсынды. Лемма тәуелсіз екілік кездейсоқ айнымалылардың сызықтық Буль функциясының (XOR өрнегі) бұрылысының (күтілетін мәннің 1/2-ден ауытқуы) кіріс бұрылыстарының көбейтіндісімен байланысты екенін көрсетеді:

немесе

мұндағы – бұрылыс (нөлге қарай), ал – тепе-теңдік. Керісінше, егер лемма орындалмаса, кіріс айнымалылары тәуелді болады.

Интерпретация

Лемма тәуелсіз екілік айнымалыларды XOR операциясы арқылы қосу әрқашан қисайдылықты азайтады (немесе кем дегенде оны арттырмайды); сонымен қатар, шығыс қисайдылықсыз болады, егер және тек қана кем дегенде бір қисайдылықсыз кіріс айнымалысы болса. Екі айнымалы үшін шаманың және арасындағы корреляцияның өлшемі екеніне назар аударыңыз, ол тең; оны арасындағы корреляция ретінде түсіндіруге болады.

Практика

Іс жүзінде, X-тер блок шифрларының S-қораптарына (ауыстыру компоненттері) жуықтап келген шамалар. Әдетте, X мәндері S-қораптарына кіріс ретінде беріледі, ал Y мәндері – сәйкес шығыстар болып табылады. Криптоаналитик S-қораптарын қарастырып, ғана ықтималдық бұрмалауларын анықтай алады. Көкейкесті мәселе – нөл немесе бір ықтималдығына ие кіріс және шығыс мәндерінің комбинацияларын табу. Жуықтап келген шама нөлге немесе бірге неғұрлым жақын болса, сызықтық криптоанализдегі оның тиімділігі соғұрлым жоғары. Дегенмен, іс жүзінде бинарлық айнымалылар, үймелеу леммасының негіздемесіндегідей, тәуелсіз болмайды. Осы мәселені лемманы қолданғанда есте ұстау қажет; ол автоматты криптоанализ формуласы емес.