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

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

Начать лучше всего с множеств и групп. Я бы начинал объяснять уже с десткого сада. Обожаемые нашими чиновниками реестры - пример множества сведений (например о недвижимости, которую можно спиздить). И так как в одном из последних законов предлагается создать "реестр реестров", то парадокс Рассела начинает играть новыми яркими цветами - должен ли реестр реестров включать самое себя? (Многим он известен, как история про цирюльника и бритьё)

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

Более безопасный пример группы - циферблат часов. У нас есть числа от 0 до 12 и операция сложения. Сколько ни складывай из циферблата не выйдешь. 9 + 4 (mod 12) = 1, 2 + 2 (mod 2) = 0. В модульной арифметике дважды два не всегда равно четырем. Ноль - нейтральный элемент группы, сколько не прибавляй нулей - стрелка не сдвинется. Обратный элемент - вращаем стрелку в обратном направлении. 9 + (- 9) (mod 12) = 9 + 3 (mod 12) = 0. Такая группа называется (Z12, +)

Простые дроби - группа с операцией умножения, в которой обратный элемент для числа a/b - это b/a и нейтральный элемен единица. 1/2 * 2/1 = 1 Так как дроби образуют группу и со сложением и с умножением, то такая конструкция называется "поле". Бесконечное поле рациональных чисел Q. Группы могут содержать другие группы в качестве подгрупп (кубик-рубика часть группы S48). Я хотел привести пример изоморфизма, но страшное слово убьёт половину аудитории, достаточно сказать, что иногда одну (или несколько) групп можно "превратить" в другую.

А ещё важнее запомнить, что группа - фундаментальная алгебраическая структура, которая необязательно имеет отношение к числам (просто математикам так удобнее). Структуры важнее чисел и формул, и задают ткань реальности, понятия "симметрии" и многие другие. Теория групп помимо математики (а там её можно встретить даже в анализе!) используется в химии, лингвистике, а физика пропитана ею настолько плотно, что физики когда-то кривились и называли её чумой (Gruppenpest).

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

Самый известный пример - шифр Цезаря, в котором буквы сдвигаются на несколько позиций. Если у нас ключ 'C', то текст ABZ превращается в CDB. То есть это просто сложение по модулю 26 (для латинских букв), и ключ и текст - элементы одного множества, и шифр - группа (Z26, +). Шифровать текст дважды "Цезарем" бесполезно, групповая операция ассоциативна (a + k1) + k2 = a + (k1 + k2). Взломать его можно или перебором (пространство ключей мало) или частотным анализом (тут всё объяснил Конан Дойл и гораздо лучше меня).

И мы переходим от Дойла к Жюлю Верну. Следующий шифр Виженера похож на Цезаря, только ключом служит не одна буква, а фраза. Складываем первую букву текста с первой буквой ключа, вторую со второй и дальше по кругу. Чтобы взломать шифр, текст нужно разрезать на полоски, если ключ из четырех символов, то возьмём 1, 5, 9 символ и дальше как с "Цезарем". Определить длину ключа можно заметив повторы в криптограмме - это места где текст и ключ втречаются в тех же позициях.

Как и в случае с Цезарем шифрование двумя ключами (на сленге криптографов - каскад) даст тот же результат, что и однократное шифрование "третьим" ключом, но есть ньюансы, длина этого ключа равна наименьшему общему кратному (LCM, НОК) от длин ключей. Что как бы нам напоминает о том, что в группе может быть внутренняя структура. НОК вычислить легко: LCM(a, b) = a * b / GCD(a, b), где GCD наибольший общий делитель, и если вы и про Эвклида ничего не слышали, то всё совсем плохо. "Здрастуй школа".

Если Виженер вам по нраву, пользуйтесь несколькими ключами, у которых длины - (со)простые числа, у них не может быть общих делителей по определению. Для ключей с длиной 11 и 13 длина эффективного ключа будет 143. Если ключ той же длины, что и текст, то такой шифр называют "одноразовым блокнотом" и его нельзя взломать. Перебирая все возможные ключи мы получим все возможные тексты заданной длины и не сможем понять, какой именно нам нужен. В случае с блокнотом повторное использование ключей приводит к взлому.

