1 Laborki:
Wejściówka - obliczyć NWD rozszerzonym algorytmem Euklidesa
Na zajęciach przykłady różnych szyfrowań (nie na ocenę)
Zadanie na zajęcia do zrobienia w EXCEL (zad.docx)
2 Laborki:
Wejściówka - macierz 2x2 mod 26
Na zajęciach przykłady szyfrowań (nie na ocenę - np. Hilla)
Zadanie na zajęciach do zrobienia na kartce lub w EXCEL (zad2.docx)

dzisiaj na wejsciowce bylo:
a) znajdz wszystkie x takie, ze 5x=12 mod 77
b) znajdz wszystkie x takie, ze 8x=12 mod 77

streszczenie rozwiazania:

rozszerzony algorytm Euklidesa dla 5,77:
77=15*5+2
5=2*2+1
1=5-2*2=5-2*(77-15*5)=31*5-2*77
zatem 1=31*5 mod 77

x=31*5x=31*12=64 mod 77
zatem x =77k+64 dla k calkowitego. drugi podpunkt analognicznie.
na zajeciach to samo co wyzej.

Dla leniwych zadanie b\, trochę inaczej:

8x=12(77)
8x=12(7) i 8x=12(11)
x=12(7) i 8x=1(11)
x=5(7) i 8x=1(11)

Liczymy odwrotność 8 w Z_11. Z rozszerzonego algorytmu Euklidesa mamy:
11 = 8 + 3
8 = 2*3 + 2
3 = 2 + 1
1 = 3 - 2 = 3 - (8 - 2*3) = -8 + 3*3 = -8 + 3*(11 - 8) = 3*11 - 4*8

Czyli 3*11 = 4*8 + 1, inaczej 4*8=-1(11)
10*4*8=-10(11)
40*8=1(11)
7*8=1(11)
Zatem odwrotnością 8 jest 7.

8x=1(11)
7*8x=7(11)
56x=7(11)
x=7(11), dołączając wcześniej obliczony warunek dostajemy koniunkcję
x=7(11) i x=5(7)

Rozwiązujemy układ kongruencji
x = 11*k_1 + 7
11*k_1 + 7 = 5 (mod7)
4*k_1 = 5(mod 7)
2*4*k_1 = 2*5 (mod 7) //biorę z dupy odwrotność 4 mod 7
k_1 = 3 (mod 7)
k_1 = 7*k_2 + 3
x = 11(7*k_2 + 3) + 7 = 77*k_2 + 33 + 7 = 77*k_2 + 40

Sprawdzenie: k_2 := 0 ; 40*8 = 400 - 80 = 320
320 - 12 = 308
308 / 77 = 4 //gitara

LAB2

http://imageshack.us/photo/my-images/804/macierz.png/

Macierz odwrotna to iloczyn transponowanej macierzy złożonej z dopełnień algebraicznych
( http://pl.wikipedia.org/wiki/Dope%C5%82 ... gebraiczne )
oraz odwrotności wyznacznika (w tym wypadku odwrotności w pierścieniu Z_k, czy tam Z_26)

Żeby sprawdzić czy macierz da się odwrócić trzeba policzyć wyznacznik. Jeśli wyznacznik jest elementem odwracalnym w pierścieniu nad którym jest macierz to się da. Element x jest odwracalny w pierścieniu Z_k wtw. nwd(x,k) = 1.

Przykład1:
|1 3 2|
|2 1 3|= ... = 18 , nwd(18,26) != 1 więc macierz jest nieodwracalna (w Z_26, w R jest odwracalna)
|3 2 1|

Przykład2:
|11 8|
|3 7| = 53 = 1(mod 26)

A^{-1} =
|a_{1,1}, a_{1,2}| ^T
|a_{2,1}, a_{2,2}|
a_{1,1} = 1
a_{1,2} = -3
a_{2,1} = -8
a_{2,2} = 7 , to wszystko trzeba teraz transponować i pomnożyć przez odwrotność wyznacznika (1^{-1} = 1), wynik to A^{-1}.
Zauważmy jeszcze że -3 = 23 i -8 = 18 w Z_{26}, stąd wynik MSO.

Ogólnie trzeba tylko uważać na ten wyznacznik, policzyć jego odwrotność w pierścieniu (np z Euklidesa, pamiętając że ułamki działają trochę inaczej w Z_k
) i traktować współczynniki jak reszty z dzielenia przez k (inaczej elementy pierścienia ilorazowego Z/kZ) - tzn można odejmować całkowite wielokrotności k. Sposób działa dla macierzy kwadratowych dowolnego wymiaru.

Dla większych macierzy łatwiej po pierwsze sprawdzić, czy dany wyznacznik i 26 mają NWD = 1 (czyli czy jest odwracalne), a jeśli tak, to później wystarczy dostawić sobie obok macierz jednostkową i tak, jak przy normalnych macierzach, metodą przekształceń Gauss'a, pamiętając, że w tej arytmetyce nie można dzielić, a jedynie mnożyć przez odwrotność (np. odwrotnością 3 jest 9, bo 9x3 mod 26 = 1). Doprowadzając naszą pierwotną macierz do postaci jednostkowej z macierzy, która była dostawiona utworzy nam się macierz odwrotna.

LAB3

Generowanie klucza RSA (5 wykład)

Takie zadania mieliśmy:
4. Znajdź tekst jawny jeśli klucz publiczny
0) (n,e) = (74498803, 7), szyfrogram to (35225132,33236691,46945999),
1) (n,e) = (64231009, 7), szyfrogram to (36334266, 26708080, 3370140)

5. Pokaż że znajomość fi(N) , gdzie N jest modułem RSA jest równoważna ze znajomością rozkładu N na czynniki.
0) N=40955977
fi(N)=40943056

1) N=48470593
fi(N)=48456640


Na wejściówce dawał p i q i z tego się wyznaczało klucz

U nas na wejściówce dał liczbę do rozłożenia na czynniki pierwsze (faktoryzacja):
a)299
b)323
co robiliśmy nawet w podstawówce


Laborka: to samo zadanie dostaliśmy co grupa wyżej, tylko zmienione dane. Słuchać i notować jak tłumaczy, zadania które robicie mają taką samą treść jak te które są do wykonania samodzielnego. Do obliczeń modulo takich dużych liczb jakie podał (8 cyfrowe chyba) najlepszy jest wolfram alfa. Czasu aż za dużo, z łatwością można wynieść 10pkt.

najnowsze zadanie z laborki trzeciej - algorytm RSA -> znając N i e obliczyć d.
N=493
e = 15

LAB4

Uprzedzając pytania:
Wejściówka: potęgowanie modularne - banalna sprawa, w necie jest dużo przykładów.
Zadanie na zajęciach: program w c, liczący potęgowanie modularne - też śmiesznie łatwe.

u nas też będzie potęgowanie modularne. U następnej grupy po nas (nie mam pojęcia która to grupa) będzie generowanie grup cyklicznych.

Nie wiem czy którejś z grup jeszcze się to przyda ale myślę że warto napisać. Dzisiaj:
wejściówka potęgowanie modularne w stylu:


Warto było skorzystać z zależności aby nie bawić się z tak wysokim wykładnikiem

przy założeniu że


Zadanie do wykonania na zajęciach:
Zaimplementuj algorytm El Gamala. Program wczytuje tekst jawny i klucz publiczny. Umożliwia zaszyfrowanie tekstu jawnego i odszyfrowanie szyfrogramu po podaniu klucza prywatnego.

---