Кіріспе

Сызықтық алгебраға негізделген алмастыру шифры

Классикалық криптографияда Хилл шифры — сызықтық алгебраға негізделген полиграфиялық алмастыру шифры. Лестер С. Хилл 1929 жылы ойлап тапқан бұл шифр, бір уақытта үштен астам символдармен жұмыс істеуді практикалық (бірақ қиын) еткен алғашқы полиграфиялық шифр болды. Келесі талқылау матрицалар туралы қарапайым білімді меңгергендерге арналған.

Қауіпсіздік

Hill шифрі толық сызықтық болғандықтан, белгілі ашық мәтіндік шабуылға осал. Қарсылас ашық мәтін/шифрмәтін таңбалар жұбын ұстап алып, сызықтық жүйені құра алады, оны (көбінесе) оңай шеше алады; егер жүйе анықталмаса, бірнеше ашық мәтін/шифрмәтін жұбын қосу жеткілікті. Бұл шешімді стандартты сызықтық алгебра алгоритмдерімен есептеуге өте аз уақыт кетеді. Матрицалық көбейтудің өзі қауіпсіз шифрді қамтамасыз етпесе де, ол басқа сызықтық емес операциялармен біріктірілгенде пайдалы болады, себебі матрицалық көбейту диффузияны қамтамасыз ете алады. Мысалы, тиісті таңдалған матрица матрицалық көбейту алдындағы шағын айырмашылықтардың, көбейтуден кейін үлкен айырмашылықтарға әкелетініне кепілдік бере алады. Шындығында, кейбір қазіргі заманғы шифрлер диффузияны қамтамасыз ету үшін матрицалық көбейту қадамын қолданады. Мысалы, AES-тегі MixColumns қадамы – матрицалық көбейту. Twofish-тегі g функциясы – мұқият таңдалған матрицалық көбейтумен (MDS) сызықтық емес S-қораптарының комбинациясы.

Кілттің кеңістігінің өлшемі

Кілттер кеңістігі – барлық мүмкін кілттердің жиынтығы. Кілт кеңістігінің мөлшері – мүмкін кілттердің саны. Биттермен өлшенетін тиімді кілт мөлшері – кілт кеңістігінің екілік логарифмі. n × n өлшемді матрицалар бар. Осылайша, немесе шамамен, n × n матрицаларын пайдалана отырып Хилл шифрінің кілт мөлшеріне жоғарғы шек қойылады. Бұл тек жоғарғы шек, себебі әрбір матрица инвертирлене бермейді, демек кілт ретінде қолданыла алмайды. Инвертирленетін матрицалардың санын Қытайлық қалдық теоремасы арқылы есептеуге болады. Яғни, матрица 26 модуль бойынша инвертирленеді, егер және тек қана ол 2 және 13 модульдері бойынша да инвертирленетін болса. 2 модуль бойынша инвертирленетін n × n матрицалардың саны жалпы сызықтық топ GL(n,Z2) ретіне тең. Ол тең, 13 модуль бойынша инвертирленетін матрицалардың саны (яғни GL(n,Z13) реті) . 26 модуль бойынша инвертирленетін матрицалардың саны – осы екі санның көбейтіндісі. Сонымен қатар, кілт матрицасында тым көп нөлдерден аулақ болу қажет, себебі олар диффузияны төмендетіп жібереді. Нәтижесінде, қарапайым Хилл шифрінің тиімді кілт кеңістігі шамамен . 5 × 5 Хилл шифрі үшін бұл шамамен 114 бит. Әрине, кілт іздеу – ең тиімді шабуыл емес.

Механикалық іске асыру

Бір мезгілде 2 символмен жұмыс істегенде, Хилл шифры Playfair немесе бифид шифрына қарағанда ешқандай артықшылықты ұсынбайды, тіпті олардан нашаррақ және қалам мен қағазбен жұмыс істеуге сәл қиын. Өлшемдері артқан сайын, шифрды қолмен пайдалану адам үшін мүмкін емес болып кетеді. 6 өлшемді Хилл шифры механикалық түрде іске асырылды. Хилл мен оның серігі осы құрылғыға патент алды, ол 26 модулі бойынша 6 × 6 матрицалық көбейтуді тізбектер мен тізбектер жүйесі арқылы жүзеге асырды. Айыныштысы, берілістердің орналасуы (яғни кілт) әрбір машина үшін бекітілгендіктен, қауіпсіздік үшін үш рет шифрлау ұсынылды: құпия сызықтық емес қадам, одан кейін машинадан кең таралған қадам, содан кейін үшінші құпия сызықтық емес қадам. (Кейінірек пайда болған Even-Mansour шифры да кілті жоқ диффузиялық ортаңғы қадамды қолданады). Мұндай комбинация 1929 жылға өте қуатты болды және Хиллдің ортадағы шабуыл, сондай-ақ шатасу және диффузия ұғымдарын түсінгенін көрсетеді. Алайда, оның машинасы сатылмады.