Система шифрования с открытым ключом алгоритм rsa. Криптографическая система RSA. ЭЦП и открытый ключ

Разработанный ещё в 70-е годы прошлого века механизм распределения прав в операционных системах оказался настолько успешным, что используется в UNIX-системах до сих пор, то есть уже больше сорока лет.

Права доступа 777 - что это?

Базовый принцип способа распределения доступа включает в себя существование обязательных атрибутов, таких как имена пользователей системы, а также их групп. Почти очевидным является тот факт, что в Linux у каждого юзера может быть только одно имя, которое должно быть уникально в рамках этой системы. С помощью никнейма пользователь входит в систему, то есть проходит авторизацию. Помимо этого, операционка содержит конечное число групп пользователей. Каждый из них может входить в состав одной или нескольких групп. Редактировать свойства, создавать и удалять группы может суперпользовать - root. Участники различных групп имеют различные права для действий в системе. Так, например, администратор владеет большими правами, чем гость.

Индексный дескриптор (который есть у каждого файла) содержит логин владельца и название группы пользователей, имеющей права к данному файлу.

При создании файла его владельцем становится пользователь, от имени которого запущен этот процесс. Группа новосозданного файла так же определяется с помощью идентификатора группы действующего процесса. При дальнейшей работе все эти значения можно изменить при помощи команд консоли, о которых далее пойдет речь.

Как изменить права доступа

Команда chmod может изменить режим пользовательского доступа к файлу. Как-либо менять эти права разрешено исключительно его владельцу либо суперпользователю. В Unix-системах код принято задавать в виде числа в восьмеричной форме, или при помощи специальных мнемонических знаков (букв). Использование каждого способа имеет свои преимущества и недостатки. Так, с помощью цифрового указания прав доступа системный администратор сможет быстрее настроить нужный тип доступа, а с помощью мнемонических кодов он сможет сделать это более точно - например, добавить или удалить право на запись, либо запретить право на чтение.

В качестве первого аргумента консольной команды chmod выступает спецификация пользовательских прав доступа, а это есть мнемоническое обозначение, или восьмеричное число. Второй и следующий аргументы это названия файлов, к которым мы пытаемся изменить права доступа. При установке прав в виде трех чисел, первая цифра определяет права для владельца, 2-ая для группы, и третья для всех остальных юзеров.

Мнемонические обозначения прав доступа

Доступ к файлам в системе прав имеет такие вариации:

r - доступ к чтению файла;
w - право редактирование данных (но не удаление);
x - возможость запускать файл к исполнению.

По отношению к каталогам действует такия система прав:

r — пользователь может читать любые файлы директории;
w — с этими правами можно создавать и удалять файлы в папке, даже если некоторые из них в каталоге принадлежат другому юзеру;
x — обозначает право входа в директорию. Если вы имеете права w к вложеной папке но не имеете прав на папку уровнем выше, то и к своей папке никак не пробьетесь.

Всего возможно 8 различных комбинаций, которые приведены на рисунке ниже.

С помощью таблицы ниже вы сможете понять, как реализовать сложные варианты назначения прав, а также как установить права доступа 777, используя мнемонические спецификации chmod.

Как установить права доступа 777 через SSH

Приведем некоторые примеры использование команды chmod:

chmod 711 file_name.txt.

Использование такого сценария распределения файлов приведет к тому, что у владельца будут все права на файл, а все остальные группы пользователей смогут только выполнять его.

При использования кода 775 мы предоставим владельцу и всей его группе полный перечень прав. Остальные же пользователи не смогут выполнять изменения в файле. Нужно сказать, что для указания файла только по его собственному имени, необходимо находится в директории, где расположен этот файл. В ином случае вы можете переместиться в эту директорию командой cd имя_директории/имя_вложеной_директории или использовать следующую структуру:

chmod 775 /var/bin/file_name.txt.

Чтобы рекурсивно изменить права ко всем файлам в каталоге и всем вложенным папкам, нужно добавить ключ -R к команде chmod. Полученная команда будет выглядеть так:

chmod -R 711 file_name.

В итоге, как выставить права доступа 777 для файла или каталога, не будет проблемой - просто необходимо залогиниться на вашем веб-сервере через SSH и выполнить команду:

