1970-90. Развитие технологий открытых ключей шифрования и надежных хеш-функций.

2009. Выпуск первой криптовалюты биткоин (BTC)

2018. Фанат виртуальной многопользовательской (количество одновременно играющих игроков достигает $ 900\, 000$) игры Counter-Strike приобрел невероятно редкую винтовку с автографом известного профессионального игрока за $ 61\, 000 $ USD (см. сайт магазина)

01.04.2024. Существует $ > 10\, 000 $ криптовалют. Обменный курс: $ 1 $ BTC = $ 69\,968.1 $ USD

Модулярная арифметика (арифметика остатков): степенная функция $$ f(x)=x^{n} \pmod{M} \ , $$ где $ M=p $ или $ M=p_1p_2 $, а $ p,p_1, p_2 $ простые числа. Достаточно большие: $ \sim 10^{60}, \sim 10^{100}, \sim 10^{150} $

$ f(x) $ определена на множестве $ \{0,1,\dots,M-1 \} $ и отображает это множество в себя.

1. Сравнительно просто вычисляется (стандартный персональный компьютер).

2. Генератор случайных чисел: если уже известно $ f(x_1) $, то предсказать в каких пределах лежит $ f(x_2) $ невозможно (даже если $ x_2 $ рядом с $ x_1 $).

Односторонняя функция: при $ M=p_1p_2 \sim 10^{300} $ обратную функцию к $ f(x) $ реально найти только если известны сомножители $ p_1 $ и $ p_2 $ (математическая задача факторизации большого целого числа не имеет алгоритмического решения, реализуемого за на всех компьютерах мира за разумное время).

Вывод. Любой человек в состоянии сгенерировать себе ключи шифрования, абсолютно стойкие к взлому. (И это — головная боль всех спецслужб мира!).

Ключи алгоритма RSA: $$ p_1,p_2, {\mathbf E}, {\mathbf D} \, . $$ Числа $ p_1,p_2, {\mathbf D} $ держатся в секрете, числа $ {\mathbf E} $ и $ M= p_1p_2 $ публично известны.

Шифрование открытого текста $ x \in \{0,1,\dots,M-1\} $ (цифрового его представления) производится по правилу: $$ c= x^{\mathbf E} \pmod{M} $$ и его может выполнить любой человек планеты.

А вот дешифрование может произвести либо создатель ключа: $$ x=c^{\mathbf D} \pmod{M} \ , $$ либо тот, кто сможет разложить число $ M $ на множители.

Создатель шифра может совершить еще одну операцию над открытым текстом $ x \in \{0,1,\dots,M-1\} $. Он может применить к нему функцию дешифрования: $$ s=x^{\mathbf D} \pmod{M} \, . $$ Результатом будет число $ s \in \{0,1,\dots,M-1\} $, представляющее собой абсолютно случайную последовательность цифр. Если это число посылается любому человеку планеты, то последний может применить к нему открытый ключ шифрования $ (\mathbf E, M) $ (который известен публично!). Если результатом действия $$ \left(\widetilde s \right)^\mathbb E \pmod{M} $$ будет осмысленный текст, то сообщение $ \widetilde s $ считается принадлежащим именно предполагаемому отправителю, т.е. создателю ключа $ (\mathbf E, \mathbf D, M) $.

Число $ s $ называется (электронно)-цифровой подписью (ЭЦП) сообщения $ x $.

Тем самым, созданный ключ $ (\mathbf E, \mathbf D, M) $ может служить представителем его создателя в интернете. С одной стороны, решая проблему безопасности переписки, а, с другой стороны, обеспечивая аутентификацию сообщения (т.е. принадлежность присланного сообщения именно создателю ключа).

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

Что делать если сообщение $ x $ оказывается слишком длинным, т.е. $ x > M $? Тогда к нему применяют дополнительную операцию — хеширование (или просто хеш). Разбивают на небольшие блоки: $$ x=x_1 \mid x_2 \mid \dots \mid x_k $$ и вычисляют контрольную сумму: $$ h(x) = x_1 + x_2 + \dots + x_k \pmod{\widetilde M} \, $$ где $ \widetilde M \in \mathbb N $ — произвольное, достаточно большое, но $ \widetilde M < M $. После этого отсылке подлежит пара $$ (x, \left[ h(x) \right]^{\mathbf D} \pmod{M}) \, . $$ Получатель, получив пару $ (\widetilde x, \widetilde s) $ вычисляет $ h(\widetilde x) $ и сравнивает это число с $$ \widetilde s^{\mathbf E} \pmod{M} \, . $$ В случае совпадения считается, что сообщение пришло именно от предполагаемого отправителя, и пришло неповрежденным.

На практике используют более сложные хеши, например рекурсивно вычисляемую функцию Девиса-Мейера: $$ h(x)= H_k, \quad \mbox{ где } \ H_j= H_{j-1} \oplus \left[ H_{j-1}^{x_j} \pmod{\tilde M} \right] \quad \mbox{ для } \ j\in \{1,\dots,k \}\ . $$ Здесь значение $ H_0\in \{2,\dots, \tilde M -1\} $ берется произвольным фиксированным, а $ \oplus $ означает операцию побитного сложения по модулю $ 2_{} $ чисел, представленных в двоичной системе счисления.

Цель: усложнить возможность подделки любой стороной корреспонденции, а именно, отравителем, получателем или же посторонним злоумышленником. Функция $ h(x) $ уже не будет однозначной на множестве $\{0,1,\dots, \widetilde M-1\} $. Обязательно будут существовать коллизии: $$ h(x_1)=h(x_2) \quad \mbox{при} \ x_1\ne x_2 \, . $$ Важно, чтобы эти коллизии были трудно обнаруживаемыми, т.е. чтобы функция $ h(x) $ вела себя как генератор случайных чисел.

(Англ.) ledger. Другой перевод — банковская книга (гроссбух).

Недостатки. Высокая банковская комиссия за транзакционные услуги. и отсутствие анонимности (как самих услуг, так и вовлеченных клиентов). Вся история — не только финансовая, но и персональные данные — в «одних руках», чистота которых зачастую сомнительна. И допуск клиента к его же средствам не всегда гарантирован.

Пример. В 2018 г. Bank of England конфисковал $ 14 $ тонн золота, принадлежавшие Центральному банку Венесуэлы.

Достоинства. Блокировка нечестного поведения клиента: проблема double spending, когда клиент пытается расплатиться за $2 $ разных товара (две услуги) одной и той же суммой со своего счета.

(Англ.) distributed ledger

Количество криптовалюты («крипты») во всей системе и ее распределение по узлам известно каждому узлу в любой момент времени. Если узел $ 1$ намеревается перевести определенное количество крипты узлу $ 2$, то он сначала информирует об этом все узлы системы.

Все узлы сначала проверяют выполнимость (валидность) заявки: узел $1 $ обладает необходимым количеством крипты.

или как добавить запись в реестр? Какому-то узлу нужно поручить создание новой записи и включение ее в реестр.

Решить задачу: найти такое число $ x $, чтобы $$ h(x) = \underbrace{0000\dots 000}_{20 \ \mbox{нулей}}\overbrace{*****\dots********}^{\widetilde M-20 \ \mbox{произвольных цифр}} \ ; $$ здесь $ h(x) $ — упомянутый выше хеш $$ h(x)= H_k, \quad \mbox{ где } \ H_j= H_{j-1} \oplus \left[ H_{j-1}^{x_j} \pmod{\widetilde M} \right] \quad \mbox{ для } \ j\in \{1,\dots,k \}\ . $$ Здесь значение $ H_0\in \{2,\dots, \widetilde M -1\} $ берется уже не произвольным, а зависящим от последней записи в реестре.

Кто первый подберет хотя бы одно число $ x $ (и покажет его всем остальным) — тот и получает право добавить запись в реестр. А в качестве бонуса получает некоторое количество крипты.

Этот процесс называется майнингом (добычей) крипты. Принятие решения узлами системы на основе реализации такой схемы (или иного алгоритма, требующего использования вычислительных мощностей) называется консенсусом на основе proof-of-work (доказательства выполненной работы).

А на следующем цикле (для новой записи в реестр) потребуется решить задачу в уже «усиленном» варианте: $$ h(x)= \underbrace{0000\dots 000}_{21 \ \mbox{нулей}}\overbrace{*****\dots********}^{\widetilde M-21 \ \mbox{произвольных цифр}} \, . $$ То есть майнинг дорожает с каждым циклом. А, кстати, сколько он стоит в смысле затрат электроэнергии (не считаю уж необходимость закупки подходящей техники — ферм крипты)? Можно посмотреть ЗДЕСЬ.

(Англ.) Chain — цепь. Схеме реестра представляет собой последовательность блоков, каждый из которых содержит в себе информацию о предыдущем. То есть, действительно — цепь

Создание «разветвления» (англ. fork). Обнаружить коллизию для хеша блока $ N $ и попытаться оспорить приоритет:

уговаривая узлы присоединиться к альтернативной цепи блокчейна.

Правило для узлов: всегда следовать за цепью, имеющей в настоящий момент наибольшую длину.

Основное условие стойкости системы: большинство ее участников действуют честно, т.е. соблюдая правила.

Достоинства proof-of-work-блокчейна: надежность, взломоустойчивость

Недостатки: дороговизна майнинга, низкая пропускная способность (скорость проведения транзакций).

Альтернативы? — Организация консенсуса на других принципах. Например, голосование. Можно и такое, при котором процедура голосования сама делается децентрализованной.

Основные опасности: double spending и «сговор большинства».

Как производится конвертация крипты в реальные (фиатные) деньги? Разными способами — например вот так.

Обменный курс: $ 1 $ BTC = $ 69\,968.1 $ USD

Почему так дорого?!