Login lub e-mail Hasło   

Liczby pierwsze - algorytm RSA

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/pr(...)ex.html
W roku 1977 trzej profesorowie z MIT w USA opublikowali nowy rodzaj szyfrowania danych, który nazwano od pierwszych liter ich nazwisk systemem RSA.
Wyświetlenia: 29.681 Zamieszczono 03/11/2006


R.L.Rivest

Adi Shamir

L. Adleman
Twórcy algorytmu RSA

W roku 1977 trzej profesorowie z MIT w USA, Ronald L. Rivest, Adi Shamir i Leonard Adleman, opublikowali nowy rodzaj szyfrowania danych, który nazwano od pierwszych liter ich nazwisk systemem RSA.  Jest to niesymetryczny algorytm szyfrujący, którego zasadniczą cechą są dwa klucze: publiczny do kodowania informacji oraz prywatny do jej odczytywania. Klucz publiczny (można go udostępniać wszystkim zainteresowanym) umożliwia jedynie zaszyfrowanie danych i w żaden sposób nie ułatwia ich odczytania, nie musi więc być chroniony. Dzięki temu firmy dokonujące transakcji poprzez sieć Internet mogą zapewnić swoim klientom poufność i bezpieczeństwo. Drugi klucz (prywatny, przechowywany pod nadzorem) służy do odczytywania informacji zakodowanych przy pomocy pierwszego klucza. Klucz ten nie jest udostępniany publicznie. System RSA umożliwia bezpieczne przesyłanie danych w środowisku, w którym może dochodzić do różnych nadużyć. Bezpieczeństwo oparte jest na trudności rozkładu dużych liczb na czynniki pierwsze.

Załóżmy, iż dysponujemy superszybkim komputerem, który jest w stanie sprawdzić podzielność miliarda dużych liczb w ciągu jednej sekundy. Aby złamać szyfr RSA należy rozbić klucz publiczny na dwie liczby pierwsze będące jego dzielnikami. Znajomość tych liczb pozwala rozszyfrować każdą informację zakodowaną kluczem prywatnym i publicznym.

Brzmi dosyć prosto. Jednakże nie ma prostej metody rozbijania dużych liczb na czynniki pierwsze. Nie istnieje żaden wzór, do którego podstawiamy daną liczbę i w wyniku otrzymujemy wartości jej czynników pierwszych. Należy je znaleźć testując podzielność kolejnych liczb.

Z rozważań o liczbach pierwszych wynika, iż w przypadku dwóch różnych dzielników pierwszych jeden musi leżeć poniżej wartości pierwiastka z danej liczby, a drugi powyżej (dlaczego?). Zatem, aby go znaleźć musimy wyliczyć pierwiastek z rozkładanej liczby, a następnie testować podzielność przez liczby nieparzyste leżące poniżej tego pierwiastka.

Statystycznie poszukiwany czynnik pierwszy powinien znajdować się w górnej połówce zakresu od 2 do pierwiastka z n. Ile działań musimy wykonać? Policzmy.

Klucz 128 bitowy. Pierwiastek jest liczbą 64 bitową. W zakresie od 2 do 264 co druga liczba jest nieparzysta, zatem jest ich około 264 / 2 = 263. Ponieważ interesuje nas tylko górna połówka, to ilość liczb do sprawdzenia jest dwa razy mniejsza, czyli wynosi 263 / 2 = 262. Ile czasu zajmie naszemu superkomputerowi sprawdzenie podzielności przez około 262 liczb, jeśli w ciągu 1 sekundy wykonuje on miliard sprawdzeń? Odpowiedź brzmi:

zajmie to około 262 / 109 = 4611686018 sekund =

= 76861433 minut = 1281023 godzin = 53375 dni = 146 lat

Czy sądzisz, że ktoś będzie czekał przez prawie dwa życia na złamanie szyfru? Zatem można podać do publicznej wiadomości liczbę będącą iloczynem dwóch dużych liczb pierwszych i mieć prawie pewność, iż nikt jej nie rozbije na czynniki pierwsze w rozsądnym czasie. Ostatecznie zamiast 128 bitów możemy zwiększyć klucz do np. 1024 bitów, a wtedy czas łamania szyfru liczy się miliardami miliardów... miliardów lat.

Algorytm RSA składa się z trzech podstawowych kroków:

Fazy algorytmu RSA
I

Generacja klucza publicznego i tajnego. Klucz publiczny jest przekazywany wszystkim zainteresowanym i umożliwia zaszyfrowanie danych. Klucz tajny umożliwia rozszyfrowanie danych zakodowanych kluczem publicznym. Jest trzymany w ścisłej tajemnicy.

II

Użytkownik po otrzymaniu klucza publicznego, np. poprzez sieć Internet, koduje za jego pomocą swoje dane i przesyła je w postaci szyfru RSA do adresata dysponującego kluczem tajnym, np. do banku, firmy komercyjnej, tajnych służb. Klucz publiczny nie musi być chroniony, ponieważ nie umożliwia on rozszyfrowania informacji - proces szyfrowania nie jest odwracalny przy pomocy tego klucza. Zatem nie ma potrzeby jego ochrony i może on być powierzany wszystkim zainteresowanym bez ryzyka złamania kodu.

III Adresat po otrzymaniu zaszyfrowanej wiadomości odczytuje ją za pomocą klucza tajnego.

Generacja klucza publicznego i tajnego dla algorytmu RSA
I

Znajdź dwie duże liczby pierwsze (mające np. po 1024 bity). Oznacz je jako p i q. Istnieją specjalne algorytmy generujące duże liczby pierwsze.

II

Oblicz:
Ø = (p - 1) (q - 1)
oraz
n = p q

Wygenerowane liczby pierwsze usuń, aby nie wpadły w niepowołane ręce. Ø  to tzw. funkcja Eulera, n jest modułem.

III
Wykorzystując odpowiednio algorytm Euklidesa znajdź liczbę e, która jest względnie pierwsza z wyliczoną wartością funkcji Eulera Ø (tzn. NWD(e, Ø) = 1) Liczba ta powinna również spełniać nierówność 1 < e < n . Nie musi ona być pierwsza lecz nieparzysta.
IV

Oblicz liczbę odwrotną modulo Ø  do liczby e, czyli spełniającą równanie d e  mod Ø = 1. Można to zrobić przy pomocy rozszerzonego algorytmu Euklidesa, który umieściliśmy w naszym opracowaniu.

V

Klucz publiczny jest parą liczb (e, n), gdzie e nazywa się publicznym wykładnikiem. Możesz go przekazywać wszystkim zainteresowanym.

VI

Klucz tajny to (d, n), gdzie d nazywa się prywatnym wykładnikiem. Klucz ten należy przechowywać pod ścisłym nadzorem.

p = 13
q = 11

Wybieramy dwie dowolne liczby pierwsze. W naszym przykładzie nie będą one duże, aby nie utrudniać obliczeń. W rzeczywistości liczby te powinny być ogromne.

Ø = 120 Obliczamy Ø = (p - 1) (q - 1) , czyli tzw. funkcję Eulera:
   Ø = (13 - 1) (11 - 1) = 12 10 = 120
n = 143 Obliczamy moduł n:
   n = p q = 13 11 = 143
e = 7 Wyznaczamy wykładnik publiczny e. Ma on być względnie pierwszy z Ø czyli z liczbą 120. Warunek ten spełnia, np. liczba 7.
d = 103 Wyznaczamy następnie wykładnik prywatny, który ma być odwrotnością modulo Ø liczby e, czyli
   d 7 mod 120 = 1.
Liczbą spełniającą ten warunek jest 103
(7,143) Klucz publiczny (e, n)
(103,143) Klucz tajny (d, n)

Szyfrowanie RSA
I Otrzymujesz od adresata klucz publiczny w postaci pary liczb (e, n).
II

Wiadomość do zaszyfrowania zamieniasz na liczby naturalne t, które muszą spełniać nierówność
    0 < t < n
Można tutaj skorzystać np. z łączenia kodów znaków. Oczywiście adresat musi znać użyty przez ciebie sposób przekształcenia tekstu w liczbę, aby mógł on później odtworzyć otrzymaną wiadomość. Zwykle nie ma z tym problemu, ponieważ nadawca i odbiorca stosują wspólne oprogramowanie, które troszczy się za ciebie o takie szczegóły techniczne.

III Na tak otrzymanych liczbach wykonujesz operację szyfrowania i otrzymujesz liczby
    c = t e mod n.
IV

Liczby c są zaszyfrowaną postacią liczb t i przekazuje się je adresatowi wiadomości. Klucz (e, n) umożliwił ich zaszyfrowanie, lecz nie pozwala ich rozszyfrować.

e = 7
n = 143
Otrzymaliśmy klucz publiczny (e, n). Przy jego pomocy możemy zakodować liczby od 0 do 142. Zauważ, iż liczby 0 oraz 1 nie zostaną zakodowane (dlaczego?).
c = 7 Załóżmy, iż chcemy przesłać adresatowi zaszyfrowaną liczbę t = 123. W tym celu musimy obliczyć wartość wyrażenia:
   c = 1237 mod 143 = 425927596977747 mod 143 = 7
Wynik jest zaszyfrowaną liczbą 123. Przesyłamy go do adresata.

Rozszyfrowywanie RSA
I

