Применение методов криптографии в шифровании информации Процедурное (традиционное)программирование Олимпиадная работа по ИКТ ученика 10Б класса Лежнина. - презентация

1 Применение методов криптографии в шифровании информации Процедурное (традиционное)программирование Олимпиадная работа по ИКТ ученика 10Б класса Лежнина Кирилла и ученика 10В класса Белова Сергея

2 Зачем это надо? В июне 1815 года Наполеон проигрывал англичанам Битву при Ватерлоо. По легенде, за сражением внимательно наблюдали братья Ротшильды. Едва убедившись, что Наполеон проиграет сражение, один из них, державший почтовых голубей, отправил их с зашифрованными инструкциями, в Лондон к своим агентам. Утром следующего дня один из братьев Ротшильдов явился на Лондонскую биржу. Он был единственным в Лондоне, кто знал о поражении Наполеона. Притворно сокрушаясь по поводу успехов французского императора, он начал продавать свои акции. Остальные последовали его примеру. Английские, австрийские и прусские ценные бумаги дешевели с каждой минутой и оптом скупались агентами Ротшильда. О том, что Наполеон проиграл битву, на бирже узнали лишь через день. Многие держатели ценных бумаг покончили с собой, а Ротшильды заработали 40 миллионов фунтов стерлингов. Достоверная информация, полученная раньше других, позволила Ротшильдам вести беспроигрышную игру на бирже. Пожалуй, эта история и не стоила бы упоминания, если бы не дошедшая до нас фраза одного из братьев:Кто владеет информацией, тот владеет миром.

3 Азы криптографии. Азы криптографии. Если вы хотите передать свое текстовое сообщение (последовательность символов некоторого алфавита) адресату так, чтобы оно осталось тайным для посторонних лиц, то у вас есть, по крайней мере, две возможности. Вы можете попытаться скрыть сам факт передачи текста, то есть прибегнуть к методам стеганографии, в арсенале которой - симпатические (невидимые) чернила, микроточки и тому подобные средства. Другая возможность заключается в попытке скрыть смысл сообщения от посторонних лиц, случайно или намеренно познакомившихся с передаваемым текстом. В этом случае вы можете прибегнуть к методам криптографии. Термин «криптография» происходит от двух греческих слов: «криптос» - тайна и «графейн» - писать, и означает тайнопись. «Тайнопись» как раз и подразумевает, что вы скрываете смысл своего сообщения. Сообщение, которое вы хотите передать адресату, будем называть открытым сообщением. Например, одним из открытых сообщений является фраза: КОРАБЛИ ОТХОДЯТ ВЕЧЕРОМ Для сохранения сообщения в тайне оно преобразуется криптографическими методами и только после этого передается адресату. Преобразованное сообщение будем называть шифрованным сообщением (или зашифрованным сообщением). Другое название зашифрованного сообщения - криптограмма (или шифртекст). Данное зашифрованное сообщение может выглядеть, например, так: ЮПЯТБНЩМСДТЛЖГПСГХСЦЦ Зашифрованное сообщение не обязательно должно быть последовательностью букв, как в указанной выше задаче. Часто зашифрованное сообщение может представлять собой последовательность цифр или специальных знаков (например, «пляшущих человечков»). Процесс преобразования открытого сообщения в шифрованное будем называть шифрованием или зашифрованием. Адресату заранее сообщается, как из шифрованного сообщения получить открытое. Этот процесс получения исходного сообщения называют расшифрованием. При выборе правила шифрования надо стремиться к тому, чтобы посторонние лица, не знающие правила расшифрования, не смогли восстановить по криптограмме открытое сообщение. В этом случае вы скроете смысл сообщения и обеспечите тайнопись.

4 Для удобства дальнейшего изложения обозначим буквой A - открытое сообщение, B - шифрованное сообщение, f - правило шифрования, g - правило расшифрования. В этом случае зашифрование открытого сообщения A в шифрованное сообщение B можно записать в виде f(A) = B. Обратное преобразование (то есть получение открытого сообщения A путем расшифрования B) запишется в виде соотношения g(B) = A. Правило зашифрования f не может быть произвольным. Оно должно быть таким, чтобы по шифртексту B с помощью правила расшифрования g можно было однозначно восстановить открытое сообщение A. Однотипные правила зашифрования можно объединить в классы. Внутри класса правила различаются между собой по значениям некоторого параметра, которое может быть числом, таблицей и т. д. В криптографии конкретное значение такого параметра обычно называют ключом. По сути дела, ключ выбирает конкретное правило зашифрования из данного класса правил. Зачем понадобилось вводить понятие ключа? Есть, по крайней мере, два обстоятельства, которые позволяют понять необходимость этого. Во-первых, обычно шифрование производится с использованием специальных устройств. У вас должна быть возможность изменять значение параметров устройства, чтобы зашифрованное сообщение не смогли расшифровать даже лица, имеющие точно такое же устройство, но не знающие выбранного вами значения параметра. Во-вторых, многократное использование одного и того же правила зашифрования f для зашифрования открытых текстов создает предпосылки для получения открытых сообщений по шифрованным без знания правила расшифрования g. Поэтому необходимо своевременно менять правило зашифрования. Используя понятие ключа, процесс зашифрования можно описать в виде соотношения fα(A) = B, в котором α - выбранный ключ, известный отправителю и адресату. Для каждого ключа α шифрпреобразование fα должно быть обратимым, то есть должно существовать обратное преобразование gα, которое при выбранном ключе α однозначно определяет открытое сообщение A по шифрованному сообщению B: gα(B) = A. Совокупность преобразований fα и набор ключей, которым они соответствуют, будем называть шифром.

5 Какие бываю шифры Шифрами перестановки называются такие шифры, преобразования из которых приводят к изменению только порядка следования символов исходного сообщения. Примером преобразования, которое может содержаться в шифре перестановки, является следующее правило. Каждая буква исходного сообщения, стоящая в тексте на позиции с четным номером, меняется местами с предшествующей ей буквой. В этом случае ясно, что и исходное, и шифрованное сообщение состоят из одних и тех же букв. Шифрами замены называются такие шифры, преобразования из которых приводят к замене каждого символа открытого сообщения на другие символы - шифробозначения, причем порядок следования шифробозначений совпадает с порядком следования соответствующих им символов открытого сообщения. В качестве примера преобразования, которое может содержаться в шифре замены, приведем такое правило. Каждая буква исходного сообщения заменяется на ее порядковый номер в алфавите. В этом случае исходный буквенный текст преобразуется в числовой.

6 Под стойкостью шифра, как правило, понимается способность противостоять попыткам провести его вскрытие. При анализе шифра обычно исходят из принципа, сформулированного голландцем Огюстом Керкгоффсом ( ). Согласно этому принципу при вскрытии криптограммы противнику известно о шифре все, кроме используемого ключа. Одной из естественных характеристик шифра является число его возможных ключей. Ведь вскрытие шифра можно осуществлять перебором всех возможных его ключей. Подчас смешивают два понятия: шифрование и кодирование. Мы уже договорились, что для шифрования надо знать шифр и секретный ключ. При кодировании нет ничего секретного, есть только определенная замена букв или слов на заранее определенные символы. Методы кодирования направлены не на то, чтобы скрыть открытое сообщение, а на то, чтобы представить его в более удобном виде для передачи по техническим средствам связи, для уменьшения длины сообщения и т. д. В принципе, кодирование, конечно же, можно рассматривать как шифр замены, для которого набор возможных ключей состоит только из одного ключа (например, буква а в азбуке Морзе всегда кодируется знаками · и это не является секретом). В настоящее время для защиты информации широко используются электронные шифровальные устройства. Важной характеристикой таких устройств является не только стойкость реализуемого шифра, но и высокая скорость осуществления процессов шифрования и расшифрования. Для создания и обеспечения грамотной эксплуатации такой техники широко используются достижения современной криптографии, в основе которой лежат математика, информатика, физика, электроника и другие науки. Современная криптография бурно развивается. В ней появляются новые направления. Так, с 1976 года развивается «открытая криптография». Ее отличительной особенностью является разделение ключей для зашифрования и расшифрования. При этом ключ для зашифрования не требуется делать секретным, более того, он может быть общедоступным и содержаться в телефонном справочнике вместе с фамилией и адресом его владельца. Наряду с термином «криптография» в литературе встречается термин «криптология», также происходящий от греческих корней, означающих «тайный» и «слово». Этот термин используется для обозначения всей области секретной связи. Криптологию делят на две части: криптографию и криптоанализ. Криптограф пытается найти методы обеспечения секретности сообщений, криптоаналитик пытается при неизвестном ключе выполнить обратную задачу. При этом часто говорят, что криптоаналитик вскрыл шифр, хотя чаще он вскрывает ключ заранее известного шифра. Наряду с термином «криптография» в литературе встречается термин «криптология», также происходящий от греческих корней, означающих «тайный» и «слово». Этот термин используется для обозначения всей области секретной связи. Криптологию делят на две части: криптографию и криптоанализ. Криптограф пытается найти методы обеспечения секретности сообщений, криптоаналитик пытается при неизвестном ключе выполнить обратную задачу. При этом часто говорят, что криптоаналитик вскрыл шифр, хотя чаще он вскрывает ключ заранее известного шифра.

