Исследовательские задачи

Уважаемые друзья!

На этой странице публикуются исследовательские задачи Unsolved, которые не обязательно имеют четкую постановку или даже окончательное решение. Каждая Unsolved – это скорее не задача, а направление исследований. Идею Unsolved предложил наш читатель axiomatikos.

Формулировка очередной Unsolved сопровождается комментариями автора, соображениями и, надеемся, решениями читателей.

Присылайте интересные Unsolved по адресу agievich at bsu by.

Unsolved № 2. Парковка

Улица Л имеет длину l. На улице организовано одностороннее автомобильное движение и вся правая сторона Л предназначена для парковки. Боб в автомобиле находится в начале улицы и хочет добраться в самый ее конец, к месту работы. Боб может ехать на автомобиле со скоростью v1, запарковать автомобиль на свободном месте, а затем идти пешком со скоростью v2 < v1. Боб может попытаться подъехать как можно ближе к концу улицы, чтобы сократить время ходьбы пешком. Однако свободных для парковки мест может не оказаться, разворачиваться нельзя и Бобу придется сделать круг по кварталу, чтобы  вернуться в начало Л. Для этого Бобу потребуется время t. Боб может оценивать плотность запаркованных машин на начальном отрезке улицы и, руководствуясь этой оценкой, принимать решение о парковке на очередном свободном месте. Проблема в том, что другие водители действуют примерно так же, поэтому плотность свободных мест на протяжении улицы меняется, что затрудняет принятие решения.
Предложите стратегию, которая позволит Бобу попасть на работу как можно раньше.

Автор: agievich.

Дата публикации: 25.07.2012.

Комментарии автора:

[25.07.2012] Менять скорость движения на автомобиле запрещено. Можно только остановиться для парковки на свободном месте.

Соображения:

[CryptoOfficer, 16.10.2012] pdf.

Unsolved № 1. Определить ключ

Пусть X = {0,1}n – множество двоичных слов длины n. На X заданы две бинарные операции: операция ⊕ сложения слов-как-двоичных-векторов и операция + сложения слов-как-чисел (по модулю 2n ): 110 ⊕ 011 = 101,  110 + 011 = 001. Задана случайная биекция g: XX. Предполагается, что значения g эффективно вычисляются, например, g задана таблично. Зашифрование открытого текста a в шифртекст b на ключе (x, y) выполняется по правилу:
    b = g(a + x) ⊕ y,      a, b, x, yX.
Предложите алгоритм определения неизвестного ключа (x, y) по T парам (открытый текст at, шифртекст bt). Алгоритм должен быть существенно проще полного перебора ключей.
Число пар T может быть большим. Более того, при решении можно выбирать открытый текст at и получать соответствующий шифртекст bt.

Автор: axiomatikos.

Дата публикации: 06.05.2012.

Комментарии автора:

[17.04.2012] pdf.

Соображения:

[CryptoOfficer, 11.07.2012] Мы имеем дело с каскадом двух шифров, соответственно криптоанализ проводится методом meet in the middle с памятью 2^n и числом операций 2^n при T=2. Это существенно проще полного перебора ключей с числом операций 2^{2n}, чего и хотел добиться автор.

 

Новости
23.05.2017
XХII научно-практическая конференция «Комплексная защита информации»
31.03.2017
ITSecurity-2017
22.02.2017
Ввод в действие новой редакции СТБ 34.101.47
21.02.2017
План семинара весна 2017
20.01.2017
Итоги NSUCRYPTO-2016
24.10.2016
План семинара осень 2016
29.08.2016
Ввод в действие СТБ 34.101.77
15.06.2016
CTCrypt-2016
19.04.2016
Криптографические стандарты: планы на 2016 год