Екатерина Юрьевна Америк

Элементы арифметики в криптографии

Е.Ю.Америк планирует провести 2 занятия.

Программа:

• Повторение: кольцо Z/nZ (алгоритм Евклида, функция Эйлера, китайская теорема об остатках, малая теорема Ферма).
• Некоторые оценки "количества времени", необходимого для тех или иных операций.
• Система RSA (возможно, и некоторые другие криптосистемы с открытым ключом).
• Как строить большие простые числа (нужные для RSA) и как попытаться разложить большое число на множители.

Вначале будет рассказано о некоторых криптосистемах с открытым ключом — в частности, о знаменитой RSA. В основе таких криптосистем лежат так называемые «односторонние функции». Это такие функции f из множества сообщений в множество криптограмм (зависящие от параметра, «ключа»), что любое значение f можно вычислить достаточно быстро, в то время как вычисление f ^–1 настолько трудно, что оно оказывается неосуществимым на практике за разумное время.

Один из источников «односторонних функций» — арифметика в кольце Z/nZ. При этом естественно возникают некоторые «алгоритмические» вопросы арифметики: как построить «большое» простое число? Как проверить «большое» число на простоту? Как разложить «большое» составное число на множители? Я постараюсь рассказать о некоторых алгоритмах, которые для этого используются.

Наконец, я надеюсь рассказать — очень кратко и, как правило, без доказательств — об эллиптических кривых и их применении в криптографии и алгоритмических проблемах.

Желательно некоторое знакомство с начальными понятиями алгебры (группа, кольцо, поле, теорема Лагранжа) и арифметики (алгоритм Евклида, кольцо Z/nZ, китайская теорема об остатках).

Organization Committee e-mail:
dubna@mccme.ru