Trapdoor One-Way Function: различия между версиями
м Замена текста — «↵<p><span>» на «<span>» |
м Замена текста — «]]</span>» на «]]» |
||
| Строка 1: | Строка 1: | ||
<span>[[Категория: компьютеры]] | <span>[[Категория: компьютеры]] <span>[[Категория: информатика]] <span>[[Категория: безопасность]]<span style="color: indigo;">односторонняя функция с секретом, функция-ловушка, «лазейка» в односторонней функции</span><br/><span style="color: darkslategray;"> Односторонняя функция, эффективное вычисление обратного значения которой возможно при знании дополнительной (секретной — такая секретная информация называется «лазейкой») информации. Функция f<sub>k</sub>(x), зависящая от параметра k, такая что, при известном k можно найти полиномиальные алгоритмы E<sub>k</sub> и D<sub>k</sub>, позволяющие легко вычислить f<sub>k</sub>(x) для всех x и f<sub>k</sub><sup>–1</sup>(y) для всех y, а нахождение f<sub>k</sub><sup>–1</sup>(y) без знания k трудно вычислимо (полиномиального алгоритма не существует) даже при известном алгоритме E<sub>k</sub>. На основе понятия односторонней функции с секретом был предложен принцип открытого распределения ключей и, как следствие, криптосистемы с открытым ключом. Исследования таких функций проводится в основном по следующим направлениям:<br/> • дискретное возведение в степень — алгоритм Диффи-Хеллмана и др.;<br/> • факторизация простых чисел — алгоритм [[RSA]] и др.;<br/> • коды, исправляющие ошибки — алгоритм МакЭллиса и др.;<br/> • задачи NP-полноты — задача об «укладке ранца» и др.</span><br/><i>Смотри также</i> [[RSA]], [[Diffie-Hellman Algorithm]]<br/><br/>— [[Участник:Игорь Мостицкий|Игорь Мостицкий]] ([[Обсуждение участника:Игорь Мостицкий|обсуждение]]) 16:02, 9 января 2026 (MSK) | ||
Текущая версия от 16:06, 24 января 2026
односторонняя функция с секретом, функция-ловушка, «лазейка» в односторонней функции
Односторонняя функция, эффективное вычисление обратного значения которой возможно при знании дополнительной (секретной — такая секретная информация называется «лазейкой») информации. Функция fk(x), зависящая от параметра k, такая что, при известном k можно найти полиномиальные алгоритмы Ek и Dk, позволяющие легко вычислить fk(x) для всех x и fk–1(y) для всех y, а нахождение fk–1(y) без знания k трудно вычислимо (полиномиального алгоритма не существует) даже при известном алгоритме Ek. На основе понятия односторонней функции с секретом был предложен принцип открытого распределения ключей и, как следствие, криптосистемы с открытым ключом. Исследования таких функций проводится в основном по следующим направлениям:
• дискретное возведение в степень — алгоритм Диффи-Хеллмана и др.;
• факторизация простых чисел — алгоритм RSA и др.;
• коды, исправляющие ошибки — алгоритм МакЭллиса и др.;
• задачи NP-полноты — задача об «укладке ранца» и др.
Смотри также RSA, Diffie-Hellman Algorithm
— Игорь Мостицкий (обсуждение) 16:02, 9 января 2026 (MSK)
