Судя по вашим комментариям, симметричное шифрование должно помочь вам - не говоря уже о том, что оно будет быстрее асимметричного. Возможно, вы захотите взглянуть на класс RijndaelManaged - он такой же, как реализация AES, но у вас больше гибкости с точки зрения размеров блоков.
Теперь, говоря о безопасности, это будет зависеть от того, насколько защищен ваш ключ. В вашем случае вы говорите о сохранении его в коде. Поэтому вам необходимо защитить свой код / сборки (скажем, если он будет лежать в среде управляемого сервера). Лучшим вариантом было бы поместить ключ в файл конфигурации (если файлы конфигурации хранятся в контролируемой среде, они предлагают гибкость его изменения). В случае, если вы хотите вставить код и код / сборку, но хотите защитить от атак обратного инжиниринга - путаница в сочетании со стеганографией была бы подходящим вариантом. Ниже пара статей о реализации стеганографии в .NET: