Шифрование- как метод защиты информации

Введение

 

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

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

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

Когда только возник интернет, никто не мог гарантировать безопасности ваших данных, а переписки в первых чатах велись в открытых глобальных чатах, где каждый мог прочитать, о чем и с кем вы ведете беседу. Все в интернете было прозрачно.

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

Для реализации конфиденциальности и используются те самые алгоритмы шифрования.

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

Криптология

Криптоло́гия (от др.-греч. κρυπτός — скрытый и λόγος — слово) — наука, занимающаяся методами шифрования и расшифровывания. Криптология состоит из двух частей — криптографии и криптоанализа. Криптография занимается разработкой методов шифрования данных, в то время как криптоанализ занимается оценкой сильных и слабых сторон методов шифрования, а также разработкой методов, позволяющих взламывать криптосистемы.

История криптологии

История криптологии начинается еще с древних времен и продолжается и по сей день.

Криптогра́фия (от др.-греч. κρυπτός «скрытый» + γράφω «пишу») — наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации), аутентификации (проверки подлинности авторства или иных свойств объекта), а также невозможности отказа от авторства.

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

Криптология древности

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

Первый период (приблизительно с III тысячелетия до н. э.) характеризуется господством моноалфавитных шифров (основной метод — замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами).

Второй период (хронологические рамки — с IX века на Ближнем Востоке и с XV века в Европе— до начала XX века) ознаменовался введением в обиход полиалфавитных шифров.

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

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

Древний Египет

Первым известным применением криптографии принято считать использование специальных иероглифов около 4000 лет назад в Древнем Египте. Элементы криптографии обнаружены уже в надписях Старого и Среднего царств, полностью криптографические тексты известны с периода XVIII династии. Иероглифическое письмо, произошедшее от пиктографии, изобиловало идеограммами и, в результате отсутствия огласовки, дало возможность создавать фонограммы в виде ребусов.

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

Скитала

Скитала, также известная как «шифр древней Спарты», также является одним из древнейших криптографических устройств.

Скитала использовалась в войне Спарты против Афин в конце V века до н. э.

Принцип её действия изложил Плутарх (около 45—125 н. э.).

Скитала представляла собой длинный стержень, на который наматывалась лента из пергамента. На ленту наносился текст вдоль оси скиталы, так, что после разматывания текст становился нечитаемым. Для его восстановления требовалась скитала такого же диаметра.

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

Диск Энея

С именем Энея Тактика, полководца IV века до н. э., связывают несколько техник шифрования и тайнописи.

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

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

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

Квадрат Полибия

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

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

Шифр Цезаря

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

Так, в латинском алфавите можем использовать числа от 0 (соответствующего A) до 25 (Z). Обозначая число, соответствующее исходному символу, x, а закодированному - y, можем записать правило применения подстановочного шифра:

y = x + z (mod N)

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

Шифр Цезаря в принятых обозначениях соответствует значению секретного ключа z = 3 (а у Цезаря Августа z = 4). Такие шифры раскрываются чрезвычайно просто даже без знания значения ключа: достаточно знать лишь алгоритм шифрования, а ключ можно подобрать простым перебором (так называемой силовой атакой).

Криптология средних веков

Арабская криптология

С VIII века н. э. развитие криптографии происходит в основном в арабских странах. Считается, что арабский филолог Халиль аль-Фарахиди первым обратил внимание на возможность использования стандартных фраз открытого текста для дешифрования. Он предположил, что первыми словами в письме на греческом языке византийскому императору будут «Во имя Аллаха», что позволило ему прочитать оставшуюся часть сообщения. Позже он написал книгу с описанием данного метода — «Китаб аль-Муамма» («Книга тайного языка»).

В 855 году выходит «Книга о большом стремлении человека разгадать загадки древней письменности» арабского учёного Абу Бакр Ахмед ибн Али Ибн Вахшия ан-Набати, одна из первых книг о криптографии с описаниями нескольких шифров, в том числе с применением нескольких алфавитов. Также к IX веку относится первое известное упоминание о частотном криптоанализе — в книге Ал-Кинди «Манускрипт о дешифровке криптографических сообщений».

В книге X века «Адаб аль-Куттаб» («Руководство для секретарей») ас-Сули есть инструкции по шифрованию записей о налогах, что подтверждает распространение криптографии в обычной, гражданской жизни.

