The following is an updated and edited version of my posts to this sage-support thread.
You have a bitstring as output by
and you want to convert that bitstring to an integer. Or in general, you want to convert a bit vector to its integer representation.
Here are two ways, assuming that you want the bits in little-endian order, i.e. you read the bits from right to left in increasing order of powers of 2.
sage: version() 'Sage Version 4.5.3, Release Date: 2010-09-04' sage: from sage.crypto.stream import blum_blum_shub sage: b = blum_blum_shub(length=6, lbound=10**4, ubound=10**5); b 100110 sage: type(b) <class 'sage.monoids.string_monoid_element.StringMonoidElement'> sage: # read in little-endian order sage: # conversion using Python's built-in int() sage: int(str(b), base=2) 38 sage: # conversion using Sage's built-in Integer() sage: Integer(str(b), base=2) 38
Now assume you read the bitstring as output by blum_blum_shub in big-endian order, i.e. from left to right in increasing order of powers of 2. You simply convert the bitstring to a string, reverse that string, and apply any of the above two methods.
sage: # reversing a string sage: str(b) '100110' sage: str(b)[::-1] '011001' sage: # read in big-endian order sage: int(str(b)[::-1], base=2) 25 sage: Integer(str(b)[::-1], base=2) 25
Or you can do as follows:
sage: b = "100110" sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b)) 25 sage: sum(Integer(i) * (2^Integer(e)) for e, i in enumerate(b[::-1])) 38
Another way is to use Horner’s method. Here’s a Sage function that computes the integer representation of a bit vector read using big-endian order. A usage example is also shown.
sage: def horner(A, x0): ... # Evaluate the polynomial P(x) at x = x_0. ... # ... # INPUT ... # ... # - A -- list of coefficients of P where A[i] is the coefficient of ... # x_i. ... # - x0 -- the value x_0 at which to evaluate P(x). ... # ... # OUTPUT ... # ... # An evaluation of P(x) using Horner's method. ... i = len(A) - 1 ... b = A[i] ... i -= 1 ... while i >= 0: ... b = b*x0 + A[i] ... i -= 1 ... return b sage: A = [1, 0, 0, 1, 1, 0] sage: horner(A, 2) 25
As an exercise, modify the function horner to output the integer representation of a bit vector that is read using little-endian order.
Sage 4.3.3 merged an implementation of the Blum-Goldwasser probabilistic public-key encryption scheme described in the following paper:
- M. Blum and S. Goldwasser. An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information. In Proceedings of CRYPTO 84 on Advances in Cryptology, pp. 289–299, Springer, 1985.
I wrote that implementation based on a public domain version by Mike Hogan and David Joyner. See ticket #7746 for background information. A big thank you to David Joyner for reviewing that ticket and many suggestions for improvement. The current implementation in Sage 4.3.3 follows the description of the Blum-Goldwasser scheme as described in the following book:
- A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.
This implementation is documented in the Sage reference manual. In this post, I will provide some usage examples.
The Blum-Goldwasser encryption and decryption algorithms make use of the least significant bit of a binary string. A related concept is the least significant bits of a binary string. For example, given a positive integer , let be the binary representation of so that is a binary string of length . Then the least significant bit of is . If , then the least significant bits of are . The least significant bit of an integer is also referred to as its parity bit, because this bit determines whether the integer is even or odd. In the following example, we obtain the least significant bit of an integer:
sage: from sage.crypto.util import least_significant_bits sage: least_significant_bits(123, 1)  sage: least_significant_bits(123, 4) [1, 0, 1, 1]
The following encryption/decryption example is taken from Example 8.57, pages 309–310 of (Menezes et al. 1996):
sage: from sage.crypto.public_key.blum_goldwasser import BlumGoldwasser sage: bg = BlumGoldwasser(); bg The Blum-Goldwasser public-key encryption scheme. sage: p = 499; q = 547 sage: pubkey = bg.public_key(p, q); pubkey 272953 sage: prikey = bg.private_key(p, q); prikey (499, 547, -57, 52) sage: P = "10011100000100001100" sage: C = bg.encrypt(P, pubkey, seed=159201); C ([[0, 0, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]], 139680) sage: M = bg.decrypt(C, prikey); M [[1, 0, 0, 1], [1, 1, 0, 0], [0, 0, 0, 1], [0, 0, 0, 0], [1, 1, 0, 0]] sage: M = "".join(map(lambda x: str(x), flatten(M))); M '10011100000100001100' sage: M == P True
Now generate a pair of random public/private keys. Use the public key to encrypt a plaintext. Then decrypt the resulting ciphertext using the private key. Finally, compare the decrypted message with the original plaintext.
sage: from sage.crypto.public_key.blum_goldwasser import BlumGoldwasser sage: from sage.crypto.util import bin_to_ascii sage: bg = BlumGoldwasser() sage: pubkey, prikey = bg.random_key(10**4, 10**6) sage: P = "A fixed plaintext." sage: C = bg.encrypt(P, pubkey) sage: M = bg.decrypt(C, prikey) sage: bin_to_ascii(flatten(M)) == P True
If is a private key, then is the corresponding public key. Furthermore, we have .
sage: p, q, a, b = prikey sage: pubkey == p * q True sage: gcd(p, q) == a*p + b*q == 1 True
sage: from sage.crypto.util import ascii_integer sage: bin = BinaryStrings() sage: B = bin.encoding("A"); B 01000001 sage: ascii_integer(B) 65 sage: B = bin.encoding("C"); list(B) [0, 1, 0, 0, 0, 0, 1, 1] sage: ascii_integer(list(B)) 67 sage: ascii_integer("01000100") 68 sage: ascii_integer([0, 1, 0, 0, 0, 1, 0, 1]) 69
Compute the binary representation of some ASCII strings:
sage: from sage.crypto.util import ascii_to_bin sage: ascii_to_bin("A") 01000001 sage: ascii_to_bin("Abc123") 010000010110001001100011001100010011001000110011
Convert some ASCII strings to their binary representations and recover the ASCII strings from the binary representations:
sage: from sage.crypto.util import ascii_to_bin sage: from sage.crypto.util import bin_to_ascii sage: A = "Abc" sage: B = ascii_to_bin(A); B 010000010110001001100011 sage: bin_to_ascii(B) 'Abc' sage: bin_to_ascii(B) == A True sage: A = "123 \" #" sage: B = ascii_to_bin(A); B 00110001001100100011001100100000001000100010000000100011 sage: bin_to_ascii(B) '123 " #' sage: bin_to_ascii(B) == A True
Testing for the presence of Blum primes within some closed intervals. The interval has a Blum prime, the smallest such prime being 7. The interval has no primes, hence no Blum primes.
sage: from sage.crypto.util import has_blum_prime sage: from sage.crypto.util import is_blum_prime sage: has_blum_prime(4, 100) True sage: for n in xrange(4, 100): ... if is_blum_prime(n): ... print n ... break ... 7 sage: has_blum_prime(24, 28) False
Choose a random prime and check that it is a Blum prime:
sage: from sage.crypto.util import random_blum_prime sage: p = random_blum_prime(10**4, 10**5) sage: is_prime(p) True sage: mod(p, 4) == 3 True