Del 7.sagews

Laboration 2

Del 7 Kodningsteori och McEliece kryptosystem

Insamlingsdatum: 15 oktober 2019

%md
Namn: Eric Turesson

Namn: Eric Turesson

Lösning av uppgift 5

# Kropp
F = GF(2)
# Generatormatris
G = matrix(F, [
        [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0,1,0,0,1,1,1,0,0,1,0,0,1,1,1,0],
        [0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,0,1,0,1,0,0,0,1,1,1,0,0,1,0,0,1],
        [0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,0,1,0,1,0,0,0,1,1,1,0,0,1,0,1],
        [0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,0,1,0,1,0,0,0,1,1,1,0,0,1,1],
        [0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,1,1,0],
        [0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1],
        [0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,0,1,0,0,0,0,1,1],
        [0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1,1,1,0,0,1,0,0,0,0,0,0,0,1,1,0,0,1,1,1,0],
        [0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,0,1],
        [0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,0,1,1,0,1,0,0,0,1,0,1],
        [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,0,1,1,0,1,0,0,0,1,1],
        [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,0,1,1,0,0,0,0,0,0,1,1,1,1,1,0],
        [0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,0,0,1],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,0,1],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,1],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1]])
# Basbytesmatris
S = matrix(F, [
        [1,0,1,1,1,0,0,0,1,1,1,0,0,1,1,1],
        [0,1,1,0,1,0,1,1,1,1,0,0,1,0,1,0],
        [0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0],
        [0,0,0,1,1,0,1,1,0,1,0,1,1,1,0,0],
        [0,0,1,0,1,0,0,1,0,1,1,0,1,1,0,0],
        [0,0,0,1,1,1,1,0,1,1,1,1,0,1,0,1],
        [0,1,1,0,1,0,0,1,1,0,1,0,0,0,0,1],
        [1,0,0,1,1,1,1,1,0,0,1,1,0,1,0,0],
        [1,1,0,0,1,1,0,1,0,1,0,0,0,1,1,1],
        [0,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1],
        [0,1,0,0,1,0,0,1,0,0,0,1,1,0,1,1],
        [0,1,1,1,0,1,0,0,0,1,1,0,0,0,0,1],
        [1,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1],
        [0,1,1,1,1,1,1,1,0,0,0,0,1,1,0,1],
        [0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0],
        [1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1],])
# Permutation
sigma = Permutation([27, 39, 16, 36, 30, 34, 40, 18, 38, 17, 5, 33, 8, 28, 10, 24, 26, 6,
                     14, 23, 19, 35, 4, 9, 13, 20, 12, 22, 7, 37, 25, 32, 31, 11, 29, 15, 1, 2, 3, 21])

def text_till_block2 ( t ) :
    return [ t [ i : i +2] for i in range (0 , len ( t ) ,2) ]
def block2_till_vektor (b) :
    h = map(lambda x : Integer (ord(x) ) , list(b) )
    h = map(lambda x : x. digits (2 , padto = 8) , h)
    return vector (F, flatten (h) )
def vektor_till_heltal (v) :
    w = v.lift()
    return sum([w[ i ] * 2^ i for i in range ( len (w) ) ])
def vektor_till_block2 (b) :
    b2 = [b [0:8] , b [8:16]]
    b2 = map( vektor_till_heltal , b2)
    return ''. join (map(chr , b2) )
def block2_till_text (b) :
    return ''. join (b)
def e_nyckel(t):
    v = vector(F,40)
    l = []
    while len(l) < t:
        x = randint(0,39)
        if x not in l:
            l.append(x)
    for i in range(5):
        v[l[i]] = 1
    return v
def McEliece_encrypt(m):
    e = vector(F,40)
    e = m*G_prim + e
    return e
def McEliece_decrypt(c):
    u = c*P_inv
    v = C.decode_to_message(u,'NearestNeighbor')
    return v*S_inv

# skriv in din lösning (klicka på ett horisontell streck för att infoga fler celler)
#c)
l = text_till_block2("These go to eleven")
listOfVec = []
for element in l:
    v = block2_till_vektor(element)
    listOfVec.append(v)
#d)
C = LinearCode(G)
#e)
length = C.length()
dimension = C.dimension()
print "e)Lenght = %d\t" % length ,"Dimension = %d\n" % dimension
#f)
minimum = C.minimum_distance()
t = round((minimum - 1)/2) - 1
print "f)number of discoverable wrongs = %d\t" % (minimum - 1) ,"Number of fixable wrongs = %d\n" % (t)
#g)
S_inv = S.inverse()
P = matrix(F,sigma.to_matrix())
P_inv = P.inverse()
I_test = P*P_inv
I = matrix.identity(40)
if I_test.list() == I.list():
    print "h) P*P^(-1) == I\n"
#i)
G_prim = S*G*P
e = e_nyckel(t)
print "j) wt(e) = %d" % e.hamming_weight()
listOfEnc = []
for element in listOfVec:
    listOfEnc.append(McEliece_encrypt(element))
print "The encrypted messages c:"
for element in listOfEnc:
    print element