Jesteś adresatem zaszyfrowanych wiadomości. Wcześniej wszystkim korespondentom przesłałeś wygenerowany klucz publiczny (e,n), za pomocą którego mogą oni szyfrować i przesyłać ci swoje dane. Otrzymujesz więc zaszyfrowaną wiadomość w postaci liczb naturalnych c, które muszą spełniać warunek:
    0 < c < n

II Liczbę c przekształcasz na pierwotną wartość t stosując wzór:
    t = c d mod n
III Z otrzymanej liczby t odtwarzasz wg ustalonego systemu znaki tekstu. Teraz możesz odczytać przesłaną wiadomość.

d = 103
n = 143
c = 7

Otrzymaliśmy zakodowaną wiadomość o wartości 7. Jesteśmy w posiadaniu klucza prywatnego, który służy do rozszyfrowywania wiadomości zakodowanych kluczem publicznym.

t = 123

Wykonujemy następujące operacje:
   t = 7103 mod 143
Potęga jest zbyt duża, aby można ją było w normalny sposób obliczyć (języki programowania mają zwykle ograniczenia co do wielkości liczb całkowitych, np. w Pascalu liczby te nie mogą przekraczać wartości 4294967295). Jednakże nas nie interesuje wartość liczbowa potęgi, a jedynie reszta z dzielenia jej przez 143. Możemy więc rozłożyć potęgę na iloczyn składników o wykładnikach równych kolejnym potęgom liczby dwa:

7103 mod 143 = 764 + 32 + 4 + 2 + 1 mod 143 =
(764 mod 143)
(732 mod 143) (74 mod 143) (72 mod 143) 7 mod 143

71 mod 143 = 7
72 mod 143 = (71 mod 143)2 mod 143 = 49 mod 143 = 49
74 mod 143 = (72 mod 143)2 mod 143 = 492 mod 143 = 113
78 mod 143 = (74 mod 143)2 mod 143 = 1132 mod 143 = 42
716 mod 143 = (78 mod 143)2 mod 143 = 422 mod 143 = 48
732 mod 143 = (716 mod 143)2 mod 143 = 482 mod 143 = 16
764 mod 143 = (732 mod 143)2 mod 143 = 162 mod 143 = 113

Do wyliczenia potęgi bierzemy tylko te reszty, które występują w sumie potęg 2: (jeśli byłoby ich bardzo dużo, to każde mnożenie można wykonać z operacją modulo, dzięki czemu wynik nigdy nie wyjdzie poza wartość modułu)

t = 7103 mod 143 = 113 16 113 49 7 mod 143 = 123

Na podstawie podanych informacji napiszemy prostą aplikację, która pełnić będzie rolę kompletnego systemu szyfrowania RSA. Proces szyfrowania i rozszyfrowywania jest identyczny, różni się tylko rodzajem zastosowanego klucza. Dlatego w aplikacji występują jedynie dwie opcje: tworzenie kluczy RSA oraz szyfrowanie RSA. W pierwszym przypadku program generuje dwa klucze, publiczny oraz prywatny. Należy zapamiętać te dane, gdyż będą one potrzebne w drugiej opcji do szyfrowania lub rozszyfrowywania. Proponujemy zastosowanie tej aplikacji do prostej zabawy w klasie. Tworzymy jedną grupę uczniów, która utworzy klucz publiczny oraz prywatny. Klucz publiczny przekaże reszcie klasy, klucz prywatny zachowa dla siebie. Następnie pozostali uczniowie na podstawie otrzymanych kluczy publicznych mogą kodować swoje dane i przekazywać je pierwszej grupie, która za pomocą klucza prywatnego dokona rozszyfrowania wiadomości.

Życzymy dobrej zabawy.

Wydruk z uruchomionego programu
System szyfrowania danych RSA
-----------------------------
(C)2005 mgr Jerzy Wałaszek

MENU
====
[ 0 ] - Koniec pracy programu
[ 1 ] - Generowanie kluczy RSA
[ 2 ] - Kodowanie RSA

Jaki jest twój wybór? (0, 1 lub 2) :
Generowanie kluczy RSA
----------------------

KLUCZ PUBLICZNY
wykładnik e = 3
moduł n = 391

KLUCZ PRYWATNY
wykładnik d = 235

Zapisz te dane i naciśnij Enter
Kodowanie danych RSA
--------------------

Podaj wykładnik = 3
Podaj moduł = 391
----------------------------------

Podaj kod RSA = 123

Wynik kodowania = 98

Zapisz te dane i naciśnij Enter
Kodowanie danych RSA
--------------------

Podaj wykładnik = 235
Podaj moduł = 391
----------------------------------

Podaj kod RSA = 98

Wynik kodowania = 123

Zapisz te dane i naciśnij Enter
Microsoft Visual Basic 2005 Express Edition

 

