Что такое асимметричное шифрование.
Суть асимметричного шифрования состоит в использовании различных ключей для шифровки и дешифровки сообщения. При этом один из ключей, называемый открытым (англ. public key) является общедоступным, а другой, называемый личным (англ. private key) хранится в секрете.
Наиболее распространены следующие применения асимметричного шифрования.
1. Шифровка открытым ключом (англ. public key encryption). Вы хотите получать шифрованные сообщения от кого угодно, но так, чтобы никто кроме вас не смог их прочесть. Для этого вы публикуете открытый ключ, который каждый сможет использовать для шифровки сообщений, однако личный ключ, используемый для дешифровки, известен только вам, поэтому никто другой прочесть эти сообщения не сможет.
2. Цифровая подпись (англ. digital signature). Используется для защиты сообщений, программных продуктов и других видов интеллектуальной собственности от несанкционированного изменения. В данном случае, наоборот, личный ключ используется для шифровки, а продукт поставляется с так называемой цифровой подписью, содержащей кроме открытого ключа информацию об авторе продукта. Зачастую подпись является зарегистририванной, так что автор будет распознан без обрашения к информации в подписи. Таким продуктом можно пользоваться, однако после всякого изменения, его придется заново подписывать, что доступно только автору продукта, владеющему необходимым для этого личным ключом. Поэтому продукт, измененный без согласия автора, можно сразу распознать, как неаутентичный.
В настоящее время существует множество разнообразных подходов к асимметричному шифрованию. Алгоритм RSA использует трудность разложения очень большого числа на простые множители, алгоритм DSA основан на сложности вычисления дискретного логарифма, в так называемых эллиптических методах в качестве криптографической операции используется скалярное произведение точки эллиптической кривой на данное целое число, определяемое неким хитрым способом.
Все эти методы основаны на невозможности раскрытия личного ключа за обозримое время, тогда как с увеличением быстродействия компьютеров необозримое время с течением времени становится вполне обозримым, особенно при одновременном использовании нескольких компьютеров с многоядерными процессорами. Другой недостаток асимметричных методов шифрования состоит в том, что они работают медленнее симметричных методов.
В этой статье речь пойдет об одной из первых, но несмотря на это довольно распространенной (если не самой распространенной) системе асимметричного шифрования — системе RSA, применяемой в различных сетевых протоколах, среди которых TLS/SSL (для передачи данных и работе на отдаленных компьютерах), S/MIME (для электронной почты), и реализованном различными библиотеками, включая OpenSSL, Nettle, Bouncy Castle, crypto++, libcrypt, а также для большинства используемых в настоящее время цифровых подписей.
Возникновение криптосистемы RSA
RSA — это начальные буквы его создателей, Рональда Ривеста, Ади Шамира и Леонарда Адлемана Rivest —Shamir—Adleman) сотрудников Массачусетского технологического института (Massachusets Institute of Technology, MIT).
Как рассказывал Адлеман, идея пришла в апреле 1977 года после пасхального седера, где будущие соавторы, как и несколько предшествующих месяцев, обсуждали возможность одностороннего алгоритма, упомянутого в опубликованной годом ранее статье сотрудников Станфордского университета Диффи и Хеллмана [Diffie, W., and Hellman, M. "New directions in cryptography." IEEE Trans. Inform. Theory IT-22, 6 (Nov. 1976), pp. 644-654.], В ту же полночь ему позвонил Ривест и предложил алгоритм, основанный на разложении на множители (англ factorisation) большого числа. Обычно придирчивый Адлеман здесь не усмотрел слабостей и согласился, что взломать систему можно только выполнив разложение на множители, что в те времена считалось практически невыполнимой задачей, требующей нескольких тысяч лет.
В статье, написанной Ривестом, авторы первоначально были указаны в алфавитном порядке, но Адлеман отказался быть в числе соавторов, считая свой вклад незначительным. Позже Ривест переубедил его, но Адлер согласился лишь с условием быть в конце списка после Ривеста и Шамира. В том же порядке указаны инициалы в названии алгоритма. Статья была опубликoвана в феврале следующего 1978 года [R.L Rivest, A. Shamir, L. Adleman. "A method for obtaining digital signatures and public-key cryptosystems." Communications of the ACM, volume 2, issue 2, Feb. 1978, pp 120–126 ].
Позднее оказалось, что к системе, практически идентичной RSA, пришел еще в 1973 году британский математик Клиффорд Кокс (Clifford Cocks), однако его результаты были засекречены вплоть до 1997 года, когда термин RSA прочно утвердился.
Замечу, с трудностью разложения на множители встречались еще несколько веков назад. Знаменитый Пьер Ферма (Pierre de Fermat) был убежден, что все числа вида 2^(2^k)+1, называеные числами Ферма, являются простыми. Действительно, при k=0,1,2,3 и 4 соответствующие числа 3, 5, 17, 257, 65537 являются простыми и жизнь была бы прекрасна, если бы так было для всех значений k. Однако не менее знаменитому Леонарду Эйлеру (Leonhard Euler) в 1732 году без всякого калькулятора или компьютера удалось разложить на множители число 2^(2^5)+1 или 2³²+1=4.294.967.297, которое оказалось равным 641×6.700.417. Досаднее всего то, что простых чисел Ферма, бóльших 2¹⁶+1=65537 (к этому числу мы еще вернемся) до сих пор не обнаружено, о чем криптографам приходится сожалеть.
Книга «Основы науки», написанная 1874 году английским экономистом Вильямом Джевонсом (William Stanley Jevons, "Principles of Science"), содержащит следующее : «Может читатель сказать, какие два числа, умноженные друг нa друга, дадут число 8.616.460.799? Думаю, маловероятно, что кто-либо кроме меня это когда-нибудь узнает.». Упомянутое число, названное числом Джевонса, удалось «взломать» уже в 1880-м году неким Чарльзом Баском (Charles J. Busk). Оно равно 89.681×96.079. В настоящее время Prime Factorization Calculator выполняет разложение на множители числа Джевонса за 0,003 секунды «чистого времени».
Задача RSA-129 (RSA-129 challenge)
Еще до публикации статьи авторов алгоритма, в августе 1977 года в журнале "Scientific American" появилась статья известного популяризатора математики Мартина Гаднера [Martin Gardner, "Mathematical Games. "A new type of cypher that would take millions of years to break" Scientific American, volume 237, no. 2 (August 1977), pp. 120-125], знакомого также русскоязычным читателям благодаря переводам его книг.
В статье Гарднера, с согласия авторов, приводится описание алгоритма и предлагается 100 долларов США первому, кто расшифрует фразу на английском языке, зашифрованную следующим 128-значным числом:
9686 9613 7546 2206 1477 1409 2225 4355
8829 0575 9991 1245 7431 9874 6951 2093
0816 2982 2514 5708 3569 3147 6622 8839
8962 8013 3919 9055 1829 9451 5781 5154
Дается открытый код, используемый для кодировки сообщения, состоящий из так называемого открытого показателя степени (aнгл. public exponent) s=9007 (в настоящее время чаще используется буква e) и 129-значного числа r (буква n в настоящее время), равного
114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
Сказано, что число r, позднее получившее название RSA-129, является произведением 64-значного простого числа p и 65-значного простого числа q. Если удастся найти p и q, то, благодаря описанию алгоритма, можно найти секретный показатель степени (англ. secret exponent), число t (буква d в настоящее время), используя который можно узнать закодированную фразу.
В качестве иллюстрации тем же ключом кодируется фраза из 19 букв "ITS ALL GREEK TO ME" (В. Шекспир, «Юлий Цезарь», акт 1, действие 2), Если ее отцифровать, используя двузначные порядковые номера букв в латинском алфавите (01-A, 02-B, 03-C, ..., 26-Z), а также 00 для пробела, получаем следующее 38-значное число (включая ведущий ноль, который можно отбросить): m=09201900011212000718050511002015001305. Возводим это число в открытую степень s (то есть 9007), от полученного огромного числа берем остаток от деления на r (оно же RSA-129), и получаем следующую 128-значную шифровку:
19993513149780510045231712274026064742320401705839146310370371740625971608948927504309920962672582675012893554461353823769748026
Зная секретный показатель t, возводим шифровку в степень t, берем остаток от деления на r и получаем исходное число m, из которого по порядковым номерам букв восстанавливаем закодированную фразу.
В статье Гарднера содержится фраза: «Ривест и его сподвижники не обладают доказательством того, что в никто будущем не найдет быстрый алгоритм, позволяющий разложить на множители такое большое число, как используемое ими r, или взломает шифр другим методом, о котором они не догадываются. Они считают обе возможности весьма отдаленными.»
Решение задачи RSA-129
Несмотря на оптимизм авторов алгоритма, понадобилось менее 17 лет, чтобы решить задачу RSA-129. В апреле 1994 года в новостных группах Интернета появилась радостная заметка о решении задачи, отправленная одним из сотрудников MIT Дереком Аткинсом (Derek Atkins).
Значения p и q оказались равными 3490529510847650949147849619903898133417764638493387843990820577 и 32769132993266709549961988190834461413177642967992942539798288533откуда секретный показатель степени равен 106698614368578024442868771328920154780709906633937862801226224496631063125911774470873340168597462306553968544513277109053606095. Возводим шифровку в секретный показатель степени (любопытно, справится с этим за обозримое время Wolfram Alpha), берем остаток от деления на RSA-129 и получаем 200805001301070903002315180419000118050019172105011309190800151919090618010705, что в буквенном эквиваленте выглядит так:
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
или, говоря по-простому, «Волшебные слова — это брезгливый ягнятник». Для далеких от биологии (коим является и Siempre Su Servidor) скажу, что ягнятник (он же «бородатый стервятник» или «бородач», лат. Gypaetus barbatus, англ. bearded vulture, реже ossifrage ) — это птица из семейства ястребиных. В Британии словом ossifrage иногда обозначают птицу из семейства соколиных (русск. скопа, лат. Pandion haliaetus).
В сообщении указано, что только для процесса отсеивания понадобилось 5000 mips лет. Это значит, что компьютер, выполняющий миллион операций в секунду справился бы с этим за 5000 лет. Тем не менее вычисление заняло только 8 месяцев, благодаря помощи 600 волонтеров из более чем 20 стран со всех континентов, кроме Антарктиды.
Для меня остаются открытыми два вопроса: 1) Kакое отношение к волшебным словам имеет брезгливая птица? С точки зрения криптографии я не вижу в этой фразе нет ничего особенного. Сразу можно заметить, буквы J, К, V и Y в ней отсутствуют. Хотя истинные криптографы меня возможно поправят. 2) Стоило ли тратить столько компьютерных и людских ресурсов ради ничего не значащей фразы за довольно скромное вознаграждение (уверен что стоимость проекта по расшифровке превышает премию во много раз). Замечу, что полученная премия в 100 долларов (она даже не была привязана к индексу цен!) была пожертвована в пользу Free Software Foundation.
Премия была выплачена от имени компании "RSA Security" основанной авторами RSA в 1982 году. Начиная с 1991 года "RSA Security" предлагала премии гораздо большего размера за разложение на множители различных чисел, содержащих от 100 десятичных цифр (RSA-100, 330 бит, премия $1,000US) до 607 десятичных цифр (RSA-2048, 2048 бит, премия $200,000US). Список чисел можно найти в Википедии, где также содержится список лауреатов. Бóльшая часть премий досталась голландскому криптографу Арьену Ленстра (Arjen Lenstra), который также был одним из руководителей проекта расшифровки RSA-129. В 2007 году премии выдавать перестали, но это не остановило публикации о разложении на множители новых чисел. Участие в этом приняли также россияне Данилов, Поповян, Замарашкин, Желтков и Матвеев, но, к сожалению, некоторые из них опоздали получить премию, а за другие числа премия почему-то не была предусмотрена. Остались нефакторизованными числа, содержащие 260 и более цифр (862 и более бит), но сотрудники RSA Security до сих пор хранят тайну их факторизации.
Описание алгоритма RSA
Не могу обойтись без «настоящей» математики. Поэтому попробую (насколько я это понимаю) дать описание алгоритма по нахождению ключей для использования в шифровке и дешифровки криптосистемой RSA, а также доказать правильность выбора ключей.
С точки зрения шифровщика. Дан показатель степени d и модуль n. Требуется зашифровать некоторое число m, которое предполагается меньшим чем √(n)/10. Возводим m в степень d, берем остаток от деления на n и получаем шифровку, которую обозначим через k. Это можно записать равенством: m^d ≡ k mod (n) (1). Такое обозначение (произносится «m^d сравнимо с k по модулю n») означает, что m^d и k дают одинаковые остатки при делении на n, другими словами m^d−k делится на n. Оказывается, сравнение по модулю обладает многими замечательными свойствами, на которых останавливаться не буду. Но даже если вы с ними не знакомы, надеюсь сможете познакомиться по ходу дела.☺
С точки зрения дешифровщика. Дано зашифрованное число k, показатель степени e и модуль n. (Число n одинаково для шифровки и дешифровки.) Возводим k в степень e, берем остаток от деления на n и получаем исходное число m. Таким образом, k^e ≡ m mod(n) (2).
Объединим эти равенства. Возводим равенство (1) в степень е. Получаем: (m^d)^e ≡ k^e mod (n). Правая часть полученного равенства совпадает с левой частью равенства (2). Применяя равенство (2) получаем: (m^d)^e≡ m mod(n), или, перемножая показатели степеней, m^(de)≡ m mod(n) (3).
В зависимости от назначения шифровки, одно из чисел d и e будет секретным показателем, а другое — открытым. Поскольку в равенство (3) эти числа входят симметрично, их можно менять местами. Для определенности, будем считать d секретным. Оно должно быть достаточно большим, чтобы было не так просто отгадать. Наоборот, открытый показатель степени e должен быть сравнительно небольшим, чтобы не удлинять работу большого количества пользователей. Для бóльшего сокращения времени рекомендуется, чтобы двоичное представление e содержало как можно меньше единиц.
Остается «лишь» найти возможность нахождения n, d и e, удовлетворяющих равенству (3) для любого положительного m, меньшего √(n)/10, чтобы зная n и e, нельзя было (в обозримом будущем) вычислить значение d.
Вот метод, применяемый в RSA. Возьмем два достаточно больших простых числа p и q. Эти числа должны быть примерно одинаковой величины, но неодинаковой длины. Как вы помните в задаче RSA-129 числа были 64- и 65-значными. Будем считать, что p<q<100p (4). Выбрав p и q, мы сразу находим n, как их произведение: n=pq (5).
Для нахождения d и e воспользуемся теоремой Эйлера из теории чисел. Пусть 𝜑(n) (функция Эйлера) — количество натуральных чисел меньших n и взаимно простых с n. В данном случае n — произведение двух различных простых чисел p и q, поэтому 𝜑(n)=(p−1)(q−1) . Теорема Эйлера утверждает, что если числа a и n — взаимно простые (то есть их наибольший общий делитель равен 1, HOD(а,n)=1), то a^𝜑(n) ≡1 mod(n).
На самом деле, вместо функции Эйлера, которой изначально пользовались авторы алгоритма, можно использовать функцию Кармайкла (Robert Carmichael), дающую наименьшее число λ(n), обладающее свойством НОД(a,n)=1 ⇒ a^λ(n)≡1 mod(n) (6). В случае произведения двух различных простых чисел p и q, λ(n) — это наименьшее общее кратное p−1 и q−1, то есть λ(n)=НОК(p−1, q−1) (7). Напомню, что для нахождения наименьшего общего кратного можно, применяя алгоритм Евклида, вычислить наибольший общий делитель НОД, и, разделив произведение чисел на НОД, получить, то, что требуется. Чуть длиннее, чем просто перемножить, зато ввиду меньшего значения результата, затрата времени в последствии с лихвой окупится.
Выбираем число e, меньшее λ(n), большее 2 и взаимно простое с λ(n), то есть 2<е<λ(n), НОД(е, λ(n))=1 (8) . В качестве e часто выбирается наибольшее из известных простых чисел Ферма, ранее упомянутое 2¹⁶+1=65537. Это простое число содержит только 2 единицы в двоичном представлении, что, как упоминалось ранее, ускоряет возведение в степень.
Выбираем положительное число d, меньшее λ(n) таким образом, чтобы удовлетворялось равенство: de≡1 mod(λ(n)) (9). О том, как это сделать без перебора, поговорим чуть позже.
Заметим, что не зная р и q, нельзя узнать λ(n), а следовательно число d вычислить не просто, если вообще возможно. Осталось показать, что алгоритм работает, то есть числа d и e действительно удовлетворяют равенству (3).
Для этого запишем равенство (9), как de = cλ(n)+1 (10), где c — некоторое целое число. Поскольку d и λ(n) положительны а число e больше 2, число c также положительно. Отсюда m^(de) = m^(cλ(n)+1) = m^(cλ(n)) × m = (m^λ(n))^c × m (11)
Из (4) и (5) следует, что 100p²>pq=n, откуда √n<10p, следовательно, учитывая (4), √n/10<p<q. Вспомним, что m<√n/10, поэтому m<p<q, и так как p и q — простые числа, число m является взаимно простым с p и q, а следовательно и с n=pq. В таком случае, согласно (6), m^λ(n)≡1 mod(n). Возводя в положительную степень c, находим: (m^λ(n))^c≡1 mod(n). Умножая на m, получаем: (m^λ(n))^c × m≡ m mod(n) (12).
Левая часть (12) — это в точности правая часть (11), равная m^(de). Таким образом m^(de) ≡ m mod(n), что является копией равенства (3). Полный порядок!
В настоящее время для шифровки RSA рекомендуется использовать значения n, содержащие от 1024 до 4096 бит, причем использование 1024-битных чисел не считается достаточно надежным. Также к кодируемой информации (особенно если это обычный буквенный текст) добавляются некоторые символы (англ. padding), не несущие полезной информации, но усложняющие расшифровку .
Советы по выполнению алгоритма RSA
Для выполнения алгоритма можно использовать реализованный в ряде языков программирования класс BigInteger (в некоторых языках BigInt), позволяющий оперировать со сколь угодно большими целыми числами. На языке Python операции с очень большими числами являются встроенными. Вопрос только в быстродействии.
В приведенном выше алгоритме есть несколько медленных мест, которые желательно ускорить.
1) Нахождение больших простых чисел p и q. Доказательство того, что простых чисел бесконечно много, содержится еще в «Началах» Евклида, но их появление не подчиняется какому-либо шаблону. К счастью, наряду с примитивным решетом Эратосфена, есть гораздо более эффективные алгоритмы отсева простых чисел, наиболее популярные из которых приведены в Википедии. Говоря откровенно, я не стал в них вникать, но надеюсь, кому это очень необходимо, способен на всё. 🙂 Можно конечно просто забросить все простые числа необходимого интервала в файл и выбирать их оттуда случайным образом, но насколько большим окажется такой файл, не могу предвидеть.
2) Нахождение d, удовлетворяющего равенству de≡1 mod(λ(n)). Здесь рекомендуется использовать соотношение Безу (Étienne Bézout) о наибольшем общем делителе (не путать с более известной теоремой Безу об остатке деления многочлена), согласно которому для любой пары целых чисел s и t, отличных от нуля, найдутся целые взаимно-простые коэффициенты a и b, называемые коэффициентами Безу, дающие равенство аs+bt=НОД(a,b). Вот и пригодилось требование (8); НОД(е, λ(n))=1, откуда, согласно соотношению Безу, ае+bλ(n) = 1. Далее пишем: ае=1−bλ(n), откуда следует ае≡1 mod(λ(n)). Выходит коэффициент a и есть искомое число d. Найти коэффициенты Безу можно используя расширенный алгоритм Евклида, где частные от деления не отбрасываются, а используются для ведения двух последовательностей, приводящих к коэффициентам Безу.
Здесь есть один нюанс, на который многие почему-то не обращают внимания. Понятно, что поскольку е и λ(n) положительны, коэффициенты Безу а и b должны быть разного знака, иначе |ае+bλ(n)|>1. Где гарантия, что а окажется положительным? К счастью, здесь есть выход. Оказывается, что ввиду очевидного тождества аs+bt=(a+(kt)/u)s+(b−(ks)/u)t, числа (a+(kt)/u и b−(ks)/u, где u=НОД(s,t) (в данном случае это а+kλ(n) и b−ke) также также являются коэффициентами Безу при любом целом k, как положительном, так и отрицательном. Поэтому, если полученное значение a окажется отрицательным, или большим λ(n) (последнее, однако, вряд ли возможно), то можно подобрать число k таким образом, чтобы «вогнать» a в требуемый промежуток.
3) Поскольку значение секретного показателя степени d — гигантское число, возведение в степень d — адские муки даже для компьютера. К счастью, владелец секретного показателя знает также значения p и q, благодаря чему может существенно ускорить возведение в степень d, используя китайскую теорему об остатках (англ "Chinese remainder theorem").
Для этого вначале вычисляются следующие значения: Dp = d mod (p−1) (т.е. остаток от деления на p−1), Dq = d mod (q−1) (аналогично), q' выбирается так что q' q ≡ 1 mod(p) (как это делается, мы уже знаем). Если всегда используется один и тот же личный ключ (чаще всего так и бывает), эти числа можно вычислить раз и навсегда.
Далее, для исходного числа m результат k=m^d mod(pq) находится следующим образом: c₁=m^Dp mod (p), c₂=m^Dq mod(q), h = q' (c₁−c₂) mod (p), k=(c₂ + hq) mod(pq). Как видим, в этом случае показатели степени Dp и Dq меньше p−1 и q−1 соответственно, а следовательно на несколько порядков ниже значения d. Примерно на такой же порядок числа «по модулю» p и q ниже «старого модуля» n=pq. И хотя здесь вместо одного возведения в степень d участвуют два возведения в степень Dp и Dq, все равно так быстрее примерно в три раза.
И это (неужели?) ...
