Реализация зашифрования/расшифрования произвольного двоичного файла с использованием шифра М-ичного гаммирования при М=28

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ  УКРАИНЫ

Харьковский национальный университет  радиоэлектроники

 

Факультет Компьютерной инженерии  и управления

Кафедра Безопасности информационных технологий

 

 

 

 

 

КУРСОВАЯ РАБОТА

по предмету «Технологии  программирования» на тему:

РЕАЛИЗАЦИЯ ЗАШИФРОВАНИЯ/РАСШИФРОВАНИЯ  ПРОИЗВОЛЬНОГО ДВОИЧНОГО ФАЙЛА  С ИСПОЛЬЗОВАНИЕМ ШИФРА М-ИЧНОГО ГАММИРОВАНИЯ ПРИ М=28

 

 

 

Выполнил:

студент І курса 

группы БИКС-11-2

Лозовой Алексей

Научный руководитель:

 

 

 

 

Харьков-2011

РЕФЕРАТ

 

 

Курсовая работа содержит 19 страницы, 1 рисунок, 1 приложение, 6 источников.

Объектом исследования являются методы шифрования

Предмет исследования – шифрование данных с использованием шифра двоичного гаммирования

Основная цель состоит  в написании программы, выполняющей зашифрование/расшифрование произвольного двоичного файла с использованием шифра шифра m- ичного гаммирования при m = 28.

 ГАММИРОВАНИЕ, ШИФРОВАНИЕ, ДВОИЧНЫЙ ФАЙЛ, ФОРМИРОВАНИЕ КЛЮЧЕВЫХ  ДАННЫХ,  ЛРР.  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

 

ВСТУПЛЕНИЕ……………………………………………………………………

1 РАССМОТРЕНИЕ ТЕОРЕТИЧЕСКИХ ОСНОВ ШИФРОВАНИЯ ..............

    1. Шифры. Их виды и свойства…………………………………………..

1.1.1Симметричные криптографические  системы…………….…..

1.1.2Ассимметричные криптографические системы…….……..….

1.2  Гаммирование …………………………………………………………..

1.2.1 Метод гаммирования.…………………………………………..

1.2.2 Основные свойства ЛРР и ЛРПМ………………………………

2  ОПИСАНИЕ ПРОГРАММНОЙ МОДЕЛИ ШИФРОВАНИЯ....................... 

ВЫВОДЫ…………………………………………………………………………

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ …….. ……………………...

ПРИЛОЖЕНИЕ А………………………………………………………………...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВСТУПЛЕНИЕ

 

 

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

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

В истории развития криптографии выделены три периода:

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

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

Третий период имеет свое начало с появлением работ У.Диффи и М.Хелмана "Новые направления в криптографии" (1976), "Защищенность и имитостойкость: введение в криптографию" (1979), которые показали возможности организации секретной связи без предварительной передачи секретного ключа (ключа дешифрования).

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

В нашей работе будет подробнее рассмотрена одна  из широко применяемых систем криптографического  преобразования  - гаммирование.

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

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

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

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

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

История этого шифра достаточно давняя. Алгоритм, положенный в его  основу (схема однократного использования), чаще всего связывают с именем инженера американской компании ат&т Г.С. Вернама. В 1917 году он опубликовал замечательную систему побитового  шифрования открытого текста, представленного в коде Бодо, когда каждый бит преобразуется с использованием соответствующего ему бита ключа по следующему алгоритму:

, , , .

Это так называемое сложение по модулю два ("XOR"). Расшифрование осуществляется той же операцией, что очень удобно для реализации. Вернам предлагал использовать ключ только один раз (one - time pad), несмотря на трудности передачи по секретному каналу этого ключа, длина которого равна длине шифруемого открытого текста. Однако это дает, как показал впоследствии К.Шеннон, действительно нераскрываемый шифр.

Таким образом формируется n-разрядная случайная двоичная последовательность — ключ шифра, известный отправителю и получателю сообщения. Отправитель производит побитовое сложение по модулю два ключа.

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

 

 

 

1 РАССМОТРЕНИЕ ТЕОРЕТИЧЕСКИХ ОСНОВ  ШИФРОВАНИЯ 

 

 

1.1 Шифры, их виды и свойства

 

Шифр – это совокупность инъективных отображений множества  открытых текстов во множество шифрованных  текстов, проиндексированная элементами из множества ключей: {Fk : X → S, K ∈ K}.

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

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

В криптографии криптографические  системы (или шифры) классифицируются следующим образом:

1) симметричные криптосистемы

2) асимметричные криптосистемы

 

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

 

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

  1. Моно - и многоалфавитные подстановки.

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

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

3) Блочные шифры - семейство обратимых преобразований блоков (частей фиксированной длины) исходного текста. Фактически блочный шифр - это система подстановки на алфавите блоков. Она может быть моно - или многоалфавитной в зависимости от режима блочного шифра. Иначе говоря, при блочном шифровании информация разбивается на блоки фиксированной длины и шифруется поблочно. Блочные шифры бывают двух основных видов: шифры перестановки (transposition, permutation, P-блоки) и шифры замены (подстановки, substitution, S-блоки) 5. В настоящее время блочные шифры наиболее распространены на практике.

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

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

 

1.1.2 Асcимметричные криптографические системы

 

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

 

    1. Гаммирование

 

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

 

      1. Метод гаммирования

 

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

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

- символы исходного текста  и гамма представляются в двоичном  коде и располагаются один  под другим;

- каждая пара двоичных  знаков заменяется одним двоичным  знаком шифрованного текста в  соответствии с принятым алгоритмом;

- полученная последовательность  двоичных знаков шифрованного  текста заменяется символами  алфавита в соответствии с  выбранным кодом.

Таким образом, букву надо представить целым числом, а целое  число затем перевести в двоичную систему.

Псевдослучайная двоичная последовательность(ПСДП) генерируется при помощи линейного  рекуррентного регистра(ЛРР).

Линейный рекуррентный регистр строится на основе линейных рекуррентных соотношений.

ЛРР представляет собой сдвиговый  регистр с линейными обратными  связями (его структурная схема  представлена на рисунке 1), в котором  входной сигнал образуется в результате сложения по модулю 2 нескольких фиксированных  разрядов. В результате образуется выходной сигнал в виде ПСП «0»  и «1». Он обладает интересным свойством: по происшествии некоторого времени, определяемого  длиной регистра, он в точности повторяется (регистр максимальной длины n перед  повторением проходит через 2n-1 состояний). Т.е. образуются циклические или  кольцевые ПСДП.

 

Рис. 2.1 – Cтруктурная схема ЛРР

 
Очередное значение, формируемое на выходе ЛРР, вычисляется по формуле

                                                             (2.1) 
где - операция вычисления суммы по модулю 2 
- состояние j -го бита ЛРР 
- коэффициент обратной связи. 
При этом для двоичного ЛРР . 
Каждому линейному рекуррентному регистру длиной n разрядов можно сопоставить полином обратных связей h(x) с двоичными коэффициентами вида: 
                                       
причем обязательно . 
 
Если полином h(x) - примитивный, то длина последовательности, генерируемой ЛРР, максимальна и равна: 
.

Такая последовательность называется последовательностью максимальной длины для сдвигового регистра. Питерсон и Уэлдон показали, что при любом целом существует n-битовая последовательность MLSRS с периодом .

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

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

- нелинейную логику и  фильтрацию содержимого регистра

- ЛРР с переменным шагом

- ЛРР со сжатием

 

      1. Основные свойства ЛРР и ЛРПМ (на периоде)

 

  1. Функционирование ЛРР однозначно определяется используемым образующим полиномом f (t) :

f (t) = c m × t m + c m – 1 × t m - 1 + . . . + c 2 × t 2 + c 1 × t 1 + 1 ,     f (t) Î Z 2 [t ] . (2.2)

Здесь m ¾ степень полинома (deg(f (t)));

ci  ¾ коэффициенты ci Î{0, 1}, c0 = 1.

  1. Период ЛРПМ (линейной рекуррентной последовательности максимального периода) T = 2 m – 1.

ЛРПМ может быть получена только при использовании примитивного образующего полинома f (t) . В противном случае период формируемой последовательности будет заведомо меньшим.

  1. Расстояние единственности l 0 = 2 × m .

