logo search
Коды и шифры

Процессы зашифрования и расшифрования в системе rsa

Для зашифрования сообщения по методу RSA предполагаемому пользователю необходимо знать значение модуля n(=pq) и ключ зашифрования e - эти величины общедоступны. Значения чисел p и q и ключа расшифрования d известны только "хозяину" используемой системы.

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

  1.  преобразовать буквы сообщения в числа подобно тому, как это показано в таблице 1.1, получая, к примеру, A=00, B=01, ..., Z=25;

  2.  если в записи модуля n не более D цифр, разбить числовое представление сообщения на блоки, в каждом из которых не более D цифр; эти блоки обозначим B1,B2, ...;

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

  4.  (BI)e(mod n), I=1,2,... - в результате получаются блоки шифрованного текста C1,C2,...

Шифрованное сообщение записывается C1C2... (в виде последовательности чисел, а не букв).

Процедура расшифрования сообщения в точности та же самая, как и при зашифровании, за исключением того, что теперь преобразуются блоки шифрованного текста CI, а на шаге (4) вместо ключа зашифрования e используется ключ расшифрования d. Из способа получения d следует, что

(CI)d=B,

или, другими словами, происходит восстановление исходного сообщения.

Пример 13.3

Зашифровать по системе RSA сообщение

COMEXATXNOON

при n=3127 и ключе зашифрования e=17.

Зашифрование

Преобразуем текст в числа обычным образом по таблице 1.1. Поскольку значение модуля (3127) записывается с помощью четырех цифр, разобьем текст на пары букв следующим образом:

CO ME XA TX NO ON

0214 1204 2300 1923 1314 1413

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

Итак, наша задача состоит в том, чтобы вычислить значение (0214)17(mod 3127). Везде, где это возможно в модульных вычислениях такого типа, мы для нахождения степеней исходного числа будем последовательно возводить его в квадрат, а затем перемножим значения соответствующих степеней. Поскольку 16=24, то, действуя таким образом, мы почти вычислим необходимую нам степень. Итак, вычислим следующие степени:

(214)2=45796=143127+20182018(mod 3127),

откуда

(214)4(2018)2=4072324=13023127+970970(mod 3127),

и

(214)8(970)2=940900=3003127+28002800(mod 3127),

откуда

(214)16(2800)2=7840000=25073127+611611(mod 3127).

Окончательно получаем

(214)17214611=130754=413127+25472547(mod 3127).

Итак, 0214 при зашифровании переходит в 2547.

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

2547 3064 2831 0063 2027 1928.

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

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

2129=2048+64+16+1=211+26+24+1,

то в ходе вычислений понадобится возвести каждое четырехзначное число в степени 24, 26 и 211 путем последовательного возведения в квадрат с дельнейшим перемножением нужных нам чисел. С использованием метода "последовательного возведения в квадрат" для вычисления 2129-й степени числа понадобится "всего лишь" по 14 операций умножения и деления, в то время как для прямого подсчета "в лоб" их потребуется более 4000. Далее выполнены операции по расшифрованию четвертого четырехзначного блока из приведенного выше шифрованного текста (т.е. 0063), чтобы продемонстрировать , как именно выполняются подсчеты, и чтобы подтвердить, что в данном случае число 2129 действительно является ключом расшифрования.

Необходимо вычислить значение (63)2129 и найти остаток от его деления на 3127. Из сказанного выше следует, что

(63)2129=(63)2048(63)64(63)16(63)1,

и мы переходим к составлению таблицы степеней числа 63 с показателями 2n до значения n=11 путем последовательного возведения в квадрат. Так как (63)2=3969=3127+842, то в строку таблицы для n=2 мы заносим число 842. Продолжая подобным образом, получаем всю таблицу степеней, которая показана в Таблице 13.1.

Таблица 13.1

n

N=2n

(63)N(mod 3127)

0

1

63

1

2

842

2

4

2262

3

8

872

4

16

523

5

32

1480

6

64

1500

7

128

1687

8

256

399

9

512

2851

10

1024

1128

11

2048

2822

Для вычисления значения (63)2129(mod 3127) теперь перемножаем четыре числа, стоящие в правом столбце напротив значений n=0,4,6 и 11:

(63)21296352315002822.

Поскольку

63523=32949=103127+16791679(mod 3127),

и

15002822=4233000=13533127+21692169(mod 3127),

и наконец,

16792169=3641751=11643127+19231923(mod 3127),

то в результате расшифрования блока 0063 получается значение 1923. Оно преобразуется в пару букв TX, которая на самом деле является четвертым диграфом исходного сообщения.

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