В 1412 году выходит 14-томная энциклопедия Ибн ал-Хаима «Субх ал-Ааша», один из разделов которой «Относительно сокрытия в буквах тайных сообщений» содержал описание семи шифров замены и перестановки, частотного метода криптоанализа, а также таблицы частотности букв в арабском языке на основе текста Корана.

В словарь криптологии арабы внесли такие понятия, как алгоритм и шифр.

 

Индейская криптология

В XVI веке при дипломат. переписке Карла I становится популярным метод nomenclator — указатель географических названий. 11 марта 1532 года Родриго Ниньо, посол в Венеции, использовал его для того, чтобы напомнить императору о некоторых средствах защиты на тот случай, если турецкий султан захочет захватить крепость Клиса в Далмации (около Сплита, Хорватия). Почти 25 лет спустя то же самое сделал маркиз де Мондехар, вице-король Неаполя, чтобы известить Филиппа II о возможных переговорах относительно перемирия между христианами и турками, что стало причиной кризиса имперской разведки в Средиземноморье. Бернардино де Мендоса (1541—1604), посол Испании в Англии и Франции во многих своих письмах использовал метод nomenclator, где особую роль играла замена букв цифрами и шифр из биграмм.

Термин «индейская криптография» («criptografía indiana»), внедрённый исследователем Гильермо Ломанн Вильена (исп. Guillermo Lohmann Villena), применяется для обозначения зашифрованных документов в испанских колониях Америки. Первым известным документом на территории Америки, в котором использовался шифр («caracteres ignotos»), была депеша Христофора Колумба, адресованная Диего Колумбу в 1500 году и перехваченная губернатором Санто-Доминго, Франсиско де Бобадилья.

Свой шифр имел завоеватель Мексики Эрнан Кортес и вице-короли Перу Педро де ла Гаска, Франсиско де Толедо, адмирал Антонио де Агуайо. Испанский Государственный Совет снабдил графа де Чинчон, губернатора Перу с 1629 по 1639 год, новым изобретением в криптографии начала XVII века — указателем индейских географических названий («nomenclator indiano»); одновременно с этим была внедрена новая система — буквы замещались двумя цифрами

Уникальный слоговой шифр иезуитов использован в Тетради Бласа Валера (Куско, 1616); одновременно в документе содержится дешифровка инкских кипу, юпаны, знаков токапу и секес, ключевое значение в кипу и в шифре имел цвет, то он послужил поводом для изобретения в 1749 году метода цветного книгопечатания.

Черные кабинеты

В 1626 году, при осаде города Реальмон, а позже и в 1628 году при осаде Ла-Рошели, французский подданный Антуан Россиньоль (1600—1682) расшифровал перехваченные сообщения и тем самым помог победить армию гугенотов. После победы правительство Франции несколько раз привлекало его к расшифровке шифров. После смерти А. Россиньоля его сын, Бонавентур Россиньоль, а позже и внук, Антуан-Бонавентур Россиньоль, продолжили его дело. В то время правительство Франции привлекало к работе множество криптографов, которые вместе образовывали так называемый «Чёрный кабинет».

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

В России датой учреждения первой государственной шифровальной службы можно считать 1549 год — образование «посольского приказа» с «циферным отделением». А как минимум с 1702 года Петра сопровождала походная посольская канцелярия под руководством первого министра Ф. А. Головина, которая с 1710 года приобрела статус постоянного учреждения. В нём сосредоточилась криптографическая работа с перепиской между Петром, его приближёнными и различными получателями, а также по созданию новых шифров.

Впоследствии над дешифрованием сообщений в России трудились в том числе такие математики, как Кристиан Гольдбах, Леонард Эйлер и Франц Эпинус. При этом во время Семилетней войны (1756—1763) Эйлер, находясь в Пруссии, хотя и продолжал переписываться с высшими лицами Российской империи, также занимался дешифровкой перехваченных писем русских офицеров.

К началу XVIII века подобные кабинеты были по всей Европе, в том числе «Die Geheime Kabinettskanzlei» в Вене, первое дешифровальное отделение в Германии под начальством графа Гронсфельда[1], группа Джона Валлиса в Англии. До, во время и после войны за независимость США они оказались способны вскрыть большую часть колониальных шифров. Большинство из них было закрыто к середине XIX века, по одной из версий — из-за отсутствия вооружённого противостояния с США.

Криптология Руси и России

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

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

Шифры петровской эпохи были шифрами замены, с тем дополнением, что открытый текст письма состоял из частей, написанных на нескольких разных языках. Шифры вручались отбывавшим на миссии дипломатам, командирам крупных военных подразделений. Начиная с 30-х годов XVIII века каждое десятилетие ужесточались требования к шифрам, а последним находились новые применения. Так, с 1730-х годов таблицы замены стали составляться с поправкой на защиту от частотного криптоанализа. В 1740-е годы в России начинают свою работу упомянутые выше чёрные кабинеты. А в 1750-х годах от шифров стали требовать алфавиты мощностью более чем в тысячу символов.

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

В начале XIX века с приходом к власти Александра I вся криптографическая деятельность переходит в ведение Канцелярии Министерства иностранных дел Российской империи. Одним из наиболее значимых достижений ведомства стало дешифрование приказов и переписки Наполеона I во время Отечественной войны 1812 года. Примечательно также, что с 1803 года на службе в Канцелярии находился выдающийся российский ученый П. Л. Шиллинг, которому приписывается изобретение биграммных шифров.

Первая половина XIX века ознаменована изобретением электромагнитного телеграфа П. Л. Шиллингом в 1832 году. Для его безопасного использования был опубликован коммерческий шифр. Появление этого шифра привело к созданию и государственных дипломатических шифров для передачи данных с использованием современных технологий. А созданный примерно в те же годы Цифирный комитет устанавливал сроки действия каждого шифра.

Криптология в современности

С конца 1990-х годов начинается процесс открытого формирования государственных стандартов на криптографические протоколы. Пожалуй, самым известным является начатый в 1997 году конкурс AES, в результате которого в 2000 году государственным стандартом США для криптографии с секретным ключом был принят шифр Rijndael, сейчас уже более известный как AES. Аналогичные инициативы носят названия NESSIE в Европе и CRYPTREC в Японии.

В самих алгоритмах в качестве операций, призванных затруднить линейный и дифференциальный криптоанализ, кроме случайных функций (например, S-блоков, используемых в шифрах DES и ГОСТ) стали использовать более сложные математические конструкции, такие как вычисления в поле Галуа в шифре AES. Принципы выбора алгоритмов (криптографических примитивов) постепенно усложняются. Предъявляются новые требования, часто не имеющие прямого отношения к математике, такие как устойчивость к атакам по сторонним каналам. Для решения задачи защиты информации предлагаются всё новые механизмы, в том числе организационные и законодательные.

Также развиваются принципиально новые направления. На стыке квантовой физики и математики развиваются квантовые вычисления и квантовая криптография. Хотя квантовые компьютеры лишь дело будущего, уже сейчас предложены алгоритмы для взлома существующих «надёжных» систем (например, алгоритм Шора). С другой стороны, используя квантовые эффекты, возможно построить и принципиально новые способы надёжной передачи информации. Активные исследования в этой области идут с конца 1980-х годов.

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

 

 

Алгоритмы

Алгори́тм (лат. al­go­rithmi — от арабского имени математика Аль-Хорезми[1]) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.

Симметричные алгоритмы

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

• отправитель передает получателю ключ (в случае сети с несколькими абонентами у каждой пары абонентов должен быть свой ключ, отличный от ключей других пар);

• отправитель, используя ключ, зашифровывает сообщение, которое пересылается получателю;

• получатель получает сообщение и расшифровывает его.

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

Потоковые шрифты

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

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

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

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

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

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

При использовании генератора ПСЧ возможны несколько вариантов

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

2. Побитовое шифрование потока данных с обратной связью (ОС) по шифртексту. Такая система аналогична предыдущей, за исключением того, что шифртекст возвращается в качестве параметра в генератор ПСЧ. Характерно свойство распространения ошибок. Область распространения ошибки зависит от структуры генератора ПСЧ.

3. Побитовое шифрование потока данных с ОС по исходному тексту. Базой генератора ПСЧ является исходная информация. Характерно свойство неограниченного распространения ошибки.

4. Побитовое шифрование потока данных с ОС по шифртексту и по исходному тексту.

Блочные шрифты

При блочном шифровании информация разбивается на блоки фиксированной длины и шифруется поблочно. Блочные шифры бывают двух основных видов:

