dxdt.blog: занимательный интернет-журнал

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

Всё это, кстати, связано и с подсчётом количества корней уравнений. Можно принять, что “бесконечные процессы” в качестве корней уравнений данного типа не допускаются. Геометрически, – пусть и несколько неожиданным образом, – это означает, что не всякие кривые, которые “пересекают” рациональную числовую координатную ось, имеют с этой осью общие точки. Потому что иррациональное число √2, например, не принадлежит множеству точек оси. А на другом конце геометрической интерпретации оказывается бесконечный процесс, возникающий в ходе геометрического доказательства иррациональности √2.

Удобно, что можно поделиться ссылкой на заметку из 2008 года (почти 15 лет назад), про дирижабли:

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

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

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

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

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

Другой момент, о котором постоянно забывают: а если в качестве открытых исходников опубликован код на ассемблере – это сильно помогает в поиске уязвимостей или уже меньше? Ассемблер, даже как явление, сейчас известен меньшему кругу специалистов, это да. Но можно же обфусцировать исходный код на С, да ещё так, что понять его будет посложнее, чем соответствующий кусок в машинных кодах x86.

Вообще, трудность в понимании записи произвольного, заранее не известного, алгоритма настолько фундаментальная, что, похоже, именно она и является причиной формулирования знаменитой проблемы P≟NP. Из этого, впрочем, следует вывод, что и в обратную сторону, – то есть, для превентивного выявления закладок/уязвимостей, – публикация исходников работает не так эффективно, как принято думать: дефекты не просто всегда есть, но они и могут долго оставаться незамеченными, к сожалению. Однако открытые исходники – там, где их возможно открыть – конечно, лучше, и публикация исходников, сама по себе, не делает программу или программную систему, которая распространяется по конечным пользователям, “более уязвимой”.

Шуточное сравнение, но занимательное, поскольку показывает “почти экспоненциальные” (см. ниже) различия. А именно: одноплатный Raspberry Pi 4 (Model B) и “большой” процессор. Raspberry Pi бывает удобно использовать для некоторых вычислений, особенно четвёртую версию, поскольку она заметно более мощная, но тут я решил в качестве второго устройства взять систему на базе i9-10900K. В качестве алгоритмической основы применён пакет CADO-NFS – это реализация метода NFS (в русскоязычной терминологии, обычно, метод “решета числового поля”) факторизации чисел. Система на процессоре Intel работает под Debian 11, а Raspberry Pi – под Raspberry Pi OS (64 bit), которая тоже основана на Debian 11. CADO-NFS я собрал из исходных кодов, с типовыми настройками (за исключением параметра, задающего разрядность счётчиков, но это детали). У Raspberry Pi 4 – Broadcom BCM2711 и четыре ядра Cortex-A72, без разгона, а у i9-10900K – 10 ядер (Comet Lake, куда более мощных, понятно) на 20 потоков, без разгона.

Что получилось (RPi – Raspberry Pi 4, указано время, затраченное на факторизацию):
1) для полупростого числа разрядностью 200 бит: RPi – ~88 сек.; i9 – ~27 сек. RPi/i9 == ~3.26;
2) для полупростого числа разрядностью 319 бит: RPi – ~4879 сек.; i9 – ~262 сек. RPi/i9 == ~18.62;
3) для полупростого числа разрядностью 336 бит: RPi – ~9861 сек.; i9 – ~578 сек. RPi/i9 == ~17.06;
4) для полупростого числа разрядностью 353 бита: RPi – ~17812 сек.; i9 – ~751 сек. RPi/i9 == ~23.72.

Итак, с ожидаемо огромным преимуществом выиграла система с i9, но для чисел малой разрядности – разница не так уж велика, что, конечно, не менее ожидаемо. (Конечно, показатели зависят и от самого числа, но для шуточного сравнения это не так уж важно.) При этом, из-за меньшего объёма памяти, RPi в принципе сошла бы с дистанции значительно раньше, если бы соревнование продолжилось (в системе с i9 установлено 128 Gb ОЗУ, а в RPi – только четыре гигабайта).