Borland
Delphi 7.0
Personal
Edition
{
*******************************************************
** Przykładowa aplikacja obrazująca sposób działania **
** asymetrycznego systemu kodowania informacji RSA. **
** ------------------------------------------------- **
** (C)2003 mgr Jerzy Wałaszek **
** I Liceum Ogólnokształcące **
** im. Kazimierza Brodzińskiego **
** w Tarnowie **
*******************************************************
}


program rsa;

{$APPTYPE CONSOLE}

// Procedura oczekuje na naciśnięcie klawisza Enter
// po czym czyści ekran okna konsoli
//-------------------------------------------------

procedure Czekaj;
var
i : integer;
begin
writeln;
writeln('Zapisz te dane i nacisnij Enter');
readln;
for i := 1 to 500 do writeln;
end;

// Funkcja obliczająca NWD dla dwóch liczb
//----------------------------------------

function nwd(a,b : integer) : integer;
var
t : integer;
begin
while b <> 0 do
begin
t := b;
b := a mod b;
a := t
end;
nwd := a
end;

// Funkcja obliczania odwrotności modulo n
//----------------------------------------


function odwr_mod(a,n : integer) : integer;
var
a0,n0,p0,p1,q,r,t : integer;
begin
p0 := 0; p1 := 1; a0 := a; n0 := n;
q := n0 div a0;
r := n0 mod a0;
while r > 0 do
begin
t := p0 - q * p1;
if t >= 0 then
t := t mod n
else
t := n - ((-t) mod n);
p0 := p1; p1 := t;
n0 := a0; a0 := r;
q := n0 div a0;
r := n0 mod a0;
end;
odwr_mod := p1;
end;

// Procedura generowania kluczy RSA
//---------------------------------

procedure klucze_RSA;
const
tp : array[0..9] of integer =
(11,13,17,19,23,29,31,37,41,43);
var
p,q,phi,n,e,d : integer;
begin
writeln('Generowanie kluczy RSA');
writeln('----------------------');
writeln;

// generujemy dwie różne, losowe liczby pierwsze

repeat
p := tp[random(10)];
q := tp[random(10)];
until p <> q;

phi := (p - 1) * (q - 1);
n := p * q;

// wyznaczamy wykładniki e i d

e := 3;
while nwd(e,phi) <> 1 do inc(e,2);
d := odwr_mod(e,phi);

// gotowe, wypisujemy klucze

writeln('KLUCZ PUBLICZNY');
writeln('wykladnik e = ',e);
writeln(' modul n = ',n);
writeln;
writeln('KLUCZ PRYWATNY');
writeln('wykladnik d = ',d);
Czekaj;
end;

// Funkcja oblicza modulo potęgę podanej liczby
//---------------------------------------------

function pot_mod(a,w,n : integer) : integer;
var
pot,wyn,q : integer;
begin

// wykładnik w rozbieramy na sumę potęg 2. Dla reszt
// niezerowych tworzymy iloczyn potęg a modulo n.

pot := a; wyn := 1; q := w;
while q > 0 do
begin
if (q mod 2) = 1 then wyn := (wyn * pot) mod n;
pot := (pot * pot) mod n; // kolejna potęga
q := q div 2;
end;
pot_mod := wyn;
end;

// Procedura kodowania danych RSA
//-------------------------------


procedure kodowanie_RSA;
var
e,n,t : integer;
begin
writeln('Kodowanie danych RSA');
writeln('--------------------');
writeln;
write('Podaj wykladnik = '); readln(e);
write(' Podaj modul = '); readln(n);
writeln('----------------------------------');
writeln;
write('Podaj kod RSA = '); readln(t);
writeln;
writeln('Wynik kodowania = ',pot_mod(t,e,n));
Czekaj;
end
;

// ********************
// ** Program główny **
// ********************


var
w : integer;

begin
randomize;
repeat
writeln('System szyfrowania danych RSA');
writeln('-----------------------------');
writeln(' (C)2003 mgr Jerzy Walaszek ');
writeln;
writeln('MENU');
writeln('====');
writeln('[ 0 ] - Koniec pracy programu');
writeln('[ 1 ] - Generowanie kluczy RSA');
writeln('[ 2 ] - Kodowanie RSA');
writeln;
write('Jaki jest twoj wybor? (0, 1 lub 2) : ');
readln(w);
writeln; writeln; writeln;
case w of
1 : klucze_RSA;
2 : kodowanie_RSA;
end;
writeln; writeln; writeln;
until w = 0;
end.
Borland
C++ Builder
6.0
Personal
Edition
/*
*******************************************************
** Przykładowa aplikacja obrazująca sposób działania **
** asymetrycznego systemu kodowania informacji RSA. **
** ------------------------------------------------- **
** (C)2003 mgr Jerzy Wałaszek **
** I Liceum Ogólnokształcące **
** im. Kazimierza Brodzińskiego **
** w Tarnowie **
*******************************************************
*/


