Слишком близкие простые

Прогресс комнаты 0 / 4

Задание 1Введение

Цель: Факторизацию методом Ферма и почему простые p и q должны быть далеко друг от друга.

Генератор ключей выбрал q как следующее простое после p (почти). n — 1024 бита, факторизовать «в лоб» нельзя. Или можно?

Задание 2Теория и инструменты

Если p и q близки, то n = a² − b², где a = (p+q)/2 близко к √n, а b = (q−p)/2 мало.

Начинаем с a = ⌈√n⌉ и увеличиваем a, пока a² − n не станет полным квадратом b². Тогда p = a − b, q = a + b. При близких простых это занимает считанные итерации даже для 1024-битного n.

Инструменты

Python: math.isqrt, pow(e, -1, phi)

Больше теории — в разделе «Обучение: Криптография».

Задание 3Практика: найдите флаг

Данные задания636 символов

n = 100180652263792406686512987127975285105857197531200214081725942461007870943641098736466887042504820614965622191615603420468515405613913686219129296863499733988530289175154225668012597381851701405679704076185303503756274585561692402290310611726226065327236521994937559014315457715763508862223827500905927848691
e = 65537
c = 12454932595433837646028490577781742729069757413971551451589478251487855131059017433547597167622738548958223124062514293571729931146826083233336057932772185337809527916368516928461190477556303255045595704095645662925677522871163195308816434830204609534747791681317780087828887246472640411468235600331820237805

Вопрос: какой флаг спрятан в данных? Войдите, чтобы ответить

Пошаговый план — открывайте по одному шагу

1
Вычислите a = isqrt(n) + 1.
2
Проверяйте, является ли a² − n полным квадратом (isqrt(x)² == x). Если нет — увеличьте a.
3
Найдите p = a − b, q = a + b, проверьте p·q == n.
4
Вычислите φ = (p−1)(q−1), d = e⁻¹ mod φ, m = c^d mod n.
5
Переведите m в байты.

Подсказки — каждая до решения стоит −50 очков

Войдите, чтобы открыть подсказку 1

Войдите, чтобы открыть подсказку 2

Задание 4Как защититься

Генерируйте ключи стандартными библиотеками (OpenSSL, cryptography): они выбирают p и q независимо и случайно.

Разборы участников

Разборы открываются после того, как вы решите комнату, — чтобы не спойлерить ответ.