Автор Тема: Ломаем 3DOшные RSA ключи с помощью BOINC  (Прочитано 110232 раз)

0 Пользователей и 4 Гостей просматривают эту тему.

Оффлайн Leonis

  • Новенький
  • *
  • Сообщений: 15
    • Новая реальность
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #195 : 06 Февраль 2010, 08:33:28 »
//troosh
логи посмотрел, но спросонья ничего не понял. подчеркните пожалуйста нужную строчку :))

Оффлайн Versus

  • REALьный 3DOшник
  • Постоялец
  • *
  • Сообщений: 193
  • URSS creator
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #196 : 06 Февраль 2010, 10:10:11 »
А вообще интересен сам процесс. Не так как мы сейчас понимаем: вот комп, он считает, он помогает. А подробнее. Есть же какие-то формулы расчета, есть какие-то исходные данные. Вот, на выходе получили какие-то цифры. А как они получили и что они означают? Ну, кроме непосредственно первого ключа. Или все это секрет?
IBI VICTORIA UBI CONCORDIA

Оффлайн troosh

  • FREEDO-DEVELOPER
  • Частый гость
  • *
  • Сообщений: 73
  • Э3М
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #197 : 06 Февраль 2010, 18:57:27 »
Тут нет никаких секретов.
Для проверки подлинности файлов в 3DO используют подсчет контрольной суммы при помощи алгоритма MD5, к этим полученным 16 байтам добавляют постоянный префикс из 48 байт, что в итоге даёт 64 байт или 512 бит. Из этих 64 байт шифрованием по алгоритму RSA (приватным ключом) получают другие 64 байт которые дописываются к конец подписываемого файла.
При проверке файла расшифровывают последние 64 байт публичным ключом, убеждаются что 48-ми байтный префикс такой, как и должен быть, а оставшие 16 байт точно какая же контрольная сумма MD5 всего файла (без подписи конечно). Если совпадений нет, то такой файл использоваться не будет, - тут ошибка или злой умысел.

Как же работает шифрование/дешифрование по алгоритму RSA? На удивление он достаточно прост и использует в обоих случаях одну единственную математическую операцию, - возведение в степень. Только при этом применяется не привычная всем арифметика из школы, а арифметика по модулю некоторого числа, когда в результате любых вычислений могут получиться только целые числа от нуля до модуля минус 1. Иначе говоря, все результаты можно расположить в пределах некоторого круга (кольца). Так сумма (900+120) mod 1000 равна 20, а не 1020, а разность (3-5) mod 47 равна не -2, а 45. Даже когда компьютер складывает два байта и в результате тоже получает байт, то он фактически складывает по модулю 256.

У этой арифметики много разных свойств, одно из которых позволяет при выборе модуля из произведения двух простых чисел (модуль N=p*q) получать по произвольно заданному числу (e - публичный ключ) другое такое число (d - приватный ключ), такое что какое бы мы не взяли число (m - сообщение) возведение его в степень d, а затем в степень е будет вновь давать исходное сообщение m. Т.е. после первого возведения в степень будет получаться зашифрованное сообщение (обычно обозначают - c), а второе возведение будет давать исходное число m. По первым буквам фамилий математиков предложивших использовать это свойство ( ((m ** d) mod N) ** e mod N) == m ) в качестве шифра с двумя разными ключами и был назван алгоритм RSA.

Вся его стойкость основывается на трудности по числу N найти простые числа p,q, что позволит атакующему найти приватный ключ d. А всего-то нужно число N разложить на множители, это просто когда оно небольшое (15=3*5), а вот для чисел, состоящих из сотен цифр,  это проблема. Для её решения придумываются новые математические методы (можно я не буду тут об этом писать?), ну и быстродействие компьютеров растет, - в 90-х годах казалось, что 512 битного числа достаточно для устойчивости от взлома разложением N на тот момент, а сегодня на это потребуется один-два месяца работы одного компьютера. 

Вот таким вот разложением мы тут и занимаемся... Хотя проект, к которому мы примкнули, работает не над взломом RSA ключей, а применяет разложение для решения  других математических проблем, где также важно разложение больших чисел на множители.

Ну а по логам, если смотреть на файл msieve.LA+SQRT.log