Я бы не углублялся в элементарную математику и криптографию, но не так давно компания "Бережа" разместила объявление о работе, закодированное и последовательно зашифрованное несколькими простыми шифрами, и многие начали ломаться чуть ли на Цезаре, что с моей точки зрения есть полное и окончательное безобразие. Вопросы о том формирует ли каскад группу, как устроены современные симметричные шифры оставим на Новый Год, и сразу перейдём к вопросу, мучающему министра. Что такое криптография с открытым ключом?

Оставим в покое многострадальный RSA (о нем у меня есть отдельный пост), тем более что структура, лежащая в основе RSA - полугруппа, а если быть совсем точным, то так как там есть нейтральный элемент, то - моноид. И перейдём сразу к алгоритму Диффи-Хеллмана. Одноразовый блокнот всем хорош, но ключей много и их нужно как-то передавать и надежно хранить, что само по себе нередко приводило к расстрелу за шпионаж. Потому люди задумались о том, как сделать так, чтобы получить общий ключ для Алекса и Юстаса (или как их называют Алиса и Боб), не выдав страшную военную тайну.

Надо вам сказать, что если количество элементов ("порядок группы") в мультипликативной группе (операция модульное умножение) - простое число, то такая группа Zp будет циклической. В ней обязательно существует такой элемент g (он называется генератор), что умножая его сам на себя можно получить все остальные элементы, всю группу целиком. Можем быстренько проверить: 3^0, 3^1, 3^2 ... 3^6 (mod 7) = 1, 3, 2, 6, 4, 5, тройка - генератор циклической мультипликативной группы (Z7, *). (Если к Zp добавить операцию сложения, которая тоже порождает группу, то получится конечное поле Fp. Всегда. Для всех простых. Потом пригодится)

Алиса и Боб выбирают достаточно большую группу Zp и договариваются (в открытом виде) о группе, том самом числе p и генераторе g. Алиса выбирает случайный секретный ключ a, Боб b. Затем Алиса посылает Бобу число g^a, а Боб в ответ присылает число g^b. Алиса возводит число Боба в степень a, а Боб делает то же самое с числом Алисы, так что на выходе у них одно и тоже число (g^a)^b = (g^b)^a = g^(a * b), его-то они и используют в качестве ключа для симметричного шифра. Злые фашисты могут подслушать числа p, g, g^a, g^b и это им ничем не поможет. Задача фашистов найти x, зная (g^x) mod p. Называется DLP - проблема поиска дискретного логарифма.

Всё бы ничего но числа, которые нужно возводить в огромные степени в алгоритмах RSA, DSA, DH довольно большие, и дяди и тёти криптографы начали подыскивать не менее сложные задачи, так чтобы и ключи были поменьше и надежность была на высоте. Тут-то и появляются эллиптические кривые. Если вы любите рисовать графики, то попробуйте формулу y^2 = x^3 + ax + b и получится, что-то похожее на чертеж ненавистного Цукербергу женского соска в разрезе. Суть в том, что рисовать график мы будем не на плоскости, а в конечном поле Fp, все то же самое только по модулю p.

Получившиеся точки (если их нарисовать будут раскиданы по экрану хаотически), я нарисовал картинку и немного изменил параметры, так чтобы фейсбук не забанил меня за эллиптическую обнажонку. Красные точки - таже самая кривая только в поле F_1019. Точки можно складывать между собой так, что в результате тоже получается точка, лежащая на кривой (если полставить x и y в уравнение, то левая часть равна правой), а значит они образуют группу. Складывая точку саму с собой (умножая её на константу), мы как будто бы вертим стрелку циферблата. Повернуть в одну сторону легко, а узнать где она была изначально - сложно. Задача называется, сюрприз, ECDLP. И ключи короткие.

