Опис використаних систем шифрування

Теоретична частина

Опис використаних систем шифрування

 

1. Афінні шифри вищих порядків.

Подумаємо, як можна розширити монограмні шифри попереднього пункту так, щоб вони оперували з k-грамами для довільного k > 1. Спочатку введемо операцію додавання в Z_n^k. Сумою векторів X = (x₁,. . .,х_k) і s = (s₁,… ,s_k) з Z_n^k є вектор X + S = ((x₁ + s₁) mod n,…, (х_k + s_k) mod n). Z^k_n з операцією додавання є групою. Вектор -S = (n — s₁,…, n — s_k) є оберненим до вектора

S = (s₁,…,s_k).

 

Шифр зсуву  k-го порядку.

Ключ: S є Z^k_n.

Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою Е(Х) = X + S.

Дешифрування. Кожна k-грама X' криптотексту заміщується k-грамою D(X') = X' + 5’, де

S' = -S є дешифруючим ключем.

 

Лінійний шифр k-го порядку.

Ключ: А Є GL_k(Z_n).

Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою Е(Х)= АХ.

Дешифрування. Кожна k-грама Х’ криптотексту заміщується k-грама D(X') = A'X', де

А’ = А^-1 — дешифруючий ключ.

 

Афінний шифр k-го порядку.

Ключ: А Є GL_k{Z_n} і S Є Z_n^k.

Шифрування. Повідомлення розбивається на k-грами. Кожна k-грама X заміщується k-грамою Е(Х) = АХ + S.

Дешифрування. Кожна k-грама X' криптотексту заміщується k-грамою D{X’} = А’X’ + S’, де А’ = А^-1 і S’ = -A’S — дешифруючий ключ.

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Алгоритм RSA

Безпека алгоритму RSA побудована на принципі складності факторизації. Алгоритм використовує два ключі — відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пари ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключем, то розшифрувати його можна тільки відповідним секретним ключем.

Генерація ключів

Для того, щоб згенерувати  пари ключів виконуються такі дії:

1. вибираються два великих простих числа   і 
2. обчислюється їх добуток 
3. обчислюється Функція Ейлера 
4. вибирається ціле   таке, що   та   взаємно просте з 
5. за допомогою розширеного алгоритма Евкліда знаходиться число   таке, що 

Число   називається модулем, а числа   і   — відкритою й секретною експонентами, відповідно. Пари чисел   є відкритою частиною ключа, а   — секретною. Числа   і   після генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті.

Шифрування й  розшифрування

Для того, щоб зашифрувати  повідомлення   обчислюється

.

Число   і використовується в якості шифртексту. Для розшифрування потрібно обчислити

.

Неважко переконатися, що при  розшифруванні ми відновимо вихідне  повідомлення:

З умови

виходить, що

 для деякого цілого  , отже

Згідно з теоремою Ейлера:

,

тому

 

 

Практична частина

 

Завдання №1

Згідно варіанту нам потрібно зашифрувати слово «Хід» Лінійним афінним шифром 1 порядку.

Порядкові номери букв, які  потрібно зашифрувати:

 

Х	І	Д
25	11	5

 

Для зашифрування використаємо наступні ключі:

 

S = 5

 

Формула за шифрування: 

Y1=25+5=30mod33=30 ь

Y2=11+5=16mod33=16 м

Y3=5+5=10mod33=10 и

 

Шифртекст після виконання шифрування:  ьми

 

 

 

 

 

Завдання №2

Згідно варіанту потрібно зашифрувати слово «ТРИ» шифром RSA. При шифруванні потрібно використати наступні ключі: p=3, q=11.

Проведено попереднє зашифрування алгоритмом RSA, та знаходження змінної d для закритого ключа, що використовується в розшифруванні криптотексту.

1. дано: p = 3, q = 11;
2. розрахуємо модуль n = p * q, який буде рівним n = 3 * 11 = 33;
3. розрахуємо phi(n) = (p – 1) * (q – 1), що буде рівним phi(n) = (3 – 1) * (11 – 1) = 20;
4. навмання вибираємо е з кільця цілих чисел 1 < e < phi(n), таке що НСД(e, phi(n)) = 1.

е = 11;

5. отримуємо відкритий ключ (e, n), який дорівнює (11, 33);
6. за допомогою розширеного алгоритму Евкліда знаходимо d:

d = e ^–1 mod phi(n);

d = 11 ^–1 mod 20;

Цілочисельно ділимо phi(n) = 20 на e ^–1 = 11:

            40 = 1 * 11 + 9;

11 = 1 * 9 +2;

9 = 4 * 2 + 1;

2 = 9 * 1 + 0.

 

U_i+1 = U_i-1 -  q_i * U_i

V_i+1 = V_i-1 - q_i * V_i

U₀ = V₁ = 1

V₀ = U₁ = 0

 

i =1           U₂ = U₀ – q₁ * U₁ = 1 – 1 * 0 = 1

                 V₂ = V₀ – q₁ * V₁ = 0 – 1 * 1 = - 1

 

i =2          U₃ = U₁ – q₂ * U₂ = 0 – 1 * 1 = - 1

                V₃ = V₁ – q₂ * V₂ = 1 – 1 * (-1) = 2

 

i =3         U₄ = U₂ – q₃ * U₃ = 1 – 4 * (-1) = 5

                V₄ = V₂ – q₃ * V₃ = 1 – 4 * 2 = - 7

        

Отже, наше d буде дорівнювати останній елемент V₄ mod 40, тобто -7 mod 20 = 13.

7. отримуємо закритий ключ (d, n), який дорівнює (13, 33).
8. Далі проводиться зашифрування слова. Згідно нашого варіанту потрібно зашифрувати слово «ТРИ»

 

 

Порядкові номери букв, які  потрібно зашифрувати:

 

Т	Р	И
22	20	10

 

 

 

C₁ = 22¹¹ mod 33 = 22

11 → 1011

l= 3

i = 1,4             z₀ = 1

i = 1                z₁ = z₁* z₁ * X mod 33 = 1* 1 * 22 mod 33 =22

i = 2                z₂ = z₁* z₁ mod 33 = 22 * 22  mod 33 = 22

i = 3                z₃ = z₁* z₁ * X mod 33 = 22* 22 * 22 mod 33 = 22

i = 4                z₄ = z₁* z₁ * X mod 33 = 22* 22 * 22 mod 33 = 22

 

C₁ = 20¹¹ mod 33 = 20

11 → 1011

l= 3

i = 1,4             z₀ = 1

i = 1                z₁ = z₁* z₁ * X mod 33 = 1* 1 * 20 mod 33 = 20

i = 2                z₂ = z₁* z₁ mod 33 = 20 * 20 mod 33 = 4

i = 3                z₃ = z₁* z₁ * X mod 33 = 4* 4 * 20 mod 33 = 23

i = 4                z₄ = z₁* z₁ * X mod 33 = 23* 23 * 20 mod 33 = 20

 

C₁ = 10¹¹ mod 33 = 10

11 → 1011

l= 3

i = 1,4             z₀ = 1

i = 1                z₁ = z₁* z₁ * X mod 33 = 1* 1 * 10 mod 33 = 10

i = 2                z₂ = z₁* z₁ mod 33 = 10 * 10 mod 33 = 1

i = 3                z₃ = z₁* z₁ * X mod 33 = 1* 1 * 10 mod 33 = 10

i = 4                z₄ = z₁* z₁ * X mod 33 = 10* 10 * 10 mod 33 = 10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Програмна реалізація алгоритмів шифрування

 

Афінний шифр 1 порядку.

Слово, яке потрібно зашифрувати  – «Хід»

Ключі, використані в програмі:

Ключ А(матриця) – 25

Ключ S - 30

Програма шифрує 2 методами:

1. При формуванні шифр тексту використовується Український алфавіт;
2. При формуванні шифр тексту використовується таблиця ASCII.

 

 

Код програми

 

// LiniynuyWufr.cpp : Defines the entry point for the console application.

//

 

#include "stdafx.h"

#include "iostream"

#include <conio.h>

#include <cmath>

#include <windows.h>

 

static int wufrnum[3];  //масив для числових значень шифртексту

static  int  wordnum[3]; //масив для числових значень відкритого тексту

static  int kluchA=25;  //масив ключа

static  int kluchS=30;

static char ASCII[3];

char* alfavit="абвгґдеєжзиiїйклмнопрстуфхцчшщьюя"; //алфавіт включає 33 символи

char* slovo="хiд";  //слово яке потрібно зашифрувати

 

void Ocufrovka() //функція для оцифровування слова

{

 for(int j=0;j<3;j++)

{ 

 for(int i=0;i<33;i++)

{

if(alfavit[i]==slovo[j])

{

 wordnum[j]+=i;

}

}

}

}

 

void Encryption()  //функція для шифрування

{

for(int i=0; i<3; i++)

{

wufrnum[i]=(wordnum[i]*kluchA)+kluchS;

ASCII[i]+=wufrnum[i]%256;

wufrnum[i]=wufrnum[i]%33;

}

}

 

void Vuvedennja()  //функція для виводу на екран

{

std::cout<<"Слово, яке потрiбно зашифрувати -  "<<slovo<<std::endl;

std::cout<<"Ключ шифрування A -  "<<kluchA<<std::endl;

std::cout<<"Ключ шифрування S -  "<<kluchS<<std::endl;

std::cout<<"Порядковий номер букв, якi потрiбно зашифрувати:"<<std::endl<<std::endl;

for(int i=0; i<3; i++)  //Алгоритм виведення на екран порядкового номеру букв

{

std::cout<<slovo[i]<<" - "<<wordnum[i]<<std::endl;

}

 

std::cout<<"\nШифртекст -  ";

for(int i=0;i<3;i++)   //Алгоритм виведення на екран шифртексту

{

std::cout<<alfavit[wufrnum[i]];

}

 

std::cout<<std::endl<<"Шифртекст (ASCII) - ";

for(int i=0;i<3;i++)   //Алгоритм виведення на екран шифртексту (ASCII)

{

std::cout<<ASCII[i];

} 

}

 

 int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "Ukrainian");