то видно, что один из модулей (512-ти битное число или 154 десятичных знаков) был получен произведением двух чисел (77 и 78 значных):

92148915259187652735546324658820788400295573942653196481790449977806032404181
106877327934456063902508171996636457205791109741669452896794832726122641936429

Оффлайн Versus

  • REALьный 3DOшник
  • Постоялец
  • *
  • Сообщений: 193
  • URSS creator
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #198 : 06 Февраль 2010, 20:24:53 »
Ух... Спасибо за развернутый ответ! Есть непонятные моменты, но их я буду изучать самостоятельно. Еще раз спасибо!  :D
IBI VICTORIA UBI CONCORDIA

Оффлайн Leonis

  • Новенький
  • *
  • Сообщений: 15
    • Новая реальность
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #199 : 07 Февраль 2010, 09:04:59 »
Половину не понял, но очень рад тому, что есть люди, понимающие всю эту математику :)

Оффлайн Silentman

  • Новенький
  • *
  • Сообщений: 11
  • 3DOboy
    • 3DO Planet
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #200 : 07 Февраль 2010, 09:58:30 »
Кстати, а какое название будет носить задание для расшифровки второго ключа?
3DO - more than just a videogame

Оффлайн troosh

  • FREEDO-DEVELOPER
  • Частый гость
  • *
  • Сообщений: 73
  • Э3М
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #201 : 08 Февраль 2010, 06:38:33 »
Кстати, а какое название будет носить задание для расшифровки второго ключа?

Уже пошли задания по нашему второму ключу:
C154_2_....0000_10000_20100207160147

Оффлайн doom_sun

  • REALьный 3DOшник
  • Ветеран
  • *
  • Сообщений: 1344
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #202 : 08 Февраль 2010, 06:40:05 »
Цитировать
Уже пошли задания по нашему второму ключу:
C154_2_....0000_10000_20100207160147

Есть такая "буква в слове"  ;D
Трудные вещи становятся только труднее, если их откладывать.

(с) Джордж Р.Р. Мартин "Таинственный рыцарь"

Оффлайн Versus

  • REALьный 3DOшник
  • Постоялец
  • *
  • Сообщений: 193
  • URSS creator
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #203 : 08 Февраль 2010, 08:15:49 »
Ага, и у меня пошло!
IBI VICTORIA UBI CONCORDIA

Оффлайн Leonis

  • Новенький
  • *
  • Сообщений: 15
    • Новая реальность
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #204 : 08 Февраль 2010, 22:25:19 »
Завтра в командном зачете будет на 6, а что вероятнее, на 5 месте ! :))

Оффлайн Versus

  • REALьный 3DOшник
  • Постоялец
  • *
  • Сообщений: 193
  • URSS creator
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #205 : 15 Февраль 2010, 07:44:49 »
Есть в тройке лучших!  ;D
IBI VICTORIA UBI CONCORDIA

Оффлайн Андрей

  • Новенький
  • *
  • Сообщений: 17
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #206 : 20 Февраль 2010, 09:06:00 »
Закончились задания

Оффлайн Leonis

  • Новенький
  • *
  • Сообщений: 15
    • Новая реальность
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #207 : 20 Февраль 2010, 12:47:50 »
Закончились задания

Обнови проект, у меня 6 новых уже :)

Оффлайн Андрей

  • Новенький
  • *
  • Сообщений: 17
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #208 : 20 Февраль 2010, 13:46:10 »
Всё,пошли новые задания,интересно,сколько ещё будут вестись расчеты?
« Последнее редактирование: 20 Февраль 2010, 13:49:15 от Андрей »

Оффлайн Silentman

  • Новенький
  • *
  • Сообщений: 11
  • 3DOboy
    • 3DO Planet
Re: Ломаем 3DOшные RSA ключи с помощью BOINC
« Ответ #209 : 20 Февраль 2010, 14:48:35 »
Всё,пошли новые задания,интересно,сколько ещё будут вестись расчеты?
Задания, содержащие расчёты со вторым ключом, уже закончились и я так понял сейчас обрабатываются. А вообще все расчеты никогда не закончатся =)
3DO - more than just a videogame