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

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

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

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

191 691 573 337 365 730 651 493 177 354

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

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