{
    "version": "https:\/\/jsonfeed.org\/version\/1.1",
    "title": "Заметки Андрея Гейна: posts tagged crypto",
    "_rss_description": "Блог Андрея Гейна: заметки о жизни, программировании, преподавании и дизайне",
    "_rss_language": "en",
    "_itunes_email": "",
    "_itunes_categories_xml": "",
    "_itunes_image": "",
    "_itunes_explicit": "",
    "home_page_url": "https:\/\/andgein.ru\/blog\/tags\/crypto\/",
    "feed_url": "https:\/\/andgein.ru\/blog\/tags\/crypto\/json\/",
    "icon": "https:\/\/andgein.ru\/blog\/pictures\/userpic\/userpic@2x.jpg?1631100411",
    "authors": [
        {
            "name": "Андрей Гейн",
            "url": "https:\/\/andgein.ru\/blog\/",
            "avatar": "https:\/\/andgein.ru\/blog\/pictures\/userpic\/userpic@2x.jpg?1631100411"
        }
    ],
    "items": [
        {
            "id": "5",
            "url": "https:\/\/andgein.ru\/blog\/all\/5-crypto-backdoor-writeup\/",
            "title": "Заметка пятая. Разбор задания Crypto Backdoor с Google CTF 2017",
            "content_html": "<p>Это заметка о том, как мы с Костей Плотниковым решали задание на ассиметричную криптографию с Google CTF, который прошёл неделю назад. Она кишит кодом на питоне, несложными терминами из теории групп и математическими выкладками. Смело пропускайте, если боитесь чего-нибудь из этого.<\/p>\n<script type=\"text\/x-mathjax-config\">\nMathJax.Hub.Config({\n  tex2jax: {\n     inlineMath: [['$','$'], ['\\\\(','\\\\)']]\n  },\n  \"HTML-CSS\": {\n     linebreaks: { automatic: true, width: \"75% container\" }\n   }, \n  \"SVG\": {\n     linebreaks: { automatic: true, width: \"75% container\" }\n   } \n});\n<\/script>\n<script async src='https:\/\/cdnjs.cloudflare.com\/ajax\/libs\/mathjax\/2.7.0\/MathJax.js?config=TeX-AMS_CHTML'><\/script>\n<p>Формулировка как всегда бесконечно расплывчата:<\/p>\n<blockquote>\n<p>This public-key cryptosystem has a flaw. Can you exploit it? <a href=\"\/files\/blog\/5\/crypto_backdoor.py\">crypto_backdoor.py<\/a><\/p>\n<\/blockquote>\n<p>Костя попробовал меня ввести в курс дела, когда я присоединился к нему. Он рассказал, что в скрипте реализовано что-то вроде <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%AD%D0%BB%D0%BB%D0%B8%D0%BF%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F\">эллиптической криптографии<\/a>. Работает она так: сначала на плоскости рисуется специальная <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%AD%D0%BB%D0%BB%D0%B8%D0%BF%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BA%D1%80%D0%B8%D0%B2%D0%B0%D1%8F\">кривая<\/a>, а затем для каждой пары точек на ней определяется операция сложения. Сумма двух точек с кривой тоже лежит на кривой за исключением случая, когда получается особое значение — ноль. После этого естественным образом определяется умножение точки на натуральное число.<\/p>\n<p>В эллиптической криптографии Боб, желающий получать зашифрованные сообщения от Алисы, выбирает секретное число $N$ и точку на эллиптической кривой $g$. Последняя называется генератором и сообщается всем желающим, а вот секретное число становится закрытым ключом Боба. Открытым ключом в этом случае называется произведение генератора и закрытого ключа; $B = Ng$.<\/p>\n<p>Собственно, на мысли об эллиптических кривых Костю натолкнули наличие в скрипте точки-генератора и двух открытых ключей:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\"># Modulus\np = 606341371901192354470259703076328716992246317693812238045286463\n# g is the generator point.\ng = (160057538006753370699321703048317480466874572114764155861735009, 255466303302648575056527135374882065819706963269525464635673824)\n# Alice&#039;s public key A:\nA = (460868776123995205521652669050817772789692922946697572502806062, 263320455545743566732526866838203345604600592515673506653173727)\n# Bob&#039;s public key B:\nB = (270400597838364567126384881699673470955074338456296574231734133, 526337866156590745463188427547342121612334530789375115287956485)<\/code><\/pre><p>Модуль $p$ здесь тоже неслучаен — в эллиптической криптографии как раз рассматриваются кривые над полем $\\mathbb{Z}_p$. Позже, правда, мы пришли к выводу, что эллиптическая криптография тут совсем ни при чём... Но сначала мы внимательно изучили операцию сложения двух точек:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">def add(a, b, p):\n  if a == -1:\n    return b\n  if b == -1:\n    return a\n  x1, y1 = a\n  x2, y2 = b\n  x3 = ((x1*x2 - x1*y2 - x2*y1 + 2*y1*y2) * modinv(x1 + x2 - y1 - y2 - 1, p)) % p\n  y3 = ((y1*y2) * modinv(x1 + x2 - y1 - y2 - 1, p)) % p\n  return (x3, y3)<\/code><\/pre><p>Нейтральный элемент (он же <i>ноль<\/i>) обозначен как $-1$, поэтому первые четыре строки функции очевидны. Функция $modinv(x, p)$ находит обратный элемент к $x$ в кольце $\\mathbb{Z}_p$ с помощью расширенного алгоритма Евклида. Значит, сумма точек $(x_1, y_1)$ и $(x_2, y_2)$ это точка<br \/>\n$$\\left(\\frac{x_1x_2 – x_1y_2 – x_2y_1 + 2y_1y_2}{x_1+x_2-y_1-y_2-1}, \\frac{y_1y_2}{x_1+x_2-y_1-y_2-1}\\right)$$<\/p>\n<p>Дробь означает целочисленное деление в кольце $\\mathbb{Z}_p$.<\/p>\n<h2>Упрощаем сложение<\/h2>\n<p>Математик во мне захотел разобраться с этой операцией. Больше всего смущали одинаковые знаменатели и сложный числитель первой координаты. Стало проще, когда я переписал числитель как $(x_1-y_1)(x_2-y_2)+y_1y_2$, а знаменатель как $(x_1-y_1) + (x_2-y_2)$. Давайте перейдём из системы координат $(x, y)$ в систему $(t, y)$, где $t = x-y$. Обратный переход тоже очень простой: $x = t + y$. Если переписать операцию сложения в новой системе координат, то получится<\/p>\n<p>$$(t_1, y_1) + (t_2, y_2) = \\left(\\frac{t_1t_2+y_1y_2}{t_1+t_2-1} – \\frac{y_1y_2}{t_1+t_2-1}, \\frac{y_1y_2}{t_1+t_2-1}\\right) = \\left(\\frac{t_1t_2}{t_1+t_2-1}, \\frac{y_1y_2}{t_1+t_2-1}\\right)$$<\/p>\n<p>Получившаяся формула в некотором смысле даже симметрична. Это дало нам оптимизм на несколько следующих часов.<\/p>\n<h2>Мастер-секрет<\/h2>\n<p>Однако в скрипте само по себе сложение нигде не используются. Зато используется умножение точки на число:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">from secret_data import aliceSecret, bobSecret, flag\n\nassert A == mul(aliceSecret, g, p)\nassert B == mul(bobSecret, g, p)\n\naliceMS = mul(aliceSecret, B, p)\nbobMS = mul(bobSecret, A, p)\nassert aliceMS == bobMS\nmasterSecret = aliceMS[0]*aliceMS[1]<\/code><\/pre><p>Настало время разобраться, что вообще происходит в скрипте и что нужно найти.<\/p>\n<p>$aliceSecret$ — это натуральное число, закрытый ключ Алисы, он умножается на известный нам генератор, и в результате получается известный нам открытый ключ Алисы. Аналогичное проделывается с ключами Боба. После этого открытый ключ Боба умножается на закрытый ключ Алисы, получая точку $aliceMS = aliceSecret \\times bobSecret \\times g$. Симметричная операция вычисляет $bobMS = bobSecret \\times aliceSecret \\times g$. Очевидно, что эти две точки должны совпасть, что и проверяется последним assert’ом. Мастер-секретом объявляется произведение координат этой общей точки. Этот мастер-секрет и надо найти, так как в конце скрипта он ксорится с флагом:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">def encrypt(message, key):\n  return message ^ key\n\nlength = len(flag)\nencrypted_message = encrypt(I(flag), masterSecret)\nprint &quot;length = %d, encrypted_message = %d&quot; % (length, encrypted_message)\n# length = 31, encrypted_message = 137737300119926924583874978524079282469973134128061924568175107915062758827931077214500356470551826348226759580545095568667325<\/code><\/pre><h2>Умножение в новых координатах<\/h2>\n<p>Раз для подсчёта мастер-секрета используется умножение, то вернёмся к нашим формулам и выясним, как точка в новых координатах $(t, y)$ умножается на число $k$. Переберём несколько маленьких коэффициентов:<\/p>\n<p>$$2(t, y) = (t, y) + (t, y) = \\left(\\frac{t^2}{2t-1}, \\frac{y^2}{2t-1}\\right)$$<\/p>\n<p>$$3(t, y) = 2(t, y) + (t, y) = \\left(\\frac{t^2}{2t-1}, \\frac{y^2}{2t-1}\\right) + (t, y) =<br \/>\n\\left(\\frac{\\frac{t^3}{2t-1}}{\\frac{t^2}{2t-1} + t – 1}, \\frac{{\\frac{y^3}{2t-1}}}{\\frac{t^2}{2t-1} + t – 1}\\right) =<br \/>\n\\left(\\frac{t^3}{3t^2-3t+1}, \\frac{y^3}{3t^2-3t+1}\\right)$$<\/p>\n<p>$$4(t, y) = 2(t, y) + 2(t, y) = \\left(\\frac{t^2}{2t-1}, \\frac{y^2}{2t-1}\\right) + \\left(\\frac{t^2}{2t-1}, \\frac{y^2}{2t-1}\\right)  =<br \/>\n\\left(\\frac{\\frac{t^4}{(2t-1)^2}}{\\frac{2t^2}{2t-1} – 1}, \\frac{\\frac{y^4}{(2t-1)^2}}{\\frac{2t^2}{2t-1} – 1}\\right) =<br \/>\n\\left(\\frac{\\frac{t^4}{2t-1}}{2t^2-2t+1}, \\frac{\\frac{y^4}{2t-1}}{2t^2-2t+1}\\right) =<br \/>\n\\left(\\frac{t^4}{4t^3-6t^2+4t-1}, \\frac{y^4}{4t^3-6t^2+4t-1}\\right) $$<\/p>\n<p>Умножать дальше становилось всё сложнее, поэтому пора найти закономерность. В числителях всё время получается $t^k$ и $y^k$, а в знаменателях видны биномиальные коэффициенты. Смотрите, $4t^3-6t^2+4t-1$ похоже на $t^4 + (4t^3-6t^2+4t-1)$, что в свою очередь равно $(t + 1)^4$. Так у нас появилась гипотеза, что знаменатель равен $(t+1)^k – t^k$.<\/p>\n<p>Итоговую формулу<\/p>\n<p>$$k \\times (t, y) = \\left(\\frac{t^k}{(t+1)^k – t^k}, \\frac{y^k}{(t+1)^k – t^k}\\right)$$<\/p>\n<p>теперь можно доказать по индукции по $k$. Делать я этого, конечно же, не буду.<\/p>\n<h2>Решение<\/h2>\n<p>Задача будет решена, если мы узнаем закрытый ключ Алисы или Боба. В случае с Бобом нам достаточно найти такое $k \\in \\mathbb{Z}_p$, что $kg = B$. В наших новых координатах и формулах это выглядит так:<\/p>\n<p>$$\\left(\\frac{g_t^k}{(g_t+1)^k – g_t^k}, \\frac{g_y^k}{(g_t+1)^k – g_t^k}\\right) = (B_t, B_y)$$<\/p>\n<p>где $(g_t, g_y)$ — координаты генератора $g$ в системе $(t, y)$, а $(B_t, B_y)$ — аналогичные координаты точки $B$. Взяв из этого равенства первую координату, получаем:<\/p>\n<p>$$ \\frac{g_t^k}{(g_t+1)^k – g_t^k} = B_t$$<\/p>\n<p>$$g_t^k = B_t ((g_t+1)^k – g_t^k)$$<\/p>\n<p>$$g_t^k (1 + B_t) = B_t (g_t+1)^k$$<\/p>\n<p>$$\\left(\\frac{g_t}{g_t+1}\\right)^k = \\frac{B_t}{1 + B_t}$$<\/p>\n<p>Чтобы найти искомое $k$, достаточно вычислить логарифм в кольце $\\mathbb{Z}_p$, то есть решить задачу <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B5_%D0%BB%D0%BE%D0%B3%D0%B0%D1%80%D0%B8%D1%84%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5\">дискретного локарифмирования<\/a>. Здесь мы с Костей приуныли, потому что поняли, что зашли в тупик. Дискретное логарифмирование — задача, которую нельзя решить за нормальное время.<\/p>\n<p>Только через час Костя догадался проверить данный нам модуль $p$ на простоту. Совершенно неожиданно он оказался составным:<\/p>\n<p>$$p = 961236149 \\times 951236179 \\times 941236273 \\times 911236121 \\times 931235651 \\times 921236161 \\times 901236131$$<\/p>\n<p>Наверняка все знают, как посчитать дискретный логарифм по непростому основанию. А мы не знаем. Так что мы взяли бумажку и стали придумывать алгоритм.<\/p>\n<blockquote>\n<p><i>Когда-то Асанов рассказывал байку, что студенты УПИ обычно знают способ решить задачу, а студенты матмеха не знают. Зато студенты матмеха могут придумать решение. Кажется, теперь я понял эту байку.<\/i><\/p>\n<\/blockquote>\n<h2>Дискретный логарифм по составному основанию<\/h2>\n<p>Пусть мы нашли дискретный логарифм от $b$ по основанию $a$ в кольцах $\\mathbb{Z}_p$ и $\\mathbb{Z}_q$. То есть мы нашли такие $n$ и $m$, что<\/p>\n<p>$$a^n \\equiv b \\pmod{p}$$<br \/>\n$$a^m \\equiv b \\pmod{q}$$<\/p>\n<p>Теперь мы хотим решить задачу в кольце $\\mathbb{Z}_{pq}$, то есть найти такое $k$, что $a^k \\equiv b \\pmod{pq}$. Порядком числа $a$ в кольце называется такое минимальное натуральное $z$, что $a^z = 1$. Пусть число $a$ имеет порядки $u$ и $v$ в кольцах $\\mathbb{Z}_p$ и $\\mathbb{Z}_q$ соответственно. Тогда $b \\equiv a^n \\equiv a^{n + u} \\equiv a^{n+2u} \\equiv a^{n+3u} \\equiv \\dots \\pmod{p}$ и $b \\equiv a^m \\equiv a^{m + v} \\equiv a^{m+2v} \\equiv a^{m+3v} \\equiv \\dots \\pmod{q}$. Если мы найдём число, которое можно выразить и как $n + ?u$, и как $m + ?v$, то оно станет ответом задачи дискретного логарифмирования по модулю $pq$.<\/p>\n<p>Ну а найти такое число — дело техники и расширенного алгоритма Евклида. Если $n + ?u = m + ?v$, то $?u – ?v = m – n$. Если $m-n$ не делится на $НОД(u, v)$, то решения нет, иначе расширенный алгоритм Евклида решит это <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B8%D0%BE%D1%84%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D0%BE_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5#.D0.9B.D0.B8.D0.BD.D0.B5.D0.B9.D0.BD.D1.8B.D0.B5_.D0.B4.D0.B8.D0.BE.D1.84.D0.B0.D0.BD.D1.82.D0.BE.D0.B2.D1.8B_.D1.83.D1.80.D0.B0.D0.B2.D0.BD.D0.B5.D0.BD.D0.B8.D1.8F\">линейное диофантово уравнение<\/a>, и всё станет хорошо.<\/p>\n<p>Так как данный в задании модуль $p$ мы разложили на простые множители $p_1 \\times p_2 \\times \\dots \\times p_7$, которые к тому же получились не очень большими, то мы можем решить задачу дискретного логарифмирования в каждом из $\\mathbb{Z}_{p_i}$. Соединить семь чисел в один большой ответ поможет описанный только что алгоритм.<\/p>\n<h2>Как решить дискретный логарифм для  $p_i$<\/h2>\n<p>Простые делители модуля $p$ были не очень большими, но и не настолько маленькими, чтобы дискретный логарифм можно было найти простым перебором. К счастью, есть алгоритм <i>Baby Steps Giant Steps<\/i>, который позволяет сделать это намного быстрее — за $O(\\sqrt{n})$. Его мы и реализовали. Да, мы думали о том, что Baby Steps Giant Steps уже реализован в куче библиотек, но лично меня это только раззадоривает — так интересно ведь всё сделать самому.<\/p>\n<h2>Как найти порядок элемента в кольце<\/h2>\n<p>На часах было уже около часа ночи, а мне предстояло запрограммировать на питоне поиск порядка элемента в кольце $\\mathbb{Z}_p$. Теорема Эйлера шептала, что $x^{\\phi(p)} \\equiv 1 \\pmod{p}$, но $\\phi(p)$ могло оказаться не минимальным числом с таким свойством. Значит, искомый порядок — это делитель $\\phi(p)$. Но делителей слишком много, чтобы перебирать их все. Так что пришла пора узнать более быстрый способ находить порядок элемента. На помощь пришла <a href=\"http:\/\/cacr.uwaterloo.ca\/hac\/about\/chap4.pdf\">пдфка из интернета<\/a>, в которой есть чудесный алгоритм 4.79, я реализовал его и научился быстро находить порядок элемента в кольце, зная разложение на простые множители у $\\phi(p)$.<\/p>\n<h2>Заключение<\/h2>\n<p>Применив всю магию сверху, мы нашли закрытый ключ Боба $bobSecret$. Умножив его на открытый ключ Алисы, мы нашли мастер-секрет, который и выдал нам флаг:<\/p>\n<pre class=\"e2-text-code\"><code class=\"\">Master secret found: (254828745614253797280016043417264027645246572307317271091197847, 540509273347153402828726537667691800163306365090607497812000946)\nFlag: CTF{Anyone-can-make-bad-crypto}<\/code><\/pre><p>Если вкратце повторить всё наше решение, то оно перестаёт казаться страшным и длинным:<\/p>\n<ol start=\"1\">\n<li>переходим в систему координат $(t, y)$,<\/li>\n<li>вычисляем $a = \\frac{g_t}{g_t+1}$ и $b = \\frac{B_t}{1 + B_t}$,<\/li>\n<li>решаем задачу дискретного логарифма $a^{?} = b$ в кольце $\\mathbb{Z}_p$, зная разложение $p$ на простые множители,<\/li>\n<li>умножаем полученный ответ на открытый ключ Алисы $A$, это и есть мастер-секрет,<\/li>\n<li>переходим обратно в координаты $(x, y)$, перемножаем координаты мастер-секрета, расшифровываем флаг.<\/li>\n<\/ol>\n",
            "date_published": "2017-06-24T13:10:53+01:00",
            "date_modified": "2018-06-29T15:55:44+01:00",
            "tags": [
                "crypto",
                "CTF",
                "python",
                "writeup",
                "математика"
            ],
            "_date_published_rfc2822": "Sat, 24 Jun 2017 13:10:53 +0100",
            "_rss_guid_is_permalink": "false",
            "_rss_guid": "5",
            "_e2_data": {
                "is_favourite": false,
                "links_required": [
                    "highlight\/highlight.js",
                    "highlight\/highlight.css"
                ],
                "og_images": []
            }
        }
    ],
    "_e2_version": 4134,
    "_e2_ua_string": "Aegea 11.3 (v4134)"
}