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

[TyVik]

плиз, под хабракат описание метода :)
насколько я помню, SHA-1 теоретически ломается (американцы переходят на SHA-2). Способ генерации хорош, только порой легче jz на jnz поправить :) Хм, кстати, а можно ж так всю программу зашифровать…

[codecity]

Работает все просто.

Закрытый ключ в этом алгоритме — это массив случайно сгенерированных чисел. Этот массив условно разбивается на группы по 5 байт. Находится хеш каждой группы (для усложнения находится и хеш от хеша несколько сотен тысяч раз). Эти хеши образуют открытый ключ (их можно укоротить для экономии места на диске).

Подпись закрытым ключем делается так:

Находится хеш исходного сообщения. Берем 3 первых байта этого хеша, и находим в ЗАКРЫТОМ ключе элемент (из 5-ти байт) с таким порядковым номером. Если получилось число большее, чем всего есть элементов — используем остаток от деления.

Проверка подписи открытым ключем так:

Находится хеш исходного сообщения. Берем 3 первых байта этого хеша, и находим в ОТКРЫТОМ ключе элемент с таким порядковым номером. Если хеш подписи равен этому элементу открытого ключа — значит подпись верна. Иначе — подпись не верна.

Надеюсь не слишком запутано. Для большей ясности можно посмотреть пример (есть только на C#).

[galaxy]

То есть Вы выдаете кусок своего приватного ключа, каждый раз, когда подписываете, прекрасно…
Взломать с теми исходными данными, что Вы дали я не берусь, но имхо, для массового подписывания чего-либо метод непригоден, ибо через какое-то время гулять по миру будет большая часть Вашего ключа.
К тому же метод неустойчив к replay атакам: если случайно совпадет pos (позиция в массиве, которую Вы получаете их хеша), злоумышленник сможет подписать свои данные. Т.к. pos — индекс в достаточно небольшом массиве, это отнюдь не невероятно. К тому же злоумышленник может специально добавлять в свои данные мусор, пока не случится коллизия.
Т.о., при условии, что я уловил суть, применение у алгоритма весьма ограниченное и специфическое.

[codecity]

Вы верно уловили суть. Алгоритм подходит только для тех случаев, когда сложно заполучить несколько вариантов подписи (серийник обычно выдается один, второй достать сложно). Практически имеет смысл применить этот алгоритм, если программу используют не более 100-500 тыс. человек.

По поводу replay атак. Для серийников это не так страшно. Обычно подписывают информацию в строгом формате: к примеру, срок использования в месяцах (1 байт) + привязка к железу (4 байта). Т.е. мусор там вставить некуда.

[Tails]

Если это так просто и надежно, то почему не используется повсеместно? Почему практически ко всем программам (особенно крупным — Adobe'овские, 3dsmax) есть кейгены? :)

[codecity]

Имхо, у этих гигантов свой подход к бизнесу: сначала их пользователи юзают версию незаконно, привыкают к ней, потом этих пользователей подталкивают (всяческими методами) использовать продукт легально.

[sidristij]

Согласен. Если бы Microsoft изначально требовала бы с России бабки за лицензии, фиг бы сейчас Windows хоть в паре квартир стоял бы. Как раз в этом случае все сидели бы сейчас под никсами

[codecity]

Так можно, об этом я упомянул в начале стетьи. Но для этого нужно изменить исходный файл.

[KLUBS]

стойкость алгоритма определяется временем его использования и попыток взлома. RSA используется достаточно давно и при правильном использовании «сломать» мало шансов. Новый алгоритм, никем не используется больше т.е. шансов быть сломанным гораздо больше.
Собственно вывод, зачем изобретать велосипед? RSA продержится еще…

[codecity]

RSA — старый и надежный. И хотя современная криптография активно пропагандирует алгоритмы на эллиптических кривых — RSA позиции не охотно уступает.

Единственная проблема в отношении генерации серийных номеров с RSA — попись (и серийный номер) получается длинной.

Предложенный мной алгоритм — абсолютно не претендует на роль аналога RSA. А вот для генерации серийников для простых программ (с десятками тысяч пользователей) — вполне подойдет.

[Roder]

В таблице выше приведено время взлома, при котором цифровая подпись проверяется 1 сек.
…
Время наложения подписи очень маленькое, несколько миллисекунд (INTRICACY = 256), в реальных проектах его нужно увеличить.

Создатель генератора не будет проверять ключ с помощью проекта, он сам реализует проверку в кейгене вытащив ее из программы. Закладываться в расчетах стойкости на то, что проверяться будет долго из-за искусственных ограничений — ошибка.

[codecity]

Идея в том, чтобы даже теоретически невозможно было проверить подпись быстрее, чем за x секунд процессорного времени (на средней машине).

Вот сколько на средней машине займет 1 млн. нахождений хеша от хеша?

Хотя, мне вот недавно сообщили, что циклическое получение хешей (т.е. хеш от хеша много раз подряд) — теоретически можно упростить. Насколько это просто и можно ли что-нибуль придумать, чтобы упрощение стало невозможным — пока не могу сказать.

[Midas]

Почему бы не использовать разные методы хеширования, чередуя их применение — тогда такой опасности не будет.

[naum]

Вы на wasm'e в crypto раздел запостите целиком. Тот же Ruptor посмотрит, уже приятно будет.