Pull to refresh

Асимметричный алгоритм для генерации коротких серийных номеров

Lumber room
Введение

Хуже всего, когда для вашей программы создан генератор серийных номеров. Взломанные (переделанные) версии программ используют куда менее охотно – есть риск подхватить вирус или потерять данные. А вот когда есть возможность скачать подлинную программу с официального сайта и самостоятельно сгенерировать номер – это катастрофа для разработчика.


Единственный известный мне способ обезопасить себя от SNG (Serial Number Generator) – применение асимметричного алгоритма цифровой подписи. В таком случае, генерируется 2 ключа: открытый и закрытый. В программе зашит открытый ключ, он служит для проверки серийных номеров. Закрытый ключ есть только у разработчика: с его помощью можно сгенерировать серийный номер (по сути, серийный номер является подписью имени пользователя и лицензионной информации).

Подобрать закрытый ключ и сделать SNG в таком случае – практически невозможно. Данная защита взламывается только созданием модифицированной версии программы с подменой публичного ключа. Но и это не всегда простая задача.

Очень часто разработчики применяют RSA, в качестве алгоритма цифровой подписи для геренации SN. Очевидный недостаток: SN получается весьма длинным. Вот подпись ключом длиной 512 бит (практически, минимальная длина ключа):

7095C60FC9ABE8968A1DDB8A9E36FCF0DBDDAC6ACE0B648E9ED72B6DC7E06880
ACF7DCC058A7433340B01E2409579210B8ACE2B3F663D2368ACEE815E3FF6E1B


Очевидно, что такой SN ввести с этикетки коробочной версии продукта или продиктовать по телефону будет довольно проблематично :)

Какие же есть решения?

Один из известных алгоритмов цифровой подписи с короткой подписью – HFE. К сожалению, он запатентован и его использование стоит денег.

Теперь о главном

Хочу предложить вашему вниманию альтернативный алгоритм с открытым/закрытым ключом, который идеально подходит для генерации коротких серийных номеров. Он очень простой, надежный и абсолютно бесплатный. К статье прикреплен файл с реализацией алгоритма на языке C#.

Алгоритм весьма простой, но достаточно устойчив против SNG.

По вопросу авторства. Мне не встречалось описание этого алгоритма, по-этому пока считаю себя его первооткрывателем (пусть даже он очень простой). Если кто-нибудь докажет обратное, буду благодарен.

Итак, несколько фактов об этом алгоритме:

Данные приведены в формате: длина подписи; процессорное время, необходимое для взлома:

4 байта ~100 лет
5 байт ~35 тыс. лет
6 байт 8 млн. лет

Как видите, даже очень короткая подпись является весьма надежной. Хотя, время взлома можно задавать в разумных пределах: чем большее время взлома вы зададите, тем дольше будет и проверяться цифровая подпись, тем дольше будут генерироваться открытый/закрытый ключи. В таблице выше приведено время взлома, при котором цифровая подпись проверяется 1 сек. (вполне приемлемо для проверки SN при регистрации программы). За время подписи отвечает константа INTRICACY, объявленная в классе KuSigner.

Второй важный параметр – длина ключа. Чем длиннее ключ, тем меньше коллизий, но и тем дольше он генерируется. Длина должна быть равной количеству продвинутых недобросовестных пользователей вашей программы (у которых хватит ума и наглости объединиться с целью поиска коллизий).

Стойкость алгоритма основана на необратимости функции хеширования. В моей реализации используется алгоритм MD4 (моя собственная реализация на C#). Хотя в этом алгоритме (MD4) найдены коллизии и для многих задач он не подходит, для нашей задачи он является вполне надежным. Параноики, конечно, могут заменить его на SHA1.

Чтобы понять в деталях как работает мой алгоритм – лучше всего посмотрите исходный код. Имхо, так будет проще всего.

Теперь несколько простых примеров использования моего кода:

1. Генерация ключей:

KuSigner kuSigner = new KuSigner(1000, 5); // стойкость ключа (в недобросовестных клиентах :)), длина подписи<br><br>kuSigner.GenerateKeys(); // генерация ключей: открытый и закрытый<br><br>* This source code was highlighted with Source Code Highlighter.


2. Экспорт ключа в xml:

string publicKey = kuSigner.ToXmlString(false); // только публичный ключ<br><br>string privateKey = kuSigner.ToXmlString(true); // оба ключа, и публичный и приватный<br><br>* This source code was highlighted with Source Code Highlighter.


3. Восстановление ключа из xml:

KuSigner publicSigner = new KuSigner(publicKey);<br>KuSigner privateSigner = new KuSigner(privateKey);<br><br>* This source code was highlighted with Source Code Highlighter.


4. Подпись строки:

byte[] signatureBytes = privateSigner.Sign(Encoding.UTF8.GetBytes("Подписываемая строка"));<br><br>// для красоты, байты можно представить в виде строки (серийный номер)<br>string signatureString = BitConverter.ToString(signatureBytes).Replace("-", string.Empty);<br><br>* This source code was highlighted with Source Code Highlighter.


5. Проверка подписи строки:

bool isValid = privateSigner.VerifySignature(Encoding.UTF8.GetBytes("Подписываемая строка"), signatureBytes);<br><br>* This source code was highlighted with Source Code Highlighter.


Теперь, для затравки, предлагаю вам взломать этот алгоритм (не бесплатно!).

Я выкладываю открытый ключ (с такими же параметрами, как в примере выше: длина 5 байт, стойкость 1000). Время наложения подписи очень маленькое, несколько миллисекунд (INTRICACY = 256), в реальных проектах его нужно увеличить. Приватный ключ оставляю у себя.

Далее, даю несколько строк и их подписи моим закрытым ключом:

1. Строка (здесь и далее без кавычек): «Привет мир», подпись: 945D50CCFD
2. Строка: «test», подпись: 4C4CA4C336
3. Строка: «test2», подпись: EF20C68781

Вы можете проверить эти подписи, используя открытый ключ, который расположен в архиве, прикрепленном к статье.

А теперь внимание! Кто сможет получить подпись строки «Вася Пупкин», тому дам 25 WMZ. Вполне серьезно. Сумма, конечно, не большая, но ведь в этом вопросе главное не деньги…

Учтите, что проверить подпись строки «Вася Пупкин» сможет любой (публичный ключ есть). А вот наложить подпись могу только я (если вы докажете обратное, получите приз и общественное признание :)).

Жду ваших комментариев!

P.S.
Самое главное: ссылка на архив с реализацией алгоритма и с публичным ключом.
Tags: цифровая подпись
Hubs: Lumber room
Total votes 29: ↑26 and ↓3 +23
Comments 15
Comments Comments 15