Алгоритм кодировки RSA

Размещено на http://www.allbest.ru/

Московский Государственный Университет Леса

Кафедра «Прикладная математика»

Курсовая работа по предмету «Системное ПО»

«Алгоритм кодировки RSA»

Москва 2015



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

Реализовать клиент серверное приложение для пересылки закодированной информации. В качестве алгоритма реализовать алгоритм RSA.

Описание программы

Программа написана на языке C++ с использованием библиотеки Qt.

В программе реализовано:

· генерация открытых и секретных ключей;

· возможность выбора кодировать сообщение или нет;

· диалоговое окно ввода порта и адреса сервера;

· вывод закодированного сообщения на стороне сервера.

Алгоритм работы

Пользователь вводит сообщение в поле для ввода и отправляет его нажатием на кнопку “Send”. Если сообщение должно быть закодировано, то нужно отметить поле “Encrypt”, а также сгенерировать секретный и открытый ключи нажатием на кнопку “Generate Keys”. Если ключи не были сгенерированы перед отправкой, то будет выведено сообщение об ошибке. Если же все условия для начала кодировки выполнены, то перед отправкой запуститься алгоритм RSA. Он закодирует сообщение через открытый ключ. После чего оно будет отправлено на сервер, где будет выведено в закодированном виде и отправлено обратно клиенту. На стороне клиента сообщение будет раскодировано, используя секретный ключ, и выведено на экран.



Алгоритм создания открытого и секретного ключей

RSA-ключи генерируются следующим образом:

1. Выбираются два различных случайных простых числа и заданного размера (например, 1024 бита каждое).

2. Вычисляется их произведение , которое называется модулем.

3. Вычисляется значение функции Эйлера от числа :

4. Выбирается целое число (), взаимно простое со значением функции . Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма17, 257 или 65537.

· Число называется открытой экспонентой (англ. public exponent)

· Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в .

· Слишком малые значения , например 3, потенциально могут ослабить безопасность схемы RSA.

5. Вычисляется число , мультипликативно обратное к числу по модулю , то есть число, удовлетворяющее сравнению:

· Число называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

6. Пара публикуется в качестве открытого ключа RSA (англ. RSA public key).

7. Пара играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

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

Предположим, Боб хочет послать Алисе сообщение .

Сообщениями являются целые числа в интервале от до , т.е .

Шифрование:

· Взять открытый ключ Алисы

· Взять открытый текст

· Зашифровать сообщение с использованием открытого ключа Алисы:

Расшифрование:

· Принять зашифрованное сообщение

· Взять свой закрытый ключ

· Применить закрытый ключ для расшифрования сообщения:



приложение алгоритм ключ шифрование

Исходный код

clientwindow.h

#ifndef CLIENTWINDOW_H

#define CLIENTWINDOW_H

#include <QMainWindow>

#include <QtNetwork/QAbstractSocket>

#include <QtNetwork/QTcpSocket>

#include <QtCore/QTime>

//#include "startdialog1.h"

//#include "startdialog2.h"

//#include <QWidget>

#define DEFAULT_HOST "127.0.0.1"

#define DEFAULT_PORT 2323

namespace Ui {

class ClientWindow;

}

class ClientWindow: public QMainWindow

{

Q_OBJECT

public:

QString strHost;

quint16 nPort;

ClientWindow(const QString& strHost, quint16 nPort, QWidget* pwgt = 0) ;

~ClientWindow();

void setStrHost(QString str) {strHost = str;}

void setNPort(quint16 value) {nPort = value;}

QString getStrHost() const {return strHost;}

quint16 getNPort() const {return nPort;}

void setDefaultValues();

qint64 encrypt(char ch);

char decrypt(qint64 ch);

private:

Ui::ClientWindow *ui;

quint16 nNextBlockSize;

QTcpSocket *pTcpSocket;

qint64* encrypted;

char* decrypted;

qint64 n;

int e;

int d;

qint64 generateNumber(qint64 n);

qint64 gcd(qint64 a, qint64 b);

private slots:

void slotReadyRead();

void slotError(QAbstractSocket::SocketError);

void slotSendToServer();

void slotConnected();

void slotDisconnected();

void on_disconButton_clicked();

void generateKeys();

};

#endif // CLIENTWINDOW_H

clientwindow.cpp

#include "clientwindow.h"

#include "ui_clientwindow.h"

#include "startdialog1.h"

#include <QMessageBox>

#include <limits.h>

#include <math.h>

#include <ctime>

ClientWindow::ClientWindow(const QString& strHost, quint16 nPort, QWidget* pwgt /*=0*/):

QMainWindow(pwgt),

ui(new Ui::ClientWindow),

nNextBlockSize(0)

{

ui->setupUi(this);

setStrHost(strHost);

setNPort(nPort);

pTcpSocket = new QTcpSocket(this);

pTcpSocket->connectToHost(strHost, nPort);

connect(pTcpSocket, SIGNAL(connected()), SLOT(slotConnected()));

connect(pTcpSocket, SIGNAL(disconnected()), SLOT(slotDisconnected()));

connect(pTcpSocket, SIGNAL(readyRead()), SLOT(slotReadyRead()));

connect(pTcpSocket, SIGNAL(error(QAbstractSocket::SocketError)),

this, SLOT(slotError(QAbstractSocket::SocketError)));

connect(ui->sendButton, SIGNAL(clicked()), SLOT(slotSendToServer()));

connect(ui->generateKeysButton, SIGNAL(clicked()), SLOT(generateKeys()));

//connect(ui->textEdit_2, SIGNAL(pressed()),SLOT(slotSendToServer()));

// font size fix for Ubuntu

QFont _font = font();

_font.setPointSize(8);

setFont(_font);

ui->progressBar->hide();

}

void ClientWindow::slotReadyRead()

{

QDataStream in(pTcpSocket);

in.setVersion(QDataStream::Qt_4_5);

for (;;) {

if (!nNextBlockSize) {

if (pTcpSocket->bytesAvailable() < sizeof(quint16)) {

break;

}

in >> nNextBlockSize;

}

if (pTcpSocket->bytesAvailable() < nNextBlockSize) {

break;

}

QTime time;

QString str;

in >> time >> str;

if (str.contains("/auth/succeed"))

{

ui->textEdit->append(time.toString() + " [Server]: " + '"' + "Client" + '"' + " has connected.");

qDebug() << "!" << ui->textEdit->document()->toPlainText();

setWindowOpacity(1);

ui->sendButton->setFocus();

}

else if (str.contains("/auth/failed"))

{

}

else if (str.contains("/disc/"))

{

pTcpSocket->disconnectFromHost();

}

else if (str.contains("/encrypted/"))

{

//str.remove("/encrypted/");

str.clear();

int length;

in >> length;

encrypted = new qint64[length];

int i = 0;

ui->progressBar->show();

ui->progressBar->setRange(0, length);

while (!in.atEnd()) {

in >> encrypted[i];

str.append(QChar(decrypt(encrypted[i])));

ui->progressBar->setValue(i);

i++;

}

ui->progressBar->hide();

delete[] encrypted;

ui->textEdit->append(time.toString() + " [Server]: [DECRYPTION] " + str);

}

nNextBlockSize = 0;

}

}

void ClientWindow::slotError(QAbstractSocket::SocketError err)

{

QString strError =

"Error: " + (err == QAbstractSocket::HostNotFoundError ?

"The host was not found.":

err == QAbstractSocket::RemoteHostClosedError ?

"The remote host is closed.":

err == QAbstractSocket::ConnectionRefusedError ?

"The connection was refused.":

QString(pTcpSocket->errorString()));

int n = QMessageBox::critical(0,

"Attention", strError + " Try again?", QMessageBox::Yes |

QMessageBox::Cancel);

if (n == QMessageBox::Yes) {

StartDialog1 *sd1 = new StartDialog1;

sd1->show();

close();

}

else if(n == QMessageBox::Cancel){

qDebug() << n;

close();

}

ui->textEdit_2->append(strError);

}

void ClientWindow::slotSendToServer()

{

QString str = ui->textEdit_2->document()->toPlainText();

if (str.isEmpty()) return;

if (ui->encryptCheckBox->isChecked()) {

if (!n || ui->publicKeyLineEdit->text().isEmpty() || ui->secretKeyLineEdit->text().isEmpty()) {

QString strError;

strError = QString("You must generate keys first if you want to encrypt the message. Press the \"") +

QString("Generate Keys\" button or toogle off the \"Encrypt\" check box.");

int n = QMessageBox::critical(0, "Attention", strError, QMessageBox::Yes);

if (n == QMessageBox::Yes) {

return;

}

else if(n == QMessageBox::Cancel){

return;

}

ui->textEdit->append(QTime::currentTime().toString() + "[ERROR]: " + strError);

}

}

QByteArray arrBlock;

QDataStream out(&arrBlock, QIODevice::WriteOnly);

out.setVersion(QDataStream::Qt_4_5);

out << quint16(0) << QTime::currentTime();

QTextStream stream(&str);

char ch;

//out << str.length();

if (ui->encryptCheckBox->isChecked()) {

out << QString("/encrypted/");

out << str.length();

encrypted = new qint64[str.length()];

int i = 0;

ui->progressBar->show();

ui->progressBar->setRange(0, str.length());

while (!stream.atEnd()) {

stream >> ch;

encrypted[i] = encrypt(ch);

//ch = encoded[0];

out << encrypted[i];

ui->progressBar->setValue(i);

i++;

}

ui->progressBar->hide();

}

else {

out << str;

}

out.device()->seek(0);

out << quint16(arrBlock.size() - sizeof(quint16));

pTcpSocket->write(arrBlock);

str = QTime::currentTime().toString() + " [Client]: " + ui->textEdit_2->document()->toPlainText();

ui->textEdit->append(str);

ui->textEdit_2->clear();

delete[] encrypted;

}

