?

Log in

No account? Create an account
Кое-что по поводу RSA - //L
March 19th, 2007
08:11 pm

[Link]

Previous Entry Share Next Entry
Кое-что по поводу RSA
Лет семь назад разбирался с асимметричными алгоритмами шифрования. В итоге уяснил для себя следующее: в отличие от симметричных, коих существует немеряно, асимметричных алгоритмов есть по-существу только два, один связывают с именами Ривеста, Шамира и Адлемана (надеюсь, я не исказил), другой - Диффи и Хеллмана. Суть второго алгоритма достаточно проста, возможно, именно по этой причине он существует во множестве вариаций на тему. А вот с RSA мне пришлось затратить некоторые усилия.. Разобравшись, и на радостях от этого, я тогда написал текст для одного вновь появившегося интернет-ресурса. Ресурс вскоре благополучно прекратил свое существование, а я, наткнувшись в своих архивах недавно на этот текст, подумал, что он вполне может быть полезен еще кому-то. Например, если этот кто-то тоже захочет вникнуть в суть RSA, не будучи при этом профи ни в крипто, ни в теории чисел. Посему решил выложить его здесь.


Алгоритм RSA.



Приветствие читателя.

Данный текст есть следствие моих поисков в Сети на предмет ознакомления с этим самым алгоритмом. Потратя часть своей драгоценной (для меня) жизни на изучение всяких безумных статей, в конце концов пришел к выводу, что качество материалов свободного доступа в Инете все-таки оставляет желать лучшего. То есть с горем пополам можно было понять - что, но не почему. Призвав на помощь всю свою силу воли и преодолев природное отвращение к перемещениям в пространстве, я сходил в книжный и стал счастливым обладателем довольно толстой книги каких-то Нодена и Китте. Мой скорбный труд был не напрасен - я наконец понял все тайны асимметричного криптоалгоритма RSA! Так что спешу этим всем поделиться. Радуйся: тебе больше не нужно рыскать по сети и открывать толстые и непонятные книги, а достаточно будет прочесть мою мааленькую статейку, и ты тоже будешь знать все.

Вводная.

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

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

Как это бывает.

Ключи: 1-й - (n,a), 2-й - (n,b); n,a,b - целые положительные числа (какие именно, поговорим позже). Текст рубим на куски, не превышающие, если прочесть их как запись целого числа, число n: получаем что-то вроде (t1,t2,...,tm), t1<n, t2<n,..., tm<n. Отправитель сообщения, имеющий на руках число a, возводит каждое из чисел t1,t2,...,tm в степень a, а затем находит остатки от деления t1a,t2a,...,tma на n, получая что-нибудь вроде (u1,u2,...,um), u1<n, u2<n, ..., um<n; и именно это и оказывается в руках получателя. Если составить вместе u1,u2,...,um, получается текст, ничем не напоминающий исходный. (Вообще-то, здесь надо подумать; но это так, за кадром.) Что же делает получатель? А он делает для расшифровки ровно ту же операцию, которую отправитель делал для зашифровки, только вместо (t1,t2,...,tm), которых у него нет, берет (u1,u2,...,um), которые у него есть, а вместо числа a, которого у него нет, берет число b, которое у него есть. И он при этом получит t1,t2,...,tm, из которых был составлен исходный текст!
Надо отметить, что простые числа действительно должны быть большие: чтобы шифр не поддавался взлому, порядок этих чисел (десятичный!) должен быть трехзначным.

Подытоживая вышесказанное.

Основное утверждение (форма1). Если

1) n=p*q - произведение двух простых чисел,

2) остаток от деления a*b на (p-1)*(q-1) равен 1,

3) число t<n, и остаток от деления ta на n равен u,

то остаток от деления ub на n равен t.

Первый шаг.

