Можно ли применить RSA к комплексным числам?

RSA — популярный алгоритм шифрования с открытым ключом. Он имеет некоторые математические предположения.Я имею в виду, что нельзя применять RSA к элементам любой алгебраической структуры. Элементы из определенных алгебраических структур могут использоваться только в RSA.

Я хочу знать, попадают ли комплексные числа в эти конкретные алгебраические структуры или нет. Если нет, то из-за отсутствия какого свойства комплексные числа стали недопустимыми хотя бы теоретически?

Набор комплексов $\mathbb С$ не подходит для RSA. Это связано с тем, что RSA (как и вся криптография) отображает открытый текст и зашифрованный текст в конечные наборы (например, $\mathbb Z_n$ или это подмножество $\mathbb Z_n^*$), и $\mathbb С$ бесконечно.

Любая попытка представить конечное подмножество $\mathbb С$ подходит для ЮАР и использование собственного умножения не удается. В деталях включая $0$ или нет, то необходимость замкнутости этого множества относительно умножения оставляет нам множество $\{e^{2i\pi/n}\text{ для }i\in\mathbb N\text{ с }i<n\}$ как единственная возможность. Это множество тривиально изоморфно группе $(\mathbb Z_n,+)$, и, таким образом, не приводит к безопасной криптосистеме.

^{С другой стороны, мы можем сделать отношение эквивалентности $\sim$, совместимый с умножением в (подмножестве) $\mathbb С$ [то есть: для любого $а$, $а'$, $б$, $b'$ в $\mathbb С$ (или указанное подмножество), $а\сим а'$ и $б\сим б'$ подразумевает $а\,б\сим а'\,б'$ ], такое, что множество классы эквивалентности конечно, и полученное умножение является внутренним на фактор-группе. Тривиальный пример рассматривает $\mathbb Z_n\подмножество\mathbb R\подмножество\mathbb C$, и $\sim$ определяется как эквивалентность по модулю $n$ для этого подмножества $\mathbb С$. Этот ответ приводит более интересный пример. Есть еще больше возможностей, если мы переопределим умножение, включив Аналог RSA на эллиптической кривой, который можно легко переназначить на $\mathbb С$. Я не вижу, чтобы они соответствовали исходному вопросу, поскольку мы меняем как набор (по ограничению), так и операцию (чтобы сохранить ее внутренней).}

Данный $р,к$ формы 4к+3$, мы можем определить комплексные числа по модулю $р$ или мод $q$. Форма гарантирует, что $-1$ не имеет там квадратного корня, поэтому мы работаем с квадратичным расширением $GF(p)$ и $GF(q)$, т.е. $$GF(p^2) \simeq GF(p)[i]/(i^2+1)$$ и $$GF(q^2) \simeq GF(q)[i]/(i^2+1).$$

Комбинируя их, мы можем определить RSA поверх $(\mathbb{Z}/n\mathbb{Z})[i]/(i^2+1)$, $n=pq$, то есть комплексные числа, действительные и мнимые части которых определены по модулю $n$. Арифметика (умножение, сложение и т. д.) производится аналогично комплексным числам. Например. $$(a+bi)(c+di)\equiv (ac-bd) + (ad+bc)i \pmod{n}$$ (значения хранятся в виде пар $(а,б)$ и $(в,г)$).

Порядок мультипликативной группы $\mathrm{lcm}(p^2-1, q^2-1)$, поэтому нам нужно $$e\cdot d \equiv 1 \pmod{\mathrm{lcm}(p^2-1, q^2-1)}.$$

Конечно, факторинг $n$ ломает схему, так что нет повышения безопасности.

Другая возможная проблема заключается в том, что комплексные числа имеют (квадратную) норму, которая является мультипликативной и ее легко вычислить, не зная $р$ и $q$: $$N(a+bi) \эквив a^2+b^2 \pmod{n},$$ $$N(c) \equiv N(m^e) \equiv N(m)^e \pmod{n}.$$ Поскольку норма живет в $GF(p)\раз GF(q)$, сводим к базовому моду RSA $n$. Может ли злоумышленник каким-то образом сломать мод RSA $n$, тогда атакующий восстанавливает норму сообщения.

Резюме:

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

Других значимых атак на эту схему я не вижу, был бы рад узнать, если они есть.

Обновление: Вместо $\sqrt{-1}$ мы можем использовать любой другой $\sqrt{d}$ что не лежит в базовом поле, т.е. работать с $\mathbb{Z}[\sqrt{d}]/n\mathbb{Z}$. Это было сделано в варианте сигнатуры OSS. (OSS был сломан, но только потому, что он сам по себе слаб, RSA, определенный над квадратичными целыми числами, должен быть в порядке.)

Элементы из определенных алгебраических структур могут использоваться только в RSA.

Я не совсем уверен, что вы имеете в виду. Шифрование RSA можно (и обычно так) рассматривать как:

• Возьмите битовую строку открытого текста (до некоторой максимальной длины, несколько меньшей, чем размер модуля)

• Запустите его через функцию заполнения, чтобы преобразовать его (плюс некоторую случайность) в число от 0 до N-1.

• Запустите базовую общедоступную операцию RSA, чтобы преобразовать ее в другое число от 0 до N-1.

• Преобразуйте это число в битовую строку зашифрованного текста.

(и операции расшифровки и подписи аналогичны).

Таким образом, любые значения, которые могут быть представлены битовой строкой (ограниченного размера), могут обрабатываться RSA.

Теперь это нарушает гомоморфные свойства RSA (не случайно; они редко бывают полезны пользователю и могут быть полезны злоумышленнику, поэтому мы хотим, чтобы они были разделены); с другой стороны, неясно, насколько они будут полезны для комплексных чисел.

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