CoCalc Shared Filesmceliece_ex.sagews
Author: Susan Margulies
Views : 35
Description: McEliece helper code for SM468
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)
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
print "Bob generates public key G1 = S*G*P"
G1 = S*G*P
G1

Bob chooses encoding matrix G [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] Thus, the associated parity check matrix H is [1 1 0 1 1 0 0] [1 0 1 1 0 1 0] [0 1 1 1 0 0 1] Bob chooses invertible matrix S [1 0 0 1] [1 1 0 1] [0 1 0 1] [1 1 1 0] 1 Bob chooses permutation matrix P [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] Bob generates public key G1 = S*G*P [0 0 1 1 0 1 0] [1 0 1 0 0 1 1] [1 1 0 0 0 1 0] [1 0 1 0 1 0 0]
print "Alice chooses message m"
x = Matrix(GF(2), [[1,0,0,0]])
x
print "Alice chooses random error vector e"
e = Matrix(GF(2), [[0,0,0,0,1,0,0]])
e
print "Alice computes ciphertext y = x*G1 + e"
y = x*G1 + e
y

Alice chooses message m [1 0 0 0] Alice chooses random error vector e [0 0 0 0 1 0 0] Alice computes ciphertext y = x*G1 + e [0 0 1 1 1 1 0]
print "Bob decrypts ciphertext y by computing y1"
y1 = y*P.inverse()
y1
print "Bob computes syndrome of y1 or S(y1) = y1*H^T"
y1*H.transpose()
print "Find corresponding row in H^T"
H.transpose()
print "It is row 3! Correct the 3th bit in y1 -> x1!"
# y1 = [0 0 1 0 0 0 1]
x1 = Matrix(GF(2), [[1, 0, 0, 1, 0, 0, 1]])
x1
print "By extracting the first 4 bits, we see that x0*G = x1"
x0 = Matrix(GF(2), [[1, 0, 0, 1]])
x0
x0*G
print "Compute the message by taking x0*S^-1"
x0*S.inverse()

Bob decrypts ciphertext y by computing y1 [1 0 1 1 0 0 1] Bob computes syndrome of y1 or S(y1) = y1*H^T [0 1 1] Find corresponding row in H^T [1 1 0] [1 0 1] [0 1 1] [1 1 1] [1 0 0] [0 1 0] [0 0 1] It is row 3! Correct the 3th bit in y1 -> x1! [1 0 0 1 0 0 1] By extracting the first 4 bits, we see that x0*G = x1 [1 0 0 1] [1 0 0 1 0 0 1] Compute the message by taking x0*S^-1 [1 0 0 0]
power_mod(10, 196, 197)

1