Дискретная математика. Математические вопросы криптографии. Ерош И.Л. - 21 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

21
Вместо буквы исходного сообщения передается номер телефона
абонента, фамилия которого начинается с этой буквы. Поскольку фами-
лия по начальной букве выбирается случайным образом, то одинако-
вым буквам могут соответствовать различные номера телефонов. Од-
нако расшифрование при этом производится однозначно. Криптоанали-
тику, пытающемуся вскрыть шифр, придется решать обратную задачу:
по номеру телефона искать фамилию абонента, имеющего этот теле-
фон. Эта задача при наличии только алфавитного телефонного справоч-
ника может оказаться чрезвычайно громоздкой. Однако легальный по-
лучатель сообщения имеет “лазейку” в виде телефонного справочника,
составленного в соответствии с возрастающими номерами телефонов.
В этом случае найти по телефону фамилию абонента труда не пред-
ставляет. Конечно, этот пример приводится не для практического ис-
пользования, так как всем понятно, что можно составить обратный спра-
вочник. Однако он иллюстрирует идею открытого распределения клю-
чей и принцип “лазейки”.
В настоящее время разработаны различные криптосистемы с от-
крытым распределением ключей. Все они основаны на односторонних
функциях, когда задача шифрования выполняется легко, а обратная за-
дача – очень сложно. Большая часть этих идей использует математи-
ческий аппарат теории чисел. Приведем перечень некоторых фунда-
ментальных задач теории чисел, для которых оценка сложности еще не
определена, но решение которых представляется достаточно трудоем-
ким.
FACTOR (n). Найти разложение большого числа n на множители.
PRIMALITY (n). Решить вопрос о том, является ли n простым чис-
лом?
FIND-PRIME (>n). Найти простое число, большее n.
SQUAREFREENESS (n). Решить, делит или нет квадрат простого
числа число n?
QUAD-RESIDUE (a, n). Решить, выполняется или нет сравнение
x
2
≡ a mod n для некоторого x?
SQUAREROOT (a, n). Найти, если возможно, такое число x, что
x
2
≡ a mod n.
DISCRETE-LOG (a, b, n). Найти, если возможно, такое x, что a
x
≡ b mod n.
Общий прием, используемый при построении криптосистем с откры-
тым ключом, состоит в следующем:

Страницы