eXeLab
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
обновлён 2 декабря!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

Русский / Russian English / Английский

Сейчас на форуме:
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS · SVN ·

 eXeL@B —› Крэки, обсуждения —› RSA или нет? И как решить?
Посл.ответ Сообщение


Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 23 декабря 2017 13:58 · Поправил: BlackCode New!
Цитата · Личное сообщение · #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

Заранее спасибо

Ранг: 390.7 (мудрец)
Статус: Участник
"Тибериумный реверсинг"

Создано: 23 декабря 2017 14:29 New!
Цитата · Личное сообщение · #2

BlackCode пишет:
M=C^E mod M

Эм! А в случае:
Code:
  1. M=C^D mod N

тогда что?


Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 23 декабря 2017 14:34 · Поправил: BlackCode New!
Цитата · Личное сообщение · #3

ELF_7719116 пишет:
тогда что?

Как что? Расшифровка с теми данными, что я здесь выложил.
Опечатался немного


Ранг: 229.1 (наставник)
Статус: Участник
radical

Создано: 23 декабря 2017 17:55 New!
Цитата · Личное сообщение · #4

BlackCode пишет:
как найти экспоненту которая используется для зашифровки данных

Без факторизации - никак )
Неважно, как вы буквы назовете, проблема остается та же.

| Сообщение посчитали полезным: BlackCode


Ранг: 68.6 (постоянный)
Статус: Участник

Создано: 23 декабря 2017 18:05 · Поправил: kunix New!
Цитата · Личное сообщение · #5

Публичная экспонента обычно маленькая.
Поэтому, для начала - перебрать экспоненты до, скажем, 100000. Шифровать данные и расшифровывать приватной экспонентой.
Да и 512 бит отлично факторизуется.

UPD: не, походу публичная тоже большая.

| Сообщение посчитали полезным: BlackCode



Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 23 декабря 2017 19:17 New!
Цитата · Личное сообщение · #6

Факторизацию уже запустил,модулус кстати 508 бит а не 512. Надеюсь проблем с факторизацией не должно быть

Добавлено спустя 2 минуты
kunix
Кстати в начале так и сделал, типа брута перебрал 3000000 простых чисел в прогрессии,результата не дало.

Ранг: 68.6 (постоянный)
Статус: Участник

Создано: 23 декабря 2017 19:25 · Поправил: kunix New!
Цитата · Личное сообщение · #7

Там еще любопытно, что экспонента больше модуля. Видно, к ней k*(p-1)(q-1) прибавили. Вопрос - зачем
Проверил, может, экспонента это x + k*(p-1)(q-1), где x - малая экспонента, но тоже не подошло.


Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 23 декабря 2017 19:30 · Поправил: BlackCode New!
Цитата · Личное сообщение · #8

kunix
Вскрытие покажет. (факторинг) В принципе время уйти должно меньше чем у 512.

Добавлено спустя 1 час 49 минут
kunix
По ходу это реально паблик экспонента
Ее сделали такой большой видимо для запутывания.
Я взял эту экспоненту и в РСАтулс сгенерил пару модулус и приват кей.
Зашифровал и расшифровал благополучно данные.
Так что только факторизация поможет

P.S. DimitarSerg был прав


Ранг: 113.1 (ветеран)
Статус: Участник

Создано: 24 декабря 2017 01:32 New!
Цитата · Личное сообщение · #9

Интересно, осуществима ли на сегодняшний день факторизация RSA-512 в домашних условиях? Я недавно факторизовал RSA-384 (использовалась программой DekTec StreamXpert). У меня на это дело с неделю ушло. Правда временами делал перерыв на ночь.


Ранг: 264.7 (наставник)
Статус: Участник
RBC

Создано: 24 декабря 2017 02:18 · Поправил: Kindly New!
Цитата · Личное сообщение · #10

Larry пишет:
Интересно, осуществима ли на сегодняшний день факторизация RSA-512 в домашних условиях?

да в принципе и пару лет назад было вполне осуществимо. проц 8 поток с 4GHz и за 10 полных суток сфакторишь как нефиг. с оговоркой, что нужна сборка под многопоток и проц интел.

я разложил у себя по моему за 245 часов, это при том, что по незнанке юзал до 70-80% 32-бит сборку вместо 64, которая на 30-35% быстрее.
чтоб не соврать, оптимизированная 64 сборка под многопоток и интел, с 8 потоками 4.2Ghz должна сфакторить за 155 часов.

Ранг: 300.6 (мудрец)
Статус: Модератор
CrackLab

Создано: 24 декабря 2017 02:39 New!
Цитата · Личное сообщение · #11

Kindly какой у тебя проц?

Ранг: 389.9 (мудрец)
Статус: Участник

Создано: 24 декабря 2017 07:33 New!
Цитата · Личное сообщение · #12

Kindly
и где взять эту сборку?

Ранг: 68.6 (постоянный)
Статус: Участник

Создано: 24 декабря 2017 07:54 New!
Цитата · Личное сообщение · #13

Я думаю, надо брать GGNFS.
http://gilchrist.ca/jeff/factoring/


Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 24 декабря 2017 08:15 New!
Цитата · Личное сообщение · #14

Посмотрим за какое время факторизуется у меня на i7-7820X.
У меня в 32 потока работает. На 8 ядрах я по 4 потока запустил

