Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2000/01/15.pdf Дата изменения: Fri Dec 23 19:25:38 2005 Дата индексирования: Tue Oct 2 00:09:41 2012 Кодировка: Windows-1251 Поисковые слова: arp 220

МАЛАЯ

ТЕОРЕМА

ФЕРМА

15

точности числа, взаимно простые с 12, и что незачеркнутые числа не образуют решетки. б) Докажите теорему Эйлера по следующему плану: 1) числа, взаимно простые с n, заполняют собой n столбцов таблицы 9; 2) остатки от деления на m всех m чисел любого столбца таблицы 9 различны; 3) в каждом столбце присутствует ровно m чисел, взаимно простых с m; 4) число взаимно просто с mn тогда и только тогда, когда оно взаимно просто с n (такие числа лежат в n столбцах) и взаимно просто с m (в каждом столбце таких чисел m ). 40. Окружность разделили n точками на n равных частей. Сколько можно построить различных замкнутых ломаных из n равных звеньев с вершинами в этих точках? (Две ломаные, получающиеся одна из другой поворотом, считаем одинаковыми. На рисунке 1 изображены все такие ломаные при n = 20.) 41. Для любых натуральных чисел m и n докажите равенства: а) m n = HOK m, n HOД m, n ; б) mn = HOK m, n HOД m, n ; в) m n НОД m, n = mn НОД m, n . г) Пусть m и n натуральные числа, причем НОД(m,n) > 1. Докажите неравенство mn > m n . 42. Решите уравнения: а) x = 18; б) x = 12; в) x x =

bg

Получилось некоторое 78-значное число x. Затем взяли 64-значное простое число p и 65-значное простое число q. Перемножили их (не вручную, разумеется, а на компьютере): pq = 11438162575788886766932577997614661201021829 67212423625625618429357069352457338978305971235639 58705058989075147599290026879543541. Теперь главное:
yx
9007

bg

bg

bg

b

mod pq .

g

= 12;

= x/n, где n натуральное число, натуральное число, n > 1.

b g b g d b gi d b g d b gi b b gbg b g b gd bg b bg FH x IK = x x; д) b xg = x г*)
2 2

b gi g b gi gbg bg bg /2; е) b x g = x/3; ж*) b x g n > 3; з) bnx g = b x g , где

Понимаете? Они опубликовали и произведение pq, и число 9007, и сам метод шифрования (и, разумеется, число y). Было даже сказано, что из чисел p и q одно 64значное, а другое 65-значное. В секрете остались только сами числа p и q. Требовалось найти x. Эта история завершилась в 1994 году, когда Аткинс, Крафт, Ленстра и Лейланд расшифровали эту фразу. Числа p и q оказались равны p = 349052951084765094914784961990389813341776463 8493387843990820577, q = 327691329932667095499619881908344614131776429 67992942539798288533. В книге 'Введение в криптографию' (М., МЦНМО, 1998 г.) сказано: 'Этот замечательный результат (разложение на множители 129-значного числа) был достигнут благодаря использованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта и продолжавшейся после предварительной теоретической подготовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединенных сетью Internet.' К сожалению, рассказ о методе квадратичного решета увел бы нас далеко в сторону от основной темы. Потому оставим его до лучших времен, а здесь обсудим основную идею системы RSA (по первым буквам фамилий авторов: Rivest, Shamir, Adleman). Идея очень красива. Во-первых, зная p и q, можно найти pq = (p 1)(q 1). Во-вторых (и это главное!), если

= n

Шифры с открытым ключом
На вопрос, что он написал в шифровке, Штирлиц ответил: 'Не помню. Теперь это знает только Центр.'

Вообразите, что вам нужно получить зашифрованное сообщение от вашего друга, но вы с ним не договорились заранее, каким шифром будете пользоваться. Как быть? Существует ли такой метод шифрования, что его можно сообщить всему миру (в том числе и вашему другу, и врагам), но это не даст врагам возможности расшифровать сообщение? Это был бы замечательный шифр: в отличие от старых шифров, где главный секрет ключ, знание которого позволяет и зашифровывать, и расшифровывать сообщения, новый шифр 'с открытым ключом': каждый может зашифровывать, но только автор шифра может расшифровать получаемые сообщения.
Шифр RSA
...Так начались необычайные события, которые вовлекли в свой круговорот немало людей. Е.Велтистов

bg

ef = 1 + k pq ,
где e, f, k натуральные числа, то для любого числа x, взаимно простого с pq, по теореме Эйлера имеем

bg

Скорее всего, шифр с открытым ключом уже В 1978 году три математика Ривест, Шамир зашифровали некоторую английскую фразу ли награду в 100$ первому, кто расшифрует

изобретен! и Адлеман и пообещасообщение

x

ef

= x x

ej

k pq

bg

x 1 = x

b

mod pq .

g

y = 968696137546220614771409222543558829057599911 2457431987469512093081629822514570835693147662288 3989628013391990551829945157815154. Они подробно объяснили способ шифрования. Сначала фразу бесхитростно (a = 01, b = 02, c = 03,..., z = 26, пробел = 00) записали в виде последовательности цифр.
4*

Вы поняли, что такое e и f? В нашем примере e = 9007 (единственное обязательное математическое требование к числу e его взаимная простота с числом (p 1)(q 1); впрочем, брать e = 1 или e = (p 1)(q 1) 1 вряд ли разумно, если хотите сохранить секреты). А число f, как уже было сказано, решение сравнения
ef 1

d

mod pq .

b gi

(В Приложении рассказано, как алгоритм Евклида позволяет решать такие сравнения.)