chmod 777 имя_файла.

Как установить права доступа 777 в контрольной панели сервера

Вы также можете реализовать аналогичную процедуру через визуальный интерфейс FTP клиента FileZilla или SFTP клиента WinSCP. Для этого необходимо будет выполнить авторизацию на вашем сервере в одной из этих программ, в визуальном интерфейсе выбрать ваш файл или папку, затем нажать правую клавишу мыши и установить галочки рядом с нужными правами.

Иногда, в случае срочной надобности, у вас может не быть доступа к Windows-клиенту, поэтому можно осуществить смену прав доступа через контрольную панель веб-сервера. Для этого, используя файловый менджер вашей контрольной панели, выберите необходимые файлы и нажмите на кнопку Change Permissions ("Смена прав"). Далее необходимо будет так же отметить всё галочками, и теперь вопрос, как установить права доступа 777 на папку больше не будет для вас сложным.

Алгоритм шифрования с открытым ключом RSA был предложен одним из первых в конце 70-х годов ХХ века. Его название составлено из первых букв фамилий авторов: Р.Райвеста (R.Rivest), А.Шамира (A.Shamir) и Л.Адлемана (L.Adleman). Алгоритм RSA является, наверно, наиболее популярным и широко применяемым асимметричным алгоритмом в криптографических системах.

Алгоритм основан на использовании того факта, что задача разложения большого числа на простые сомножители является трудной. Криптографическая система RSA базируется на следующих двух фактах из теории чисел:

задача проверки числа на простоту является сравнительно легкой;
задача разложения чисел вида n = pq (р и q - простые числа); на множители является очень трудной, если мы знаем только n , а р и q - большие числа (это так называемая задача факторизации, подробнее о ней см. "Основные положения теории чисел, используемые в криптографии с открытым ключом").

Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные должны быть представлены в виде целых чисел между 0 и n -1 для некоторого n .

Шифрование

Итак, рассмотрим сам алгоритм. Пусть абонент А хочет передать зашифрованное сообщение абоненту Б. В этом случае абонент Б должен подготовить пару (открытый ключ; закрытый ключ) и отправить свой открытый ключ пользователю А.

Первым этапом является генерация открытого и закрытого ключей. Для этого вначале выбираются два больших простых числа Р и Q . Затем вычисляется произведение N :

После этого определяется вспомогательное число f :

f = (Р - l)(Q - 1).

Затем случайным образом выбирается число d < f и взаимно простое с f .

Числа d и N будут открытым ключом пользователя, а значение е – закрытым ключом.

Таким образом, на этом этапе у пользователя должна быть информация, указанная в следующей таблице:

Так как пользователь Б хочет получить зашифрованное сообщение от пользователя А, значит пользователь Б должен отправить свой открытый ключ (d, N) пользователю А. Числа Р и Q больше не нужны, однако их нельзя никому сообщать; лучше всего их вообще забыть.

На этом этап подготовки ключей закончен и можно использовать основной протокол RSA для шифрования данных.

Второй этап – шифрование данных . Если абонент А хочет передать некоторые данные абоненту Б, он должен представить свое сообщение в цифровом виде и разбить его на блоки m 1 , m 2 , m 3 , ... , где m i < N . Зашифрованное сообщение будет состоять из блоков с i .

Абонент А шифрует каждый блок своего сообщения по формуле

c i = m i d mod N

используя открытые параметры пользователя Б, и пересылает зашифрованное сообщение С=(с 1 , с 2 , с 3 , ...) по открытой линии.

Абонент Б, получивший зашифрованное сообщение, расшифровывает все блоки полученного сообщения по формуле

Все расшифрованные блоки будут точно такими же, как и исходящие от пользователя А.

Злоумышленник, перехватывающий все сообщения и знающий всю открытую информацию, не сможет найти исходное сообщение при больших значениях Р и Q .

Пример вычислений по алгоритму

Пусть пользователь А хочет передать пользователю Б сообщение. В этом случае вначале пользователь Б должен подготовить открытый и закрытый ключи. Пусть им выбраны, например, следующие параметры:

Р = 3, Q = 11, N = 3x11 = 33.

Тогда f = (Р - l)(Q - 1) = (3-1)(11-1) = 20 .

Затем пользователь Б выбирает любое число d , не имеющее общих делителей с f (это необходимо для того, чтобы зашифрованное сообщение можно было потом однозначно восстановить). Пусть d = 13 . Это число будет одним из компонентов открытого ключа.

Под катом описаны примеры выбора «плохих» параметров шифра RSA.

«Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля RSA (числа n ) для каждого из корреспондентов сети. В связи с этим можно сказать следующее. Читатель может самостоятельно убедиться в том, что зная одну из трех величин p , q или φ(n) , можно легко найти секретный ключ RSA…».

Дополним этот текст. При неудачном выборе модуля шифра RSA, как это сделано в примере пособия, приводимом ниже, можно дешифровать текст и без наличия секретного ключа, т.е. не зная ни одной из трех названных величин.

Для этого достаточно располагать зашифрованным текстом, заданным модулем шифра n , открытым ключом е шифра и выполнить всего три шага атаки «бесключевого чтения». После четвертого атакующего шага устанавливается, что на предыдущем шаге был получен исходный текст, он может быть прочитан. Покажем, насколько просто это делается.

Вначале приведем сам пример со стр. 313-315 из названного пособия.

Пример

Шифрование короткого исходного текстового сообщения: RSA .
Получатель устанавливает шифр с характеристиками n=pq=527 , где р=17 , q=31 и φ(n)=(р –1)(q – 1)=480 . В качестве открытого ключа е выбрано число, взаимно простое с φ(n) , е=7 . Для этого числа с помощью расширенного алгоритма Евклида найдены целые числа u и v , удовлетворяющие соотношению е∙u+φ(n)∙v=1 :

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137 .

Поскольку –137≡343(mod480) , то d=343 .

Проверка: 7∙343=2401≡1(mod480) .

Текстовое сообщение представляется в виде последовательности чисел, содержащихся в интервале . Для этого буквы R , S и A кодируются пятиразрядными двоичными числами. Используются порядковые номера этих букв в английском алфавите при их двоичном представлении:

R=18 10 =(10010) 2 , S=19 10 =(10011) 2 ,
A=1 10 =(00001) 2 .

Тогда RSA=(100101001100001) 2 . Разбиение текста на блоки ограниченной длины дает представление из двух блоков: RSA=(100101001), (100001)=(М 1 =297, М 2 =33) .

Последовательно шифруются блоки исходного текста М 1 =297 , М 2 =33 :
y 1 =Е k (М 1)=М 1 e ≡297 7 (mod527)=474 .

Здесь воспользовались тем, что:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474 ,
y 2 =Е k (М 2)=M 2 e ≡33 7 (mod527)=407 .

Шифрованный текст, как и исходный, получаем в виде двух блоков: у 1 =474 ; у 2 =407 .

Расшифрование представляется последовательностью действий D k (y i)=(y i) d =(y i) 343 (mod 527) , i=1,2 .

Вычисления возведения в степень d более удобно проводить, предварительно представляя показатель степени суммой степеней числа 2 , а именно: 343=256+64+16+4+2+1 .

Используя это представление показателя степени d=343 , получаем:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
и окончательно 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297 .

Аналогично вычисляется значение 407 343 (mod527)=33 .

Переход к буквенному представлению расшифрованного сообщения дает: RSA .

После рассмотрения примера в пособии приводятся рассуждения о стойкости системы RSA. Подчеркивается необходимость соблюдения осторожности в выборе модуля шифра RSA (числа n ) для каждого из корреспондентов сети. Указывается на недопустимость игнорирования требований к выбираемым характеристикам системы шифрования. Среди таких требований, к сожалению, не указано то, нарушение которого иллюстрирует приведенный пример.

Атака на шифр RSA

Рассмотрим пример атаки на шифр RSA. Воспользуемся данными примера, приведенного на странице 313-315 в учебном пособии «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001.

Неудачность (недопустимость) выбранных параметров системы в этом примере легко показывается вычислениями, реализующими атаку бесключевого чтения исходного текста. Сущность такой атаки состоит в следующем. Заданы открытый ключ шифра RSA (е=7 , n=527 ) и шифрованный текст. В примере шифрованный текст представлен двумя блоками
у=(у 1 =474, у 2 =407) .

