Возможно ли отыскать открытый ключ, если известен закрытый(он вшит в программу)? А то для кейгена необходимо. Еще есть триальный ключ, вшитый в программу. Этих данных достаточно, или публичный ключ найти не удастся?

Я бы сказал, что известен открытый, хотя в принципе без разницы. Если там RSA 512 бит (или меньше) и у тебя есть доступ к хорошему компу (лучше нескольким) то факторизовать реально, недавно после 2 лет факторизовали 576(?)-битный RSA распределенными вычислениями.

В приватный ключ публичный входит как составляющая

„Я бы сказал, что известен открытый, хотя в принципе без разницы. Если там RSA 512 бит (или меньше) и у тебя есть доступ к хорошему компу (лучше нескольким) то факторизовать реально, недавно после 2 лет факторизовали 576(?)-битный RSA распределенными вычислениями.“

ага, на 10 000 машинах.

факторизовать рельно, но чтобы такое сделать на одном или нескольких компах, надо научиться логарифмировать в поле простого числа. Как составляющая для этого надо знать все простые числа от 1 до sqrt(N).
& В современной математике пока не было публикаций, что такое умеют делать для больших чисел.

З.Ы.
Сори если с терминами немного попутал, в голове бардак, почти неделю не спал...

Хе , я тоже такое спрашивал у народа , думал что будет просто :)

Я так понял из твоих слов что тебе известен закрытй ключ, т.е. число D (Private Exponent), а тебе необходимо найти открытый ключ, т.е. числа E(Public Exponent) и N (Modulus).
Если в этой программе используется расшифровка с помощью RSA (а она используется т.к. тебе известен ключ D), то в этой проге просто обязано присутствовать число N, т.к.
M=C^D mod N,
где C - шифротекст, M - сообщение , а '^'- это степень такая.
Так что смотри в проге где-то должно быть число N.
Значит остается найти только число E, которое обычно равно
10001h, а если не равно то его можно подобрать т.к. оно обычно относительно небольшое.

techgl
Ты наверно хочешь найти закрытый ключ, ведь открытый - он на то и открытый, что всем известен. Хотя, вобщем-то, без разницы - с точки зрения алгоритма они равноправны. А, зная одну часть ключа, ты не найдёшь вторую часть за разумное время, если создатели программы не дураки и выбрали необходимую длину ключа.

techgl
„меня на такие мысли натолкнула сигнатура:
'PKF'\x0x0A\x01.... “

Судя по гуглу , то PKF это public key file используемый в SecretAgent

Выдержка из доки :
Key Generation Options-Z# math (ring/field; for key generation only)
1 SA2-compatible 512-bit DSA p/q/g
2 *DSA 512-bit
3 DSA 1024-bit
4 RSA 512-bit (e = F3)
5 RSA 768-bit (e = F3) (unused?)
6 RSA 1024-bit (e = F3)
7 Fortezza

Ты хочешь закейгенить SecretAgent ?

Ухмм... Ухмм... Буду краток и без всяких "понтов"... :)
То что там ломают всякие ботаны, типа RSA-576 - можно просто забыть... ;)

К сведению: TMG - факторизовали RSA-384 (MPQS): 3 недели,
3 компьютера.

Первым делом найди публичный ключ и определи его размер.
Если он больше 400 бит - капец. Тогда сможешь написать только кейген-патч.
Иначе качай PPSIQS (или что нибудь альтернативное), разбирайся как это работает, ищи компы, на которых будешь распределенно факторизовать.

Это был первый способ.

Способ №2. Определи BigNum Library, на основе которрой реализована регистрационная защита. Открою один "секрет":
некоторые из них используют т.н. weak prime number generator. Т.е. в чем фишка: seed в random generator'е создается, например, на базе текущего времени, с помощью него генерятся P и Q, ну а N=P*Q. Т.е. количество значений seed почти ограничено. Т.о. определяешь имеет ли твоя либа эту уязвимость. Если так, то садишься и разбираешься как генерятся P и Q. Пишешь затем брутфорс, который переберёт все возможные значения seed: генеришь P и Q, получаешь N, сравниваешь со своим: совпало - пишешь в файл, ну и всё такое.

Так даже RSA-2048 сломали. ;)

Вот вообщем и всё. :)

P.S.
А что там за программа ?

„Способ №2. Определи BigNum Library,“
такое есть только в очень старых версиях этих библиотек/защит. Мне встречались программы с защитой, которая (защита) стоит больше $1000, а использовался 17 битный RSA, плюс оба множителя (приватный+публичный) тоже имелись :)
techgl
вообще лучше с теории начать...

Отвечу скорее всего всем. А именно, опишу, что взламываю, и что успел раскопать. Пациент - Network Serial Port Kit(последняя версия, если его уже взломали, мне не интересно, хочу докопать сам, раз уж взялся).

Программа состоит из двух частей - клиент(служит для управления) и сервер(выполняет непосредственные функции программы). Форма регистрации находится в клиенте. Структура ключа такова:
typedef struct
{
char md5hash[16]; // это хеш посчитанный от 3 полей ниже
char username[256];
char compname[256];
int license;//кол-во дней. Если 0, то Unlimited
} KeyData;

typedef struct
{
char md5hash[16]; // MD5 хеш всего кейблока
char pkf_magic[4]; // это сигнатура 'PKF'\x0x0A
int pkf_num; // я не понял что это, но по программе должно быть равно единице
char res_table[64]; // это видимо ключ, или его часть, см. ниже
KeyData kd; // информация о пользователе она в исходном ключе шифруется
} KeyBlock;

Все это "одевается" в ASCII Armor, и окантовываетя таким вот:
-----BEGIN NETWORKSERIALPORTKIT KEY BLOCK-----
-----END NETWORKSERIALPORTKIT KEY BLOCK-----

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

Там то, что я уже описывал:
rsa_init(c_table, c_tablelen, f_table, f_tablelen, table, tablelen); /*
table - 64 бита, это KeyBlock.res_table
c_table - ­константа(видимо или e, или часть ключа)
db 19h, 0AFh, 70h, 0BDh, 0ABh, 0D5h, 9Fh, 88h, 0, 0C0h
db 86h, 40h, 58h, 5, 9Ah, 0A3h, 7Ah, 5Ah, 1Fh, 0EEh, 42h
db 0Fh, 24h, 7Ch, 7, 0DFh, 0ADh, 9, 0F6h, 20h, 40h, 81h
db 70h, 0C0h, 3Ah, 0D4h, 38h, 0C0h, 94h, 0A2h, 53h, 66h
db 6Bh, 66h, 0B5h, 5Ch, 61h, 12h, 0B8h, 0CDh, 51h, 5Ch
db 8Fh, 86h, 0B2h, 0Bh, 24h, 38h, 0BFh, 43h, 0E9h, 0C6h
db 0ECh, 0C9h
rsa_modtable(pk_table, table);
rsa_decrypt(pk_table, inbuf, outbuf, inbuflen);

Сервер расшифровывает KeyData и считает ее хеш, если хеш не совпадает с KeyData.md5_hash - Wrong Key. Иначе - счастье.

В программу вшит trial_key, в нем, поле lisence = 15. Поэтому через 15 дней программа перестает работать.

По поводу библиотеки работы с числами, там используется MPI, и самописные функции работы с такими числам.

Вот все, что есть на данный момент. Самая сложная - это rsa_init. Там большая вложенность. Копать тяжло. Если ее раскопать, то кейген можно считать написаным.

Непонятно, почему вы говорите что закрытый ключ в программе все равно что открытый. Я читал описание RSA, там шифруется Открытым ключем, а вот расшифоровать только Закрытым.

„Я читал описание RSA, там шифруется Открытым ключем, а вот расшифоровать только Закрытым.“

Это при шифровании/расшифровании.
При подписи все наоборот: данные подписываются закрытым ключом (сервер), а проверяются открытым (твоя программа).
По крайней мере, так должно быть. Иначе просто теряется всякий смысл в прикручивании ассиметричной криптографии.

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

„
А если ты знаешь открытый ключ, то получить закрытый сложно -- нужно решить задачу разложения модуля на простые сомножители, т.е. факторизовать модуль, а это для адекватных длин модуля вычислительно очень сложно.
“
Тоесть даже имея триальный ключ и зная "что" в нем и имея открытый ключ нельзя получить закрытый? Каким образом тогда ломают такие программы, если учесть что патчить нельзя, ибо там хитрая система проверок, завязаная на функции самой программы(в разных местах вызывается код и происходит ряд преобразований). Патчить сложно.

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

а программы такие AFAIK наиболее просто ломать патч+кейген: пропатчиваешь в экзешнике ключик на "правильный" и пишешь под него кейген. Хотя такое не всегда годится.

„Непонятно, почему вы говорите что закрытый ключ в программе все равно что открытый. Я читал описание RSA, там шифруется Открытым ключем, а вот расшифоровать только Закрытым.“

Читал значит невнимательно или не то, что надо.

„Тоесть даже имея триальный ключ и зная "что" в нем и имея открытый ключ нельзя получить закрытый? Каким образом тогда ломают такие программы, если учесть что патчить нельзя, ибо там хитрая система проверок, завязаная на функции самой программы(в разных местах вызывается код и происходит ряд преобразований). Патчить сложно.“

Нет, тебе определенно стоит матчасть подучить сначала, а потом уже браться RSA ковырять :)