"""Offline public-vector study of CMAC, AES-GCM and AES-SIV.
Python standard library only. Public fixed keys, no randomness or external state.
This readable AES uses table lookups and Python integers: NOT constant time and
NOT a production crypto library. Explicit require() checks remain active under -O.
seal/tag raise ValueError on invalid parameters; open/verify return failure.
GCM callers must allocate unique 12-byte nonces under each secret key.
SIV associated-data components are ordered, immutable bytes; optional nonce is
its last AD component. No interface provides replay detection.
"""
from hmac import compare_digest
import json
MASK=(1<<128)-1
LIMIT=1<<20

def require(b,s):
 if not b:raise ValueError(s)
def hx(s):return bytes.fromhex(s)
def xor(a,b):
 require(len(a)==len(b),'xor width');return bytes(x^y for x,y in zip(a,b))
def check_bytes(x):require(type(x) is bytes,'immutable bytes required')
def gf8(a,b):
 out=0
 for _ in range(8):
  if b&1:out^=a
  a=((a<<1)^ (0x11b if a&128 else 0))&255;b>>=1
 return out
def power8(a,e):
 out=1
 while e:
  if e&1:out=gf8(out,a)
  a=gf8(a,a);e>>=1
 return out
def sub_byte(a):
 x=power8(a,254) if a else 0;y=x^0x63
 for k in range(1,5):y^=((x<<k)|(x>>(8-k)))&255
 return y
SBOX=tuple(sub_byte(i) for i in range(256))
class AES128:
 def __init__(self,key):
  check_bytes(key);require(len(key)==16,'AES-128 key');w=list(key);rc=1
  while len(w)<176:
   temp=w[-4:]
   if len(w)%16==0:
    temp=[SBOX[x] for x in temp[1:]+temp[:1]];temp[0]^=rc;rc=gf8(rc,2)
   for v in temp:w.append(w[-16]^v)
  self.rk=[w[i:i+16] for i in range(0,176,16)];self.calls=0
 def __call__(self,block):
  check_bytes(block);require(len(block)==16,'AES block');self.calls+=1;s=list(xor(block,bytes(self.rk[0])))
  for rnd in range(1,11):
   s=[SBOX[x] for x in s];s=[s[r+4*((c+r)%4)] for c in range(4) for r in range(4)]
   if rnd!=10:
    z=[]
    for i in range(0,16,4):
     a,b,c,d=s[i:i+4];z.extend((gf8(a,2)^gf8(b,3)^c^d,a^gf8(b,2)^gf8(c,3)^d,a^b^gf8(c,2)^gf8(d,3),gf8(a,3)^b^c^gf8(d,2)))
    s=z
   s=[x^y for x,y in zip(s,self.rk[rnd])]
  return bytes(s)
def dbl(b):
 require(len(b)==16,'dbl width');v=int.from_bytes(b,'big');return (((v<<1)&MASK)^(0x87 if v>>127 else 0)).to_bytes(16,'big')
def pad(b):
 require(len(b)<16,'pad short block');return b+b'\x80'+bytes(15-len(b))
