RSA - следующий уровнь проблем

Теперь у меня все в порядке - RSA работает быстро по проверке подписи и 70 секунд у поставщика на генерацию одной лицензии 1024-битным ключом.

Но тут вырисовалась новая проблема.

Дело в том, что злоумышленник может сгенерировать свою пару открытый+закрытый ключ и подсунуть программе свой открытый ключ и свою лицензию.

Соответственно, нужно еще отличать настоящую лицензию от подделки.

Можно, конечно, хранить разрешенные ключи в программе, но есть два недостатка:

1. При вводе новой пары в оборот нужно перекомпилировать программу.

2. Строку ключа или даже MD5 ключа легко найти в коде EXE-файла и заменить на свои. Это даже проще, чем отладка и патчинг кода. Можно даже написать постоянный патч, который ищет эту строку и меняет ее на нужную. Будет работать на всех последующих версиях программы.

Что-то я  в тупике. А теперь подскажите, как это можно сделать по-нормальному?