[Kryptografia] Affine transformation

Mecze sie z tym od jakiegos czasu i jakos dojsc nie moge.
Mam rownanie:
c = a*k mod n
Jak wyznaczyc z tego rownania a? Zalozenie jest takie, ze k i n sa wzglednie pierwsze. Mozna nawet dokladniej przyjac, ze n = 26.

Nie wiem czy o to Ci chodzilo, ale przedstawie to do czego doszedlem.
c = ak mod n <==> ak = c + mn, m = 0, 1, 2, ...
a = (c + mn) div k
Czyli poszukujemy takiego m by (c + mn) bylo podzielne przez k i mamy a.

#include <stdio.h>

int daj_a(int c, int k, int n)
{
  int m;

  for (m = 0; (c + m*n) % k; m++);

  return (c + m*n) / k;
}

int main(void)
{
  int a, k = 7, n = 26, c;
  for (a = 0; a < 31; a++)
  {
    c = a*k % n;
    printf("%2d --> %2d --> %2d\n", a, c, daj_a(c, k, n));
  }
  getchar();
  return 0;
}

Akurat nie chodzilo mi o sprawdzanie roznych mozliwosci. Moze przedstawie dokladniej.
Szyfrujemy tak:
c = ak1 mod n
Rozszyfrowujemy:
a = ck2 mod n

Przy czym k1*k2 mod n = 1
Dla n = 26 takimi parami sa np 3 i 9.
Wiec moznaby chyba sprowadzic to do zagadnienia jak znalezc k2 majac k1. Wychodzi z tego rownanie diofantyczne, ktorego algorytm rozwiazywania nie podoba mi sie (bo sie nie miesci w 1 linijce :P). Wiec zastanawiam sie, czy moze jest jakis inny sposob.

Zapraszam, zapraszam ... kolejny niezrównoważony pseudomatematyczny bełkot. Co chwilę wpadam w dygresję i przekraczam wszelkie rozsądne rozmiary postu.

W gruncie rzeczy sądzę, że teoria liczb jest świetnym kandydatem na najtrudniejszą gałąź matematyki. Zdecydowanie jesteśmy bardziej bezbronni wobec krwiożerczej i przerażającej sumy uogólnionej niż ledwo niegrzecznej całki.

Zapraszam do lektury !

"mod" może mieć dwa znaczenia:

reszta w dzieleniu całkowitoliczbowym (np. Delphi).
x = 12 mod 10
tutaj x jest jedną liczbą = 2

przystawanie dwóch liczb (kongruencja)
x = 12 (mod 10)
tutaj x może przyjąć jedną z nieskończenie wielu wartości = {2, 12, 22, 32, ...}.
Reguła jest następująca:
reszta z dzielenia x przez 10 jest taka sama jak reszta z dzielenia 12 przez 10 (czyli 2).

Jeszcze jeden przykład:
5 mod 4 = 1
5 (mod 4) = 1 lub 5 lub 9 ...

Jest więc pewna subtelna różnica w zapisie i będę ją uwzględniał w dalszej części tekstu.

Pierwszy pomysł
Dryo, prawdopodobnie miałeś na myśli równanie:
c = a*k (mod n)

Chcemy wyznaczyć wartość a. Pierwszy pomysł polega na wykorzystaniu dwóch praw:

jeśli a = b (mod n) to

1. b = a (mod n)
2. a:d = b:d (mod n:d) przy czym a, b i n są podzielne przez liczbę naturalną d

Możemy więc zapisać
a*k = c (mod n)
a = c:k (mod n:k)

Niestety, wbrew pozorom nie przybliżyliśmy się do rozwiązania ani trochę. Wynika to z dwóch faktów:

1. c oraz n muszą być podzielne przez k
2. z treści zadania wiemy że n i k są wzglęnie pierwsze

Liczby względnie pierwsze to takie, których największy wspólny dzielnik wynosi 1.

Inaczej nwd(n,k)=1
W związku z tym k nie jest podzielnikiem n, gdyż wtedy nwd(n,k)=k
Inaczej mówiąc n nie jest podzielny przez k - nie możemy więc zastosować drugiego z przytoczonych praw kongruencji.

Szukamy brutalną siłą
Rozwiązanie problemu istnieje i uprzedzając powiem że prowadzi przez tzw. odwrotny algorytm Euklidesa. Wpierw jednak rozpracujmy przykład:

c = ak (mod n)
7 = a3 (mod 8)

Wartości c, a i n są ograniczone na dwa sposoby:

1. nwd(n,k) = 1
2. c < n

Drugie wynika z tego, że reszta z dzielenia przez np. 8 może w największym przypadku wynosić 7.

Wracamy do przykładu, mamy
7 = a*3 (mod 8)

Pytamy więc: Dla jakiej wartości a reszta z dzielenia 3*a przez 8 wynosi 7. Sprawdźmy dla kilku wartości:

a 3*a mod 8

1 3
2 6
3 1
4 4
5 7
6 2
7 5
8 0
9 3
10 6

Jedną z możliwych odpowiedzi jest więc a=5

A ile wynosi 3*11 mod 8 ?
bez liczenia możemy powiedzieć: 1

ciąg 3, 6, 1, 4, 7, 2, 5, 0 powtarza się cyklicznie a każda wartość z zakresu [0, 7] występuje w nim dokładnie jeden raz (analogię tego zjawiska znajdziemy w tablicach haszujących - a dokładniej w jednej z popularnych strategi obsługi kolizji)

Spróbujmy teraz zobaczyć co się stanie gdy odrzucimy warunek nwd(n,k)=1, np.
7=a*4 (mod 8)

a 4*a mod 8

1 4
2 0
3 4

Zauważmy że nie istnieje rozwiązanie równania 7=4*a (mod 8)

Można to skojarzyć z długością cyklu, która w ogólnym przypadku wynosi:
n / nwd(k,n)

... faktycznie
n / nwd(k,n) = 8 / nwd(4,8) = 8/4 = 2

W związku z tym możemy wywnioskować, że:
Warunek nwd(n,k)=1 jest warunkiem wystarczającym rozwiązywalności równania (ale nie koniecznym, gdyż np. równianie 4=4a (mod 8) rozwiązanie posiada).

Rozwiązanie
(Prawdopodobnie bardziej niecierpliwi już dawno zarzucili czytanie.)

Wychodzimy od problemu:
c = k*a (mod n)
a = ?

Gdybyśmy potrafili wyrazić c za pomocą wyrażenia:
c = kx - ny

To okaże się, że wartość x jest jednym z możliwych rozwiązań !

Oto dowód:
Podstawiamy do wzoru c = ka (mod n)
kx - ny = ka (mod n)

korzystamy z pierwszej własności kongruencji:
ka = kx - n*y (mod n)

Na chwilę się zatrzymajmy
Czy jest jakaś różnica pomiędzy:
24 (mod 10)
14 (mod 10)
4 (mod 10) ?

Nie ! Każde z nich definiuje ten sam zbiór rozwiązań = {4, 14, 24, 34 ...}
W związku z tym możemy napisać że
241 - 100 (mod 10) =
241 - 101 (mod 10) =
241 - 102 (mod 10)

a bardziej ogólnie:
kx - ny (mod n) =
kx - n0 (mod n) =
k*x (mod n)

teraz podstawiając otrzymujemy:
ka = kx (mod n)

a to oznacza że:
a=x

Podsumowując, jeśli wyrazimy c za pomocą wyrażenia:
c = kx - ny

to x jest jednym z rozwiązań.

Sposób
Wspominałem o odwrotnym algorytmie Euklidesa - ta potoczna nazwa jest odrobinę myląca. W istocie jego działanie rozpoczyna się w miejscu, w którym klasyczny algorytm Euklidesa się kończy.

posłużę się przykładem (tym samym co pierwsza tabelka):

7 = 3a (mod 8)
a = ?

Będziemy chcieli więc przedstawić c=7 jako
c = kx - ny
7 = 3x - 8y

Zaczynamy od zastosowania algorytmu Euklidesa dla wartości n i k. Może wydawać się to głupie, gdyż wynik tego działania jest z góry znany - nwd(n,k)=1 z treści zadania.

Jednak tak naprawdę nie interesuje nas wynik, tylko droga którą do niego dochodzimy:

8 = 23 + <font color="red">2</span>
3 = 12 + <font color="red">1</span>
2 = 2*1 + 0

Zanim wyrazimy 7 jako
7 = 3x - 8y

wpierw rozpiszemy
1 = 3x' - 8y'

robimy to w oparciu o przedostatni wiersz algorytmu Euklidesa:
<font color="red">1</span> = 3 - 1*<font color="red">2</span>
1 = 3 - 1*(8 - 23)
1 = 33 - 8*1