Ocufrovka();

Encryption();

Vuvedennja();

std::cin.get();

return 0;

}

 

 

 

Результат виконання програми зашифрування Афінним лінійним шифром 1 порядку

 

           Шифр RSA.

Слово, яке потрібно зашифрувати  – «Код»

Ключі, використані в програмі: p-9; q-15

 

 

 

 

 

                                        Код програми

// rsaSINGLE.cpp : Defines the entry point for the console application.

//

 

#include "stdafx.h"

#include "iostream"//стандартна бібліотека вводу виводу

#include <conio.h>

#include "cmath"//С++ математична бібліотека

 

char* word="код";//Слово, яке потрібно зашифрувати

char* alfavitt="абвгґдеєжзиiїйклмнопрстуфхцчшщьюя";//кириличний алфавіт

long q,p,n,phi;//зміні по формулі

long e;

//=========================================

 long tempArr[4];//

 long temp[3];//масив результатів

 double rozmirByte[2];//масив кількості байт слова

 //=========================================

 

 

long Pow(long num,long n)//перегруження функції піднесення в степінь типом long

{

 

      long res = num;

      for (long i = 1; i < n; i++)

         {

            res *= num;

         }

                 return res;

}

  int Pow(int num,int n)//перегруження функції піднесення в степінь типом int

{

               int res = num;

               for (int i = 1; i < n; i++)

         {

            res *= num;

         }

                 return res;

}

  int Zedn(int a,int b)//функція конюкції(зливання) двох змінних типу int

{      

   int result=0;

       int count=0;

       while (a>10)

       {

               a%=10;

               count++;

       }

   result=a*(Pow(10, count+1)) + b;

       return result;

}

 void FindE()//функція для знаходження найбільшого спільного дільника та числа Е

{

p=9;

q=15;

n=p*q;

phi=n-p-q+1;

            int count=2;//мінімально може бути  два числа бо ділиться на 1 і само себе

 for (int i = 2; i<phi; i++)

                {

                int temp = 0;

                for (int j = 1; j <= i; j++)

                {

                        // Кількість дільників

                        if (i/j*j==i)

                                temp++;

                }

                // Число просте і n на нього не ділиться

                if ((temp < 3) && (phi/i*i < phi))

                {

                        count ++;

                        e=i;//найменше взаємно просте число

break;

                }

                }

}

 

void SearchWord()//функція перетворення символів в числовий тип

{

for(int i=0;i<33;i++)

for(int j=0;j<3;j++)

{

  if(alfavitt[i]==word[j])

tempArr[j]=i;

}

 

}

void Rezalt()//поблокове шифрування

{

double c;

double nlog=std::log(n+0.0)/std::log(2.0);//обчислення розміру n

//std::cout<<nlog<<std::endl;

for (int i = 0; i < 3; i++)

{   

c=0;

c=std::log(tempArr[i]+0.0)/std::log(2+0.0);//обчислення розміру елементів

rozmirByte[i]=c;

}

int b;

for (int i = 0; i < 3; i++)//поблокове шифрування

{

    b =0;

if(rozmirByte[i]&&rozmirByte[i+1]<nlog&&i+1<=2)

{

b=Zedn(tempArr[i],tempArr[i+1]);

    }

else

{

          b=tempArr[i];

}

temp[i]=Pow((long)b,(long)e)%n;

         } 

} 

 

void Vuvid()//виведення на екран

{

setlocale(LC_ALL, "Ukrainian");

std::cout<<"Слово яке потрiбно зашифрувати - "<<word<<std::endl;

std::cout<<"Ключ р = "<<p<<std::endl;

std::cout<<"Ключ q = "<<q<<std::endl;

std::cout<<"n = "<<n<<std::endl;