First of all, I have to say that my knowledge using Sage math is really very limited, but I really want to improve and be able to solve these problems that I have. I was asked to implement the following:
Use the STR implementation of the NTRU cryptosystem and cryptography library to create a KEM / DEM system with 128-bit security, a generated 128-bit key, and use the 128-bit AES cipher in the DEM phase.
While trying to solve, I came across an implementation of NTRU-Prime in sage and wanted to use it to solve this problem:
My Attemp:
p = 739; q = 9829; t = 204 Zx.<x> = ZZ[]; R.<xp> = Zx.quotient(x^px-1) Fq = GF(q); Fqx.<xq> = Fq[]; Rq.<xqp> = Fqx.quotient(x^px-1) F3 = GF(3); F3x.<x3> = F3[]; R3.<x3p> = F3x.quotient(x^px-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 ur 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))
Now I know that I can use this to move on to solving the above question. I assume that the key mentioned in the question is the private key because it is the one we generate (am I right?), So I know that I need to edit this function:
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)
To do this, I tried editing the encodeRq function used on this to encode only 128 bits, but this caused a lot of compilation of errors that I simply could not understand. But at least I have the right to assume this here, where should I set my key to generate with 128 bits?
I believe that the KEM mentioned in the question is handled by function encapsulation and believes that I don't need to change anything (am I right?)
The biggest problem is really the DEM phase, which I assume is implemented in the decapsulation function (am I right?), But how should I change this to use AES? How do I do this for a sage? any library I should know about?
I got a little lost here and just want to know if my assumptions are correct and is being shown on the right path. Thanks for any answer in advance.