Интересен и другой момент: система с i9 использует чипсет Z590, водяное охлаждение, занимает место на полке и суммарно потребляет при интенсивных вычислениях около 360 Вт (точность измерения мощности, впрочем, не очень высокая, но результат похож на правду); RPi – это одноплатный компьютер, который под нагрузкой потребляет менее 6 Вт. То есть, i9 требуется в 60 раз больше электрической мощности. Вот так.

В январе 2013 года, кроме прочего, на dxdt.ru появлялась записка об очередном годе проекта в Сети. Вообще, я как-то перестал отмечать движение dxdt.ru по ленте времени. В упомянутой записке сказано, что проект появился в 2004 году. Всё так и есть, хоть архив WordPress и начинается с 2006 года: дело в том, что раньше использовалась другая CMS (если я правильно помню, то это была самописная CMS на языке Perl). В записке из 2013 года сказано, “что сейчас в dxdt.ru опубликованы 1871 заметка и 8804 комментария”. Что ж, за десять лет эти показатели изменились: сейчас – 2,656 записок и 11,317 комментариев. Записок стало больше всего-то на 785, что составляет, в среднем, лишь около 80 новых в год. Не густо, конечно. Но, во-первых, не так важно количество; во-вторых, это всё ещё более одной записки в неделю (что бы это ни значило). Ну и комментарии иногда появляются. Посмотрим, что будет дальше.

Разгадка к задаче про 2^255+19. В диалоге из “эпиграфа” к задаче говорится, что “очевидно, 2^255 + 19 делится на три”. Практически вся современная криптография так или иначе использует арифметику остатков. Поэтому понять, что 2^255 + 19 делится на три можно моментально: 2^255 при делении на 3 (mod 3) даёт остаток -1 (см. ниже); а 19 – это +1 (mod 3), потому что на 3 делится 18, соответственно, 19 == 6*3 + 1. Сумма остатков -1 + 1 == 0. Следовательно, число делится на три.

Почему 2^255 даёт остаток -1? Потому что 255 – нечётное число. Действительно, 2 в чётной степени будет давать остаток 1 (mod 3), а в нечётной остаток -1 (или 2, что здесь то же самое), так как 2 == 1*3 + (-1). Из этого можно вывести признак делимости на 3 для числа в двоичной записи, то есть, когда основание системы равно двум. А именно: биты со значением 1 (единица) на чётных позициях будут давать +1, на нечётных -1; если сумма (по единичным битам) делится на 3, то и само число делится. Пример (позиции считаем справа налево): 42 == 0b00101010; 1 + 1 + 1 == 3, следовательно, делится; 42 == 14*3; 43 == 0b00101011; 1 + 1 + 1 + (-1) == 2, следовательно, 43 не делится на 3.

Решение для 2^2023 + 2023. Доказываем, что делится на 3:
2^2023 (mod 3) == -1 (см. выше)
2023 = 2022 + 1; воспользуемся привычным признаком делимости для десятичной системы: 2 + 2 + 2 == 6, то есть, 0 (mod 3) => 2023 == 1 (mod 3)
-1 + 1 == 0

Естественно, возможны и другие, чем-то более привычные, способы. Например, в шестнадцатеричной системе, где 2^2023 это будет восьмёрка со множеством нулей, а 2023 == 0x07E7, поэтому в записи нашего числа, кроме нулей, встречаются только шестнадцатеричные цифры 8, 7, E и 7. В шестнадцатеричной системе действует тот же признак делимости на 3, что и в десятичной (“если сумма значений цифр делится на 3”), потому что основание системы 16 == 15 + 1, то есть, остаток 1. Шестнадцатеричное E это 14: 8 + 7 + 14 + 7 == 36; 36 == 12*3.

