Виженер шифры

Виженер шифры (фр. Chiffre de Vigenère) — мәтінді сөздер арқылы берілген кілт көмегімен шифрлау әдісі. Бұл әдіс көпалфавиттік алмасу тәсілінің ең қарапайым түрі болып табылады. Виженер шифры бірнеше рет жаңартылған. Бірінші рет бұл криптография жүйесін 1553 жылы Джовани Баттиста Беллазо (итал. Giovan Battista Bellaso) La cifra del. Sig. Giovan Battista Bellasо кітабына енгізсе де, XIX ғасырда бұл әдіс француз дипломаты Блез Виженердің атына жазылған. Криптоанализдің кейбір түрлеріне ақиық болса да,бұл әдіс түсінуге әрі іске асыруға өте жеңіл.

Тарихы

1466 жылы танымал сәулетші философ Леон Альберти Рим Папасының кеңсесінде шифрлар туралы трактатын таныстырады. Трактатта әртүрлі шифрлау әдістері, сонымен қатар кейбір көмекші мәтіндегі ашық мәтіннің бүркеу жолдары көрсетілген. Жұмыс соңы “хандарға ғана лайық шифр” деген сөздермен аяқталған. Бұл шифрлық диск түрінде жүзеге асырылған көпалфавиттік шифр. Шифрдың мағынасы кілтке сәйкес бірнеше алмасу операциясында жатыр. Осыдан кейін, Альберти кері шифрлауға арналған код ойлап табады. Ертерек ойлап табылса да, бұл кодты Еуропа елдері 400 жыл өткеннен кейін ғана қолданысқа енгізе бастады.

1518 жылы Германияда пайда болған криптография кітабы арқасында шифрлау саласының дамуына алғашқы қадамдар жасалады. Вюрцбург шіркеуінде жұмыс істейтін Аббат Иоганнес Тритемий, бірсаран шифрларға сипаттама берілген “Полиграфия” кітабын жазады. Осы шифрлардың біреуінде Тритемий кестесімен қатар (бастапқы Виженер кестесі) көпалфавиттік орын алмасу идеясы да жүзеге асырылған. Шифрлау жүйесі осындай ретте орын алған: ашық мәтіннің бірінші әрібі бірінші жол бойынша шифланады, екінші әрібі екінші және т.б. Соңғы жол қолданылғаннан кейін, шифрлау барысы қайтадан бірінші жолға өтеді. Тритемий шифрында кілт қолданылмайды, сондықтан шифрлау әдісінің өзі құпия болып саналады.

Тритемий ұсынған әдістің келесі даму қадамы итальянец Джовани Белазомен жасалған еді. 1533 жылы оның "Шифр синьора Белазо" атты кітапшасы жарық көреді. Бұл шифрда кілт ретінде сөз немесе қанатты сөйлемдер қолданылған. Құпиясөз кейбір кезде ашық мәтіннің астына да жазылады. Ашық мәтіннің астында тұрған кілт сөз әрібі, Тритемий кестесіндегі ретке көрсетеді. Сол рет бойынша әріпті алмастыру қажет.
Джованни Батиста Порта Тритемий мен Белазо идеясын одан әрі дамытқан Белазоның жерлесі. Ол бірінші жолы алфавиттік ретпен орналасқан Тритемий кестесінен бас тартып, оны шифрдың кілті болатын кез-келген әріп ретімен алмастырды. Ал кестенің басқа жолдары циклді түрде қозғалып отырады. Порта биграммды шифрды, сонымен қатар биграммдық алмасуды жүзеге асыратны механикалық диск сипаттамасын өзінің "О тайной переписке" кітабында жария еткен.

