Ejemplo Criptosistema McEliece en SAGE

En el 1978 McEliece presentó un nuevo criptosistema de clave pública, basado en la Teoría de los Códigos. Dado que esta teoría es muy compleja, los expertos recomiendan una familiarización matemática preliminar con la Teoría de la Codificación, los Códigos de Goppa, y los Cuerpos de Galois.

 En el sistema de McEliece, cada usuario ha de elegir un polinomio irreducible de grado $delta$, y construir una matriz generadora del correspondiente código de Goppa, matriz G, de orden k x n. También ha de calcular la llave pública, que es una matriz generadora del código Goppa. Este código debe ser  tal que no exista un algoritmo computable que corrija los errores con éste código en un tiempo pequeño. La llave pública es obtenida a partir de la multiplicación de una matriz aleatoria no singular de orden 2^m-k*m, y una matriz de permutaciones de orden 2^m. Todos los usuarios del sistema mantienen sus respectivas llaves públicas, mientras que las matrices S,G e P serán secretas.

A continuación presentamos el algoritmo para generación de las llaves, cifrado de un texto plano y descifrado de un texto cifrado, según wikipedia, y su respectiva implementación mediante un ejemplo en SAGE. Es necesario "correr" primero la última de las celdas de este post, la cual contiene los algoritmos auxiliares como por ejemplo el algoritmo de Patterson.

Generación de Llaves