7 Шифр перестановки Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки (ШП). Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста. Например, если для преобразования используется подстановка и в соответствии с ней зашифровывается слово МОСКВА, то получится КОСВМА. n n! При больших n для приближенного вычисления n! можно пользоваться известной формулой Стирлинга :

8 Шифр Цезаря Данная работа рассматривает реализацию Цезаря. Шифр Цезаря относится к шифрам простой замены, то есть каждому элементу стандартного алфавита соответствует один и только один элемент шифрованного алфавита. Следует отметить, что справедливо и обратное. Особенность шифра Цезаря заключается в том, что стандартный алфавитсдвигается на n-ое количество символов в произвольную сторону, и вместо символов открытого текста записываются символы нового алфавита в строгом обратимом соответствии. Например, для того, чтобы закодировать слово конференция со сдвигом на 1 символ влево (вместо а будет записана буква б, вместо б будет записана буква в, и так далее), необходимо заменить все символы на соответствующие им, в результате чего получится: лпохжсжочйа (мы берем алфавит из 32 букв без ё). Таким образом, два человека, знающие сдвиг и алфавит, могут передавать друг другу шифрованные сообщения, недоступные третьим лицам. Но, зная шифр, третье лицо при наличие стальных нервов и предельной аккуратности, может перебрать все варианты, а в данном случае их 32(количество вариантов сдвигов, включая нулевой), причем один из них – нулевой – будет истинным и текст может быть прочитан. Но в наше время информация имеет тенденцию к краткосрочности существования, то есть информация устаревает очень быстро. И пока человек будет заниматься дешифровкой информации логическими методами и методом перебора вариантов, она потеряет свою значимость. А если использовать для реализации шифра аппаратные и программные средства, шифрование и дешифровка может занимать не более минуты. Шифр Цезаря применялся еще задолго до эпохи компьютерных технологий, и его реализация не требует особых программных и аппаратных средств. А благодаря тому, что быстродействие компьютеров в наше время позволяет выполнять эти операции гораздо быстрее, шифрование и дешифровка этого шифра происходит практически мгновенно. Теперь перейдем конкретно к программе зашифровки:

9 program zezar; var n: integer; text_star,text_new,alphabet:string; dlina,i,j,l:integer; BEGIN alphabet:='abcdefghijklmnopqrstuv wxyz_'; n := length(alphabet); writeln('Enter your open text'); readln(text_star); writeln('Enter the number of displacement'); readln(l); l := l mod n; dlina:=length(text_star); for i := 1 to dlina do begin for j := 1 to n do if alphabet[j] = text_star[i] then begin text_new[i] := alphabet[(j- 1+l+n) mod n + 1]; break; end; text_new[0] := chr(dlina); text_new[dlina+1] := chr(0); writeln('Open text:',text_star,', the number of displacement is ',l,', the code:',text_new); readln; END.

10 3 варианта программы расшифровки 1.Зная сдвиг алфавита, можно легко раскодировать закрытый текст, введя вместо сдвига в ту же самую программу сдвиг с обратным знаком. 2.Не зная сдвига, можно перебрать все 32 варианта и вывести их на экран и предоставить пользователю возможность самому выбрать осмысленный текст. 3.Не зная сдвига, но используя статистический метод, можно вывести единственный вариант. Последний метод требует дополнительного пояснения:

11 Статистический метод Особенность данного метода заключается в том, что используя статистику частоты использования букв в каком-либо языке, можно найти разницу между номером использования буквы, долю этих букв во всем тексте и разницу между статистическим показателем по этой букве и найденной долей использования этой буквы в введенном тексте и выбрать наименьшую разницу. Она и будет искомой. Следует, отметить, что данный метод не является универсальным, ибо заимствованные и жаргонные слова могут исказить статистику по буквам во введенном тексте. Теперь рассмотрим программу расшифровки:

12 Program ZesarDecodersOdnimVariantom; const n=32; var a:array[0..n] of string; b:array[0..n] of string; f:array[1..n] of integer; p:array[1..n] of real; i,j,k,c,m,ket,q:integer; sum,min:real; s,s1,st:string; flag:boolean; t:text; begin min:=5000; for i:=160 to 175 do a[i-159]:=chr(i); for i:=224 to 239 do a[i-207]:=chr(i); a[0]:='я'; for i:=128 to 159 do b[i-127]:=chr(i); b[0]:='Я'; {относительная частота встречаемости букв русского алфавита} p[1]:=8.89; p[2]:=1.55; p[3]:=3.65; p[4]:=1.69; p[5]:=3.06; p[6]:=8.10; p[7]:=0.92; p[8]:=2.00; p[9]:=6.39; p[10]:=1.19; p[11]:=4.57; p[12]:=5.87; p[13]:=3.08; p[14]:=6.43; p[15]:=10.92; p[16]:=2.71; p[17]:=4.16; p[18]:=5.11; p[19]:=5.76; p[20]:=3.03; p[21]:=0.06; p[22]:=0.84; p[23]:=0.29; p[24]:=1.67; p[25]:=1.01; p[26]:=0.26; p[27]:=0.03; p[28]:=2.12; p[29]:=2.32; p[30]:=0.14; p[31]:=0.33; p[32]:=1.88;

13 assign(t,'Input.txt'); reset(t); readln(t,s); close(t); k:=0; for i:=1 to length(s) do begin for j:=1 to n do if (s[i]=a[j]) or (s[i]=b[j]) then begin f[j]:=f[j]+1; end; for k:=1 to n do {перебираем возможные ключи} begin sum:=0; for m:=1 to n do {обнуляем массив частот букв при данном ключе} begin f[m]:=0; end; s1:=s; for i:=1 to length(s1) do {просматриваем текст} begin flag:=false; for j:=1 to n do begin if (s1[i]=a[j]) and (flag=false) then {если находим букву русского алфавита,то формируем новый текст по данному ключу} begin delete(s1,i,1); c:=j-k; if c

14 if (s1[i]=b[j]) and (flag=false) then begin delete(s1,i,1); c:=j-k; if c

15 Структура работы: Данная работа состоит из двух частей: 1.Программа кодировки текста с использованием шифра Цезаря с заданным сдвигом. 2.Программа декодировки текста с использованием шифра Цезаря с неизвестным шагом.

16 Как работать с этими программами? 1.Вы можете сами (вручную) закодировать фразу, но для удобства мы создали программу, которая поможет быстро Вам это сделать. Запустите файл ZEZAR_ZA.PAS, введите исходную фразу и сдвиг, запомните полученную фразу! 2.Запустите файл DESHIFRR.PAS, введите зашифрованную фразу и получите расшифровку!

17 Список использованной литературы Кирюхин В.М., Лапунов А.В., Окулов С.М. Задачи по информатике: Международные олимпиады 1989 – 1996: Для факультативов по информатике в старших классах. – М.: ABF, 1996 Боглаев Ю.П. Вычислительная математика и программирование. – М.: Высшая школа, 1990 Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. – М.: Наука, Майерс Г. Искусство тестирования программ. – М.: Финансы и статистика, Никольская И.Л. Математическая логика. – M.: Высшая школа, 1981.