То есть закон функционирования ЛРР (вид образующего полинома) может  быть однозначно восстановлен по 2×m безошибочно полученным подряд расположенным битам ЛРПМ. Это и следующее (связанное с ним) свойство являются основными недостатками ЛРР, из – за которых они не могут использоваться в изолированном виде в качестве ГКП.

  1. Структурная скрытность Sc = l 0 / T = 2×m / (2 m – 1 ) .

То есть структурная скрытность для ЛРР достаточно низкая ¾ закон функционирования ЛРР легко раскрываем.

  1. Количество нулей (на периоде ЛРПМ) на один меньше количества единиц: N0 = 2 m – 1 – 1 и N1 = 2 m – 1 соответственно.
  2. Длина максимальной серии из единиц ¾ m, из нулей ¾ (m - 1).
  3. Свойства псевдослучайности:  из общего количества серий на периоде ЛРПМ

1 / 2 всех длин имеют длину 1;

1 / 4 ¾ длину 2;     

. . . 

1 / 2 k ¾ длину k.

  1. На периоде ЛРПМ по одному разу встречаются все m – разрядные комбинации от 1 до 2 m – 1  (свойство “окна”).
  2. Количество изоморфизмов ЛРПМ N И = j (T ) / m  (здесь j (T ) ¾ значение функции Эйлера) .

То есть для данной степени m существует N И примитивных полиномов и, соответственно, N И ЛРПМ, отличающихся тонкой структурой и не являющихся циклическими сдвигами друг относительно друга.

  1. Сумма двух ЛРПМ, отличающихся только циклическим сдвигом, также является ЛРПМ, отличающейся от двух исходных только циклическим сдвигом.

То есть комбинирование (линейное) нескольких отрезков одной и той  же ЛРПМ не дает увеличения структурной  скрытности.

В качестве начального содержимого  регистра ¾ битов (S m - 1 , S m - 2 , …, S 1 , S 0 ) 2 ¾ задается случайный (псевдослучайный) двоичный m - разрядный вектор (запрещенной является только нулевая комбинация).

Бит обратной связи ЛРР (в  соответствии с (2.2)) формируется согласно следующему соотношению:

                                                                                (2.3)

где Sj ¾ содержимое ячеек регистра;

ci ¾ коэффициенты образующего полинома (причем c 0 = 1).

 

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

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

 

 

 

 

 

 

ВЫВОДЫ

 

 

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

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

2. Наиболее широко гаммирование используется при шифровании сообщений в двоичном коде. В этом случае легко реализуется устройство, генерирующее ключ. Оно будет представлять собой регистр сдвига с обратными связями. Соответствующий выбор с обратной связью позволяет генерировать двоичные послед, периодичность повторения которых будет составлять (2^n)-1, где n число разрядов регистра. Такие последовательности называют псевдослучайными. Принцип шифрования гаммирования будет заключаться в генерации гамма шифра с помощью датчика псевдослучайных чисел и наложения полученной суммы на открытые данные, например использования сложения по модулю 2.

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

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

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

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

6. Симметричное шифрование было  введено в системы обработки информации в нашей стране в 1990 году. Оно также входит в стандарты СНГ. Метод шифрования с гаммированием, выполняет функции поточного шифроалгоритма  при криптографической защите и криптографическом преобразовании.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

 

1.Асосков В.В., Иванов М.А.  Поточные шифры. М., Кудиц-образ, 2003, 336 с.

2.Герасименко ВА, Малюк  А.А. Основы защиты информации. М., МГИФИ, 1997, 352с.

3.Кон П.И. Универсальная  алгебра. М., Мир, 1968,  412с.

4. Коробейников А.Г. Математические  основы криптографии. Учебное                пособие. СПБ, ГИТМО, 2002, 478с.

5.Мельников В.В. Защита  информации в компьютерных системах. М., Финансы и статистика, 1997, N 9, с.13 – 18.

6. Шнайер Б.В. Прикладная  криптография. М., Триумф, 2002, 816с.


Реализация зашифрования/расшифрования произвольного двоичного файла с использованием шифра М-ичного гаммирования при М=28