This program implements Blum-Goldwasser Probabilistic Encryption Algorithm with parameters p=499, q=547, a=-57, b=52, X0 =159201 and message m=10011100000100001100.

[Programming-a](Programming-a)

Alice * chooses a Blum integer n such that n=p \cdot q and p \equiv 3~mod~4, q \equiv 3~mod~4. * computes two integers a and b using Euler-Extended Algorithm such that ap + bq = 1

public key is n private keys are p,q,a,b

In this homework,

n = 159201, p = 499, q = 547, a = -57, b = 52

Bob chooses a random number x_0 \in QR_n. Compute

k = \lfloor log n \rfloor\\
h = \lfloor log k \rfloor

The message is divided into t blocks such that each block is of h bits.

In this homework, k=18, h=4, t=5

Then follow the encryption rule of BG, we will have the ciphertext: [50, 0, 44, 46, 52, 40632].

50, 0, 44, 46, 52 are c_1, c_2, c_3, c_4, c_5

40632 is X_{t+1}.

&d_1 = [(p+1)/4]^{t+1} ~mod~p-1\\
&d_2 = [(q+1)/4]^{t+1} ~mod~q-1\\\\
&u = X_{t+1}^d_1 ~mod~p \\
&v = X_{t+1}^d_2 ~mod~q\\
&X_0 = vap + ubq~mod~N

Follow the above steps to compute X_0, we then can decode the ciphertext and get 10011100000100001100

In the code, I don't use the given a and b. Instead, I use

      a = p^{-1}~mod~q\\
b = q^{-1}~mod~p.

• BG_demo.py is the main program. Run it using Python 3.
• Blum_Goldwessar_Class.py defines class BG which is used for both encryption and decryption.
• Number_Package.py contains useful functions related to number manipulation such as multiplicative inverse, exponential with modulo.

python3 BG_demo.py

and the expected output is

Ciphertext is
[50, 0, 44, 46, 52, 40632]
Decryption result
10011100000100001100
Decryption success