Недавно прогресс дошел до того, что ученым удалось факторизовать (привет RSA) и найти дискретный логарифм (привет DH) для чисел длинной 768 бит, это очень большое число. Сильно больше чем атомов во вселенной. При этом прогресс связан не ростом вычислительной мощности, а с улучшениями в алгоритмах. Для кривых таких алгоритмов нет. Происходит это потому, что группы точек эллиптических кривых более абстрактные. Грубо говоря, у кривой нет простых множителей, на которые её можно разложить. Зато существует 65537 способов закосячить криптоалгоритм и превратить его в полнейшее говно. О чем стоило бы поговорить отдельно.

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

Что помешает Федорову и Дубилету подсадить вам Авакова в смартфон вместе "Дией"? Что ему помешает подделать результаты выборов? Что помешает жижитальным трансформатором распылить ответственность за подделку документов на такие маленькие кусочки, что крайних просто не останется? Для ответа на этот вопрос уравнений не придумано. Никакие модные слова, произносимые цифровыми проходимцами (и которые они сами не понимают) не заставят меня им поверить.

Dual_EC_DRBG

Linux/NSA

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

Неуёмные приступы "хочу всё знать" случаются не только у замусоренных академиков, но и в цивилизации тоже. Когда надежные алгоритмы шифрования стали доступны всем без исключения, гебня всех стран и континентов чутка приуныла и стала думать, как лучше всего отжимать секреты у граждан. Криптовойны бушевали довольно долго и самое лучшее, что АНБ тогда придумало - давайте мы вам разрешим пользоваться 64-битными ключами, а взамен вы нам доверите хотя бы кусочек. http://www.cypherspace.org/adam/hacks/lotus-nsa-key.html

Даже кое-где реализовали. В Лотус в 1998 году был вшит RSA-ключ АНБ с O=Министерство Правды и CN=Большой Брат. Длина модуля 760 бит, и сейчас такой ключ уже можно взломать не за все деньги мира. Естественно, если можно пользоваться хорошей вещью, то зачем брать испорченную? И затея не зашла, а желание подслушивать никуда не девалось и тогда долбоёбы придумали хитрый план по прохиванию ослабленных стандартов через NIST, причем в самых неожиданных местах.

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

В Линуксе есть два отдельных "устройства" /dev/random и /dev/urandom В random лежат настоящие случайные числа, а в urandom псевдослучайные. Интересный ход мысли: мы не доверяем АНБ потому для генерации случайных ключей не будем пользоваться криптоалгоритмами, а выберем их по-настоящему случайно, чтобы зарядить их в алгоритмы, которым мы не доверяем (Oh, wait... теории заговоров косят иногда даже таких крутых программистов как Торвальдс). Но если вы параноик, то это не значит, что за вами не следят.

Возьмём (EC)DSA. Для тех кого пугают слова "конечное поле" и "эллиптическая кривая" у меня теперь есть специальный пост https://www.facebook.com/ruheight/posts/820871451694548 Для того, чтобы что-нибудь подписать нам понадобится циклическая группа Zp, с генератором g, где p - не только простое число, но у него есть большой простой множитель q. Для q подойдут числа Софи Жермен p = 2q + 1 (q и p - простые). И если вам с целью углубления гендерного равенства захочется рассказать о женщинах математиках, то перестаньте таскать труп Гипатии и вспомните о Жермен и Нёттер.

Выберите случайное число x меньше q, y = g^x mod p ваш публичный ключ, а x - секретный. Узнать x, зная только y нетривиальная задача на чем всё и строится. Подпись состоит из двух чисел r = g^k mod p mod q, и s = k^-1(H(m) + xr) mod q, где H(m) - хеш от сообщения (хеш - односторонняя функция, которая служит своеобразным "отпечатком" текста). Пара (r, s) и есть подпись. Алгоритм проверки можно посмотреть в Википедии. А вот число k - должно быть совершенно случайным. Если оно не очень случайное или повторяется (r в подписях будет одинаковым для разных сообщений), то тогда беда. Все действия по модулю q:

