Thành viên:Tigerking1994

Шифрование Chop-Rivest для ранца

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

Схема шифрования ранца Merkle-Hellman важна по историческим причинам, поскольку это была первая конкретная реализация схемы шифрования с открытым ключом. Впоследствии было предложено много вариантов, но большинство, в том числе оригинал, были продемонстрированы как небезопасные, примечательным исключением является схема ранцевания Чор-Ривеста.

Схема Chor-Rivest является единственной известной схемой шифрования с открытым ключом ранца, которая не использует некоторую форму модульного умножения для маскировки простой задачи суммирования сумм.

Алгоритм Генерация ключей для шифрования с открытым ключом Chor-Rivest

АННОТАЦИЯ: каждый объект создает открытый ключ и соответствующий закрытый ключ. Каждый объект A должен выполнять следующие действия:

1. Выберите конечное поле $\mathbb {F} _{q}$ характеристики q, где ${\mathit {q}}$ = $p^{h}$, ${\mathit {p}}\geq {\mathit {h}}$ , и для которого задача дискретного логарифма является выполнимой.
2. Выберите случайный мононический неприводимый многочлен ${\mathit {f}}$(${\mathit {x}}$) степени ${\mathit {h}}$ над $\mathbb {Z} _{p}$. Элементы $\mathbb {F} _{q}$ будут представлены как многочлены от $\mathbb {Z} _{p}[{\mathit {x}}]$ степени меньше ${\mathit {h}}$, причем умножение выполняется по модулю ${\mathit {f}}(x)$.