Регистрация Войти
Рейтинг:0
Robert Singleton avatar Crypto

AES и квантовые вычисления

флаг za
Robert Singleton

Я пытаюсь понять алгоритм шифрования AES-256, как он будет реализован на закрытом квантовом компьютере (на самом деле, симуляторе), и у меня есть некоторые проблемы с пониманием теории, лежащей в его основе. Статьи, которые я читал, начинаются с кольца многочленов, заданного формулой $F_2[х]/(1 + х + х^3 + х^6 + х^8)$. В чем смысл многочлена $1 + х + х^3 + х^6 + х^8$? И как это относится к $GF(2^8)$?

105
0 + 0
Robert Singleton avatar
флаг za
Robert Singleton
Название статьи, которую я читаю, звучит так: «Снижение стоимости внедрения усовершенствованного стандарта шифрования в виде квантовой схемы».
0
Ответить
poncho avatar
флаг my
poncho
Возможно, вы захотите начать с https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf, где пытается описать, что такое AES, включая операцию умножения, которая вас смущает.
4
Ответить
kelalaka avatar
флаг in
kelalaka
[Руководство по флешке AES](http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html)
1
Ответить
kelalaka avatar
флаг in
kelalaka
Наш канонический ответ [Поля Галуа в криптографии] (https://crypto.stackexchange.com/q/2700/18298) и [Нужна помощь в понимании математики Rijndael S-Box] (https://crypto.stackexchange.com/q /85670/18298) и
1
Ответить
Рейтинг:1
meshcollider avatar Crypto
флаг gb
meshcollider

Чтобы ответить на конкретный вопрос, $F_2[х]/(1 + х + х^3 + х^6 + х^8)$ изоморфен $GF(2^8)$. Видеть здесь для получения дополнительной информации.

Полином $ г (х) = 1 + х + х ^ 3 + х ^ 6 + х ^ 8 $ неприводима над $F_2$, поэтому частное является полем. Степень многочлена равна 8, поэтому это алгебраическое расширение степени 8 полинома. $F_2$. Другими словами, это $F_{2^8}$.

Элементы в $F_2[х]/(г(х))$ являются классами эквивалентности многочленов по модулю $г(х)$.

Это стандартный способ построения алгебраических расширений поля конечной степени.

Кстати, я думаю, что у AES действительно есть $х^4$ вместо $х^6$ в полиноме. Не уверен, что это опечатка в вашем вопросе или вы где-то это читали.

0 + 0
Robert Singleton avatar
флаг za
Robert Singleton
Это было очень полезно.Я безуспешно пытался разложить полином на $_2$, поэтому полезно знать, что он неприводим. Как доказать, что конкретный полином неприводим в $F_2$? У меня очень мало интуиции для $_2$. Кроме того: вы действительно правы, многочлен имеет $x^4$ вместо $x^6$. Есть ли причина, по которой AES выбрал $1 + x + x^3 + x^4 + x^6$ вместо какого-то другого неприводимого полинома?
0
Ответить
meshcollider avatar
флаг gb
meshcollider
@RobertSingleton, вы можете использовать [тест Рабина на неприводимость] (https://en.m.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Rabin.27s_test_of_irreducibility). Выбор полинома является лишь частью стандарта.
1
Ответить
kelalaka avatar
флаг in
kelalaka
Вы можете найти, как увидеть, что полиномы AES неприводимы [здесь] (https://crypto.stackexchange.com/a/77958/18298). Причина выбора малого веса неприводима именно в том, что снижает затраты на вычисления в конечном поле.
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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