Добавлено спустя 1 час 3 минуты
kunix пишет:
Я думаю, надо брать GGNFS.

Вот на ней-то я и факторизую)

Добавлено спустя 2 часа 48 минут
Вот --> моя сборка <-- которой я факторизую, если кому интересно
pass: exelab.ru

Для запуска
1. В файлах example.ini и example.n ввести свой модулус в десятеричном виде.
2. В файле factmsieve.py внести изменения здесь (это мои настройки)

Code:
  1. # Set binary directory paths
  2. GGNFS_PATH = 'C:\Factor'
  3. MSIEVE_PATH = 'C:\Factor'
  4.  
  5. # Set the number of CPU cores and threads
  6. NUM_CORES = 8
  7. THREADS_PER_CORE = 4
  8.  
  9. USE_CUDA = True
  10. GPU_NUM = 0
  11. MSIEVE_POLY_TIME_LIMIT = 0
  12. MIN_NFS_BITS = 264


3. Запустить RUN.bat

P.S. Сборка ggnfs (svn413) win64 core2 и msieve1.53 (svn1002) win64 cuda

Ранг: 7.7 (гость)
Статус: Участник

Создано: 24 декабря 2017 11:08 New!
Цитата · Личное сообщение · #15

а возведение в степень при такой большой экспоненте вообще реально?

C^E там же число будет огроменное??? сколько оно будет вычислятся-то вообще?

потом модулем конечно приведется к нужно размерности.

Но мне кажется что-то автор топика не так разреверсил...


Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 24 декабря 2017 11:11 · Поправил: BlackCode New!
Цитата · Личное сообщение · #16


Ранг: 264.7 (наставник)
Статус: Участник
RBC

Создано: 24 декабря 2017 12:46 New!
Цитата · Личное сообщение · #17

SReg пишет:
Kindly какой у тебя проц?

i7 6700K @4.2

BfoX пишет:
Kindly
и где взять эту сборку?

msieve-153-x64_IvyBridgeBuild
https://www.upload.ee/files/7803187/Factorization.rar.html

Собирал под себя с рекомендациями и изменениями Ultras

| Сообщение посчитали полезным: Ultras, kampaster



Ранг: 229.1 (наставник)
Статус: Участник
radical

Создано: 24 декабря 2017 13:34 New!
Цитата · Личное сообщение · #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

| Сообщение посчитали полезным: BlackCode, plutos



Ранг: 1015.9 (!!!!)
Статус: Участник

Создано: 24 декабря 2017 18:45 New!
Цитата · Личное сообщение · #19

вроде экспонента должна быть праймом ? и если не правильно подобрана то вроде была какая то уязвимость, не ?


Ранг: 229.1 (наставник)
Статус: Участник
radical

Создано: 24 декабря 2017 19:34 New!
Цитата · Личное сообщение · #20

reversecode пишет:
вроде экспонента должна быть праймом ?

Нет, взаимно простая с фи (p-1)*(q-1)

reversecode пишет:
и если не правильно подобрана то вроде была какая то уязвимость, не

Надо еще умудриться неправильно подобрать )

В любом случае все публичные атаки собраны здесь:
https://github.com/Ganapati/RsaCtfTool
Code:
  1.  
  2.     Weak public key factorization
  3.     Wiener's attack
  4.     Hastad's attack (Small public exponent attack)
  5.     Small q (< 100,000)
  6.     Common factor between ciphertext and modulus attack
  7.     Fermat's factorisation for close p and q
  8.     Gimmicky Primes method
  9.     Past CTF Primes method
  10.     Self-Initializing Quadratic Sieve (SIQS) using Yafu
  11.     Common factor attacks across multiple keys
  12.     Small fractions method when p/q is close to a small fraction
  13.     Boneh Durfee Method when the private exponent d is too small compared to the modulus (i.e d < n^0.292)
  14.     Elliptic Curve Method

| Сообщение посчитали полезным: sefkrd



Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 24 декабря 2017 20:28 New!
Цитата · Личное сообщение · #21

Кстати, хотел спросить, никто не встречал глюк с msieve, когда пытаешься запустить
факторизацию модуля с битностью больше 512 msieve тупо падает с ошибкой?

Ранг: 68.6 (постоянный)
Статус: Участник

Создано: 1 января 2018 19:44 New!
Цитата · Личное сообщение · #22

Чем все закончилось?


Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 2 января 2018 00:26 · Поправил: BlackCode New!
Цитата · Личное сообщение · #23

kunix пишет:
Чем все закончилось?


Продолжается факторизацией.
Уже 9 дней комп молотит, больше 93000000 реляций 173%, но решения пока нет.

Ранг: 68.6 (постоянный)
Статус: Участник

Создано: 2 января 2018 08:58 New!
Цитата · Личное сообщение · #24

Странно. А скиньте лог и конфиг.


Ранг: 56.1 (постоянный)
Статус: Участник

Создано: 2 января 2018 09:16 New!
Цитата · Личное сообщение · #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.
 eXeL@B —› Крэки, обсуждения —› RSA или нет? И как решить?

Оригинальный DVD-ROM: eXeL@B DVD !

Вы находитесь на форуме сайта EXELAB.RU
Проект ReactOS