Введение
Схема шифрования с открытым ключом
учебная схема шифрования с открытым ключом
Криптосистема Рабина — это семейство схем шифрования с открытым ключом, основанных на функции с секретом (trapdoor function), безопасность которой, как и у RSA, связана со сложностью факторизации целых чисел. Функция с секретом Рабина имеет то преимущество, что математически доказано, что её инверсия столь же сложна, как и факторизация целых чисел, в то время как для функции с секретом RSA подобного доказательства не существует. Её недостаток заключается в том, что каждый выход функции Рабина может быть сгенерирован любым из четырех возможных входов; если каждый выход является шифротекстом, то для расшифровки требуется дополнительная сложность, чтобы определить, какой из четырех возможных входов был исходным открытым текстом. Неудачные попытки обойти это часто либо позволяют атакующему, выбирая шифротекст, восстановить секретный ключ, либо, кодируя избыточность в пространстве открытого текста, делают недействительным доказательство безопасности относительно факторизации. Схема цифровой подписи Рабина была первой схемой, для которой доказано, что подделать подпись столь же сложно, как и факторизовать число. Функция с секретом позднее была использована в учебниках в качестве примера схемы шифрования с открытым ключом.
the textbook public key encryption scheme
The Rabin cryptosystem is a family of public key encryption schemes
based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization. The Rabin trapdoor function has the advantage that inverting it has been mathematically proven to be as hard as factoring integers, while there is no such proof known for the RSA trapdoor function. It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext. Naive attempts to work around this often either enable a chosen ciphertext attack to recover the secret key or, by encoding redundancy in the plaintext space, invalidate the proof of security relative to factoring. The Rabin signature scheme was the first digital signature scheme where forging a signature could be proven to be as hard as factoring. The trapdoor function was later repurposed in textbooks as an example of a public key encryption scheme,
Эффективность
Для шифрования необходимо вычислить квадрат по модулю n. Это более эффективно, чем RSA, который требует вычисления как минимум куба. Для расшифровки применяется китайская теорема об остатках, а также два возведения в степень по модулю. Здесь эффективность сопоставима с RSA.
Безопасность
Доказано, что любой алгоритм, способный найти один из возможных открытых текстов для каждого зашифрованного текста Рабина, может быть использован для факторизации модуля. Таким образом, дешифрование Рабина для случайного открытого текста не менее сложно, чем задача факторизации целых чисел, что не было доказано для RSA. Обычно считается, что не существует алгоритма полиномиального времени для факторизации, что подразумевает отсутствие эффективного алгоритма для расшифровки случайного зашифрованного значения Рабина без секретного ключа. Криптосистема Рабина не обеспечивает неотличимость при атаках с выбранным открытым текстом, поскольку процесс шифрования детерминирован. Злоумышленник, получив шифротекст и предполагаемое сообщение, может легко определить, кодирует ли шифротекст это сообщение (просто проверив, приводит ли шифрование предполагаемого сообщения к данному шифротексту). Криптосистема Рабина уязвима для атак с выбранным шифротекстом (даже если сообщения-запросы выбираются равномерно случайным образом из пространства сообщений). Добавление избыточности, например, повторение последних 64 бит, позволяет системе выдавать единственный корень. Это нейтрализует конкретную атаку с выбранным шифротекстом, поскольку алгоритм дешифрования затем выдает только тот корень, который уже известен злоумышленнику. Если применять эту технику, доказательство эквивалентности задаче факторизации становится недействительным, поэтому с 2004 года неясно, является ли этот вариант безопасным. В "Руководстве по прикладной криптографии" Менеза, Оршота и Ванстона эта эквивалентность считается вероятной, однако, пока нахождение корней остается двухэтапным процессом (1. нахождение корней и 2. применение китайской теоремы об остатках).
The Rabin cryptosystem does not provide indistinguishability against chosen plaintext attacks since the process of encryption is deterministic. An adversary, given a ciphertext and a candidate message, can easily determine whether or not the ciphertext encodes the candidate message (by simply checking whether encrypting the candidate message yields the given ciphertext). The Rabin cryptosystem is insecure against a chosen ciphertext attack (even when challenge messages are chosen uniformly at random from the message space). By adding redundancies, for example, the repetition of the last 64 bits, the system can be made to produce a single root. This thwarts this specific chosen ciphertext attack, since the decryption algorithm then only produces the root that the attacker already knows. If this technique is applied, the proof of the equivalence with the factorization problem fails, so it is uncertain as of 2004 if this variant is secure. The Handbook of Applied Cryptography by Menezes, Oorschot and Vanstone considers this equivalence probable, however, as long as the finding of the roots remains a two part process (1. roots and and 2. application of the Chinese remainder theorem).