Сейчас самый популярный хеш – 9ec4c12949a4f31474f299058ce2b22a. Это число, размещённое на официальной нашивке штатовского киберкомандования. С подачи Wired многие кинулись “расшифровывать” – что значит сей хеш? Быстро выяснилось, что это как бы всего лишь MD5 от официального “бюрократического” описания миссии киберкомандования (текст не привожу, его легко найти; уже сутки как вошло в “Википедию”). Вроде бы, уже официальные лица подтвердили, что, да, так и есть – использовался текст описания миссии, несекретный. Пресса пошумела в англоязычном секторе. Сейчас российская подхватит. Очень много блогеры пишут. В общем, грамотный PR, без дураков.

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

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

Вот.



Комментарии (11) »

К работающему на dxdt.ru сервису генерации картинок с формулами, записанными LaTeX (это нужно для удобного размещения формул в вебе), добавилась страница, на которой работает очень простой “редактор предложений”. Редактор пригодится для генерации строки с <img…> для вызова картинки. Редактор доступен (и, возможно, будет развиваться) вот по этому адресу: https://dxdt.ru/le/. Подробности о предмете – на странице “LaTeX в вебе“.

Пример использования:

Formula



Комментарии (8) »

Классический футбольный мяч шьётся по развёртке усечённого икосаэдра:

Фото: Sebastiano Calì

Усечённый икосаэдр строится из правильных пяти- и шестиугольников и получается таким образом: у икосаэдра “срезают” каждую вершину – то есть, на месте вершины появляется грань, представляющая собой правильный пятиугольник.

(Понятно, впрочем, что надутый мяч – не многогранник.)



Комментарии (2) »

Всё-таки довольно забавно начинает звучать текст, если автор называет псевдослучайные числа – случайными. Вот в “Компьютерре” статья, где как раз речь о псевдослучайных числах, но автор предпочитает уверенно называть их “случайные”. В статье пишут, например:


Скажем, генератор случайных чисел, встроенный в ОС Windows, автоматически используется во всех приложениях системы, связанных с защитой информации. И при этом конкретные алгоритмы генерации, используемые в Microsoft для данной цели, никогда открыто не публиковались[…]

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

Вот такие случайные числа, генерируемые, тем не менее, “алгоритмом” и, тем не менее, вычисляемые на будущее аналитиками. По-моему, кошмар.

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

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

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

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

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

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

Ссылка по теме: моя колонка про случайные числа на “Информационном буме”.



Комментарии (2) »

Кстати, первое опровержение известной гипотезы Эйлера насчёт обобщения большой теоремы Ферма появилось в 1966-ом:

1445 = 1335+1105+845+275

Опровержение просто вычислили. Это оказался один из первых замечательных вычислительных результатов, или даже вообще первый. И из последних самый нашумевший вычислительный результат – это задача об укладке апельсинов.



Comments Off on Эйлер и числа

Забавно (специально для arbuz.uz Скляревского):

31138+20128+19538+8618=28238+27678+25578+11288

Там же: 224955952840404+75924319813914+272397916926404=299998579386094

(via)



Comments Off on Числа

Между прочим, раз тут зашел разговор, то Том Хейлз (Thomas C. Hales), механистически разобравшийся в 1998 году со старинной задачей Кеплера о наиболее плотной упаковке сфер, поддерживает целый проект по обоснованию своего доказательства с помощью специального формализма.

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

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

Компьютерным программным кодам нет доверия.

Это правильно.

Но Хейлз поддерживает проект под названием Flyspeck. Вообще-то, flyspeck – английское название для “мушиного помета”, но по версии создателей проекта это всего лишь слово из словаря, подходящее под маску /f.*p.*k/ (где FPK – Formal Proof of Kepler).

Цель проекта – получение программной реализации некоего компьютерного “формализма”, оперирующего не какими-то “алгоритмами” и “данными”, а строгими теоремами (там есть и тип данных – theorem). Таким образом, планируется получение виртуально строгого, но, вместе с тем, компьютерного, вычислительного доказательства. Попутно обещают выкинуть все интуитивное из всех доказательств вообще. Вот так. Объем работы – двадцать человеко-лет.



Комментарии (2) »
Навигация по запискам: « Позже