` ` `Всем нам (по книгам и кинофильмам) известна такая система передачи секретной информации. Имеется «ключ»
К. Это – относительно небольшой текст или какой-нибудь другой информационный «блок», который надо хранить как зеницу ока. Сообщение
С с помощью
К преобразуется в «шифр»
Ш. Это тоже информационный блок, примерно совпадающий по объёму с
С, но не доступный пониманию не подготовленного человека.
Ш передаётся по каналу связи (желательно – тоже засекреченному, но не всегда это возможно) «Штирлицу». Он тоже знает
К, и с его помощью преобразует
Ш в
С, которое и читает.
` ` `Надёжность такой системы зависит от объёма
К, а в случае малого объёма ещё и от того, в какой степени выбор очередного заменяющего символа зависит от всех символов
С (чем сильнее зависит, тем «лучше»). В СССР была разработана для дипломатов и особо ценных агентов система, которую можно считать практически АБСОЛЮТНО надёжной. Не зная её деталей, обрисую её условно. У Штирлица и Сталина имеются одинаковые книжки, сделанные только в двух экземплярах. На каждой странице написан отдельный
К. Это просто таблица случайных чисел (двузначных), указывающая, на сколько нужно увеличить номер (в «алфавите») очередного шифруемого символа из
С при переходе к
Ш. Если получившийся номер превысит объём алфавита, то он берётся «по модулю», равному объёму алфавита (проще сказать, берётся остаток от деления получившегося номера на объём алфавита). Расшифровка делается путём вычитания номеров. Передаваемые
С-я, как правило меньше объёма
К. И (главное!), как Штирлиц, так и Сталин обязаны после использования очередного
К сразу его уничтожить.
` ` `Такой
Ш, перехваченный «по дороге», расшифровать невозможно. Один недостаток у этой системы: не годится она для массового использования, например для оперативного управления войсками.
` ` `Во время второй мировой войны немцы создали знаменитую шифровальную машину «Энигма», обладавшую большой оперативностью и выглядевшую просто как пишущая машинка. В качестве
К использовался (сменяемый) набор из нескольких кулачков, от формы которых зависел характер замены символов при шифровке. Не очень большой объём такого
К вместе с многократным его использованием, а также шифрование «буква за буквой», позволили в итоге англичанам путём дотошного изучения статистики
С-й научиться читать немецкие
Ш-ы, и успешно топить их подводные лодки. Руководителем этих работ по дешифровке считается знаменитый математик Алан Тьюринг. (Поляки любят хвастаться, что научившимися делать это "англичанами" были на самом деле служившие у них два поляка.)
` ` `Рассмотрим теперь ГИПОТЕТИЧЕСКУЮ достаточно надёжную систему шифрования, в которой вместо одного ключа
К используются два:
К1 и
К2. При этом
С шифруется с помощью
К1, а расшифровывается посредством
К2. Оказывается, при этом могут появиться новые возможности, в частности, можно снабдить каждого человека так называемой «электронной подписью». Мыслится это так. Каждому человеку даются свои
К1 и
К2. При этом
К2 ("открытый" ключ) публикуется вместе с именем этого человека во всех телефонных и т.п. справочниках. А
К1 ("закрытый" ключ) человек хранит в тайне от всех..
Допустим, этот человек хочет послать в другую страну документ, имеющий юридическую силу. Он шифрует его с помощью
К1 и пересылает его вместе со своим именем (имя не шифрует). Получатель по этому имени находит в справочнике его
К2 и применяет его к полученному
Ш. Если получится ОСМЫСЛЕННЫЙ текст, делается вывод, что документ получен именно «от того» человека.
` ` `Именно такую систему шифрования придумали в 1976 г. два молодых (тогда) американских математика У.Диффи и М.Э.Хеллман. Система оказалась на редкость надёжной потому, что характер замены отдельного символа
С-я зависит сразу от всех символов
С-я (точнее об этом – ниже). И именно такая (или модернизированная?) система используется например в «Western Union». Реализована на практике она была, конечно, не в 1976 г., а позже. Свои
К1 и
К2 (и «электронную подпись») имеет там каждое "отделение".
` ` `Ключи эти выглядят как две пары чисел:
К1 = (а1, q) и
К2 = (а2, q).
При этом число q является произведением двух ПРОСТЫХ чисел (делящихся только на единицу и самого себя) непривычно фантастической длины (например более 60 знаков).
Число а1 – тоже фантастической длины, но выбирается достаточно произвольно (есть некоторые ограничения, но при первом знакомстве считайте это несущественным). Заслугой этих американцев является (найденный ими и доказанный!) способ нахождения числа а2, обеспечивающий такую процедуру шифрования-дешифрования
С-й:
Превращаем
С в целое число любым способом, для которого мы умеем производить обратное преобразование. Например, заменим каждый символ его номером (двузначным: 1=01) в «алфавите». Это число дальше и будем считать
С-ем. Возведём
С в степень а1 и найдём остаток от деления результата на q. В результате и получим
Ш. Расшифровка делается аналогично:
Ш возводится в степень а2 и берётся остаток от деления на q. Это и будет
С.
` ` `Схема достаточно прозрачна. но на первый взгляд кажется, что она потребует фантастических вычислительных ресурсов из-за чудовищного количества «тактов» при возведении в степень и чудовищного нарастания количества «знаков» у промежуточных результатов.
К счастью второе можно преодолеть, работая только с остатками у каждого промежуточного результата, иначе говоря, работая "в кольце вычетов по модулю q ". Например, пусть q=15. и пусть
74*51 = 3774 = 251*15+9, то есть остаток от деления 3774 на 15 равен 9.
Но этот результат можно получить и не умножая 74*51, а умножая только их остатки :
74 = 4*15+14
51 = 3*15+6
14*6 = 84 = 5*15+9, т о есть остаток тоже равен 9. И так будет «всегда» (теорема).
Количество «тактов» тоже можно свести к разумному, используя быстрое нарастание геометрической прогрессии. Например, вместо 99 умножений для вычисления числа а^100 можно поступить так:
b=a*a (одно умножение)
b1=b*b (одно умн.). Уже получено а^4.
b2=b1*b1 (одно умн.). Получено а^8.
b3=b2*b2 (одно умн.). Получено а^16.
b4=b3*b3 (одно умн.). Получено а^32.
B5=b4*b4*b4*b1 (три умн.). Получено а^100 путём всего 8 умножений.
Одним словом, при использовании компьютера всё это выглядит реальным. Остался вопрос: как научиться изобретать нужные фантастические простые числа? Оказывается (этому результату уже более 100 лет), существует способ тестирования произвольного числа на простоту без попыток деления его на последовательные простые числа. И этот способ для огромных чисел требует умеренного числа операций. Но даже если нам удалось установить, что рассматриваемое число – не простое, а составное, способ этот не даёт никаких рекомендаций для нахождения его делителей.
Среди 60-значных чисел примерно каждое 140-е будет простым (благодарим за знание таких вещей великого русского математика П.Л.Чебышёва!). Поэтому их можно просто перебирать и тестировать. Число а1 можно, как я сказал, брать достаточно произвольно. А вот придуманный этими американцами способ нахождения числа а2 требует ЕЩЁ И ЗНАНИЯ разложения числа q на эти укаанные выше два простых числа. Кстати, числа а1 и а2 оказались обладающими свойством взаимности: то есть можно и шифровать с помощью а2, тогда расшифровывать с помощью а1.
При выбранных здесь параметрах можно передавать блоки информации примерно в 60 символов. Более крупные можно резать на куски…
` ` `На чём держится нынешняя уверенность в большой надёжности этой системы? На том, что до сих пор не придумано алгоритма разложения произвольного числа на множители, существенно более эффективного, чем последовательное деление на членов «таблицы простых чисел». А этот способ потребует для разложения числа q от современных компьютеров миллиард миллиардов миллиардов … миллиардов лет работы.
Более эффективные способы искали величайшие математики (Ферма, Эйлер, Лагранж…).
Были у них и некоторые удачи, но… если ускорить работу скажем в миллион раз, в нашем случае это мало что даёт… Так что хакер, сумеющий честно (без пистолетов и грабежа) «взломать» эту систему, встанет в один ряд с этими величайшими…
[свернуть]
Ответить с цитированием
