在Sage上使用密码系统NTRU的KEM/DEM

Question

首先,我必须说我使用Sage数学的知识非常有限,但我真的想改进并能够解决我遇到的这些问题.我被要求实施以下内容:

使用密码系统NTRU的Sage实现和库"加密"来构建具有128位安全性的KEM/DEM系统,生成128位的密钥,并且在DEM阶段,使用128位的密码AES.

在尝试解决时,我遇到了sage中NTRU-Prime的实现,并希望用它来解决这个问题:

我的遗产:

p = 739; q = 9829; t = 204
Zx.<x> = ZZ[]; R.<xp> = Zx.quotient(x^p-x-1)
Fq = GF(q); Fqx.<xq> = Fq[]; Rq.<xqp> = Fqx.quotient(x^p-x-1)
F3 = GF(3); F3x.<x3> = F3[]; R3.<x3p> = F3x.quotient(x^p-x-1)

import itertools

def concat(lists):
    return list(itertools.chain.from_iterable(lists))

def nicelift(u):
    return lift(u + q//2) - q//2

def nicemod3(u): # r in {0,1,-1} with u-r in {...,-3,0,3,...}
    return u - 3*round(u/3)

def int2str(u,bytes):
    return ''.join([chr((u//256^i)%256) for i in range(bytes)])

def str2int(s):
     return sum([ord(s[i])*256^i for i in range(len(s))])

def encodeZx(m): # assumes coefficients in range {-1,0,1,2}
    m = [m[i]+1 for i in range(p)] + [0]*(-p % 4)
    return ''.join([int2str(m[i]+m[i+1]*4+m[i+2]*16+m[i+3]*64,1) for i in range(0,len(m),4)])

def decodeZx(mstr):
    m = [str2int(mstr[i:i+1]) for i in range(len(mstr))]
    m = concat([[m[i]%4,(m[i]//4)%4,(m[i]//16)%4,m[i]//64] for i in range(len(m))])
    return Zx([m[i]-1 for i in range(p)])

def encodeRq(h, nBits = 9856):
    h = [lift(h[i]) for i in range(p)] + [0]*(-p % 3)
    h = ''.join([int2str(h[i]+h[i+1]*10240+h[i+2]*10240^2,5) for i in range(0,len(h),3)])
    return h[0:(nBits/8)]

def decodeRq(hstr):
    h = [str2int(hstr[i:i+5]) for i in range(0,len(hstr),5)]
    h = concat([[h[i]%10240,(h[i]//10240)%10240,h[i]//10240^2] for i in range(len(h))])
    if max(h) >= q: raise Exception("pk out of range")
    return Rq(h)

def encoderoundedRq(c,nBits):
    c = [1638 + nicelift(c[i]/3) for i in range(p)] + [0]*(-p % 2)
    c = ''.join([int2str(c[i]+c[i+1]*4096,3) for i in range(0,len(c),2)])
    return c[0:1109]

def decoderoundedRq(cstr):
    c = [str2int(cstr[i:i+3]) for i in range(0,len(cstr),3)]
    c = concat([[c[i]%4096,c[i]//4096] for i in range(len(c))])
    if max(c) > 3276: raise Exception("c out of range")
    return 3*Rq([c[i]-1638 for i in range(p)])

def randomR(): # R element with 2t coeffs +-1
    L = [2*randrange(2^31) for i in range(2*t)]
    L += [4*randrange(2^30)+1 for i in range(p-2*t)]
    L.sort()
    L = [(L[i]%4)-1 for i in range(p)]
    return Zx(L)

def keygen():
    while True:
        g = Zx([randrange(3)-1 for i in range(p)])
        if R3(g).is_unit(): break
    f = randomR()
    h = Rq(g)/(3*Rq(f))
    pk = encodeRq(h)
    return pk,encodeZx(f) + encodeZx(R(lift(1/R3(g)))) + pk


import hashlib

def hash(s): h = hashlib.sha512(); h.update(s); return h.digest()

def encapsulate(pk):
    h = decodeRq(pk)
    r = randomR()
    hr = h * Rq(r)
    m = Zx([-nicemod3(nicelift(hr[i])) for i in range(p)])
    c = Rq(m) + hr
    fullkey = hash(encodeZx(r))
    return fullkey[:32] + encoderoundedRq(c,128),fullkey[32:]

def decapsulate(cstr,sk):
    f,ginv,h = decodeZx(sk[:185]),decodeZx(sk[185:370]),decodeRq(sk[370:])
    confirm,c = cstr[:32],decoderoundedRq(cstr[32:])
    f3mgr = Rq(3*f) * c
    f3mgr = [nicelift(f3mgr[i]) for i in range(p)]
    r = R3(ginv) * R3(f3mgr)
    r = Zx([nicemod3(lift(r[i])) for i in range(p)])
    hr = h * Rq(r)
    m = Zx([-nicemod3(nicelift(hr[i])) for i in range(p)])
    checkc = Rq(m) + hr
    fullkey = hash(encodeZx(r))
    if sum([r[i]==0 for i in range(p)]) != p-2*t: return False
    if checkc != c: return False
    if fullkey[:32] != confirm: return False
    return fullkey[32:]


print("Exe 2")
print("")
pk,sk =  keygen()
c,k   =  encapsulate(pk)
k     == decapsulate(c,sk)
print("")
print("{:d} bytes in public key that is {:d} bits".format(len(pk),len(pk)*8))
print("{:d} bytes in secret key that is {:d} bits".format(len(sk),len(sk)*8))
print("{:d} bytes in ciphertext that is {:d} bits".format(len(c),len(c)*8))
print("{:d} bytes in shared secret that is {:d} bits".format(len(k),len(k)*8))

现在我知道我可以用它来解决上面提到的问题.我假设问题中提到的密钥是私钥,因为这是我们生成的密钥(我是对的吗？)所以我知道我必须编辑这个函数:

def keygen():
    while True:
        g = Zx([randrange(3)-1 for i in range(p)])
        if R3(g).is_unit(): break
    f = randomR()
    h = Rq(g)/(3*Rq(f))
    pk = encodeRq(h) #Encode private key with 128 bits
    return pk,encodeZx(f) + encodeZx(R(lift(1/R3(g)))) + pk

为了做到这一点,我尝试编辑在这个上使用的函数encodeRq只编码128位,但这带来了许多我无法理解的编译错误.但至少我是否正确地假设它在这里我必须设置我的密钥以128位生成？

我相信问题中提到的KEM是用函数封装处理的,并且相信我不需要改变任何东西(我是对的吗？)

最大的问题是DEM阶段,我认为是在功能解封装上实现的(我是对的吗？)但是我应该如何改变它以使用AES？我怎么在圣人身上做到这一点？我应该知道的任何图书馆？

我在这里有点迷失,只是想知道我的假设是否正确并在正确的道路上表明.谢谢你提前回答.