Применение формул прогонки для шифрования текстовых данных

Пастухов Ю.Ф. под лицензией CC BY 4.0. Чтобы просмотреть копию этой лицензии, посетите

Формулы прогонки с трехдиагональной матрицей в разностных уравнениях наиболее известны в Численных методах [1], [2]. Метод прогонки (трехдиагональный матричный алгоритм) используется в задаче аппроксимации достаточно гладких функций кубическими сплайнами; для решения краевой задачи с обыкновенным дифференциальным уравнением второго порядка и выше; в краевой задаче Дирихле с уравнением в частных производных эллиптического типа (уравнение Пуассона [1]).

В данной работе впервые используется метод трехдиагональной прогонки для шифрования и дешифрования текстовых данных в классах вычетов по простому модулю. В последнее время все более сложные математические методы используются для шифрования текстовой и графической информации. Например, в работах [6], [7], [8], [9], [10], [11], [12], [13], [14], [15].

Постановка задачи

Рассмотрим систему рекуррентных уравнений для решения СЛАУ с трехдиагональной матрицей. Запишем эту систему уравнений в виде [1, стр. 585], предложенном авторами известного учебника Численные методы Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков для решения краевой задачи Дирихле для уравнения Пуассона [1]:

• -    b 0 x 0 + с 0 x 1 = f . , k = ⁰        ______

• -    a k x k - 1 ^- b k x k + ^ck x k + 1 = fk , k = ¹ n ^{- 1} .    (1)

• , a n x n - 1 — b n x n = fn , ^k = n

Если в задаче (1) коэффициенты, прав ы е части и неизвестные a_k,b_k,c_k, f_k,x_k e R , k = 0, n являются действительными числами, то решение системы уравнений (1) известно: [1], [2]

^xk = fak + 1 ^{+ v} k , ^k = ⁰, ^{n — 1} . ⁽²⁾

Коэффициенты прогонки с индексом k=0 вычисляем по формуле (3) [1]:

x = £2x1__fo2 C0 v = -Jx x 0       1     ^ A0 J ,V 0    J b0             b0        b0

.

В формуле (2) коэффициенты прогонки вперед [1] имеют вид

A k = (  , c^k

( a A — 1

—i

—

^{, V} k =~^{f k}T ^{a V} l - ^L\ ’ ^{k =} n n - ¹ . ⁽⁴⁾

^b k )       ( a k ^A k — 1 ^— bk )

Наконец, значение переменной xn  на правом конце находим по формуле (5) [1]:

x = fn - anVn—1 n n n —1     n

.

Зная x_n , коэффициенты A , v , k = 0, n — 1 , вычисляем остальные неизвестные по обратному циклу с понижением индекса по формуле (6) [1]:

x k = ^{A x} + 1 + ^v k , ^k = ^{n —} 1,° .         ⁽⁶⁾

В литературе [1], [2] формулы (3), (4) называют формулами прогонки вперед , а формулы (5), (6) формулами прогонки назад.

Рассмотрим решение задачи (1) на множестве целочисленных остатков ak,bk,Ck, fk,xk e {1,2,..., p — 1}(modp), k = 0,n

по модулю простого числа p

^- b 0 x 0 + с 0 x i = f . (mod p \  k = ⁰

a k x k - 1 ^- b k x k + ^c k x k + 1 = fk ( mod p )   ,   ;-----;

1                    г         \         , k = 1, n - 1 . (7)

a n x n - 1 ^- b n x n = ^f _n ( mod P ) ,  ^k = ⁿ

. a k , b k , ^c k , fk , x k ^{E{ 0,1,2,}...^, P ^{- 1 }}

Необходимость выбора простого числа p в задаче (7) связано со свойствами делимости целых чисел [3], [4].

Пусть[3] числа a , x , m e Z целые, тогда справедлива

Теорема 1 [3, стр.19]. Для того чтобы сравнение ax = 1(mod m ) имело решение, необходимо и достаточно, чтобы a было взаимно просто с m .

Следствие 1 . Каждый примитивный класс вычетов a( НОД ( a , m ) = 1 ) по ( mod m ) имеет ровно один обратный класс x: ax = 1(mod m ) [3, стр. 19].

Следствие 2. Пусть m = p - простое число. Тогда для любого целого остатка числа p a = { 1,2,..., m - 1 } (mod p ) существует единственный остаток – решение уравнения ax = 1(mod p ) .

Доказательство. Так как каждый остаток a = {1,2,..., p - 1}(modp) взаимно прост с простым числом p, то есть принадлежит примитивному классу вычетов, то по Теореме 1 решение x сравнения ax = 1(mod p) существу- ет, а по Следствию 1 класс, которому принадлежит число x, единственный (возможно и совпадение классов, например, для остатков a = x = 1(modp): 1 -1 = 1 = 1(modp)). Следствие 2 из Теоремы 1 доказано.

Теперь формулы прогонки вперед аналогично (3), (4) перепишем в виде

A) = с 0 b 0 ^{- 1 ( mod} p X ^v 0 =^{- f} . b 01 ^{( mod} p ) ,

Ak = - ck(af-.-1 - bk)-1(mod p \ vk =(fk - akvk-1)(ak^k-1 - bk)-1(mod p),k = 1, n -1

А формулы прогонки назад из формул (5), (6) примут вид xn = (fn - anVn-1 Xan^n-1 - bn )-1 (modp),        (10)

x_k - 1 = A - 1 x_k + v _k - 1 ( mod p ) k = n - 1,0 .          (11)

Сформулируем достаточные условия разрешимости задачи (7) и корректности алгоритма (8)–(11) в виде Теоремы 2.

Теорема 2 (достаточные условия корректности алгоритма (8)–(11)).

Пусть в задаче (7), алгоритме (8)–(11) выполнены условия на коэффициенты:

• 1)        b 0 = c 0 ( mod p ), c 0 e { 1,2,..., p - 1 } ;

• 2)     b_k = a _k + c _k ( mod p ), c _k e { 1,2,..., p - 1 }, k = 1, n ;

диагональный элемент матрицы коэффициентов системы (7) сравним с суммой недиагональных элементов строки по (mod p).

Тогда:

• 1.    A = 1 ( mod p ), k = 0, n - 1 .

• 2.    Задача (7) имеет единственное решение в классах вычетов по простому модулю p, а алгоритм (8)–(11) корректен.

Доказательство Теоремы 2 проведем по индукции.

• 1.    a) База индукции k = 0 . Так как по условию 1) Теоремы 1 c ₀ = b ₀ ( mod p ) число A в формуле (8)

• 2.    Используя доказанную первую часть, проверим корректность формул (8): V ₀ = - f 1 b - ( mod p ) = - f 1 c ₀¹ ( mod p )    существует,

A = с ₀ b - ¹ ( mod p ) = с ₀ с ₀¹ ( mod p ) = 1 ( mod p ) .

b) Инду ктив ный переход. Пусть A = 1(mod p ), k = 1, s - 1 . Тогда в первой формуле (9) с учетом условия 2) Теоремы 2

b_k = a_k + c_k ( mod p ) ^ c_k = b_k - a_k ( mod p ) k = 1, n ^A =^{- c} s ( ^{a A} - 1 ^{- b} s ^)- 1 ^{( mod} p ) = ^c s ⁽ b s ^- a _s f - 1 ^)- 1 ^{( mod} p ) »

As = cs (bs - as )-1 (mod p) = cs (cs )-1 (mod p) = 1(mod p).

Индуктивный переход и часть 1 Теоремы 2 доказана.

так как по условию 1) Теоремы 2 c ₀ e { 1,2,..., p - 1 } и (по следствию 2 Теоремы 1) существуют числа c - ¹ и v = - fc - 1 ( mod p ) . Поэтому формула (8) корректна. Аналогично в формуле (9):

^v k = ⁽ fk ^{- a}k ^v k - 1 X a A - 1 ^- bk ^)- ‘ ^{( mod} p\ ^k = 1, ^{n - 1} » ^v k = ^{( a}k ^v k - 1 ^{- f}k \^bk ^{- a}k A - 1 ) - ‘ ^{( mod} p ) »

vk =(akvk-1 - fk )(bk - ak )-1(modp) « vk =(ak Vk-1 - fk Xck)-1 (mod p).

Последняя формула корректна, так как существует число (ск )-1, k = 1, n по условию 2) Теоремы 2. Формула (10) эквивалентна формуле xn =(fn - anVn-1 XanA-1 - bn )-1 (modp)^

