Почему я боюсь криптовалют с открытым ключом

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

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

Пусть мы наблюдаем две последовательности x_t  и y_t, t=1,…, N, где x_t  из GF(2ⁿ) – многомерное поле размерности n из 2-х элементов 0 и 1, а  y_t  из поля действительных чисел R. Между этими последовательностями существует функциональная связь для любого целочисленного положительного t

y_t=F_k(x_t)+ξ_t,

где F_k(x) –функция отображения GF(2ⁿ) в R, зависящая от «ключа» k из некоторого множества К, которую для любого k мы знаем;

ξ_t– последовательность стационарных действительнозначных случайных величин со средним нуль и независящих от x_t.

А вот какой k  был в том случае, который  наблюдаем, этого мы не знаем.

Также обычно предполагается, что дисперсия Σ ξ_t  равна C₀·N, где C₀– некоторая константа.

Задача дешифрования – это определение при известных последовательностях  x_t  и y_t, неизвестного «ключа» k,  изначально  выбранного из  множества K случайным и равновероятным образом.

При этом обычно x_t  для любого t также предполагался случайным и равновероятным вектором из GF(2ⁿ) и для любого k дисперсия ΣF_k(x_t) равна C_k·N  и для всех k константа C_k меньше либо равна константы C.

Как определить k? Можно тотальным перебором. Берем ключ r и строим статистику S(r)=ΣF_r(x_t)·y_t. Если r=k, то среднее этой статистики положительно и  равно Σ(F_r(x_t))², т. е. является выборочной статистикой для оценки положительной величины N·E(F_r(x))², где Eg(x) – это математическое ожидание при случайном и равновероятном векторе x действительнозначной функции g(x) отображающей GF(2ⁿ) в R.

Для k≠r получаем оценку величины N·E(F_r(x)·F_k(x)), которая может быть очень разной для разных k.

Но выше было написано: «неизвестного «ключа» k,  выбранного из  множества K случайным и равновероятным образом.»

Поэтому для среднего второго распределения получаем

N·E(F_r(x)·Σ_kF_k(x)·|K|^-1), где |K| — число ключей.

Так как Σ_kF_k(x)·|K|^-1  нам известна, то мы ее можем сделать любой. И потому обычно ее в уравнении для y_tделают равной нулю.

Таким образом, мы получаем задачу различения двух простых гипотез о среднем статистики с разностью средних O(N) и дисперсиями O(N)  для обеих гипотез. Каким должно быть N для хорошего различения таких гипотез в случае, когда  статистика F_r(x_t)·y_tимеет нормальное распределение, для каждой из гипотез можно легко найти в любом учебнике по математической статистике.

Как и есть огромное число статей, в которых получены условия слабых зависимостей случайных величин x_t  и ξ_t  достаточные для  асимптотической нормальности суммы ΣF_r(x_t)·y_t. Одна из них принадлежит и автору данной заметки:

Верхние оценки для семиинвариантов суммы мультииндексированных случайных величин

Но трудоемкость тотального перебора, увы, равна |K|. Как ее можно сократить? Вот тут мы и приходим к методу «статаналогов».

Предположим, что К является декартовым произведением двух множеств  K₁и K₂. Как можно определить ключ (k₁,k₂), k_iєK_i, только тотальным перебором K₁? Да по той же «логике», как и вышеизложенное. Мы должны найти функцию G_r(x), где rєK₁, такую, что для ключей вида k=(r,k₂) имеет место условие:

EG_r(x)·F_k(x)≥δ>0,

и N достаточно большое, чтобы различить две простые гипотезы о среднем статистики с разностью средних не меньше δ·Nи дисперсиями O(N). 

В государственном криптографическом анализе СССР еще  считалось, что слабостью шифра является случай, когда такое возможно даже не для всех r из K₁, а только для его подмножества с числом элементов  z·|K₁|, где 0<z<1.

И какая у нас получается трудоемкость определения ключа? Очень простая

|K₁|+β·|K|,

где β – ошибка второго рода нашего критерия, а вероятность правильного определения ключа данным алгоритмом 1-α, где α – ошибка первого рода нашего критерия.

Кроме одного этапа можно сделать несколько, путем дробления K₂на еще одно декартово произведение K₂и K₃ и построение статаналогов для новых k вида (r,k), r=(r₁,r₂), r₁ из оставшихся «ключей» из K₁ после первого этапа, а r₂ из K₂и сократить трудоемкость до

|K₁|+β·|K₁|·|K₂|+ β· β₁·|K|,

где β₁ – ошибка второго рода нашего критерия для второго этапа алгоритма.

Потом делить можно K₃и так далее.

А что самое интересное из написанного выше, без чего собственно весь вышеизложенный текст превращается в демагогию? Это вопрос: как строить функцию G_r(x)? И вот тут мы попадаем в разложение функции F_k(x) в ряд Фурье

F_k(x)=Σf_k(a)(-1)^<a,x>,

где  a из GF(2ⁿ)  и  <a,x>= Σa_i·x_i(сумма произведения координат по модулю 2).

И как построить «статаналог», зависящий только от r из K₁?

А предположим, что для любого фиксированного r  из K₁и любого «ключа» k равного (r,k₂) существует A(r) – подмножество GF(2ⁿ) такое, что для любых a из этого множества нам известна функция g_r(a), принимающая значения -1, 0 и +1, для которой имеют место равенства

g_r(a)=sign(f_k(a)), если aєA(r) и нуль в противном случае.

Возьмем в качестве функции G_r(x) функцию Σg_r(a)(-1)^<a,x>. И что получим для    EG_r(x)·F_k(x), если k=(r,k₂)? Да очень простое равенство

Σmod(f_k(a))·I(aє A(r)), где mod(s) – модуль s, I — индикатор события.

Почему? Да потому что для любого a≠нулевому вектору E(-1)^<a,x>=0, а для нулевого вектора это 1.

И наша задача дешифрования сведется только к анализу достаточности N наблюдений для «хороших» α и  β нашего критерия на отличие последней суммы от нуля.

То, что написано выше, было известно задолго до прихода автора в 5 отдел Спецуправления. И потому все шифраторы строились так, что если последовательность векторов  x_tслучайна, равновероятна и независима, то на реальной длине N любого шифратора для одного ключа k α и  β получались «плохими». Но в реальности для «черных ящиков» у последовательности x_tотсутствовала независимость. Собственно при помощи алгоритмов, основанных на методе оценок семиинвариантов сумм слабозависимых случайных величин, автору статьи и удалось для одной такой зависимости  x_t, которая имела место, построить быстрые алгоритмы вычисления f_k(a) для векторов a c числом единиц не больше 3-х при n больше 1000. Это для расчета всех f_k(a) нет и ничего не будет быстрее «алгоритма Фурье» с трудоемкостью 2^n/2. А, как показано выше, именно расчет f_k(a) для подмножества GF(2ⁿ) и лежит в основе метода дешифрования «статаналог».

И, как ни парадоксально, во всех новых изобретениях публичных шифраторов и «производстве криптовалют»  автор нигде не видел даже того, что написал выше про советскую криптографию: все шифраторы строились так, что если последовательность векторов  x_tслучайна, равновероятна и независима, то на длине Nлюбого шифратора для одного «ключа» k α и  β получались «плохими».

Естественно предчувствую  «возражение» против написанного: «Зачем Вы пишите про  поле GF(2ⁿ), операции которого давно не используются в современных шифраторах».

Так двоичность векторов x_tиз современных компьютеров никуда не делась, а функцией F_k(x_t) можно точно описать любые операции в любом кольце и поле. И ряд Фурье существует  для любой функции отображающей  двоичные вектора размера n в поле действительных чисел. А величина (-1)^<a,x>появляется  просто из определения этого ряда.

И конечно самый интересный для сегодняшних дешифровальшиков вопрос: «Какую функцию F_k(x_t) Вы видите в шифраторе МММ?». Увы, это та задача, которую Вы сами и должны решать, если хотите дешифровать тем методом, который в истории криптографии с 1945-го по 1990-й года был самым успешным для дешифрования, если не считать шпионаж с покупкой «ключей».

Ссылка на определение статистического аналога из учебника по криптографии
studme.org/205763/informatika/statisticheskie_analogi