CoCalc Public Filesmceliece_ex.sagewsOpen in with one click!
Author: Susan Margulies
Views : 102
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