Каждый шифрованный блок атакуется индивидуально, вначале атакуем у 1 =474 , после его дешифрования, атакуем другой блок у 2 =407 .

Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений у i , у 1 =у имеющийся шифрованный текст.

В алгоритме атаки на шифрованный текст определяется такой номер шага j , для которого y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i , i>1 . Из последнего соотношения видим, что при возведении в степень е значения (y i e j–1 (mod n)) получается начальный шифoртекст y i = у 1 .

Но это и означает, что на этом шаге шифровался открытый текст. Непосредственными вычислениями (их оказывается совсем немного) с использованием экранного калькулятора находим то значение j , при котором цикл шифрования завершается значением y 1 , с которого цикл и был начат.

Атака на первый блок у 1 =474 шифртекста.
Шаг 1 : 474 7 (mod527)=382 ;
Шаг 2 : 382 7 (mod527)=423 ;
Шаг 3 : 423 7 (mod527)=297 ;
Шаг 4 : на этом шаге шифруется уже найденный исходный текст, но его необходимо выполнить, так как атакующий исходного текста не знает. Признаком завершения атаки является совпадение начального значения шифртекста (474 ) и результата 4-го шага зашифрования. Именно такое совпадение и имеет место.

297 7 (mod527)=474 получили начальный (первый) блок шифртекста. Атака на первый блок завершена успешно у 1 =474 . Предшествующий результат шага 3 равен открытому тексту М 1 =297 .

n=527 r=297 по модулю n=527 . Это записывается так y i =у 1 =297 . Формируем степенные вычеты
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297 .

Атака на второй блок у 2 =407 шифртекста.
Шаг 1 : 407 7 (mod527)=16 ;
Шаг 2 : 16 7 (mod527)=101 ;
Шаг 3 : 101 7 (mod527)=33 ;
Шаг 4 : 33 7 (mod527)=407 .

Вновь на третьем шаге получен блок исходного текста (М 2 =33 ), но атакующему это неизвестно, и он выполняет следующий (четвертый шаг), результат которого (407 ) совпадает с начальным шифртекстом у 2 =407 .

По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=33 по модулю n=527 . Это записывается так y i =у 2 =33 .
Формируем степенные вычеты ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33 .

Результат атаки (исходный текст М 1 =297 , М 2 =33 ) получен трехкратным шифрованием заданного шифртекста. Больший успех для атакующего шифртекст трудно представить.

Продолжая обсуждение вопроса о выборе модуля и других параметров шифра, можно добавить, что модуль шифра (n=527 ) некоторые исходные тексты вообще не позволяет шифровать. При этом выбор значения открытого ключа е большой роли не играет. Существуют значения исходных текстов, которые вообще невозможно зашифровать выбранным шифром с модулем n=527 .

Ни на одном из заданных е не удается зашифровать исходные тексты, представляемые числами
187 , 341 , 154 и 373 .

Пример (невозможность шифрования значений некоторых исходных текстов)

Пусть исходные тексты представлены четырьмя блоками y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373) . Экспонента е открытого ключа шифра может быть любым взаимно простым числом с функцией Эйлера φ(n)=φ(527)=480 . Впрочем, для рассматриваемого случая открытый ключ е может быть задан произвольно. Действительно, пусть е=2, 4, 7, 9, 17, 111 тогда:

154 2 (mod527)=1 ;
154 4 (mod527)=1 ;
154 7 (mod527)=154 ;
154 9 (mod527)=154 ;
154 17 (mod527)=154 ;
154 111 (mod527)=154 ;
187 2 (mod527)=187 ;
187 4 (mod527)=187 ;
187 7 (mod527)=187 ;
187 9 (mod527)=187 ;
187 17 (mod527)=187 ;
187 111 (mod527)=187 ;
341 2 (mod527)=341 ;
341 4 (mod527)=1 ;
341 7 (mod527)=341 ;
341 9 (mod527)=341 ;
341 17 (mod527)=341 ;
341 111 (mod527)=341 ;
373 2 (mod527)=1 ;
373 4 (mod527)=373 ;
373 7 (mod527)=373 ;
373 9 (mod527)=373 ;
373 17 (mod527)=373 ;
373 111 (mod527)=373 .