Дж. Карданоның "О разных вещах" қосымшасымен бірге "О тонкостях" кітабы Италияда XVI ғасырдың жартысында пайда болады. Бұл кітап мазмұнында криптографияның жаңа идеясы өз орнын тапқан. Ашық мәтіннің бөліктері кілт ретінде қолданылған (өзіндік кілт идеясы). Бұл әдіс тарихта "Кардано торы" деп аталынған. Франция елшісі Блез де Виженер Тритемий, Белазо, Кардано, Порта, Альберти жұмыстарымен танысқаннан кейін, өзі де криптография саласына қызыға бастады. Криптографияның іргетасы 1585 жылы шыққан Виженердің "Трактат о шифрах" кітабында мазмұндалды. Ол өзінің еңбегінде бір заңдылықты байқайды: "Әлемдегі бүкіл заттар шифр көрінісі. Бүкіл табиғат шифр мен құпия хаттардан тұрады". Бұл ой ықтималдықтар теориясының авторы Блез Паскальмен қайталанса, қазіргі уақытта оны Норберт Винер кибернетика ғалымы да қолдайды.

Негізінен Виженер жұмысы 3 ғалымның Тритемий, Беллазо, Порта еңбектерінің қосындысынан тұрса да, "Виженер шифрі" деген атау "Тритемий кестесі" және т.б. атаулардың орнын басқан. Осы мәселеге орай Дэвид Кан «Взломщики кодов» кітабында өзінің наразылығын білдірді: "бұл шифрды ойлап табуға бірнеше авторлар қатысқанымен, көбісі Виженердің бұл әдіске мүлдем қатысы жоқ екендігін елемеген". Виженер шифры қолмен оңай бұзыла қоймайтындығымен танымал. Атақты жазушы, математик Чарльз Лютвидж Доджсон (Льюис Кэрролл) өзінің «Алфавитный шифр» мақаласында Виженер шифрын бұзылуға келмейтін шифрлардың бірі ретінде жариялаған. 1917 жылы Scientific American журналы да Виженер шифрының төзімділігі жайлы сөз қозғайды. Дегенмен бұл қалыптасып кеткен ой өз қарсылығын табады. Шифрды XIX ғасырда Касиски толық бұзады, бірақ тәжірбиелі криптоаналитиктер бұл критограмманы бұзу жолын XVI ғасырдың басында тапқандығы одан кейін айқындалады. Виженер шифры жолдар және шифрлық дисктер арқылы жүзеге асатындықтан өте қарапайым болып келеді. Мысалға, «конфедераттар» Азаматтық соғыс барасында мыстан жасалған шифрлық дискті қолданған. Конфедерация жолдауы құпиялылықтан алшақ болғандықтан, олардың қарсыластары жүйелі түрде шифрды бұзып отырған. Соғыс уақытында Конфедерация сөз тіркестерінен тұратын 3 кілтке сүйенген: «Manchester Bluff», «Complete Victory» және-соғыс соңына жетейін дегендіктен-«Come Retribution».

Қазіргі күнде Виженер шифры төзімділікті қажет етпейтін бағдарламаларда қолданылады. Мысалға, программа-архиватор "ARJ" . Гилберт Вернам шифрдың төзімділігін арттыру үшін оны дамытып көрді. Шифр 1918 жылы Вернам-Виженер шифры деген атау алады, бірақ жақсартуларға қарамастан бұл әдіс криптоанализге шыдамдылық танытпады. Бірақ соңғы жұмыстары нәтиже беріп ол бұзуға төтеп бере алатын Вернам шифрына қол жеткізеді.

Сипаттамасы