x n = ⁽ a n ^V n - 1 - ^fn X ^bn - a n ^{)- 1 ( mod} p ) ^

xn = (an Vn-1 - fn )(cn )-1 (modp) , которая корректна по условию 2) Теоремы 2, так как число (сп )-1 существует. То есть, формулы (8)-(11) корректны. Теорема 2 доказана.

Теорема 3 (Необходимые условия корректности алгоритма (8)-(11)).

Модуль шифрования - простое число p .

• 1)   b k - a k ^ k - i * ⁰ ( mo^d P ) »

A -1 * b/A ^'( mod P ), k = 1, n

• 2)    b о e { 1,2,..., p - 1 } .

Доказательство Теоремы 3 разобьем на части.

• 1)    Простота числа p необходима для взаимно-однозначного поиска обратного числа к любому остатку по ( mod p ) . Это следует из Теоремы 1 и ее Следствий 1 и 2.

• 2)    Запишем уравнение (9)

4 ^{- -} c k ^{( а} Л - 1^- b k ^{)- 1 ( mod} p ) .

Вторую часть теоремы докажем от противного. Пусть при некотором индексе k

3 k : A - 1 - b_ka_k ¹ (mod p ), k e 1, n ^ ^{( b}k ^- a k ^A k - 1 ^{)- 0 ( mod} p ) ^ .

Не        существует        числа

(bk - akAk- 4) 1 (mod p) ^ невозможно вычислить коэффициент A - - С (A A-1 - bk )-1 (mod p)  по предыдущему коэффициенту A-1 • Также невозможно правильно определить все последующие коэффициенты цепочки A+1, Ak+2,...

формул прогонки вперед .

• 3)    Условие b e { 1,2,..., p - 1 } следует из Формулы A - с о b o1 ( mod p ) при вычислении коэффициента A • Теорема 3 доказана .

Применим алгоритм (8)-(11) для шифрования текстовых (символьных) данных. Например, восклицательный знак на клавиатуре в таблице ASCII имеет порядковый номер 33 [5]. Рассмотрим примеры.

Пример 1. Текст для шифрования: "Москва - город-герой в Великой Отечественной войне 1941-1945!!!" английским шрифтом (рис. 1.).

-***input text***                                                   А

Moskua — gorod-geroi и Uelikoi Otechestuennoi uoine 1941-1945???

| ***shifrovanie»**

gHF¥ltUU8XK@c=Qz^eQ’KMUvu§l3F3+Ve ^Е?хьй цО

***deshiFrouan ie***

Moskva — gorod-geroi и Uelikoi Otechestuennoi uoine 1941 1945???

Press any key to continue                                          *

Рис. 1. Шифруется текст (пример 1) с ключами с0 = 1,Ьо = 1,n = 64,с0 - Ьд(mod257)

ck = 2k +1 < p = 257, ck e {1,2,..., p -1}, k = 0, n ak = 3k +1;bk - ak + ck(mod257),k = 1,n .

В примере 1 использованы условия 1), 2) Теоремы 2 (ограничения на коэффициенты). Как видно из рис. 1, исходный и дешифрованный тексты посимвольно совпадают.

Пример 2. Текст для шифрования: "Москва - город-герой в Великой Отечественной войне 1941-1945!!!" с другими ключами (рис. 2).

***input text***

loskua - gorod-geroi и Uelikoi Otechestuennoi uoine 19411945???

***shifrouanie***

!!WW||!lgA

$4u7fU! DCACeEh 2^ l^b 4lc KOJdC C J ¥=gMbi ЬЛ FHA "ииэт

***deshiFrouanie***

loskua - gorod-geroi и Uelikoi Otechestuennoi uoine 19411945???

Press any key to continue

Рис. 2. Шифруется текст (пример 2) с ключами с0 = 3, Ьо = 3, n = 64, с0 - bg (mod 257)

c_k = k + 3 <  p = 257, c_k e { 1,2,..., p -1 }, k = 0, n a_k = 13 k + 2; b_k - a_k + c_k ( mod257 ), k = 1, n

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

