Если вы не верите мошеннику, то с чего бы верить его цифровой подписи?
Не могу без боли смотреть на украинских жижитальных неучей. Всё-таки с образованием у нас полная и окончательная катастрофа. Цифровой министр не знает что такое мем (нет, мем не смешная картинка, а аналог гена из мира идей, концепцию придумал Ричард Докинс) и не знает даже основ криптографии, без которой никак не обойтись во всех этих ваших смартфонах и цифровых трансформаторах.
Для хипстеров смартфон - магическая тумбочка, в которую сложены ништяки цивилизации, даже боюсь представить, что будет, если спросить их о том как работает Интернет. Не удивлюсь, если они думают, что он сам собой заводится в проводах и маленькие эльфы таскают 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 Так как дроби образуют группу и со сложением и с умножением, то такая конструкция называется "поле". Группы могут содержать другие группы в качестве подгрупп (кубик-рубика часть группы 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 способов закосячить криптоалгоритм и превратить его в полнейшее говно. О чем стоило бы поговорить отдельно.
Вся это нужно для того, чтобы зашифровать текст открытым ключом, а расшифровать закрытым. Знание открытого ключа, шифротекста, алгоритма и параметров шифрования не позволяет вскрыть переписку или подделать подпись. И конечно же, даже если господин Федоров всё это прочитает и поймёт хотя бы половину, то это не означает что я ему поверю хоть на йоту. Если вы не верите мошеннику, то с чего бы верить его цифровой подписи?
Что помешает Федорову и Дубилету подсадить вам Авакова в смартфон вместе "Дией"? Что ему помешает подделать результаты выборов? Что помешает жижитальным трансформатором распылить ответственность за подделку документов на такие маленькие кусочки, что крайних просто не останется? Для ответа на этот вопрос уравнений не придумано. Никакие модные слова, произносимые цифровыми проходимцами (и которые они сами не понимают) не заставят меня им поверить.