Шифрлау және дешифрлауға арналған Виженер шаршысы, Виженер кестесі (tabula recta). Цезарь шифрында алфавиттің әрбір әрібі бір позициялық орынға жылжиды. Мысалға, Цезарь шифрында ауысым 3-ке тең болса A=D, B=E және т.б. Виженер шифры әртүрлі ауысымды Цезарь шифрынан тұрады. Шифрлау үшін Виженер шаршысын (кестесін) қолдануға болады. Латын алфавитіне сүйене отырып жасалған Виженер кестесі 26 таңбадан тұрады, сонымен қатар әрбір жол бірнеше позицияға жылжыған. Яғни бізде 26 әртүрлі Цезарь шифры пайда болады. Кілт сөздің таңбасына орай әрбір шифрлау кезеңіне әртүрлі алфавит қолданылады. Мысалға, ашық мәтін келесідей деп алайық: ATTACKATDAWN Хат жіберіп жатқан адам кілт сөздің (LEMON) ұзындығы мәтін ұзындығына тең болғанша циклді түрде қайталап жазады LEMONLEMONLE Ашық мәтіннің бірінші таңбасы A-L кілтіне сәйкес келеді. Жабық мәтіннің бірінші таңбасы L, Виженер кестесіндегі L жолы мен A қатарының қиылысуында жатыр. Тура осындай жүйеде біз екінші әрібі, Е жолы мен Т қатарының қиылысуында жатыр. Ашық мәтіннің келесі бөлігі осылай шифрланады: Ашық мәтін: ATTACKATDAWN Кілт: LEMONLEMONLE Дешифрлау процесі келесідей жүреді: Кілт таңбаларына келетін жолды Виженер кестесінен табамыз. Жол бойынан жабық мәтінге тән бірінші таңбаны іздейміз. Бірінші таңба тұрған қатар, ашық мәтіннің бірінші әрібіне сәйкес келеді. Келесі әріптерді дешифрлау дәл осындай әдіспен жүреді. Егерде n – алфавиттегі әріптер саны; mj-ашық мәтін әріптері; kj-кілт әріптері болса, Виженер әдісін келесідей формуламен беруге болса: cj=mj+kj (mod n) Дешифрлау: mj=cj-kj (mod n) Компьютерде бұндай операция ASCII кодтарын қосу операциясына сәйкес келеді. Дегенмен де, егер Виженер кестесі циклдік араласудан ғана тұрмаса, оның беріктігі артатындығына нық сенімдімін. Әріп қатар мен жолда бір рет қана кездесетіндей кесте жасау өте қиын. Оны тек электрондық компьютерлік құрылғыларда ғана байқап көрген жоқ. Күнделікті өмірде қолдануда Виженер кестесі ешқандай қиындық көрсетпейді. Ол тек шифрлау мен дешифрлауды жеңілдетеді.

Криптоанализ

Виженер шифры мәтіндегі әріптер жиілігі мәселесін шешкенімен, кейбір дербес жағдайларда таңбалар қайталанады. Кілттің жиі қайталанатындығы осы шифрдың басты кемшілігі болып табылды. Сондықтан шифрдың қарапайым крпитоанализі 2 кезеңнен тұрады:

1. Кілт ұзындығын анықтау. Шифрланған мәтіннің әрбір екінші әрібін алып текст құраймыз, сосын әрбір үшінші әрібін және т.б. Текст біртектіліктен айырмашылығы көп болса ғана табылған кілттің ұзындығы жайлы айтуға болады.
2. Криптоанализ. Бөлек-бөлек болғанда тез бұзылатын шифр Цезарінің жиынтығы.

Фридман мен Касиски сынақтары бізге кілт ұзындығын табуға көмектесе алады.

Касиски әдісі

Чарльз Беббидж 1854 жылы Виженер шифрына қарсы шабуылға арналған ең бірінші алгоритм ойлап табушылардың бірі еді. Алгоритмді жобалауға ынталандырған Твейтспен алмасқан хаты болатын. Твейтс жаңа шифр ойлап тапқандығы жайлы «Journal of the Society of the Arts» журналына жібереді. Беббидж Твейтске оның шифры Виженер шифрының түрленген нұсқасы екендігін айтады. Беббидж Твейтстің шифрын дешифрлау арқылы Альфред Теннисонның поэмасы «The Vision of Sin» алады. Сонымен қатар, кілт ретінде оның әйелінің аты Emily алынғанын да анықтайды. Бірақ ол өзінің ашылуын жарияламайды. Сондықтан оның атауы1836 жылы сол алгоритмді қайта ашқан Пруссия армиясының офицері Фридрих Вильгельм Касискиге берілді. Тек 20 ғасырда ғана, ғалымдар Беббиджтің жазбаларын тексеру арқылы бұл алгоритмнің бірінші ғалымы жайлы түсінік пайда бола бастады. Бұл әдіс идеясы периодтық кілттер ағысына негізделген. Сонымен қатар, табиғи тілде жиі кездесетін хат комбинациялары да бар:биграммалар және тригаммалар. Бүкіл жағдайды ескере отырып, біз қайталанып кездесетін шифрмәтіндегі таңбалар-ашық мәтіндегі танымал биграмм мен триграмм іздері деген нұсқа пайда болады. Қайталанатын сөздер арасындағы арақашықтық лозунг ұзындығына тең болу керек. Осыған орай, осындай арақашықтықтардың ең үлкен ортақ бөлгішін таба отырып, біз кілттің ұзындығы жайлы мүмкін гипотеза аламыз. Мысал ретінде келесі криптограмманы қарап көрейік:

UTPDHUG NYH USVKCG MVCE FXL KQIB. WX RKU GI TZN, RLS BHZLXMSNP KDKS; СЕВ IH HKEWIBA, YYM SRB PER SBS, JV UPL О UVADGR HRRWXF. JV ZTVOOV УН ZCQU У UKWGEB, PL UQFB Р FOUKCG, TBF RQ VHCF R KPG, 0U КЕТ ZCQU MAW QKKW ZGSY, ЕР PGM QKETK UQEB DER EZRN, MCYE, MG UCTESVA, WP KFT ZCQU MAW KOIJS, LCOV NTHDNV JPNUJVB IH GGV RWX ONKCGTHKFL XG VKD, ZJM VG CCI MVGD JPNUJ, RLS EWVKJT ASGUCS MVGD; DDK VG NYH PWUV CCHIIY RD DBQN RWTH PFRWBBI VTTK VCGNTGSF FL IAWU XJDUS, HFP VHSF, RR LAWEY QDFS RVMEES FZB СНН JRTT MVGZP UBZN FD ATIIYRTK WP КЕТ HIVJCI; TBF BLDPWPX RWTH ULAW TG VYCHX KQLJS US DCGCW OPPUPR, VG KFDNUJK GI JIKKC PL KGCJ lAOV KFTR GJFSAW KTZLZES WG RWXWT VWTL WP XPXGG, CJ EPOS VYC BTZCUW XG ZGJQ PMHTRAIBJG WMGEG. JZQ DPB JVYGM ZCLEWXR:CEB lAOV NYH JIKKC TGCWXE UHE JZK. WX VCULD YTTKETK WPKCGVCWIQT PWVY QEBFKKQ, QNH NZTTWIREL IAS VERPE ODJRXGSPTC EKWPTGEES, GMCG TTVVPLTEEJ; YCW WV NYH TZYRWH LOKU MU AWO, KEPM VG BLTP VQN RD DSGG AWKWUKKPL KGCJ, XY GPP KPG ONZTT ICUJCHLSE KET DBQHJTWUG. DYN MVCK ZT MEWCW HTWE ED JL, GPU YAE CH LQ! PGR UE, YH MWPP RXE CDJCGOSE, XMS UZGJQJL, SXVPN HBG!

WX биграммасы қайталануы арасындағы арақашықтықты есептеп көрейік. Кейбір арақашықтықтар 9,21,66 және 30 тең. Басқа бөліністер кездейсоқ шықса, басқалары кілт ұзындығы жайлы ақпаратты сақтайды. Жұп-жұп бойынша осы сандардың ең үлкен ортақ бөлгішін табайық: ЕҮОБ (30,66) = 6, ЕҮОБ (3,9) = ЕҮОБ (9,66) = ЕҮОБ (9,30) = ЕҮОБ (21,66) = 3. Кілт ұзындығы 3 әріптен тұратындығы мүмкін емес. 9 бен 21 арқашықтық кездейсоқ түсті деп есептеп, кілт ұзындығын 6 ретінде аламыз.

Фридман сынағы

Фридман сынағы (кей-кезде каппа-тест деп аталады) Вильям Фридманмен 1920 жылы ойлап табылды. Фридман шифрды бұзу үшін қайталанатын таңбалар жиілігін есептейтін ұқсастық индексін қолданған. 2 кездейсоқ таңдалған мәтін таңбаларының КР ықтималдығын (ағылшын әрібі үшін 0,067-га тең), сонымен қатар 2 кездейсоқ таңдалған мәтін таңбаларының КТ ықтималдығын біле отырып, кілттің ұзындығына баға беруге болады: Ұқсастық ықтималдықтар тәсіліне жүргізілген бақылаудан шығады: Бұл жерде С-алфавит көлемі (ағылшын тілінде 26 таңба бар), N-мәтін ұзындығы, nj-бақылаудағы шифрланған мәтін таңбаларының қайталану жиілігі. Дегенмен, бұл тек жуық мән, бұл мәннің дәлдігі мәтін көлемі ұлғайған сайын өсе береді. Практикада бұл тәсіл әртүрлі кілттерді анықтай жүріп, соңғы, нақты мәнге келуге көмектеседі.

