Содержание статьи
Условия конкурса
Всего будет четыре задачи. Первые три — легкие, за правильное решение которых начисляется по 5 баллов за каждую. Четвертая — настоящий жесткач, и стоит она 15 баллов. Победитель определяется по двум показателям: количество баллов + скорость выполнения заданий. Проще говоря, первые, кто качественнее всего справятся с решением, получают призы.
Десять победителей получают 10 дополнительных баллов к поступлению в магистратуру Computer Science, организованную компаниями Acronis и JetBrains, и годовую лицензию Acronis True Image 2018. Также трем первым участникам, приславшим правильные ответы, мы дополнительно подарим:
- power bank;
- наушники;
- кружку Acronis.
Выполнять задания нужно вот здесь. Необходимо будет пройти по ссылке, записать ход решения и дать конечный ответ.
Задача № 1 (разминка). 5 баллов
С помощью одного очень популярного шифра мы зашифровали совет, который даем всем друзьям! Вам необходимо угадать шифр, расшифровать фразу и воспользоваться советом. Так как последний пункт мы не сможем проверить, оставим его на вашей совести. 🙂
Jiks cx bw bpm ncbczm!
Задача № 2. 5 баллов
В задачах шифрования и обеспечения сетевой безопасности используют особые алгоритмы, которые генерируют последовательность чисел. Очевидно, что эта последовательность не является «абсолютно случайной». Если выбрать хороший алгоритм, наша числовая последовательность будет проходить большинство тестов на случайность. Такие последовательности обычно называют псевдослучайными.
Один из стандартных алгоритмов генерации псевдослучайных чисел — линейный конгруэнтный метод (ЛКМ). Он не обладает особой криптографической стойкостью, поэтому применяется в простых случаях. Линейный конгруэнтный метод заключается в вычислении элементов линейной рекуррентной последовательности по модулю некоторого натурального числа m, которые можно посчитать по формуле (1), где n > 0, a и c — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа X0, и при разных его значениях получаются различные последовательности псевдослучайных чисел.
Значения X0, a, c, m называют параметрами генератора. Они полностью определяют результат его работы. Мы решили немного изменить метод и вместо умножения Xn на константу использовать возведение константы в степень Xn. Теперь посчитать n+1 член последовательности можно по формуле (2).
Как мы уже сказали, существенным недостатком метода ЛКМ является предсказуемость его членов, но! Именно это дает возможность решить задачку.
Необходимо предсказать следующие пять значений нашей последовательности. Первые члены: Х1 = 27, Х2 = 54, Х3 = 29, Х4 = 30.
Подсказка: a^X0 = c.
Задача № 3. 5 баллов
Вы наверняка знаете, что хеширование — это преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины, которое, как правило, используется для сравнения данных. Также хеш-коды используются для хранения паролей, так как записывать исходный пароль где-либо очень ненадежно.
Мы решили пойти дальше и сделать несколько операций хеширования одного пароля подряд, чтобы было еще надежнее хранить (шутка). Исходный пароль — стандартный восьмизначный пароль для Windows (регистр учитывается). Решением данной задачи будет правильный алгоритм и количество операций хеширования, а также исходный пароль. Удачи!
fac3377a2f9356a6b1927ba015fcc8cb
Задача № 4. Сложная. 15 баллов!
Пользователь хранит свои файлы в облаке. Каждый раз, добавляя или стирая файл, извлекая его или загружая новую версию, он хочет убедиться, что между обращениями файлы никто не трогал. Для этого пользователь хранит некоторые хеш-значения от данных. Рассмотрим два крайних случая:
- Пользователь хранит хеш-значение от всего массива данных, каждый раз скачивает весь массив и сравнивает хеши. В этом случае на стороне пользователя хранится совсем немного, зато во время проверки пересылается очень много данных, а сама проверка идет долго.
- Пользователь хранит хеш-значение от каждого файла, каждый раз скачивает только нужный файл и сравнивает хеши. В этом случае на стороне пользователя хранится линейный от числа файлов массив данных, но время проверки и объем пересланных данных совсем маленькие.
Придумайте систему, при которой и массив данных, хранящихся у пользователя, и время проверки, и объем пересылаемых данных менее, чем линейны. Опишите протокол проверки, что ничего не изменялось, и протокол обновления данных.
IT-компании, шлите нам свои задачки!
Миссия этой мини-рубрики — образовательная, поэтому мы бесплатно публикуем качественные задачки, которые различные компании предлагают соискателям. Вы шлете задачки на lozovsky@glc.ru — мы их публикуем. Никаких актов, договоров, экспертиз и отчетностей. Читателям — задачки, решателям — подарки, вам — респект от нашей многосоттысячной аудитории, пиарщикам — строчки отчетности по публикациям в топовом компьютерном журнале