s1 = k^-1(h1 + x*r), s2 = k^-1(h2 + x*r)
s1 - s2 = k^-1(h1 + x*r - h2 - x*r) = k^-1(h1 - h2)
k = (h1 - h2) / (s1 - s2)
x = (s*k - h) * r^-1

Выглядит немного страшновато, но ничего сложнее школьных действий со скобками, сложением и умножением тут нет. Напомню на всякий случай, что k^-1 - просто 1 / k. Только попробуйте сказать, что не знаете про дроби и скобки и я вас прокляну на веки вечные. И именно в этом месте Sony с размаху насрала себе в штаны, используя одинаковые k для разных подписей, после чего у них потёк секретный ключ x, а вместе с ним и защита Play Station 3. То что Sony использовала эллиптические кривые (ECDSA) им не помогло. Всё тоже самое, вместо возведения в степень y = g^x, скалярное умножение y = x * G, где G - точка на кривой.

И в 2006 году в NIST (Национальный Институт Стандартов и Технологий) приходят хитрожопые долбоёбы из АНБ и говорят, что мы придумали отличный генератор псевдослучайных чисел, который называется Dual_EC_DRBG. Звучит загадочно, но на самом деле всё довольно просто. Есть параметры эллиптической кривой, секретное начальное значение генератора s_0 и точка на кривой Q. Следющее значение генератора A = s_i * Q. Потом отрезаем от координаты x точки A 30 байт из 32-х и отдаём как случайное.

У подобной конструкции есть проблема. (на самом деле не одна, но то несущественные детали) Если у нас есть 30 байт из 32, то мы можем пробежать по оставшимся 16 битам перебором, подставить x в уравнение кривой, и вычислить y, чтобы узнать следующее значение генератора. Для этого, в параметрах генератора есть точка P, и следующее его состояние s_(i + 1) = s_i * P. Потому генератор "Dual" - одно умножение для того, чтобы из состояния получить новое значение, и второе умножение, чтобы изменить состояние. Казалось бы всё хорошо, и надежно.

Вот тут как раз и порылись американские чекисты и предложили два конкретных значения P и Q (NIST SP800-90A), забыв рассказать откуда они взялись. А ведь вся суть эллиптических кривых в том, что точки кривой в конечном поле образуют группу. И между ними может быть связь. АНБшники просто выбрали случайное число n, выбрали случайную точку Q, а P задали, как P = n * Q, и та же самая математика, которая не даёт подделать цифровую подпись гарантирует, что вычислить ключ от черного хода - число n практически невозможно.

Зная как точки P и Q связаны между собой, АНБ может по одному значению генератора псевдо-случайных чисел вычислить внутреннее состояние генератора и все последующие его значения. На внедрение чудо-стандарта спец. служба потратила миллионы долларов в виде взяток. Теперь осталось только показать, как можно использовать протрояненный генератор.

Когда вы открываете Фейсбук, и в адресной строке появляется "зеленый замочек", ваш компьютер установил защищенное соединение. В протоколе TLS широко используются и случайные числа (в том числе в открытом виде), и те же самые протоколы ECDH, ECDSA. Возможность "угадать" следующее случайное число позволяет не только вскрыть одну защищенную сессию (восстановить ключи ECDH), но и вскрыть секретный ключ ECDSA, который подтверждает идентичность сервера, и в последствии притворяться им. Атака человек-в-середине, MITM, а не Зеленский с Трампом во рту и хуйлом в заднице.

Разумеется их вывели на чистую воду. Вначале в теории, показав, что есть такая возможность http://dualec.org/DualECTLS.pdf , а после того как Сноуден опубликовал документы АНБ, то и на практике. Сейчас разворачивается очередной виток криптовойн, и парламентарии разных стран пытаются давить на социальные сети и мессенджеры, чтобы запустить чексисткую кисоньку в переписку для нашего же блага (и для защиты детей конечно), сами при этом почему-то предпочитают пользоваться защищенными каналами связи и такими мессенджерами как Signal.

