Пару недель назад NIST (институт по стандартам) назвал участников третьего раунда для стандарта пост-квантовой криптографии (PQC). Новость не привлекла особенного внимания. А между тем, процесс любопытный, особенно той запутанностью, которую он вызывает в головах граждан. Многие неверно полагают, что квантовый компьютер похож на обычный, просто по тем же дорожкам бегут нолики и единички одновременно. Главное дорожки сделать из иттербия, а не из меди. Или что это вообще компьютер. Учитывая, что мы находимся в самой читающей стране в мире с передовой наукой, то (пусть меня заранее простят математики, физики и криптографы за возможные ошибки и недопустимые упрощения), но начнём мы со "стрелочек" или - векторов.
Все вы их рисовали на уроках геометрии, в тетрадках в клеточку и учились складывать их между собой и умножать на обычные числа (скаляры, чтобы не путать с вектором, вектор - не число). Те же самые стрелочки, если переместить их в начало координат можно задать двумя числами, координатами “второго конца”, например (1, 2) или (0.5, 18). Их можно складывать (a, b) + (c, d) = (a + b, c + d), или умножать на число n * (a, b) = (n * a, n * b) - тогда стрелочка не меняет направления и становится длиннее или короче. Множество всех возможных векторов (все возможные числа в скобочках через запятую) называется векторное пространство. Если чисел два, то и размерность пространства тоже два. Векторное пространство - алгебраический объект, и если разные вещи можно представить одинаково, то можно поймать просветление.
Вектор (2, 2) можно разложить на сумму двух векторов и множители, например через (0, 1) и (1, 0), как 2 * (0, 1) + 2 * (1, 0) = (2 * 0, 2 * 1) + (2 * 1, 2 * 0) = (0 + 2, 2 + 0) = (2, 2), а вот выразить вектор (0, 1), используя (1, 0), скалярное умножение и сложение - не получится. Они линейно-независимы. Два вектора перпендикулярны и состоят из нулей и единиц - ортонормированный базис двумерного векторного пространства, заданного над полем действительных чисел. У стрелочки есть ещё и длина, её называют модулем вектора и она равна |(a, b)| = √(a^2 + b^2) Только звучит страшно. Прямоугольник. Пифагор. От геометрии за восьмой класс ещё никто не умирал (не считая отдельных древних греков, для которых знакомство с алогосом √2 закончилось не самым лучшим образом).
Отвлечемся от стрелочек и решим квадратное уравнение x^2 + 1 = 0. Результат - корень квадратный из минус единицы. Долгое время люди считали такие числа с̶а̶т̶а̶н̶и̶н̶с̶к̶о̶й̶ ̶е̶б̶а̶н̶и̶н̶о̶й̶ бессмыслицей, пока не научились с их помощью получать реальные, кошерные результаты. Так появились комплексные числа вида a + b*i, где i тот самый корень. Две компоненты числа не смешиваются. Они “разные”. Их можно складывать вычитать, умножать на действительное число. И записывать парами (a, b). Рисовать в виде стрелочек (на комплексной плоскости). Раскладывать на запчасти по базису (1, 0) и (0, i) (и не только, базисы бывают всякие, к чему мы ещё вернёмся) Вектор можно задать длиной и углом. А еще умножать (x, y) * (u, v) = (x * u - y * v, x * v + y * u). Тоже вектор. С умножением векторное пространство замкнулось в алгебру комплексных чисел.
Если бит - обычный выключатель “вкл.” или “выкл.”, то кубит может одновременно находится в двух состояниях |0> и |1> Состояние |\psi> = a*|0> + b*|1>, где a и b комплексные числа. Суперпозиция. Мешок Шредингера, в котором спрятан полуживой от ужаса кот. Вероятность, что кубит после измерения окажется в состоянии |0> равна |a|^2 и в состоянии |1> = |b|^2. Сумма вероятностей равна единице. |a|^2 + |b|^2 = 1 Где |a| - модуль вектора “a”, его мнимая часть - фаза (заходя в морько вы можете встретить волну в ее верхней или нижней точке, а может даже посередине). Вы можете запутать несколько кубитов в единую систему и перевести ее в суперпозицию, количество различных вариантов, которые можно закодировать таким способом 2^n. Если n = 5. То возможных результатов 32. Если n = 128, то вы удивитесь насколько их много.
Все вы их рисовали на уроках геометрии, в тетрадках в клеточку и учились складывать их между собой и умножать на обычные числа (скаляры, чтобы не путать с вектором, вектор - не число). Те же самые стрелочки, если переместить их в начало координат можно задать двумя числами, координатами “второго конца”, например (1, 2) или (0.5, 18). Их можно складывать (a, b) + (c, d) = (a + b, c + d), или умножать на число n * (a, b) = (n * a, n * b) - тогда стрелочка не меняет направления и становится длиннее или короче. Множество всех возможных векторов (все возможные числа в скобочках через запятую) называется векторное пространство. Если чисел два, то и размерность пространства тоже два. Векторное пространство - алгебраический объект, и если разные вещи можно представить одинаково, то можно поймать просветление.
Вектор (2, 2) можно разложить на сумму двух векторов и множители, например через (0, 1) и (1, 0), как 2 * (0, 1) + 2 * (1, 0) = (2 * 0, 2 * 1) + (2 * 1, 2 * 0) = (0 + 2, 2 + 0) = (2, 2), а вот выразить вектор (0, 1), используя (1, 0), скалярное умножение и сложение - не получится. Они линейно-независимы. Два вектора перпендикулярны и состоят из нулей и единиц - ортонормированный базис двумерного векторного пространства, заданного над полем действительных чисел. У стрелочки есть ещё и длина, её называют модулем вектора и она равна |(a, b)| = √(a^2 + b^2) Только звучит страшно. Прямоугольник. Пифагор. От геометрии за восьмой класс ещё никто не умирал (не считая отдельных древних греков, для которых знакомство с алогосом √2 закончилось не самым лучшим образом).
Отвлечемся от стрелочек и решим квадратное уравнение x^2 + 1 = 0. Результат - корень квадратный из минус единицы. Долгое время люди считали такие числа с̶а̶т̶а̶н̶и̶н̶с̶к̶о̶й̶ ̶е̶б̶а̶н̶и̶н̶о̶й̶ бессмыслицей, пока не научились с их помощью получать реальные, кошерные результаты. Так появились комплексные числа вида a + b*i, где i тот самый корень. Две компоненты числа не смешиваются. Они “разные”. Их можно складывать вычитать, умножать на действительное число. И записывать парами (a, b). Рисовать в виде стрелочек (на комплексной плоскости). Раскладывать на запчасти по базису (1, 0) и (0, i) (и не только, базисы бывают всякие, к чему мы ещё вернёмся) Вектор можно задать длиной и углом. А еще умножать (x, y) * (u, v) = (x * u - y * v, x * v + y * u). Тоже вектор. С умножением векторное пространство замкнулось в алгебру комплексных чисел.
Если бит - обычный выключатель “вкл.” или “выкл.”, то кубит может одновременно находится в двух состояниях |0> и |1> Состояние |\psi> = a*|0> + b*|1>, где a и b комплексные числа. Суперпозиция. Мешок Шредингера, в котором спрятан полуживой от ужаса кот. Вероятность, что кубит после измерения окажется в состоянии |0> равна |a|^2 и в состоянии |1> = |b|^2. Сумма вероятностей равна единице. |a|^2 + |b|^2 = 1 Где |a| - модуль вектора “a”, его мнимая часть - фаза (заходя в морько вы можете встретить волну в ее верхней или нижней точке, а может даже посередине). Вы можете запутать несколько кубитов в единую систему и перевести ее в суперпозицию, количество различных вариантов, которые можно закодировать таким способом 2^n. Если n = 5. То возможных результатов 32. Если n = 128, то вы удивитесь насколько их много.
Квантовые вычисления - “теория вероятностей с комплексными числами”. Вероятность каждого состояния от 0,0,0,0… до 1,1,1,1,... = 1 / 2^n. Когда вы измерите чему на самом деле равны кубиты, то получите случайное число. Если примените функцию к регистру из кубитов, то получите случайное значение функции. Функции воздействующие на состояние называются вентилями, а в математике операторами и задаются матрицами (то же что и вектор только квадратное, если умножить вектор на матрицу, то получится ещё один вектор). Например оператор Адамара превращает состояние |0> в суперпозицию (|0> + |1>) / √2 (привет пифагорейцам) - нолик и единичка после измерения “выпадают” с равной вероятностью.
Больше всего это похоже на то, как будто вы светите лазерной указкой с расстояния в десять километров на солнечную панель, а потом измеряете заряд в каждой ячейке. Указкой можно вертеть в разные стороны, подносить ближе и дальше и тоже самое можно делать в обратном порядке. Все действия обратимы. Такие матрицы называются унитарными. “Вращаются” при этом не операторы, а вектора состояний, к которым их применяют. Квантовый компьютер “вычисляет” произведение матриц в многомерном векторном пространстве над полем комплексных чисел. В реальности это может выглядеть как атом редкоземельной хуйни, охлаженный почти до абсолютного нуля, по которому пиздячат лазером, и он “хочет” вернуться в “классическое” состояние за доли секунды. Ад для инженера.
Не очень похоже на проводочки, микросхемы и параллельные универсальные вычисления. Так как?
Два самых известных алгоритма для квантовых компьютеров - алгоритм Шора (разложение чисел на множители, дискретные логарифмы, группы точек эллиптических кривых) и алгоритм поиска Гровера (сопоставление входов и выходов “черного ящика”, например симметричного шифра). С него и начнем. Для начала нам потребуется оракул. Функция, которая на нужном нам входе даёт “1”, а на остальных “0”. В случае с шифром, “вход” - ключ. Оракул позволяет отличить то что мы ищем от всего остального. На обычном компьютере придётся по очереди пробовать все варианты. А для квантового компьютера - это одно из возможных состояний, которое он пытается пометить, чтобы искать иголку среди зубочисток, а не зубочистку в зубочистках. А потом усилить ее. Чтобы иголка стала длиннее. А следовательно, станет выше вероятность того, что система (после того как мы её в конце “потрясем”) окажется именно в этом состоянии.
Чем больше попыток, тем выше вероятность. Статистика. То что сложность задается степенью числа N, а не числом в степени N, не значит что это просто. Для симметричных шифров Гровер сокращает количество бит вдвое. И если ключ 128 бит, то сложность Гровера 2^64, а не 2^128 как на классическом компьютере, то есть √N Потому рекомендуется использовать ключи 256 бит. Больше не обязательно, алгоритм оптимален, ни на обычном, ни на квантовом компьютере ничего лучше сделать нельзя (если шифр надежен и люди не придумали как его ломать как-нибудь по-другому).
В свою очередь Шор ничего не раскладывает на множители. Есть такая штука преобразование Фурье. Ему на вход можно подать волны, например звуковые. Самую отвратительную песню про “черные глаза” или не менее тошнотворный голос президента Зеленского. На выходе получим тоже самое только разложенное по частотам, а не по времени. Дергающиеся столбики в плеере, которые показывают сколько в Зеленском в каждую данную секунду басовитого мычания, среднечастотного хрипения и боевых визгов собаки чау-чау. Причем здесь множители и простые числа?
Больше всего это похоже на то, как будто вы светите лазерной указкой с расстояния в десять километров на солнечную панель, а потом измеряете заряд в каждой ячейке. Указкой можно вертеть в разные стороны, подносить ближе и дальше и тоже самое можно делать в обратном порядке. Все действия обратимы. Такие матрицы называются унитарными. “Вращаются” при этом не операторы, а вектора состояний, к которым их применяют. Квантовый компьютер “вычисляет” произведение матриц в многомерном векторном пространстве над полем комплексных чисел. В реальности это может выглядеть как атом редкоземельной хуйни, охлаженный почти до абсолютного нуля, по которому пиздячат лазером, и он “хочет” вернуться в “классическое” состояние за доли секунды. Ад для инженера.
Не очень похоже на проводочки, микросхемы и параллельные универсальные вычисления. Так как?
Два самых известных алгоритма для квантовых компьютеров - алгоритм Шора (разложение чисел на множители, дискретные логарифмы, группы точек эллиптических кривых) и алгоритм поиска Гровера (сопоставление входов и выходов “черного ящика”, например симметричного шифра). С него и начнем. Для начала нам потребуется оракул. Функция, которая на нужном нам входе даёт “1”, а на остальных “0”. В случае с шифром, “вход” - ключ. Оракул позволяет отличить то что мы ищем от всего остального. На обычном компьютере придётся по очереди пробовать все варианты. А для квантового компьютера - это одно из возможных состояний, которое он пытается пометить, чтобы искать иголку среди зубочисток, а не зубочистку в зубочистках. А потом усилить ее. Чтобы иголка стала длиннее. А следовательно, станет выше вероятность того, что система (после того как мы её в конце “потрясем”) окажется именно в этом состоянии.
Чем больше попыток, тем выше вероятность. Статистика. То что сложность задается степенью числа N, а не числом в степени N, не значит что это просто. Для симметричных шифров Гровер сокращает количество бит вдвое. И если ключ 128 бит, то сложность Гровера 2^64, а не 2^128 как на классическом компьютере, то есть √N Потому рекомендуется использовать ключи 256 бит. Больше не обязательно, алгоритм оптимален, ни на обычном, ни на квантовом компьютере ничего лучше сделать нельзя (если шифр надежен и люди не придумали как его ломать как-нибудь по-другому).
В свою очередь Шор ничего не раскладывает на множители. Есть такая штука преобразование Фурье. Ему на вход можно подать волны, например звуковые. Самую отвратительную песню про “черные глаза” или не менее тошнотворный голос президента Зеленского. На выходе получим тоже самое только разложенное по частотам, а не по времени. Дергающиеся столбики в плеере, которые показывают сколько в Зеленском в каждую данную секунду басовитого мычания, среднечастотного хрипения и боевых визгов собаки чау-чау. Причем здесь множители и простые числа?
Я уже как-то рассказывал о том как работает #RSA. Напомню, что действия происходят в группе Z/nZ,* с порядком (количеством элементов) \phi(n) = (p - 1) * (q - 1), где p и q - простые числа. И у этой группы есть внутренняя структура, подгруппа со сложением \phiZ,+, состоящая из чисел \phi, 2*\phi, 3*\phi, … Её значения периодически повторяются, так что есть такое r, что f(x + r) = f(x) mod \phi Если получится найти период r (тут-то и нужен Фурье), то мы узнаем число \phi, и тогда для того чтобы найти числа p и q, достаточно решить квадратное уравнение p^2 - (n + 1 - \phi) * p + n = 0 Задача называется “поиск скрытой абелевой подгруппы” (AHSP). В квантовом компьютере преобразование Фурье работает гораздо быстрее.
Однако, отнюдь не любую задачу можно свести к скрытым подгруппам или поиску. Давайте-ка подумаем, а что будет если умножить вектор не на действительное, а на целое число? Тогда “конец стрелочки” должен заканчиваться на пересечении линий тетрадного листа, вместо точек, которые могут оказаться где угодно. Получилась решетка…
Однако, отнюдь не любую задачу можно свести к скрытым подгруппам или поиску. Давайте-ка подумаем, а что будет если умножить вектор не на действительное, а на целое число? Тогда “конец стрелочки” должен заканчиваться на пересечении линий тетрадного листа, вместо точек, которые могут оказаться где угодно. Получилась решетка…
Мне позвонил Kostiantyn и рассказал о том, что часть людей из тех, кто подписал петицию к USAID хотят отозвать свои голоса (петиция о том, что даже свиньи лучше разбираются в апельсинах, чем министерство цифровой трансформации в кибербезопаности, и что выступать координатором или бенефициаром многомилионного проекта цифрожижа не может). Такое вот "частно-государственное партнерство", когда министерство бегает по бизнесам и угрожает им из-за действий их сотрудников. Тех кто снял свою подпись я прекрасно понимаю - работа есть работа и никто не хочет ссориться с государством. Однако, у меня горит. Если бы в МЦТ просто сидели неучи, это еще можно было бы как-то перетерпеть, но теперь они становятся агрессивными. Входят во вкус. Угрозы пошли. Я по-прежнему глубоко убеждён в том, что Федорова, Выскуба и Ко необходимо гнать от "кибер" поганой метлой.
О, а вот и отечественного отслеживания контактов подвезли, животное Шмыгаль вещает:
"Минздрав, МВД, Минцифры и другие ответственные органы должны создать эффективную систему отслеживания контактов людей, которые заболели COVID-19. Эти эпидемиологические расследования должны быть системными, с жестким контролем за самоизоляцией"
Отслеживание контактов не для домашнего ареста, и не для того, чтобы мусора поганые следили за людьми (не их собачье дело), а для того, чтобы предупредить человека о том что он находится в зоне риска, тест сделать, обратиться к врачу.
Но нет. "Расследования", OMFG! Мусорская дия продолжает бурить дно. Не взлетит конечно, но крови попортит изрядно. #ACAB #злодия
"Минздрав, МВД, Минцифры и другие ответственные органы должны создать эффективную систему отслеживания контактов людей, которые заболели COVID-19. Эти эпидемиологические расследования должны быть системными, с жестким контролем за самоизоляцией"
Отслеживание контактов не для домашнего ареста, и не для того, чтобы мусора поганые следили за людьми (не их собачье дело), а для того, чтобы предупредить человека о том что он находится в зоне риска, тест сделать, обратиться к врачу.
Но нет. "Расследования", OMFG! Мусорская дия продолжает бурить дно. Не взлетит конечно, но крови попортит изрядно. #ACAB #злодия
ОМОН (сущ., неодуш., мн. ч.; укр. Беркут, бел. АМАП) - сучьи выблядки, которым нравится по приказу диктаторов убивать и калечить сограждан #ЖывеБеларусь #ACAB
Как наглядно показывает опыт Беларуси, России и Китая (там сейчас блокируют TLS 1.3), блокировки и фильтрация контента нужны исключительно с одной целью - держать людей в подчинении. Угрожать, чтобы приучить к самоцензуре. Блокировать диссидентов. И в крайних случаях оставить людей без связи, чтобы разрушить самоорганизацию. Никаких других целей у гебни и мусорья не было и нет. Играют в игры с Интернетом исключительно авторитарные режимы. Украина (пока) гибридный. И противозаконные решения СНБО, введенное в силу указами президента и решения подментованных судов нужно отменить, проекты законов предусматривающие цензуру - запихнуть депутангам в законотворческий орган, вмешательство в работу сети со стороны государства - запретить раз и навсегда.
(Напоминалка. Купить протухший домен из "санкционного" списка. Прописать A на сайт Кіберполіція, Офіс Президента України, Служба безпеки України. Блокировки по IP - это так просто)
(Напоминалка. Купить протухший домен из "санкционного" списка. Прописать A на сайт Кіберполіція, Офіс Президента України, Служба безпеки України. Блокировки по IP - это так просто)
Мне показали нечеловечески прекрасное.
Извечная мечта всех долбоёбов, чтобы работу вместо них делал компьютер. "Раскрывать преступления не выходя из кабинета", "с помощью Экселя" (по специальному допуску). И это проблема. Мусора не умеют раскрывать преступления. Они не умеют даже сфабриковать дело (чтобы убедительно сделать фейк, нужно хоть раз увидеть настоящее).
Следующий шаг после "не выходя из кабинета", начать придумывать преступления, чтобы героически их раскрывать. В пресс-релизе они еще хвастаются тем, как собираются злоупотреблять своими и без того немаленькими полномочиями.
Кстати, три года назад НАВС оставили в Интернете беспарольный диск, со списком личного состава, копией сайта и пиратским ZverCD. https://cutt.ly/vd38gP5 Более того, сервер несколько раз был взломан хакерами (по настоящему, там же лежали куски эксплоита SambaCry).
Решил посмотреть, сделали ли они из той истории какие-нибудь выводы? Да, как же. Там и конь не валялся. Так что Національна академія внутрішніх справ вы бы лучше вместо фантазий про Эксель-пинкертонов и массовой противозаконной слежке навели порядок на своих собственных серверах. Для начала.
Извечная мечта всех долбоёбов, чтобы работу вместо них делал компьютер. "Раскрывать преступления не выходя из кабинета", "с помощью Экселя" (по специальному допуску). И это проблема. Мусора не умеют раскрывать преступления. Они не умеют даже сфабриковать дело (чтобы убедительно сделать фейк, нужно хоть раз увидеть настоящее).
Следующий шаг после "не выходя из кабинета", начать придумывать преступления, чтобы героически их раскрывать. В пресс-релизе они еще хвастаются тем, как собираются злоупотреблять своими и без того немаленькими полномочиями.
Кстати, три года назад НАВС оставили в Интернете беспарольный диск, со списком личного состава, копией сайта и пиратским ZverCD. https://cutt.ly/vd38gP5 Более того, сервер несколько раз был взломан хакерами (по настоящему, там же лежали куски эксплоита SambaCry).
Решил посмотреть, сделали ли они из той истории какие-нибудь выводы? Да, как же. Там и конь не валялся. Так что Національна академія внутрішніх справ вы бы лучше вместо фантазий про Эксель-пинкертонов и массовой противозаконной слежке навели порядок на своих собственных серверах. Для начала.
Я уже несколько раз подумывал пересказать историю Майка Стея, про zip-архив и триста тысяч долларов в биткоинах. Однако, для того чтобы она заиграла в красках, пришлось немного порыться в линейной алгебре и архивах. Майк Стей - исследователь, который лет двадцать назад занимался восстановлением данных.
В то время Майкрософт не торопился покупать лицензии у RSA и ссориться с АНБ. В их продуктах использовалась "экспортная" 40-битная криптография. Ломалось всё настолько быстро и чтобы не разачаровывать заказчиков, фирма где работал Майк изображала "кропотливый взлом", чтобы буквы пароля мигали и неторопливо появлялись на экране по одной.
В том числе Майк придумал атаку на шифрование в архиваторе ZIP (если внутри архива пять файлов или больше) и написал об этом статью ("ZIP Attacks with Reduced Known Plaintext", FSE 2001) А не так давно к нему в линкедине подошел некий русский (тут я насторожился) и спросил: сможет ли он взломать пароль от архива, в котором лежит не пять, а два файла?
Стей ответил, что сложность взлома в таких условиях порядка 2^73 (ключ в ZIP 96 бит) и для этого понадобятся ресурсы стоимостью около ста тысяч долларов. К его великому удивлению потенциальный заказчик согласился и объяснил, что в архиве лежат кошельки стоимостью в триста тысяч долларов.
При чем здесь линейная алгебра? В старых версиях архиватора ZIP используется потоковый шифр. Он начинает с определенного состояния, шифрует соль и пароль пользователя, и потом выдаёт длинную гамму, которая выглядит как случайные числа. Складывает гамму с открытым текстом и так получается шифр.
Его состояние состоит из трех слов по 32 бита. Два из них k0 и k2 - CRC32, а k1 - TLCG усеченный линейный конгруентный генератор. Звучит очень страшно, но на самом деле: y = a*x + b mod m, где "mod m" - остаток от деления. А усеченный он потому, что за один раз выдаёт не всё свое состояние, а только восемь бит. И нужно по нескольким значениям генератора узнать что у него внутри?
Из-за ошибок в реализации шифра, часть состояния шифра течет, но по-прежнему остается гигантское пространство для перебора. И тогда в ход пошли решетки. Решетка - комбинация векторов, в которой коэффициенты заданы целыми числами. Очень похоже на векторное пространство, но решетка дискретна. У неё может быть базис (вектора с помощью которых можно представить любой другой вектор) и они не уникальны.
Бывает "хороший" базис (вектора короткие и близкие к ортогональным), а бывают "плохие" - представьте, что вам нужно найти все точки решетки, пользуясь десяти метровой линейкой и транспортиром с отметкой в семь с половиной градусов. Задача поиска ближайшего вектора к произвольной точке (CVP) худо-бедно решается для "хороших" базисов и очень больно для "плохих". Особенно, когда речь идёт не о "стрелочках" на плоскости, а о векторах с размерностью 200+
Людей давно интриговали уравнения и многочлены - линейные, квадратные, кубические: x^5 - x^2 + 1, x^2 + 2x -1337, и тому подобные. Если записать коэффициенты через запятую, то получится вектор (1, 0, 0, 1, 0, 1) и (1, 2, -1337) со сложением, вычитанием и другими полезными вещами. Базис соответственно (x^5, x^4, x^3, x^2, x^1, x^0) и (x^2, x^1, x^0) - квадраты с кубами не смешиваются. И мы начинаем подбираться к ZIP и биткоинам.
TLCG (и не только его, но и многие другие задачи) можно "раскрутить", если решить систему уравнений a^{i-1}*x_1 - x_i ≡ 0 mod m, так как речь идёт о целых числах, то получается решетка с большим и "плохим" базисом. На неё можно натравить LLL (алгоритм Ленстры-Ленстры-Ловаса), чтобы получить базис получше. Всё что верно для "плохого" базиса (L), верно и для "хорошего" (B). Если L*x ≡ 0 mod m, то и B*x ≡ 0 mod m. Решетка одна и та же, базисы разные.
В то время Майкрософт не торопился покупать лицензии у RSA и ссориться с АНБ. В их продуктах использовалась "экспортная" 40-битная криптография. Ломалось всё настолько быстро и чтобы не разачаровывать заказчиков, фирма где работал Майк изображала "кропотливый взлом", чтобы буквы пароля мигали и неторопливо появлялись на экране по одной.
В том числе Майк придумал атаку на шифрование в архиваторе ZIP (если внутри архива пять файлов или больше) и написал об этом статью ("ZIP Attacks with Reduced Known Plaintext", FSE 2001) А не так давно к нему в линкедине подошел некий русский (тут я насторожился) и спросил: сможет ли он взломать пароль от архива, в котором лежит не пять, а два файла?
Стей ответил, что сложность взлома в таких условиях порядка 2^73 (ключ в ZIP 96 бит) и для этого понадобятся ресурсы стоимостью около ста тысяч долларов. К его великому удивлению потенциальный заказчик согласился и объяснил, что в архиве лежат кошельки стоимостью в триста тысяч долларов.
При чем здесь линейная алгебра? В старых версиях архиватора ZIP используется потоковый шифр. Он начинает с определенного состояния, шифрует соль и пароль пользователя, и потом выдаёт длинную гамму, которая выглядит как случайные числа. Складывает гамму с открытым текстом и так получается шифр.
Его состояние состоит из трех слов по 32 бита. Два из них k0 и k2 - CRC32, а k1 - TLCG усеченный линейный конгруентный генератор. Звучит очень страшно, но на самом деле: y = a*x + b mod m, где "mod m" - остаток от деления. А усеченный он потому, что за один раз выдаёт не всё свое состояние, а только восемь бит. И нужно по нескольким значениям генератора узнать что у него внутри?
Из-за ошибок в реализации шифра, часть состояния шифра течет, но по-прежнему остается гигантское пространство для перебора. И тогда в ход пошли решетки. Решетка - комбинация векторов, в которой коэффициенты заданы целыми числами. Очень похоже на векторное пространство, но решетка дискретна. У неё может быть базис (вектора с помощью которых можно представить любой другой вектор) и они не уникальны.
Бывает "хороший" базис (вектора короткие и близкие к ортогональным), а бывают "плохие" - представьте, что вам нужно найти все точки решетки, пользуясь десяти метровой линейкой и транспортиром с отметкой в семь с половиной градусов. Задача поиска ближайшего вектора к произвольной точке (CVP) худо-бедно решается для "хороших" базисов и очень больно для "плохих". Особенно, когда речь идёт не о "стрелочках" на плоскости, а о векторах с размерностью 200+
Людей давно интриговали уравнения и многочлены - линейные, квадратные, кубические: x^5 - x^2 + 1, x^2 + 2x -1337, и тому подобные. Если записать коэффициенты через запятую, то получится вектор (1, 0, 0, 1, 0, 1) и (1, 2, -1337) со сложением, вычитанием и другими полезными вещами. Базис соответственно (x^5, x^4, x^3, x^2, x^1, x^0) и (x^2, x^1, x^0) - квадраты с кубами не смешиваются. И мы начинаем подбираться к ZIP и биткоинам.
TLCG (и не только его, но и многие другие задачи) можно "раскрутить", если решить систему уравнений a^{i-1}*x_1 - x_i ≡ 0 mod m, так как речь идёт о целых числах, то получается решетка с большим и "плохим" базисом. На неё можно натравить LLL (алгоритм Ленстры-Ленстры-Ловаса), чтобы получить базис получше. Всё что верно для "плохого" базиса (L), верно и для "хорошего" (B). Если L*x ≡ 0 mod m, то и B*x ≡ 0 mod m. Решетка одна и та же, базисы разные.
Есть вектор старших битов генератора y, то его состояние (x) можно представить как x = y + z, где z неизвестные младшие биты. L*x = m*k, B*x = m*k (для неизвестного k), B * (y + z) = m * k, B *z = m * k - B * y, так как базис B короткий, то и значение k будет *меньше* и его можно попробовать вычислить, как ⌊(B*y)/m⌉. Пример в комментариях. Что и сделал Майк Стей. Написал коротенькую программку для sage и... не получил ни одного верного результата.
И тут он догадался посмотреть на разницу между правильным значением и вычисленным. И каждый раз получал один из 36 векторов. Ему больше не нужно было подбирать значения LCG грубой силой, а достаточно сравнить попадают ли решения-кандидаты в один из заранее известных результатов. Перебирать от одного до 36 гораздо проще, чем от одного до 4 миллиардов. Программа работала десять дней и... снова облом.
После исправления всех глюков, программа нашла 96-битный ключ от архива и биткоины были спасены. Почему я напрягся как электричество? Я немного погуглил и выяснил, что в 2011 году на одном из форумов пользователь выложил программу для "резервного копирования кошельков" на Java. Вместо бэкапа прожка заливала кошель в почтовый ящик и стирала его с компьютера (бывшего) владельца.
Из-за криворукости мошенника внутри оказались пароли к почтовому ящику, на который уходили кошельки. Часть украденных биткоинов удалось вернуть. Там же нашлись письма на другие почтовые ящики (Tolsi.ru@gmail.com), а часть битка ушла на кошелек пользователя Tolsi. Сергей "Tolsi" Толмачев - программист на Java. Большой энтузиаст биткоинов. В 2011 году он пообещал "вернуться в биткоин через пять лет". Именно он-то и заказал у Майка Стея в 2016 году взлом архива, от которого он забыл пароль.
И тут он догадался посмотреть на разницу между правильным значением и вычисленным. И каждый раз получал один из 36 векторов. Ему больше не нужно было подбирать значения LCG грубой силой, а достаточно сравнить попадают ли решения-кандидаты в один из заранее известных результатов. Перебирать от одного до 36 гораздо проще, чем от одного до 4 миллиардов. Программа работала десять дней и... снова облом.
После исправления всех глюков, программа нашла 96-битный ключ от архива и биткоины были спасены. Почему я напрягся как электричество? Я немного погуглил и выяснил, что в 2011 году на одном из форумов пользователь выложил программу для "резервного копирования кошельков" на Java. Вместо бэкапа прожка заливала кошель в почтовый ящик и стирала его с компьютера (бывшего) владельца.
Из-за криворукости мошенника внутри оказались пароли к почтовому ящику, на который уходили кошельки. Часть украденных биткоинов удалось вернуть. Там же нашлись письма на другие почтовые ящики (Tolsi.ru@gmail.com), а часть битка ушла на кошелек пользователя Tolsi. Сергей "Tolsi" Толмачев - программист на Java. Большой энтузиаст биткоинов. В 2011 году он пообещал "вернуться в биткоин через пять лет". Именно он-то и заказал у Майка Стея в 2016 году взлом архива, от которого он забыл пароль.
👍2
В пятницу министр цифровой трансформации Федоров провел пресс-конференцию, на которой любезно поделился своими планами по беспощадной и всеобъемлющей цифровизации проебываемой экономики, а заодно представил своего советника Дениса Алейникова из прекрасной страны, всем известной своими креветками и редкими сырами, синеокой сестры Беларуси. Я включил звук погромче и слушал, и слушал повизгивая, с широко закрытыми глазами, так что мне приснился сон…
(Все совпадения несут в себе злые намерения и отнюдь не случайны)
С утра по Киеву ходил худой человек с красными от цифровизации глазами и выскубленной до синевы мордой. Он раздавал у метро написанные от руки объявления:
4 августа, в помещении ООО “Вектор” состоится лекция на тему “Блокчейнизация как стремительный драйвер окончательной цифровизации третьего цикла хайпа по Гартнеру”. Лекцию читает гросс-министр оптимизации и цифровых наук Федор Михельсон.
Вход рубль, выход два.
Сам министр тоже не терял времени. Он заарендовал спейс за неназванную сумму бюджетных денег и перебросился на вертолетную площадку беглого любителя страусов. В Векторе сидел грустный ФОП-айтишник, безмерно страдающий от недостатка державной заботы и любви, и задумчиво листал уголовный кодекс.
- Гросс-министр оптимизации всего! - заявил Федор присаживаясь за стол. - устраиваю у вас цифровизацию, страну в страпоне и нейро-искусственный аграрно-биологический интеллект на блокчейне!
Глаза единственного представителя креативной индустрии округлились до пределов дозволенных природой, а сам он как-то сжался и уменьшился в размерах, потому что за подобными предложениями обычно следовал удар тараном в дверь, и люди с неприятно тупыми лицами и автоматами наперевес начинают рыться в личных вещах и ломать дороговалютную технику своими обезьяньими от кривизны руками.
Представитель убежал. Федор осмотрел помещение. На стенах висели фотографии страусов, оставшиеся от бывшего владельца. На столе рядом с кодексом лежала запыленная папка с подписью “Форма номер 17. Предельно допустимые показатели джиттера в оптических сетях”. Что такое джиттер Федор не знал, но заранее проникся уверенностью, что в оффшоре его мечты без тщательнейших замеров джиттера никак не обойтись. Креативная индустрия вернулась с дюжиной граждан и гражданок разных возрастов, которые подходили по очереди здороваться.
Киевские айтишники прониклись к Федору сыновней любовью. Федора несло. Он почувствовал прилив новых сил и цифровых идей.
- Вы не поверите, - говорил он, - как далеко двинулась цифровая мысль. Вы знаете Илон Маск дошел до пошлых вещей, с ним невозможно стало работать. Цифровой мир в беспокойстве. Почему в провинции нет смарт-мысли? Например, вот ваше ООО “Вектор”. Так и называется ООО “Вектор”. Скучно, девушки! Почему бы вам, в самом деле, не назвать её как-нибудь хайпово! Назвали бы “Snatch, Inc”, “GoogLag”, Дия-Сити или хотя бы "Вектор плюс". Хорошо было бы! Звучно!
Идея имела успех. ООО “Вектор” общим решением собрания учредителей немедленно переименовали в “Дия-Сити”. Каждый достал из папки “Завантаження” свою секретную цифровую подпись и квалифицированно приложился.
(Все совпадения несут в себе злые намерения и отнюдь не случайны)
С утра по Киеву ходил худой человек с красными от цифровизации глазами и выскубленной до синевы мордой. Он раздавал у метро написанные от руки объявления:
4 августа, в помещении ООО “Вектор” состоится лекция на тему “Блокчейнизация как стремительный драйвер окончательной цифровизации третьего цикла хайпа по Гартнеру”. Лекцию читает гросс-министр оптимизации и цифровых наук Федор Михельсон.
Вход рубль, выход два.
Сам министр тоже не терял времени. Он заарендовал спейс за неназванную сумму бюджетных денег и перебросился на вертолетную площадку беглого любителя страусов. В Векторе сидел грустный ФОП-айтишник, безмерно страдающий от недостатка державной заботы и любви, и задумчиво листал уголовный кодекс.
- Гросс-министр оптимизации всего! - заявил Федор присаживаясь за стол. - устраиваю у вас цифровизацию, страну в страпоне и нейро-искусственный аграрно-биологический интеллект на блокчейне!
Глаза единственного представителя креативной индустрии округлились до пределов дозволенных природой, а сам он как-то сжался и уменьшился в размерах, потому что за подобными предложениями обычно следовал удар тараном в дверь, и люди с неприятно тупыми лицами и автоматами наперевес начинают рыться в личных вещах и ломать дороговалютную технику своими обезьяньими от кривизны руками.
Представитель убежал. Федор осмотрел помещение. На стенах висели фотографии страусов, оставшиеся от бывшего владельца. На столе рядом с кодексом лежала запыленная папка с подписью “Форма номер 17. Предельно допустимые показатели джиттера в оптических сетях”. Что такое джиттер Федор не знал, но заранее проникся уверенностью, что в оффшоре его мечты без тщательнейших замеров джиттера никак не обойтись. Креативная индустрия вернулась с дюжиной граждан и гражданок разных возрастов, которые подходили по очереди здороваться.
Киевские айтишники прониклись к Федору сыновней любовью. Федора несло. Он почувствовал прилив новых сил и цифровых идей.
- Вы не поверите, - говорил он, - как далеко двинулась цифровая мысль. Вы знаете Илон Маск дошел до пошлых вещей, с ним невозможно стало работать. Цифровой мир в беспокойстве. Почему в провинции нет смарт-мысли? Например, вот ваше ООО “Вектор”. Так и называется ООО “Вектор”. Скучно, девушки! Почему бы вам, в самом деле, не назвать её как-нибудь хайпово! Назвали бы “Snatch, Inc”, “GoogLag”, Дия-Сити или хотя бы "Вектор плюс". Хорошо было бы! Звучно!
Идея имела успех. ООО “Вектор” общим решением собрания учредителей немедленно переименовали в “Дия-Сити”. Каждый достал из папки “Завантаження” свою секретную цифровую подпись и квалифицированно приложился.
- Блокчейн, знаете ли вы что такое блокчейн? Он двигает вперёд не только экономику, но и культуру. Айти обогащает страну! Если вы согласитесь на мой проект, то спускаться на пристань вы будете по виртуальным лестницам. Дия-Сити станет центром Европы. Что вы раньше слышали о Бангалоре? Говно, коровы и курсы обучения си с крестами. А теперь этот городишко богат и знаменит своей утечкой мозгов в разные стороны. Сколково в Москве! ПВТ в Минске! Успех, грандиозный успех, даже новостные сайты не открываются, потому что они больше никому не нужны и новости происходят прямо на улицах. Поэтому я и говорю, нам нужно устроить цифровую супер-державу, минуя доебанную ПСО и олигархами энергетику. Дийови платить деньги не будут. Они будут их по-лу-чать. Это же все чрезвычайно просто. Ведь в оффшор съедутся любители айти со всего мира. Сотни тысяч людей, богато обеспеченных людей, будут стремиться в Дия-Сити. Поднятие сельского хозяйства в радиусе на тысячу километров: гостей нужно снабжать — овощи, фрукты, икра, смузи и кофе. IBM, Amazon, Microsoft бросят свою силиконовую долину, чтобы переехать в Дия-Сити и хайповать на блокчейне! Нейро-искусственный квантумный интеллект! Биотехнологическое СЕО! Хайп. Оптимизация!
Ослепительные перспективы развернулись перед айтишниками…
(Раздаётся оглушительный удар тарана в двери. В помещение врывается СБУ, налоговая, инспекция электросвязи и другие ответственные за цифровизацию лица, чья ответственность давно и окончатиельно превысила их компетентность)
Ослепительные перспективы развернулись перед айтишниками…
(Раздаётся оглушительный удар тарана в двери. В помещение врывается СБУ, налоговая, инспекция электросвязи и другие ответственные за цифровизацию лица, чья ответственность давно и окончатиельно превысила их компетентность)
Хотя я занимаюсь всевозможным хайтеком, я очень консервативен и у меня есть обоснованные сомнения в том, как в Украине работает инфраструктура открытых ключей. Потому для того, чтобы поучаствовать в выборах (а я как и многие наши сограждане не собираюсь всю жизнь сидеть на одном месте), то я завтра пойду в отделение государственного реестра избирателей и изменю место голосования. Список оффлайновых отделений тут https://www.drv.gov.ua/ords/portal/!cm_core.cm_index?option=ext_organ_ved&prejim=3&pmn_id=105 Если совсем уж не хочется или не получается ходить ногами, то тоже самое можно сделать в онлайне. А если у вас нет ЭЦП, то и получить её в ПриватБанке онлайн (что неправильно, но может упростить вам жизнь), а как это сделать можно прочитать на странице Д7 https://www.facebook.com/426507261147892/posts/1047058002426145 Сделать нужно до девятого числа, не откладывайте.
Одного такого билета вагнеровца достаточно, чтобы собрать ТСК в Раде https://itd.rada.gov.ua/services/Petition/Index/8464?aname=published
Чекистско-мусорская падаль хочет сделать вам "чебурашку" как на России. Это не 6688, а гораздо, гораздо хуже. Законопроект 4004 предусматривает установку #СОРМ - тотальная, полностью бесконтрольная прослушка коммуникаций, включая Интернет. За наш с вами счет. Законопроект 4002 при этом усилит цензуру, потому что предусматривает уголовную ответственность за нарушение санкций (что правильно), но у нас "санкциями" называется и цензура Интернета в том числе. Там еще много вкусного, вроде необходимости доказывать законность происхождения виртуальных активов (доказывается вина, а не невиновность), и обязанность провайдеров полностью сотрудничать с органами. Если проекты примут, то про Интернет в Украине и какой-либо связанный с ним бизнес можно просто забыть. Раз и навсегда.