Category: математика

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

Скажем, обычный RSA для таких целей уже не подходит, так как вся сила RSA в том, что разложение 4096-битного числа на два простых множителя — это экстремально ресурсоёмкая задача, на которую даже на современных суперкомпьютерах понадобится срок, сравнимый с возрастом наблюдаемой Вселенной.

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

А теперь Микрософт объявил, что первый из алгоритмов, ML-KEM (чорт, мне нравится это название, КЕМ!) уже встроены в стандартную библиотеку шифрования их ОС. ML-KEM — алгоритмом Шора уже не ломается.

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

Т.к. дату в формате ММДДГГГГ обычно пишут только в США, специальный день календаря 3.14 получается сугубо американским.

Ну, тогда вот вам шутку на математическом английском.

Объясняю, если кто недопонял:

Квадратный корень из минус единицы — это комплексное число, которое записывают буквой i.
Двойка в третьей степени — это восемь (eight), произносится точно так же как слово ate.
Сигма — это сумма (sum), произносится как слово some.
Ну и само число Пи, которое в английском Pi, и произносится не как Pee, а как слово Pie (пирог).

Так что получаем фразу, которая звучит как i ate some pie (я съел кусок пирога). Математический кавай.

Обожаю такие шутки.

Математик заходит в забегаловку, берёт столик на двоих. К нему подходит неопрятная официантка.

–Что будете заказывать?
–Я закажу бифштекс, но я также хочу разыграть своего коллегу, который тут будет с минуты на минуту. Вот сто долларов; когда он придёт, я задам вам вопрос, а вы ответите “икс в кубе поделить на три”, хорошо?
–Конечно.

Официантка берёт деньги и уходит.

За столик присаживается коллега математика.

–Привет!
–Привет! Слушай, тут такое классное место, и даже обслуживающий персонал умный. Вот смотри!

Математик останавливает проходяющую мимо официантку.

–Скажите мне, каков будет неопределённый интеграл функции икс в квадрате?
–Икс в кубе поделить на три плюс константа.

PS: шутка прекрасно переводится на все языки, матан — язык универсальный.

Для начала немного теории.

Как хранятся пароли в операционных системах, вебсайтах, и т.д. Не открытым текстом, разумеется. Они хранятся в виде хешей. Хеш — это строка определённой длины, получаемая при обработке ввода (пароля в данном случае) хеш-функцией. До недавнего времени (да и сейчас кое-где) использовался алгоритм MD5. Так, хеш MD5 слова “password” представляет собой строку 5f4dcc3b5aa765d61d8327deb882cf99.

Поэтому когда ты логинишься на вебсайт, пароль обрабатывается алгоритмом MD5, и сравниваются хеши. Если на выходе 5f4dcc3b5aa765d61d8327deb882cf99, то всё нормально. Винда делает немного по-другому: хеш генерируется прямо на клиенте, и пересылается не пароль, а сразу хеш. Это цуцуть безопаснее. Ещё хеш солят, но про это в другой раз.

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

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

Сломаем MD5 хеш 5f4dcc3b5aa765d61d8327deb882cf99:

hashcat.exe -m 0 -a 3 hash.txt ?l?l?l?l?l?l?l?l

И меньше, чем за секунду всё сломано.

На моей уже старенькой 1070GTX поиск хешей MD5 происходит со скоростью около 8 миллиардов комбинаций в секунду.

Даже если сменить пароль на более сложный, типа P@$$w0rd, то 8-значный пароль взламывается в обозримые сроки, даже на не очень новом железе — за несколько дней.

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

А недавно я попробовал сломать бекап смартфона Apple. Для тёщи, которая раскокала телефон вдребезги, успев, правда, незадолго до сделать ему бекап. Но вот беда — она забыла пароль от бекапа! Она только знала, что пароль восьмизначный.

Хеш пароля для айфонного бекапа берётся в файле Manifest.plist. Этот файл скармливается вот этому сайту, например, и тебе дают хеш.

Так вот хеш там — какой-то проприетарный. И имеет настолько высокую вычислительную сложность, что на моей видеокарте котохеш перебирает комбинации со скоростью… 83 варианта в секунду. Надо отдать должное чувству юмора разработчиков котохеша: во время работы оно показывает, сколько времени осталось до перебора всех вариантов. Так вот в данном случае оно говорит, что работа программы закончится после следующего Большого Взрыва 😀

Вот так вот Плотнег лососнул тунца.

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

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

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

Топоры-вилы-факелы отставить.