Криптография. 2

1. Теоритическая часть.

1. Введение.

   История криптографии насчитывает около 4 тысяч лет. В качестве основного критерия периодизации криптографии возможно использовать технологические характеристики используемых методов шифрования.

   Первый период (приблизительно с 3-го тысячелетия до н.э.) характеризуется господством моноалфавитных шифров (основной принцип – замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами). Второй период (хронологические рамки – с IX века на Ближнем Востоке (Ал-Кинди) и с XV века в Европе (Леон Баттиста Альберти) – до начала XX века) ознаменовался введением в обиход полиалфавитных шифров. Третий период (с начала и до середины XX века) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров.

   Четвёртый период – с середины до 70-х годов XX века – период перехода к математической криптографии. В работе Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам – линейному и дифференциальному криптоанализу. Однако до 1975 года криптография оставалась «классической», или же, более корректно, криптографией с секретным ключом.

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

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

2. История развития криптографии.

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

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

   Криптология - это раздел математики, изучающий математические основы криптографических методов. 
 

1. Криптография  древнего периода.

    Криптография возникла вместе с письменностью. В исторических документах древних цивилизаций Индии, Египта, Месопотамии имеются сведения о системах и способах составления шифрованного письма. Так, в древнеиндийских рукописях содержится изложение 64-х способов преобразования текста. Среди них написание знаков не по порядку, а вразброс по некоторому правилу. Многие из приводимых способов следует рассматривать как криптографические, т. е. обеспечивающие секретность переписки. Приведена система замены букв. Упоминается, что тайнопись является одним их 64-х искусств, которым следует владеть как мужчинам, так и женщинам.Совершенно отсутствуют сведения об использовании шифров в Древнем Китае, что объясняется, по-видимому, сложностью употреблявшегося иероглифического письма. Данные о первых способах тайнописи весьма обрывочны. Предполагается, что она была известна в древнем Египте и Вавилоне. До нашего времени дошли указания на то, что искусство секретного письма использовалось в древней Греции. Первые действительно достоверные сведения с описанием метода шифрования относятся к периоду смены старой и новой эры и описывают шифр Цезаря - способ, которым Юлий Цезарь прятал свои записи от излишне любопытных глаз. С высоты достижений современной криптографии шифр Цезаря предельно примитивен: в нем каждая буква сообщения заменялась на следующую за ней по алфавиту.

   В Спарте в V-VI веке до нашей эры существовала хорошо развитая криптография. Одним из первых приборов, реализующих шифр перестановки, является так называемый прибор СЦИТАЛЛА. Для шифрования текста использовался цилиндр заранее обусловленного диаметра. На цилиндр наматывался тонкий ремень из пергамента, и текст выписывался построчно по образующей цилиндра (вдоль его оси). Затем ремень сматывался и отправлялся - получателю сообщения. Последний наматывал его на цилиндр того же диаметра и читал текст по оси цилиндра. В этом примере ключом такого шифра являлся диаметр цилиндра.

  Интересно, что изобретение дешифровального устройства "АНТИСЦИТАЛЛА" приписывается великому Аристотелю. Он предложил для этого использовать конусообразное "копье", на которое наматывался перехваченный ремень, который передвигался по оси до того положения, пока не появлялся осмысленный текст.

  Полибий описывает систему шифра, называемую "квадрат Полибия".  Применительно к современному латинскому алфавиту из 26 букв шифрование по этому квадрату заключалось в следующем. В квадрат размером 5x6 клеток выписываются все буквы алфавита, при этом буквы I,J не различаются (J отождествляется с буквой I);

Шифруемая буква  заменялась на координаты квадрата, в котором она записана. Так, B заменялась на AB, F на BA, R на DB и т.д. При расшифровании каждая такая пара определяла соответствующую букву сообщения. Ключом такого шифра являлось расположение букв в таблице 5x5. 
 

2.2. Криптография арабского мира.

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

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

2.3. Криптография в эпоху Возрождения (XIV--XVI вв.).

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

   В XVI веке в европейских государствах появились первые специальные органы дипломатической службы. Появление этих государственных органов – спецслужб активно стимулировало развитие криптографии в этих государствах. В 1466 году Леон Альберти, знаменитый архитектор и философ представил трактат о шифрах в папскую канцелярию. В трактате рассматриваются различные способы шифрования, в том числе маскировка открытого текста в некотором вспомогательном тексте. Работа завершается собственным шифром, который он назвал "шифр, достойный королей". Это был многоалфавитный шифр, реализованный в виде шифровального диска.

   Суть заключается в том, что в данном шифре используется несколько замен в соответствии с ключом. Позднее Альберти изобрел код с перешифровкой. Данное изобретение значительно опередило свое время, поскольку данный тип шифра стал применяться в странах Европы лишь 400 лет спустя. В 1518 году в развитии криптографии был сделан новый шаг благодаря появлению в Германии первой печатной книги по криптографии.  Трисемус написал "Полиграфию", первую печатную работу  по  криптографии.  В ней он первым систематически описал применение шифрующих  таблиц, заполненных алфавитом в измененном порядке.

   Отметим, что великий ученый и художник эпохи Возрождения Леонардо да Винчи (1452-1519) владел криптографией и пользовался ею, в частности, в своих рукописях. 
 

2.4. Криптография в XVII--XVIII веках.

   XVII - XVIII века вошли в историю криптографии как эра "черных кабинетов" –специальных государственных органов по перехвату, перлюстрации и дешифрованию переписки (в первую очередь, дипломатической). В штат “черных кабинетов” входили криптографы – дешифровальщики, агенты по перехвату почты, специалисты по вскрытию пакетов (не оставляющему никаких следов), писцы – копировальщики, переводчики, специалисты - граверы по подделке печатей, химики (для выявления “невидимых чернил”), специалисты по имитации почерков и т.д. Таким образом, “черные кабинеты” состояли из высококвалифицированных специалистов в различных областях деятельности. Эти специалисты ценились “на вес золота” и находились под особым покровительством властей.

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

Этот   очень  распространенный вид шифра сохранился до  наших  дней. сообщение:       ПРИЕЗЖАЮ ШЕСТОГО

   В компьютере  такая  операция  соответствует  сложению  кодов

ASCII символов  сообщения и ключа по некоторому  модулю. 

   Во Франции при Людовике XIV по предложению кардинала Ришелье создается дешифровальное отделение, которое возглавил Антуан Россиньоль. Россиньоль, помимо криптографии, увлекался математикой, и это, безусловно, сказалось на эффективности его криптографической деятельности. На основании ряда высказываний Россиньоля можно сделать вывод о том, что именно он впервые сформулировал современную и в наши дни концепцию "временной стойкости шифров". Так, говоря о военных шифрах, он отмечал, что эти шифры должны быть просты, удобны "для применения в боевых условиях" и "должны хранить тайну приказа до его выполнения". Криптография в России развивалась по пути христианских стран. Датой появления криптографической службы следует считать 1549 год (царствование Ивана IV), с момента образования "посольского приказа", в котором имелось "цифирное отделение". Используемые шифры – такие же как в западных странах – значковые, замены, перестановки. Петр I полностью реорганизовал криптографическую службу, создав "Посольскую канцелярию".

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

2.5. Криптография в XIX веке.

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

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

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

   С 80-х годов XIX века криптография во всех ведущих государствах считается наукой и ее изучают в военных академиях. 
 

2.6. Криптография в XX веке.

XX век – век двух мировых войн, век научно-технического прогресса, век социальных потрясений и передела государственных границ. В этом веке криптография стала электромеханической, затем электронной. Это означает, что основными средствами передачи информации стали электромеханические и электронные устройства.

Работы К. Шеннона "Теория связи в секретных системах" (выполнена в 1945 году – опубликована в 1949 году) и  советского ученого-радиотехника В. А. Котельникова "Основные положения автоматической шифровки.

В данных работах  были сформулированы и доказаны математическими  средствами необходимые и достаточные  условия недешифруемости системы шифра. Было установлено, что единственным недешифруемым шифром является так называемая лента одноразового использования(One – time Pad), когда открытый текст шифруется с помощью случайного ключа такой же длины. Это обстоятельство делает абсолютно стойкий шифр очень дорогим в эксплуатации.

1978 – Первая и  наиболее  известная  криптографическая  система  с открытым ключом - так  называемая система RSA.  Ее  название  происходит  от  первых  букв  фамилий авторов Rivest, Shamir и Aldeman, которые придумали ее  во  время совместных   исследований   в   Массачусетском    технологическом институте в 1977 году. Она основана на трудности разложения очень больших целых чисел на простые сомножители. 

3. Заключение.

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

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

2. Практическая  часть.

(Вариант  №20)

1. Общая характеристика задачи.

   ООО «Сигмаком» предоставляет услуги доступа к сети Интеренет. Данные о тарифах на услуги предоставления доступа к Интернету для абонентов квартирного сектора предоставлены на рис. 20.1, о курсе у.е. к рублю РФ на определенную дату – на рис. 20.2. 

1. Построить таблицы по приведенным ниже данным.

      2. Произвести расчет начисленной суммы, баланса на конец месяца в у.е. и рублях за услуги предоставления доступа к Интернету для абонентов квартирного сектора. Для определения начисленной суммы использовать функцию ВПР() (рис. 20.1 – 20.3). Необходимо учитывать, что предоплаченный трафик входит в сумму абонентской платы и необходимо оплачивать только тот трафик, который получен сверх предоплаченного. 

Начислено, у.е. = Абонентская  плата, у.е. +

+ (Трафик, Mb – Предоплаченный трафик, Mb) x

x Стоимость трафика  за 1Mb, у.е.

     Данные расчета занести в таблицу на рис. 20.3

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

   4. Сформировать и заполнить ведомость начисления за услуги предоставления доступа к Интернету за месяц. 
 
 
 
 
 

Тарифы  на услуги предоставления доступа к Интернету

ООО "Сигмаком" для абонентов квартирного сектора

(декабрь  20__г.).

Рис. 20.1. Тарифы на услуги предоставления доступа к Интернету для абонентов квартирного сектора. 

Рис. 20.2. Курс у.е. к рублю РФ, установленный ООО «Сигмаком» 

Начисления  за услуги предоставления доступа к Интернету

за  декабрь 20__г.

Рис. 20.3.  Начисления за услуги предоставления доступа к Интернету

2.Описание алгоритма решения.

1.Запустить табличный процессор MS Excel.

2.Создать книгу с именем «СигмаКом».

3.Лист 1 переименовать в лист с названием «Тариф».

4.На рабочем листе «Тариф» создать таблицу документа

«Тарифы на услуги предоставления доступа к Интернету  для абонентов квартирного сектора»

5.Заполнить таблицу исходными данными (ячейки A6-D9) (см.рис.20.4.).

Рис. 20.4. Рабочий лист «Тарифы»

6.Лист 2 переименовать в лист с названием «Курс».

7.На рабочем листе «Курс» создать таблицу документа

«Курс у.е. к рублю  РФ, установленный ООО «Сигмаком»

8.Заполнить таблицу исходными данными (ячейки A2-B2) (см.рис.20.5.).

Рис. 20.5. Рабочий лист «Курс»

9.Лист 3 переименовать в лист с названием «Начисления»

10.На рабочем листе «Начисления» создать таблицу документа

«Начисления за услуги предоставления доступа к  Интернету»

11.Заполнить таблицу исходными данными (ячейки A5-Е9)

12.Заполнить ячейки F5 – F9 соответственно формулами:

=Тарифы!B6+(E5-Тарифы!C6)*Тарифы!D6

=Тарифы!B8+(E6-Тарифы!C8)*Тарифы!D8

=Тарифы!B9+(E7-Тарифы!C9)*Тарифы!D9

=Тарифы!B7+(E8-Тарифы!C7)*Тарифы!D7

=Тарифы!B6+(E9-Тарифы!C6)*Тарифы!D6 (см.рис.20.6.)

Рис. 20.6. Рабочий лист «Начисление»

(Используем  формулу из условия)

13.Занести в ячейку G5 формулу:    =D5-F5

14.Размножить введенную в ячейку G5 формулу для остальных ячеек (с G6 по G9) данной графы (столбца).

15.Занести в ячейку H5 формулу:  =G5*32

16.Размножить введенную в ячейку H5 формулу для остальных ячеек (с H6 по H9) данной графы (столбца).

17. Добавить в таблицу итоговую строку, введя в ячейку C10 символьную строку «итого».

18.Занести в ячейку D10 формулу: =СУММ(D5:D9)

19.Размножить введенную в ячейку D10 формулу для остальных ячеек (с E10 по H10) данной строки (см.рис.20.7.).

Рис. 20.7. Законченный рабочий лист «Начисление»

20.Добавить новый лист с названием «Гистограмма».

21.На рабочем листе «Гистограмма» представить графически данные с рабочего листа «Начисления» (графы «ФИО абонента», «Баланс на начало месяца, у.е» и «Баланс на конец месяца, у.е») (см.рис.20.8.).

Рис. 20.8. Рабочий лист «Гистограмма»

22.  Разработать структуру шаблона таблицы «Ведомость начисления за услуги предоставления доступа к Интернету за месяц» (см.рис.20.9.).

23.Заполнить ячейки A4 – A8 соответственно формулами:

=Начисления!C5

=Начисления!C6

=Начисления!C7

=Начисления!C8

=Начисления!C9

24.Заполнить ячейки B4 – B8 соответственно формулами:

=Начисления!F5

=Начисления!F6

=Начисления!F7

=Начисления!F8

=Начисления!F9 

25. Добавить в таблицу итоговую строку, введя в ячейку A9 символьную строку «итого».

26.  Занести в ячейку B9 формулу: =СУММ(B4:B8) (см. рис. 20.9).

Рис. 20.9. Рабочий лист «Ведомость» 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. Литература.

1. Акулов О.А., Медведев Н.В. Информатика: базовый курсю – М.:Омега-Л, 2005

2. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: Учеб. Пособие. – М.:Гелиос АРВ, 2005.

3. Информатика. Лабораторный практикум для студентов 2 курса всех специальностей. – М.:ВЗФЭИ, 2006.

4. Самосудов А.  Что может криптография? http://content.online/ru/mpl/face?id=4078

5. Жельников В. Криптография от папируса до компьютера. - М.: "АВF", 1996 -335с.

6. Материалы сайта http://www.elitarium.ru/.