Из рассмотренного примера следует простой вывод. Действительно, к выбору параметров процесса шифрования надо подходить очень внимательно и проводить тщательный предварительный анализ таких параметров. Как это делать - отдельный вопрос, и в рамках этой работы он не рассматривается.

Под катом описаны примеры выбора «плохих» параметров шифра RSA.

Вначале приведем сам пример со стр. 313-315 из названного пособия.

Пример

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137 .

Поскольку –137≡343(mod480) , то d=343 .

Проверка: 7∙343=2401≡1(mod480) .

R=18 10 =(10010) 2 , S=19 10 =(10011) 2 ,
A=1 10 =(00001) 2 .

Последовательно шифруются блоки исходного текста М 1 =297 , М 2 =33 :
y 1 =Е k (М 1)=М 1 e ≡297 7 (mod527)=474 .

Здесь воспользовались тем, что:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474 ,
y 2 =Е k (М 2)=M 2 e ≡33 7 (mod527)=407 .

Шифрованный текст, как и исходный, получаем в виде двух блоков: у 1 =474 ; у 2 =407 .

Расшифрование представляется последовательностью действий D k (y i)=(y i) d =(y i) 343 (mod 527) , i=1,2 .

Используя это представление показателя степени d=343 , получаем:

Аналогично вычисляется значение 407 343 (mod527)=33 .

Переход к буквенному представлению расшифрованного сообщения дает: RSA .

Атака на шифр RSA

Пример (невозможность шифрования значений некоторых исходных текстов)

Наконец-то настало время заняться описанием RSA-криптосистемы. Помимо объяснения, как она работает, мы должны в деталях обсудить ее безопасность; другими словами, почему настолько трудно взломать сообщение, зашифрованное RSA-криптосистемой?

§ 12.1. О начале и конце

Чтобы реализовать систему шифрования RSA, предназначенную для одного пользователя, необходимо выбрать два различных простых числа р и q и вычислить их произведение Простые р и q хранятся в тайне, в то время как число становится частью открытого ключа. В § 12.5 мы подробно обсудим метод выбора простых составляющих ключа, а также то, как этот выбор связан с надежностью системы.

Сообщение (которое можно считать целым числом) шифруется путем возведения в некоторую степень по модулю Поэтому сначала мы должны найти способ представить текст сообщения в виде списка классов по модулю Это, в действительности, еще не процесс шифрования, а только подготовка сообщения к тому, чтобы его можно было зашифровать.

Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, - последовательность букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из следующей таблицы:

(см. скан)

Пробел между словами заменяется на число 99. Проделав эту процедуру, мы получим число, возможно очень большое, если сообщение было длинным. Однако, это еще не окончательное число, к которому мы стремимся, а всего лишь набор классов по модулю И теперь нам нужно разбить численное представление сообщения на кусочки, каждый из которых - натуральное число, не превосходящее Эти кусочки принято называть блоками сообщения.

Например, численное представление девиза «ПОЗНАЙ СЕБЯ» выглядит так:

Выбрав простые мы получим произведение Поэтому численное представление сообщения, выписанное выше, нужно разбить на блоки, меньшие чем 23 393. Приведем одно из таких разбиений.

Конечно, выбор блоков не однозначен, но и не совсем произволен. Например, во избежание двусмысленностей на стадии

расшифровки не следует выделять блоки, начинающиеся с нуля.

При расшифровке сообщения, зашифрованного системой шифрования RSA, получают последовательность блоков. Затем их соединяют вместе и получают численное представление сообщения. И только после замены чисел буквами в соответствии с приведенной таблицей можно будет прочесть исходное сообщение.

Обратите внимание на то, что каждая буква таблицы кодируется двузначным числом. Так делается для предотвращения путаницы. Предположим, мы пронумеровали буквы по порядку, начиная с 1, т.е. А соответствует 1, Б - 2, и так далее. В этом случае мы не сможем точно сказать, обозначает ли блок 12 пару букв или только одну букву двенадцатую букву алфавита. Конечно, для численного представления сообщения можно использовать любое однозначное соответствие между буквами и числами, например, -кодировку, при которой перевод сообщения в цифровую форму автоматически выполняется компьютером.

