Кіріспе
Жария кілт шифрлау схемасы, оқулықтағы жария кілт шифрлау схемасы. Рабин криптожүйесі – тұйық есіктік функцияға негізделген жария кілт шифрлау схемаларының бір отбасы, оның қауіпсіздігі 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-ға шамалас.
Қауіпсіздік
Кез келген алгоритм, Рабин шифрланған шифрмәті үшін мүмкін жай мәтіндердің біреуін таба алатыны дәлелденді. Осылайша, кездейсоқ жай мәтінді Рабин әдісімен шифрдан шығару, бүтін сандарды есепке бөлу мәселесінен кем емес, ал мұндай нәрсе 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).