Python - 304

import random
r=raw_input
R=lambda s:range(len(s))
o=lambda c:ord(c)-65
j=''.join
if r()[0]=='D':
 s=r('>')
 d=r('>')
 print j(chr((o(s[i])-o(d[i]))%26+65)for i in R(s))
else:
 s=r('>')
 d=[random.randint(0,26)for i in R(s)]
 print j(chr((o(s[i])+d[i])%26+65)for i in R(s))
 print j(chr(n+65)for n in d)

I believe that this meets the specs exactly (Including the '>' at the start of the input prompts.) It does not validate input, so I think that it will just produce garbage output if you give it characters outside of [A-Z]. It also only checks the first letter of the input command. Anything starting with D will result in a decryption and anything else at all will result in an encryption.