Въведение в мрежовата сигурност / Network security basics

admin
Free
  • 2 lessons
  • 0 quizzes
  • 10 week duration

Анализ на функционалността, програмна реализация и използване на шифър на Виженер / Analysis of the functionality, development and implementation of the Vigenere cipher

Анализ на функционалността, програмна реализация и използване на шифър на Виженер

1. Въведение

    Целта на това практическо упражнение е студентите да усвоят особеностите на шифъра на Виженер. За изпълнението на поставената цел, ще се извърши теоретичен анализ на функционалността на шифъра на Виженер и посредством работната среда на Python ще се реализира програмен модул за прилагане на шифъра. Създаването на модула ще бъде проследено и разяснено стъпка по стъпка. В края на практическото упражнение, студените ще тестват създадения от тях програмен модул и ще шифрират и дешифрират съобщения с шифъра на Виженер.

2. Цел на упражнението

  • История и анализ на функционалните особености на шифъра на Виженер;
  • Реализиране на програмен модул за прилагане на шифър на Виженер;
  • Шифриране на текстова информация и дешифриране на шифрограми посредством създадения програмен модул.

3. Инсталиране на Python и запознаване с работната среда

    Изтеглете инсталационния файл на Python 2.7. След изтегляне, стартирайте инсталационния файл python-2.7.3.exe и инсталирайте работната среда с настройките по подразбиране. Стартиране на Python в графичен режим и се запознайте с работната среда. От меню Start изберете All Programs > Python 2.7 > IDLE (Python GUI). След като работния екран на Python се зареди разгледайте менютата и възможностите, които ви се предоставят.

4. История и анализ на функционалните особености на шифъра на Виженер

    Шифъра на Виженер е много по-сигурен в сравнение с шифрите със заместване и шифъра на Цезар. Това се дължи на факта, че съществуват огромен брой възможни ключове, за да се извърши атака с изчерпателно претърсване, както и на това, че този шифър не може да бъде разбит въз основа на честотата на срещане на буквите в езиците. За пръв път информация за шифъра е публикувана през 1553 от италианския криптограф Джовани Батиста Беласо (Giovan Battista Bellaso), но носи наименованието на Блейз ди Виженер (Blaise de Vigenère), който го преоткрива многократно в годините след 1553. Смята се, че шифъра остава неразбиваем докато Чарлз Бабидж (Charles Babbage) не го разбива през 19-ти век. На френски шифъра е известен като le chiffre indéchiffrable, което се превежда като неразшифруемия шифър.
Analysis of the functionality, development and implementation of the Vigenere cipher

1. Introduction

    The purpose of this practical exercise is to present to the students the specifics about the Vigenere cipher. For the completion of the purpose of the exercise, the students will go through a detailed analysis of the functionality of the Vigenere cipher and using the Python IDLE environment will realise their own programing module for the implementation of the cipher. The development of the programing module will be presented in details and will be provided on a step-by-step principle. At the end of the exercise, the students will test the developed programing module and will encode and decode messages using the Vigenere cipher.

2. Purpose of the exercise

  • Introduction to the Vigenere cipher and analysis on its functional specifics;
  • Development of a programing module for implementation of the Vigenere cipher;
  • Encoding and decoding of plaintext messages using the developed programing module for implementation of the Vigenere cipher.

3. Installation of Python and introduction to the working environment

    Download the installation file for Python 2.7. After downloading the required files, execute file python-2.7.3.exe and install the work environment with default configuration. Start the Python GUI and get to know the working environment. From menu Start, choose All Programs > Python 2.7 > IDLE (Python GUI). When the IDLE environment is started, explore the environment and the menus.

