Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм шифрування з відкритим ключем RSA.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Основи збору, передавання та обробки інформації
Група:
КС-3
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
кафедра
“Комп’ютеризовані
системи автоматики”
EMBED Word.Picture.8
Звіт
до лабораторної роботи № 3
з дисципліни “Основи збору, передавання та обробки інформації”
на тему:
Алгоритм шифрування з відкритим ключем RSA
Варіант №12
Виконала:
Ст..гр. КС-3
Львів- 2008
Мета роботи: вивчити принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідити числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA.
1. Загальні відомості
2.2.1. Метод справа-наліво двійкового потенціювання.
Цей метод має декілька назв. Інколи його називають алгоритмом двійкових квадратів та добутків, оскільки він реалізується за допо могою цих операції, а інколи і алгоритмом індійського потенціювання. Має назву потенціювання справа-наліво, тому що він перебирає символи вказівника степеню, починаючи з молодшого розряду.
Нехай необхідно обчислити вираз (2.5) зі значенням EMBED Equation.3
EMBED Equation.3 . (2.7)
Представимо число EMBED Equation.3 у вигляді суми степенів 2
EMBED Equation.3 (2.8)
Тепер розпишемо вираз (2.7) з врахуванням розкладу (2.8)
EMBED Equation.3
EMBED Equation.3 . (2.9)
Застосовуючи властивість (2.3), (2.6) до виразу (2.9), отримуємо
EMBED Equation.3 . (2.10)
Такий підхід і називається методом двійкових квадратів та добутків. Мовою С++ цей алгоритм виглядає так:
// обчислення EMBED Equation.3
m = 1;
while (x)
{
if (x&1) m = (m*a) % n;
x = x >> 1;
a = (a*a) % n;
}
2.4.1. Алгоритм Евкліда.
В основі алгоритму лежить повторне ділення із залишком: обчислюємо залишок EMBED Equation.3 , потім EMBED Equation.3 і так далі, поки залишок на стане рівним нулю.
Загальний алгоритм Евкліда обчислення НСД ( EMBED Equation.3 , EMBED Equation.3 ) для EMBED Equation.3
поки ( EMBED Equation.3 )
EMBED Equation.3
EMBED Equation.3 ; EMBED Equation.3
EMBED Equation.3
Мовою С++ цей алгоритм виглядає так:
// обчислення НСД ( EMBED Equation.3 , EMBED Equation.3 )
while (a != 0)
{
temp = b %a;
b = a;
a = temp;
}
nsd = b;
Загальний розширений алгоритм Евкліда
обчислення оберненого значення EMBED Equation.3
EMBED Equation.3
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 ;
поки ( EMBED Equation.3 )
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3
EMBED Equation.3 ; EMBED Equation.3 ; EMBED Equation.3
якщо ( EMBED Equation.3 ) EMBED Equation.3 { EMBED Equation.3 }
Мовою С++ цей алгоритм виглядає так:
// обчислення EMBED Equation.3
// вхід: числа a та n, для яких треба знайти nsd= НСД ( EMBED Equation.3 , EMBED Equation.3 )
long long n1, c, k, nsd, c1, c2, k1, k2, q, r;
n1 = n; //резервуємо значення n
c2 = 1; c1 = 0; k2 = 0; k1 = 1;
while(n != 0)
{
q = a/n; r = a - q*n; c = c2 - q*c1; k = k2 - q*k1;
a = n; n = r; c2 = c1; c1 = c; k2 = k1; k1 = k;
}
nsd = a; c = c2; k = k2;
// якщо аглоритм дав від’ємне значення с, тоді с = с (mod n)
if (c < 0) c += n1;
// вихід: числа nsd, c, k
// с – обернене значення за модулем n
Зауваження: у результаті роботи алгоритму можуть виникати від’ємні числа, і тому усі змінні мають бути знакового типу. Для беззнакових (unsigned) змінних алгоритм буде працювати некоректно! Якщо EMBED Equation.3 = НСД ( EMBED Equation.3 , EMBED Equation.3 ) EMBED Equation.3 , то числа EMBED Equation.3 та EMBED Equation.3 не є взаємно простими.
Завдання
На основі інструментарію Visual C++ 2005 розробити Windows Forms програму CLR для реалізації вказаного проекту алгоритму криптографічної системи з відкритими ключами RSA.
Усі окремі алгоритми (наприклад, обчислення НСД бінарним алго ритмом Евкліда) реалізувати у вигляді підпрограм (функцій).
З метою компактності у завданні вказуються лише номери алгоритмів, на основі яких потрібно реалізувати загальний проект програ ми RSA. Розшифрування номерів подаються тут:
1. Алгоритм піднесення до степеню: 1.1. Метод справа-наліво двійкового потенціювання; 1.2. Метод зліва-направо двійкового потенціювання; 1.3. Рекурсивний метод двійкового потенцію вання; 1.4. Метод вікна; 1.5. Метод змінного вікна.
2. Обч. найбільшого спільного дільника: 2.1. Алгоритм Евклі да; 2.2. Бінарний алгоритм Евкліда.
3. Обч. оберненого значення за модулем: 3.1. Розширений ал горитм Евкліда; 3.2. Розширений бінарний алгоритм Евкліда.
4. Тести визначення простоти числа: 4.1. Тест Рабіна-Мілера; 4.2. Тест Соловея-Штрасена; 4.3. Тест Лемана.
Кількість EMBED Equation.3 повторів імовірнісних тестів на простоту виз нача ється із заданої похибки EMBED Equation.3 .
Для злому системи RSA дається файл із зашифрованими даними, де дані для підбору секретного ключа вказані у назві файлу, наприклад, назва файлу:
#1 E=958391433 n=2505437719.txt.rsa
звідси відкритий ключ E=958391433, основа n=2505437719.
файл: #18
Алг: 1.1; 2.1; 3.1
Список ідентифікаторів,констант, змінних, функцій, методів, використаних у програмі.
unsigned long long- безнако вий цілочисель ний тип даних;
Е-відкритий ключ;
D-cекретнийий ключ;
Блок try { } catch { } – це механізм обробки виключних ситуацій.
static_cast-ключове слово;
c,k,q,r,p-цілі числа;
nsd- найбільший спільний дільник;
Основна програма
#pragma endregion
unsigned long long Inverse(unsigned long long a,unsigned long long n)
{
long long n1,c,k,nsd,c1,c2,k1,k2,q,r;
n1=n;
c2=1;c1=0;k2=0;k1=1;
while(n!=0)
{
q=a/n;r=a-q*n;c=c2-q*c1;k=k2-q*k1;
a=n;n=r;c2=c1;c1=c;k2=k1;k1=k;
}
nsd=a;c=c2;k=k2;
if(c<0) c+=n1;
return c;
}
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) {
unsigned long long p,q,n,E,D,i=3;
E=Convert::ToUInt64(textBox1->Text);
n=Convert::ToUInt64(textBox2->Text);
while(i<=n)
{
if(n%i==0)break;
i+=2;
}
p=i;q=n/p;
D=Inverse(E,(p-1)*(q-1));
textBox3->Text=p.ToString();
textBox4->Text=q.ToString();
textBox5->Text=D.ToString();
}
unsigned long long StepMOD(unsigned long long a,unsigned long long x,unsigned long long n)
{
unsigned long long m=1;
while(x)
{
if(x&1)m=(m*a)%n;
x=x>>1;
a=(a*a)%n;
}
return m;
}
private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) {
String^filename;
unsigned char p;
unsigned int c1;
unsigned long long m,c,n,D;
n=Convert::ToUInt64(textBox3->Text);
D=Convert::ToUInt64(textBox5->Text);
openFileDialog1->ShowDialog();
filename=openFileDialog1->FileName;
BinaryReader^ binReader=gcnew BinaryReader(File::Open(filename,FileMode::Open));
BinaryWriter^ binWriter=gcnew BinaryWriter(File::Open(filename->Replace(".rsa",""),FileMode::Create));
try
{
do
{
c1=binReader->ReadUInt32();
c=static_cast<unsigned long long>(c1);
m=StepMOD(c,D,n);
p=static_cast<unsigned char>(m);
binWriter->Write(p);
}
while(1);
}
catch(...){}
binReader->Close();
binWriter->Close();
}
};
}
Результат програми
Прості числа
p=51647
q=38447
Відкритий ключ
E=448985331
Секретний ключ
D=480245047
Основа
n=1985672209
Висновок: вивчила принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідила числові алгоритми, що використовуються у криптографії та реалізувала алгоритмічною мовою С++ алгоритм шифрування RSA.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора