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

Одна из наиболее популярных систем шифрования, используемая для безопасной передачи данных в Интернете, — это 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).

Модульная арифметика

Описанная система шифрования с открытым ключом основана на математической концепции, известной как модульная арифметика (modular arithmetic), или модульная система. Эта система получается путем замены каждого целого числа из традиционной арифметической системы остатком, образующимся при делении этого числа на предопределенное значение. Предопределенное значение называется модулем. Например, пусть модуль равен 7, тогда целые значения О 1 2 3 4 5 6 7 8 9... будут преобразованы в значения О 1 2 3 4 5 6 0 1 2...

Для обозначения остатка, полученного при делении х на т, обычно используется сокращение х (mod m), которое читается как «х по модулю от» или иногда просто «к модуль от». Так, 9 (mod 7) равно 2, так как остаток от деления 9 на 7 равен 2. Аналогично, 24 (mod 7) равно 3, потому что при делении 24 на 7 получается остаток 3; а 5 (mod 7) равно 5.

Два целых числа, которые при делении на т дают одинаковый остаток, называются эквивалентными по модулю т. Так, 16 и 23 эквивалентны по модулю 7, так как 16 (mod 7) = 23 (mod 7). Действительно, при делении на 7 и значение 16, и 23 дают остаток 2. Для обозначения того, что значение х эквивалентно у по модулю т часто используется сокращение х = у (mod от). Так, 16 = 23 (mod 7).

После преобразования обычных целых значений в модульную систему по модулю от у нас остаются только значения 0, 1, 2, 3,..., от - 1. Мы можем выполнять арифметические операции в пределах ограниченного набора чисел; для этого операция сначала выполняется так же, как в традиционной арифметике, а затем ответ, предположим, х, переводится обратно в ограниченный диапазон путем замены его на значение х (mod m). Так, в модульной системе по модулю 7 у нас есть только значения 0, 1, 2, 3, 4, 5 и 6. При сложении 2 + 6 мы получим значение 1, так как 2 + 6 = 8, что при делении на 7 дает в остатке 1. Результатом умножения 2x6 будет 5, так как 2x6= 12, а при делении на 7 остаток равен 5.

Арифметика в модульной системе — это искаженное отражение арифметики в традиционной системе. Она является отражением в том смысле, что если х = a (mod rri) и у = Ъ (mod т), то х + у = а + Ъ (mod m). А искажение означает, что суммы и произведения в двух системах не равны. В частности, произведение двух различных целых чисел в модульной системе может быть равно 1, что ни при каких условиях невозможно в традиционной системе целых чисел. Например, в системе по модулю 7 мы имеем 3x5 = 1 (так как 3x5= 15, а 15 -н 7 в остатке дает 1).

Два числа, которые при умножении дают 1, называются мультипликативными инверсиями друг друга. В традиционной системе целых чисел у значения 3 нет мультипликативной инверсии. Традиционная мультипликативная инверсия числа 3, которая равна '/3) лежит за пределами системы целых чисел. Но в системе целых чисел по модулю 7 у значения 3 есть мультипликативная инверсия, равная (как мы увидели) 5.

Когда же у значения х есть мультипликативная инверсия в системе по модулю ml Математики говорят, что если хит — два положительных целых числа, таких что х < т и х и т взаимно простые (это означает, что единственное целое, на которое без остатка делятся и х, и т, равно 1), то у значения х будет мульти-i пликативная инверсия в модульной системе по модулю т. Например, 6 меньше 13 и у этих двух значений единственный общий делитель равен 1. Поэтому у 6 должна быть мультипликативная инверсия в системе по модулю 13. Действительно, инверсией является число 11, так как 6 х 11 = 66, что при делении на 13 дает в остатке 1. Поэтому 6x11 = 1 (mod 13).

То, что у некоторых целых чисел есть мультипликативные инверсии в модульных системах, может с первого взгляда показаться странным. В частности, так как 6 и 11 — мультипликативные инверсии в системе по модулю 13, мы обнаружим, что 6х 11 у. х = х для любого значения х. Действительно, 6х11хх=(6хИ)хх = х

Обратно к шифрованию

Обратите внимание, что, если значение х неотрицательно и меньше, чем модуль т, то х (mod m) равно х. Это значит, что при выполнении арифметических операций, обычные результаты которых лежат в диапазоне от 0 до т - 1, в модульной системе мы получим те же результаты. Так, если взять очень большое значение модуля, то можно выполнять обычные арифметические вычисления, даже не зная, находимся ли мы в традиционной арифметической системе или в модульной системе. В частности, так как сумма всех значений в списке 1 4 6 12 25 51 105 210 421 850

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

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

a, аг а3 я4 а5 а6 а7 а8 а9 аю

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

Если мы умножим каждую запись исходного списка на х, то получим список

а.\Хагх агх atx аъх а6х а7х asx a9x а1Ох,

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

К b2 b3 bA b5 b6 b-, bs bg bi0,

где каждая запись эквивалентна по модулю п соответствующим записям в списке

а1ха2х а3х а4х а5х а6х а7х аъх адх а1Ох.

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

а^ха-рс аъх аАх аъх а6х а7х asx a9x а1Ох.

Предположим, что нам дано число, равное сумме 6, + b3 + b5, и необходимо выбрать из списка

6, b2 b3 b4 b5 b6 b7 bs b9 bi0

записи, которые в сумме дают это значение. Так как

b, + Ь3 + Ь5 = (а,дг+ а3х + a5-^)(niod m)

и у является мультипликативной инверсией х, то мы знаем, что

у(й, + Ь3 + Ь5) = у{ахх+ а3х + а5х) (mod от) = ух(а{ + а3 + а5) (mod m) = (а, + а3 + а5) (mod m).

Это означает, что если мы умножим сумму значений, выбранных из списка 6, b2 b3 bt b5 b6 b7 b& b9 bi0

на у, разделим произведение наши запишем остаток, то этот остаток будет равен сумме соответствующих записей исходного списка

at a2 a3 aA a5 a6 a-, as ag a10.

И так как задача о ранце в терминах этого списка решается просто, мы сможем легко узнать, что это за записи. То есть мы можем решить исходную задачу

0 ранце, выбрав соответствующие записи из списка

6, Ь2 Ь3 64 b5 b6 b7 bs b9 bm.

Вкратце, чтобы выбрать из списка 6, b2 b3 bt b5 b6 b7 bs b9 bl0

значения, составляющие сумму s, нам необходимо только вычислить значение s х у (mod m), найти в списке

а, а2 а3 а4 а5 а6 а7 а8 а9 а10

записи, сумма которых равна этому значению, и затем выбрать соответствующие значения в списке

bi b2 b3 b4 b5 be b7 b8 b9 bi0

Рассмотрим пример на списке

1 4 6 12 25 51 105 210 421 850

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

642 257 1541 771 2184 388 391 782 2206 304

Предположим, что теперь перед нами встала задача выбора из этого списка значений, сумма которых равна 4507. Мы умножаем 4507 на 18, получаем значение 81 126, делим его на 2311 и записываем остаток, равный 241. Затем обнаруживаем, что в исходном списке сумму 241 дают значения 6, 25 и 210. Так как это третья, пятая и восьмая записи в соответствующем списке, делаем вывод, что третья, пятая и восьмая записи в списке

642 257 1541 771 2184 388 391 782 2206 304

дают в сумме 4507. Действительно, значения 1541, 2184 и 782 решают исходную задачу о ранце.

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

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