Основное содержание
Course: Информатика > Модуль 2
Урок 4: Современная криптография- Основная теорема арифметики
- Криптография с открытым ключом: что это такое?
- Дискретное логарифмирование
- Протокол Ди́ффи — Хе́ллмана
- Алгоритм шифрования RSA, шаг 1
- Алгоритм шифрования RSA, шаг 2
- Алгоритм шифрования RSA, шаг 3
- Временная сложность алгоритма (объяснение)
- Функция Эйлера
- Объяснение функции Эйлера
- Алгоритм шифрования RSA, шаг 4
- Что дальше?
Дискретное логарифмирование
Своего рода математический замок, основанный на принципе модульной арифметики. Создатели: Brit Cruise.
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.
Транскрипция к видео
нужна функция которая легко вычислить но сложно подобрать аргумент по значению на помощь приходят модульная арифметика также известная как часовая арифметика чтобы найти остаток от деления 46 на 12 нужно взять веревку длиной 48 единиц и обернуть вокруг часов с окружностью 12 единиц это называется модуль и где она закончится это и будет ответ то есть остаток от деления 46 на 12 будет равен 10 легко теперь давайте возьмём в качестве модуля простое число например 17 затем найдем так называемые первообразной корень по модулю 17 в нашем случае 3 1 образный корень это число которое при возведении в степень будет равномерно распределяться по нашим часам если возвести 3 в любую степень x то остаток от деления на 17 может с одинаковой вероятностью оказаться любым числом от 0 до 16 а вот обратный процесс уже будет выглядеть сложнее зная что остаток 12 в какую степень нужно возвести 3 это называется задачей дискретного логарифмирования теперь у нас есть функция которая легко вычислить но сложно обратить имея на руках число 12 нам придется методом подбора найти соответствующую степень насколько это сложно с не большими числами легко но если взять простой модуль длиной в сотни знаков подобрать аргумент становится невозможно даже имея в распоряжении самый мощный компьютер для перебора всех вариантов понадобится 1000 лет то есть сила односторонней функции определяется временем для поиска аргумента по значению