Это очень интересная задача для меня, поскольку она включает в себя целочисленное переполнение и расширенный алгоритм Евклида, которому я научился на уроках криптографии в университете. Это было так взволновано !!

Цели:

  1. Найдите длинное целое число, соответствующее уравнению.
  2. Преобразуйте правильное целое число в флаг с помощью заданной функции.

Охваченные темы:

  1. Найдите мультипликативную обратную величину длинного целого числа по модулю n .
  2. Использование целочисленного переполнения для поиска правильного решения для приведенных формул.

Описания:

Перейдите по ссылке ниже, чтобы увидеть исходный код заданного вопроса.

https://gist.github.com/ghoulgy/1749da21f6351f3f9df9cf3c4ccbd759

Из исходного кода видно, что функция arrayOfString и creator просто тролль, чтобы сбить нас с толку. Просто… Удалите их!
Остались важные функции: securing_fsecure, getHexString, hexToASCII и main.

getHexString ()

Получите символы в paramString и переставьте их в правильном порядке, который будет декодирован с помощью hexToASCII () во флаг.

hexToASCII ()

Преобразуйте упорядоченное шестнадцатеричное значение в читаемое значение ASCII, в котором создается флаг.

главный()

Там есть инструкция if для проверки результатов securing_fsecure (), истинно или ложно.

securing_fsecure ()

Он имеет шестнадцатеричное значение, которое передается в функцию, поэтому преобразуйте его в текст ascii и отобразите replaceac3th1s. Хм ... Это подсказка, что ответ на получение флага находится здесь. Внутри функции есть оператор if, который содержит простые математические формулы с длинным целым числом.

if (42L + -37L * Long.parseLong(paramString) == 17206538690L) {
          bool = true;
          getHexString(paramString);
          System.out.println("\nYay! I think I got it!? The flag is here somewhere...");
        }

Отсутствующее (paramString) - это значение, переданное в функцию.
Переставьте формулы:

-37L * Long.parsedLong(paramString) = 17206538648L

Невозможно найти точное длинное значение paramString, поскольку разделение ANS и -37L будет округлено до ближайшего десятичного значения.

Длинное целое число не будет хранить значение с плавающей запятой

Чтобы найти точное значение, может быть, его можно решить с помощью целочисленного переполнения?

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

Эта ссылка расскажет больше об этом типе вопросов.

В Java long - это 64-битный тип со знаком, который может хранить до 2⁶⁴ значений.

Нахождение обратного умножения 37 по модулю 2⁶⁴ по этой ссылке.
Результатов: 1495681951922396077L

Проверьте значение, проверив, что 1495681951922396077L является обратным 37 в моде 64.

37L * 1495681951922396077L == 1L

Умножьте инвертированное значение 37 на исходное значение для сравнения, чтобы получить правильное значение paramString.

Еще раз подтвердите, используя исходную формулу.

42L + -37L * -4487045856232229816L == 17206538648L

Бац !!! Джекпот !!!

В контексте Java подписанное 64-битное длинное целое число -4487045856232229816L является правильным решением.

Теперь мы получили правильное значение paramString для передачи в функцию.
Чтобы распечатать флаг, я изменяю тип getHexString () с void на String, который возвращает значение String. Затем напишите строку распечатки в securing_fsecure () и запустите ее .

Пометить Get. Ваше здоровье!

Личные мысли

Общее пошаговое руководство заключается в нахождении мультипликативной обратной величины 37L по модулю 2⁶⁴, а затем с использованием дефектов целочисленного переполнения для получения правильного значения формул.

Использованная литература:

Https://www.youtube.com/watch?v=shaQZg8bqUM
https://brilliant.org/wiki/extended-euclidean-algorithm/
https: // dsri. github.io/modinverse/
https://math.stackexchange.com/questions/2172758/impossible-math-number-needs-to-be-divisible-and-greater-than-an-end- результат / 2172777