17 декабря 2016 в 16:26

Задание с экзамена по защите информации

Сразу озвучу задачку, чтобы не было предвкушения, будто тут будет показан какой-то крутой новый метод шифрования.

Нужно доказать, что

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

За день до нашего экзамена ребята с параллельной группы скинули одну задачку(описана в начале статьи), решить которую не смогли. Сидела я на работе, думала, как ее решить, около часа. Какие идеи и первые мысли по решению были у меня в голове на тот момент, я не скажу, уже несколько лет прошло. Кстати мне на экзамене попалась задачка такого же типа. Ниже покажу доказательство двух типовых задачек. Если вы знаете, как доказать по-другому, отпишитесь в комментариях.

Итак, приступим. Доказательство построено с использованием теоремы Эйлера.
Еще раз повторю задание. Нужно доказать, что делится на 12 для всех простых x > 3.

x и 12 — взаимно простые, тогда по т.Эйлера, делится на 12, т.е. остаток от деления равен 0 (в теореме единица перенесена в правую часть равенства, сделаем так же):



Для числа 12 существует четыре меньших него и взаимно простых с ним чисел (1, 5, 7, 11), поэтому функция Эйлера принимает значение четыре:




Перенесем единицу из правой части равенства влево и воспользуемся формулой из школы, разложим на множители разность квадратов:



Сокращаем на :



Что и требовалось доказать.

А теперь вот вам еще одна типовая задачка, которая попалась мне на экзамене. Когда решение было показано преподу, он почему-то был удивлен, поскольку, как он потом сказал, было бы достаточно просто посчитать в лоб, возвести в степень и показать, что одно число делится на другое. А решение, которое я ему показала, он видит впервые. Вот всегда думаешь, что для доказательства нужно применить теоремы, следствия, аксиомы, а оказывается «можно было просто в лоб посчитать».

Доказать, что число делится на 105.

Если число делится нацело, то остаток 0. Числа 73 и 105 – взаимно простые => по т. Эйлера:



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





Переносим единицу влево и раскладываем на множители:



Сокращаем на :



Разложим на множители и сократим еще раз:




Остаток от деления на 105 — ноль, деление нацело. Ч.т.д.

Возможно, кому-то пригодится это решение, но, надеюсь, что у вас на ЗИ будет что-то поинтереснее.
@AnROm
карма
15,0
рейтинг 5,5
Программист
Самое читаемое Разное