4. History and analysis of the functional specifics of the Vigenere cipher

    The Vigenere cipher is much more secure construction, compared to the Caesar cipher and other substitution ciphers. This is because the cipher key space is much larger, which makes any brute-force attack inoperable, as the time for the attack will be very long and unacceptable. Additionally, the methods for plaintext attack, which were suitable for the substitution ciphers, are also not usable with the Vigenere cipher, as the cipher texts are not presenting any means for measuring the frequency of letter repetition. For the first time information about the cipher was published in 1553 by the Italian cryptographer Giovan Battista Bellaso, but the cipher is named after Blaise de Vigenère, who rediscovers the cipher in the years following 1553. It is considered that the cipher remained unbroken until the 19th century, when Charles Babbage managed to break it and published his results. In French, the cipher is known as le chiffre indéchiffrable, which means the undecipherable cipher.

    Шифъра на Виженер наподобява шифъра на Цезар, но с тази разлика, че се използват множество ключове. Често, поради факта, че се използва повече от едно множество от замествания, шифъра се нарича и полиазбучен шифър със заместване (polyalphabetic substitution cipher). При шифъра на Цезар обикновено се използват стойностите от 0 до 25, които указват преместването на символа от азбуката. При шифъра на Виженер, вместо цифри се използват букви. Буквата A ще се използва за ключ 0, буквата B за 1 и така до Z, която ще отговаря на 25.
    The Vigenere cipher has some similarities with the Caesar cipher, but with the difference that many keys can be used. Because there is more than one substitution, the cipher is also referred to as polyalphabetic substitution cipher. The Caesar cipher usually implements the values from 0 to 25, which are used to determine rate for the shifting of the alphabetic letters. With the Vigenere cipher, letters are used instead of digits. The letter A will be used as key 0, the letter B as 1 and so on until Z, which will represents 25.

    Ключа при шифъра на Виженер е последователност от символи, които могат да формират (или не) определена дума. Тази ключовата дума се разделя на множество подключа. Ако се използва думата PIZZA, първия подключ е P, втория е I, третия и четвъртия са Z, а последния пети подключ е A. Първия подключ се използва за шифриране на първия символ от съобщението, втория подключ се използва за втория символ и т.н. След изчерпването на символите от ключовата дума, се преминава отново към първия подключ от нея и операцията се повтаря, докато не се шифрира цялото съобщение. По този начин шифъра на Виженер наподобява многократното използване на шифъра на Цезар.
    The key in the Vigenere cipher is a string of symbols, which can represent or not a specific word. This keyword is divided into a subset of keys. For example, let us take the keyword PIZZA. In this case, the first sub-key will be P. The second sub-key will be I. The third and fourth sub-keys will be Z, and the last one will be A. The first sub-key will be used for the encoding of the first symbol of the plaintext message. The second sub-key will be used for the encoding of the second symbol in the plaintext message and so on. After all sub-keys are used once, the whole keyword is used again repeatedly, until the whole plaintext message is fully encoded. In this way, the Vigenere cipher reassembles the repeated implementation of the Caesar cipher.

    По този начин за да шифрираме съобщението “COMMON SENSE IS NOT SO COMMON” с ключа “PIZZA” ще трябва да приложим един и същ шифър на Цезар за всеки пети символ.
    In this way, if we wish to encrypt the message “COMMON SENSE IS NOT SO COMMON” with the keyword “PIZZA”, we will have to apply the same Caesar cipher for each fifth symbol.

    За криптирането на буквата C се използва подключа P, който е 15-я символ в английската азбука, което означава, че ще се получи шифрограмата R и т.н. Процеса се повтаря за всички символи от съобщението.
    For the encryption of the letter C we will use the sub-key P, which is the 15th symbol in the English alphabet, which means that we will get the encrypted letter R and so on. The process is repeated for all symbols from the message.

    Използването на шифъра на Виженер с ключовата дума PIZZA (която е съставена от подключове 15, 8, 25, 25, 0) и съобщението COMMON SENSE IS NOT SO COMMON извежда шифрограмата RWLLOC ADMST QR MOI AN BOBUNM. С увеличаване на броя на символите в ключовата дума, се увеличава и степента на сигурност, която се предоставя от шифъра срещу атаки с изчерпателно претърсване. Ключовата дума PIZZA е изключително слаба, като ключ, защото съдържа само пет символа. При нея са налични 11 881 376 възможни комбинации (265 = 26 × 26 × 26 × 26 × 26 = 11 881 376). Единадесет милиона ключа са прекалено много за ръчно разбиване на шифъра, но компютър може да се справи с тази задача за няколко часа. Процеса ще включва първоначалното дешифриране на шифрограмата с ключовата дума AAAAA и проверка за наличието на английски думи в текста. Ако такива не са намерени ще се продължи с ключовата дума AAAAB, след което с AAAAC и така докато се стигне до PIZZA. Добрата новина е, че за всяка допълнителна буква в ключовата дума, броя на възможните комбинации се увеличава кратно на 26.
    The use of the Vigenere cipher with the keyword PIZZA (which is composed from the sub-keys 15, 8, 25, 25, 0) and the plaintext message COMMON SENSE IS NOT SO COMMON outputs the cipher text RWLLOC ADMST QR MOI AN BOBUNM. With the increase of the number of symbols in the keyword, we increase the difficulty of the cipher, which will make it harder to break with brute-force attacks. The keyword PIZZA is extremely weak, as a key, because it contains only five sub-keys. With her, there are 11 881 376 possible combinations (265 = 26 × 26 × 26 × 26 × 26 = 11 881 376). Eleven million keys are too much for manual decoding of the cipher text, but a modern computer can do this in few minutes. The process will include the initial deciphering of the cipher text with the keyword AAAAA and check for any English words in the output. If no words are found, the program will continue with the keyword AAAAB, then with the keyword AAAAC, etc., until it reaches the keyword PIZZA. The good news is that for every additional sub-key, the number of possible combinations is increased by multiplication with 26.

    Ключовата дума може да бъде всяка една дума, включително и произволна комбинация от символи, като DURIWKNMFICK. На практика е много удачно да се използва за ключова дума такава последователност от символи, каквато не може да се намери в речник. Думата RADIOLOGISTS е съставена от 12 символа и се помни по-лесно от DURIWKNMFICK. Опитен криптоаналитик обаче е в състояние да се досети, че е използвана 12 символна дума за ключ, което означава 95,428,956,661,682,176 възможни комбинации, но думите от 12 символа са далеч по-малко – 1,800. Това прави използването на думата RADIOLOGISTS по-лесно за разбиване от това да се използва 3 символен произволен низ. Разбира се криптоаналитика няма как да знае, колко символа е ключовата дума, което прави този факт малко по-лесен за приемане. Въпреки това може да се опита решаване на шифрограмата, чрез итеративно увеличаване на стойността на символите в ключовата дума.