§ 12.2. Шифровка и дешифровка

Сообщение, подготовленное к шифровке по методу § 12.1, состоит из последовательности блоков, каждый из которых - число, меньшее, чем Теперь обсудим, как шифруется каждый блок. Для этого нам потребуется число равное произведению простых и натуральное число, обратимое по модулю т.е. число удовлетворяющее условию

Напомним, что по известным р и q число легко вычисляется. Действительно,

Пара называется открытым, или кодирующим, ключом криптосистемы RSA, которую мы описываем. Пусть блок сообщения, то есть целое число, удовлетворяющее неравенству Символом мы будем обозначать блок зашифрованного сообщения, соответствующий Он вычисляется по следующему правилу:

Заметим, что каждый блок сообщения шифруется отдельно. Поэтому зашифрованное сообщение, фактически, состоит из отдельных закодированных блоков. Более того, мы не можем объединить эти блоки в одно большое число, поскольку в результате расшифровать сообщение станет невозможно. Вскоре мы увидим причину этого.

Вернемся к примеру, который начали рассматривать в первом параграфе. Мы зафиксировали так что Теперь нужно выбрать число Напомним, что оно должно быть взаимно простым с Наименьшее простое число, не делящее 23088, равно 5. Положим Чтобы закодировать первый блок сообщения из § 12.1, нам предстоит определить вычет числа 25245 по модулю 23 393. С помощью программы символьных вычислений (или калькулятора, если хватит терпения) мы получим, что искомый вычет равен 22 752. Итак, Все же зашифрованное сообщение представляется следующей последовательностью блоков:

Посмотрим, как декодируются блоки зашифрованного сообщения. Чтобы приступить к дешифровке, нам необходимо знать и обратный элемент к по модулю Последний из них - это натуральное число, которое мы будем обозначать через Пара называется секретным, или декодирующим ключом системы шифрования RSA. Если а - блок зашифрованного сообщения, то соответствующая его дешифровка

Получается в результате операции:

Прежде чем вернуться к примеру, необходимо дать некоторые комментарии. Во-первых, вычислить очень легко, если знать Действительно, секретный ключ определяется с помощью расширенного алгоритма Евклида. Во-вторых, если блок исходного сообщения, то мы вправе ожидать равенства Другими словами, декодируя блок шифрованного сообщения, мы надеемся узнать соответствующий блок исходного. То, что это так и будет, не следует непосредственно из описанного выше алгоритма, но мы все подробно обсудим в следующем параграфе.

Наконец, как мы утверждали во введении и на протяжении всей книги, для взлома RSA-криптосистемы необходимо разложить на множители, потому что для дешифровки сообщения нужно знать Однако после того, как работа системы подробно описана, ясно, что последнее утверждение не совсем точно. Чтобы прочесть шифровку, кроме самого нужно знать только обратный к элемент по модулю Поэтому для взлома системы достаточно вычислить при известных Оказывается, это вычисление равносильно разложению числа на множители, как мы убедимся в § 12.4.

В обсуждаемом примере Для определения применим расширенный алгоритм Евклида к числам и 5.

(см. скан)

Таким образом, Следовательно, обратным к 5 по модулю будет -9235 и

Наименьшее натуральное число, сравнимое с -9235 по модулю Значит, для раскодирования блока шифрованного сообщения мы должны возвести его в степень 13 853 по модулю 23 393. В нашем примере первый закодированный блок - это 22 752. Вычисляя вычет числа 22 75213853 по модулю 23 393, получим Заметьте, что даже при таких малых числах требования, предъявляемые при работе RSA-криптосистемы, превышают возможности большинства карманных калькуляторов.

§ 12.3. Почему она работает?

Как мы уже отмечали ранее, шаги, описанные выше, приводят к работающей криптосистеме, только если в результате декодирования каждого блока шифрованного сообщения будет восстанавливаться соответствующий блок исходного. Предположим, что мы имеем дело с системой RSA, имеющей открытый ключ и секретный ключ Придерживаясь обозначений § 12.2, нам нужно показать, что для любого целого числа удовлетворяющего неравенству выполняется тождество