#include <iostream>
#include <iomanip>


using namespace std;

// Funkcja czeka na dowolny klawisz i czyści ekran
//------------------------------------------------


void czekaj(void)
{
char c[1];

cout << "\nZapisz te dane\n\n";
cin.getline(c,1);
cin.getline(c,1);
for(int i = 1; i < 500; i++) cout << endl;

}

// Funkcja obliczająca NWD dla dwóch liczb
//----------------------------------------

int nwd(int a, int b)
{
int t;

while(b != 0)
{
t = b;
b = a % b;
a = t;
};
return a;
}

// Funkcja obliczania odwrotności modulo n
//----------------------------------------


int odwr_mod(int a, int n)
{
int a0,n0,p0,p1,q,r,t;

p0 = 0; p1 = 1; a0 = a; n0 = n;
q = n0 / a0;
r = n0 % a0;
while(r > 0)
{
t = p0 - q * p1;
if(t >= 0)
t = t % n;
else
t = n - ((-t) % n);
p0 = p1; p1 = t;
n0 = a0; a0 = r;
q = n0 / a0;
r = n0 % a0;
}
return p1;
}

// Procedura generowania kluczy RSA
//---------------------------------


void klucze_RSA()
{
const int tp[10] = {11,13,17,19,23,29,31,37,41,43};
int p,q,phi,n,e,d;

cout << "Generowanie kluczy RSA\n"
"----------------------\n\n";

// generujemy dwie różne, losowe liczby pierwsze

do
{
p = tp[rand() % 10];
q = tp[rand() % 10];
} while (p == q);

phi = (p - 1) * (q - 1);
n = p * q;

// wyznaczamy wykładniki e i d

for(e = 3; nwd(e,phi) != 1; e += 2);
d = odwr_mod(e,phi);

// gotowe, wypisujemy klucze

cout << "KLUCZ PUBLICZNY\n"
"wykladnik e = " << e
<< "\n modul n = " << n
<< "\n\nKLUCZ PRYWATNY\n"
"wykladnik d = " << d << endl;
czekaj();
}

// Funkcja oblicza modulo potęgę podanej liczby
//---------------------------------------------


int pot_mod(int a, int w, int n)
{
int pot,wyn,q;

// wykładnik w rozbieramy na sumę potęg 2
// przy pomocy algorytmu Hornera. Dla reszt
// niezerowych tworzymy iloczyn potęg a modulo n.


pot = a; wyn = 1;
for(q = w; q > 0; q /= 2)
{
if(q % 2) wyn = (wyn * pot) % n;
pot = (pot * pot) % n; // kolejna potęga
}
return wyn;
}

// Procedura kodowania danych RSA
//-------------------------------


void kodowanie_RSA()
{
int e,n,t;

cout << "Kodowanie danych RSA\n"
"--------------------\n\n"
"Podaj wykladnik = "; cin >> e;
cout << " Podaj modul = "; cin >> n;
cout << "----------------------------------\n\n"
"Podaj kod RSA = "; cin >> t;
cout << "\nWynik kodowania = " << pot_mod(t,e,n) << endl;

czekaj();
}

// ********************
// ** Program główny **
// ********************

main()
{
int w;

srand((unsigned)time(NULL));

do
{
cout << "System szyfrowania danych RSA\n"
"-----------------------------\n"
" (C)2003 mgr Jerzy Walaszek\n\n"
"MENU\n"
"====\n"
"[ 0 ] - Koniec pracy programu\n"
"[ 1 ] - Generowanie kluczy RSA\n"
"[ 2 ] - Kodowanie RSA\n\n"
"Jaki jest twoj wybor? (0, 1 lub 2) : ";
cin >> w;
cout << "\n\n\n";
switch (w)
{
case 1 : klucze_RSA(); break;
case 2 : kodowanie_RSA(); break;
}
cout << "\n\n\n";
} while(w != 0);
}
Microsoft
Visual
Basic 2005
Express
Edition
' *******************************************************
' ** Przykładowa aplikacja obrazująca sposób działania **
' ** asymetrycznego systemu kodowania informacji RSA. **
' ** ------------------------------------------------- **
' ** (C)2005 mgr Jerzy Wałaszek **
' ** I Liceum Ogólnokształcące **
' ** im. Kazimierza Brodzińskiego **
' ** w Tarnowie **
' *******************************************************

Option Explicit On

Module
Module1

' Procedura oczekuje na naciśnięcie klawisza Enter
' po czym czyści ekran okna konsoli
'-------------------------------------------------

Public Sub Czekaj()

Console.WriteLine()
Console.WriteLine("Zapisz te dane i naciśnij Enter")
Console.ReadLine()

End Sub

' Funkcja obliczająca NWD dla dwóch liczb
'----------------------------------------

Public Function nwd(ByVal a As Integer, ByVal b As Integer) As Integer

Dim
t As Integer

While
b <> 0
t = b
b = a Mod b
a = t
End While
Return
a

End Function

' Funkcja obliczania odwrotności modulo n
'----------------------------------------

Public Function odwr_mod(ByVal a As Integer, ByVal n As Integer) As Integer

Dim
a0, n0, p0, p1, q, r, t As Integer

p0 = 0 : p1 = 1 : a0 = a : n0 = n
q = n0 \ a0
r = n0 Mod a0
While r > 0
t = p0 - q * p1
If t >= 0 Then
t = t Mod n
Else
t = n - ((-t) Mod n)
End If
p0 = p1 : p1 = t
n0 = a0 : a0 = r
q = n0 \ a0
r = n0 Mod a0
End While
Return
p1

End Function

' Procedura generowania kluczy RSA
'---------------------------------

Public Sub klucze_RSA()

Dim tp() As Integer = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43}
Dim p, q, phi, n, e, d As Integer

Console.Clear()
Console.WriteLine("Generowanie kluczy RSA")
Console.WriteLine("----------------------")
Console.WriteLine()

' generujemy dwie różne, losowe liczby pierwsze

Do
p = tp(Int(Rnd() * 10))
q = tp(Int(Rnd() * 10))
Loop Until p <> q

phi = (p - 1) * (q - 1)
n = p * q

' wyznaczamy wykładniki e i d

e = 3
While nwd(e, phi) <> 1 : e = e + 2 : End While
d = odwr_mod(e, phi)

' gotowe, wypisujemy klucze

Console.WriteLine("KLUCZ PUBLICZNY")
Console.WriteLine("wykładnik e = {0,4}", e)
Console.WriteLine(" moduł n = {0,4}", n)
Console.WriteLine()
Console.WriteLine("KLUCZ PRYWATNY")
Console.WriteLine("wykładnik d = {0,4}", d)
Czekaj()

End Sub

' Funkcja oblicza modulo potęgę podanej liczby
'---------------------------------------------

Public Function pot_mod(ByVal a As Integer, ByVal w As Integer, _
ByVal n As Integer) As Integer

Dim
pot, wyn, q As Integer

' wykładnik w rozbieramy na sumę potęg 2. Dla reszt
' niezerowych tworzymy iloczyn potęg a modulo n.

pot = a : wyn = 1 : q = w
While q > 0
If (q Mod 2) = 1 Then wyn = (wyn * pot) Mod n
pot = (pot * pot) Mod n ' kolejna potęga
q = q \ 2
End While
Return
wyn

End Function

' Procedura kodowania danych RSA
'-------------------------------

Public Sub kodowanie_RSA()

Dim e, n, t As Integer

Console.Clear()
Console.WriteLine("Kodowanie danych RSA")
Console.WriteLine("--------------------")
Console.WriteLine()
Console.Write("Podaj wykładnik = ") : e = Val(Console.ReadLine)
Console.Write(" Podaj moduł = ") : n = Val(Console.ReadLine)
Console.WriteLine("----------------------------------")
Console.WriteLine()
Console.Write("Podaj kod RSA = ") : t = Val(Console.ReadLine)
Console.WriteLine()
Console.WriteLine("Wynik kodowania = {0}", pot_mod(t, e, n))
Czekaj()

End Sub

Sub
main()

Dim w As Integer

Randomize
()
Do
Console.Clear()
Console.WriteLine("System szyfrowania danych RSA")
Console.WriteLine("-----------------------------")
Console.WriteLine(" (C)2005 mgr Jerzy Wałaszek ")
Console.WriteLine()
Console.WriteLine("MENU")
Console.WriteLine("====")
Console.WriteLine("[ 0 ] - Koniec pracy programu")
Console.WriteLine("[ 1 ] - Generowanie kluczy RSA")
Console.WriteLine("[ 2 ] - Kodowanie RSA")
Console.WriteLine()
Console.Write("Jaki jest twój wybór? (0, 1 lub 2) : ")
w = Val(Console.ReadLine)
Select Case w
Case 1 : klucze_RSA()
Case 2 : kodowanie_RSA()
End Select
Loop Until
w = 0

End Sub

End Module
Python

Program należy uruchamiać z dysku przez podwójne kliknięcie myszką pliku ze skryptem.

# -*- coding: cp1250 -*-
# *******************************************************
# ** Przykładowa aplikacja obrazująca sposób działania **
# ** asymetrycznego systemu kodowania informacji RSA. **
# ** ------------------------------------------------- **
# ** (C)2005 mgr Jerzy Wałaszek **
# ** I Liceum Ogólnokształcące **
# ** im. Kazimierza Brodzińskiego **
# ** w Tarnowie **
# *******************************************************

import random
import os

