Однонаправленные функции

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 09:10, 12 мая 2016.

Понятие однонаправленной функции (One-way function)[1]

TemplateDifinitionIcon.svg Определение «Определение - Однонаправленная функция»
Функция называется однонаправленной, если:
  1. Для любого х, принадлежащего области определений, найти значение вычислительно просто, т.е. существует полиномиальный алгоритм
  2. Почти для всех принадлежащих области значений, найти значение вычислительно невозможно, т.е. [2]. Т.к. прообразов может быть много, то должна быть обеспечена невозможность найти хотя бы один.

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

В настоящее время ни для одной функции не доказано, что она является однонаправленной. Из существования таковой немедленно следует, что .

Для многих криптографических примитивов ее существование необходимо и достаточно, для других - только необходимо.

Примеры "претендентов" на однонаправленную функцию

  1. Пример из жизни: разбитая тарелка (разбить - легко, собрать черепки в целую тарелку - затруднительно).
  2. где:
фиксированный открытый текст;
ключ;
шифротекст.
Все симметричные алгоритмы должны быть полиномиальны (для обеспечения быстрого зашифрования).
Злоумышленник:
  • знает
  • ищет , т.е. восстанавливает ключ по известному открытому тексту и шифротексту.
Длина ключа может быть:

GOST, AES стойки против атаки симметричным ключом.

3. где:

- первообразный корень,

- большое простое число.

Все зависит от размера .

Длина , принятая в алгоритмах:

до 2010г.

в настоящее время.

4.

- базовая точка эллиптической кривой над конечным простым полем - аналог первообразного корня.

5. Hash functions (функции хеширования) - представляют собой однонаправленные функции, обладающая дополнительными свойствами. В настоящее время NIST проводит конкурс на новый стандарт хеширования "SHA-3" (New Cryptographic Hash Algorithm (SHA-3) Family). К 9 декабря 2010 года были отобраны 5 финалистов: BLAKE, Grøstl, JH, Keccak, и Skein. На сегодняшний день наиболее часто и широко применяемым алгоритмом криптографического хеширования является SHS-1 (160 бит - длина хеш-значения), а также SHA-2: SHA-224/256 и SHA-384/512.

Области применения однонаправленных функций

1. Парольные системы

Owf1 new.PNG

В случае парольных систем очень важно обязательно сохранять целостность базы, т.к. она может быть скопирована, изучена, возможно, модифицирована. Тот, кто скопировал базу, пытается отыскать значение:

2. Системы аутентификации S/KEY (Bellcore Corp.)

Owf2 new.PNG

3. Микроплатежи

Приставка "микро" в слове "микроплатежи" обусловлена тем, что оплата может производиться десятой долей цента. Для обеспечения полной безопасности, обычно, используется ЭЦП, однако ЭЦП - очень дорогая операция, применяемая в случае платежей на большие суммы.

TemplateExampleIcon.svg Пример Пример систем микроплатежей
PayWord, MicroMint, система оплаты сотового телефона.


Системы предоплаты:

Owf3 new.PNG

Провайдер может обмануть следующим образом: списать сразу всю сумму, а не поэтапно, в соответствии с оказанными услугами.

В системах предоплаты используется система, аналогичная S/KEY:

Пользователь Провайдер


Проверка значения ; если верно, то провайдер списывает деньги

Злоумышленник Z ищет прообраз от
(хочет получить )

Для доказательства правильного снятия средств провайдер должен предъявить все прообразы, соответствующие списанным суммам
НО: может подменить
Поэтому, как правило, дубликат имеется у третьей стороны (судьи, доверенного лица[3])
Owf4 new.PNG

Можно обойтись и без доверенных лиц - в этом случае необходима ЭЦП.

4. Одноразовая подпись (One-time signature)[4]

Алгоритм одноразовой подписи представляет собой набор из трех алгоритмов:

а) Алгоритм выработки параметров
Owf5 new.PNG
б) Алгоритм выработки подписи

Двоичный вектор: документ,

- ЦП к документу, которая ставится подписывающим (т.е. А) в некоторый момент времени .

Документ с ЦП служат для offline-аутентификации. Любой, кто имеет открытый ключ, может, в таком случае, проверить ЦП.

в) Алгоритм проверки ЦП

Пусть В проверяет ЦП.

Дано: ЦП (необходима для обеспечения подлинности, НЕ секретности).

Проверка:

Пусть: - прообраз (в ЦП). Тогда можно предположить, что злоумышленник, заменив: получит подделку ЦП. Однако такая ситуация недопустима, т.к. применяется однонаправленная функция

Алгоритм одноразовой подписи обязан обеспечить неотказуемость (non-repudation), т.е. возможность доказать третьей стороне, что что-то было действительно выполнено.

Особенности схемы

+ быстрая ЦП (используется только симметричный алгоритм)
+ универсальность (основа - стандарт о ЦП)
+ стойкая, в т.ч. в случае создания квантовых компьютеров
- одноразовость (нельзя использовать два раза одни и те же ключи)
- большой размер ( 256 бит; современная ЭЦП - 512бит). Поэтому для подписи большого текста используют хэш-функцию
(256 бит для современных хеш-функций).

Атака

Подмена открытых ключей:

Удостоверяющий центр хранит открытые ключи в целостности. Сам УЦ подписать НЕ может (т.к. не вычислит прообраз -ов). В УЦ хранятся сертификаты ОК (оформлены согласно стандарту X.509: указывается время действия сертификата, вид используемого алгоритма, отозван ли сертификат или нет, и пр.).

(Public Key Cryptography, Инфраструктура Открытых Ключей)

Необходимо также подписывать хэш, т.к. возможно "выкидывание" части документа.

5. Сертификат честности

Пусть - большое простое число.

Назовем "плохими" следующего вида: (раскладываются по степеням малых простых чисел).

может быть выбрано "плохо". Необходимо, чтобы вырабатывающий сертификат обеспечивал выбор "хорошего" .

На стороне проверяющего сертификат имеем: (выбираем), (получаем) (предъявляем).

Вообще говоря, при случайном выборе вероятность выбрать плох - очень низкая.

Пусть было выбрано:

плох плохплох плпл (НО: найти пл вычислительно сложно).

6. GSM Security

- долговременный ключ длиной 128 бит.

  • MS (Mobile Station)=ME(Mobile Equipment)+SIM-карта.
  • BS (Basic Station)
  • MSC (Mobile Switching Center)
Owf6 new.PNG

Аутентификация MS:

(128) лежит в SIM, (128) - передается от BS, - старшие биты, передаваемые в открытом виде.

Ключ для шифрования:

- получаем аналогичным предыдущему образом, но с другой однонаправленной функцией - A8.

Как правило, в качестве A3, A8 используются плохие функции: также стоит отметить, что между станциями передаваемый трафик не шифруется.

На практике никто ничего не вычисляет: передаются между базовыми станциями (BS) и проверяются.

7. Карты предоплаты (Scratch Cards)

Выработка scratch-кодов:

1. Выработка случайной последовательности (например, посредством ПАК "Соболь"), энтропия которой относительно невелика.
2. Перешифровать.
Результат разбиения на "отрезки": проверочный символ.
Нарезаем на "отрезки" следующим образом: остальное отбрасываем.
~10-15% - ошибки.
Проверочный символ получается с помощью однонаправленной функции с ключом
3. - хеш-значение результата помещается в базу. Таким образом, в центре обработки:
Owf7 new.PNG

Примечания

  1. Первым однонаправленную функцию предложил Р. Нидхэм (Needham R.)
  2. Именно не существует, а не не известен.
  3. Т.е. TTP (от англ. "Trusted Third Part").
  4. Предложена Лампортом (Lamport).