Партнерка на США и Канаду по недвижимости, выплаты в крипто

  • 30% recurring commission
  • Выплаты в USDT
  • Вывод каждую неделю
  • Комиссия до 5 лет за каждого referral

Московский государственный институт электроники и математики

(технический университет)

Кафедра ИКТ

Отчет по лабораторной работе

по дисциплине

“Зашита Информации”

на тему

“Алгоритм шифрования RSA”

Выполнил:

Студент группы с-85

Проверил:

Преподаватель

Москва 2008

Содержание

Техническое задание. 3

Формальное описание шифра. 3

Реализация программы на языке C++. 4

Пример выполнения. 6

Техническое задание

Формально описать и реализовать на языке программирования C++ алгоритм шифрования RSA.

Формальное описание шифра

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

Генерация ключей

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

Выбираются два больших случайных простых числа p\,и q\, Вычисляется их произведение n=pq \, Вычисляется Функция Эйлера \varphi(n)=(p-1)(q-1) Выбирается целое e\,такое, что 1<e<\varphi(n)и e\,взаимно простое с \varphi(n) С помощью расширенного алгоритма Евклида находится число d\,такое, что ed\equiv 1\pmod{\varphi(n)}это значит, что de = 1 + k\varphi(n)\,при некотором целом k\,.

Число n\, называется модулем, а числа e\,и d\,— открытой и секретной экспонентами, соответственно. Пара чисел (n,\,e)является открытой частью ключа, а d\,— секретной. Числа p\,и q\,после генерации пары ключей могут быть уничтожены, но ни в коем случае не должны быть раскрыты.

Шифрование и расшифровывание

Для того, чтобы зашифровать сообщение m<n\,вычисляется

НЕ нашли? Не то? Что вы ищете?

c=m^e\bmod\,n \,.

Число c\, и используется в качестве шифртекста. Для расшифровывания нужно вычислить

m=c^d\bmod\,n \,.

Нетрудно убедиться, что при расшифровывании мы восстановим исходное сообщение:

c^d\equiv (m^e)^d\equiv m^{ed}\pmod n\,

Из условия

ed\equiv 1\pmod{\varphi(n)}

следует, что

ed=k\varphi(n)+1для некоторого целого k\,, следовательно

m^{ed}\equiv m^{k\varphi(n)+1}\pmod n

Согласно теореме Эйлера:

m^{\varphi(n)}\equiv 1\pmod n,

поэтому

m^{k\varphi(n)+1}\equiv m \pmod n

c^d\equiv m\pmod n\,

Реализация программы на языке C++

#include "stdafx. h"

#include <stdio. h>

#include <stdlib. h>

#include <time. h>

#include <conio. h>

#include <iostream>

using namespace std;

struct rsa_public_key {

int e, m;

};

struct rsa_private_key {

int d, m;

};

// Нахождение общего делителя

int gcd(int a, int b)

{

if (b == 0)

return a;

else

return gcd(b, a % b);

}

// Решение Диофантова уравнения a*x + b*y = 1

void SolveDiophant(int a, int b, int &x, int &y)

{

int a11=1, a12=0, a21=0, a22=1;

while (1) {

int r = a % b;

if (r == 0) {

x = a12;

y = a22;

return;

}

else {

int q = a/b;

int save12 = a12;

int save22 = a22;

a12 = a11-save12*q;

a22 = a21-save22*q;

a11 = save12;

a21 = save22;

a = b;

b = r;

}

}

}

// Поиск числа y, такого что (x*y)%m == 1

int FindInvert(int x, int m)

{

int y, sux;

SolveDiophant(x, m, y, sux);

while (y < 0)

y += m;

return y;

}

// вычисление (a в степени b)%m

int Power(int a, int b, int m)

{

a %= m;

int res = a;

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

res = (res * a) % m;

return res;

}

// Генерируем пару ключей.

// GCD(e, p-1) = GCD(e, q-1) = 1

void GenKeyPair(int p, int q, int e, rsa_public_key &pub,

rsa_private_key &pri)

{

if ((gcd(e, p-1) != 1) || (gcd(e, q-1) != 1)) {

printf("GenerateKeyPair: Invalid parameters\n");

exit(1);

}

pub. m = p*q;

pub. e = e;

pri. m = p*q;

// Функция Эйлера phi(m)

int phi_m = (p-1)*(q-1);

pri. d = FindInvert(e, phi_m);

}

// Сообщение должно быть < key. m

int Encode(int source, rsa_public_key &key)

{

return Power(source, key. e, key. m);

}

int Decode(int source, rsa_private_key &key)

{

return Power(source, key. d, key. m);

}

int main ()

{

setlocale (LC_CTYPE, "Russian_Russia.1251");

int p;

int q;

int e=59;

int vvod;

cout<<"Введите чило P:"<<endl;

cin>>p;

cout<<"Введите чило Q, близкое к P:"<<endl;

cin>>q;

cout<<"Введите сообщение, которое будет закодировано:"<<endl;

cin>>vvod;

rsa_public_key pub_key;

rsa_private_key pri_key;

GenKeyPair(p, q, e, pub_key, pri_key);

srand(time(NULL));

int source = vvod % pub_key. m;

int enc = Encode(source, pub_key);

int dec = Decode(enc, pri_key);

if (dec!= source)

printf("Ошибка! Недостаточно памяти для сообщения\n");

else

printf("Исходное сообщение: %d, Закодированное: %d, Декодированное: %d\n",

source, enc, dec);

printf("Публичный ключ: %d, Секретный ключ: %d",

pub_key. m, pri_key);

getch();

}

Пример выполнения

1. Запуск

2. Ввод начальных данных

3.Ввод сообщения

4.Вывод результатов шифрования.