Content Oriented Web
Make great presentations, longreads, and landing pages, as well as photo stories, blogs, lookbooks, and all other kinds of content oriented projects.
Математика тайны, или введение
в теорию шифрования

«И что бы смогла сделать устрица со своим секретом, будь он у нее? Сидела бы у себя в грязи и глупо хихикала?»
Деннет Д. Сознание объясненное.
Поэтому эволюцию коммуникации следует рассматривать как коммуникацию стратегическую, которая мотивирована скорее необходимостью обмана и манипуляции, а не скоординированного поведения – эволюционировал необходимо образующийся в результате такой потребности разрыв между действительными целями и намерениями респондента, и теми, которые имело смысл транслировать на «аудиторию».
Существо, транслирующее всю имеющуюся у него информацию о своих состояниях и намерениях всем без исключения слушателям, гарантированно погибнет.
Формированию такого разрыва должны были, прежде всего, способствовать ландшафты, в которых могло стать осмысленным понятие тайны, поскольку тайна – это не просто что-то известное вам и не известное другим: чтобы корректно говорить об обладании некоторой тайной, вам необходимо знать, что другие этого не знают, и иметь возможность контролировать данный факт.
Виртуальные ландшафты Всемирной Паутины, таким образом, явились естественным продолжением более традиционных коммуникативных пространств, в которых проблемы конфиденциальности, целостности и удостоверения источника информации также ставились и как-то решались уже в глубокой древности. Можно считать, что криптография как техника защиты текста возникла почти одновременно с письменностью, а способы тайного письма были известны уже цивилизациям Месопотамии, Индии и Египта – хотя их техники и не были в узком смысле слова математическими.
один из видов шифра подстановки, в котором каждый символ открытого текста заменяется символом, расположенным в алфавите на каком-то фиксированном числе позиций левее или правее. В частности, считается, что Юлий Цезарь в секретной переписке со своими генералами для шифрования использовал сдвиг на три позиции влево:
Классическим примером одного из ранних шифров является так называемый шифр Цезаря, или сдвиг Цезаря –
Столь же простым и столь же уязвимым является шифр перестановки, при котором символы не заменяются на другие по каком-либо правилу, а переставляются местами.
В особенности, перед частотным анализом – поскольку в каждом языке та или иная буква алфавита имеет вполне определенную частоту употребления, то зашифрованные символы таким образом относительно легко распознаются.
Древнейшим инструментом для перестановочного шифрования была скитала (жезл) – палочка определенного диаметра, с намотанной на ней пергаментной лентой, на которую затем наносился текст:
Будучи размотанной, лента содержала буквы сообщения, переставленные между собой местами на расстояние, равное длине окружности с диаметром палочки. Прочитать такое сообщение мог любой, обладающий палочкой такого же диаметра.
Именно этот разрыв и следует считать протоформой того «личного рабочего пространства», которое мы теперь именуем сознанием.

