| dbo:abstract
|
- 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. (en)
- Le cryptosystème de Blum-Goldwasser (BG) est un algorithme de chiffrement asymétrique proposé par Manuel Blum et Shafi Goldwasser en 1984. Blum-Goldwasser est un cryptosystème probabilistique et sémantiquement sûr avec une augmentation de taille de chiffrement constante. L'algorithme de chiffrement implémente un chiffrement de flot basé sur l'opérateur XOR, utilisant le générateur de nombres pseudo-aléatoires Blum Blum Shub (BBS) pour générer la clé de chiffrement. Le déchiffrement est accompli en travaillant sur l'état final du générateur BBS en utilisant la clé secrète, dans le but de retrouver la valeur initiale de la graine et reconstruire la clé de chiffrement. Le cryptosystème BG est sémantiquement sûr de par sa construction basée sur le problème de la décomposition en produit de facteurs premiers ; c’est-à-dire la factorisation d'une valeur composite où sont des grands nombres premiers. BG a de nombreux avantages sur les précédents schémas de chiffrement probabilistiques tels que le cryptosystème de Goldwasser-Micali. En premier lieu, sa sécurité sémantique se réduit seulement à la factorisation de nombres premiers sans autre forme de supposition (par exemple, le Problème de la résiduosité quadratique ou le problème RSA). En second lieu, BG est efficace en termes de stockage, conduisant à une augmentation constante de la taille du chiffrement indépendamment de la longueur du message en clair. Les implémentations logicielles de BG sont aussi relativement efficaces et l'algorithme se comporte bien, même en face de cryptosystèmes comme RSA (dépendant de la longueur du message et des choix d'exposants). Cependant, BG est très vulnérable aux attaques à textes clairs choisis (voir ci-dessous). Grâce à l'algorithme probabilistique, un texte clair donné peut produire des résultats très différents à chaque chiffrement. Cette propriété est significative car elle empêche de reconnaître les messages interceptés, par comparaison à un dictionnaire de textes chiffrés connus. (fr)
- L'algoritmo Blum-Goldwasser è un algoritmo di crittografia asimmetrica proposto da Manuel Blum e Shafi Goldwasser nel 1984. Si tratta di un algoritmo probabilistico semanticamente sicuro, e la dimensione del testo criptato aumenta di un fattore costante rispetto al testo in chiaro. Per criptare un messaggio, l'algoritmo utilizza come chiave uno stream di bit pseudo-casuali generati con l'algoritmo Blum Blum Shub (BBS). Per decrittare un messaggio si utilizza la chiave privata per trovare il seme iniziale con cui sono stati generati i bit della chiave. Blum-Glodwasser è semanticamente sicuro, assumendo che la fattorizzazione di numeri interi sia un problema intrattabile; in particolare si considera il caso in cui dove sono numeri primi molto grandi. Quest'algoritmo ha diversi vantaggi su altri algoritmi di crittografia probabilistici. Primo, la sua sicurezza è basata solamente sul problema della fattorizzazione, senza bisogno di altre assunzioni (come l'intrattibilità del problema del residuo quadratico o dell'). In secondo luogo, è molto più efficiente in termini di occupazione di spazio, perché introduce un aumento costante della dimensione rispetto ai dati in chiaro. È anche piuttosto efficiente in termini computazionali, perché non sfigura a confronto con altri algoritmi quali RSA. Tuttavia, è fortemente vulnerabile ad un attacco di tipo chosen cipher-text. Poiché per criptare si utilizza un algoritmo probabilistico, uno stesso testo in chiaro può produrre risultati molto diversi ogni volta che viene criptato. Questo porta dei vantaggi significativi, poiché impedisce ad un avversario di riconoscere messaggi intercettati confrontandoli con altri intercettati precedentemente. (it)
- Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 1984 году. Пусть m1, m2, … , mm — последовательность бит открытого текста.В качестве параметров криптосистемы выбираем n=pq — число Блюма, x0 — случайное число из Zn, взаимно простое с N. В качестве открытого ключа для шифрования выступает n, в качестве секретного ключа для расшифрования — пара (p, q). Для того, чтобы зашифровать открытый текст, обладатель открытого ключа выбирает x0. На основе BBS-генератора по вектору инициализации x0 получают последовательность квадратов x1, x2, … , xm, по которой получают последовательность младших бит b1, b2, …, bm. Путём гаммирования с этой последовательностью битов открытого текста и получают шифрованный текст ci=mi⊕bi, i=1,2,…,m. Шифрограмма, которая пересылается обладателю секретного ключа, есть (c1,c2,…,cm, xm+1). После формирования шифрограммы последовательность xi, i=0,1,…,m уничтожается, и при следующем сеансе связи отправитель выбирает новое x0. Получатель шифрограммы восстанавливает по xm+1 последовательность главных корней xm, … , x1 и последовательность их младших бит b1, b2, …, bm, а затем расшифровывает шифрограмму: mi=ci⊕bi , i=1,2,…,m. (ru)
|
| rdfs:comment
|
- 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. (en)
- Le cryptosystème de Blum-Goldwasser (BG) est un algorithme de chiffrement asymétrique proposé par Manuel Blum et Shafi Goldwasser en 1984. Blum-Goldwasser est un cryptosystème probabilistique et sémantiquement sûr avec une augmentation de taille de chiffrement constante. Grâce à l'algorithme probabilistique, un texte clair donné peut produire des résultats très différents à chaque chiffrement. Cette propriété est significative car elle empêche de reconnaître les messages interceptés, par comparaison à un dictionnaire de textes chiffrés connus. (fr)
- L'algoritmo Blum-Goldwasser è un algoritmo di crittografia asimmetrica proposto da Manuel Blum e Shafi Goldwasser nel 1984. Si tratta di un algoritmo probabilistico semanticamente sicuro, e la dimensione del testo criptato aumenta di un fattore costante rispetto al testo in chiaro. Per criptare un messaggio, l'algoritmo utilizza come chiave uno stream di bit pseudo-casuali generati con l'algoritmo Blum Blum Shub (BBS). Per decrittare un messaggio si utilizza la chiave privata per trovare il seme iniziale con cui sono stati generati i bit della chiave. (it)
- Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 1984 году. Пусть m1, m2, … , mm — последовательность бит открытого текста.В качестве параметров криптосистемы выбираем n=pq — число Блюма, x0 — случайное число из Zn, взаимно простое с N. В качестве открытого ключа для шифрования выступает n, в качестве секретного ключа для расшифрования — пара (p, q). (ru)
|
