Кіріспе
Асимметриялық кілт шифрлеу алгоритмі
Блум-Голдвассер (BG) криптожүйесі – Мануэль Блум мен Шафи Голдвассердің 1984 жылы ұсынған асимметриялық кілт шифрлеу алгоритмі. Блум-Голдвассер – ықтималдық, семантикалық тұрғыдан қауіпсіз криптожүйе, шифрмәтіннің тұрақты көлемде кеңеюімен сипатталады. Шифрлеу алгоритмі кілт ағынын жасау үшін Blum Blum Shub (BBS) псевдокезеңсіз сандар генераторын пайдалана отырып, XOR негізіндегі ағын шифрлеуін іске асырады. Шифрды ашу жеке кілтті пайдалана отырып, BBS генераторының соңғы күйін өңдеу арқылы жүзеге асырылады, осылайша бастапқы тұқымды табуға және кілт ағынын қайта құруға болады. BG криптожүйесінің семантикалық қауіпсіздігі бүтін сандарды факторлаудың қиындығына негізделген; атап айтқанда, үлкен жай сандар болатын құрама мәнді факторлау. BG, Goldwasser-Micali криптожүйесі сияқты бұрынғы ықтималдық шифрлеу схемаларына қарағанда бірнеше артықшылықтары бар. Біріншіден, оның семантикалық қауіпсіздігі тек бүтін сандарды факторлауға дейін тоғысып келеді, қосымша болжамдарды қажет етпейді (мысалы, квадраттық қалдық мәселесінің немесе RSA мәселесінің қиындығы). Екіншіден, BG сақтау жағынан тиімді, хабарлама ұзындығына қарамастан шифрмәтіннің тұрақты көлемде кеңеюін қамтамасыз етеді. BG есептеу жағынан да салыстырмалы түрде тиімді, тіпті RSA сияқты криптожүйелермен салыстырғанда да жақсы нәтижелер көрсетеді (хабарлама ұзындығына және көрсеткіштер таңдауына байланысты). Дегенмен, BG адаптивті таңдалған шифрмәтінге қарсы шабуылдарға өте осал (төменде қараңыз). Шифрлеу ықтималдық алгоритм арқылы орындалатындықтан, берілген ашық мәтін әр шифрланған сайын өте әртүрлі шифрмәтіндерді тудырады. Бұл маңызды артықшылықтар береді, себебі ол қарсыластың ұсталған хабарламаларды белгілі шифрмәтіндердің сөздігімен салыстыру арқылы тануына мүмкіндік бермейді.
The Blum–Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum–Goldwasser is a probabilistic, semantically secure cryptosystem with a constant size ciphertext expansion. The encryption algorithm implements an XOR based stream cipher using the Blum Blum Shub (BBS) pseudo random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the private key, in order to find the initial seed and reconstruct the keystream. The BG cryptosystem is semantically secure based on the assumed intractability of integer factorization; specifically, factoring a composite value where are large primes. BG has multiple advantages over earlier probabilistic encryption schemes such as the Goldwasser–Micali cryptosystem. First, its semantic security reduces solely to integer factorization, without requiring any additional assumptions (e. g., hardness of the quadratic residuosity problem or the RSA problem). Secondly, BG is efficient in terms of storage, inducing a constant size ciphertext expansion regardless of message length. BG is also relatively efficient in terms of computation, and fares well even in comparison with cryptosystems such as RSA (depending on message length and exponent choices). However, BG is highly vulnerable to adaptive chosen ciphertext attacks (see below). Because encryption is performed using a probabilistic algorithm, a given plaintext may produce very different ciphertexts each time it is encrypted. This has significant advantages, as it prevents an adversary from recognizing intercepted messages by comparing them to a dictionary of known ciphertexts.
Операция
Блюм-Голдвассер криптожүйесі үш алгоритмнен тұрады: қоғамдық және жеке кілтті құрайтын ықтималды кілт жасау алгоритмі, ықтималды шифрлау алгоритмі және детерминистік сырқат алу алгоритмі.
Қауіпсіздік және тиімділік
Blum–Goldwasser схемасы, соңғы BBS күйі және ашық кілт берілгенде кілт ағыны биттерін болжаудың қиындығына негізделген семантикалық қауіпсіздікке ие. Дегенмен, белгілі бір формадағы шифрмәтіндер, қарсылас таңдалған шифрмәтіндің шифрлануын сұрайтын бейімделмелі таңдалған шифрмәтін шабуылына осал. Алғашқы шифрмәтінді шифрлау, жай мәтіннің көлеміне байланысты, BG схемасы RSA-дан есептеу тұрғысынан арзан немесе қымбат болуы мүмкін. RSA-ның көптеген қолданылымдары шифрлау уақытын азайту үшін оңтайландырылған тұрақты шифрлау көрсеткішін пайдаланады, сондықтан RSA шифрлауы, ең қысқа хабарламалардан басқа, көбінесе BG-дан озып кетеді. Алайда, RSA шифрлау көрсеткіші кездейсоқ түрде таралғандықтан, модульдік дәрежелеу бірдей ұзындықтағы шифрмәтін үшін BG шифрлаумен салыстырылатын квадратуралар/көбейтулер санын қажет етуі мүмкін. BG схемасының артықшылығы, ұзын шифрмәтіндерге тиімді масштабталуында, ал RSA үшін бірнеше жеке шифрлаулар қажет. Мұндай жағдайларда BG схемасы айтарлықтай тиімді болуы мүмкін.
Depending on plaintext size, BG may be more or less computationally expensive than RSA. Because most RSA deployments use a fixed encryption exponent optimized to minimize encryption time, RSA encryption will typically outperform BG for all but the shortest messages. However, as the RSA decryption exponent is randomly distributed, modular exponentiation may require a comparable number of squarings/multiplications to BG decryption for a ciphertext of the same length. BG has the advantage of scaling more efficiently to longer ciphertexts, where RSA requires multiple separate encryptions. In these cases, BG may be significantly more efficient.