МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра БІТ
Практична робота № 4 Криптосистема Рабина з навчальної дисципліни: “Прикладна криптологія” Львів – 2011 Завдання Написати програму, яка здійснює шифрування і розшифрування тексту за допомогою криптосистеми Рабина. Теоретичний вступ Криптосистема Рабина - криптографічний алгоритм з відкритим ключем. Її безпека, як і у RSA, пов'язана з труднощами розкладання на множники. Безпека схеми Рабина спирається на складність пошуку квадратних коренів за модулем складеного числа. Складність цього алгоритму аналогічна проблемі розкладання на множники. Головною незручністю практичного застосування криптосистеми Рабина є те, що при розшифруванні тексту виходить чотири різних повідомлення. І треба застосувати додаткові зусилля для знаходження істинного початкового тексту. Блок-схема програми Текст програми using System; using System.Collections; using System.IO; namespace Rabin { class Program { static void Main() { string UA_Alfabet = "абвгґдеєжзиіїйклмнопрстуфхцчшщьюя"; char[] alfavit = UA_Alfabet.ToCharArray(); Console.WriteLine("Введiть фразу для шифрування:"); string vvid = Console.ReadLine(); char[] ch = vvid.ToCharArray(); int[] num = new int[ch.Length]; for (int i = 0; i < ch.Length; i++) { for (int count = 0; count < 33; count++) { if (ch[i] == alfavit[count]) { num[i] = count; break; } } } int p = 0, q = 0; bool perev = false; while (perev == false) { Console.WriteLine("\nВведiть значення р"); p = int.Parse(Console.ReadLine()); perev = ProstiChusla(p); if (perev == true) { if (p % 4 != 3) { Console.WriteLine("Число не рiвне 3 за mod4"); perev = false; } } } perev = false; while (perev == false) { Console.WriteLine("\nВведiть q"); q = int.Parse(Console.ReadLine()); perev = ProstiChusla(q); if (perev == true) { if (q % 4 != 3) { Console.WriteLine("Число не рiвне 3 за mod4"); perev = false; } } } int n = p * q; //Шифрування int[] shufr = new int[num.Length]; for (int y = 0; y < shufr.Length; y++) { shufr[y] = num[y] * num[y]; if (shufr[y] > n) shufr[y] %= n; } //Вивід Console.WriteLine("\nЗашифроване повiдомлення"); for (int t = 0; t < shufr.Length; t++) Console.Write("{0} ", shufr[t]); //Розшифрування int pob, qob; pob = QSD(p, q); qob = QSD(q, p); double[] mp = new double[shufr.Length]; double[] mq = new double[shufr.Length]; double[] r = new double[shufr.Length]; double[] _r = new double[shufr.Length]; double[] s = new double[shufr.Length]; double[] _s = new double[shufr.Length]; for (int v = 0; v < mp.Length; v++) { mq[v] = 1; mp[v] = 1; } for (int y = 0; y < shufr.Length; y++) { for (int z = 0; z < ((p + 1) / 4); z++) { mp[y] *= shufr[y]; mp[y] = modul(mp[y], p); } for (int z = 0; z < ((q + 1) / 4); z++) { mq[y] *= shufr[y]; mq[y] = modul(mq[y], q); } r[y] = (pob * p * mq[y] + qob * q * mp[y]); r[y] = modul(r[y], n); _r[y] = n - r[y]; s[y] = (pob * p * mq[y] - qob * q * mp[y]); s[y] = modul(s[y], n); _s[y] = n - s[y]; } //Вивiд Console.WriteLine("\n\nРозшифроване повiдомлення:"); for (int e = 0; e < r.Length; e++) { if (r[e] < 33) { int temp = (int)r[e]; Console.Write("{0}", alfavit[temp]); } if (_r[e] < 33) { int temp = (int)_r[e]; if (_r[e] != r[e]) { Console.Write("{0}", alfavit[temp]); } } if (s[e] < 33) { int temp = (int)s[e]; if (s[e] != r[e] && s[e] != _r[e]) { Console.Write("{0}", alfavit[temp]); } } if (_s[e] < 33) { int temp = (int)_s[e]; if (_s[e] != r[e] && _s[e] != _r[e] && _s[e] != s[e]) { Console.Write("{0}", alfavit[temp]); } } } Console.Read(); } public static bool ProstiChusla(int x) { int ostacha; for (int i = 2; i < x; i++) { ostacha = x % i; if (x == 2) { Console.WriteLine("число не просте"); return false; } if (ostacha == 0) { Console.WriteLine("число не просте"); return false; } } return true; } public static double modul(double x, int y) { if (x > y) x %= y; while (x < 0) x += y; return x; } public static int QSD(int a, int b) { int x = 0; int _x = 1; int quot, temp, tempx; while (b != 0) { quot = a / b; temp = a; a = b; b = temp % b; tempx = x; x = _x - quot * x; _x = tempx; } return _x; } } } Результат виконання програми
Висновок Під час виконання даної лабораторної робои я ознайомився з криптосистемою Рабина та реалізував програму, що реалізує шифрування та розшифрування введеного тексту.