5. Реализиране на програмен модул за прилагане на шифър на Вижинер

    Създайте нов файл с разширение .py и го отворете с текстов редактор по ваш изобр. Запознайте се с програмния код и го анализирайте:
    The keyword can be every single word, including a random symbol combination, like DURIWKNMFICK. Practically, it is very good to use as a keyword a symbol combination, which cannot be found in a dictionary. The word RADIOLOGISTS is composed from 12 symbols and is more easly remembered than DURIWKNMFICK. A good cryptanalyst can figure out that a 12-symbol word is used as a keyword, which means that there are 95,428,956,661,682,176 possible combinations, but the letters formed by 12 symbols are much less – just 1,800. This means that the word RADIOLOGISTS is much easier to break then to use any random 3-symbol combination. Of course, the cryptanalyst cannot know, how long the keyword is, which makes this situation a little easier to accept. However, the cryptanalyst can try resolving the encryption by iteratively increasing the value of the characters in the keyword until he manages to break the code.

    5. Development of a programing module for implementation of the Vigenere cipher

      Create a new file with a .py extension and open it with a text editor. Introduce the following programing code and try to analyse it:

6. Прилагане на създадения код за шифър на Виженер

    Използвайте новосъздадения програмен код, за да разрешите следните шифрирани съобщения, Ключовата дума за шифрирането им е ZAHARIEV:

    • Zthnrasae iuvvvxzc toe wqvns esetbvjmij dzomozl jodxyodr pn kpi 1930n zt Poni Woztl Cftpzfe.
    • Zthnrasae, om Bltkvqihn, Wziibh hnu Qvdrh hntmwoqy, daj jsmm ou Otbswdr 4, 1903 pn Yiqdktvn, Ema Tnrr tf ir zkejtiqgvk eugzvizq aud r agcnos tvigcdr.
    • Z PLRJWRVK CVMGCXZQ IZ A XMRZQAS-PLZTJRE JODXYODR DHFAI NHZL, CRXEWHLPTZMW VMD VRZOMIZL ZACM TMHCL MRSI DS UZEWCP ANR PNUQZDCUHLJ, IRY HS PNKMRYDD AO SM SKDRHTVL HDQEJTCG FT ZN LNU-CWZQ WPTY VS DMTLRMMRDMG JODXYODR VPVZEONR.
    • Cuyieo xcd Slcfvh Rnrsd Niv, Otrpnx esmjek ffz xcd Gvvvzrhdna Cfli vmd Jygpim Rcooft (KX&BS) ht Stiobhsep Xemj, Byikimi’r cvdvjvzzkpnx kiisrl. Ffz e ohml hv tiy Gua 8, tym wzbtpoe zinoouszjpz eoy Gvzqvm nhvrt gmxpaaeiptriz. Hv liqhsld r vyhaey ow bixgnpqlmw anr irviodmg Neiuei biwhvzw, dmcsuuqrb hmwrfdihdnas kw xcd pye-niv Knlpsy jshae tekpsy znk ae mpzbtyodmgcznpcrt qvbhpnv blvs cvucl jdmd zekbmifs moi blz Dnpgdi qvbhpnv. Bymhnn pciczc a wimwxvk rvlv qr xqajkzvk dmtlrtmtodd joumh hdszaxmw ogaa eeifgdd ahv Ipghez tf liadaa tym Rvyiz ie ueix cyutqeg dnnaxmqzmtz, iekppciug kpi Wztalv wj oge Htcirohc; pt yiw wdeu ejbmhztld kpeo shps nwvf rhvrkmrzc toe niv dm Ebrfxi wx az mrvc vr tdo kw jjtr ferzw
