Decrypting a block of AES
Python, 661 chars

R=range
I=lambda x:[int(x[2*i:2*i+2],16)for i in R(16)]
k=I(raw_input())
c=I(raw_input())
P=[]
x=1
for i in R(512):P+=[x];x^=x*2^(x&gt;&gt;7)*0x11b
S=[255&amp;(99^j^(j&gt;&gt;4)^(j&gt;&gt;5)^(j&gt;&gt;6)^(j&gt;&gt;7))for i in R(256)for j in[(P[255-P.index(i)]if i else 0)*257]]
for r in R(10):
 for i in R(4):k+=[k[-16]^S[k[-3-(i&gt;2)*4]]]
 k[-4]^=[1,2,4,8,16,32,64,128,27,54][r]
 for i in R(12):k+=[k[-16]^k[-4]]
for r in R(11):
 c=[x^y for x,y in zip(k[160-16*r:],c)]
 if r&gt;9:break
 for i in[0,4,8,12]*(r&gt;0):c[i:i+4]=[x^y^z^w for j in R(4)for x,y,z,w in[[P[a+P.index(v)]if v else 0 for a,v in zip((2*[104,238,199,223])[3-j:],c[i:i+4])]]]
 c=(c*13)[::13];c=map(S.index,c)
print''.join(map(chr,c))


k is the key, c is the ciphertext.  I build P, the powers of 3 in the field, then S, the sbox.  Then k is extended with the key schedule.  Finally we do the AES decryption.  Mixcolumns is the hard phase, all the other phases are pretty straightforward.