На самом деле, достаточно доказать, что

Действительно, как 6, так и неотрицательные целые числа, меньшие Поэтому они сравнимы по модулю тогда и только тогда, когда они равны. Это, в частности, объясняет, почему мы разбиваем численное представление сообщения на блоки, меньшие Кроме того, отсюда видно, что блоки

закодированного сообщения необходимо записывать отдельно: в противном случае наши рассуждения не будут работать.

Из рецептов шифрования и дешифрования следует, что

Поскольку элементы взаимно обратны по модулю найдется такое натуральное к, что Более того, по условию, числа больше Следовательно, Подставляя вместо произведения в уравнение (3.1), получаем

Теперь воспользуемся теоремой Эйлера, которая утверждает, что Отсюда т. е.

и мы полностью получили бы доказательство, если бы в него не закралась маленькая ошибочка.

Внимательно просмотрев еще раз наши рассуждения, Вы заметите, что мы не учитывали условий теоремы Эйлера. На самом деле, прежде чем применять теорему, необходимо убедиться во взаимной простоте чисел За этим, казалось бы, нужно следить при подготовке сообщения к шифровке, т.е. во время разбиения численного представления сообщения на блоки нужно добиваться уверенности в том, что все получающиеся блоки взаимно просты с К счастью, в этом нет необходимости, потому что на самом деле сравнение выполнено для любого блока. И ошибка кроется не в результате, который мы хотим доказать, а только лишь в самом доказательстве. Правильный подход основывается на рассуждениях, использованных при доказательстве теоремы Корселта в главе 7.

Напомним, что где различные простые числа. Определим вычеты числа по модулям Поскольку

вычисления для обоих простых чисел аналогичны, мы проработаем в деталях только случай Итак, мы уже убедились в том, что

для некоторого целого Следовательно,

Мы хотели бы теперь применить теорему Ферма, но имеем право сделать это, только если не делит Пусть это требование выполнено. Тогда и мы получаем, что

Заменив теорему Ферма теоремой Эйлера, мы не решили возникшей проблемы: сравнение справедливо только для некоторых, но не для всех блоков. Однако теперь блоки, для которых рассуждения не проходят, должны делиться на Далее, если делит то как 6, так и сравнимы с 0 по модулю а значит сравнимы между собой. Таким образом, доказываемое сравнение справедливо и в этом случае. Следовательно, сравнение истинно для любого целого числа Обратите внимание на то, что мы не. могли использовать подобное рассуждение, когда применяли теорему Эйлера к Действительно, неравенство не означает сравнения потому что число составное.

Итак, мы доказали, что Аналогично доказывается сравнение Другими словами, делится и на и на Но различные простые числа, так что Таким образом, лемма из § 3.6 гарантирует нам, что делит А так как мы имеем для любого целого числа Другими словами, Как мы отметили в начале параграфа, этого достаточно для доказательства равенства поскольку обе его части - неотрицательные целые числа, меньшие Подводя итог, можно утверждать, что

алгоритм предыдущего параграфа приводит к практической криптосистеме. Теперь нужно убедиться в ее надежности.

§ 12.4. Почему система надежна?

Напомним, что RSA - система шифрования с открытым ключом, состоящим из произведения различных простых чисел и натурального числа обратимого по модулю Посмотрим внимательно, что можно сделать для взлома RSA, если все, что известно, это пара

Чтобы раскодировать блок, зашифрованный с помощью RSA, мы должны узнать число обратное к по модулю Проблема в том, что практически единственный известный способ сделать это основывается на применении расширенного алгоритма Евклида к Однако для вычисления по формуле из § 9.4 нам нужно знать что подтверждает первоначальное утверждение: взлом RSA требует разложения на множители. А поскольку трудности разложения носят принципиальный характер, система RSA безопасна.

Можно, конечно, предположить, что когда-нибудь кто-нибудь откроет алгоритм, вычисляющий без информации о множителях числа Что, например, произойдет, если некто придумает эффективный способ определения непосредственно по На самом деле, это всего лишь замаскированный способ разложения Точнее говоря, если

известны, то мы с легкостью вычисляем Действительно,

так что сумма искомых простых делителей известна. Далее,

поэтому разность тоже известна. Теперь, решая простую систему линейных уравнений, легко наг ходим разложение на множители.

Значит, алгоритм, вычисляющий фактически раскладывает число на множители, так что это одного поля ягодки. Но успокаиваться пока рано. Можно пойти дальше в своих фантазиях и предположить, что кто-то изобрел алгоритм, определяющий непосредственно по Но Так что, если нам известны то мы знаем число, кратное Оказывается, такой информации тоже достаточно для разложения Вероятностный алгоритм, приводящий к такому разложению, можно найти в . В упражнении 7 приведен похожий (но более простой) алгоритм разложения в предположении, что криптосистему Рабина можно взломать. Он даст вам представление о вероятностном алгоритме из .

Остается последняя возможность для взлома: попытка восстановления блока непосредственно по вычету по модулю Если достаточно большое, то систематический перебор всех возможных кандидатов для поиска единственный выход. Никто еще не придумал ничего лучшего. Мы перечислили основные аргументы, объясняющие, почему взлом RSA-криптосистемы считается равносильным разложению на простые множители, хотя строгого доказательства этого утверждения пока еще нет.

§ 12.5. Выбор простых

Из предыдущего обсуждения вытекает, что для безопасности RSA-криптосистемы важно правильно выбрать простые числа Естественно, если они малы, то система легко взламывается. Однако недостаточно выбрать большие Действительно, даже если р и q огромны, но разность мала, их произведение легко разлагается на множители с помощью алгоритма Ферма (см. § 3.4).

Это не праздный разговор. В 1995 году два студента одного американского университета взломали версию RSA, находящуюся в общественном пользовании. Такое стало возможным из-за плохого выбора простых множителей системы.

С другой стороны, RSA использовалась в течение долгого времени и, если простые сомножители выбраны тщательно, то система в действительности оказывается достаточно надежной. Таким образом, любому программисту системы шифрования RSA необходим эффективный метод удачного выбора простых чисел.

Предположим, мы хотим создать RSA-криптосистему с открытым ключом в котором целое число имеет около знаков. Сначала выберем простое число количество знаков которого лежит между возьмем близким к В настоящее время рекомендованный для персонального использования размер ключа равен 768 битам, т.е. должно приблизительно состоять из 231 цифры. Чтобы построить такое число, нам потребуются два простых, скажем, из 104 и 127 знаков. Обратите внимание на то, что выбранные таким образом простые достаточно далеки друг от друга, т.е. применение алгоритма Ферма для разложения в этой ситуации непрактично. Кроме того, нам нужно удостовериться в том, что в разложении чисел на простые множители участвуют не только малые делители, но и большие. Действительно, в противном случае, число становится легкой добычей для некоторых известных алгоритмов разложения (см. ). Рассмотрим теперь метод, с помощью которого находят простые числа, удовлетворяющие перечисленным условиям.

Сначала нам потребуется один простой результат о распределении простых чисел. Напомним, что обозначает количество простых, не превосходящих х. Учитывая теорему о простых числах, мы видим, что для больших х число приблизительно равно где натуральный логарифм

по основанию (см. § 4.5). Пусть очень большое, какое-то положительное число. Мы хотим оценить количество простых чисел, лежащих между прикинуть разность Благодаря теореме о простых числах и свойствам логарифма, разность приблизительно равна

Предполагая, что очень мало, мы можем считать значение равным 0 и получить разумную оценку разности Итак, число простых, заключенных между приблизительно равно Естественно, оценка тем точнее, чем больше х и меньше Для более подробного знакомства с такой оценкой см. ([Д.10]).

Предположим, что нам нужно выбрать простое число в окрестности целого х. Для определенности будем считать, что х имеет порядок , а простое ищем в интервале от х до Было бы полезно знать заранее, сколько простых чисел находится в этом интервале. Для оценки количества простых можно воспользоваться только что полученным результатом. В нашем примере величина имеет очень маленький порядок: Поэтому по формуле, выписанной выше, мы заключаем, что в интервале между лежит приблизительно

простых числа. В конце второго параграфа главы 11 мы сформулировали стратегию, предназначенную для доказательства простоты данного нечетного числа Она состоит из трех шагов.