wystarczy teraz przemnożyć stronami
7 = 321 - 87

odpowiedź: rozwiązaniem 7 = 3*a (mod 8) jest między innymi liczba 21
sprawdzenie: w istocie 7 = 63 (mod 8) [czytaj "7 przystaje do 63 modulo 8"]

Uogólnienie
A jeśli szukamy najmniejszego możliwego a ?

• inaczej mówiąc jeśli szukamy rozwiązania 7 = 3*a mod 8
  Jest nim x mod n
  czyli 21 mod 8 = 5

W ogólności a = { a1, a1 + n, a1 + 2n, ... a1 + kn }
gdzie a1=x mod n
(x jest wynikiem naszego algorytmu)

Pozdrawiam bardzo gorąco
kapustka

Hehehehehe...
Gdzie ja to już widziałem???
Chwila....
Tak to wygląda jak...
Hmmm...
W jednej książce widziałem (w faq-ach też) podobny (może nawet identyczny tylko zmienne inne) wzór: RSA....

Ale panowie, panowie...

Bez aluzji.........

Chyba nie rozumiem twojej idiotycznej aluzji dArO.

Jeśli próbujesz zarzucić mi, że część wzorków gdzieś już widziałeś - to masz absolutną rację ! Sądzę że spokojnie byłbyś w stanie podać ogromny spis różnych książek w wielu językach.

Widzisz stary napisałem to wszystko nie dlatego by podszywać się pod autora tego kryptosystemu ... tylko po to aby pokazać w jaki sposób można (według mnie) rozwiązać równanie:

c = a*k (mod n)
ze względu na zmienną a.

Albo jesteś strasznie głupi albo próbujesz być złośliwy.
Tak czy inaczej wkurzyłeś mnie.

Ale panowie, panowie ...
Bez aluzji ...

ps.
flabra ... dzięki za propozycję. Koniecznie to zrób.

// done - as kncik tforzuff_4p wrzucilem do 'z pogranicza' [mf]

Kapustka: zerknij na komentarz przy artykule (tam najpierw przeczytalem). Ale dziekuje za rozwiniecie tematu.

"W jednej książce widziałem (...)" :-D

male sprostowanie co do tego kryptosystemu - nie jest to RSA (mlze byc to jedynie skladnik RSA, calosc algorytmu jest znacznie bardziej skomplikowana) - powyzsze rownanie afiniczne jest pewna modyfikacja standardowego szyfru Cezara
c=(a+k)mod ; Chociaz uogolniona wersja zmodyfikowanego algorytmu ma postac c=((a+k)*p)mod n;

gdzie n to np. 26. (czyli ilosc liter w alfabecie angielskim)
Szyfr ten zostal zmodyfikowany o dodanie iloczynu po to, aby krok pomiedzy przestawieniem liter nie byl staly. Oczywiscie k i p powinny byc wzglednie pierwsze i jest to klucz szyfrowania.
A odnosnie odszyfrowania informacji - to znajac paramety p i k odszyfrowanie wcale nie wymaga obliczenia znaku a - wystarczy utworzyc dwa wektory i porownac wartosci o tych samych indeksach - prostrze i znacznie szybsze...
pozdrawiam...

powyzsze rownanie afiniczne jest pewna modyfikacja standardowego szyfru Cezara
c=(a+k)mod ; Chociaz uogolniona wersja zmodyfikowanego algorytmu ma postac c=((a+k)*p)mod n;

Dokladniej to oryginalny kod wzor byl c = (a*k+p) mod n
I mozna z mojej perspektywy to szyfr cezara jest uproszczona wersja szyfru:
c = (a^t*k_t+a^t-1*k_t-1+a^t-2*k_t-2+...+a²*k₂+a¹*k₁+a⁰*k₀) mod n :)

A odnosnie odszyfrowania informacji - to znajac paramety p i k odszyfrowanie wcale nie wymaga obliczenia znaku a - wystarczy utworzyc dwa wektory i porownac wartosci o tych samych indeksach - prostrze i znacznie szybsze...

To rozwiazanie jest oczywiste, ale nie podobalo mi sie z tego samego wzgledu: zajmuje wiecej niz jedna linijke :)
Chcialem po prostu dowiedziec sie, czy jest mozliwe wyznaczenie prostego wzoru matematycznego deszyfrujacego to na podstawie k i n. Jak widac nie da sie. Ale serdecznie dziekuje wszystkim za proby. Na pewno takie dyskusje warte sa poczytania.