class CMAC:
 def __init__(self,key):
  self.aes=AES128(key);self.L=self.aes(bytes(16));self.k1=dbl(self.L);self.k2=dbl(self.k1)
 def tag(self,m,trace=None):
  check_bytes(m);require(len(m)<=LIMIT,'teaching message limit');n=max(1,(len(m)+15)//16);full=bool(m) and len(m)%16==0
  last=xor(m[-16:],self.k1) if full else xor(pad(m[16*(n-1):]),self.k2);state=bytes(16)
  for i in range(n):
   b=last if i==n-1 else m[16*i:16*i+16];state=self.aes(xor(state,b))
   if trace is not None:trace.append(dict(index=i,formatted=b.hex(),chain=state.hex()))
  return state
 def verify(self,m,t):
  try:return type(t) is bytes and len(t)==16 and compare_digest(self.tag(m),t)
  except ValueError:return False
def cbc_mac(key,m):
 require(len(m)>0 and len(m)%16==0,'raw CBC whole blocks');aes=AES128(key);s=bytes(16)
 for i in range(0,len(m),16):s=aes(xor(s,m[i:i+16]))
 return s
# GHASH maps the leftmost wire bit to the constant coefficient.
IDENTITY=1<<127
R=0xe1000000000000000000000000000000
def gmul(x,y):
 require(0<=x<=MASK and 0<=y<=MASK,'GF128 element');z=0;v=y
 for i in range(128):
  if x&(1<<(127-i)):z^=v
  v=(v>>1)^(R if v&1 else 0)
 return z
def gpow(x,e):
 require(e>=0,'power exponent');z=IDENTITY
 while e:
  if e&1:z=gmul(z,x)
  x=gmul(x,x);e>>=1
 return z
def ginv(x):
 require(x!=0,'nonzero field divisor');return gpow(x,(1<<128)-2)
def ghash(h,blocks,trace=None):
 require(len(blocks)%16==0,'GHASH aligned');s=0
 for i in range(0,len(blocks),16):
  b=blocks[i:i+16];s=gmul(s^int.from_bytes(b,'big'),h)
  if trace is not None:trace.append(dict(block=b.hex(),chain=s.to_bytes(16,'big').hex()))
 return s.to_bytes(16,'big')
def gcm_lengths(a,c,n,t=16):
 require(all(type(x) is int and x>=0 for x in (a,c,n,t)),'nonnegative byte lengths')
 require(n==12 and t==16,'GCM fixed IV/tag variant');require(a<=(1<<61)-1 and c<=(1<<36)-32,'GCM standard length')
def encoded_ac(a,c):
 return a+bytes((-len(a))%16)+c+bytes((-len(c))%16)+(8*len(a)).to_bytes(8,'big')+(8*len(c)).to_bytes(8,'big')
def counter_xor(aes,initial,data,width,trace=None):
 check_bytes(initial);check_bytes(data);require(len(initial)==16,'counter block');require(width in (32,128),'counter width');q=int.from_bytes(initial,'big');low=(1<<width)-1;out=[]
 require((len(data)+15)//16<=1<<width,'counter cycle')
 for off in range(0,len(data),16):
  j=off//16;cb=((q&~low)|((q+j)&low)).to_bytes(16,'big');stream=aes(cb);b=data[off:off+16];out.append(xor(b,stream[:len(b)]))
  if trace is not None:trace.append(dict(counter=cb.hex(),stream=stream.hex()))
 return b''.join(out)
class GCM:
 def __init__(self,key):self.aes=AES128(key);self.h=int.from_bytes(self.aes(bytes(16)),'big')
 def validate(self,n,a,c):
  for b in (n,a,c):check_bytes(b)
  gcm_lengths(len(a),len(c),len(n));require(len(a)+len(c)<=LIMIT,'teaching total limit')
 def tag(self,n,a,c,trace=None):
  self.validate(n,a,c);j0=n+b'\0\0\0\1';return xor(self.aes(j0),ghash(self.h,encoded_ac(a,c),trace))
 def seal(self,n,a,p,trace=None):
  self.validate(n,a,p);ct=[];gh=[];c=counter_xor(self.aes,n+b'\0\0\0\2',p,32,ct if trace is not None else None);t=self.tag(n,a,c,gh if trace is not None else None)
  if trace is not None:trace.update(counter=ct,ghash=gh,h=self.h.to_bytes(16,'big').hex(),j0=(n+b'\0\0\0\1').hex())
  return c,t
 def open(self,n,a,c,t):
  try:
   self.validate(n,a,c)
   if type(t) is not bytes or len(t)!=16 or not compare_digest(self.tag(n,a,c),t):return None
  except ValueError:return None
  return counter_xor(self.aes,n+b'\0\0\0\2',c,32)
def forge_one_block(c1,t1,c2,t2,chosen):
 for b in (c1,t1,c2,t2,chosen):check_bytes(b);require(len(b)==16,'one-block/full-tag attack')
 dc=int.from_bytes(xor(c1,c2),'big');require(dc!=0,'distinct ciphertexts');dt=int.from_bytes(xor(t1,t2),'big');h2=gmul(dt,ginv(dc));tf=xor(t1,gmul(int.from_bytes(xor(c1,chosen),'big'),h2).to_bytes(16,'big'))
 return tf,h2
class SIV:
 def __init__(self,key):
  check_bytes(key);require(len(key)==32,'SIV-CMAC-256 total key');self.mac=CMAC(key[:16]);self.enc=AES128(key[16:])
 def validate(self,ad,p):
  require(type(ad) in (tuple,list) and len(ad)<=126,'at most126 AD components');check_bytes(p)
  for a in ad:check_bytes(a)
  require(sum(map(len,ad))+len(p)<=LIMIT,'teaching total limit')
 def s2v(self,parts,trace=None):
  require(type(parts) in (tuple,list) and len(parts)<=127,'S2V components')
  for p in parts:check_bytes(p)
  require(sum(map(len,parts))<=LIMIT,'teaching total limit')
  if not parts:return self.mac.tag(bytes(15)+b'\1')
  d=self.mac.tag(bytes(16));rows=[]
  for a in parts[:-1]:
   tag=self.mac.tag(a);d=xor(dbl(d),tag)
   if trace is not None:rows.append(dict(tag=tag.hex(),d=d.hex()))
  last=parts[-1];long=len(last)>=16;t=last[:-16]+xor(last[-16:],d) if long else xor(dbl(d),pad(last));v=self.mac.tag(t)
  if trace is not None:trace.update(ad_steps=rows,final_branch='xorend' if long else 'short',final_input=t.hex(),v=v.hex())
  return v
 def seal(self,ad,p,trace=None):
  self.validate(ad,p);v=self.s2v(list(ad)+[p],trace);q=bytearray(v);q[8]&=127;q[12]&=127;ct=[];c=counter_xor(self.enc,bytes(q),p,128,ct if trace is not None else None)
  if trace is not None:trace.update(q=bytes(q).hex(),counter=ct)
  return v+c
 def open(self,ad,z):
  try:
   check_bytes(z)
   if len(z)<16:return None
   v,c=z[:16],z[16:];self.validate(ad,c);q=bytearray(v);q[8]&=127;q[12]&=127;p=counter_xor(self.enc,bytes(q),c,128)
   if not compare_digest(self.s2v(list(ad)+[p]),v):return None
   return p
  except ValueError:return None

def edge_checks(k,m,key,nonce,ad1,p1,k1,k2,ad2,p2):
 rejected=[]
 def rejects(name,f):
  try:f()
  except ValueError:rejected.append(name);return
  raise RuntimeError('missing parameter rejection: '+name)
 for name,args in [('aad overflow',((1<<61),0,12)),('plaintext overflow',(0,(1<<36)-31,12)),('IV length',(0,0,13)),('tag length',(0,0,12,15)),('negative length',(-1,0,12)),('bool length',(False,0,12))]:rejects(name,lambda args=args:gcm_lengths(*args))
 gcm_lengths((1<<61)-1,(1<<36)-32,12)
 for name,fn in [('AES key',lambda:AES128(bytes(15))),('SIV key',lambda:SIV(bytes(16))),('mutable bytes',lambda:CMAC(k).tag(bytearray())),('teaching limit',lambda:CMAC(k).tag(bytes(LIMIT+1))),('AD arity',lambda:SIV(k1).seal([b'']*127,b'')),('S2V arity',lambda:SIV(k1).s2v([b'']*128)),('field division zero',lambda:ginv(0))]:rejects(name,fn)
 mac=CMAC(k);tr=[];before=mac.aes.calls;t48=mac.tag(m[:48],tr);require(mac.aes.calls-before==3,'48-byte CMAC count')
 g=GCM(key);trg={};before=g.aes.calls;c,t=g.seal(nonce,b'abc',bytes(17),trg);require(g.aes.calls-before==3 and len(trg['ghash'])==4,'GCM AES/GHASH counts')
 require(g.open(nonce,b'abc',c,t)==bytes(17) and g.open(nonce,b'abc',c,t)==bytes(17),'GCM allows replay')
 mutations=0
 for off in range(len(t)):
  bad=t[:off]+bytes([t[off]^1])+t[off+1:];require(g.open(nonce,b'abc',c,bad) is None,'GCM tag mutation');mutations+=1
 require(not mac.verify(None,bytes(16)) and not mac.verify(b'',b'') and g.open(bytes(11),b'',b'',bytes(16)) is None,'malformed verification')
 s=SIV(k1);short_trace={};z=s.seal(ad1,p1,short_trace);before=s.mac.aes.calls+s.enc.calls;long_trace={};long=s.seal(ad1,p1+b'\0\0',long_trace)
 require(s.mac.aes.calls+s.enc.calls-before==5 and long_trace['final_branch']=='xorend','SIV 16-byte cost/branch')
 empty=dict(zero_components=s.s2v([]).hex(),empty_plaintext=s.seal([],b'').hex(),empty_ad_and_plaintext=s.seal([b''],b'').hex());require(len(set(empty.values()))==3,'empty vector distinctions in this sample')
 require(s.seal(ad1,p1)==z and s.open(ad1,z)==p1 and s.open(ad1,z)==p1,'SIV determinism and replay')
 s2=SIV(k2);z2=s2.seal(ad2,p2);changed=s2.seal(ad2,p2+b'!');require(changed[:16]!=z2[:16],'same nonce different sample')
 require(s2.open([ad2[1],ad2[0],ad2[2]],z2) is None,'AD order authenticated')
 require(s.seal([b'ab',b'c'],b'x')!=s.seal([b'a',b'bc'],b'x'),'field boundaries in this sample')
 for off in range(len(z2)):
  bad=z2[:off]+bytes([z2[off]^1])+z2[off+1:];require(s2.open(ad2,bad) is None,'SIV bit mutation');mutations+=1
 require(s.open([],b'') is None and s.open([bytearray()],z) is None,'SIV malformed')
 require(len(s.seal([b'']*126,b''))==16,'maximum AD component arity')
 a20=hx('3ad77bb40d7a3660a89ecaf32466ef97f5d3d585');pp=hx('d9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39');cc,tt=g.seal(nonce,a20,pp);cc2,tt2=g.seal(nonce,a20+b'\0',pp)
 e1,e2=encoded_ac(a20,cc),encoded_ac(a20+b'\0',cc2);different=[i//16 for i in range(0,len(e1),16) if e1[i:i+16]!=e2[i:i+16]]
 require(cc==cc2 and different==[6] and tt!=tt2,'AAD zero changes only length block in this sample')
 # A recording primitive tests counter carry independently from encryption.
 class Recorder:
  def __init__(self):self.seen=[]
  def __call__(self,b):self.seen.append(b.hex());return bytes(16)
 carry={}
 for width in (32,128):
  rec=Recorder();counter_xor(rec,hx('000000000000000000000001ffffffff'),bytes(17),width);carry[str(width)]=rec.seen
 require(carry['32'][1]=='00000000000000000000000100000000' and carry['128'][1]=='00000000000000000000000200000000','counter width carry')
 return dict(rejections=rejected,tag_or_ciphertext_mutations=mutations,aad_zero_extension=dict(changed_block_indices=different,tag=tt2.hex(),length_block=e2[-16:].hex()),cmac48=dict(tag=t48.hex(),trace=tr),siv16=dict(output=long.hex(),trace=long_trace),empty_cases=empty,counter_carry=carry,costs=dict(cmac48_AES=3,gcm17_AES=3,gcm17_GHASH=4,siv16_AES=5),replay_both_accept=True,swapped_AD_rejected=True,same_nonce_changed_plaintext_V=changed[:16].hex())

def main():
 k=hx('2b7e151628aed2a6abf7158809cf4f3c');m=hx('6bc1bee22e409f96e93d7e117393172aae2d8a571e03ac9c9eb76fac45af8e5130c81c46a35ce411e5fbc1191a0a52eff69f2445df4f9b17ad2b417be66c3710');a=AES128(k)
 require(a(hx('3243f6a8885a308d313198a2e0370734'))==hx('3925841d02dc09fbdc118597196a0b32'),'FIPS AES appendix B')
 mac=CMAC(k);cm=[]
 for n,t in [(0,'bb1d6929e95937287fa37d129b756746'),(16,'070a16b46b4d4144f79bdd9dd04a287c'),(40,'dfa66747de9ae63030ca32611497c827'),(64,'51f0bebf7e3b9d92fc49741779363cfe')]:
  tr=[];tag=mac.tag(m[:n],tr);require(tag==hx(t),'RFC4493');cm.append(dict(n=n,tag=tag.hex(),trace=tr))
 raw=cbc_mac(k,m[:16]);forged=m[:16]+xor(m[:16],raw);ctag=mac.tag(m[:16]);cm_attempt=m[:16]+xor(m[:16],ctag);require(cbc_mac(k,forged)==raw and mac.tag(cm_attempt)!=ctag,'tag-only CBC/CMAC comparison')
 zero=GCM(bytes(16));c,t=zero.seal(bytes(12),b'',bytes(16));require(c==hx('0388dace60b6a392f328c2b971b2fe78') and t==hx('ab6e47d42cec13bdf53a67b21257bddf'),'GCM one block')
 key=hx('feffe9928665731c6d6a8f9467308308');nonce=hx('cafebabefacedbaddecaf888');p=hx('d9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b391aafd255');aad=hx('3ad77bb40d7a3660a89ecaf32466ef97f5d3d585');g=GCM(key);gcm=[]
 for msg,ad,expected in [(b'',b'','3247184b3c4f69a44dbcd22887bbb418'),(p,b'','4d5c2af327cd64a62cf35abd2ba6fab4'),(p[:60],aad,'f07c2528eea2fca1211f905e1b6a881b')]:
  tr={};cc,tt=g.seal(nonce,ad,msg,tr);require(tt==hx(expected) and g.open(nonce,ad,cc,tt)==msg,'GCM standard');gcm.append(dict(p=msg.hex(),aad=ad.hex(),c=cc.hex(),t=tt.hex(),trace=tr))
 c1,t1=g.seal(nonce,b'',bytes(16));c2,t2=g.seal(nonce,b'',b'\x01'+bytes(15));chosen=xor(c1,b'\x80'+bytes(15));tf,h2=forge_one_block(c1,t1,c2,t2,chosen);require(h2==gmul(g.h,g.h) and g.open(nonce,b'',chosen,tf)==b'\x80'+bytes(15),'GCM fresh forgery')
 k1=hx('fffefdfcfbfaf9f8f7f6f5f4f3f2f1f0f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff');ad1=[hx('101112131415161718191a1b1c1d1e1f2021222324252627')];p1=hx('112233445566778899aabbccddee')
 k2=hx('7f7e7d7c7b7a79787776757473727170404142434445464748494a4b4c4d4e4f');ad2=[hx('00112233445566778899aabbccddeeffdeaddadadeaddadaffeeddccbbaa99887766554433221100'),hx('102030405060708090a0'),hx('09f911029d74e35bd84156c5635688c0')];p2=b'this is some plaintext to encrypt using SIV-AES';sv=[]
 for key,ad,msg,expected in [(k1,ad1,p1,'85632d07c6e8f37f950acd320a2ecc9340c02b9690c4dc04daef7f6afe5c'),(k2,ad2,p2,'7bdb6e3b432667eb06f4d14bff2fbd0fcb900f2fddbe404326601965c889bf17dba77ceb094fa663b7a3f748ba8af829ea64ad544a272e9c485b62a3fd5c0d')]:
  s=SIV(key);tr={};z=s.seal(ad,msg,tr);require(z==hx(expected) and s.open(ad,z)==msg,'RFC5297');sv.append(dict(output=z.hex(),trace=tr))
 edges=edge_checks(k,m,hx('feffe9928665731c6d6a8f9467308308'),nonce,ad1,p1,k1,k2,ad2,p2)
 print(json.dumps(dict(status='PASS',checks=edges,cmac=dict(L=mac.L.hex(),k1=mac.k1.hex(),k2=mac.k2.hex(),vectors=cm),cbc_forgery=dict(message=forged.hex(),tag=raw.hex()),gcm=gcm,gcm_forgery=dict(c1=c1.hex(),t1=t1.hex(),c2=c2.hex(),t2=t2.hex(),h2=h2.to_bytes(16,'big').hex(),chosen=chosen.hex(),forged_tag=tf.hex()),siv=sv),indent=2))
if __name__=='__main__':main()