Возможна ли следующая криптосистема:
Длина ключа обычно намного меньше длины вводимого текста.
Я предполагаю, что открытые тексты практически несжимаемы; то есть им разрешено быть произвольными битовыми комбинациями.
Если это так, то если вам разрешено выбирать ключи на основе открытых текстов, то это возможно, но только если длина ключей составляет не менее половины длины открытого текста. Если ключи выбираются независимо от открытых текстов, то это невозможно.
Давайте сначала покажем последнее утверждение; предположим, что у вас есть такой метод; то, что вы могли бы сделать для кодирования двух сообщений T1 и T2, — это выбрать два произвольных (и хорошо известных) ключа K1 и K2 и зашифровать их в сообщение M, а затем отправить это сообщение M кому-то. Что этот кто-то (кто знает K1, K2) может сделать для восстановления T1, T2, так это запустить функцию расшифровки на M (используя как K1, K2); что дает ему T1, T2. Что это означает, что если длина T1, T2, M составляет n бит, то ему отправляется 2n бит информации, выраженной только в n битах - так как мы предполагали, что T1, T2 несжимаемы, это невозможно.
Первое утверждение аналогично; чтобы отправить T1, T2, вы должны выбрать процедуру выбора K1, K2, а затем отправить K1, K2 и M - вам нужно будет отправить K1, K2, потому что мы больше не можем предполагать, что получатель их знает. Получатель снова использует функцию расшифровки для восстановления T1, T2 - если T1, T2, M имеют длину n бит, а K1, K2 имеют длину k бит, то мы отправили ему 2n бит, выраженных как общее количество n+2k битов - это возможно только при 2n $\ле$ п+2к или к $\ge$ н/2.
Последняя часть должна показать, что первое утверждение возможно — один простой (хотя и небезопасный) способ продемонстрировать его [1] состоит в том, чтобы разделить $Т1, Т2$ на половинки, $T1_a, T1_b, T2_a, T2_b$. Затем мы устанавливаем $K1 = T1_a$ и $K2 = T2_b$ и установить $M = T2_a || T1_b$ - способ "расшифровки" достаточно очевиден.
[1]: Это предполагает, что два метода дешифрования для T1 и T2 различны — можно составить единый метод, который работает для обоих, однако я не могу придумать такой метод, который легко объяснить.