listOfDec = []
print "\n"
for element in listOfEnc:
    listOfDec.append(McEliece_decrypt(element))
print "The Decrypted messages m:"
s = ""
for element in listOfDec:
    s += block2_till_text(vektor_till_block2(element))
print s

e)Lenght = 40 Dimension = 16 f)number of discoverable wrongs = 11 Number of fixable wrongs = 5 h) P*P^(-1) == I j) wt(e) = 5 The encrypted messages c: (0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1) (0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1) (1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0) (0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1) (1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0) (1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0) (1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1) (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1) (0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0) The Decrypted messages m: These go to eleven The Decrypted messages m: Gentlemen, you can't fight in here! This is the war room.X

Lösning av uppgift 6

# Kryptogram
kryptogram = [
    vector(F, [0,0,1,1,1,1,0,0,0,1,0,1,0,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,0,1,0,0,1,1]),
    vector(F, [0,0,1,1,1,1,0,0,0,0,0,1,0,0,1,0,1,1,1,1,0,1,0,1,0,0,1,0,1,0,1,0,0,0,0,0,1,1,1,1]),
    vector(F, [1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,1,1,1]),
    vector(F, [1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,1,0,0,1,1,1,1,0,1,0,0,0,0,1,1,1,0,0,0,0,1,0,0]),
    vector(F, [0,0,1,0,1,1,0,1,0,1,0,1,1,1,1,1,1,0,0,1,0,0,0,1,1,0,1,0,1,0,1,0,0,0,0,1,0,1,1,1]),
    vector(F, [0,1,1,1,0,0,0,0,1,0,1,0,1,1,0,1,0,0,0,1,1,1,0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,1,0]),
    vector(F, [0,1,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,0,1,1,1,0,1,0,0,0]),
    vector(F, [0,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,0,1,0,1,1,0,1,1,0,1,0,0,1,0,0,0,1,0,1,0]),
    vector(F, [0,0,1,1,1,0,1,0,1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,1,0,1,1,0,0,0,1,0,0,1,0,1,1,0,0,0]),
    vector(F, [1,0,1,1,1,0,0,0,0,0,1,1,0,0,1,0,1,1,1,1,1,0,0,1,1,1,0,1,0,0,1,0,1,0,1,1,0,0,1,0]),
    vector(F, [1,0,0,0,1,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,0,1,0,0,1,0,0,0,0,0,1,0]),
    vector(F, [0,0,1,0,1,1,1,0,0,0,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,1,0,0,1,0,0,0,1,1]),
    vector(F, [0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,0,1,1,0,1,1,0,1,0,1,0]),
    vector(F, [1,1,0,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,0,0,0,1]),
    vector(F, [1,1,1,1,1,1,1,1,1,0,1,0,0,1,0,0,0,1,0,0,1,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,0,1,0,1]),
    vector(F, [1,1,1,0,0,1,0,1,0,0,0,1,0,1,0,1,1,0,0,0,0,1,0,0,1,0,0,1,1,1,0,0,0,0,0,0,1,1,0,1]),
    vector(F, [0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,0,0,1]),
    vector(F, [0,0,1,1,0,0,0,0,0,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,0,1,1,0,1,0,0,0,0,1,1,1,1,0,1]),
    vector(F, [0,0,0,1,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,0,0,1,1]),
    vector(F, [0,0,1,0,1,1,0,1,1,0,0,1,1,1,0,1,0,1,1,0,1,0,0,1,0,0,1,0,1,1,0,0,0,1,0,0,1,1,0,0]),
    vector(F, [1,1,0,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,0,1,1]),
    vector(F, [0,0,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,0,0,0,1,0,1,0,1,0,1,0,1,1,0,1,0,0,0,0,1,1,1,1]),
    vector(F, [1,0,1,0,1,0,1,1,0,0,0,1,0,1,1,1,0,1,0,0,0,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,0,0,1,0]),
    vector(F, [1,0,0,0,0,0,1,0,0,1,1,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,1,0,0,0]),
    vector(F, [1,1,1,0,1,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1,1,0,0,1,0,0]),
    vector(F, [0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,0,0,1,1,1,1,0,1,1,1,1,0,1,0,1,0,1,1,1,1,0,1,0,0]),
    vector(F, [1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,0,1,1,0,1,0,1,1,0,1,0,1,1,1,1,0,0,1,1,0,1,0,1,0]),
    vector(F, [1,0,1,1,0,1,0,0,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,0,1,1,0,1,0,0,1,1,1,0,1,0,1]),
    vector(F, [1,1,1,1,1,1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,1,1,0,0,0,1,0,0,0,1,0,1,0,0,1,1,1,1,0,1])]

# skriv in din lösning (klicka på ett horisontell streck för att infoga fler celler)
listOfDec2 = []
for element in kryptogram:
    listOfDec2.append(McEliece_decrypt(element))
print "The Decrypted messages m:"
q = ""
for element in listOfDec2:
    q += block2_till_text(vektor_till_block2(element))
print q

The Decrypted messages m: Gentlemen, you can't fight in here! This is the war room.X