Комментарии (31)

  • +3
    Поправьте меня, если я что-то пропустил, но не нужно ли перед тем как сокращать x^2 + 1 показать, что он взаимно прост с 12?
    • +3
      Нужно, спасибо, что поправили
      • +31
        Незачто. Кажется что для этой задачи есть гораздо более простое решение без теоремы Эйлера, а пользуясь только школьными знаниями: рассмотрим 3 числа p-1, p и p+1. Одно из них точно делится на 3, и по-условию это не p, кроме того p-1 и p+1 — оба четные. Собираем все вместе (p-1)(p+1) делится на 3 и на 2^2, т. е. делится на 12.
        • +2
          Совершенно верно, эта задачка из старых олимпиадных для младших классов.
        • +4
          73^12 — 1 делится на 105?

          также решается без вычислений
          105 = 3 * 5 * 7,
          1) деление на 3 доказывается вашим способом, поскольку 73^6 — не делится на 2 и 3.
          2) деление на 5 простое возведение в степень разряда единиц 3^2 = 9, 9^2 = 81, 1 в любой степени 1, вычитаем 1 = искомое число кратно 10, то есть делится на 5
          3) деление на 7 — 73^3+1 делится на 7 поскольку куб суммы (70+3)^3 = все члены разложения делятся на 7 кроме 3^3=27, но ведь +1)) = 28 тоже чики.
          • 0
            можно ещё степень пошагово понижать:
            73^12 = 32^12 = 1024^6 = 26^6 = 2^6 * 13^6 = 2^6 * 64^3 = 2^24 = 1024^2 * 2^4 = 26^2 * 2^4 = 2^2 * 13^2 * 2^4 = 2^2 * 64 * 2^4 = 2^12 = -26 * 2^2 = -104 = 1 (все действия по (mod 105))
            итого
            1 = 1 mod 105
      • +5
        Вы просто написали, что x^2 + 1 взаимно просто с 12, но не объяснили почему — это как-то странно. Мне вот например, не очевидно почему это так.
        • 0

          Очевидно, что не взаимно просто, т.к. простое x>3 нечётное, x^2+1 — чётное.

    • 0
      А он и не взаимно прост: как минимум делится на 2 (тем не менее, можно доказать, что не делится на 3 или 4)
      • +1
        И правда, как я сразу не заметил, взаимная простота здесь не обязательна, тем не менее показать, что x^2+1 не кратно 12 все равно нужно, иначе не понятно на каком основании был отброшен множитель x^2+1. Так что для полноты картины покажем, что x^2+1 не делится на 4.
        Очевидно, что если x — простое, то x^2 — нечетное, значит x^2-1 и x^2+1 — соседние четные числа, значит одно из них делится на 4, а другое нет. Нужно показать, что на 4 делится именно x^2-1. x^2-1 = (x-1)(x+1), как (x-1) так и (x+1) — оба четные, значит x^2-1 — делится на 4, а x^2+1 ничего не остается кроме как не делиться на 4, а значит и на 12. Все верно?
        • +1
          Нет не верно, взаимная простота все равно нужна.
          • 0
            Для x = 5: x² + 1 = 26. А так как 12 и 26 имеют общий делитель (2), они не взаимно простые ⇒ взаимная простота не нужна.
            • 0
              Вы показали ровно то, что она не нужна для x == 5, но есть еще бесконечное количество других x, для которых это тоже нужно показать. Справедливости ради отмечу конечно, что рассматривать бесконечное число всех простых чисел не нужно, потому что мы все равно работаем по модулю 12, но тем не менее нужно рассмотреть больше чем один случай x == 5, чтобы доказать это утверждение.

              Взаимная простота гарантирует, что существует обратный по умножению, и значит на него можно домножить левую и правую части равенства и тем самым избавиться от множителя. Так что в общем случае, чтобы сократить взаимная простота необходима. В данном случае может быть можно обойтись и без нее, но это еще тоже нужно доказать.
  • +6
    Я скажу больше. x*x — 1 делится на 24 для всех простых x > 3
    • +1
      У меня такое ощущение, как будто тут какой-то флешмоб: все зашли и стали обсуждать статью с примером из задавальника по дискрану первого курса. Мало того, как вы заметили, облегченным примером. Дальше будет статья про то почему простых чисел бесконечно,
  • +8

    Мне кажется, доказать можно проще:


    1. Раскладываем на (x-1)(x+1)
    2. Т.к. x — простое и нечетное, то (x - 1) и (x + 1) — четные => (x-1)(x + 1) ⋮ 4
    3. Среди n подряд идущих натуральных чисел существует единственное ⋮ n (одно из свойств делимости натуральных чисел). Возьмем 3 подряд идущих: (x - 1), x, (x + 1). x ⋮ 3 => либо (x - 1) ⋮ 3, либо (x + 1) ⋮ 3 => (x - 1)(x + 1) ⋮ 3
    4. (x - 1)( x + 1) ⋮ 3; (x - 1)( x + 1) ⋮ 4 => (x - 1)( x + 1) ⋮ 12, ч.т.д.
    • +4
      Из двух соседних четных одно обязательно делится на 4. То есть (x-1)(x + 1) ⋮ 8
      • 0
        Вот и я удивился, когда упоминание теоремы Эйлера увидел.
        (Простите, это ответ Sencho_Pens.)
  • 0
    Отлично
  • +12
    А у меня одного возникает вопрос — какое отношение это имеет к защите информации?
    • +4
      У нас много было задачек по теории чисел, полиномам и др. Многие аспекты из теории чисел используются в алгоритмах шифрования.
    • 0
      А у меня другой вопрос: неужели только я не понимаю, как это решать?
    • +5
      Конкретно эти задачи — никакого отношения к защите информации не имеют. Однако, в системах шифрования очень часто используется операция «остаток от деления» (можно сказать «функция от двух аргументов»), и поэтому программист, работающий с шифрованием данных, должен знать свойства этой операции. А подобные задачи хорошо учат и позволяют проверить уровень теоретической подготовки.

      Ну, это примерно как в МИСиС преподавали курс химии, подавляющая часть которого к металлургии никак не относится.
      • 0

        А на экзамене по предмету, связанному с металлургией, вам давали задачки из этого курса химии? Просто тут речь о том, что на экзамене по безопасности задача могла бы быть более приближенной к криптографии, например. Впрочем, это дело преподавателя.

  • +1
    У нас на защите информации будет шестичасовая bug bounty на специально сделанной для этого уязвимой площадке. Нужно будет при помощи Kali Linux заниматься брутфорсом, XSS атаками, SQL injections и так далее. Дальше рассказать не могу, поскольку являюсь преподавателем этой дисциплины и не хочу спойлерить :) Может, потом напишу сюда отдельным постом.
    • +1
      Обязательно пишите! Буду ждать ))
    • +2
      Мне так грустно читать про это, потому что я закончил универ, как раз по направлению ИБ и откровенно говорю, что я дерьмовый спец, просто потому, что не было таких вот мероприятий. В какой-то момент я просто положил болт на учебу, в которой была только тупая теория, и занялся прокачкой своих С++ навыков. Теперь работаю разочарованым в российском образовании программистом…
      • +1
        Вы не поверите, но ближайшее будущего российского образования — это мы, разочарованные в нём студенты, которые хотят сделать что-то немного лучше. У меня вот договор с работодателем, что я ухожу на день в неделю преподавать. Себе в убыток, зато следующее поколение будет чуть менее разочарованным.
  • 0

    странное условие
    возьмите x=4, согласно вашего условия
    4>3 true
    (4*4-1 mod 12)=0 false

    • +1
      Условие: для всех простых x > 3

      4 — составное число, помимо как на 1 и 4 оно делится еще и на 2
      • 0

        прошу прощения, упустил из виду :-(

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.