# Procedura wywołuje polecenie systemowe, które czyści
# zawartość okienka konsoli znakowej. W systemie Windows
# jest to cls. W systemie Unix clear
#-------------------------------------------------------
def cls():
os.system("cls")

# Procedura oczekuje na naciśnięcie klawisza Enter
# po czym czyści ekran okna konsoli
#-------------------------------------------------

def Czekaj():
print
raw_input("Zapisz te dane i nacisnij Enter")

# Funkcja obliczająca NWD dla dwóch liczb
#----------------------------------------

def nwd(a, b):
while b: a, b = b, a % b
return a

# Funkcja obliczania odwrotności modulo n
#----------------------------------------

def odwr_mod(a, n):
p0, p1, a0, n0 = 0, 1, a, n
q, r = n0 // a0, n0 % a0
while r:
t = p0 - q * p1
if t >= 0:
t = t % n
else:
t = n - ((-t) % n)
p0, p1, n0, a0 = p1, t, a0, r
q, r = n0 // a0, n0 % a0
return p1

# Procedura generowania kluczy RSA
#---------------------------------

def klucze_RSA():
tp = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
cls()
print "Generowanie kluczy RSA"
print "----------------------"
print

# generujemy dwie różne, losowe liczby pierwsze

p = q = 0
while p == q:
p, q = tp[random.randint(0, 9)], tp[random.randint(0, 9)]
phi, n = (p - 1) * (q - 1), p * q

# wyznaczamy wykładniki e i d

e = 3
while nwd(e, phi) != 1: e += 2
d = odwr_mod(e, phi)

# gotowe, wypisujemy klucze

print "KLUCZ PUBLICZNY"
print "wykladnik e = %4d" % e
print " modul n = %4d" % n
print
print "KLUCZ PRYWATNY"
print "wykladnik d = %4d" % d
Czekaj()

# Funkcja oblicza modulo potęgę podanej liczby
#---------------------------------------------

def pot_mod(a, w, n):

# wykładnik w rozbieramy na sumę potęg 2. Dla reszt
# niezerowych tworzymy iloczyn potęg a modulo n.

pot, wyn, q = a, 1, w
while q:
if (q % 2) == 1: wyn = (wyn * pot) % n
pot = (pot * pot) % n # kolejna potęga
q //= 2
return wyn

# Procedura kodowania danych RSA
#-------------------------------

def kodowanie_RSA():
cls()
print "Kodowanie danych RSA"
print "--------------------"
print
e = int(raw_input("Podaj wykladnik = "))
n = int(raw_input(" Podaj modul = "))
print "----------------------------------"
print
t = int(raw_input("Podaj kod RSA = "))
print
print "Wynik kodowania =", pot_mod(t, e, n)
Czekaj()

# ********************
# ** Program główny **
# ********************

w = 1
while w:
cls()
print "System szyfrowania danych RSA"
print "-----------------------------"
print " (C)2005 mgr Jerzy Walaszek "
print
print "MENU"
print "===="
print "[ 0 ] - Koniec pracy programu"
print "[ 1 ] - Generowanie kluczy RSA"
print "[ 2 ] - Kodowanie RSA"
print
w = int(raw_input("Jaki jest twoj wybor? (0, 1 lub 2) : "))
if w == 1: klucze_RSA()
elif w == 2: kodowanie_RSA()
JavaScript
<html>
<head>
<title>
Algorytm RSA</title>
</head>
<body>
<form style=
"border:2px outset #FFCC00;
PADDING-RIGHT: 4px;
PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px;
PADDING-TOP: 1px;
BACKGROUND-COLOR: #FFCC00"

name=
"rsa">
<div align=
"center"><center>
<h2>
Generator kluczy RSA</h2>
<p>(
C)2004 mgr Jerzy Wałaszek I LO w Tarnowie</p>
<p>
<input onclick=
"js_genkeys()" type="button" value="Generuj klucze">
<input onclick=
"js_keyclr()" type="button" value="Czyść klucze">
</p>
<table cellSpacing=
"4" cellPadding="4"
bgColor=
"#FF9933" border="0"
style=
"border-collapse: collapse">
<tr>
<th colSpan=
"2">Klucz publiczny</th>
<th colSpan=
"2">Klucz prywatny</th>
</tr>
<tr>
<td>
wykładnik</td>
<td id=
"gkey_e" style="TEXT-ALIGN: center">...</td>
<td>
wykładnik</td>
<td id=
"gkey_d" style="TEXT-ALIGN: center">...</td>
</tr>
<tr>
<td>
moduł</td>
<td id=
"gkey_n1" style="TEXT-ALIGN: center">...</td>
<td>
moduł</td>
<td id=
"gkey_n2" style="TEXT-ALIGN: center">...</td>
</tr>
</table>
<hr>
<h2>
Koder szyfru RSA</h2>
<p>
(C)2004 mgr Jerzy Wałaszek I LO w Tarnowie</p>
<table cellSpacing=
"4"
cellPadding=
"4"
bgColor=
"#FF9933"
border=
"0"
style=
"border-collapse: collapse">
<tr>
<td>
wykładnik</td>
<td><input name=
"ed"></td>
</tr>
<tr>
<td>
moduł</td>
<td><input name=
"n"></td>
</tr>
<tr>
<td>
wiadomość</td>
<td><input name=
"m"></td>
</tr>
</table>
<p>
<input onclick=
"js_codeRSA()" type="button" value="Koduj RSA">
<input onclick=
"js_codeclr()" type="button" value="Czyść formularz">
</p>
<p id=
"rsa_out">...</p>
</center></div>
</form>

