print("Bob chooses encoding matrix G")
G = Matrix(GF(2), [[1,0,0,0,1,1,0],
                  [0,1,0,0,1,0,1],
                  [0,0,1,0,0,1,1],
                  [0,0,0,1,1,1,1]])
G
print("Thus, the associated parity check matrix H is")
H = Matrix(GF(2), [[1,1,0,1,1,0,0],
                  [1,0,1,1,0,1,0],
                  [0,1,1,1,0,0,1]])
H
print("Bob chooses invertible matrix S")
S = Matrix(GF(2), [[1,0,0,1],
                  [1,1,0,1],
                  [0,1,0,1],
                  [1,1,1,0]])
S
det(S) # check for invertibility
print("Bob chooses permutation matrix P")
P = Matrix(GF(2), [[0,0,1,0,0,0,0],
                  [1,0,0,0,0,0,0],
                  [0,0,0,0,1,0,0],
                  [0,0,0,0,0,1,0],
                  [0,0,0,0,0,0,1],
                  [0,1,0,0,0,0,0],
                  [0,0,0,1,0,0,0]])
P
036d5e0-c82f-44ad-8e41-a20c6099e43b

print("Bob generates public key G1 = S*G*P")
G1 = S*G*P
G1

print("Alice chooses message x")
x = Matrix(GF(2), [[1,0,1,0]]) # you can choose your own message
x

print("Alice chooses random error vector e (hamming weight 1)")
e = Matrix(GF(2), [[0,1,0,0,0,0,0]]) # you can choose your own error vector, hamming weight 1
e

print("Alice computes ciphertext y = x*G1 + e")
y = x*G1 + e
y

print("Bob decrypts ciphertext y(= xG1 + e) by computing r1(=yP^-1) = received word")
r1 = y*P.inverse()
r1

print("Bob computes syndrome of r1 or S(r1) = r1*H^T")
r1*H.transpose()

print("Decode by finding corresponding row in H^T")
H.transpose()

print("It is row 6! Correct the 6th bit in r1 -> c1!")
# r1 = [1 1 0 0 0 0 1]
c1 = Matrix(GF(2), [[1, 1, 0, 0, 0, 1, 1]]) # correct the bit by hand
c1

print("Extracting the first 4 bits to find x1G = c1")
x1 = Matrix(GF(2), [[1, 1, 0, 0]])
x1
x1*G # show that x1G = c1 (message*G = codeword)

print("Compute the message by taking x1*S^-1")
x1*S.inverse()
print("Here is the original x")
x

6+4+7+6.25