Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17




НазваниеСодержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17
страница77/78
Дата конвертации11.12.2012
Размер5.58 Mb.
ТипРеферат
1   ...   70   71   72   73   74   75   76   77   78

Шифрование с открытым ключом


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

Шифрование при помощи задачи о ранце


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

191 691 573 337 365 730 651 493 177 354

так, чтобы их сумма была равна 2063.

Наиболее известный способ решения задачи о ранце заключается в последовательной проверке всех возможных комбинаций чисел, пока не будет найдено решение. Но если в списке п значений, проверить придется 2" комбинаций. Поэтому, если только нам не посчастливится найти правильную комбинацию в начале поиска, время, необходимое для решения, будет очень большим. Чтобы самостоятельно понять эту особенность, попробуйте решить приведенную ранее задачу о ранце. Вы обнаружите, что это займет много времени, хотя список состоит всего из 10 значений. Представьте свое замешательство, если вам будет дано 20 значений, то есть более миллиона комбинаций для проверки.

Популярные системы шифрования


Одна из наиболее популярных систем шифрования, используемая для безопасной передачи данных в Интернете, — это PGP (Pretty Good Privacy), которую разработал Филипп Циммерман в 1991 году. PGP — простая в использовании система шифрования общего назначения с открытым ключом, бесплатно распространяемая в Интернете для некоммерческого использования. Алгоритм, на основе которого разработана PGP, — это RSA, названный в честь его создателей: Рона Райвеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Адлемана (Leonard Adleman). В отличие от систем шифрования, основанных на сложности решения задачи о ранце, которые мы обсуждаем в этом разделе, RSA основана на сложности поиска множителей больших целых чисел.

RSA является примером того, как патентное право и государственное регулирование влияют на распространение программного обеспечения. Действительно, за RSA велось множество патентных битв, и правительство США продолжает ограничивать ее распространение. Подробнее об этой грандиозной эпопее вы можете узнать, найдя соответствующие документы в Сети. Для начала советую вам поискать узлы, посвященные PGP и RSA.

Задачу о ранце на основе приведенного выше списка можно применять для шифрования сообщений следующим образом: сначала представим сообщение в виде строки битов, возможно, используя ASCII или Unicode. Затем разобьем эту строку на сегменты по 10 битов и представим каждый 10-битовый сегмент в виде одного числа. Это число получается путем сложения значений из списка, занимающих места, соответствующие позициям единиц в 10-битовом сегменте. Например, 10-битовый сегмент 1ОО11О0ОО1 будет представлен числом 1247 (рис. 11.8): единицы в сегменте находятся на первой, четвертой, пятой и десятой позиции, а сумма соответствующих значений в списке (191, 337, 365 и 354) равна 1247. Аналогично, комбинация 0010011010 будет представлена числом 2131 (573 + 730 + + 651 + 177). Сообщение 1001100001001О011010 будет зашифровано последовательностью из двух чисел: 1247 и 2131.



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

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

Чтобы получить эту хитрость, заметим, что некоторые задачи о ранце решаются легко. Предположим, что список состоит из следующих значений: 1 4 6 12 24 51 105 210 421 850

Каждое число в списке больше суммы всех предшествующих чисел. Поэтому, если нам необходимо выбрать набор значений, сумма которых равна 995, мы будем точно знать, что одно из требуемых значений — это 850, так как сумма всех остальных значений будет слишком мала. Сделав этот выбор, мы сократим задачу до выбора чисел, сумма которых равна 995 - 850, то есть 145. Но это означает, что нужно обязательно выбрать 105, так как это самое близкое к искомому меньшее значение. Продолжая размышлять подобным образом, мы быстро сделаем вывод, что нужные нам значения — это 850, 105, 24, 12 и 4.

А теперь финальный аккорд: существует способ преобразования подобных простых задач о ранце в сложные задачи и обратно. Рассмотрим процесс преобразования в терминах трех «волшебных» чисел. Позже мы узнаем, откуда берутся эти волшебные числа и как построить собственную систему шифрования. Наши волшебные числа — это 642, 2311 и 18.

Первый шаг — преобразовать список

1 4 6 12 25 51 105 210 421 850

при помощи которого конструируется простая задача о ранце, в другой список, соответствующий более сложной задаче. Мы сделаем это, умножив каждое число из списка на 642 (первое магическое число) и записав остатки от деления произведений на 2311 (второе магическое число). В итоге получим список

642 257 1541 771 2184 388 391 782 2206 304

В частности, вместо значения 4 из исходного списка теперь стоит 257, так как 4 х 642 = 2568, а остаток от деления 2568 на 2311 равен 257.

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

Например, наша задача — выбрать значения из списка

642 257 1541 771 2184 388 391 782 2206 304

сумма которых равна 4895. Сначала умножаем 4895 х 18 = 88 ПО, затем делим 88 110 на 2311, остаток равен 292. Затем определяем, что значения 6, 25, 51 и 210 — это значения из списка

1 4 6 12 25 51 105 210 421 850

дающие в сумме 292. Так как это третье, пятое, шестое и восьмое значения в соответствующем списке, делаем вывод, что третье, пятое, шестое и восьмое числа в списке

642 257 1541 771 2184 388 391 782 2206 304

дают в сумме 4895. Действительно, 1541 + 2184 + 388 + 782 - 4895, что и требовалось.

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

642 257 1541 771 2184 388 391 782 2206 304

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


1   ...   70   71   72   73   74   75   76   77   78

Похожие:

Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconОсновы работы с Sharepoint в какое место веб-страницы разрешается вставить новую веб-часть (в браузере)?
В какое представление веб-страницы будут вноситься изменения, если выбрать команду Настроить эту страницу?
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВведение в физику и технологию элементной базы ЭВМ и компьютеров
Введение   8
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСодержание
Содержание размещают после титульного листа отчёта (как правило, на стр. 2). Слово «Содержание» рас­полагают посередине страницы...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconСоздание веб-страницы в простом текстовом редакторе
Давайте создадим  веб-страницу. Для этого нужно напечатать ее исходный код в простом текстовом редакторе  блокнот
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЗагрузка uploading теория
После того как набор html страниц веб-сайта создан. Все они связаны между собой с помощью ссылок. Страницы наполнены контентом. Таким...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЛитература 153 Алфавитный указатель 155 Предисловие редактора русского издания Глубокоуважаемые коллеги! Содержа­ние этой книги значительно шире и глуб­же, нежели заявлено в ее названии. Я бы назвала ее «Лечение и реставрация молочных зубов»
Предисловие редактора русского издания 6 Введение 9 Предисловие 11 Благодарности 13
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 icon        Информатика  Системы счисления и  арифметические основы эвм  
Введение   
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconЯндекс - поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости, картинки, статьи
Яндекс — поисковая машина, способная по вашему запросу найти в русскоязычной части интернета наиболее подходящие веб-страницы, новости,...
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Содержание предисловие 2 веб-страницы 3 введение 6 1архитектура ЭВМ 17 iconВзаимодействие веб-сайтов по культуре с пользователем. 
Предисловие к русскому изданию   4 
Разместите кнопку на своём сайте:
kak.znate.ru


База данных защищена авторским правом ©kak.znate.ru 2012
обратиться к администрации
KakZnate
Главная страница