Euclidean Algorithm, compute and such that . Compute . This will be the same value which was used in encryption (see proof below). can then used to compute the same sequence of values as were used in encryption to decrypt the message, as follows. For from 1 to Compute . Compute the least significant bits of . Compute . Finally, reassemble the values into the message . Example Let and . Then and . To encrypt the six-bit message , we break it into two 3-bit blocks , so . We select a random and compute . Now we compute the values as follows: So the encryption is . To decrypt, we compute It can be seen that has the same value as in the encryption algorithm. Decryption therefore proceeds the same as encryption: Proof of correctness We must show that the value computed in step 6 of the decryption algorithm is equal to the value computed in step 4 of the encryption algorithm. In the encryption algorithm, by construction is a quadratic residue modulo . It is therefore also a quadratic residue modulo , as are all the other values obtained from it by squaring. Therefore, by Euler's criterion, . Then Similarly, Raising the first equation to the power we get Repeating this times, we have And by a similar argument we can show that . Finally, since , we can multiply by and get from which , modulo both and , and therefore . Security and efficiency The Blum–Goldwasser scheme is semantically-secure based on the hardness of predicting the keystream bits given only the final BBS state and the public key . However, ciphertexts of the form are vulnerable to an adaptive chosen ciphertext attack in which the adversary requests the decryption of a chosen ciphertext . The decryption of the original ciphertext can be computed as . 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