• шифры перестановки (transposition, permutation, P-блоки);

• шифры замены (подстановки, substitution, S-блоки).

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

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

• моноалфавитные (код Цезаря);

• полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma).

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

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

В современных криптографических системах, как правило, используют оба способа шифрования (замены и перестановки). Такой шифратор называют составным (product cipher). Oн более стойкий, чем шифратор, использующий только замены или перестановки.

Ассиметричные алгоритмы

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

Схема обмена информацией такова:

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

• отправитель, используя открытый ключ получателя, зашифровывает сообщение, которое пересылается получателю;

• получатель получает сообщение и расшифровывает его, используя свой секретный ключ.

Алгоритм Диффи-Хелмана

Алгоритм Диффи-Хелмана (Whitfield Diffie и Martin Hellman, 1976 год) использует функцию дискретного возведения в степень и похож на метод Эль-Гамаля.

Сначала генерируются два больших простых числа n и q. Эти два числа не обязательно хранить в секрете. Далее один из партнеров P1 генерирует случайное число x и посылает другому участнику будущих обменов P2 значение A = qx mod n

По получении А партнер P2 генерирует случайное число у и посылает P2 вычисленное значение B = qy mod n

Партнер P1, получив В, вычисляет Kx = Bx mod n, а партнер P2 вычисляет Ky = Ay mod n. Алгоритм гарантирует, что числа Ky и Kx равны и могут быть использованы в качестве секретного ключа для шифрования. Ведь даже перехватив числа А и В, трудно вычислить Kx или Ky.

Алгоритм Диффи-Хелмана, обеспечивая конфиденциальность передачи ключа, не может гарантировать того, что он прислан именно тем партнером, который предполагается. Для решения этой проблемы был предложен протокол STS (station-to-station). Этот протокол для идентификации отправителя использует технику электронной подписи. Подпись шифруется общим секретным ключом, после того как он сформирован. Подпись включает в себя идентификаторы как P1, так и P2.

Алгоритм RSA

Разработан в 1977 году в Массачусетском технологическом институте (США). Получил название по первым буквам фамилий авторов (Rivest, Shamir, Adleman). Криптостойкость основана на вычислительной сложности задачи разложения большого числа на простые множители.

Алгоритм RSA предполагает, что посланное закодированное сообщение может быть прочитано адресатом и только им. В этом алгоритме используется два ключа - открытый и секретный. Данный алгоритм привлекателен также в случае, когда большое число субъектов (N) должно общаться по схеме все-со-всеми. В случае симметричной схемы шифрования каждый из субъектов каким-то образом должен доставить свои ключи всем остальным участникам обмена, при этом суммарное число используемых ключей будет достаточно велико при большом значении N. Применение асимметричного алгоритма требует лишь рассылки открытых ключей всеми участниками, суммарное число ключей равно N.

Сообщение представляется в виде числа M. Шифрование осуществляется с помощью общедоступной функции f(M), и только адресату известно, как выполнить операцию f-1. Адресат выбирает два больших простых (prime) числа p и q, которые делает секретными. Он объявляет n=pq и число d, c (d,p-1)=(d,q-1)=1 (один из возможных способов выполнить это условие, выбрать d больше чем p/2 и q/2). Шифрование производится по формуле:

 

f(M) ≡ Md mod n,

 

где M и f(M) оба ≤ n-1. Как было показано, может быть вычислено за разумное время, даже если M, d и n содержит весьма большое число знаков. Адресат вычисляет M на основе Md, используя свое знание p и q. В соответствие со следствием, если

 

dc ≡ (p-1)1, тогда (Md)e ≡ p1.

 

Исходный текст M получается адресатом из зашифрованного F(M) путем преобразования: M = (F(M))e (mod pq). Здесь как исходный текст, так и зашифрованный рассматриваются как длинные двоичные числа.

Аналогично (Md)e ≡ qM, если dc ≡ (q-1)1. e удовлетворяет этим двум условиям, если cd ≡ (p-1) (q-1)1. Теорема 1 гласит, что мы можем позволить e=x, когда x является решением уравнения dx + (p-1)(q-1)y = 1.

Так как (Md)e - M делимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная Md, вычислив его значение в степени e и определив остаток от деления на pq. Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором ~1050 комбинаций. Данная проблема изучается уже около 100 лет. RSA-алгоритм запатентован (20 сентября 1983, действует до 2000 года).

