Возможно это не финал решения, но из нашего общения в коментариях я вынес предположение, что строка у вас хранится в виде
"абвгдежзийклмнопрстуфхцчшщъыьэюя"
дальше суть проблемы:
position =alphabet.find('я') # 31
newPosition = position + key # 36
alphabet [newPosition] # ааааа! нет такой буквы
предпологаю, что вы хотели забацать шифр соломона, в котором при переходе через край счёт начинается заново
position =s.find('я') # 31
newPosition = (position + key) % len(alphabet) # 4
alphabet [newPosition] # д
кстати не забывайте, что либо в алфавите должны быть и строчные и прописные буквы, либо перед шифрованием всё нужно приводить к тому регистру, в котором хранится ваш словарь.
А из-за чего сдвиг шифра неправильный без понятия: скиньте ка свой алфавит.