Algoritmo para Decodificação de Códigos de Goppa Binário

Dentre os sistemas criptográficos assimétricos ou de chave pública práticos, eficientes e seguros temos: DSA, RSA, baseados em curvas Elípticas, entre outros. A segurança desses sistemas está ameaçada devido ao advento da computação quântica e do algoritmo quântico desenvolvido por Peter Shor em 1994, que resolve o problema da fatoração de números inteiros em tempo polinomial.

Em 1978 Robert McEliece propôs um sistema criptográfico aleatório que, na época,  não foi posto em prática devido ao fato do tamanho de suas chaves serem consideravelmente grandes. Atualmente esse sistema tem tido muita aceitação por parte da comunidade de pesquisadores em criptografia devido à sua resistência aos ataques provenientes dos algoritmos quânticos, como o algoritmo o de Shor. Outra vantagem deste sistema criptográfico é o fato de que seus algoritmos de cifração e decifração são mais rápidos, no que se refere à complexidade de tempo, em comparação com o sistema consolidado RSA.

Este post está focado na implementação do algoritmo de decodificação para códigos de Goppa [1]. Para isto, apresentarei, embaixo, esta implementação feita no CAS SAGE. Note que o código escrito ali pode ser "rodado" fazendo click no botão Evaluate.

Implementação do Algoritmo do Patterson

xxxxxxxxxx

 

1

#Algoritmos Auxiliares

2

def split(p):

3

    # split polynomial p over F into even part po

4

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

5

    Phi1 = p.parent()

6

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

7

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

8

    return (p0,p1)

9

def xgcdm1(self, other):

10

    delta = self.degree()

11

    if other.is_zero():

12

        R = self.parent()

13

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

14

    # Algorithm 3.2.2 of Cohen, GTM 138

15

    R = self.parent()

16

    A = self

17

    B = other

18

    U = R.one_element()

19

    G = A

20

    V1 = R.zero_element()

21

    V3 = B

22

    while true:

23

        Q,R = G.quo_rem(V3)

24

        T = U - V1*Q

25

        U = V1

26

        G = V3

27

        V1 = T

28

        V3 = R

29

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

30

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

31

             break

32

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

33

    lc = G.leading_coefficient()

34

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

35

def g_inverse(p,g):

36

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

37

    return u.mod(g)

38

#Implementação do algoritmo de Patterson

39

def decodePatterson(y): 

40

    s2 = H*y

41

    s2 = vector(s2)

42

    print 's2',s2

43

    X1 = X;

44

    g1 = g

45

    polSyn1 = PR(0);

46

    for i in range(len(s2)):

47

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

48

    g0g1 = split(g1);    

49

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

50

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

51

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

52

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

53

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

54

    for i in range(N):

55

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

56

            print 'error position',i

57

​

58

m = 4; K = GF(2); F.<a> = GF(2^m); delta = 3

59

PR = PolynomialRing(F,'X')

60

X = PR.gen()

61

N = 15

62

L = [a^i for i in range(N)]

63

g = X^3 + X + 1

64

print 'polinômio de Goppa'

65

print g

66

T = matrix(F,delta,delta)

67

for i in range(delta):

68

    count = delta - i + 1 - 1

69

    for j in range(delta):

70

        if i > j:

71

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

72

            count = count + 1

73

        if i < j:

74

            T[i,j] = 0

75

        if i == j:

76

            T[i,j] = 1

77

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

78

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

79

H = T*V*D

80

#print H #descomentar para olhar a matrix de teste de paridade em GF(2^m)

81

​

82

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

83

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

84

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

85

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

86

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

87

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

88

print 'matrix de teste de paridade'

89

print H_Goppa_K

90

​

91

krnl = H_Goppa_K.right_kernel();

92

G_Goppa = krnl.basis_matrix();

93

print 'matrix geradora'

94

print G_Goppa #descomentar para olhar a matrix geradora

95

​

96

#Caso de prova

97

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

98

print 'vetor a codificar'

99

print u

100

c = u*G_Goppa

101

print 'vetor codificado'

102

print c

103

e = vector(K,N)

104

#Suponhamos que ao vetor c é adicionado erros nas posições 2 e 3

105

e[2] = 1 

106

e[3] = 1

107

print 'vetor erro'

108

print e

109

y = c + e

110

print 'vetor c com erro'

111

print y

112

print 'decodificando'

113

decodePatterson(y)

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

---

Messages

[1] N.J Patterson, ``The Algebraic Decoding of Goppa Codes", { IEEE Transactions on Information Theory}, IT-21(2):203-207, 1974. ¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!