6. Encoding and decoding of plaintext messages using the developed programing module for implementation of the Vigenere cipher

    Use the programing module you have just created to decipher the following messages. The keyword for their decoding is ZAHARIEV:

    • Zthnrasae iuvvvxzc toe wqvns esetbvjmij dzomozl jodxyodr pn kpi 1930n zt Poni Woztl Cftpzfe.
    • Zthnrasae, om Bltkvqihn, Wziibh hnu Qvdrh hntmwoqy, daj jsmm ou Otbswdr 4, 1903 pn Yiqdktvn, Ema Tnrr tf ir zkejtiqgvk eugzvizq aud r agcnos tvigcdr.
    • Z PLRJWRVK CVMGCXZQ IZ A XMRZQAS-PLZTJRE JODXYODR DHFAI NHZL, CRXEWHLPTZMW VMD VRZOMIZL ZACM TMHCL MRSI DS UZEWCP ANR PNUQZDCUHLJ, IRY HS PNKMRYDD AO SM SKDRHTVL HDQEJTCG FT ZN LNU-CWZQ WPTY VS DMTLRMMRDMG JODXYODR VPVZEONR.
    • Cuyieo xcd Slcfvh Rnrsd Niv, Otrpnx esmjek ffz xcd Gvvvzrhdna Cfli vmd Jygpim Rcooft (KX&BS) ht Stiobhsep Xemj, Byikimi’r cvdvjvzzkpnx kiisrl. Ffz e ohml hv tiy Gua 8, tym wzbtpoe zinoouszjpz eoy Gvzqvm nhvrt gmxpaaeiptriz. Hv liqhsld r vyhaey ow bixgnpqlmw anr irviodmg Neiuei biwhvzw, dmcsuuqrb hmwrfdihdnas kw xcd pye-niv Knlpsy jshae tekpsy znk ae mpzbtyodmgcznpcrt qvbhpnv blvs cvucl jdmd zekbmifs moi blz Dnpgdi qvbhpnv. Bymhnn pciczc a wimwxvk rvlv qr xqajkzvk dmtlrtmtodd joumh hdszaxmw ogaa eeifgdd ahv Ipghez tf liadaa tym Rvyiz ie ueix cyutqeg dnnaxmqzmtz, iekppciug kpi Wztalv wj oge Htcirohc; pt yiw wdeu ejbmhztld kpeo shps nwvf rhvrkmrzc toe niv dm Ebrfxi wx az mrvc vr tdo kw jjtr ferzw
7. Заключение

    Шифъра на Виженер не е податлив на директна атака с изчерпателно претърсване, особено когато ключовата дума е съставена от повече от 20 символа. В продължение на векове този шифър се е използвал за размяна на тайни съобщения и съхранение на важни текстове. Първата резултатна атака срещу този шифър става факт в началото на 20-ти век и въпреки сложността на този шифър и той бива разбит. Метода, чрез който това става факт е честотния анализ.
7. Conclusion

    The Vigenere cipher is not susceptible to a direct brute-force attack, especially when the keyword is made up of more than 20 characters. For centuries, this cipher has been used to exchange secret messages and to store important texts. The first resultant attack against this cipher was made in the beginning of the 20th century, and despite the complexity of this cipher, it was broken. The method, by which this was done, is now called frequency analysis.