криптография

OpenAI опубликовали решения 372 открытых математических задач, которые десятки лет не могли решить ученые-математики.

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

2. А свежие публикации OpenAI показывают, что машина порой использует «инопланетные приемы» (как знаменитый 37-й ход AlphaGo). То есть движется к решению не тем путем, каким обычно идут люди.

3. При этом, множество решений и доказательств «уродливые», не элегантные, людям потребуется много времени и усилий, чтобы проверить и понять построения машин. Если бы статьи такого качества прислал человек — их бы почти наверняка не стали бы публиковать. И вообще, открытые задачи в математике — это что-то вроде маяков на берегу, к которым ты идешь по прекрасным холмам, изучая окрестности. Большой ли смысл прилететь туда на вертолете?

4. Реакции математиков на анонс очень разные — от энтузиазма (там могут быть столько новых идей!) до депрессии (они за день уничтожили мою область исследований). Вот довольно занимательный сборник 100+ реакциий.

❧

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

Статья Пола Локхарда «Плач математика», ясно показывает (и даже дает почувствовать), что в школьной «математике» нет ни капли настоящей математики и какая она на самом деле красивая, простая и увлекательная.

Особенно рекомендую её тем, кто считает, что он «гуманитарий», и кто ненавидит математику ещё со школы. По математическому обряду, она везде в PDF, который невозможно нормально читать с телефона, так что собрал страничку для удобного чтения: английский оригинал и хороший перевод. Рекомендую!

Кстати, Кейти была экспертом при подготовке Вассенаарских договоренностей, которые определяют, какой софт считается оружием и как его контролировать.

Я в этой связи вспоминаю, как правительство США пыталось запретить публичное распространение криптографии, которую они не могли взломать.

Правительство классифицировало стойкие алгоритмы как вооружение и запрещало их экспорт.

Например, в середине 90-х, было две разных версии браузера Netscape: одна с нормальным 128-битным шифрованием, доступная только в США и Канаде, а остальной мир должен был довольствоваться 40-битным шифрованием.

Активисты, которые боролись с этим безумием, в числе прочего, распространяли алгоритмы и даже исходники RSA и PGP в виде книги. Потому что книги защищены первой поправкой к конституции США о свободе слова.

Вот активистская футболка тех времен, с алгоритмом RSA и крупным предупреждением «эта футболка классифицируется как вооружение и не может быть экспортирована из США или показана иностранцу».

Интересная и очень хорошо написанная статья про гомоморфное шифрование.

Это когда сервер выполняет вычисления поверх зашифрованной информации, не расшифровывая её.

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

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

То есть сервис производит полезные действия с вашими данными, не имея возможности их прочитать, сохранить, продать, потерять.

Теоретически, это работает не только с фотографиями, но и с медицинской, финансовой, избирательной и другой чувствительной информацией.

Теоретически — потому что на практике алгоритмы, работающие с такими данными, в тысячи раз медленнее, чем обычные алгоритмы, а сами данные получаются в сотни раз больше по объёму.

Под капотом там довольно сложная математика, с красивой интуитивной частью, рекомендую почитать оригинал. Придумали её ещё в 1970-х, но первый рабочий алгоритм смогли запрограммировать только в 2011.

Первая версия алгоритма обрабатывала один бит информации за 30 минут. За последние 5 лет алгоритмы и железо ускорились в триллион (1012) раз, и теперь операции с этим видом шифрования всего в 1000 раз более ресурсоёмкие, чем обычные.

Есть гипотеза, что гомоморфное шифрование продолжит ускоряться и дальше, и в какой-то момент мы сможем пользоваться онлайн-сервисами без необходимости делиться с ними личными данными. Например: отправили медицинскому сервису свои анализы или ДНК, и он поставил диагноз, не то что не сохраняя наши персональные данные, но даже не получив возможности их прочитать. Магия!

Виталик Бутерин, гениальный создатель Эфира, считает, что если 2010-е годы были эпохой криптографии эллиптических кривых, то 2020-е — эпоха гомоморфного шифрования.

Удивительное открытие для меня — это то, что уже сейчас есть продакшен-системы, которые применяют гомоморфное шифрование в реальных задачах — например, Live Caller ID Lookup айфонов, который помогает бороться со спам-звонками, сохраняя приватность.

Сегодня для подавляющего большинства «чувствительных задач» проще настроить защищённый компьютер для исполнения «приватных вычислений», но математика и технологии очень красивые, рекомендую как прекрасное чтение на выходные для технарей.

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

Как связаны дорогие и редкие железки и банковские карты, которые есть у каждого в кармане? Зачем аппаратные ключи безопасности, если нам всё равно приходится помнить десятки паролей?

Разбираемся в новом эпизоде подкаста с Сергеем Агафьиным, экспертом в области аппаратной криптографии.

Слушайте и подписывайтесь: Apple, Google, Яндекс, Spotify, Castbox, Overcast, веб-версия.

Криптография — одна из самых сложных и интересных областей программирования и математики. Часто в IT есть правильное решение. Запрограммировал всё четко и задача решена условно на вечно.

В шифровании — не так. Всегда есть противоположная сторона, противник, который пытается взломать код и расшифровать наши сообщения.

Цена таких игр бывает очень высокая — миллиарды долларов и человеческие жизни. Вспомните Алана Тьюринга, который взломал немецкую шифровальную машину Enigma и сильно изменил ход Второй мировой войны.

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

Гость — Евгений Алексеев, начальник отдела криптографических исследований КриптоПро.

Слушайте и подписывайтесь: Apple, Google, Яндекс, Spotify, Castbox, Overcast, веб-версия.

На алгоритме Диффи-Хеллмана держатся современная криптография и интернет.

Он позволяет двум незнакомым сторонам создать общий секрет по незащищенному каналу. То есть вы разговариваете без утайки, но при этом в результате разговора оба владеете информацией, которой точно нет ни у кого подслушивающего. Обычно говорят, что алгоритм позволяет «обменяться секретом», но это не совсем правда, речь всё-таки о создании нового секрета.

Вот одна картинка, которая помогла мне понять принцип работы алгоритма. Перевод мой специально для мамы. Мама, ты поймешь 100%.

Исследователи из CWI и Гугла представили практическую атаку на SHA1.

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

SHA1 придумали в 1995 году в NSA (том самом агенстве национальной безопасности США) и с тех пор он активно использовался для большинства HTTPS-сертификатов в интернете. В 2005-м году исследователи обнаружили слабость в алгоритме, позволявшую теоретически произвести атаку на коллизии — подобрать второй файл с таким же отпечатком SHA1, что и у заданного первого файла. Начиная с 2010 сертификаты начали по-умолчанию использовать SHA2 или SHA3 — более свежие версии алгоритмов.

Но это всё были умные научные статьи, где пропускаешь формулы, потому что доверяешь научному сообществу и смотришь только на выводы.

Тут же можно самому скачать две разные PDF-ки, у которых совпадают SHA1. Довольно мощное впечатление.

Теперь модно давать крупным атакам имя и делать персональные сайты-объяснения. Встречайте https://shattered.io/

Мне кажется очевидным, что криптографию нужно использовать готовую, но как мы видим на примере телеграма — с этим согласны не все 👀 https://eprint.iacr.org/2015/1177.pdf

Хорошая вводная статья о том, сколько всего нужно держать в голове при программировании криптографии http://loup-vaillant.fr/articles/rolling-your-own-crypto

Кстати, приложенная классическая картинка отвечает на популярный вопрос «как разобраться в *** за 21 день»