(противник хочет узнать закрытый ключ d) =>задача дискретного логарифмирования в Е.
Используется метод Полларда:
Дискретное логарифмирование:
,
Атаки на неотказуемость (не доказано, что возможно).
Уязвимость рандомизатора k (актуальны).
3.3 Хэш-функция
3.3.1 Хэш-функция без ключа
можно
Чтобы сэкономить время: , где H(m) – хэш-функция (сжимает сообщение), (m, S) – сообщение незначительно удлиняется.
Что надо?
Мошенник подобрать m1≠m2: .
Предъявить (m1, S) и отказаться от (m2, S).
=> Требование: сложно подобрать 2 различных сообщения с одинаковым значением хэш-функции.
Парольная защита:
Пользователь предъявляет свой идентификатор (Id) и пароль (P).
Требования:
- нельзя восстановить аргумент хэш-функции по значению (хэш-функция – односторонняя функция);
- нельзя подобрать другой аргумент с тем же значением хэш-функции.
Слабая и сильная хэш-функция:
Определение 1: Слабая хэш-функция называется односторонняя функция , где – набор векторов произвольной длины, Vn – набор бинарных векторов длины n над Zn, n – некоторая константа.
* - любые (произвольные) строки.
Свойства:
Легко вычислить H(x);
Трудно найти ,
Определение 2: Сильная хэш-функция – односторонняя функция , (n – константа) удовлетворяющая свойству 1) и 2’) трудно найти пару x’,
Пара называется коллизией хэш-функции.
Различия сильной и слабой хэш-функции:
Коллизий бесконечно много;
2’) => 2) (сильная также является слабой за счет 2-го условия, т.к. найти фиксированные коллизии нельзя).
Атака на свойство 2): есть x; противник перебирает и проверяет на совпадение значения хэш-функции: .
Перебор значений , выглядит как случайный выбор из множества Vn.
До совпадения с H(x) перебор в среднем равен ;
=.
Стойкая слабая хэш-функция => =>
=> .
Атака на свойство 2’): перебор значений H(x) до повторения, запоминая все предыдущие.
Парадокс (эффект) близнецов: если случайно выбрать элемент из n, то до первого повторения с вероятностью 0,63 придется перебрать раз.
До первого повтора противник должен перебрать .
С вероятностью 0,63 .
Для стойкой сильной хэш-функции
=> .
Следствие: У сильной хэш-функции требования на длину в 2 раза больше чем у слабой.
SHA-1
SHA-2 (расширение значений с 160 до 224,256,384,512)
SHA-3.
Типовая конструкция хэш-функции:
ISO/IEC 10118 1 часть – общая конструкция.
Мериль-Демгард
Обозначения:
- Lh – длина значения H;
- m – аргумент;
- Lm – длина m;
- L1 и L2 – целые числа ϵ Z, Lh ≤ L2;
- – стартовый вектор;
- – шаговая функция хэширования;
- – финальное преобразование.
Алгоритм:
1. m дополняется до кратности L1 бит;
2. разбить дополненную последовательность на блоки m=m1|…|mq: |m1| = L1;
3. определяем стартовое значение H0=IV;
4. для i=1…q, Hi=φ(mi, Hi-1);
5. H(m)=T(Hq)
Для конкретного х необходимо определить:
- L1, L2, Lh;
- метод дополнения L1;
- стартовый вектор IV;
- шаговая функция φ;
- финальные преобразования T;
- методы дополнения.
Как правило, L1 = L2 = Lh.
Методы дополнения описаны в ISO/IEC 10118-1, самое простое – дополнение нулями.
IV выбирается либо нулевой, либо заранее оговоренное значение.
T: часто T(Hq)=Lm бит Hq, T – односторонняя функция.
φ:
- 10118-2: построение блочного шифра для φ (ГОСТ Р 34.10-94).
- 10118-3: заказные хэш-функции, специально построенные φ
(SHA-1, SHA-2, RIPEMD-*).
- 10118-4: использование модулярной арифметики для φ;
, Ki зависит от .
Для модулярной арифметики: ;
Bi строится по m; A – константа; N=pq; e=2.257; MASH-1,-2.
ХФ ГОСТ Р 34.10-94
,
- дополнение до кратности 256 бит;
- нарезка по 256 бит;
- каждый блок сжимается с использованием шифрования ГОСТ Р 28147 ( – шаговая функция хэширования);
- два этапа сжатия с учетом контрольной суммы и длинны сообщения.
Шаговая функция χ
;
.
Алгоритм вычисления шаговой функции:
1) генерация ключей Ki (i=1…4), зависят от H и M;
2) шифрующие преобразование строки H на ключах Ki;
3) перемешивающие преобразование: результат шифрования еще раз перемешивается в H.
