Решение задания Mystic Square NeoQuest2015

[MarcusLarrson]

Задание:
Утро началось так себе: у меня сломался телефон. Просто отказался работать, ни с того ни с сего. Повозившись с ним около часа, я заглянул в сервис и совсем приуныл, узнав, во сколько обойдется ремонт…
Я решил не терять надежды и показать телефон хорошему знакомому, разбирающемуся в электронике, однако на данный момент его не было в Питере, так что я решил пока что приобрести себе недорогой «запасной» телефон. Полчаса сидения на Avito – и я нашел приличный б/у телефон, на удивление недорого. Созвонился с хозяином и через полчаса был уже на месте.
Владельцем телефона был мужчина лет 30, с довольно-таки незапоминающейся внешностью, однако мой взгляд зацепился за рисунок на его футболке: на ней был изображен циркуль, раскрытый на 60°. «Масонская символика», – мысленно отметил я, но не придал этому значения. Телефон меня устроил, я расплатился с парнем и поехал домой. Уже в метро я вставил в него свою симку, стал копаться в настройках и вдруг увидел приложение, называющееся «Mystic Square». Попросту говоря, «пятнашки», да только какие-то явно усложненные, с кучей цифр и линий. Что ж, можно скоротать время в дороге за игрой.

Решение:
Первым шагом декомпилируем приложение game.apk через http://www.decompileandroid.com/ и найдем интересные участки кода:

String s = editText.getText().toString();
                if ((new File("/sdcard/key.txt")).exists())
                {
                    String s1 = Simple.Decrypt(s);
                    Toast.makeText(getBaseContext(), s1, 1).show();
                    return;
                }
                try
                {
                    Simple.get(s);
                    return;
                }
                catch (IOException ioexception)
                {
                    ioexception.printStackTrace();
                }

Simple.Decrypt(s):

 
    static BigInteger e = new BigInteger("938605837027", 10);
    static BigInteger n = new BigInteger("8286006298514071265735892332006920710569", 10);

public static String Decrypt(String s)
    {
        ArrayList arraylist = new ArrayList();
        Scanner scanner;
        try
        {
            scanner = new Scanner(new File("/sdcard/key.txt"));
        }
        catch (FileNotFoundException filenotfoundexception)
        {
            return "0";
        }
        for (; scanner.hasNextLine(); arraylist.add(scanner.nextLine())) { }
        BigInteger biginteger = new BigInteger((String)arraylist.get(0));
        if ((new BigInteger((String)arraylist.get(1))).modPow(e, n).equals(biginteger))
        {
            (new File("/sdcard/key.txt")).delete();
            return biginteger.modPow(new BigInteger(s), n).toString(16);
        } else
        {
            return "0";
        }

Видим RSA алгоритм и надо найти секретный ключ.
Simple.get(s):

public static void get(String s)
        throws IOException
    {
        QueryString querystring = (new QueryString()).add("message", s);
        URLConnection urlconnection;
        String s1;
        if (querystring == null)
        {
            Log.e("Info", "NULL");
            urlconnection = (new URL("http://79.175.2.83/0b32bd28a8632f9895f9d5d8a6c51dad/game.php")).openConnection();
        } else
        {
            urlconnection = (new URL((new StringBuilder()).append("http://79.175.2.83/0b32bd28a8632f9895f9d5d8a6c51dad/game.php?").append(querystring).toString())).openConnection();
        }
        urlconnection.getInputStream();
        s1 = readStreamToString(urlconnection.getInputStream(), "UTF-8");
        Log.e("Info", s1);
        if (!s1.equals("Error"))
        {
            FileWriter filewriter = new FileWriter(new File("/sdcard/key.txt"));
            filewriter.write(s1);
            filewriter.close();
        }
    }

Формируется запрос вида http://79.175.2.83/0b32bd28a8632f989...e.php?message=. Если запрос прошел успешно, создается файл и записывается ответ запроса.
Сыграем в пятнашки:
Распаковываем архив, переходим в папку res\drawable\ и собираем картинку:

И получившее число 10838670582455823456841 отправим по адресу http://79.175.2.83/0b32bd28a8632f989...82455823456841.
Ответ запроса:

5890287499022904927250918089905639153507 3148792732424313619076650032785631134 key=a0bf0f01485a59addf4f9374e7c2a7b5

Получили первый флаг a0bf0f01485a59addf4f9374e7c2a7b5 и создался файл /sdcard/key.txt.
В Simple.Decrypt(s), сначала читается файл key.txt и затем идет проверка:

(new BigInteger((String)arraylist.get(1))).modPow(e, n).equals(biginteger)

Выражение в виде значений примит следующий вид:

(3148792732424313619076650032785631134 ^ 938605837027) mod 8286006298514071265735892332006920710569 == 5890287499022904927250918089905639153507

plain text = 3148792732424313619076650032785631134 
cipher text = 5890287499022904927250918089905639153507
public key = 938605837027, 8286006298514071265735892332006920710569 
private key = ?, 8286006298514071265735892332006920710569

Второй флаг: DecToHex(plain text) = 025e6f77c39943f83d1d2f8770a1a79e

Нахождение private key:
Первым делом фактаризуем модуль, т.е. число 8286006298514071265735892332006920710569 для нахождения чисел p и q.
http://factordb.com/index.php?query=...32006920710569

p = 81227239281928373027
q = 102010192292200202947

Затем вычисляем функцию эйлера:

(81227239281928373027 - 1)(102010192292200202947 - 1) = 8286006298514071265552654900432792134596

И находим:

private key = (938605837027 ^ -1) mod 8286006298514071265552654900432792134596
private key = 4708825181381486710928551540092728302699

[Neomant]

Со вторым флагом можно поподробнее.
Почему md5? Какой plain text и почему?

[MarcusLarrson]

Со вторым флагом можно поподробнее.
Почему md5? Какой plain text и почему?

Ошибся при написании. Не md5, а конвертируем десятичное число в шестнадцатеричное.
Почитай https://ru.wikipedia.org/wiki/RSA и должно стать понятно откуда plain text.

[Neomant]

Вопрос остался. Что является флагом? Экспонента приватного ключа?
Или флаг - это '025e6f77c39943f83d1d2f8770a1a79e'?
Тогда зачем искать экспоненту и откуда во флаге ведущий ноль?

[MarcusLarrson]

Вопрос остался. Что является флагом? Экспонента приватного ключа?

Флагом является plain text(незашифрованный текст) в шестнадцатеричной системе.
DecToHex(3148792732424313619076650032785631134) = 25e6f77c39943f83d1d2f8770a1a79e
Так как флаг должен быть 32 символа, добавляем 0 в начало и получаем 025e6f77c39943f83d1d2f8770a1a79e.

Тогда зачем искать экспоненту

Public key(открытая экспонента) взяли из кода, private key(секретная экспонента) просто решил попробовать вычислить.