Пример 3 показывает, что условия Теоремы 2 являются достаточными для корректности алгоритма (8)-(11), но не являются необходимыми. Текст для шифрования: "Смоленск - город-герой в Великой Отечественной войне 1941-1945!!!" (рис. 3.).

***input text***

Smolensk - gorod-geroi и Uelikoi Otechestuennoi uoine 1941-1945!?!

, ***s h if го и an ie ***

ЭвыцЗЭК OuFn$tHw

|ЦтЬЙпииш-14МВПиКэ"е -nq^tfentH^JbmQW^Jfl X ^

***de s hiF ro u an ie ***

(Smolensk - gorod-geroi и Uelikoi Otechestuennoi uoine 1941-1945!!! Press any key to continue

Рис. 3. Шифруется текст (пример 3) с ключами с₀ = 3, bg = 3, n = 64, с₀ - b₀ ( mod 257 )

c_k = 2 k + 3 <  p = 257, c_k e { 1,2,..., p -1 } , k = 0, n a_k = k + 2; b_k = c_k ( mod 257 ), k = 1, n

В примере 3 не выполнено достаточное условие Теоремы 2 b_k - a_k + c_k ( mod p ) k = 1, n . Тем не менее, исходный текст и дешифрованный совпадают.

Программа написана языке C++.

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

#include "stdafx.h"

#include#include int inverse(int x, int p) { int i,y;x=x%p; if(x<0) {x=x+p;}for(i=1 ;i<=p- 1;i++) {if(i*x%p==1) {y=i;return y;}} } int const p=257,n=65,n0=n-1;int main()

{int                                                      j,

a[n+2],b[n+2],c[n+2],nu[n+2],lamda[n+2],f[n+2] ,mas1[n+2], mas2[n+2] ,d1,d2,d3,d4;

char mas[n+2]="Moskva - gorod-geroi v Velikoi Otechestvennoi voine 1941-1945!!!\n";

printf("***input text***\n"); printf("\n");

for(j=0;j<=n;j++){printf("%c",mas[j]);} for(j=0;j <=n0;j++)

{ a[j]=(3*j+1)%p;    c[j]=(2*j+1)%p;

b[j]=(a[j]+c[j])%p;}

b[0]=c[0];printf("\n");

printf("***shifrovanie***\n");

printf("\n");f[0]=(- b[0]*mas[0]+c[0]*mas[1])%p;

if(f[0]<0)

{f[0]=f[0]+p;}for(j=1;j<=n0-1;j++)

{f[j]=(mas[j-1]*a[j]- mas[j]*b[j]+mas[j+1]*c[j])%p;

printf("%c",f[j]);}f[n0]=(mas[n0-

1]*a[n0]-mas[n0]*b[n0])%p;

printf("\n");printf("\n");lamda[0]=(c[0]

*inverse(b[0],p))%p;

nu[0]=(- f[0]*inverse(b[0],p))%p;if(nu[0]<0){nu[0]=nu[0] +p;} printf("***deshifrovanie** *\n");for(j=1 ;j<=n0;j++)

{d3=(b[j]-a[j]*lamda[j-

1])%p;lamda[j]=(c[j]*inverse(d3,p))%p;

d4=(a[j]*nu[j-1]- f[j])%p;if(d4<0) {d4=d4+p;} nu[j]=(d4*inverse(d3,p))%p;}d1=(a[n0]

*lamda[n0-1]-b[n0])%p;

d2=(f[n0]-a[n0]*nu[n0-

1])%p;if(d2<0){d2=d2+p;}mas1[n0]=(d2*invers e(d1,p))%p;

for(j=n0-1;j>=0;j--

) {mas 1[j]=(mas 1[j+1 ]*lamda[j]+nu[j])%p;} for(j=0;j<=n0;j++){printf("%c",mas1[j]);}printf( "\n");}

Основные полученные результаты:

• 1)    Предложен алгоритм шифрования-дешифрования СЛАУ с трехдиагональной матрицей в классах вычетов по простому модулю-формулы (7)-(11).

• 2)    В Теореме 2 доказаны достаточные условия корректности алгоритма (8)-(11).

• 3)    В Теореме 3 доказаны необходимые условия корректности алгоритма (8)-(11).

• 4)    Приведены 3 примера шифрования-дешифрования текстовых данных, поясняющие смысл и условия доказанных теорем.