Расшифровать сообщение RSA с цензурой части закрытого ключа?

Итак, у меня возникла эта проблема, и я понятия не имею, как ее решить.

У меня есть закрытый ключ RSA, часть которого подверглась цензуре.

$ cat key.pem
-----BEGIN RSA PRIVATE KEY-----
MIICXQIBAAKBgQDGlcensoredcensoredcensoredcensored1TUxhnjkCbowxZc
7PIpI1E2Po6aIgCBd9+6i0NUIfYm8vR6kqiqLz8k8o4LYoBkq/9Jx7pgV2Jqhr4u
wvlaQQUzi9c4qPKXp+QGoUu9f1zp8ORIMpeJmF7uA20DC93uba07qdC6twIDAQAB
AoGBAIovDuYnGiiQS6K27L4EY8e/5sbqAwdlTOVlWsfz+ai3DLNiFPSbbT1Wx9G4
4b06X6O258SD1suZ/g/ICnmnxxe5ua3a5+iiDIwGYmBDcNfq5gMq/d+1/UJF/Bb4
A1nuH2iUg6gRTPEpbg2+RYwquyWenFbqfHMgXqbHVGmOXj7hAkEA8rChKjs5zVmd
j9Gk53psry4CtuxRc39NrHuLqat9Iu0MA51Sgv4c+8dgo75DVAnT5PoLBhHJJAVa
e+rUMC4kfwJBANF7jcKzJ2UuPmL6JpbWcyirybjMIm2eCxR5U1bYlNYT+A49oOFS
Eg5woswgCyH9gDPk2Zwpq3qud9HD7Rn0bckCQQDHgwdrRXc2ZybN1eZAWffBaAzZ
PpuTXKOJWaOuX4mnTcLjsdDkWW2QWw8Kbd7B1rZ49kpbugFmeHQzjRDVbwmXAkBm
T3nFBcrP1+4QWSxPrx0/V+eFoe2OrAmtTjQtzkmi5M3Z5q+UXIkFFG3uVBgb2bur
nLHLW26s1Fkg0hgS/RZBAkAFnE+7QvRCW4+v3OsIkN63f+GIjHfCuv8L15RpBLlf
XXQyOmmu8YekTu5vbFHtSAiLyuW1yCeSsNmKYkX6Ew99
-----END RSA PRIVATE KEY-----

Как видите, первая часть строки частично подвергнута цензуре. Задача состоит в том, чтобы расшифровать это сообщение:

Qe7+h9OPQ7PN9CmF0ZOmD32fwpJotrUL67zxdRvhBn2U3fDtoz4iUGRXNOxwUXdJ2Cmz7zjS0DE8
ST5dozBysByz/u1H//iAN+QeGlFVaS1Ee5a/TZilrTCbGPWxfNY4vRXHP6CB82QxhMjQ7/x90/+J
LrhdAO99lvmdNetGZjY=

Мое первое предположение состояло в том, чтобы перебрать отсутствующую часть, но это не кажется реалистичным.

Кто-нибудь знает, возможно ли это вообще? И если да, то как бы вы собирались это сделать? Длина ключа составляет 824 символа, а цензурированная часть - 32 символа, однако я не знаю, соответствует ли каждый символ цензуры одному в закрытом ключе...


encryption rsa private-key cryptography
person user3080544    schedule 08.12.2013    source источник
comment
Вам нужно изучить кодировку (ASN.1) и сначала выяснить, что подвергается цензуре. Если это просто публичный прайм, то их относительно мало, и это будет быстро.   -  person Thomas M. DuBuisson    schedule 08.12.2013
comment
У вас есть открытый ключ? Брут-форс будет означать, что вам придется попробовать варианты $2 ^ 192$, чего я не советую :P   -  person Maarten Bodewes    schedule 08.12.2013
comment
@owlstead Нет, у меня нет открытого ключа :( И да, я подозревал, что это будет глупо: я посмотрел на polarssl.org/kb/cryptography/asn1-key-structures-in-der-and-pem и некоторые другие объяснения, но я могу похоже, не нашел хорошего разбивки на разные части ключа..   -  person user3080544    schedule 08.12.2013
comment
Просто попробуйте методом грубой силы перекомпоновать этот закрытый ключ формата PEM. Если это не удается, он возвращается к тому же уровню защиты, что и полное отсутствие закрытого ключа. (Это все еще может стоить вам жизни).   -  person Ken Cheung    schedule 08.12.2013

Ответы (1)


arrow_upward
4
arrow_downward

Вы можете решить эту с помощью онлайн ASN.1 парсер (или OpenSSL asn1parse), где вы узнаете, что база 64 строка - текст в середине, между линиями, начиная с --- - является кодировкой ASN.1 закрытого ключа. Второй элемент в ПОСЛЕДОВАТЕЛЬНОСТИ, который был изменен, содержит модуль, а не частный показатель. Структура определена в PKCS#1, который является довольно читаемым стандартом, также скопированным в RFC 3447

Модуль обычно общедоступен, но если у вас нет открытого ключа, вы все равно можете его воссоздать: Как факторизовать модуль RSA с учетом общедоступного и частного показателей?

person Maarten Bodewes    schedule 08.12.2013
comment
Хорошо, спасибо. Итак, что мне нужно сделать сейчас, когда у меня есть e, d, p и q. Чтобы воссоздать m и снова закодировать его? А потом заменить его в ключе и расшифровать? - person user3080544; 09.12.2013
comment
Да, воссоздайте n, модуль, как вы описали. Обычно n используется для модуля, но всегда ожидайте различий в обозначениях. - person Maarten Bodewes; 09.12.2013
comment
Есть ли у вас какие-либо советы по этому поводу? Когда я воссоздаю n путем умножения p и q, числа настолько велики, что у меня возникают проблемы с преобразованием в шестнадцатеричный формат. Пытался сделать это напрямую с шестнадцатеричными числами, но в итоге получил 1059-битное представление. Результат должен быть 1024 бит, верно? - person user3080544; 09.12.2013
comment
Да, модуль всегда совпадает с размером ключа. Я не пробовал предложенное решение, я просто знал, что искать... Попробуйте crypto.stackexchange.com, если у вас возникли проблемы с самим алгоритмом, или задайте здесь отдельный вопрос, разместив свой текущий код. Обратите внимание, что данный модуль должен содержать достаточно правильных битов для проверки результатов с помощью двоичного сравнения. - person Maarten Bodewes; 09.12.2013