Безопасность одна для всех. Или криптография помогает всем - и честным гражданам, и преступникам или не помогает никому. С моей точки зрения выбор очевиден. Благосостояние государства зависит не от наполнения пресвятого бюджета, а от благосостояния граждан. В государстве безопасно, если граждане находятся в безопасности. Между безопасностью и свободой нет никаких "балансов" и выбора "или-или". Если в ваши секреты не могут залезть менты, то и преступники туда залезть не смогут. Мне не нужен цифровой поводок и паспорт в телефоне, я хочу жить в свободной стране, где по улицам можно ходить без паспорта.

Проект 2693 "про медиа" (ст. 97 п.7) законодательно вводит в Украине Интернет-цензуру. Хотел по привычке добавить "по российскому образцу", но Украина уже идёт с опережением. Ткаченко, Потураев, Кравчук, Констанкевич, Кабанов, Боблях, Богуцкая, Рябуха, Сушко, Налетов, Циба - имена врагов свободы слова. Охуевшая мандатра Кравчук ещё имеет наглость ссылаться на Пастернака. Что еще можно добавить? Интернету в Украине - пизда. И медиа тоже. Будете как Грани по зеркалам бегать.

Между тем, сквозь ООН проползла резолюция о "Противодействии использованию информационно-коммуникационных технологий в преступных целях". Сама резолюция - обычное дипломатическое блеянье о приверженности, принятии, следовании, наращивании, ускорении и развитии. По сути, просят ещё один "межправительственный комитет" по Интернетам. На самом деле, так как страны спонсоры т̶е̶р̶р̶о̶р̶и̶з̶м̶а̶ резолюции: Беларусь, Камбоджа, Мьянма, Никарагуа, Северная Корея, Китай, Венесуэла и Российская Федерация (все сплошь приверженцы свободы, прав человека и родина технологий), то речь идёт о суверенном праве государств разрушать Интернет и превращать его в кучу огороженных чебурашек. О чем говорящая лошадь Лавров уже сказал открытым текстом. США традиционно выступили против и напомнили, что для борьбы с преступностью уже есть Будапештская конвенция. Но Ассамблея поддержала людоедов. Что лишний раз доказывает, что уёбищное ООН, МСЭ и прочих борцов за мир во всем мире к Интернету даже близко подпускать нельзя.

Чтобы отвлечься от серьёзных задач и немного развлечься, вспомнил о такой эпичной вещи, как "архиватор Бабушкина". Если раньше не слышали, а в Лурк заглядывать лень - Леша Бабушкин редкостной дури школяр из Барнаула, внесший неоценимый вклад в науку в виде антивирусов на BAT, ловящих всё на свете и архиваторов сжимающих любые данные в ноль. Отец юного (теперь уже не очень) дарования - проректор алтайского меда, всячески его пропихивал и закончилось всё как всегда травлей и лулзами.

Я задумался: можно ли заставить "компрессор" работать. Идея алгоритма простая: любую последовательность битов можно представить как двоичную дробь, просто приписав перед ней ноль и запятую, а так как она конечная, то можно её записать как рациональное число a / b, сократить её, и записать вместо длинной двоичной дроби два целых числа a и b. Естественно, так как несократимых дробей больше, и не факт, что получившийся числитель и знаменатель будут занимать меньше места, то работает алгоритм очень плохо.

Попробуем подогнать данные так, чтобы переплюнуть BZIP2. Для начала я сгенерировал 1024 числа типа float в диапазоне 0 .. 1.0, заполнив мантиссу случайными числами, случайной длины от 1 до 23 бит. Записал их в файл по 23 бита на число, получилось 2944 байта с энтропией 0.83 на бит. Сжимаем и получаем 2889 байт. Теперь в ход пойдёт бабушкинская магия, с непрерывными дробями возиться лень, так что только школярский брутфорс, только хардкор. Комп быстрый, числа маленькие.

