-rw-r--r-- 4205 mceliece-sage-20221023/decode.sage raw
import goppa import parameters def decode(C,Gammaprime,params): r''' Return the output of the Classic McEliece Decode function on input (C,Gammaprime) for the specified parameters. The output is either False or a length-n vector over F_2. INPUT: "Gammaprime" - a tuple (g,alphaprime[0],...,alphaprime[n-1]) where g is a monic irreducible polynomial in F_q[x] of degree t and alphaprime[0],...,alphaprime[n-1] are distinct elements of F_q "params" - a Classic McEliece parameter set ''' assert isinstance(params,parameters.parameters) m = params.m n = params.n t = params.t k = params.k Fq = params.Fq Gammaprime = tuple(Gammaprime) assert len(Gammaprime) == n+1 g,alphaprime = Gammaprime[0],Gammaprime[1:] assert all(alphaj in Fq for alphaj in alphaprime) assert len(set(alphaprime)) == n assert g.base_ring() == Fq assert g.is_monic() assert g.is_irreducible() assert g.degree() == t assert len(C) == m*t # "Extend C to v = (C,0,...,0) in F_2^n by appending k zeros." v = list(C)+[0]*k v = list(vector(GF(2),v)) # "Find the unique c in F_2^n such that (1) Hc = 0 and # (2) c has Hamming distance <=t from v. # If there is no such c, return False. ... # Set e = v+c." e = goppa.goppa_errors(n,t,Fq,alphaprime,g,v) if e is None: return False c = vector(GF(2),[e[i]+v[i] for i in range(n)]) # "If wt(e) = t and C = He, return e. Otherwise return False." if sum(1 if ej else 0 for ej in e) != t: return False kpoly = g.parent() xminusalpha = [kpoly([-alphaprime[i],1]) for i in range(n)] A = kpoly(prod(xminusalpha)) if sum(c[i]*A//xminusalpha[i] for i in range(n))%g != 0: return False return e def test1(): import matgen import encode for system in parameters.alltests: P = parameters.parameters(system,allowtestparams=True) Fq = P.Fq Fqx.<x> = Fq[] m = P.m n = P.n t = P.t k = P.k mu = P.mu nu = P.nu tries = 0 while True: print('matgen %s' % system) sys.stdout.flush() tries += 1 while True: g = Fqx.random_element(t) if g.is_irreducible(): break g /= g.leading_coefficient() alpha = list(Fq) shuffle(alpha) alpha = alpha[:n] Gamma = tuple([g]+alpha) result = matgen.matgen(Gamma,P) if result == False: continue T = result[0] Gammaprime = result[-1] break print('successful matgen; tries: %d' % tries) sys.stdout.flush() # "T is an mt x k matrix over F_2" assert T.nrows() == m*t assert T.ncols() == k # "Gamma' has the form (g,alpha'_0,alpha'_1,...,alpha'_{n-1})" g,alphaprime = Gamma[0],Gamma[1:] assert len(alphaprime) == n # "g is a monic irreducible polynomial in F_q[x] of degree t" assert g.base_ring() == Fq assert g.is_monic() assert g.is_irreducible() assert g.degree() == t # "alpha'_0,alpha'_1,...,alpha'_{n-1} are distinct elements of F_q" assert all(alphaj in Fq for alphaj in alphaprime) assert len(set(alphaprime)) == n # ----- decoding a legitimate ciphertext e = [0]*n while sum(e) < t: e[randrange(n)] = 1 C = encode.encode(e,T,P) # "If C = Encode(e,T) then Decode(C,Gammaprime) = e." assert list(decode(C,Gammaprime,P)) == list(e) print('successful decode') sys.stdout.flush() # ----- decoding a ciphertext for weight t-1 if t > 0: while True: j = randrange(n) if not e[j]: continue edelta = vector(GF(2),[i==j for i in range(n)]) Cmod = list(C) for i in range(m*t): Cmod[i] += edelta[i]+sum(T[i,j]*edelta[j+m*t] for j in range(k)) break assert decode(Cmod,Gammaprime,P) == False print('successful anti-decode for reduced weight') sys.stdout.flush() # ----- decoding a random ciphertext # "If C does not have the form He for any weight-t vector e in F_2^n, # then Decode(G,Gamma') = False." C = vector(GF(2),[randrange(2) for j in range(m*t)]) assert decode(C,Gammaprime,P) == False print('successful anti-decode for random ciphertext') sys.stdout.flush() if __name__ == '__main__': test1()