Криптография и методы ее практического применения

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

Криптография — это прикладная наука о методах и способах преобразования информации с целью её защиты от незаконных пользователей.

До 60-70-х годов ХХ века криптография во всех странах находилась в ведении структур, отвечающих за безопасность связи и информации. Развитие средств связи, таких как телеграф, телефон, радио, обуславливало изменение характера криптографии, а с применением электронных средств передачи информации задачи криптографии усложнились и расширились. В настоящее время криптографическая защита информации из тайнописи, доступной лишь посвященным, превращается в общенародное достояние.

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

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

Ситуация складывается так, что в недалёком будущем знакомство с криптографией потребуется каждому пользователю электронных средств обмена информацией. Поэтому вскоре криптография станет «третьей грамотностью» - по аналогии со «второй грамотностью», как называют владение компьютером и информационными технологиями.

Проблема защиты информации очень актуальна в настоящее время и в России. У нас не хватает специалистов, которые занимались бы этой проблемой. Многие российские пользователи ПК имеют только поверхностное представление о проблемах защиты информации и поэтому относятся к защите информации попустительски, что часто приводит к серьезным проблемам.

Актуальность настоящей работы обуславливается возникшими противоречиями между возрастающими требованиями общества к уровню знаний молодого поколения в области защиты информации и современным состоянием процесса обучения в общеобразовательной школе по данному вопросу. Рассмотрение вопросов, связанных с данной тематикой носит как теоретическую, так и практическую значимость.

Высокая значимость и недостаточная практическая разработанность этой проблемы определяют несомненную новизну данного исследования.

Объект нашего исследования - криптография и методы ее практического применения.

При этом предметом исследования являются отдельные вопросы, сформулированные в качестве задач данного исследования.

Цель нашей работы – исследование методов криптографической защиты информации для создания программ шифрования и дешифрования на языке программирования Pascal.

В рамках достижения цели были поставлены следующие задачи:

• систематизировать знания научных источников по истории криптографии;

• проанализировать математические основы симметричной криптографии;

• расширить знания о существующих способах защиты данных и о преимуществах криптографической защиты информации;

• автоматизировать алгоритмы шифрования, используя среду программирования Pascal.

Методы исследования:

• теоретический - анализ и синтез статей, обзоров специализированных и периодических изданий, информационных ресурсов Интернет по обозначенной теме;

• эмпирический - проведение эксперимента по созданию программ автоматизации алгоритмов шифрования, используя среду программирования Pascal и применение их в образовательном процессе.

История криптографии

Криптография известна с древнейших времен. В исторических документах древних цивилизаций Индии, Египта, Месопотамии имеются сведения о системах и способах составления шифровального письма. В древнеиндийских рукописях изложены 64 способа преобразования текста, в частности написание знаков не по порядку, а по определенным правилам. Более достоверные сведения о применяемых системах шифров относятся к периоду возникновения древнегреческих государств. Потребителями криптографии в этот период являлись структуры административной и религиозной власти. Плутарх сообщает, что жрецы хранили тексты прорицателей в зашифрованном виде. Э. Шюре в книге "Великие посвященные" пишет, что "с великим трудом и большой ценой добыл Платон один из манускриптов Пифагора, который никогда не записывал свое эзотерическое учение иначе, как тайными знаками и под различными символами". Там же отмечается, что Аристотель получил от Платона шифрованный текст Пифагора.

В период расцвета арабских государств (VIII век н. э. ) криптография получила новое развитие. Да и само слово "шифр" арабского происхождения, как и "цифра". В 855 году появилась "Книга о большом стремлении человека разгадать загадки древней письменности", в которой приводится описание систем шифров, в том числе и с применением нескольких шифроалфавитов. В 1412 году была издана 14-томная энциклопедия, составителем которой являлся Шехаб аль-Кашканди. В данной энциклопедии содержится раздел о криптографии, где дано описание всех известных автору способов шифрования, а также упоминается о криптоанализе системы шифра, который основан на частотных характеристиках открытого и шифрованного текста. Приводится также частота встречаемости букв арабского языка на основе маркировки текста Корана. Шифр простой замены, когда буквам алфавита ставятся в соответствии другие буквы того же алфавита, был известен до Рождества Христова, так, в Спарте в V-VI веке до н. э. существовала хорошо развитая криптография. К этому же времени относятся возникновение специального жезла для шифрования – "сцитала", применяемого для шифра перестановки. Аристотель (384-322 до н. э. ), древнегреческий ученый, ученик Платона и учитель Александра Македонского, обладал почти всеми доступными в то время знаниями. В криптографии он известен как автор способа вскрытия шифра сцитала.

В XV-XVIII веках в математике были заложены основы аппарата, применяемого в криптографии для анализа шифров и дешифрования. Основным средством для шифрования становятся коды.

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

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

В 70-х годах была опубликована революционная работа «Новые направления в криптографии» молодых американских ученых У. Деффи и М. Хеллмана. В это время количество публикаций по криптографии стремительно увеличилось. Тому были разные причины: с одной стороны, постоянное расширение областей применения криптографии; с другой – новизна и привлекательность для ученых математических моделей и задач, которые возникают из потребностей криптографии. И наконец, именно в это время сформировались все атрибуты криптографии как науки: возникли направления и научные школы со своей внутренней логикой развития, появились специализированные международные журналы, сложилась практика ежегодного проведения международных конференций.

С 70-х годов сфера применения криптографии начала расширятся, криптография стала гражданской отраслью, то есть криптографические средства начали применяться для защиты коммерческой информации.

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

Математические основы криптографии.

Комбинаторика.

Понимание математического характера криптографии началось с работ все того же К. Шеннона. Его труд «Математическая теория криптографии» в секретном варианте появился в 1945 году. А рассекречен и опубликован был в США в 1949 году. В 1963 году по инициативе А. Н. Колмогорова сборник работ К. Шеннона был издан и на русском языке.

Криптографические методы и средства защиты информации, а также их математические основы являются фундаментальными исследованиями, связывающими воедино области математики, информатики и физики.

Одним из разделов математики, который используется в криптографии, является комбинаторика. Она занимается разного рода наборами, которые можно образовывать из элементов некоего конечного множества. Некоторые элементы комбинаторики были известны в Индии ещё во II в. до н. э. Индийцы умели вычислять числа, которые сейчас называют «сочетаниями». В XII в. Баскара вычислял некоторые виды сочетаний и перестановок.

Как научная дисциплина комбинаторика сформировалась в XVII в. : французский автор А. Также посвятил сочетаниям и перестановкам целую главу в книге «Теория и практика арифметики» (1656 г. ).

Термин «комбинаторика» стал употребляться после опубликования Лейбницем в 1665 г. работы «Рассуждение о комбинаторном искусстве», в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался

Я. Бернулли во второй части своей книги «Ars conjectandi» («Искусство предугадывания») в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.

Для криптографии важными являются такие алгоритмы комбинаторики как правило умножения, выборки и перестановки. На этих алгоритмах основываются способы формирования секретных ключей для симметричных шифров. [8].

Правило умножения

Если выбор объекта происходит в два этапа и на первом этапе существует n возможностей, а на втором — m возможностей, то итоговое количество вариантов выбора равно n х m.

Выборки

Пусть имеется n объектов, и мы выбираем из них m объектов. Это и есть выборки. Количество выборок зависит от следующих факторов: считаем ли мы различными выборки из одинаковых элементов, но идущих в разном порядке (например, считаем ли мы выборки «abc» и «cab» одинаковыми или различными); возможно ли выбирать уже выбранный элемент повторно (например, в алфавите «abc» с возможностью повторного выбора элемента могут существовать выборки: «aab», «ссс», «abb» и т. д. ).

Рассмотрим случай, когда элемент не может быть выбран повторно. Это — выборки без возвращения. Количество вариантов при использовании выборок без возвращения можно рассчитать по формуле: Аmn = n(n-1)(n-2). (n-m + 1)

Алгоритм выбора

1. Ha первом этапе у нас есть возможность выбрать один элемент из n. Это можно сделать n различными способами.

2. На втором этапе можно выбрать только один из оставшихся n -1 элементов, так как один из элементов уже выбран.

3. На m-м этапе можно выбрать из n - m +1 оставшихся элементов.

4. По правилу произведения получаем количество всех возможных вариантов путем умножения количества вариантов, полученных на этапах с 1 по m.

Перестановки

Часто требуется не выбирать какие-либо элементы, а просто изменять их порядок следования. Для этого применяются перестановки.

Перестановка — это выборка п элементов из п возможных, в которой элемент не может быть выбран повторно. Для вычисления возможного количества перестановок используется формула:

Рп = Апп = n(n-1)(n-2). (n-n + 1) = n! [8].

3. 2. Построение ключей

Придумывание хорошего шифра – дело трудоемкое и дорогостоящее. Поэтому желательно увеличить «время жизни» хорошего шифра и использовать его для шифрования как можно большего количества сообщений.

Безопасность защищаемой информации определяется в первую очередь ключом (Приложение 1). Сам шифр считается известным противнику и доступным для предварительного изучения. Но применяемые в шифрах преобразования информации зависят от ключа. Поэтому у противника появляется новая задача – определить ключ, после чего можно легко почитать зашифрованные этим ключом сообщения. Законные же пользователи прежде чем обмениваться шифрованными сообщениями, должны тайно от противника обмениваться ключами или установить одинаковый ключ на обоих концах канала связи.

Чтобы оценить стойкость криптоалгоритма (Приложение 1), основываясь на длине ключа, необходимо подсчитать, сколько времени будет затрачено взломщиком для перебора всех возможных вариантов ключей для данного алгоритма.

Ключи могут быть составлены из символов алфавита, но некоторые алгоритмы в качестве ключа используют последовательность двоичных кодов, что позволяет применять к открытому тексту такие операции, как побитовое сложение и вычитание. Чтобы получить двоичный ключ, нужно каждому его элементу поставить в соответствие код из таблицы ASCII и затем перевести каждый полученный код в двоичную систему счисления. [8].

3. 3. Криптоалгоритмы: симметричные и асимметричные

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

4. Основы симметричной криптографии. Простейшие алгоритмы.

4. 1. Шифры замены.

Шифр замены — шифр, преобразования которого заключаются в замене каждого символа открытого сообщения на другие символы — шифрообозначения, где порядок следования шифрообозначений совпадает с порядком следования соответствующих им символов в открытом тексте.

4. 1. 1. Шифр Атбаш.

Один из первых шифров. Порой священные иудейские тексты шифровались методом замены, когда вместо первой буквы алфавита писалась последняя буква, вместо второй – предпоследняя и т. д.

В ходе исследования были разработаны программы кодирования и декодирования шифра Атбаш.

Листинг программы uses crt; var i: integer; s,r: string; begin clrscr; {kodirovanie} writeln ('Vvedite text'); readln (s); for i:=1 to length(s) do begin r[i]:=chr(123-(ord(s[i])-96)); write(r[i]); end; readln;

{dekodirovanie} writeln ('Vvedite shifr'); readln (s); for i:=1 to length(s) do begin r[i]:=chr(97+(122-ord(s[i]))); write(r[i]); end; readln; end.

4. 1. 2. Шифр Цезаря.

Известен факт шифрования переписки Юлия Цезаря (100-44гг. до н. э. ) с Цицероном (106-43 гг до н. э. ). Шифр Цезаря реализуется заменой каждой буквы сообщении другой буквой этого же алфавита, отстоящей в алфавите от данной буквы на фиксированное число букв. В своих шифровках Цезарь заменял букву исходного открытого текста буквой, расположенной по отношению к исходной букве на три позиции вперед. Шифр Цезаря называется циклическим потому, что при выполнении замены буквы алфавита рассматриваются как расположенные по кругу вслед за последней буквой алфавита следует первая буква алфавита. В ходе исследования были разработаны программы кодирования и декодирования шифра Цезаря:

Листинг программы кодирования шифра: program cezar_cod; uses crt; var f,s:string; a,c:char; i,k,d,l:integer; begin clrscr; writeln ('vvedite text'); readln (s); writeln ('kluch'); readln (l); for i:=1 to length (s) do begin a:=s[i]; k:=ord(a); if k > 122-l then d:=l-(122-k)+96 else d:=k+l; {проверка конца алфавита} c:=chr(d); if a=' 'then f:=f+' ' else f:=f+c; end; write (f); readkey; end.

Листинг программы декодирования шифра: program cezar_decod; uses crt; var f,s:string; a,c:char; i,k,d,l:integer; begin clrscr; writeln ('vvedite shifr'); readln (s); writeln ('kluch'); readln (l); for i:=1 to length (s) do begin a:=s[i]; k:=ord(a); if k <97+l then d:=123-(l-(k-97)) else d:=k-l; {проверка конца алфавита} c:=chr(d); if a=' 'then f:=f+' ' else f:=F+c; end; write (f); readkey; end.

4. 1. 3. Квадрат Полибия

В Древней Греции (II в. до н. э. ) был известен шифр, который выполнялся с помощью квадрата Полибия. Для шифрования использовалась таблица, представляющая собой квадрат с пятью строками и пятью столбцами, которые нумеровались цифрами. В каждую клетку такой таблицы записывалась одна буква. В результате каждой букве соответствовала пара чисел, и шифрование сводилось к замене букв парой цифр.

Идею квадрата Полибия рассмотрим на примере таблицы с русскими буквами. Число букв в русском алфавите отличается от числа букв в греческом алфавите, поэтому размер таблицы выбран иным (6х6). Заметим, что порядок расположения символов в квадрате Полибия является секретным ключом. Например слово "КРИПТОГРАФИЯ" зашифруется с помощью нашей таблицы числами: 26-36-24-35-42-34-14-36-11-44-24-63.

В ходе исследования были разработаны программы кодирования и декодирования данного шифра (текст вводится английскими строчными буквами): program polibian; uses crt; var s:array [1. 6,1. 6] of char; i,j,d,k,l,z: integer; t,x,y: string; begin clrscr; l:=96; for i:=1 to 6 do begin for j:=1 to 6 do begin l:=l+1; s[i,j]:=chr(l); end; end; s[5,3]:=' ';s[5,4]:='0'; s[5,5]:='2'; s[5,6]:='3'; for j:=1 to 6 do s[6,j]:=chr(51+j); for i:=1 to 6 do begin for j:=1 to 6 do write (s[i,j],' '); writeln; end; writeln ('Vvedite text'); readln (t); for z:=1 to length(t) do for i:=1 to 6 do for j:=1 to 6 do if s[i,j]=t[z] then write(i,j,'_'); writeln; writeln ('Vvedite shifr'); readln (t); for z:=1 to length(t) do for i:=1 to 6 do for j:=1 to 6 do begin str(i,x);str(j,y); if x+y=copy(t,z,2) then write (s[i,j]); end; readkey end.

Таблица Виженера.

Одна из основных проблем шифров простой замены – это неустойчивость к атакам, основанным на вероятностном шифровании. При достаточно большой длине шифротекста этот шифр легко взламывается путем подсчета появлений одинаковых символов. Криптографы долгое время искали возможность защитить криптоалгоритмы от подобных атак. Результатам стали шифры, использующие для шифрования более чем один алфавит. Многоалфавитные шифры используют два и более алфавитов для шифрования.

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

Заключение.

Подводя итоги нашему исследованию, можно сказать, что цель работы достигнута и получены следующие результаты:

• систематизированы знания научных источников по истории криптографии;

• проанализированы математические основы симметричной криптографии;

• расширены знания о существующих способах защиты данных и о преимуществах криптографической защиты информации;

• созданы программы автоматизирующие алгоритмы шифрования с использованием среды программирования Pascal.

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

Разработанные нами программы можно использоваться на уроках и кружках по информатики в начальной школе и среднем звене. Их можно применять при рассмотрении простых криптоалгоритмов в теме «Кодирование информации» и проверки умений и навыков зашифровывать и расшифровывать информацию, используя простейшие шифры. Они будут являться хорошим пособием для демонстрации автоматизации процесса шифрования.