Таки 6 огоньков наставили. Какие же вы аморальные пидорасы

Нашёл тут интересный пост про RSA. Сам нихуя не понял, но выглядит интересно. Автор - @ruheight

Первого марта Клаус Шнорр (ему мы обязаны цифровыми подписями) наделал шороху, загрузив препринт "Быстрая факторизация чисел алгоритмами SVP". В первой версии статьи есть приписка "это уничтожае криптосистему RSA". Именно "уничтожае", и я полагаю, что фраза "this destroyes RSA" станет мемом. Мне всегда нравился фильм "Sneakers", но так как RSA (пока) ничего не угрожает, то поговорим о факторизации и линейной алгебре.

Уже триста лет назад Ферма обратил внимание на то, что если представить составное число в виде разности квадратов, то его можно разложить на множители. n = a^2 - b^2 = (a + b) * (a - b). Например, 8051 = 8100 - 49 = 90^2 - 7^2 = (90 + 7) * (90 - 7) = 97 * 83. Поэтому числа p и q в модуле RSA не должны быть близко друг к другу. Для произведения двух простых 1024-битных чисел, разность которых 2^514, алгоритм Ферма находит множители за три шага. И это далеко не единственный способ закосячить RSA.

Затем, всего-то через пару сотен лет, Крайчик предложил новое условие u^2 ≡ v^2 (mod n), и u ≢ ±v (mod n). Дальше примеры из отличной статьи Померанца "A tale of thow sieves" http://www.ams.org/notices/199612/pomerance.pdf Для числа 2041 начинаем с √n и считаем q(x) = x^2 - n, если x = 46, 47, 48, ..., то q(x) = 75, 168, 263, ... Пока никакими квадратами и не пахнет.

Но если перемножить 46 * 47 * 49 * 51 и 75 * 168 * 360 * 560, то их квадраты (по модулю 2041) равны. 311^2 (mod 2041) = 1416^2 (mod 2041) = 794, и 311 != 1416, условие Крайчика соблюдено. Находим множитель, GCD(1416 - 311, 2041) = 13, и 2041 = 13 * 157. Осталось понять что на что умножать.

У квадрата любого числа показатели степеней простых множителей четные. (a * b * c ...)^2 = a^2 * b ^2 * c^2 ... 10 = 2^1 * 5^1. 10^2 = 2^1 * 2^1 * 5^1 * 5^1 = 2^2 * 5^2. Это сложный способ сказать, что десять в квадрате, то же, что и дважды два, дважды умноженное на пять. Слово "дважды" появляется перед каждым умножением.

Некоторые из чисел (x^2 - n) состоят только из небольших множителей. 75 = 3 * 5^2, 360 = 2^3 * 3^2 * 5, если число не содержит множителей больших, чем B, то такие числа называют B-гладкими. В числах 75, 168, 360 и 560 нет множителей больше 7, они гладкие. Погладьте их.

Можно записать степени в виде вектора 75 = 2^0 * 3^1 * 5^2 * 7^0. v(75) = (0, 1, 2, 0), v(168) = (3, 1, 0, 1). Так как нас интересует только четность, то степени можно записать по модулю 2: v(75) = (0, 1, 0, 0) mod 2; v(168) = (1, 1, 0, 1) mod 2, так как числа у нас B-гладкие, и операции по модулю два, то получившаяся хрень - векторное пространство размерности B над полем F_2.

(Я отчетливо слвшу, как некоторые из вас горестно вздыхают на словах "векторное пространство", но в том, чтобы записать единички и нолики через запятую, ничего сложного нет)

Для того, чтобы найти нужные числа, нужно подобрать вектора, которые в сумме (по модулю два) дают (0, 0, 0, 0). Если записать вектора (0,1,0,0),(1,1,0,1),(1,0,1,0),(0,0,1,1) один под другим и сложить столбцы, то получится нулевой вектор. В QS и GNFS, есть еще много тонкостей и хитростей, но речь не о них.

В этом месте Шнорр пришел к логичному выводу, что если что-то выглядит как вектор, то можно попробовать применить алгоритмы относящиееся к векторам. А именно CVP и SVP (поиск ближайшего и кратчайшего вектора в решетке), чтобы ускорить процесс поиска. А точнее приблизительных решений, потому что обе сучки в NP-hard (факторизация NP-intermediate). Потому их, кстати, и используют в пост-квантовой криптографии.

Умные дядьки, которые занимаются решетками порылись в статье Шнорра, и из неё отнюдь не очевидно, что таким способом вобще можно что-то найти. Так же там есть ошибка в оценке сложности, то есть даже, если таким способом можно что-то найти, то совсем не факт, что быстрее, чем уже существующие методы. Речь идёт о решетках ебанистических размерностей. https://github.com/lducas/SchnorrGate
Так что ваши p и q спрятанные в "зеленных замочках" сайтов, роботах-пылесосах и мобильниках могут спать спокойно.

чому клоунов наставили.

Немного контента о том, что происходит до того как выполнится ваш код в main. Рассматриваются как бинарники и запуск с линукса, так и embedded системы (аля esp32)

- How Programs Get Run
- How Programs Get Run: ELF Binaries
- Linux x86 Program Start Up or – How the heck do we get to main()?


- A General Overview of What Happens Before main() (тут целая серия статей)
- From Zero to main(): Bare metal C

https://medium.com/@tomysshadow/fixing-the-loading-in-myst-iv-revelation-86e2814afbf8 (+ part 2)

История оптимизации старой игры. Автор переписал часть кода, связанную с загрузкой фото, рассказывает про разные форматы, почему они тут играют ключевую роль и трюки для быстрой обработки изображений. Со всеми нюансами, бенчами, особенностями кода и так далее. На что только не шли разрабы старых игр, чтобы всё работало...

Уровень, к которому я стремлюсь

https://github.com/NationalSecurityAgency/ghidra

База для reverse engineering'а. Порох входа весьма низок - закиньте какой-то бинарник и поизучайте его наполнение.

Рекомендую взять бираник из первой зачади по RE на https://hack.ainfosec.com/

- Editing an Executable Binary File with Ghidra
- CheatSheet (Command+Shift+G - изменить инструкцию)

> Opens an interesting link
> Sees the profile pic
> Closes the interesting link

А я же говорил

https://theengineeringmanager.substack.com/p/parkinsons-law-its-real-so-use-it

Про закон Паркинсона и как его применять в контексте работы.

Спойлер: ставьте чёткие дедлайны. По статистике без них многие вещи делаются дольше ибо оттягиваются до последнего возможного момента

В ядре Linux 6.10 появился новый сисколл mseal, усиливающий защиту памяти от эксплоитов. Как это работает и как использовать - в статье

https://blog.trailofbits.com/2024/10/25/a-deep-dive-into-linuxs-new-mseal-syscall/

Зависла SSH сессия? Для выхода можно воспользоваться одной из escape sequences: <Enter>~.

Полный список можно найти в man ssh (раздел ESCAPE CHARACTERS) или <Enter>~? в ssh сессии (скриншот прикрепил)

by @shdwchn10

это параша, я тебе отвечаю. Не надо так писать.