Я взял семь бит для числителя и восемь для знаменателя. Если получилось найти (гениям про НОД знать не положено), то записываем 16 бит { 0, a:7, b:8 }, а если нет, то { 1, m:23 }, первая циферка - маркер. Получилось 2783 байта с энтропией 0.92. BZIP повержен :-D Если сохранять маркеры отдельно от чисел, в начале файла, то возможно его получится ещё сильнее сжать. Попробовал. 7z сжимает "упакованный" файл лучше, чем оригинальный.

Так что, принцип "анти-Дирихле": для любого самого тупого алгоритма можно подобрать данные так, чтобы он заработал.

Я очень давно не смотрю телевидение. Я его не смотрю даже, когда там показывают меня: просмотр превращается в болезненное ожидание неизбежных косяков и редакторских правок. Пользуясь случаем, хочу попросить, не присылайте мне пожалуйста ссылок на ролики и аудиозаписи. Без справки о том что вам оторвало руки, я их не открою. No pun intended, у меня есть знакомые, которым действительно сложно набрать текст, так что не ленитесь.

Новый Год я встречал в компании друзей, где зловредный прибор развлекает детей. Как следует обложив хуями прошедший 2019 год и заправив съеденные закуски текилой, я пошел договариваться с местным котом. Переговоры прошли в тёплой, дружественной обстановке и увенчались договором о дружбе и сотрудничестве. Договор немедленно вступил в силу. Обращение припиздента Какаразницы к хатоскрайцам мы с котом проспали, свернувшись калачиком на диване, и проснулись, точнее, нас бесжалостно разбудили, за тридцать секунд до полуночи.

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

Чтобы там не писали в стандартах мифических сообществ, ненависть - прекрасное чувство. Мне бы очень хотелось, чтобы вокруг малороссов и ватников (синонимы для приспособленцев и предателей) возникла пустота, вызванная естественной человеческой брезгливостью. А тех, кто сознательно участвовал в разрушении Украины ожидают фильтрационные мероприятия, поражение в правах, тюрьма и депортация в Белгородскую, Кубанскую и Ростовскую Народные Республики. Без сомнения украинцы должны объединиться для того, чтобы помочь метастазам совка гнить на свалке токсичных отходов цивилизации вместе с опухолью русского мира.

Нет никакой разницы, какие именно глупости говорит бывший президент Украины, если он делает это в Ростове. Нет никакой разницы, что думают боевики Павлов, Толстых и Мозговой, потому что они сдохли, и тем более безразлично, что у них написано в паспорте. После победы, бывшие управы СБУ, превращенные оккупантами в пыточные подвалы - разрушим, заасфальтируем, осветим и повесим вывеску "Здесь танцуют".

Верю, что так и будет. Ah ça ira, ah ça ira!

2015 был неплохой год. Приятно вспомнить. С Новым Годом!

Подвезли свежих откровений по Cambridge Analytica https://twitter.com/hindsightfiles Почитал комментарий Кристофера "Золотого дождя" Стила для Гардиан. Там https://www.theguardian.com/uk-news/2020/jan/04/cambridge-analytica-data-leak-global-election-manipulation есть упоминание, что в 2017 году услугами CA воспользовалась одна из украинских партий. Кто бы это мог быть? Думаю Юля Тимошенко. У неё как раз был "низкий старт" и её интернет-реклама заебала буквально всех, а точность таргетирования (с попытками прорекламироваться на ПиМ, например) ломала мозг опытным вебмастерам .

Скачал на пробу презентации по Болтону, и вот о чем я задумался: CA хвастается что они подняли CTR политической рекламы до 0.33% (по сравнению со средним значением 0.1% для Северной Америки) и при этом явку по отдельному округу на 8% (как эти цифры соотносятся между собой посчитайте сами). Если результаты настолько впечатляющие, то почему тогда CA вобще занималась политикой, а не напаривала нам подгузники в полоску, меховые коврики для мышек и колесики для аквариумов? В коммерческой рекламе не получается достичь тех же результатов? Специалисты по политической рекламе работают настолько плохо, что этот рынок более привлекателен, чем частный сектор?

Вопросы. Сплошные вопросы.

(1/2) Можно я ничего не буду писать ни про Иран, ни про оманскую красавицу? А то в первом случае бородатые могут обидется, а во втором, больного старца Кабуса бин Саида аль Саида может удар хватить досрочно, после того как он узнает какой к его министру пробрался лживый поблядун и зеленый проходимец, куда там тому доктору Еблану. Лучше ещё немного школьной алгебры на сон грядущий, мир на ближнем востоке нам всё-таки дорог как память (очень далеких предков) и алгебра немного проще тамошней политики.

После моих набегов в школьную программу ко мне стали приходить люди и задавать вопросы. А почему например не шифровать поверх TLS своим суперсекретным шифром? (трое таких было, да) В такие минуты я вспоминаю сержанта Хартмана, из врожденной ехидности так и тянет спросить: У твоих родителей живые дети есть? Но я же вежливый, так что напоминаю, если вы не доверяете RSA/DSA, EC(DH/DSA) внутри TLS, то почему вы собираетесь довериться им же, но снаружи? Или вот: "мы написали отличный мессенджер, который использует алгоритм Диффи-Хелмана". Не разбивайте к хуям моё любящее сердце, DH скоро исполнится пятьдесят лет, тем не менее, даже профессиональные разработчики умудряются там косячить до сих пор.

Так что, воскресная проповедь о примитивах и протоколах.

Скажите мне, что может быть проще RSA? Шифр состоит из одной операции cipher = text^e mod p*q, text = cipher^d mod p*q, так что e*d mod (p-1)(q - 1) = 1. Просто же. Ладно, ещё разок d = 1 / e, поэтому d * e = e * 1 / e = 1, и (x^e)^d = x^(e*d) = x^1 = x Тем не менее даже тут люди умудряются систематически наступать на грабли. Я недавно видел, как на одном из программистких форумов один мудачок умудрился продать алгоритм Эвклида за 2 BTC (это где-то пятнадцать тысяч баксов). Я ему даже немного завидую - наглость второе счастье. И он смог его продать, потому что покупатель вундервафли не знал как работает RSA.

Начнем с очень коротких сообщений. Я уже слышу тяжелые вздохи погромистов и крики "Я не такая!". А вот на модных блокчейн-выборах в Москве голос избирателя хранился, как короткое целое число. Между прочим закончились они беспорядками. О том как это влияет на Эль-Гамаля поищите у меня в ленте, а для RSA - просто катастрофа. Предположим, что у нас сообщение 3 и публичная экспонента (e) тоже 3, тогда c = 3^3 mod n = 27. И от того, что n у вас будет 4096 бит не поменяется ничего, в вычислениях оно участвовать не будет и результат останется 27, значит нужно просто извлечь кубический корень (обычный) и всё, текст расшифрован. Так что если вы шифруете какие-нибудь 128 битные числа, например симметричные ключи, то подумайте еще раз.

Второй хороший фокус ожидает авторов мессенджеров. В групповом часте одно и тоже сообщение нужно отправить всем участникам. Ключи (n1, 3), (n2, 3), (n3, 3) у них разные, а экспонента одна, и сообщение тоже одно. И тут нам приходит на помощь Китайская теорема об остатках. 1247 год. В Москве беженцы, в Парме бунт, а китайцы напоминают: N = n1 * n2 * n3; Ni = N / ni; di = Ni^-1 mod ni; x = c1*N1*d1 + c2*N2*d2 + c3*N3*d3 mod N, m = кубический корень из x, можете быстренько проверить ni = 41989, 50621, 53357; ci = 22565, 17881, 16518; di = 32790, 50353, 11972; x = 1030301; m = 101 И на размер ключей нам насрать, как и на разборки гвельфов с Фридрихом Вторым, а так же на то сосала ли Моника у Юсуфа бин Аляви бин Абдалы, тем пусть занимается исламский коммитех по нравственности.

