Шпаргалка по "Информатике и ИТ"

1) проблема факторизации (разложение больших чисел на простые);

2) проблема дискретного  логарифма y=a^b mod c (как найти b при известных y, a, c).

Современые криптографические  системы делятся на:

1) симметричные;

2) асимметричные.

 

 

 

 

 

 

22 Классификация методов шифрования  данных

Классификация шифров.

По принципу размещения символов в шифре:

1) подстановочные (зашифр. слово х_n строится на осн. подстановки; наи> известн. — шифр Цезаря (универсален и осн. на циклическом перемещ. 2 или 1 символов вправо или влево; сдвиг меняет шифр. Моношифр — на входе и на выходе исп-ся 1 алфавит. Особ-ть: главн. уязвимость алфавита не меняется, т.е. статистич. св-ва сообщ. не измен-ся. На учёте этих осн. построены системы криптоанализа таких шифров));

2) перестановочные (шифр созд-ся на осн. тех же символов, но переставл. местами; в криптографии сообщение х_к — открытый txt, х_n — шифрограмма (защифр. txt), метод перестановки наз. шифром);

3) комбинир. (подстановочно-перестановочн.) (все современ. шифры — такие).

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

1) симметричн. . В прям. и обратн. преобраз. (зашифр./ расшифр.) используется одинаковый ключ. Ключ является тайным. Алгоритм известен.

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

М = 10101100   К = 0101 (тайная информация) Т.к. длина блока 4, то К тоже 4.

Зашифрование:

Сообщение М делим на блоки  в соотв. С принятой длиной m1 = 1010, m2 = 1100.

C = f (алгоритм, К, М) – шифртекст (шифрограмма), справедливо для любой криптограф. системы.

При использовании блочного алгоритма шифрования текста С = с₁…с_l

В нашем случае С= с1с2

с1 = m1 + К = 1010+0101=1111 (!!! Здесь и до конца шпоры + это сложение по mod 2).

с2 = m2 + К = 1100+0101=1001

С = 11111001 такой шифртекст по открытым каналам поступает к получателю.

Обратное преобразование (расшифрование):

 M’ = f (C, K, алгоритм)       M’ = m1’m2’

m1’ = c1 + K = 1111+0101=1010= m1

m2’ = c2 + K = 1001+0101=1100= m2

M’ = 10101100 = M

В реальн. системах помимо вычислит. операций исп-ся множествен. подстановки и перестановки. Наи> известн. и 1 из стандартизован. — стандарт шифрования данных DES, принят в США и позднее исп-ся во всем мире. Длина ключа = 64 bit из кот. 54 вычислительных, 8 — биты чётности (CRC). Особ-ти этой системы: 1) хранение/ обмен ключами; 2) «+» сравнит-но не > длина ключа; вычисл. производ-ся быстрее, т.к. не > длина ключа; 3) «-» при < длине ключа проще его найти хотя бы методом простого перебора.

2) асимметр.  Системы предполагают, что при прям. и обратн. преобраз. исп-ся различн. ключи, взаимосвязан. м-у собой по известн. законам. Известный метод RSA.

С учетом принципа формирования шифр-текста:

1) блочное шифрование (сообщение М делится на блоки одинаковой длины и преобразованию подлежат все символы в блоке одновременно);

2) поточное шифрование (по очереди шифруется каждый бит сообщения).

 

 

 

 

 

 

 

 

 

23 Особенности блокового шифрования  данных

Блочное шифрование (сообщение М делится на блоки одинаковой длины и преобразованию подлежат все символы в блоке одновременно).

Алгоритм DES.

DES – Data Encryption Standard (первый международный стандарт) – стандарт шифрования данных.

DES – блочный алгоритм (64-битовый блок). Длина ключа – 56 бит (из 64 бит – 8 бит четности). Базовые методы: подстановка и перестановка данных.

1 подстан. + 1 перестан. = 1 раунд  (цикл)

Алгоритм состоит из 16 раундов, т.е. 1 блок данных длиной 64 бита обрабатывается 16 раз, в каждом из которых  используется новый ключ: в каждом раунде биты ключа сдвигаются, затем  из 56 бит выбирается 48 бит.

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

Преобразование должно использовать следующие принципы:

- Рассеивание (diffusion) — то есть изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;

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

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

24 Особенности симметричных и ассиметрич. систем шифрования данных

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

1) симметричн. В прям. и обратн. преобраз. (зашифр./ расшифр.) используется одинаковый ключ. Ключ является тайным. Алгоритм известен.

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

М = 10101100      К = 0101 (тайная информация) Т.к. длина блока 4, то К тоже 4.

Зашифрование:

Сообщение М делим на блоки  в соотв. С принятой длиной m1 = 1010, m2 = 1100.

C = f (алгоритм, К, М) – шифртекст (шифрограмма), справедливо для любой криптограф. системы.

При использовании блочного алгоритма шифрования текста С = с₁…с_l

В нашем случае С= с1с2

с1 = m1 + К = 1010+0101=1111 (!!! Здесь и до конца шпоры + это сложение по mod 2).

с2 = m2 + К = 1100+0101=1001

С = 11111001 такой шифртекст по открытым каналам поступает к получателю.