Меня постоянно будут интересовать не сами числа, а их остатки от деления на что-нибудь, поэтому, дабы подсократить изложение, я буду использовать равенство по модулю: два числа равны по модулю третьего, если их остатки от деления на это третье число одинаковы. Тогда пункт 3) Основного утверждения будет выглядеть так: если ta=u mod(n), то ub=t mod(n). Что переписывается еще короче: (ta)b=t mod(n). Приписка mod(n) как раз и напоминает, что левая и правая части в общем-то не равны, а только имеют одинаковые остатки от деления на n; по-другому - разность левой и правой части, хоть и не обязательно ноль, но обязательно делится на n. А если вспомнить еще немного из школьного курса арифметики: (ta)b=ta*b и заменить ненужные по отдельности a и b их произведением f, то Основное утверждение еще укоротится:

Основное утверждение (Форма2). Если

1) n=p*q - произведение двух простых чисел,

2) f=1 mod((p-1)*(q-1)),

то tf=t mod(n).

Правда же, как-то попроще выглядит?

Второй шаг.

Предлагаю взглянуть повнимательнее на числа 0,1,2,...,n-1, из числа которых взято t (фрагмент шифруемого текста). Взглянуть с благородной целью разложить их по полочкам (трем). Значит, всего этих чисел n. Среди них есть:

А. 0;

Б. числа p, 2*p, 3*p, ..., (q-1)*p и числа q, 2*q, 3*q, ..., (p-1)*q;

В. все остальные числа.

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

Полочка А.

Все ясно без комментариев. Даже и от f ничего требовать не надо.

Полочка В.

Разберемся, сколько на ней чисел. Всего n=p*q, одно число на полке А, (p-1)+(q-1) на полке Б, итого p*q-1-(p-1)-(q-1)=(p-1)*(q-1). Здесь придется сделать первое лирическое отступление.

Лирическое отступление 1.

Цель - убедить тебя, что (p-1)*(q-1)=K*g, где xg=1 mod(n) (вопрос: а на фига?, предлагаю пока отложить). Давай возьмем какое-то из чисел x с полочки В и проследим за тем, что из себя представляют его различные степени. Первое наблюдение, которое ты должен сделать - все они находятся на той же полке. Почему? просто потому, что если число не делится на p или q, то то же самое будет относиться и к любой его степени. Далее, какие-то степени будут равны 1 (я не имею в виду степень 0). Поясняю: всего различных вариантов значений степеней конечное число. Поэтому для каких-то двух различных чисел d1 и d2 будет иметь место соотношение xd1=xd2 mod(n), откуда после сокращения на меньшую из степеней и получается то, о чем я говорил.

Если (бы?) ты был внимателен, то должен задать вопрос: как это я так лихо сокращаю? Ведь не сказано: xd1=xd2, сказано: xd1=xd2 mod(n), то есть xd1=xd2+M*n. После сокращения довесок M*n вполне может уже и не делиться на n. Все так, но n=p*q, а число x взято с полки В, то есть ни на p ни на q не делится, так что на x может сокращаться только M.

Продолжаю: возьмем из равных 1 степеней наименьшую g (но не ноль!). Она (эта степень g) будет обязательно делить (p-1)*(q-1), и это, наверное, самое сложное место. Так что могу порекомендовать сделать перерывчик :).

Взгляни на числа x1=x, x2, ..., xg-1, xg=1 mod(n). Этих чисел ровно g, и все они _различные_: иначе, если бы было xd1=xd2 mod(n), то опять-таки сократив на меньшую степень (насчет сокращений - смотри чуть выше), ты бы мог прийти к выводу, что g все-таки не наименьшая равная 1 степень x. И эти различные числа - это _все_ возможные степени x : xg+1=x mod(n), xg+2=x2 mod(n) и так далее по кругу.

Так. А теперь давай посмотрим на такие наборы чисел:

1*x1, 1*x2, ..., 1*xg;

.............................

z*x1, z*x2, ..., z*xg.

Я подразумеваю, что 1, ..., z - это _все_ числа с полочки В, включая и само x. Самый первый из наборов мы уже рассмотрели, и пришли к выводу, что в нем g чисел, и все они разные. Но то же самое можно сказать и о каждом из этих наборов! Просто проделай те же действия. Замечу также, что любое из чисел с полочки В окажется по крайней мере в одном из наборов. Сказать, что все эти наборы разные, нельзя, очевидно например, что набор

x*x1, x*x2, ..., x*xg

- это просто исходный набор степеней x, только числа местами переставлены. Но! если в двух
наборах есть одинаковые числа, то эти наборы полностью идентичны. Проверяем: если есть два набора

u*x1, u*x2, ..., u*xg

и

v*x1, v*x2, ..., v*xg,

такие, что u*xd1=v*xd2, умножь обе части на xg-d2, тогда в правой части окажется просто v, которое, оказывается, равно u, помноженному на какую-то степень x. Значит, весь второй набор состоит из каких-то степеней x, помноженных на u; причем это _все_ степени x, так как всего чисел в наборе g. Ну так ведь и первый набор ровно такой же!

Выкинем лишние (совпадающие) наборы, и получаем в сухом остатке: имеется несколько (скажем, K) наборов чисел, по g штук в каждом наборе. Все числа в наборах различные, и всего их, значит, не больше, чем есть на полке В. Каждое число с полки В вошло хоть в один набор, значит, в наборах оказались все числа с этой полки. Другими словами, (p-1)*(q-1)=K*g, где xg=1 mod(n). Уффф. Пройдено самое трудное место, конец первому лирическому отступлению.

Итог для полки В.

Теперь поясню, зачем ЭТО было надо. Ведь у нас есть что? f=1 mod((p-1)*(q-1)). Но это значит, что f=1+L*(p-1)(q-1). А тогда xf=x1+L*(p-1)(q-1)=x*xL*(p-1)(q-1)=x*(x(p-1)*(q-1))L=x*(xK*g)L=x*(xg)K*L=x mod(n). А именно это и было нужно (если ты вдруг забыл)!

Полочка Б.

Прояснив ситуацию с полкой В, переходим к полке Б. Ты заметил, что как-то не по порядку :)? f=1+L*(p-1)*(q-1) (это уже было). Зафиксировав, сделаем еще одно лирическое отступление.

Лирическое отступление 2.

cd=c mod(d). Это такая теорема Ферма. Во избежание путаницы ее называют еще малой. Доказывается так: для c=1 все понятно, а если раскрыть скобки в выражении (c+1)d (тоже мне, бином Ньютона :)), то увидим cd+1+..., где все, что обозначено многоточием, делится на d, так что если cd=c mod(d), то (c+1)d=c+1 mod(d), поэтому начиная с 1 утверждение распространяется на все числа (это называется индукция :)). Если еще и d будет простое, то можно сократить на c и записать cd-1=1 mod(d) (вообще-то с сокращениями надо быть осторожным, я про это говорил, но в данном случае все ОК, именно потому, что d - простое).

Итог по полке Б и заключение.

Используем малую теорему Ферма применительно к текущей ситуации. pf-1=pL*(p-1)*(q-1)=(pq-1)L*(p-1), а pq-1=1 mod(q) (ведь q - простое!), значит, pf-1=1 mod(q), а если домножить на p, pf=p mod(q). Последняя запись означает, что pf=p+[что-то]*q. Видно (видно?), что это самое что-то должно делиться на p - потому как q на p не делится. Значит, pf=p+[что-то другое]*p*q. Ну то есть pf=p mod(n) (n=p*q, не забыл?). Теперь ты можешь сделать все то же самое, поменяв p и q местами, получится qf=q mod(n). То есть Основное утверждение выполняется для двух чисел с полочки Б. Но все остальные числа с полки - произведение p, q и числа с полки В. Почему с полки В? больше просто неоткуда. То есть (грубо говоря :)) x*p. Уже проверено, что xf=x mod(n) и pf=p mod(n) (а также qf=q mod(n)). Так что перемножь, и ты увидишь, что и с полкой Б все в порядке.


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

Кстати, из доказательства видно, что вполне себе можно представить RSA с тремя (и даже более) ключами: подбираем a, b, c так, чтобы a*b*c=1 mod ((p-1)*(q-1)), и получаем три ключа. Исходный текст восстанавливается после троекратного применения процедуры. Правда, придумать, зачем бы такое было нужно, мне не удалось :)

(Leave a comment)

Powered by LiveJournal.com