-rw-r--r-- 15260 mceliece-sage-20221023/byterepr.sage raw
import parameters
import controlbits
def from_vector(v):
r'''
Return the byte string representing bit vector v.
INPUT:
"v" - a list of bits
'''
v = [int(vj) for vj in v]
assert all(vj in (0,1) for vj in v)
r = len(v)
expectedlen = ceil(r/8)
if r%8 != 0:
# "If r is not a multiple of 8
# then an r-bit vector v = (v_0,v_1,...,v_{r-1}) in F_2^r
# is zero-padded on the right to length between r+1 and r+7,
# whichever is a multiple of 8"
padding = [0]*(8-(r%8))
assert len(padding) >= 1
assert len(padding) <= 7
v = v+padding
assert len(v)%8 == 0
# "and then represented as above"
r = len(v)
assert r == len(v)
assert r%8 == 0
assert expectedlen == r/8
# "the following sequence of r/8 bytes:
# (v_0+2v_1+4v_2+...+128v_7,
# v_8+2v_9+4v_10+...+128v_15,
# ...,
# v_{r-8}+2v_{r-7}+4v_{r-6}+...+128v_{r-1})"
b = [sum(int(v[j*8+i])<<i for i in range(8)) for j in range(r/8)]
assert len(b) == expectedlen
return bytes(bytearray(b))
def to_vector(b,r,narrowly=True):
r'''
Return the list of r bits
represented by byte string b.
Raise an exception if b has the wrong length.
INPUT:
"b" - bytes
"r" - a nonnegative integer
"narrowly" (optional, default True) -
raise a ValueError exception if there are padding bits with nonzero value
'''
assert parent(b) == bytes
r = ZZ(r)
assert r >= 0
assert narrowly in (True,False)
b = list(bytearray(b))
assert len(b) == ceil(r/8)
v = [1&(bi>>j) for bi in b for j in range(8)]
assert len(v) == 8*len(b)
if narrowly:
# "Narrowly Decoded Classic McEliece rejects inputs ...
# where padding bits are nonzero"
if any(vi != 0 for vi in v[r:]):
raise ValueError('padding bits do not all have value 0')
v = v[:r]
assert all(vj in (0,1) for vj in v)
assert len(v) == r
return v
def randombits_from_randombytes(randombytes):
def randombits(r):
# parameter sets allowed in this implementation have r%8 == 0
assert r%8 == 0
v = randombytes(r//8)
return to_vector(v,r)
return randombits
def from_sessionkey(K,params):
r'''
Return the byte string representing session key K.
INPUT:
"K" - a list of l bits
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
l = params.l
# "A session key K is an element of F_2^l.
# It is represented as a ceil(l/8)-byte string."
K = list(K)
assert len(K) == l
b = from_vector(K)
assert len(b) == ceil(l/8)
return b
# not used in tests currently
def to_sessionkey(b,params):
r'''
Return the session key represented by byte string b.
INPUT:
"b" - a byte string
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
l = params.l
assert len(b) == ceil(l/8)
K = to_vector(b,l)
assert len(K) == l
return K
def from_ciphertext(C,params):
r'''
Return the byte string representing ciphertext C.
INPUT:
"C" - a list of m*t bits
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
t = params.t
if parameters.supportpc:
# for testing against previous versions
if params.pc:
C0,C1 = C
return from_vector(C0)+from_vector(C1)
# "A ciphertext C is an element of F_2^{mt}.
# It is represented as a ceil(mt/8)-byte string."
C = list(C)
assert len(C) == m*t
b = from_vector(C)
assert len(b) == ceil(m*t/8)
return b
def to_ciphertext(b,params):
r'''
Return the ciphertext represented by byte string b.
INPUT:
"b" - a byte string
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
t = params.t
if parameters.supportpc:
# for testing against previous versions
if params.pc:
l = params.l
b0,b1 = b[:ceil(m*t/8)],b[ceil(m*t/8):]
return to_vector(b0,m*t),to_vector(b1,l)
assert len(b) == ceil(m*t/8)
C = to_vector(b,m*t)
assert len(C) == m*t
return C
def from_hashinput(x,params):
r'''
Return the byte string representing hash input x.
INPUT:
"x" - a hash input
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
n = params.n
m = params.m
t = params.t
if parameters.supportpc:
# for testing against previous versions
if params.pc:
if x[0] == 2:
assert len(x) == 2
return bytes(bytearray([2]))+from_vector(x[1])
u,v,C = x
u = int(u)
v = list(v)
return bytes(bytearray([u]))+from_vector(v)+from_ciphertext(C,params)
# "There are two types of hash inputs: (1,v,C), and (0,v,C).
# Here v in F_2^n, and C is a ciphertext."
u,v,C = x
u = int(u)
assert u in (0,1)
v = list(v)
assert len(v) == n
# "The initial 0 or 1 is represented as a byte."
result = bytes(bytearray([u]))
# "The vector v is represented as the next ceil(n/8) bytes."
result += from_vector(v)
# "The ciphertext is represented as the next ceil(mt/8) bytes."
result += from_ciphertext(C,params)
# "All hash inputs thus begin with byte 0 or 1"
assert bytearray(result)[0] in (0,1)
assert len(result) == 1+ceil(n/8)+ceil(m*t/8)
return result
def from_publickey(T,params):
r'''
Return the byte string representing public key T.
INPUT:
"T" - an mt x k matrix over F_2
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
t = params.t
k = params.k
# "The public key T, which is an mt x k matrix,
# is represented in a row-major fashion.
# Each row of T is represented as a ceil(k/8)-byte string,
# and the public key is represented as
# the mt ceil(k/8)-byte concatenation of these strings."
assert T.nrows() == m*t
assert T.ncols() == k
b = b''.join(from_vector(Ti) for Ti in T)
assert len(b) == m*t*ceil(k/8)
return b
def to_publickey(b,params):
r'''
Return the public key represented by byte string b.
INPUT:
"b" - a byte string
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
t = params.t
k = params.k
assert len(b) == m*t*ceil(k/8)
rows = [to_vector(b[j*ceil(k/8):(j+1)*ceil(k/8)],k) for j in range(m*t)]
T = matrix(GF(2),rows)
assert T.nrows() == m*t
assert T.ncols() == k
return T
def from_fieldelement(u,params):
r'''
Return the byte string representing field element u.
INPUT:
"u" - an element of F_q
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
uint = u.integer_representation()
ubits = [1&(uint>>j) for j in range(m)]
b = from_vector(ubits)
assert len(b) == ceil(m/8)
return b
def to_fieldelement(b,params):
r'''
Return the field element represented by byte string b.
INPUT:
"b" - a byte string
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
Fq = params.Fq
assert len(b) == ceil(m/8)
ubits = to_vector(b,m)
u = Fq(ubits)
assert from_fieldelement(u,params) == b
return u
def from_poly(g,params):
r'''
Return the byte string representing monic degree-t polynomial g.
INPUT:
"g" - a monic degree-t polynomial in F_q[x]
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
t = params.t
# "The monic-irreducible degree-t polynomial
# g = g_0 + g_1 x + ... + g_{t-1} x^{t-1} + x^t
# is represented as t ceil(m/8) bytes,
# namely the concatenation of the representations
# of the field elements g_0,g_1,...,g_{t-1}."
assert g.degree() == t
assert g.is_monic()
# this encoding doesn't care about irreducibility
b = b''.join(from_fieldelement(g[i],params) for i in range(t))
assert len(b) == t*ceil(m/8)
return b
def to_poly(b,params):
r'''
Return the monic degree-t polynomial represented by byte string b.
INPUT:
"b" - a byte string
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
t = params.t
Fq = params.Fq
Fqx.<x> = Fq[]
assert len(b) == t*ceil(m/8)
coeffs = [to_fieldelement(b[i*ceil(m/8):(i+1)*ceil(m/8)],params) for i in range(t)]
g = Fqx(coeffs+[1])
assert g.degree() == t
assert g.is_monic()
return g
def from_fieldordering(alpha,params):
r'''
Return the byte string representing field ordering alpha.
INPUT:
"alpha" - a list of q distinct elements of F_q
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
q = params.q
Fq = params.Fq
# "a sequence (alpha_0,...,alpha_{q-1})
# of q distinct elements of F_q"
alpha = list(alpha)
assert len(alpha) == q
assert len(set(alpha)) == q
assert sorted(alpha) == sorted(Fq)
# "Define pi as the permutation of {0,1,...,q-1}
# such that alpha_i = sum_{j=0}^{m-1} pi(i)_j * z^{m-1-j}
# for all i in {0,1,...,q-1}."
alphaint = [alpha[i].integer_representation() for i in range(q)]
pi = [sum(((alphaint[i]>>(m-1-j))&1)<<j for j in range(m)) for i in range(q)]
# "The ordering (alpha_0,...,alpha_{q-1}) is represented
# as a sequence of (2m-1)2^(m-1) control bits
# for an in-place Benes network for pi. ...
# This document requirs that a permutation pi be converted to
# specifically the control bits defined by controlbits in Figure 1."
c = controlbits.controlbits(pi)
assert len(c) == (2*m-1)<<(m-1)
# "This vector is represented as ceil((2m-1)2^{m-4}) bytes as above."
b = from_vector(c)
assert len(b) == ceil((2*m-1)*2^(m-1)/8)
return b
def to_fieldordering(b,params):
r'''
Return the field ordering represented by byte string b.
INPUT:
"b" - a byte string
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
q = params.q
Fq = params.Fq
assert len(b) == ceil((2*m-1)*2^(m-1)/8)
c = to_vector(b,(2*m-1)<<(m-1))
pi = controlbits.permutation(c)
alpha = [Fq([1&(pi[i]>>(m-1-j)) for j in range(m)]) for i in range(q)]
assert len(alpha) == q
assert len(set(alpha)) == q
assert sorted(alpha) == sorted(Fq)
return alpha
def from_columnselection(c,params):
r'''
Return the byte string representing column selection c.
INPUT:
"c" - a list of mu integers in increasing order between mt-mu and mt-mu+nu-1
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
t = params.t
mu = params.mu
nu = params.nu
# "a sequence c = (c_{mt-mu},...,c_{mt-1}) of mu integers
# in increasing order between mt-mu and mt-mu+nu-1."
c = [int(cj) for cj in c]
assert len(c) == mu
assert c == sorted(set(c))
assert all(cj >= m*t-mu for cj in c)
assert all(cj <= m*t-mu+nu-1 for cj in c)
# "represented as a ceil{nu/8}-byte string,
# the little-endian format of the integer
# sum_{i=0}^{mu-1} 2^{c_{mt-mu+i}-(mt-mu)}."
cint = sum(2^(ci-(m*t-mu)) for ci in c)
b = from_vector([1&(cint>>j) for j in range(nu)])
assert len(b) == ceil(nu/8)
# "However, for (mu,nu) = (0,0),
# the sequence is instead represented as
# the 8-byte string which is the little-endian format
# of 2^32-1, i.e., 4 bytes of value 255 followed by 4 bytes of value 0."
if (mu,nu) == (0,0):
assert len(b) == 0
b = bytes(bytearray([255,255,255,255,0,0,0,0]))
assert len(b) == 8
return b
def to_columnselection(b,params):
r'''
Return the column selection represented by byte string b.
INPUT:
"b" - the byte string (255,255,255,255,0,0,0,0) if (mu,nu) = (0,0);
otherwise a byte string of length ceil(nu/8)
with exactly mu bits set
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
t = params.t
mu = params.mu
nu = params.nu
if (mu,nu) == (0,0):
assert b == bytes(bytearray([255,255,255,255,0,0,0,0]))
return []
assert len(b) == ceil(nu/8)
cvec = to_vector(b,nu)
c = [m*t-mu+j for j in range(nu) if cvec[j] != 0]
assert len(c) == mu
assert c == sorted(set(c))
assert all(cj >= m*t-mu for cj in c)
assert all(cj <= m*t-mu+nu-1 for cj in c)
return c
def from_privatekey(priv,params):
r'''
Return the byte string representing private key priv.
INPUT:
"priv" - a private key (delta,c,g,alpha,s)
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
n = params.n
t = params.t
l = params.l
mu = params.mu
nu = params.nu
# "A private key (delta,c,g,alpha,s) is represented
# as the concatenation of five parts:"
delta,c,g,alpha,s = priv
# "The ceil(l/8)-byte string representing delta in F_2^l."
assert len(delta) == l
b0 = from_vector(delta)
assert len(b0) == ceil(l/8)
# "The string representing the column selections c.
# This string has ceil(nu/8) bytes,
# or 8 bytes of (mu,nu) = (0,0)."
b1 = from_columnselection(c,params)
assert len(b1) == 8 if (mu,nu) == (0,0) else ceil(nu/8)
# "The t ceil(m/8)-byte string representing the polynomial g."
b2 = from_poly(g,params)
assert len(b2) == t*ceil(m/8)
# "The ceil((2m-1)2^(m-4)) bytes representing the field ordering alpha."
b3 = from_fieldordering(alpha,params)
assert len(b3) == ceil((2*m-1)*2^(m-4))
# "The ceil(n/8)-byte string representing s in F_2^n."
assert len(s) == n
b4 = from_vector(s)
assert len(b4) == ceil(n/8)
b = b0+b1+b2+b3+b4
return b
def to_privatekey(b,params):
r'''
Return the private key represented by byte string b.
INPUT:
"b" - a byte string
"params" - a Classic McEliece parameter set
'''
assert isinstance(params,parameters.parameters)
m = params.m
n = params.n
t = params.t
l = params.l
mu = params.mu
nu = params.nu
b0len = ceil(l/8)
b1len = 8 if (mu,nu) == (0,0) else ceil(nu/8)
b2len = t*ceil(m/8)
b3len = ceil((2*m-1)*2^(m-4))
b4len = ceil(n/8)
assert len(b) == b0len+b1len+b2len+b3len+b4len
b0,b = b[:b0len],b[b0len:]
b1,b = b[:b1len],b[b1len:]
b2,b = b[:b2len],b[b2len:]
b3,b = b[:b3len],b[b3len:]
b4,b = b[:b4len],b[b4len:]
delta = to_vector(b0,l)
c = to_columnselection(b1,params)
g = to_poly(b2,params)
alpha = to_fieldordering(b3,params)
s = to_vector(b4,n)
return delta,c,g,alpha,s
# ----- miscellaneous tests
def test_vector():
assert from_vector([0,0,1,0]) == b'\4'
assert from_vector([0,0,0,1,0,0,1,0, 1,0,1,0,0,1,1,0]) == b'He'
assert to_vector(b'He',16) == [0,0,0,1,0,0,1,0, 1,0,1,0,0,1,1,0]
assert to_vector(b'He',15) == [0,0,0,1,0,0,1,0, 1,0,1,0,0,1,1]
assert to_vector(b'He',14,narrowly=False) == [0,0,0,1,0,0,1,0, 1,0,1,0,0,1]
ok = False
try:
assert to_vector(b'He',14) == [0,0,0,1,0,0,1,0, 1,0,1,0,0,1]
except:
ok = True
assert ok
for r in range(100):
print('bitvector %d' % r)
sys.stdout.flush()
v = [randrange(2) for i in range(r)]
b = from_vector(v)
assert len(b) == ceil(r/8)
assert v == to_vector(b,r)
assert v == to_vector(b,r,narrowly=False)
if __name__ == '__main__':
test_vector()