1. Alicia selecciona un código de Goppa binario Gamma com parâmetros (n,k) y capacidad de correción de delta errores; 
2. Alicia gera a matriz geradora $G$, de dimensiones n-m*k x n, del código \Gamma; Selecciona una matriz binaria no singular S, de dimensiones;n-m*k x n-m*k; 
3.  Selecciona una matriz de permutación P, de dimensión n; 
4.  Computa a matriz $G' = SGP; 
5.  La llave pública de Alicia é (G',delta) y su llave privada es (S,G,P).

Configurando los parámetros del código. En este ejemplo hemos considerado el grado del polinomio de Goppa igual a 3. El grado del polinomio para hacer la extensión del cuerpo GF(2), igual a 4.

xxxxxxxxxx

 

1

m = 4;delta = 3;N = 2^m

2

K_.<a> = GF(2);

3

F.<a> = GF(2^m);#creado el campo donde "vivirá" el código

4

PR = PolynomialRing(F,'X')

5

X = PR.gen()

6

g = X^3+X+1# Polinomio de Goppa

7

L = [a^i for i in range(N)] # Soporte del codigo

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages

Creando la matriz de teste de paridad

xxxxxxxxxx

 

1

T = matrix(F,delta,delta)

2

for i in range(delta):

3

    count = delta - i + 1 - 1

4

    for j in range(delta):

5

        if i > j:

6

            T[i,j]=g.list()[count]

7

            count = count + 1

8

        if i < j:

9

            T[i,j] = 0

10

        if i == j:

11

            T[i,j] = 1

12

V = matrix([[L[j]^i for j in range(N)] for i in range(delta)]) 

13

D = diagonal_matrix([1/g(L[i]) for i in range(N)])

14

H = T*V*D

15

H_Goppa_K = matrix(K_, m*H.nrows(),H.ncols())

16

for i in range(H.nrows()):

17

    for j in range(H.ncols()):

18

        be = bin(eval(H[i,j].int_repr()))[2:];

19

        be = '0'*(m-len(be))+be; be = list(be);

20

        H_Goppa_K[m*i:m*(i+1),j]=vector(map(int,be));

21

print H_Goppa_K

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages

Creando la matriz generadora del código y multiplicando por S y P.

xxxxxxxxxx

 

1

Krnl = H_Goppa_K.right_kernel();

2

G = Krnl.basis_matrix();

3

S = random_matrix(GF(2), N-m*delta)

4

while (S.determinant()==0):

5

    S = random_matrix(GF(2), N-m*delta)

6

rng = range(N); 

7

P = matrix(GF(2),N);

8

for i in range(N):

9

    p = floor(len(rng)*random());

10

    P[i,rng[p]]=1; rng=rng[:p]+rng[p+1:];

11

G_pub = S*G*P 

12

print G_pub

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages

Algoritmo para el proceso de cifrado:

1. Bob cifra el mensaje m como una cadena binaria de tamaño n-m*delta;
2. Bob computa el vector c' = mG';
3. Bob genera un vector de tamaño n randomico conteniendo hasta delta unos 
4. Bob computa el texto cifrado como c = c' + z.

xxxxxxxxxx

 

1

u = vector(K_,[randint(0,1) for _ in range(G_pub.nrows())])

2

c = u*G_pub

3

print 'u=',u

4

print 'c=',c

5

e = vector(K_,N)

6

e[8] = 1

7

e[9] = 1

8

print 'e=',e

9

y = c + e

10

print 'y',y

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages

Algoritmo de decifración.

1. Alice computa el inverso de P
2. Alice computa cP^{-1}. 
3. Alice usa un algoitmo de decodificación para el código G y decodifica c en m' . 
4. Alice computa m'S .

xxxxxxxxxx

 

1

yP = y*(P.inverse())

2

yd= decodePatterson(yP)

3

print (G.transpose()\yd)*S.inverse()

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages

Algoritmos Auxiliares

xxxxxxxxxx

 

1

def split(p):

2

    # split polynomial p over F into even part po

3

    # and odd part p1 such that p(z) = p2 (z) + z p2 (z)

4

    Phi1 = p.parent()

5

    p0 = Phi1([sqrt(c) for c in p.list()[0::2]])

6

    p1 = Phi1([sqrt(c) for c in p.list()[1::2]])

7

    return (p0,p1)

8

def xgcdm1(self, other):

9

    delta = self.degree()

10

    if other.is_zero():

11

        R = self.parent()

12

        return self, R.one_element(), R.zero_element()

13

    # Algorithm 3.2.2 of Cohen, GTM 138

14

    R = self.parent()

15

    A = self

16

    B = other

17

    U = R.one_element()

18

    G = A

19

    V1 = R.zero_element()

20

    V3 = B

21

    while true:

22

        Q,R = G.quo_rem(V3)

23

        T = U - V1*Q

24

        U = V1

25

        G = V3

26

        V1 = T

27

        V3 = R

28

        if V3.degree() <= floor((delta-1)/2) and G.degree() <= floor((delta)/2):

29

        #if V3.degree() < floor((delta-1)/2):# or Q.degree() < floor((delta-1)/2):#(delta-2)/2)):# or V3 == 0:

30

             break

31

    V = (G-A*U)//B

32

    lc = G.leading_coefficient()

33

    return G/lc, U/lc, V/lc

34

def g_inverse(p,g):

35

    (d,u,v) = xgcd(p,g)

36

    return u.mod(g)

37

def binPolyToF_Poly(X, a, PR, delta, m, v):

38

        polySym = PR(0)

39

        sum = PR(0)

40

        count = delta-1

41

        for i in range(len(v)):

42

            j = mod(i,m) 

43

            if j == 0 and i>1:

44

                polySym = polySym + (X^count)*sum

45

                sum = 0

46

                count = count - 1

47

            sum = sum + v[i]*a^(m-j-1)

48

        polySym = polySym + (X^count)*sum

49

        return polySym

50

def decodePatterson(y): 

51

    s2 = H_Goppa_K*y

52

    #print 's2',s2

53

    X1 = X;

54

    g1 = g

55

    #polSyn1 = PR(0);

56

    #for i in range(len(s2)):

57

    #    polSyn1 = polSyn1 + s2[i]*(X1^(len(s2)-i-1))

58

    polSyn1 = binPolyToF_Poly(X1, a, PR, delta, m, s2)

59

    #print 'sydrome',polSyn1

60

    g0g1 = split(g1);    

61

    w = ((g0g1[0])*g_inverse(g0g1[1],g1)).mod(g1)

62

    #print g_inverse(polSyn1,g1)

63

    T0T1 = split(g_inverse(polSyn1,g1) + X1)    

64

    R = (T0T1[0]+(w)*(T0T1[1])).mod(g1)

65

66

    (a11,b11,c11) = xgcdm1(g1,R);

67

    #print 'a11',a11,'\nc11',c11,'\nR',R,'\ng1',g1

68

    sigma = a11^2+X1*(c11^2)

69

    #print 'sigma',sigma

70

    #print sigma.roots()

71

    #for i in range(len(sigma.roots())):

72

    #    print 'Hola', sigma.roots()[i]

73

    for i in range(N):

74

        if (sigma(a^i)==0): # an error occured

75

            print 'error position',i

76

            y[i] = y[i] + 1

77

    return y

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages