Автор неизвестен - Opracowanie przykladow zaszyfrowania i rozszyfrowania algorytmem rsa - страница 1

Страницы:
1  2 

Zal^cznik 1 do W2 (SK)

Opracowanie przykladow zaszyfrowania i rozszyfrowania algorytmem RSA

Przyklad 1_

Lp.

Dzialanie

Przyklad

Uwagi

1)

losujemy liczby pierwsze p i q

p = 3, q = 19

liczby p i q nie powinni bye liczbami typu specjalistycz nego, na przyklad liczbami Fermata lub Mersenne'a:

pierwsze liczby Fermata wyrazony s^. w postaci 2r + 1, gdzie r > 1 - liczba pierwsza;

pierwsze liczby Mersenne'a okreslane s^. ze wzoru 2r - 1, gdzie r > 1 - liczba pierwsza (na rok 1995 zostaly znaleziony 33 wartosci r, dla ktorych 2r - 1 jest liczby pierwsz^, najwi^ksz^.

z nich r = 859433; pierwsz^ zlozon^ liczby postaci 2r - 1 dla liczby pierwszej r jest

211 - 1 = 23 * 89 = 2047)

2)

obliczamy n = p * q

n = 3 * 19 = 57

n i e - klucz publiczny

3)

wyliczamy funkcje Eulera j(n) = (p -1)(q -1)

j(n) = (3 -1)(19 -1) = 36

 

4)

losujemy liczby e tak^, ze NWD(e, j(n)) = 1

np. e = 5, poniewaz NWD(5, 36) = 1

 

Liczby p i q wymazujemy z systemu !!!

5)

okreslamy d z kongruencji d * e ° 1 mod j(n) :

 

d - klucz tajny (prywatny)

5.1) ww. kongruencji sprowadzamy do rownania Diofantesa d * e - j(n) *y = 1,

w ktorym spelnia si<? warunek e < j(n); 5.2)   stosujemy rozszerzony algorytm Euklidesa do rozwi^zania rownania Diofantesa.

Rozszerzony algorytm Euklidesa:

wersja klasyczna

qo

//

5     =    36 * 0 + 5

- - qi

36   = 5*7+1

- - q2 ® к = 2

5     =    1   * 5 + 0

Zalacznik_1_do_W2_(SK_B).doc


 

= qi

*

 

+ W-2;

 

 

Ui = qt * U-1

+ U-2;

 

 

 

 

 

(W-2 =

U-1 =0;

W-1 =

U-2 =1 ® zawsze!!!)

 

 

Wo

= 0

*

1

+ 0   =0;

 

 

U0 = 0 * 0

+ 1 =

1;

Wi

=7

*

0

+ 1   = 1 ®

Wk-1;

Uk-1

U1 = 7 * 1

+ 0 =

7;

W2

=5

*

1

+ 0   =5;

 

 

U2 = 5 * 7

+ 1 =

36;

i

-2

-1

0

1

2

 

qi

 

0

7

5

 

Wi

0

1

0

 

5

 

Ui

1

0

1

,7\

36

 

Uk-1

Wk-1

d = (-1)k-1 * Uk-1 = (-1)2-1 * 7 = -7;

y = (-1)k-1 * Wk-1 = (-1)2-1 * 1 = -1. Poniewaz otrzymany klucz prywatny d jest liczba ujemna (a powinien bye liczby dodatni^), przeprowadzamy przetwarzania stosuj^c kongruencje: d = -7 °-7 mod 36 ° ((-1) * 36 + 29) mod 36 ° 29 mod 36 = 29.

wersja modyfikowana

q2

//

36   = 5*7+1

„ - q3 ® k = 3

5     =    1   * 5 + 0

Wi = qi * Wi-1 + Wi-2 ;

W2 W3

Ui = qi * Ui-1 + Ui-2;

7*0 5 * 1 + 1 + 0

(Wo = U1 =1;    W1 = U0 =0 ®zawsze!!!)

1 ®

5 ;

Wk-1;

Wi

Ui

0

0

Uk-1

U2

U3

0

2

7

7

Uk-1

7 5

* 1

* 7

3

5

5

36

Wk-1

+ 0

+ 1 7;

36;

d = (-1)k-2 * Uk-1 = (-1)3-2 * 7 y = (-1)k-2 * Wk-1 = (-1)3-2 * 1 -7;

-1.

1

i

1

1

1

Poniewaz otrzymany klucz prywatny d jest liczba ujemna (a powinien bye liczby dodatni^), przeprowadzamy przetwarzania stosuj^c kongruencje: d = -7 °-7 mod 36 ° ((-1) * 36 + 29) mod 36 ° 29 mod 36 = 29.

6)

zaszyfrowanie: c = me mod n

np.    m = 637; ci = 65 mod 57 = 24, c2 = 375 mod 57 = 37, c = {c1c2j ={24;37}

Poniewaz m = 637 > n = 57, dzielimy m tak, zeby mj < n,       np. ni1 = 6, ni2 = 37.

 

7)

rozszyfrowanie: m = cd mod n

ni1 = 2429 mod 57 = 6, ni2 = 3729 mod 57 = 37, m = {1П1ІП2} = 637.

Przyklad 2

Lp.

Dzialanie

Przyklad

Uwagi

1)

losujemy liczby pierwszep i q

p = 7, q = 31

Patrz. Przyklad 1

2)

obliczamy n = p * q

n = 7 * 31 = 217

 

3)

wyliczamy funkcji Eulera

j(n) = (7 -1)(31 -1)=

n i e - klucz

 

j(n) = (p -1)(q -1)

180

publiczny

4)

losujemy liczbi e tak^, ze NWD(e, j(n)) = 1

np. e = 7, poniewaz NWD(7,180) = 1

 

Liczby p i q wymazujemy z systemu !!!

5)

okreslamy d z kongruencji d * e ° 1 mod j(n) :

 

d - klucz tajny (prywatny)

5.3) ww. kongruencji sprowadzamy do rownania Diofantesa d * e - j(n) *y = 1,

w ktorym spelnia si$ warunek e < j(n); 5.4)   stosujemy rozszerzony algorytm Euklidesa do rozwi^zania rownania Diofantesa.

Rozszerzony algorytm Euklidesa:

• wersja klasyczna

q0

//

7    =    180* 0+7

у

180 =    7   * 25+ 5

у

/     - - q2

7    = 5*1+2

/     - - q3

5    = 2*2+1

/        - q4 k = 4

* у■' //

2    = 1*2+0

Wi

= qi *

Wi-1

+ Wi-2 ;

 

 

Ui = qi * Ui-1

+ Ui-2;

 

 

 

 

 

(W-2 =

U-1 =0;

W-1

= U-2 =1 — zawsze!!!)

 

 

W0

= 0 *

1

+ 0

= 0;

 

 

U0 = 0 * 0

+ 1 =

1;

W1

= 25*

0

+ 1

= 1;

 

 

U1 = 25* 1

+ 0 =

25;

W2

= 1 *

1

+ 0

= 1;

 

 

U2 = 1 * 25

+ 1 =

26;

W3

=2*

1

+ 1

= 3 —

Wk-1;

Uk-1

    U3 = 2 * 26

+ 25 =

77;

W4

=2*

3

+ 1

=7 ;

 

 

U4 = 2 * 77

+ 26 =

180;

Zalacznik_1_do_W2_(SK_B).doc


i

-2

-1

0

1

2

3

4

qi

 

0

25

1

2

2

Wi

0

1

0

1

1

3 \

7

Ui

1

0

1

25

26

,77\

180

Uk-1

Wk-1

d = (-1)k-1 * Uk-1 = (-1)4-1 * 77 = -77; y = (-1)k-1 * Wk-1 = (-1)4 -1 * 3 = -3. Poniewaz otrzymany klucz prywatny d jest liczba ujemna (a powinien bye liczby dodatni^), przeprowadzamy przetwarzania stosuj^c kongruencje: d = -77 °-77 mod 180 ° ((-1) * 180 +103) mod 180 ° 103 mod 180 = 103.

• wersja modyfikowana

q2

//

180 =    7   * 25+ 5

, - q3

5  * 1 + 2

- - q4

5*   =    2A * 2 +1

- q5 k = 5

2    =    1   * 2 + 0

Wi

= qi *

Wi-1

+ Wi-2 ;

 

Ui = qi * Ui-1

+ Ui-2;

 

 

 

 

(Wo = U1 =1;

W1 =

U0 =0 —zawsze!!!)

 

 

W2

= 25*

0

+ 1  =1;

 

U2 = 25* 1

+ 0 =

25;

W3

= 1 *

1

+ 0   = 1 ;

Страницы:
1  2 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа