ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 06.04.2021
Просмотров: 171
Скачиваний: 1
Псевдослучайные функции и
перестановки
Псевдослучайная функция (Pseudo Random Function,
PRF)
— эффективно вычислимая функция, определенная на
(
K
,
X
,
Y
)
F
:
K
×
X
→
Y
.
Псевдослучайные функции и
перестановки
Псевдослучайная перестановка (Pseudo Random
Permutation, PRP)
— эффективно вычислимая функция,
определенная на
(
K
,
X
)
E
:
K
×
X
→
X
и имеющая следующие свойства:
•
Существует эффективно вычислимый алгоритм для
вычисления
E
(
k
,
x
)
•
Функция
E
(
k
,
·
)
является однозначной
•
Существует эффективно вычислимый алгоритм для
нахождения обратной функции
D
(
k
,
y
)
.
Безопасные PRF
Интуитивное определение безопасности PRF
F
:
K
×
X
→
Y
- некоторая PRF
Определим:
Funs
[
X
,
Y
] :
множество всех возможных функций из
X
в
Y
S
F
=
{
F
(
k
,
·
)
,
k
∈
K
} ⊂
Funs
[
X
,
Y
]
Невозможно отличить случайно выбранную функцию из
Funs
[
X
,
Y
]
от функции, случайно выбранной из
S
F
Безопасные PRF
Пример использования
F
:
K
× {
0
,
1
}
n
→ {
0
,
1
}
n
- безопасная PRF
Построим безопасный ГСЧ на основе
F
G
:
K
→ {
0
,
1
}
nt
G
(
k
) =
F
(
k
,
0
)
||
F
(
k
,
1
)
||
. . .
||
F
(
k
,
t
)
Основные принципы работы
R
(
k
,
m
)
- раундовая функция
У AES-128 10 раундовых функций