Все это были примеры шифрования с симметричным ключом – одно и то же правило (одна и та же палочка), или ключ используется в этом случае как для шифровки, так и для расшифровки сообщения, что рождает ряд характерных для этого вида шифрования проблем:
необходимость в отдельном секретном канале или в доверенном третьем лице, посредством которого ключ шифрования/дешифрования может быть передан от одного участника секретной коммуникации к другому;
если образована коммуникационная сеть
из N участников, то каждый участник может иметь различные правила кодирования своих сообщений при общении с каждым из остальных N − 1 участников, что создает так называемую проблему управления ключами – решение которой также, как правило, берет на себя специальное доверенное третье лицо;
поскольку одним и тем же секретным ключом владеют две и более сторон, шифрование с симметричным ключом не допускает эффективной реализации услуг электронной подписи и ​​неотказуемости (non-repudiation) – обеспечения невозможности отрицания пользователем, выполнившим какие-либо действия, факта их выполнения – в частности, отрицания отправителем информации факта ее отправления и/или отрицания получателем информации факта ее получения.
Все перечисленные проблемы очень изящно решает более современный тип шифрования – шифрование с ассиметричным, или открытым ключом.
В случае асимметричного шифрования каждый участник безопасной коммуникации создает пару ключей (e, d) – при этом только ключ дешифрования d (от англ. decryption – дешифрование) держится в секрете, тогда как ключ шифрования e (от англ. encryption – шифрование) остается в открытом доступе.
Все современные системы шифрования с открытым ключом в своей основе опираются на неподатливость (intractability) той или иной теоретико-числовой проблемы – математической задачи, теоретически решаемой, но требующей для своего решения огромного (неполиномиального – как говорят сами математики) компьютерного времени.
Самый, пожалуй, распространенный алгоритм RSA (аббревиатура от фамилий Rivest–Shamir–Adleman) использует предположительную вычислительную сложность факторизации (разложения на множители) числа, являющегося произведением двух больших простых чисел.
Подробнее об этом читайте здесь.
Идея алгоритма состоит в следующем:
случайным образом выбираются два больших простых числа p и q заданного размера (например, по 1024 бит каждое), и вычисляется их произведение n = pq;
числа p и q сохраняются в тайне, а число n предоставляется в открытый доступ;
Теперь нам понадобится немного фактов из теории чисел.
a b (mod m)
Cравнимость чисел a и b по модулю m записывают как
И есть в теории чисел такая важная функция – функция Эйлера φ(n) которая каждому натуральному числу n сопоставляет количество натуральных чисел, не превышающих n и взаимно простых с ним.
Заметим, что если n – простое, то все не превышающие его числа взаимно просты с ним, то есть их n − 1 штук.
Удивительный факт теории чисел состоит в том, что для любых взаимно простых чисел a и n:
Доказательство этого замечательного факта мы здесь опустим, хотя в самое ближайшее время обязательно к нему вернемся, так как это (наряду с малой теоремой Ферма) самый настоящий бриллиант теории чисел.
Давайте заглянем, так сказать, «под капот» этого алгоритма и посмотрим, что за математика стоит за ним.
Ранее мы уже писали.. о сравнениях двух целых чисел по некоторому модулю: напомним, что два целых числа a и b сравнимы по модулю m, если их разность a − b делится на m. Или, что-то же самое, число a дает в остатке b при делении на m. Т. е. a = mk + b.
φ(n)
a
1 (mod n).
Теперь, если n = pq, где p и q – простые, то числа, не превышающие n, и не являющиеся с ним взаимно простыми, делятся или на p, или на q.
Первые имеют форму pk, где k = 1, . . . ,q − 1.
То есть их q − 1 штук, а тех, которые делятся на q, по тем же соображениям, p − 1 штук.
Значит, в данном случае φ(n) = (n − 1) − (q − 1) − (p − 1) = pq − 1 − q + 1 − p + 1 = (p − 1)(q − 1).

То есть, для любого числа a, не делящегося на p или q, верно, что
1 (mod pq),

(p − 1)(q − 1)
a
и можно также показать, что
≡ a (mod pq)

1 + m(p − 1)(q − 1)
a
уже для любых чисел a и m.
Ну действительно, обе части сравнения можно возводить в одну и ту же степень и домножить на одно и то же целое, поэтому если
Осталось только домножить обе части на a:
a ∙ a
m(p − 1)(q − 1)
≡ 1 ∙ a (mod pq), или a

1 + m(p − 1)(q − 1)
a (mod pq).

Но вернемся к идее алгоритма шифрования:

далее выбирается число e: 1 e φ(n), взаимно простое с φ(n), которое также предоставляется в открытый доступ.
Таким образом, открытым ключом будет пара (n, e), с помощью которой шифрование выполняется следующим образом:
Сообщение a (строка какого-то кода, номер кредитной карты и т. п. – в любом случае 0 ≤ an − 1 ) переводится в число c (ciphertext) по правилу
Опять-таки, использованные свойства сравнений и обоснование того, что в альтернативной формулировке утверждения можно не требовать взаимной простоты a и n, мы опустим, но предлагаем вам самим с этим повозиться.
m
m(p − 1)(q − 1)
(p − 1)(q − 1)
a
≡ 1

= 1 (mod pq).

≡ 1 (mod pq), то a

то a

≡ 1 (mod pq),

≡ 1 ∙ a (mod pq),

или a

Согласитесь, что это относительно несложно.
Комментарий
Блестяще, не правда ли?
Гораздо более неочевидным является тот факт (и в этом состоит главная идея алгоритма RSA), что по числу b также легко восстановить a,
зная φ(n), а точнее – хранящиеся в секрете простые числа p и q, так как в данном случае, как мы помним φ(n) = (p − 1)(q − 1).
Итак, секретным ключом по сути является тройка чисел (p, q, d), где 1 d φ(n), причем
de ≡ 1 (mod φ(n)).
Такое число d называется обратным по модулю к числу e, в данном случае – по модулю φ(n).
Его часто обозначают как e...., и такое число существует в том и только в том случае, если НОД (e, φ(n)) = 1. Что и требовалось при выборе e на предыдущем шаге алгоритма.
Теперь заметим, что поскольку de = 1 (mod φ(n)), то это означает, что de дает в остатке единицу при делении на φ(n), или de = 1 + m(p − 1)(q − 1)!
Но тогда, зная d, и получив от корреспондента зашифрованное сообщение с, правило дешифрования становится простым

Действительно, мы немедленно восстанавливаем исходное сообщение a, поскольку
Комментарий
−1

Ну давайте что-нибудь сами зашифруем и расшифруем для убедительности:

Допустим, вы хотите сообщить мне трехзначный код безопасности своей кредитной карты CVV2, зашифровав свое сообщение при помощи открытого ключа. Ваш код: 100.
Я выбираю какие-то два простых числа p и q: пускай p = 13, q = 19
(напоминаем, что в реальности простые числа p и q выбираются очень большими – только в этом случае факторизация их произведения является алгоритмически трудной задачей)
Тогда n = pq = 13 ∙ 19 = 247 и φ(247) = (13 − 1)(19 − 1) = 12 ∙ 18 = 216
Теперь мне нужно выбрать число e, взаимно простое с 216. Я выбираю e = 7.
Ключ для зашифровки сообщения (247, 7) готов, и я по совершенно открытому каналу передаю его вам.
Шифрование состоит в возведении вашего числа в степень e = 7 и вычислении его значения по модулю n = 247
То есть, вообще говоря, вам нужно решить сравнение
100 ≡ c (mod 247) относительно c.
7
Это нетрудно сделать с помощью калькулятора или даже «руками»:
7d ≡ 1 (mod 216)
относительно d.

(Действительно, 7 ∙ 31 = 217 = 1 ∙ 216 + 1, поэтому все сходится.)

Получив от вас зашифрованное сообщение c, мне для расшифровки нужно возвести его в степень d и вычислить значение с . mod(247).

d

Заметьте, что слагаемые и сомножители, кратные модулю сравнения, мы всегда можем заменить нулем – в этом прелесть модулярной арифметики!
Итак,

Ну вот мы и дешифровали ваш CVV2







7
100 ≡ 35 (mod 247)
−1
То есть,


и зашифрованное сообщение c = 35 вы тоже мне спокойно передаете по открытому каналу, поскольку для расшифровки нужно вычислить d = e .. , но по модулю φ(n), а для этого надо знать p и q, которые известны только мне. Мне же не составит труда вычислить, что такое d = 31, решив сравнение


Посмотрим, как это можно сделать:

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

Читайте больше наших статей по подписке всего за 1!

Есть вопросы по материалу?

Вы можете задать их в нашем специальном чате. Мы поможем разобраться в теме лучше

Понравилась статья?