<script language=
"JavaScript">

// Funkcja obliczająca NWD dla dwóch liczb
//----------------------------------------


function nwd(a, b)
{
var t;

while(b != 0)
{
t = b; b = a % b; a = t;
}
return a;
}

// Funkcja obliczania odwrotności modulo n
//----------------------------------------

function odwr_mod(a, n)
{
var a0,n0,p0,p1,q,r,t;

p0 = 0; p1 = 1; a0 = a; n0 = n;
q = Math.floor(n0 / a0);
r = n0 % a0;
while(r > 0)
{
t = p0 - q * p1;
if(t >= 0) t = t % n; else t = n - ((-t) % n);
p0 = p1; p1 = t;
n0 = a0; a0 = r;
q = Math.floor(n0 / a0);
r = n0 % a0;
}
return p1;
}

function js_genkeys()
{
var tp = new Array(11,13,17,19,23,29,31,37,41,43);
var p,q,phi,n,e,d;

// generujemy dwie różne, losowe liczby pierwsze

do
{
p = tp[Math.floor(Math.random() * 10)];
q = tp[Math.floor(Math.random() * 10)];
}while (p == q);

phi = (p - 1) * (q - 1); n = p * q;

// wyznaczamy wykładniki e i d

for(e = 3; nwd(e,phi) != 1; e += 2);
d = odwr_mod(e,phi);

// gotowe, wypisujemy klucze

document.getElementById("gkey_e").innerHTML = e;
document.getElementById("gkey_d").innerHTML = d;
document.getElementById("gkey_n1").innerHTML = n;
document.getElementById("gkey_n2").innerHTML = n;
}

function js_keyclr()
{
document.getElementById("gkey_e").innerHTML = " ";
document.getElementById("gkey_d").innerHTML = " ";
document.getElementById("gkey_n1").innerHTML = " ";
document.getElementById("gkey_n2").innerHTML = " ";
}

// Funkcja oblicza modulo potęgę podanej liczby
//---------------------------------------------


function pot_mod(a, w, n)
{
var pot,wyn,q;

// wykładnik w rozbieramy na sumę potęg 2. Dla reszt
// niezerowych tworzymy iloczyn potęg a modulo n.


pot = a; wyn = 1;
for(q = w; q > 0; q = Math.floor(q / 2))
{
if(q % 2) wyn = (wyn * pot) % n;
pot = (pot * pot) % n; // kolejna potęga
}
return wyn;
}

function js_codeRSA()
{
var e,n,t,s;

e = parseInt(document.rsa.ed.value);
n = parseInt(document.rsa.n.value);
t = parseInt(document.rsa.m.value);
if(isNaN(e) || isNaN(n) || isNaN(t))
s = "Błąd danych";
else
s = pot_mod(t,e,n);
document.getElementById("rsa_out").innerHTML = s;
}

function js_codeclr()
{
document.rsa.ed.value = "";
document.rsa.n.value = "";
document.rsa.m.value = "";
document.getElementById("rsa_out").innerHTML = " ";
}
</script>
</body>
</html>
   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

 

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


8
komentarze: 79 | wyświetlenia: 948
111
komentarze: 32 | wyświetlenia: 60415
54
komentarze: 56 | wyświetlenia: 32423
54
komentarze: 68 | wyświetlenia: 31150
50
komentarze: 27 | wyświetlenia: 63295
49
komentarze: 18 | wyświetlenia: 64802
39
komentarze: 30 | wyświetlenia: 28644
39
komentarze: 50 | wyświetlenia: 23134
37
komentarze: 9 | wyświetlenia: 28366
36
komentarze: 37 | wyświetlenia: 23210
34
komentarze: 21 | wyświetlenia: 26233
32
komentarze: 12 | wyświetlenia: 26550
 
Autor
Artykuł



  rosly,  24/07/2008

I to się nazywa dobry artykuł

Bardzo ciekawy artykuł o szyfrowaniu danych!

Good One. Have a look at my website ( http://www.royalpharmax.com/Bu(...)-Viagra ).



Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska