RSA или нет? И как решить?

Сейчас на форуме: NIKOLA, Magister Yoda (+5 невидимых)

Посл.ответ	Сообщение
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 23 декабря 2017 13:58 · Поправил: BlackCode · Личное сообщение · #1 Всем привет Ковыряя одну прогу, нашел место расшифровки данных. Расшифровывается по формуле которую использует RSA, а именно M=C^E mod N Расшифровывается все замечательно (в BigInt калькуляторе), НО есть одна особенность с которой ранее не встречался. Экспонента не простое и маленькое число, а размером в 512 бит. Т.е. на входе имеем 3 больших числа. Очень смахивает на D (приватную экспоненту). Но с другой стороны как можно было додуматься до того, чтобы выкладывать на обозрение приватную экспоненту?) Но это лирика, основной вопрос - как найти экспоненту которая используется для зашифровки данных? В общем вот: 1. Exponenta (E) (или предполагаемое D) 3430573271005793006695452267181324156368743109516592241700481710266652277419066685261735003016953634335436126045392544353449574084947466473545348876238841 2. Modulus (N) 479172302014374367136527744590388998070765572707242754121694613979224426286355996880396074067948626435634895373177664122633456947301000843307115065182523 3. Message (С) зашифрованное сообщение 259106615284875988124328595337032193480340360562648068238613545278236070766712305957211783777440410022034277583160698241509968532389231246851827949409849 4. Result (М) расшифрованное сообшение 2665666868961153109325254081524702463542336007291584309863139488266268010836882871396952587406177509005395516095281754161192322007712 Заранее спасибо

ELF_7719116 Ранг: 419.0 (мудрец), 647thx Активность: 0.46↗0.51 Статус: Участник "Тибериумный реверсинг"	Создано: 23 декабря 2017 14:29 · Личное сообщение · #2 BlackCode пишет: M=C^E mod M Эм! А в случае: Code: M=C^D mod N тогда что?
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 23 декабря 2017 14:34 · Поправил: BlackCode · Личное сообщение · #3 ELF_7719116 пишет: тогда что? Как что? Расшифровка с теми данными, что я здесь выложил. Опечатался немного
DimitarSerg Ранг: 253.5 (наставник), 684thx Активность: 0.26↘0.25 Статус: Участник radical	Создано: 23 декабря 2017 17:55 · Личное сообщение · #4 BlackCode пишет: как найти экспоненту которая используется для зашифровки данных Без факторизации - никак ) Неважно, как вы буквы назовете, проблема остается та же. ----- ds \| Сообщение посчитали полезным: BlackCode
kunix Ранг: 71.2 (постоянный), 33thx Активность: 0.05↗0.12 Статус: Участник	Создано: 23 декабря 2017 18:05 · Поправил: kunix · Личное сообщение · #5 Публичная экспонента обычно маленькая. Поэтому, для начала - перебрать экспоненты до, скажем, 100000. Шифровать данные и расшифровывать приватной экспонентой. Да и 512 бит отлично факторизуется. UPD: не, походу публичная тоже большая. \| Сообщение посчитали полезным: BlackCode
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 23 декабря 2017 19:17 · Личное сообщение · #6 Факторизацию уже запустил,модулус кстати 508 бит а не 512. Надеюсь проблем с факторизацией не должно быть Добавлено спустя 2 минуты kunix Кстати в начале так и сделал, типа брута перебрал 3000000 простых чисел в прогрессии,результата не дало.
kunix Ранг: 71.2 (постоянный), 33thx Активность: 0.05↗0.12 Статус: Участник	Создано: 23 декабря 2017 19:25 · Поправил: kunix · Личное сообщение · #7 Там еще любопытно, что экспонента больше модуля. Видно, к ней k(p-1)(q-1) прибавили. Вопрос - зачем Проверил, может, экспонента это x + k(p-1)(q-1), где x - малая экспонента, но тоже не подошло.
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 23 декабря 2017 19:30 · Поправил: BlackCode · Личное сообщение · #8 kunix Вскрытие покажет. (факторинг) В принципе время уйти должно меньше чем у 512. Добавлено спустя 1 час 49 минут kunix По ходу это реально паблик экспонента Ее сделали такой большой видимо для запутывания. Я взял эту экспоненту и в РСАтулс сгенерил пару модулус и приват кей. Зашифровал и расшифровал благополучно данные. Так что только факторизация поможет P.S. DimitarSerg был прав
Larry Ранг: 114.4 (ветеран), 21thx Активность: 0.04↘0.01 Статус: Участник	Создано: 24 декабря 2017 01:32 · Личное сообщение · #9 Интересно, осуществима ли на сегодняшний день факторизация RSA-512 в домашних условиях? Я недавно факторизовал RSA-384 (использовалась программой DekTec StreamXpert). У меня на это дело с неделю ушло. Правда временами делал перерыв на ночь.
Kindly Ранг: 275.9 (наставник), 340thx Активность: 0.22=0.22 Статус: Участник RBC	Создано: 24 декабря 2017 02:18 · Поправил: Kindly · Личное сообщение · #10 Larry пишет: Интересно, осуществима ли на сегодняшний день факторизация RSA-512 в домашних условиях? да в принципе и пару лет назад было вполне осуществимо. проц 8 поток с 4GHz и за 10 полных суток сфакторишь как нефиг. с оговоркой, что нужна сборка под многопоток и проц интел. я разложил у себя по моему за 245 часов, это при том, что по незнанке юзал до 70-80% 32-бит сборку вместо 64, которая на 30-35% быстрее. чтоб не соврать, оптимизированная 64 сборка под многопоток и интел, с 8 потоками 4.2Ghz должна сфакторить за 155 часов. ----- Array[Login..Logout] of Life
SReg Ранг: 315.1 (мудрец), 631thx Активность: 0.3↗0.33 Статус: Модератор CrackLab	Создано: 24 декабря 2017 02:39 · Личное сообщение · #11 Kindly какой у тебя проц?
BfoX Ранг: 397.0 (мудрец), 179thx Активность: 0.17↘0.1 Статус: Участник	Создано: 24 декабря 2017 07:33 · Личное сообщение · #12 Kindly и где взять эту сборку? ----- ...или ты работаешь хорошо, или ты работаешь много...
kunix Ранг: 71.2 (постоянный), 33thx Активность: 0.05↗0.12 Статус: Участник	Создано: 24 декабря 2017 07:54 · Личное сообщение · #13 Я думаю, надо брать GGNFS. http://gilchrist.ca/jeff/factoring/
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 24 декабря 2017 08:15 · Личное сообщение · #14 Посмотрим за какое время факторизуется у меня на i7-7820X. У меня в 32 потока работает. На 8 ядрах я по 4 потока запустил Добавлено спустя 1 час 3 минуты kunix пишет: Я думаю, надо брать GGNFS. Вот на ней-то я и факторизую) Добавлено спустя 2 часа 48 минут Вот --> моя сборка <-- которой я факторизую, если кому интересно pass: exelab.ru Для запуска 1. В файлах example.ini и example.n ввести свой модулус в десятеричном виде. 2. В файле factmsieve.py внести изменения здесь (это мои настройки) Code: # Set binary directory paths GGNFS_PATH = 'C:\Factor' MSIEVE_PATH = 'C:\Factor' # Set the number of CPU cores and threads NUM_CORES = 8 THREADS_PER_CORE = 4 USE_CUDA = True GPU_NUM = 0 MSIEVE_POLY_TIME_LIMIT = 0 MIN_NFS_BITS = 264 3. Запустить RUN.bat P.S. Сборка ggnfs (svn413) win64 core2 и msieve1.53 (svn1002) win64 cuda
r0lka Ранг: 11.7 (новичок), 2thx Активность: 0.02↗0.04 Статус: Участник	Создано: 24 декабря 2017 11:08 · Личное сообщение · #15 а возведение в степень при такой большой экспоненте вообще реально? C^E там же число будет огроменное??? сколько оно будет вычислятся-то вообще? потом модулем конечно приведется к нужно размерности. Но мне кажется что-то автор топика не так разреверсил...
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 24 декабря 2017 11:11 · Поправил: BlackCode · Личное сообщение · #16 r0lka --> Все хорошо, я проверял ;) <--
Kindly Ранг: 275.9 (наставник), 340thx Активность: 0.22=0.22 Статус: Участник RBC	Создано: 24 декабря 2017 12:46 · Личное сообщение · #17 SReg пишет: Kindly какой у тебя проц? i7 6700K @4.2 BfoX пишет: Kindly и где взять эту сборку? msieve-153-x64_IvyBridgeBuild https://www.upload.ee/files/7803187/Factorization.rar.html Собирал под себя с рекомендациями и изменениями Ultras ----- Array[Login..Logout] of Life \| Сообщение посчитали полезным: Ultras, kampaster
DimitarSerg Ранг: 253.5 (наставник), 684thx Активность: 0.26↘0.25 Статус: Участник radical	Создано: 24 декабря 2017 13:34 · Личное сообщение · #18 r0lka пишет: а возведение в степень при такой большой экспоненте вообще реально? C^E там же число будет огроменное??? сколько оно будет вычислятся-то вообще? потом модулем конечно приведется к нужно размерности. А мне кажется что кому-то матчасти почитать надо, а автор топика все верно разреверсил. Это не a^b , а потом mod c, это именно a^b mod c, возведение в степень по модулю. https://en.wikipedia.org/wiki/Modular_exponentiation https://en.wikipedia.org/wiki/Montgomery_modular_multiplication ----- ds \| Сообщение посчитали полезным: BlackCode, plutos
reversecode Ранг: 1053.6 (!!!!), 1078thx Активность: 1.06↘0.81 Статус: Участник	Создано: 24 декабря 2017 18:45 · Личное сообщение · #19 вроде экспонента должна быть праймом ? и если не правильно подобрана то вроде была какая то уязвимость, не ?
DimitarSerg Ранг: 253.5 (наставник), 684thx Активность: 0.26↘0.25 Статус: Участник radical	Создано: 24 декабря 2017 19:34 · Личное сообщение · #20 reversecode пишет: вроде экспонента должна быть праймом ? Нет, взаимно простая с фи (p-1)(q-1) reversecode пишет: и если не правильно подобрана то вроде была какая то уязвимость, не Надо еще умудриться неправильно подобрать ) В любом случае все публичные атаки собраны здесь: https://github.com/Ganapati/RsaCtfTool Code: Weak public* key factorization Wiener's attack Hastad's attack (Small public exponent attack) Small q (q < 100,000) Common factor between ciphertext and modulus attack Fermat's factorisation for close p and q Gimmicky Primes method Past CTF Primes method Self-Initializing Quadratic Sieve (SIQS) using Yafu Common factor attacks across multiple keys Small fractions method when p/q is close to a small fraction Boneh Durfee Method when the private exponent d is too small compared to the modulus (i.e d < n^0.292) Elliptic Curve Method ----- ds \| Сообщение посчитали полезным: sefkrd
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 24 декабря 2017 20:28 · Личное сообщение · #21 Кстати, хотел спросить, никто не встречал глюк с msieve, когда пытаешься запустить факторизацию модуля с битностью больше 512 msieve тупо падает с ошибкой?
kunix Ранг: 71.2 (постоянный), 33thx Активность: 0.05↗0.12 Статус: Участник	Создано: 01 января 2018 19:44 · Личное сообщение · #22 Чем все закончилось?
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 02 января 2018 00:26 · Поправил: BlackCode · Личное сообщение · #23 kunix пишет: Чем все закончилось? Продолжается факторизацией. Уже 9 дней комп молотит, больше 93000000 реляций 173%, но решения пока нет.
kunix Ранг: 71.2 (постоянный), 33thx Активность: 0.05↗0.12 Статус: Участник	Создано: 02 января 2018 08:58 · Личное сообщение · #24 Странно. А скиньте лог и конфиг.
BlackCode Ранг: 71.5 (постоянный), 95thx Активность: 0.1↗0.38 Статус: Участник	Создано: 02 января 2018 09:16 · Личное сообщение · #25 kunix пишет: Странно. А скиньте лог и конфиг. Ура!) Сегодня в 5 утра закончилось. Total raw relations: 93737726 Relations: 8119586 relations Pruned matrix : 5174280 x 5174506 Total sieving time: 220.97 hours. Total relation processing time: 0.38 hours. Matrix solve time: 5.18 hours. time per square root: 0.62 hours. total time: 227.16 hours.

Для печати