Жиілік анализі

Kілт ұзындығы анықталғаннан кейін, шифрланған мәтінді әрқайсысы бір кілттің мәніне келетін бірнеше бағанаға жазуға болады.Әрбір қатар Цезарь шифры арқылы кодталған жабық мәтіннен тұрады. Осы бағанада қолданылған Цезарьдің кілті Виженер шифры кілтінің тек қана бір таңбасы болып табылады. Цезарь шифрын бұзу тәсіліне ұқсас әдістер арқылы шифрланған текстті ашық мәтінге айналдыруға болады. Касискидің жақсартылған нұсқасы Кирхгоф әдісі аталып кеткен. Бұл тәсілдің идеясы таңбалардың бағаналарда кездесу жиілігі мен жабық мәтіндегі таңбалардың кездесу жиілігін салыстыру арқылы сол бағанаға сай кілт таңбасын табуда жатыр. Кілттің бүкіл таңбалары анықталғаннан кейін, криптоаналитиктер ашық мәтінді тез дешифрлай алады. Кирхгофтың тәсілі Виженер кестесі шифрланбай, алфавит ретімен болғанда ғана жүзеге асады. Дегенмен де, Касиски нұсқасы бұл жағдай үшін кілттің ұзындығын таба алуы мүмкін.

Нұсқалар

Көпалфавиттік жүйенің іргетасы ретінде алынатын Виженер кестесі секілді қарапайым шаршылар әрине көп. Ең танымал кестелердің бірі Бьюфорд кестесі болып табылады. Бұл кестенің жолдары Виженер кестесінің жүйелілігі бойынша, бірақ керісінше ретпен орналасқан. Бұл шифр желдің жылдамдығын өлшейтін құралды ойлап тапқан Френсис Бьюфорттың құрметіне орай аталған. Виженер жүйесінің бірінші жолы мен бірінші бағанасы, сәйкесінше кестенің қатары мен колоннасына көрсетсе, Бьюфорт шаршысында бұл мақсатта бірінші жол мен соңғы бағана жұмыс істейді. Виженердің Running key (істегі кілт) нұсқасы бұрында бұзылуға келмейтін болған. Бұл версияда кілт негізгі мәтіннің ұзындығына тең блок мәтінге қолданылады. Кілт мәтіннің ұзындығына тең болғандықтан, Фридман мен Касискидің тәсілдерін біз бұл жерде қолдана алмаймыз(себебі кілт қайталанбайды). 1920 жылы Фридман бірінші болып бұл варианттың кемшілігін байқаған. Виженердің running key шифры проблемасы криптоаналитиктерде қолында кілт жайлы ақпарат болуы(блоктың таныс тілде жазылуын ескерсек). Ал бұл ақпарат шифрланған мәтіннің өзінде көрініп тұрады. Егерде кілт шынымен де кездейсоқ, әрі мәтін ұзындығына тең болса, сонымен қатар ол бір рет қана қолданылса, онда Виженер шифры теориялық түрде бұзылуға келмейді. Ендеше бұл жүйе факт түрінде төзімділікке жауап беретін Вернам-Виженер шифрына сәйкес келеді. Айқын төзімділігіне қарамастан Виженер шифры Еуропада кең қолданылмағанымен, Гронсфельд шифры бұл жерлерде танымал бола бастады. Граф Гронсфельдттің құрметіне аталған шифр 10 әртүрлі алфавитті (0-ден 9-ға дейінгі сандарға сәйкес келеді) қолданғанынан басқа, құрылымы Виженер шифрына сәйкес келеді. Гронсфельд тәсілінің артықшылығы мәтін ұзындығына сәйкес болғанша қайталанатын, әрі әріптен емес цифрадан тұратын кілтте жатыр. Гронсфельд тәсілі өзінің кемшілігіне қарамастанбүкіл Германия мен Еуропада танымал болған.

Дереккөздер

1. ↑ Martin, Keith M. Everyday Cryptography. — Oxford University Press, 2012. — p. 142 с. — ISBN 978-0-19-162588-6.
2. ↑ Перейти к: 1 2 3 4 5 6 7 8 Бабаш А.В., Шанкин Г.П. История криптографии. Часть I.. — М.: Гелиос АРВ, 2002. — С. 240 с.. — ISBN 5854380439.
3. ↑ Перейти к: 1 2 Носов В. А. Краткий исторический очерк развития криптографии (рус.) // Московский университет и развитие криптографии а России. Материалы конференции в МГУ.. — (17 октября 2002).
4. ↑ Перейти к: 1 2 3 David, Kahn. The Codebreakers: The Story of Secret Writing. — Simon & Schuster, 1999. — ISBN 0-684-83130-9.
5. ↑ Knudsen, Lars R. Block Ciphers—a survey. — London: Springer, 1997. — ISBN 3-540-65474-7.
6. ↑ Stanislaw Jarecki Crypto Overview, Perfect Secrecy, One-time Pad // University of California. — 2004.
7. ↑ Richard A. Mollin. Codes: The Guide to Secrecy From Ancient to Modern Times. — Chapman and Hall/CRC, 2005. — 704 Pages с. — ISBN 9781584884705.
8. ↑ Жельников В. Кpиптография от папируса до компьютера — М.: ABF, 1996. — 336 с. — ISBN 5-87484-054-0
9. ↑ Singh S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. — New York City: Doubleday, 1999. — 416 p. с. — ISBN 978-1-85702-879-9.
10. ↑ Н. Смарт. Криптография.. — Москва: Техносфера, 2005. — 528 с. — ISBN 5-94836-043-1.
11. ↑ Henk C.A. van Tilborg. Encyclopedia of Cryptography and Security. — Springer, 2005. — 115 с. — ISBN 038723473X.
12. ↑ Lab exercise: Vigenere, RSA, DES, and Authentication Protocols // CS 415: Computer and Network Security. — 2006.
13. ↑ Arto Salomaa. Public-Key Cryptography. — ISBN 3540528318.

Әдебиет

• Бабаш А.В., Шанкин Г.П. История криптографии. Часть I. — М.: Гелиос АРВ, 2002. — 240 с. — ISBN 5854380439.
• Жельников В. Кpиптография от папируса до компьютера — М.: ABF, 1996. — 336 с. — ISBN 5-87484-054-0
• Arto Salomaa. Public-Key Cryptography. — ISBN 3540528318.
• Н. Смарт. Криптография.. — Москва: Техносфера, 2005. — 528 с. — ISBN 5-94836-043-1.
• Singh S. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography — New York City: Doubleday, 1999. — 416 p. — ISBN 978-1-85702-879-9, 978-0-385-49531-8
• Richard A. Mollin. Codes: The Guide to Secrecy From Ancient to Modern Times. — Chapman and Hall/CRC, 2005. — 704 Pages с. — ISBN 9781584884705.
• Martin, Keith M. Everyday Cryptography. — Oxford University Press, 2012. — 142 с. — ISBN 978-0-19-162588-6
• Knudsen, Lars R. Block Ciphers—a survey. — London: Springer, 1997. — ISBN 3-540-65474-7.
• Henk C.A. van Tilborg. Encyclopedia of Cryptography and Security. — Springer, 2005. — 115 с. — ISBN 038723473X.
• Arto Salomaa. Public-Key Cryptography. — ISBN 3540528318.

Сыртқы сілтемелер

• Носов В. А. Краткий исторический очерк развития криптографии (рус.) // Московский университет и развитие криптографии а России. Материалы конференции в МГУ.. — (17 октября 2002).
• Stanislaw Jarecki Crypto Overview, Perfect Secrecy, One-time Pad // University of California. — 2004.
• Lab exercise: Vigenere, RSA, DES, and Authentication Protocols // CS 415: Computer and Network Security. — 2006.