Про измерения и DNS в Интернете: В 2020 году в журнале “Интернет Изнутри” вышла моя статья “DNS как источник глобальной информации о Сети“, где, в частности, описывается практический способ, позволяющий измерить характеристики DNS-резолверов, обслуживающих конечных пользователей веба.

Публикации за семь лет сейчас доступны на отдельном сайте журнала, почитайте.

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

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

Вообще, Аристотель не просто рассматривает падение тел строго через некоторую среду, но и предлагает классифицировать быстроту движения по пропорциям веса и сопротивления среды. А для “пустоты” такая классификация не работает, поскольку “в пустоте все тела были бы одинаково быстры, но без причины”, либо их максимальная скорость оказывается сколь угодно большой. Соответственно, пустоту (вакуум) Аристотель отвергает. И нужно учитывать, что Аристотель оперирует древнегреческими терминами и понятиями. Так, “полнота” (“заполненное”) и “пустота” (“пустое”) – πλῆρες и κενόν – это “первичные составляющие”, но Аристотель утверждает, что “полнота” должна быстро заполнять всякую пустоту, иначе возникают трудности с классификацией движения. А “скорость” в соответствующем фрагменте у Аристотеля обозначается словом τάχος, которое можно перевести и как “быстрота”, то есть, это, конечно, “скорость”, но в смысле минимального затрачиваемого времени (конкретно, “одинаково быстры” – ἰσοταχῆ; где знакомая приставка “изо-“/ἰσο как раз и обозначает одинаковость). (Другие сходные значения для той же основы: скорый, проворный и т.д.). Да и строит соответствующее понятие Аристотель на базе соизмеримости проходимых интервалов пути, интервалов времени. То есть, речь явно идёт о максимальной скорости (“быстроте движения”), достигаемой телом.

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

Одна из не очевидных особенностей DNS, как сервиса, в том, что этот сервис позволяет преодолевать самые разнообразные системы сетевых ограничений. Типичная ситуация: на некотором сервере закрыты не только все внешние входящие, но и исходящие сетевые соединения “во внешний Интернет”; это может быть сделано как силами сетевого экрана (файрвола) в операционной системе, так и настройкой правил на том или ином маршрутизаторе, за которым подключен сервер. Однако DNS-сервис здесь доступен через выделенный локальный (для сетевого сегмента) резолвер без ограничений. Почему? Во-первых, без DNS не работает множество привычных системных утилит. Во-вторых, администраторы нередко воспринимают DNS именно как сервис, поэтому доступ к резолверу считается доступом к локальным ресурсам и не фильтруется.

Понятно, что так как исходящие соединения закрыты, то запущенная на сервере “троянская программа” не сможет простым способом передать какие-то данные внешнему узлу. Но можно передать данные через DNS. Типовой и универсальный способ – запрос A-записи для имени в доменной зоне, которая делегирована на авторитативные серверы, контролируемые “принимающей стороной”. Предположим, что нужно передать последовательность из нескольких байтов (с произвольными значениями), а “инструментальная” доменная зона – test.ru. Закодируем последовательность тем или иным способом в подмножество допустимых ASCII-символов и запросим в DNS имя, где получившаяся строка будет дописана на третьем (и ниже) уровне: JBQWY3DPFVUGC3DMN4QSCIIK.TEST.RU. Данное имя, через резолвер (или несколько резолверов) попадёт в составе запроса на авторитативный сервер зоны test.ru, где его можно обработать и извлечь данные. (При необходимости, можно разделить запись полезной нагрузки точками – это не повлияет на доставку.)

DNS-запросы, содержащие подобную “абракадабру”, далеко не всегда вызывают подозрения, потому что могут генерироваться не только какими-нибудь элементами ботнета, но и вполне штатными программами, которые таким образом пытаются, например, обнаружить подмену и перехват DNS. Однако, для повышения уровня скрытности, запросы могут кодироваться каким-нибудь другим, вполне “безобидным”, способом: table.is.unavail.fedora.test.ru. Но каждый шаг в сторону снижения уровня “подозрительности” будет снижать и пропускную способность канала передачи.

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

