А что, если вместо AES попробовать хеш? При старте приложения генерируется крутая соль. А потом результат хешируется. Ну а соль можно держать в кеше приложения.
Так я вовсе отказался от шифрования. Поскольку сейчас правильный ответ для капчи хранится в сессии, то я не вижу смысла его дополнительно шифровать, нагружать процессор лишний раз
SimpleMvcCaptcha, или мой первый опыт Open Source