RSA – криптографическая система открытого ключа

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

Алгоритм RSA работает следующим образом:

Пусть p и q – два больших различных простых числа, и пусть n = p*q и e некоторое целое, взаимно простое с (p-1)*(q-1).

Оба соответствующих пространства открытых текстов Mk и зашифрованных сообщений Ck суть Zn – множество неотрицательных целых, меньших n. Если подлинное сообщение окажется слишком длинным, чтобы принадлежать Zn, его необходимо разбить на части и зашифровать, используя режим шифрования со сцеплением блоков.

Соответствующая ключу k функция шифрования Ek: Mk -> Ck определяется как Ek(m) = me mod(n). Для того, чтобы полностью определить естественный алгоритм ее вычисления достаточно записать e и n в открытый справочник. Такая пара называется открытым ключом, который легко вычисляется с помощью личного ключа .

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

Эффективный алгоритм вычисления Dk легко получить, задав дополнитель-ную секретную информацию p и q. С этой целью, используя обобщенные алгоритмы Евклида для нахождения наибольшего общего делителя, чтобы вычислить целое число d, такое что e*d = 1 mod ф(n), где ф(n) = (p-1)*(q-1). По известной теореме Эйлера m(e*d) = m mod(n) для каждого целого числа m и, следовательно, (me) d mod(n) = m, при условии что 0 <= m < n, что обеспечивается, когда m принадлежит Mk.

Функция дешифрования Dk: Ck -> Mk в связи с этим определяется как Dk(c) = md mod(n), и эффективный алгоритм для модульного возведения в степень также может быть использован и для ее вычисления. Тогда каждый пользователь криптосистемы RSA должен раз и навсегда выбрать случайно подходящие целые числа p, q и e и вычислить с их помощью d. После чего он делает свой открытый ключ доступным в пользовательском справочнике, тогда как d сохраняет в секрете. Это дает возможность любому другому пользователю шифровать посы-лаемые ему сообщения, которые только он и может расшифровать. Для того чтобы эта идея была реализована практически, решающим является удовлетворение требование, чтобы генерация больших случайных простых чисел и вычисление d были легко осуществимы. Функция дешифрования Dk: Ck -> Mk в связи с этим определяется как Dk(c) = md mod(n), и эффективный алгоритм для модульного возведения в степень также может быть использован и для ее вычисления. Суммируя все сказанное, тогда каждый пользователь криптосистемы RSA должен раз и навсегда выбрать случайно подходящие целые числа p, q и e и вычислить с их помощью d. После чего он делает свой открытый ключ доступным в пользовательском справочнике, тогда как d сохраняет в секрете.

В качестве небольшого примера, пусть p = 19 и q = 23, так что n = 437 и ф(n) = 396. Пусть также e = 13, и поэтому d = 61, так как 13*61 = 793 = 2ф(n)+1. Тогда сообщение в открытом текcте m = 123 будет зашифровано как c = 12313 mod(437) = 386. Действительно, 38661 mod(437) = 123.

Если бы существовали эффективные методы разложения на сомножители (факторинга), то, разложив n на сомножители (факторы) p и q, можно было бы получить секретный (private) ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой практически неразрешимой задаче разложения n на сомножители (то есть на невозможности факторинга n) так как в настоящее время эффективного способа поиска сомножителей не существует.

1.1.1 Описание исходных данных

Исходные данные должны представлять собой выбранный файл с данными меньше 2 Гб, максимальная длина ключа не указанна, но должна соответствовать размеру блока. Секретный ключ для расшифровки вводится в программу через интерфейс при выполнении декодирования файла. Открытый ключ определен в программе.

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

Шифрование:

1 Открываем файл.

2 Загружаем текст файла в контейнер (видимое текстовое поле)

3 Представляем текст как массив символов.

4 Приступаем к просмотру массива

5 Если обработан еще не весь массив, то считывается очередной символ, иначе переход к п.7.

6 Выполняется шифрование символа по алгоритму RSA, после чего закодированный символ записывается в результирующий массив. Переход в п.5.

7 Конец.

Декодирование выполняется аналогичным образом, но требует от пользователя ввода секретного ключа. Также несколько меняется п.6 где раунды кодирование выполняются в обратном порядке, как и сдвиг 32 битных элементов 128 битного блока.

1.1.3 Текст программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

using System.IO;

namespace ZILAB4

{

public partial class Form1 : Form

{

UInt64 p,q,n,f,_e;

private void button2_Click(object sender, EventArgs e)

{

Close();

}

char[] GetChars()

{

return textBox1.Text.ToCharArray();

}

void SetChars(char[] c)

{

textBox1.Clear();

textBox1.Text = new String(c);

}

public Form1()

{

InitializeComponent();

p = 19;

q = 257;

f = (p – 1) * (q – 1);

n = p * q;

_e = 17;//можно безопасно использовать 3;5;17;257;65537 – числа Ферма.

//d=4337;

}

//решение y = x^s mod r

private UInt64 Encryption(uint x, uint s, uint r)

{

bool[] sb = ToBinary(s);

UInt64 i = 0;

UInt64 t = r;

UInt64 n = (ulong)sb.Length;

UInt64 a = 1;

if (sb[i++])

a = x;

UInt64 y = x;

while (i < n)

{

y = ((y * y) % t);

if (sb[i])

a = ((a * y) % t);

i++;

}

return a;

}

private bool[] ToBinary(UInt64 x)

{

UInt64 i = 0;

UInt64 temp = x;

while (temp > 0)

{

i++;

temp >>= 1;

}

bool[] binary = new bool[i];

i = 0;

while (x > 0)

{

if ((x & 1) == 0)

binary[i++] = false;

else

binary[i++] = true;

x >>= 1;

}

return binary;

}

char[] crypt(char[] msg,UInt64 key)

{

char[] res = new char[msg.Length];

for (int i = 0; i < msg.Length; i++)

{

res[i] = (char)Encryption((uint)msg[i],(uint)key,(uint)n);

}

return res;

}

private void button1_Click(object sender, EventArgs e)

{

SetChars(crypt(GetChars(),_e));

}

private void button5_Click(object sender, EventArgs e)

{

SetChars(crypt(GetChars(), Convert.ToUInt64(maskedTextBox1.Text)));

}

private void button3_Click(object sender, EventArgs e)

{

OpenFileDialog OpenFileDialog1 = new OpenFileDialog();

OpenFileDialog1.DefaultExt = “*.rsa”;

OpenFileDialog1.Filter = “RSA Files|*.rsa”;

OpenFileDialog1.InitialDirectory = Application.StartupPath;

if (OpenFileDialog1.ShowDialog() == DialogResult.OK)

textBox1.Text = File.ReadAllText(OpenFileDialog1.FileName, Encoding.Unicode);

}

private void button4_Click(object sender, EventArgs e)

{

SaveFileDialog SaveFileDialog1 = new SaveFileDialog();

// Инициализируем формат файлов в котором они будут сохраняться.

SaveFileDialog1.DefaultExt = “*.rsa”;

SaveFileDialog1.Filter = “RSA Files|*.rsa”;

SaveFileDialog1.InitialDirectory = Application.StartupPath;

if (SaveFileDialog1.ShowDialog() == DialogResult.OK)

File.WriteAllText(SaveFileDialog1.FileName, textBox1.Text,Encoding.Unicode);

}

}

}

1.1.4 Результаты работы программы

Исходный текст криптограммы:

clip_image002

После шифрования:

clip_image004

После расшифровки с вводом правильного секретного ключа:

clip_image006

После расшифровки с вводом не правильного секретного ключа:

clip_image008

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

Заказать Прокат авто с водителем можно тут

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100