void ClientWindow::slotConnected()

{

if (pTcpSocket->state() == 0) {

pTcpSocket->connectToHost(getStrHost(), getNPort());

}

qDebug() << "connected";

/*QByteArray arrBlock;

QDataStream out(&arrBlock, QIODevice::WriteOnly);

out.setVersion(QDataStream::Qt_4_5);

out << quint16(0) << QTime::currentTime() << "/auth/";

out.device()->seek(0);

out << quint16(arrBlock.size() - sizeof(quint16));

qDebug() << quint16(arrBlock.size() - sizeof(quint16)) << sizeof(quint16) << sizeof("/auth/");

pTcpSocket->write(arrBlock);*/

}

void ClientWindow::slotDisconnected()

{

}

qint64 ClientWindow::encrypt(char ch)

{

qint64 c = 1;

qint64 code = qint64(ch);

unsigned int i = 0;

while (i < e) {

c = c * code;

c = c % n;

i++;

}

return c;

}

char ClientWindow::decrypt(qint64 ch)

{

qint64 m = 1;

unsigned int i = 0;

while (i < d) {

m = m * ch;

m = m % n;

i++;

}

return char(m);

}

//Алгоритм "решето Сундарама". Выбирает все простые числа

//до заданного (случайно сгенерированного).

qint64 ClientWindow::generateNumber(qint64 n)

{

int *a = new int [n];

qint64 i, j, k;

memset(a, 0, sizeof(int) * n);

for(i = 1; 3*i+1 < n; i++)

{

for(j = 1; (k = i+j+2*i*j) < n && j <= i; j++)

a[k] = 1;

}

//Выбирает из списка простых чисел ближайшее к заданному.

for(i = n-1; i >= 1; i--)

if(a[i] == 0) {

return (2 * i + 1);

break;

}

delete [] a;

}

//Алгоритм Евклида. Алгоритм для нахождения наибольшего

//общего делителя двух целых чисел. Используется для проверки

//чисел на взаимопростоту.

qint64 ClientWindow::gcd(qint64 a, qint64 b)

{

qint64 c;

while (b) {

c = a % b;

a = b;

b = c;

}

return abs(a);

}

void ClientWindow::generateKeys()

{

// Генерация двух чисел и выбор двух простых чисел.

srand( (unsigned)time( NULL ) );

int p = 1 + rand() % 100;

int q = 1 + rand() % 100;

int p_simple = generateNumber(p);

int q_simple = generateNumber(q);

qDebug() << p << p_simple << q << q_simple;

n = p_simple*q_simple;

//Генерация числа e и проверка его на взаимопростоту

//с числом ((p_simple-1)*(q_simple-1)).

int e_simple = 0;

while (e_simple !=1)

{

e = 1 + rand() % 100;

e_simple = gcd (e, ((p_simple-1)*(q_simple-1)));

}

//Определение числа d, для которого является истинным

//соотношение (e*d)%((p_simple-1)*(q_simple-1))=1.

unsigned int d_simple = 0;

d = 0;

while (d_simple !=1)

{

d += 1;

d_simple = (e*d)%((p_simple-1)*(q_simple-1));

}

QString str = "{" + QString::number(e) + ", " + QString::number(n) + "}";

ui->publicKeyLineEdit->setText(str);

str = "{" + QString::number(d) + ", " + QString::number(n) + "}";

ui->secretKeyLineEdit->setText(str);

}

void ClientWindow::setDefaultValues()

{

setStrHost(DEFAULT_HOST);

setNPort(DEFAULT_PORT);

}

ClientWindow::~ClientWindow()

{

delete ui;

}

void ClientWindow::on_disconButton_clicked()

{

QByteArray arrBlock;

QDataStream out(&arrBlock, QIODevice::WriteOnly);

out.setVersion(QDataStream::Qt_4_5);

out << quint16(0) << QTime::currentTime() << "/disc/";

out.device()->seek(0);

out << quint16(arrBlock.size() - sizeof(quint16));

pTcpSocket->write(arrBlock);

QString str;

str = QTime::currentTime().toString() + " [Server]: " + '"' + "Client" + '"' + " has disconnected.";

ui->textEdit->append(str);

StartDialog1 *sd1 = new StartDialog1;

sd1->show();

hide();

//pTcpSocket->disconnectFromHost();

deleteLater();

}

Результаты работы

Размещено на Allbest.ru