Генерация ключей RSA с помощью PGP
Как с помощью PGP сгенерировать, например, 1024-битовый открытый ключ (m=p*q) в виде 128-байтовой последовательности или, что ещё лучше, десятичного числа, а также узнать 512-битовые числа p и q (в том же виде), которые использовались для его генерации? Жедательно для PGP 2.6.3i. Но можно и для более новых версий PGP.
При генерации ключей PGP, в частности, создаёт файл Pubring.pgp. Но в этом файле кроме ключа находится ещё что-то. Хотелось бы знать, можно ли выделить ключ из этого файла и, если это возможно, как это сделать?
Есть специальная утилита pgpdump, предназначенная для раскодировки различных пакетов OpenPGP в удобочитаемый формат. Можно получить значения модуля и экспоненты любого ключа в виде шестнадцатеричного числа; перевести исчисление на любое другое основание труда не составит.
Обычным способом установить сомножители m Вам не удастся — они участвуют только в процессе генерации ключа, не покидая ОЗУ, после чего уничтожаются. Так что либо адаптируйте код программы, чтобы просто выдавала сомножители m, либо, что предпочтительней, используйте специализированное ПО, коего немало.
pgpdump с веб-интерфейсом:
http://www.pgpdump.net/
pgpdump в исходных текстах под unix:
ftp://pgp.iijlab.net/pub/pgp/tools/pgpdump-0.22.tar.gz
pgpdump для Windows:
http://pgpngpg.front.ru/gpg/pgpdump.zip
О, спасибо! Я уж думал не найду его нигде после закрытия сайта Имада.
Добавлено:
Только версия старовата...
Всем большое спасибо!
Уважаемый SATtva, у меня ещё два вопроса.
1. О каком специализированном ПО Вы говорите? (Линки и т.д., плиз :-))
2. С каким объёмом энтропийных данных работает гамма-генератор PGP? (Вопрос не совсем по теме, но всё-таки)
1. См. на sourceforge. Возможно, OpenSSL и другие криптобиблиотеки к месту придутся (точные ссылки Paranoid Ant приводил, воспользуйтесь поиском по форуму).
2. Постоянно обновляемый пул произвольных значений, получаемый от движений мыши, интервалов между нажатиями клавиш, показаний системного таймера, сопровождающих каждое из событий. Это истинные непредсказуемые случайности. Случайные числа для векторов инициализации, ключевого и прочего материала генерируются по методике ANSI X9.17.
У меня ещё два вопроса.
Первый вопрос.
При расшифровке файла, содержащего открытый ключ, программа PGPDump, в частности, выдаёт
RSA e(5 bits) – 11
Это и есть экспонента шифрования? И, если да, не слишком ли она мала? Не являются ли данные ключи слабыми? Возможна ли в данном случае атака по методу low-exponent attack?
Второй вопрос, вытекающий из первого, ещё интереснее.
Сначала цитата (откуда – неважно, везде одно и то же):
"Итак, генерация RSA-ключей (чисел m/d/e) заключается в следующем:
Так вот – вопрос. Как осуществляется подбор чисел p и q, чтобы экспонентой шифрования оказалось некое заранее заданное число? Какие условия для этого необходимо задать? И почему это число, как правило задаётся жёстко? В PGP 2.6.3i – 11 (?). Для RSA Factoring Challenge числа генерировались с использованием экспоненты 65537 (F4).
И ещё, можно ли при генерации ключей с помощью PGP 2.6.3i самому произвольно задать экспоненту шифрования?
И как генерировать только открытый ключ, без закрытого? (Чтобы не надо было набирать произвольный текст)
Малая экспонента повышает скорость выполнения криптографических операций; надёжность схемы понижается только тогда, когда реализация допускает шифрование множества (собственно, множества, равного e) идентичных сообщений разными ключами с одинаковым показателем e. В PGP это невозможно, ибо шифруемые сообщения представляют собой шифртексты, произведённые с помощью абсолютно случайных сеансовых симметричных ключей.
Если малая экспонента Вас всё же смущает (PGPdump, кстати, выдаёт числовые параметры в шестнадцатеричном виде, и Ваше "11" в десятичном счислении равно 17) поставьте версию PGP поновее. Текущие восьмые используют упомянутый показатель e = 65537.
Второй вопрос сложнее, алгоритм генерации привести не могу. Вы сами лучше разберётесь, если посмотрите на исходный текст программы. Но примерно процедура сводится к следующему: берётся некоторое начальное значение, от него по возрастающей (или по убывающей) производится поиск подходящего кандидата на простое число, проверяя каждый на удовлетворение определённому комплексному критерию. Если тест пройден, поиск прекращается. Если нет — продолжается дальше по возрастающей (или по убывающей). В нашем случае НОД является одним из критериев проверки.
Без внесения изменений в исходный код — нет.
Могу я поинтересоваться, зачем нужен открытый ключ без закрытого? Это односторонняя функция получится. Сейф, из которого ничего достать нельзя.
Поинтересоваться, конечно можно. Открытые ключи без закрытых нужны мне для проверки моих теорий в отношении факторизации ключей. Преимущественно, массовой. То есть, меня интересует возможность факторизации не одного ключа, а одного ключа из n. Сам я PGP в целях, для которых она создана, пока не пользуюсь. А изучение возможностей факторизации ключей RSA является моим хобби. Очень увлекательное занятие, понимаете ли :).
Большое спасибо за ответы на мои вопросы.
Всегда пожалуйста, DimP. Держите в курсе своих изысканий.
PGPDUMP v 0.19 от 15.06.03
http://www.chez.com/winterminator/pgpdump.zip
По RSA:
Подскажите пожалуйста, можно ли с помощью pgpdump получить закрытый ключ (private key) в виде шестнадцатеричной последовательности.
Открытый я получил (с Вашей помощью ;) ) – это, я так понимаю, e
а по закрытому в дампе: Encrypted RSA d
ПС: Поиском пользовался :)
Да, можно и закрытый: так же скармливаете пгпдампу private key block, предварительно сняв с ключа парольную фразу (иначе закрытые показатели будут encrypted).
Респект :)
Мне нужно сгенерировать ключ из с++ 6.0. Тоже ничего найти не могу толком..
Flame_xXx, Вам сюда[link1], в третий пункт.
Топик называется "Генерация ключей RSA с помощью PGP". Потому фраза "Мне нужно сгенерировать ключ из с++ 6.0" видимо вещает о попытке найти библиотеку, которая позволила бы это сделать (сгенерить PGP-ключ типа RSA) самым простым/надёжным способом.
Тогда автору вопроса стоит посмотреть в сторону gpgme[link2].