Конспект лекций для студентов, магистров и аспирантов всех специальностей

Вид материала

Конспект

Содержание Существование и единственность абсолютно стойкого шифра. Понятие полиномиального алгоритма. Определение. Алгоритм A называют полиномиальным, если его трудоёмкость T Понятие односторонней функции. Односторонней называется функция f: X  Y, обладающая двумя свойствами 2) не существует полиномиального алгоритма инвертирования функции f (т.е. решения уравнения f(x)=y относительно x). Однако, существование односторонних функций (2008) пока не доказано!! Протокол выработки общего ключа удалёнными абонентами.

Подобный материал:

• Конспект лекций бурлачков в. К., д э. н., проф. Москва, 1213.67kb.
• Конспект лекций для студентов всех специальностей дневной и заочной формы обучения, 1439.07kb.
• Курс лекций (для магистров всех специальностей Академии) харьков − 2006, 1136.42kb.
• Конспект лекций по курсу основы алгоритмизации и программирования для студентов всех, 3059.86kb.
• Конспект лекций по курсу Начертательная геометрия (для студентов заочной формы обучения, 1032.28kb.
• Конспект лекций для студентов по специальности i-25 01 08 «Бухгалтерский учет, анализ, 2183.7kb.
• Конспект лекций по курсу "Начертательная геометрия и инженерная графика" Кемерово 2002, 786.75kb.
• Конспект лекций по дисциплине «Маркетинг», 487.79kb.
• Конспект лекций для студентов специальности 080110 «Экономика и бухгалтерский учет, 1420.65kb.
• Конспект лекций по культурологии Для студентов всех специальностей, 4611.53kb.

Лекция 5

^ Существование и единственность абсолютно стойкого шифра.


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

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

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


y _i =x _i  k _i , i = 1,2, ... n ,


где x ₁ x ₂ .... x _n - открытый текст , k ₁ k ₂...k _n - ключ, y ₁ y ₂ ... y _n - шифрованный текст. Подчеркнём, что для абсолютной стойкости существенным является каждое из следующих требований к ленте однократного использования:

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

2) равенство длины ключа и длины открытого текста;

4. однократность использования ключа.
   

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

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

Далее переходим к понятиям, связанным с оценкой сложности вычислений (алгоритмов).


^ Понятие полиномиального алгоритма.


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


^ Определение. Алгоритм A называют полиномиальным, если его трудоёмкость T_A ограничена полиномом от длины записи исходных данных, то-есть существует константа c > 0 и натуральное число k такие, что T_A  cL^k , где L - длина записи исходных данных.


Примеры. Рассмотрим систему линейных алгебраических уравнений Ax = b, где A – квадратная матрица произвольного порядка n x n.

Обозначим буквой N число операций, необходимое для решения системы. Из курса информатики известно, что если решать эту систему методом Крамера, то N=O (n!), а если методом Гаусса, то

N= O (n ³). Таким образом, алгоритм Крамера - неполиномиальный, а алгоритм Гаусса - полиномиальный.


^ Понятие односторонней функции.

В 1976 году была опубликована работа молодых американских математиков У. Диффи и М. Э. Хеллмана «Новые направления в криптографии», которая существенно изменила криптографию.

У. Диффи и М. Э. Хеллман предложили принципиально новую идею создания систем открытого шифрования. Центральным понятием «новой криптографии» является понятие односторонней функции (One-way trap-door function).


^ Односторонней называется функция f: X  Y, обладающая двумя свойствами:

1) существует полиномиальный алгоритм вычисления значений f(x).

^ 2) не существует полиномиального алгоритма инвертирования функции f (т.е. решения уравнения f(x)=y относительно x).

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


^ Однако, существование односторонних функций (2008) пока не доказано!!

Односторонняя функция Диффи и Хеллмана.


Диффи и Хеллман предложили функцию:


f(x)=a ^x ( mod p ),


где p –простое число достаточно большой длины, x - произвольное натуральное число, а число a подбирается специальным образом. При некоторых условиях на эти числа (об этом ниже) отображение f будет взаимно однозначным. Общепризнанно, что инвертирование функции f (решение уравнения y=a ^x (mod p) относительно x, т. е. вычисление дискретного логарифма) является трудной математической задачей (в настоящее время (2008) не известен полиномиальный алгоритм её решения).

Рассмотрим идею открытого шифрования на простейшем примере протокола выработки общего ключа удалёнными абонентами.


^ Протокол выработки общего ключа удалёнными абонентами.


Абоненты A и B независимо друг от друга выбирают по произвольному натуральному числу – скажем x _A и x _B . Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:


x _A x _B

y _A = a (mod p) , y _B = a (mod p)


(числа a и p считаются общедоступными, например, помещаются на открытом сервере). Потом абоненты A и B обмениваются этими элементами по открытому каналу связи. Теперь абонент A, получив

y _B и зная свой секретный элемент x _A , вычисляет новый элемент:


x _A x _B x _A (x _B x _A)

(y _B ) (mod p) = (a ) (mod p) = a (mod p)


Аналогично поступает абонент B:


x _B x _A x _B (x _A x _B )

(y _A) (mod p) = (a ) (mod p) = a (mod p)


Тем самым у абонентов A и B появился общий элемент, равный

(x _A x _B) (x _B x _A)

a (mod p) = a (mod p). Этот элемент и объявляется общим ключом абонентов A и B.


x _A x _B

Из описания видно, что противник знает p, a, a _, a , не знает x _A

(x _A x _B)

и x _B и хочет узнать a . В настоящее время (2008) нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это трудная математическая задача, не сводящаяся к полиномиальному алгоритму.

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

Для работы с большими целыми числами разработаны специальные алгоритмические языки UBASIC и PARI.


Лекция 6.