2015-05-20
1090
| Закрытый ключ, ki | ||||||||
| Открытый ключ, (ki*n) mod m = (ki*31) mod 420 |
Для шифрования сообщение сначала разбивается на блоки, по размерам равные числу элементов последовательности в рюкзаке.
Затем, считая, что единица указывает на присутствие элемента последовательности в рюкзаке, а ноль — на его отсутствие, вычисляются полные веса рюкзаков - по одному рюкзаку для каждого блока сообщения.
В качестве примера возьмем открытое сообщение «АБРАМОВ», символы которого представим в бинарном виде в соответствии с табл. 3. Результат шифрования с помощью открытого ключа {62, 93, 186, 403, 417, 352, 315, 210} представлен в табл.11.
Таблица 11
Пример шифрования
| Открытое сообщение | Сумма весов | Шифрограмма (рюкзак), ci | |
| Символ | Bin-код | ||
| А | 1100 0000 | 62+93 | |
| Б | 1100 0001 | 62+93+210 | |
| Р | 1100 1111 | 62+93+417+352+315+210 | |
| А | 1100 0000 | 62+93 | |
| М | 1100 1100 | 62+93+417+352 | |
| О | 1100 1110 | 62+93+417+352+315 | |
| В | 1100 0010 | 62+93+315 |
Для расшифрования сообщения получатель должен сначала определить n-1, такое что (n * n-1) mod m = 1.
|
|
|
Затем каждое значение шифрограммы умножается на n-1 по модулю m и с помощью закрытого ключа определяются биты открытого текста.
В нашем примере сверхвозрастающая последовательность равна {2, 3, 6, 13, 27, 52, 105, 210}, m = 420, n = 31.
Значение n-1 равно 271 (31*271 mod 420 = 1).
Таблица 12
Пример расшифрования
| Шифрограмма (рюкзак), ci | (ci*n-1) mod m = (ci*271) mod 420 | Сумма весов | Открытое сообщение | |
| Bin-код | Символ | |||
| 2+3 | 1100 0000 | А | ||
| 2+3+210 | 1100 0001 | Б | ||
| 2+3+27+52+105+210 | 1100 1111 | Р | ||
| 2+3 | 1100 0000 | А | ||
| 2+3+27+52 | 1100 1100 | М | ||
| 2+3+27+52+105 | 1100 1110 | О | ||
| 2+3+105 | 1100 0010 | В |
В заключении следует отметить, что задача вскрытия данного способа шифрования успешна решена Шамиром и Циппелом в 1982 г.