Естественно, только в том случае если у модулей (ni) нет общих множителей (GCD(ni, nj) = 1). Если они есть, то всё гораздо, гораздо хуже. Если у n1 и n2 НОД не равен единице, то значит, что n1 = p * q1 и n2 = p * q2, q1 = n1 / p, q2 = n2 / p, так как числа факторизованы - разложены на множители p и q (а сложность алгоритма GCD O(log n), то есть для ключа из 4096 бит, он работает в среднем 4096 шагов), то дальше мы просто вычисляем секретные ключи d1 и d2 и расшифровываем не просто одно сообщение (в чем и заключается проблема RSA, а не в факторизации), а все сообщения. Уродец с форума как раз и предложил: давайте насобираем много-много открытых ключей и поищем НОД. Чтобы было понятно о числах какого порядка идёт речь, то количество атомов во Вселенной ~10^80, а количество простых чисел длиной 512 бит ~3.7 * 10^151

Так действительно бывает у IoT со слабыми генераторами слуачйных чисел https://factorable.net/weakkeys12.extended.pdf Число p у них одинаковое, а q разное, потому что между двумя числами в генератор случайных чисел подмешано время. Если бы не этот дурацкий фокус, то у них были бы одинаковые ключи. Наглядный пример того, как фантазии разработчика (два раза будет надежнее) не решают проблему, а маскируют её и отправляют в продакшн. Вершиной данного направления кодерской мысли я считаю какой-то вирус вымогатель, который генерировал ключи стандартным 32-битным генератором, а когда над горе-хакерами стали антивирусники смеяться, то они заменили srandom(time(NULL)) на srandom(md5(time(NULL))), и от смеха легли все. Если вы не понимаете почему, то и над вами тоже посмеются.

Для того, чтобы такого не происходило сообщение дополняют до необходимой длины. Примерно так 00 02 * всякое говно * 00 * текст (PKCS 1.5) или OAEP (PKCS 2.0) там всё немного сложнее, но RSA такая сука, что он malleable (то есть подвержен злонамеренным изменениям) и гомоморфен. Нет, шифр не превращается в охотника на особ своего пола в ночь полной луны, это значит, что f(x) * f(y) = f(x * y), что в случае RSA вполне очевидно, раз a^e * b^e = (a * b)^e. То есть примитив не обеспечивает семантическую стойкость (дав два известных сообщения m0 и m1, и получив шифротексты c0 и c1 можно отличить где был m0, а где m1) И если не дай бог ваша говнософтина выдаёт сообщение об ошибке "Invalid padding", то вы получите атаку Блейхенбахера (для PKCS 1.5) и Мангера (для PKCS 2.0)

(продолжение слеждует)

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

Так бывает. Сперва тебя взламывают хакеры Ukrainian Cyber Alliance и твою почту читает InformNapalm, а спустя какое-то время тебя задерживает Державна прикордонна служба України с фальшивым украинским паспортом и The Security Service of Ukraine начинает задавать неприятные вопросы. Просто так уж совпало. Бывают в жизни странные сближенья. https://informnapalm.org/38795-za-gratami-zhizn-i-priklyuc…/

О том что Гратова поменяли я узнал из материалов Слідство.Інфо https://informnapalm.org/ua/gratov-2020/ Я рад, что тогда удалось задержать террориста, и рад что благодаря задержанию и обмену выродка, кто-то из наших пленников смог вернуться домой. Однако, меня расстраивает то, что за те два года что "Саныч" провел в тюрьме ему так и не вынесли приговор. Несмотря на то, что доказательства террористической деятельности, и переписка боевика и мошенника были переданы украинским правоохранителям.

На месте российских спец. служб я бы присмотрелся внимательнее к Гратову: предатель и сепаратист не может не предавать. Я также обращаюсь к Службе Информации и Безопасности Республики Молдова и к Ambasada Republicii Moldova în Ucraina/Посольство Молдови в Українi обратите внимание на Гратова, возможно что он попытается бежать из РФ в Приднестровье. Его уже один раз задерживали в Кишиневе. Террорист Гратов участвовал в войнах, из-за которых многим гражданам Украины и Молдовы пришлось покинуть свои дома.

Раз уж Гратова пока не обняла земля, то я хочу, чтобы он умер в изгнании и нищете.