Обратное  преобразование (расшифрование):

 M’ = f (C, K, алгоритм)

M’ = m1’m2’

m1’ = c1 + K = 1111+0101=1010= m1

m2’ = c2 + K = 1001+0101=1100= m2

M’ = 10101100 = M

В реальн. системах помимо вычислит. операций исп-ся множествен. подстановки и перестановки. Наи> известн. и 1 из стандартизован. — стандарт. DES, принят в США и позднее исп-ся во всем мире. Длина ключа = 64 bit из кот. 54 вычислительных, 8 — биты чётности (CRC). Особ-ти этой системы: 1) хранение/ обмен ключами; 2) «+» сравнит-но не > длина ключа; вычисл. производ-ся быстрее, т.к. не > длина ключа; 3) «-» при < длине ключа проще его найти хотя бы методом простого перебора.

2) асимметр. Системы предполагают, что при прям. и обратн. преобраз. исп-ся различн. ключи, взаимосвязан. м-у собой по известн. законам. Известный метод RSA.

Криптографическая система шифрования данных RSA (1978 г.) является одной из первых практически реализованных идей Диффи и Хеллмана. RSA предполагает, что каждый пользователь независимо от других пользователей генерирует свои собственные ключи (тайный и публичный): тайный известен только пользователям, публичный – общедоступен.

В RSA n представляет собой составное число , числа p и q – большие целые простые (примерно одного порядка), n – открытое число, p и q – тайные.

Задача злоумышленника – разложить n (известное) на простые сомножители.

Система предполаг., что кажд. пользователь может независ. создать  свой ключ.

Математической  основой системы является теорема:

Для целых чисел e и d, удовлетворяющих соотношению e*d mod =1, где

1) (ф-ция Эйлера) и M (сообщение) должны быть взаимно простыми;

2) должны быть взаимно  простыми пары чисел e и n, d и n;

выполняется равенство (M^e mod n) ^d mod n = M.

Процедура генерации (создания) ключа:

1. Выбрать сопоставимые по величине 2 простых числа p и q.

2. Вычислить (n является открытым числом).

3. Вычислить функцию Эйлера [определяет количество целых положительных чисел, меньших n и взаимно простых с n; n>1; если n – простое число, то ; если , где p и q – простые числа, то ]:

( является закрытым числом).

4. Случайным образом выбирается число e (или d), которое должно быть взаимно простым с .

5. Вычисляется мультипликативное инверсное значение к величине, определенной в п. 4 в соответствии со следующими формулами:

    

Если в п. 4 выбрано e, то в п. 5 используют соотношение: .

Принято считать, что пара (e,n) – открытый ключ пользователя, а число d – закрытый ключ (d,n).

Пример1: 1. Пусть p = 3, q = 7.

2. Тогда  .

3. Вычисляем  .

4. Выбираем e = 17 (взаимно простое с 12).

5. Решаем уравнение  или .

Открытый ключ: (17,21); закрытый: (5) или (5,21).

А отправляет сообщение В. Используются ключи получателя В и при зашифровании и при расшифровании. e и n – общедоступны и находятся на специализированных сайтах.

Действия А:   1. Создание шифр-текста: .

Если М поделено на блоки  одинаковой длины (m¹, m², …, m^L), то С = с¹, с², …, с^L, где .

2. Отправка на адрес В шифр-текста С.

Действия В:   1. Получение: С = с¹, с², …, с^L.

2. Расшифрование:

В использует соответствующий тайный ключ d.

Если сообщение разделено  на блоки: .

Пример2: Открытый ключ: (17,21); закрытый: (5,21). Предполагается, что сообщение М состоит из 5 символов.

Сообщение М делится на блоки одинаковой длины по одному символу.

Пусть М = 12345 и m¹ = 01, m² = 02, …, m⁵ = 05.

Процедура зашифрования:

, , ,

, .

Шифр-текст: С = 01 11 12 16 17.

Процедура расшифрования:

, , ,

, .                      Имеем: М = 12345. 

25 Подстановочные и перестановочные  шифры

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

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

Пример моноалфавитного  шифра – шифр Цезаря: символы исходного алфавита заменяются символами того же алфавита со сдвигом на 3 символа вправо: «A» меняется на «D», «B» – на «E», «W» – на «Z», «X» – на «A» и т. д. (в некоторых случаях во внимание принимается 27-й символ – пробел). Для расшифрования необходимо выполнить обратную замену.

Пример1.

Имеем открытый текст М = «cade». На основе шифра Цезаря  С = «gdqh».

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

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

Пример2.

М = «ИНФОРМАТИКА». Запишем этот текст как показано левее.

и	н	ф
о	р	м
а	т	и
к	а

Считывание по столбцам снизу вверх приводит к  такому шифр-тексту: С = «КАОИАТРН_ИМФ».

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

 

Пример3.

Открытый текст М = «ВАСЯ_ЛЮБИТ_МАШУ», а запишем его так, как показано на рис. ниже.

Осуществляя считывания по уровням, начиная с верхнего, получим  следующий шифртекст: С = «СЮ_УАЯЛБТМШВ_ИА».

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

26. Особенности алгоритма RSA

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