Salus populi suprema lex (988) (don_katalan) wrote,
Salus populi suprema lex (988)
don_katalan

Пожалуй, стоит провести небольшой креш-курс по основам современных технологий

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

Для хипстеров смартфон - магическая тумбочка, в которую сложены ништяки цивилизации, даже боюсь представить, что будет, если спросить их о том как работает Интернет. Не удивлюсь, если они думают, что он сам собой заводится в проводах и маленькие эльфы таскают 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 способов закосячить криптоалгоритм и превратить его в полнейшее говно. О чем стоило бы поговорить отдельно.

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

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

Tags: дебилы, зеленский, піар, україна
Subscribe

promo don_katalan december 29, 2014 14:39 115
Buy for 50 tokens
Расшифровка секретного плана адмиистративно-территориального устройства России после ее распада От гуляющих по сети различных вариантов "государственного" устройства будущего российских территорий отличается наличием территорий в совместном управлении, возвратом исторических территорий…
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments