Газета "Своими Именами" №18 от 21.12.2010 - Коллектив авторов - Страница 13

История даёт множество примеров эффективных алгоритмов для решения считавшихся ранее трудноразрешимыми задачами. Достаточно вспомнить шифр Г.Ю.Цезаря (вообще-то, просто Гай Юлия, поскольку цезарями древние римляне называли всех своих императоров) или разработанный ещё в средние века частотный анализ шифров простой замены.

Показателен и пример выдающегося впоследствии физика и математика Карла Фридриха Гаусса, тогда ещё школьника. Как-то учителю понадобилось покинуть класс. Чтобы занять учеников на время своего отсутствия, он предложил им найти сумму натуральных чисел от 1 до 100. Не успел учитель открыть дверь, как маленький Гаусс, опередив его, сказал, что ему уже известен результат.

Так был открыт метод суммирования арифметических прогрессий более простой, чем прямое сложение. Основанием же метода стал известный и во времена Гаусса эффективный алгоритм умножения “в столбик”. Не будь этого алгоритма, открытие Гаусса не имело бы большого смысла.

Известно, что всякое умножение чисел сводится к их суммированию. Но заслуга Гаусса в том, что он применил умножение для вычисления суммы.

Ещё один достаточно пародоксальный пример связан с анализом. В классическом анализе справедливо равенство 1=0.999(9), которое принципиально неверно в нестандартном анализе, где 0.999(9)<1, а разница 1-0.9999(9) представляет собой бесконечно малое значение, т.е. число в смысле нестандартного анализа.

Правда, в нестандартный анализ подобные бесконечно малые числа вводятся аксиоматически. Причём совокупность аксиом такого анализа столь же непротиворечива, что и классического. Увы, и столь же неполна в смысле К. Гёделя.

Не ясна природа (да и само существование) трудной обратимости или вычислимости даже для конечных алгебраических структур (типа полей Э. Галуа), к которым теорема К.Гёделя, вроде бы, неприменима.

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

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

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

Для быстродействующего аналогового вычислителя очень высокой точности, например, молекулярного, последняя задача перестаёт быть трудноразрешимой. Но такие автоматы ещё не построены, а сделанное замечание имеет тот смысл, что трудная или, напротив, лёгкая вычислимость сегодня относится лишь к базовым операциям дискретных (цифровых) вычислителей и определяется длительностью и числом тактов, необходимых для получения результата.

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

Вместе с тем, мы не располагаем никакими доказательствами в пользу того, что окружающий нас мир является строго дискретным (цифровым) или строго непрерывным (аналоговым). Это не свойство мира, а только свойство отображения мира, присущее нашему сознанию в связи с его телесной организацией, что и определяется терминами “очевидно” и “не очевидно”. И то, что для одного является “очевидным”, для другого вовсе не обязано быть таковым, что подчёркивает субъективный характер любого нематериального феномена, включая и информационный.

Кстати, наличие “очевидного” и “не очевидного” совершенно обязательно для “взлома” шифра. Иначе у нас просто не будет никакого критерия выбора того или иного варианта расшифровки среди множества возможных, включая и взаимоисключающие. Классический пример - “КАЗНИТЬ, НЕЛЬЗЯ ПОМИЛОВАТЬ” и “КАЗНИТЬ НЕЛЬЗЯ, ПОМИЛОВАТЬ” из “Страны невыученных уроков” волшебного происшествия Л.Гераскиной. Ранее это было названо избыточностью.

Так зачем всё же изобретают шифры? Из сказанного выше следует, что, во-первых, это некоторая игра ума вроде проблемы А.Л. Пуанкаре и, во-вторых, направление решения некоторых практических задач “защиты информации” (на самом деле данных), но только той (или тех), которую(ые) можно или нужно скрыть от кого-то или от чего-то. Если “информация” (опять же “данные”) интереса не представляет, то её нечего и скрывать, например, как набившая оскомину реклама. (Реклама не является информацией, понять её невозможно, какое бы усилие воли к тому ни прилагалось.) Соответственно не скрывают и “информацию” (данные), которые невозможно скрыть или украсть. Попробуйте-ка скрыть или украсть, скажем, месяц, как то проделывал гоголевский чёрт в “Вечерах на хуторе близ Диканьки” в предновогоднюю ночь.

Возможен и ещё один ответ - “шифры изобретают для того, чтобы их ломать”. Вполне допускаю, что “взлом” можно рассматривать и как некоторую увлекательную для незаурядного ума задачку вроде разгадывания кроссворда для ума заурядного. А разработка автоматических методов “взлома” шифров может представить интерес, скажем, для компьютерных вирусологов. Но, в таком случае, разработка самих шифров должна стать одним из направлений деятельности вирусмэйкеров (вирусописателей).

Вообще-то, в природе всё динамично, а является ли что-то положительным или отрицательным определяет сама природа, а не дяди, но теперь больше тёти с двойным интеллектом, выносящие решения “именем Российской Федерации” (*) .

Реклама в метро предлагает “займись спортом, найди интересную работу или создай семью” (молодым). Не получится - наймись ишачить на “эффективного” собственника (нажившего собственность отнюдь не трудовым путём) или стань (не имея ни гроша за душой) таковым сам (для лиц среднего возраста).

А если и это не можешь - тихонько подыхай, сидя дома перед телевизором (для пожилых) . Но ни в коем случае ни о чём не думай (для всех) , не бери в руки оружие (молодым) и не создавай его (для среднего и старшего возраста), если собственные руки оружия уже не держат (для пожилых). Ведь шифры ещё и оружие обороны вирусов...

Но и приведённые соображения не исчерпывают всех доводов по поводу шифров. Ольга Берггольц в своих воспоминаниях о днях блокады Ленинграда пишет о библиотечной службе осаждённого города. Её работники не только подбирали книги из брошенных личных библиотек и не только комплектовали библиотеки госпиталей, но и участвовали в производстве предметов первой необходимости, без чего жизнь была бы просто немыслима.

Тогда город испытывал потребность и в таких предметах быта, как спички и свечи. По заказу производственников библиотекари подбирали соответствующую литературу. И тут-то выяснилось, что технология современного производства тех же спичек и свечей в осаждённом Ленинграде просто невозможна из-за отсутствия необходимых материалов и оборудования. А выход был найден в старинных манускриптах. И описанные там примитивные технологии спасли тогда жизнь не одной тысяче ленинградцев.

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