3.7Пример 2 rsa.

Пояснение:n - это количество возможных чисел. В рассмотренном ранее примере введен алфавит из 33 символов. Каждой букве этого алфавита сопоставляется номер, с которым и производится вычисление. Не очень интересная ситуация, так как каждая буква отдельно шифруется так же, как и в алгоритмах замены! Рассмотрим более интересный случай. Пусть дан алфавит, состоящий из трех символов «ABC» (берем небольшой, чтобы легче было посчитать результат). Тогда код каждой буквы - это число из интервала [0, 2]. Пусть код A=0, B=1, C=2, хотя можно было выбрать совершенно произвольно, так как мы задаем алфавит!

Тогда все возможные сочетания символов в одной позиции дают числа от 0 до 2, то есть всего три варианта. Мы получили троичную систему счисления! Если в этой системе счисления записано «число» из двух позиций, то всех возможных вариантов будет 3*3=9 штук, то есть AA, AB, AC, BA, BB, BC, CA, CB, CC. Надеюсь, что для вас очевидно то, что количество трехзначных чисел в нашей системе счисления равно 3*3*3=9*3=27.

Вернемся к RSA. Если мы хотим работать с указанными ранее ключами, следует разбить исходное сообщение на куски длиной не более n. Если текст разбивается на куски с остатком (наиболее частая ситуация), то поступают следующим образом: дополняют исходный текст заранее оговоренными символами (из заданного алфавита), кроме того, передают длину дополнения.

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

Пусть в алфавите m символов. Тогда мы имеем дело с m – ричной системой счисления, знаки которой – символы алфавита. Так как алфавит – это упорядоченная последовательность символов, то каждому символу однозначно сопоставляется его порядковый номер – количественная характеристика. Причем для левого символа номер будем считать равным 0, далее 1, 2 и т.д. до m-1.

Однозначные (одно символьные) числа в заданной системе счисления – это числа от 0 до m-1. Двузначные – число от 0 до m²-1. Трехзначные - от 0 до m³-1. И т.д. Нам надо определить максимальную степень для основания системы счисления такую, чтобы полученное число оставалось еще меньше n. Можно это рассчитать через log. На картинке ниже эта максимальная степень обозначена через k. Интересен оставшийся фрагмент числовой оси от m^k до n. Это числа, с которыми нам тоже придется работать.

Итак, на рисунке показаны следующие важные области чисел, с которыми нам придется работать в алгоритме RSA. Зеленая область (левая) – это числа от 0 до m^k, где m – основание системы счисления (длина алфавита для передаваемых сообщений), k – количество позиций числа в заданной системе счисления.

Вернемся к задаче выделения фрагмента текста нужной длины. Мы уже знаем, что всегда можно взять k символов. Но иногда можно взять и фрагмент длиной k+1 символ. Как это определить? Это можно сделать двумя способами: а) посчитав количество; б) сравнив две строки.

Вариант а). Рассмотрим сначала первый способ, хотя он и не используется на практике.

У нас сейчас n – это некоторое число. Попробуем представить фрагмент текста тоже в виде числа. Так как мы имеем дело с обычной позиционной системой счисления, то k+1 – значное число = количество = x₀*m⁰+ x₁*m¹+ x₂*m²+… x_k+1*m^k+1. Если это число оказалось больше n (попало в красную зону), то следует взять фрагмент длиной k, то есть число x₀*m⁰+ x₁*m¹+ x₂*m²+… x_k*m^k.

К полученному числу применяем базовый алгоритм возведения в степень. Затем выделяем следующий фрагмент и т.д.

Каждое полученное число следует теперь снова представить в виде строки символов, то есть в виде числа в нашей системе счисления.

Вариант б).

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

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

В соответствии с рассмотренными особенностями дискретного возведения в степень выполним расчет (шифрование – дешифрование) для сообщения ААБВВАААААА. Алфавит «АБВ». N=33, E=3, D=7.

Максимальная степень, в которую можно возвести длину алфавита, оставаясь в интервале чисел от 0 до N, это 3 (3³ = 27 < 33). Это – базовая длина фрагмента (зеленая зона), хотя следует проверять и фрагменты длиной 4 символа с целью выяснения, не попало ли число в желтую зону. Это же можно получить, если представить N в виде строки символов нашего алфавита: N= 33 = 1020₃=БАВА. Таким образом, максимальная длина строки равна 4, хотя и не все 4-х символьные строки окажутся меньше N. Например, строка ББАА больше БАВА. Поэтому гарантированно меньшие числа представлены строками из трех символов.

Первый фрагмент.

ААБВ = В*30+Б*31+А*32+А*33 = 2*30+1*31+0*32+0*33=5

5 < 33, поэтому считаем 5^E mod N = 53 mod 33 = 26

Представляем число 26 в символах нашего алфавита, то есть переводим в троичную систему счисления с заданным набором символов. То есть последовательно делим на 3, записывая остатки и частное от деления. А затем записываем цифры числа снизу вверх, выбирая сначала последнее частное, а затем остатки от деления. Получаем 222. В нашей системе счисления это выглядит как ВВВ.

Второй фрагмент.

ВААА = А*3⁰+А*3¹+А*3²+В*3³ = 0*3⁰+0*3¹+0*3²+2*3³= 54 Теперь 54 > 33, поэтому берем меньший фрагмент: ВАА = А*3⁰+А*3¹+В*3² = 0*3⁰+0*3¹+2*3²= 18. Для него считаем 18^E mod N = 18³ mod 33 = 24. А теперь 24 переводим в нашу систему счисления, получаем 220, то есть получаем ВВА.

Третий фрагмент.

АААА = 0, после возведения в степень тоже 0. А вот теперь перед нами возникла проблема. Как представить 0? Ведь А, АА, ААА, АААА – это все 0. Проблема может быть разрешена только путем введения дополнительного соглашения: к передаваемому тексту всегда должна приписываться еще и длина этого текста. Это не очень хорошо, так как дает злоумышленнику некую информацию. Либо символ с кодом 0 объявляется как специальный и не используется в сообщениях, либо используется только как признак конца.