Переход сети ARPANET на TCP/IP состоялся 01/01/1983 – то есть, в 2023 году Интернету исполнилось 40 лет. Почему отсчёт связан именно с этой датой? Потому что Интернет, как глобальная сеть, это именно ARPANET c TCP/IP и связанные технологии, к которым, прежде всего, отсносятся механизмы IP-маршрутизации между компьютерными сетями. Интернет составляют автономные системы. Логические инструменты, позволяющие определить автономную систему (в терминах Интернета и маршрутизации), это следущие понятия:

• межсетевая граница контроля над связностью узлов;
• пограничный маршрутизатор;
• алгоритм маршрутизации и схема межсетевой адресации узлов.

Межсетевая граница – позволяет разделить сетевые узлы внутри и сетевые узлы снаружи, с точки зрения структуры связности; ключевой аспект: локальная администрация сети контролирует и самостоятельно определяет связность локальных узлов (то есть, “какой компьютер куда и как подключен”), а на “коммутацию” внешних узлов повлиять не может и об их реальной связности ничего априори не знает.

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

Алгоритм маршрутизации и межсетевой адресации узлов – это универсальный и эффективный способ адресовать сети и узлы так, чтобы можно было строить практические маршруты доставки пакетов через межсетевые границы при помощи пограничных узлов-маршрутизаторов, абстрагируясь от свойств физических каналов и конкретных протоколов электросвязи. Это и есть IP (префиксы и адреса узлов) и необходимый, в современной сети, BGP (Border Gateway Protocol).

Второй важнейший составляющий элемент Интернета – DNS. Но здесь он оставлен за скобками.

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

Сейчас популярна история с чат-ботом ChatGPT, который даёт пространные ответы на вопросы из самых разных областей. Мне доступ к данному сервису получить не удалось (там хотят слишком много реквизитов), но это не важно: понять, о чём речь, не так уж трудно по многочисленным цитатам. Всё это увлечение соответствует попыткам найти смысл непосредственно в тексте. Проблема в том, что текст, как набор символов с определённой структурой, тем не менее, самостоятельного смысла не несёт. Смысл образуется (или не образуется) после того, как результат прочтения текста вкладывается в некоторую большую структуру; и чтобы говорить об “интеллекте”, давать оценки, данная структура должна быть заметно мощнее конкретного текста. Это, впрочем, хорошо известное явление, про которое написано очень много и подробно. Несомненно, письменность очень важна не только для древних языков, но и для современных. Однако переход автоматического генератора текстов от фильтрации совсем примитивных конструкций к “наследованию” чуть более развитой “семантической” структуры, свойственной многим текстам по заданной теме, скорее свидетельствует об успешной оптимизации использования вычислительной аппаратуры с целью удивить пользователей Интернета, чем о чём-то ещё.

В советском мультфильме “Трое из Простоквашино” (1978 года) есть эпизод с Галчонком и потальоном. Почтальон Печкин стучится в дверь, но дома только специально обученная птичка – Галчонок, который на стук реагирует одной и той же фразой.
– Кто там? – спрашивает Галчонок. (Это единственная фраза, которую он знает на тот момент.)
– Это я, почтальон Печкин, принёс заметку про вашего мальчика, – отвечает Печкин. Ничего не происходит, поэтому почтальон стучит снова.
– Кто там? – спрашивает Галчонок.
– Это я, почтальон Печкин, принёс заметку про вашего мальчика, – отвечает Печкин.
Цикл “запрос-ответ-пояснение” повторяется многократно. В какой-то момент Галчонок замечает муху на оконной раме и клюёт её, производя тем самым стук.
– Кто там? – спрашивает, вместо Галчонка, заскучавший Печкин.
– Это я. Почтальон Печкин. Принёс заметку. Про вашего мальчика, – будто телетайпом отбивает ответ Галчонок.
И тут столкновение могучих интеллектов оканчивается поражением Печкина: эмоционально потрясённый, почтальон теряет сознание.