Теоретически можно предположить, что возможно выполнение операции f-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.

Предположим, что мы имеем зашифрованный текст f(M) и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно - надо знать все возможные значения Mi.

Проясним использование алгоритма RSA на конкретном примере. Выбираем два простые числа p=7; q=17 (на практике эти числа во много раз длиннее). В этом случае n = p*q будет равно 119. Теперь необходимо выбрать e, выбираем e=5. Следующий шаг связан с формированием числа d так, чтобы d*e=1 mod [(p-1)(q-1)]. d=77 (использован расширенный алгоритм Эвклида). d - секретный ключ, а e и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать представляется M=19. С = Memod n. Получаем зашифрованный текст C=66. Этот “текст” может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М= Cdmod n и C=66. В результате получается M=19.

На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать адресату. На использовании общедоступных ключей базируется и так называемая электронная подпись, которая позволяет однозначно идентифицировать отправителя. Сходные средства могут применяться для предотвращения внесения каких-либо корректив в сообщение на пути от отправителя к получателю. Быстродействующие аппаратные 512-битовые модули могут обеспечить скорость шифрования на уровне 64 кбит в сек. Готовятся ИС, способные выполнять такие операции со скоростью 1 Мбайт/сек. Разумный выбор параметра e позволяет заметно ускорить реализацию алгоритма.

ELGamal

Разработан в 1985 году. Назван по фамилии автора - Эль-Гамаль. Алгоритм Эль-Гамаля может использоваться для формирования электронной подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется простое число p и два случайных числа g и x, каждое из которых меньше p. Затем вычисляется:

 

y = gx mod p

 

Общедоступными ключами являются y, g и p, а секретным ключом является х. Для подписи сообщения M выбирается случайное число k, которое является простым по отношению к p-1. После этого вычисляется a = gk mod p. Далее из уравнения M = (xa + kb) mod (p-1) находим b. Электронной подписью для сообщения M будет служить пара a и b. Случайное число k следует хранить в секрете. Для верификации подписи необходимо проверить равенство:

 

yaab mod p = gM mod p.

 

Пара a и b представляют собой зашифрованный текст. Следует заметить, что зашифрованный текст имеет размер в два раза больше исходного. Для дешифрования производится вычисление:

 

M = b/ax mod p

Заключение

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

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

• невозможность раскрытия или осмысленной модификации информации на основе анализа ее структуры,

• совершенство используемых протоколов защиты,

• минимальный объем используемой ключевой информации,

• минимальная сложность реализации (в количестве машинных операций), ее стоимость,

• высокая оперативность.

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

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

Литература

1. Водолазский В. Коммерческие системы шифрования: основные алгоритмы и их реализация. Часть 1. // Монитор. - 1992. - N 6-7. - c. 14 - 19.

2. Игнатенко Ю.И. Как сделать так, чтобы?.. // Мир ПК. - 1994. - N 83. Ковалевский В., Максимов В. Криптографические методы. // КомпьютерПресс. - 1993. - N 5. - c. 31 - 34.

4. Мафтик С. Механизмы защиты в сетях ЭВМ. - М.: Мир, 1993.

5. Спесивцев А.В., Вегнер В.А., Крутяков А.Ю. и др. Защита информации в персональных ЭВМ. - M.: Радио и связь, 1992.

6. Сяо Д., Керр Д., Мэдник С. Защита ЭВМ. - М.: Мир, 1982.

7. Шмелева А. Грим - что это? // Hard'н'Soft. - 1994. - N 5.

8. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.

9. https://ru.wikipedia.org/wiki/Алгоритм

10. https://ru.wikipedia.org/wiki/История_криптографии

11. https://ru.wikipedia.org/wiki/Криптография

12. https://sites.google.com/site/anisimovkhv/learning/kripto/lecture/tema2

13. http://www.codenet.ru/progr/alg/enc/1.php

14. https://ru.wikipedia.org/wiki/Криптология

 

Введение

 

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

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

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

Когда только возник интернет, никто не мог гарантировать безопасности ваших данных, а переписки в первых чатах велись в открытых глобальных чатах, где каждый мог прочитать, о чем и с кем вы ведете беседу. Все в интернете было прозрачно.