Lecture 07
.pdf
Введение
Криптография с симметричными ключами базируется на совместном использовании секретного ключа, в то время как асимметричная криптография базируется на персональном ключе
В криптографии с симметричными ключами, символы переставляются или заменяются другими; в асимметричной криптографии числа, представляющие открытые тексты, преобразуются с помощью математических функций
Абонент Е (Ева) – противник, конкурент
Криптоаналитик
Открытый канал связи
Открытый |
Зашифро |
|
|
|
|
Шифро |
Расшифро |
|
Открытый |
||
текст |
вание |
вание |
|
||
текст |
|
текст |
|||
|
|
|
|
||
|
|
|
|
|
|
|
|
|
Закрытый |
|
|
Абонент А (Алиса) - |
|
|
Открытый |
Абонент Б (Боб) - |
|
отправитель |
|
|
получатель |
||
|
|
|
|
||
В ассиметричных системах для зашифровки и расшифровки используются различные (асимметричные) ключи, которые связаны между собой математически и образуют пару
Открытый ключ (public key) может быть известен всем
Закрытый ключ (private key) должен знать только его владелец
Вычислительно легко создавать пару ( открытый ключ, закрытый ключ )
Вычислительно легко, имея открытый ключ и незашифрованное сообщение, создать соответствующее зашифрованное сообщение
Вычислительно легко дешифровать сообщение, используя закрытый ключ
Вычислительно невозможно, зная открытый ключ, определить закрытый ключ
Вычислительно невозможно, зная открытый ключ и зашифрованное сообщение, восстановить исходное сообщение
Шифрующие и дешифрующие функции могут применяться в любом порядке (выполняется не для всех алгоритмов с открытым ключом)
Этот термин ввели Диффи и Хеллман:
Зная х, при любом s легко вычислить y= (x)
По известному значению y и s легко вычислить х= −1( )
Сложно вычислить х= −1 по известному y, если секрет s не известен
Зная подмножество предметов, уложенных в рюкзак, легко подсчитать его суммарный вес, но, зная только вес рюкзака, и веса отдельных предметов непросто определить подмножество предметов в рюкзаке:
( , ) = |
|
× , n – количество предметов |
|
1 |
|
= ( 1, 2, … ) – бинарное представление подмножества предметов ( 1- уложен, 0-оставлен)
B = ( 1, 2, … ) – набор весов предметов
Для произвольного набора чисел задача восстановления X по s является NP-трудной
В частном случае задача имеет полиномиальный алгоритм
решения, когда последовательность ( , |
, … ) является |
|
1 2 |
|
|
супервозрастающей ( superincreasing ): ≥ |
−1 |
|
|
1 |
|
Алгоритм состоит в просмотре списка предметов в порядке убывания их весов и принятия решения для каждого предмета относительно возможности укладки в рюкзак
Возьмем на вооружение этот алгоритм, но только добавим «секрет»:
Выбираем число > |
|
и число , взаимно простое с |
|||
|
|
|
|
1 |
|
Вычисляем |
|
= |
|
mod q |
|
|
|
|
|
|
|
Держим в секрете , и (1, 2, … )
Зная подмножество предметов, уложенных в рюкзак, легко подсчитать его суммарный вес, но, зная только вес рюкзака, и веса отдельных предметов непросто определить подмножество предметов в рюкзаке:
( , ) = |
|
|
× , n – количество предметов |
|
1 |
|
= ( 1, 2, … ) – бинарное представление подмножества предметов ( 1- уложен, 0-оставлен)
= ( 1, 2, … ) – специальный набор весов предметов
Только обладатель секрета , и |
|
, |
, … |
: ≥ |
−1 |
|
|
1 |
2 |
|
|
1 |
|
сможет применить полиномиальный алгоритм для определения подмножества предметов в рюкзаке
Имеем значение функции = |
|
|
× , знаем |
|
1 |
|
(1, 2, … ) и нужно определить 1, 2, …
Находим ′такое, что ′ × ≡ 1 – мультипликативную
инверсию (используем расширенный алгоритм Евклида для решения уравнения ′ × + × = 1)
Вычисляем ′ = (′× )
Можно показать, что ′ = |
|
× |
= |
|
× |
|
1 |
|
|
1 |
|
Окончательно решаем частный случай задачи о рюкзаке с супервозрастающей последовательностью весов предметов