Второй раз за месяц найдена уязвимость в московской системе электронного голосования29.08.2019 11:03

Пусть $p=2q+1$ и $q$ простые числа длины порядка 1024 бита. $Q_p$ — группа квадратичных вычетов по модулю $p$ , $ |Q_p| = (p − 1)/2 = q$ . Для шифрования система выбирает $g \in Q_p$ , $pk \in Q_p$ — открытый и $sk \in {1, . . . , q}$ — секретный ключи ( $pk=g^{sk}$ ). Результат шифрования голоса $m$ имеет вид пары $(g^r,pk^rm)$ , $r$ -случайное число.

Если $m$ квадратичный вычет, то при любом $r$ второй компонент шифротекста тоже квадратичный вычет (аналогично — если не квадратичный вычет). Это дает возможность отличать различные голоса с помощью критерия Эйлера. Для этого нам достаточно возвести шифротекст в степень $(p-1)/2$ и проверить равен ли результат единице (в этом случае — это квадратичный вычет).

Например, номера кандидатов 1, 3 и 4 — квадратичные вычеты, а 2- нет. То есть, мы можем анализируя блокчейн по мере его обновления подсчитывать количество голосов за кандидата 2.

Атака будет работать даже тогда, когда вместо номеров кандидатов будут произвольные идентификаторы, правда с меньшей вероятностью успеха.