Permutu a funkcja jednokierunkowa VMPC

Strona funkcji VMPC  -  www.pieknafunkcja.pl

Na tej stronie wytłumaczę, dlaczego gra Permutu i funkcja jednokierunkowa VMPC to jedno i to samo. I co to właściwie jest ta funkcja...

Spójrzmy na poniższy rysunek. Zaznaczona kolumna klocków na planszy Permutu zbudowana jest z trzech symboli. Symbole te odpowiadają parom liczb, jakie zostały użyte do wyliczenia, że wartości funkcji VMPC dla liczby 1 wynosi 3.

Funkcja jednokierunkowa VMPC leży u źródła całego projektu VMPC. Odkryłem ją w roku 1998, badałem przez kilka kolejnych lat. W roku 2004 opublikowałem ją razem z Technologią Szyfrowania VMPC na międzynarodowej konferencji kryptograficznej FSE w Indiach.

Funkcja VMPC jest prostym przekształceniem permutacji wg wzoru (permutacja to ciąg "potasowanych" liczb):

f(f(f(x))+1)

Działanie funkcji VMPC można zilustrować na schemacie:

Przekonajmy się, że gra Permutu i funkcja VMPC to jedno i to samo.

Aby to zilustrować, potrzebujemy tabeli z liczbami:

Na górze mamy kolejne liczby: 1 2 3 4 5.
Na dole te same liczby są potasowane: 2 4 5 1 3.

Linia pionowa | łączy w parę liczbę na górze z liczbą pod nią.
Każda para ma swój symbol, np. para (1:2) , para (2:4) , itd.



Układanie klocków Permutu to obliczanie wartości funkcji VMPC.



Obliczmy wartość funkcji VMPC dla liczby 1 i ułóżmy pierwszą kolumnę Permutu:

Linia ukośna / łączy liczbę na górze z taką samą liczbą na dole, np. (2/2).

Wystarczy podążać za niebieską linią.

Zaczynamy od liczby 1 na górze. Pod 1 leży 2. Para (1:2) ma symbol . Zapiszmy ten symbol z boku na górze.

Ukośną linią / idziemy do liczby 2 na górze. Pod 2 leży 4. Para (2:4) ma symbol . Zapiszmy ten symbol z boku po środku.

Ukośną linią / idziemy do liczby 4 na górze. Do 4 dodajemy 1 (zgodnie ze wzorem funkcji VMPC f(f(f(x))+1)) i otrzymujemy 5. Pod 5 leży 3. Para (5:3) ma symbol . Zapiszmy ten symbol z boku na dole.

Gotowe!
Pary (1:2)(2:4)(5:3) wyznaczyły, że funkcja VMPC dla liczby 1 ma wartość 3.

Jednocześnie symbole kolejno użytych par:

Pierwsza para (1:2) na górze na czerwono
Druga para (2:4) po środku na czarno
Trzecia para (5:3) na dole na zielono

utworzyły pierwszą kolumnę Permutu.

Dalsze działania są analogiczne. Prześledźmy je na kolejnych rysunkach:



Wartość funkcji VMPC dla liczby 2 i druga kolumna Permutu:

Zaczynamy od liczby 2 na górze. Pod nią leży 4. Zapiszmy symbol pary (2:4)    na górze.

Ukośną linią / idziemy do 4 na górze. Pod 4 leży 1. Zapiszmy symbol pary (4:1)    po środku.

Ukośną linią \ idziemy do 1 na górze. Do 1 dodajemy 1 i otrzymujemy 2. Pod 2 leży 4. Zapiszmy symbol pary (2:4)    na dole.

Pary (2:4) , (4:1) , (2:4) utworzyły drugą kolumnę Permutu
i wyznaczyły, że funkcja VMPC dla liczby 2 ma wartość 4, czyli f(f(f(2))+1)=4.



Wartość funkcji VMPC dla liczby 3 i trzecia kolumna Permutu:

Pary (3:5) , (5:3) , (4:1) utworzyły trzecią kolumnę Permutu
i wyznaczyły, że funkcja VMPC dla liczby 3 ma wartość 1, czyli f(f(f(3))+1)=1.



Wartość funkcji VMPC dla liczby 4 i czwarta kolumna Permutu:

Pary (4:1) , (1:2) , (3:5) utworzyły czwartą kolumnę Permutu
i wyznaczyły, że funkcja VMPC dla liczby 4 ma wartość 5, czyli f(f(f(4))+1)=5.



Wartość funkcji VMPC dla liczby 5 i piąta kolumna Permutu:

5+1=6. Ale w tabeli mamy liczby od 1 do 5. Co zrobić?
Dodawanie faktycznie odbywa się "modulo 6", co oznacza, że zamiast liczby 6 przyjmujemy liczbę 1.
Pary (5:3) , (3:5) , (1:2) utworzyły piątą kolumnę Permutu
i wyznaczyły, że funkcja VMPC dla liczby 5 ma wartość 2, czyli f(f(f(5))+1)=2.





Obliczając wartości funkcji VMPC ułożyliśmy klocki na planszy Permutu:



Zagrajmy więc!



Granie w Permutu to odwracania funkcji VMPC.



Zbierzmy wszystkie pięć wartości funkcji VMPC, które właśnie obliczyliśmy:

Pary (1:2)(2:4)(5:3) wyznaczyły, że f(f(f(1))+1)=3
Pary (2:4)(4:1)(2:4) wyznaczyły, że f(f(f(2))+1)=4
Pary (3:5)(5:3)(4:1) wyznaczyły, że f(f(f(3))+1)=1
Pary (4:1)(1:2)(3:5) wyznaczyły, że f(f(f(4))+1)=5
Pary (5:3)(3:5)(1:2) wyznaczyły, że f(f(f(5))+1)=2

Zauważmy, że pary układają się według schematu:

(X:A)(A:B)(B+1:Y)

Na przykład:
(1:2)(2:4)(5:3)
X=1   A=2   B=4   B+1=5   Y=3

Odwrócenie funkcji VMPC polega na odtworzeniu par mając dane wartości f(f(f(x))+1)=y.
Oznacza to uzupełnienie poniższego szablonu według schematu (X:A)(A:B)(B+1:Y):

(1:_)(_:_)(_:3)
(2:_)(_:_)(_:4)
(3:_)(_:_)(_:1)
(4:_)(_:_)(_:5)
(5:_)(_:_)(_:2)



Związek pomiędzy odwracaniem funkcji VMPC a graniem w Permutu zawiera się w dwóch zasadach:

1. Wzięcie pojedynczego klocka w Permutu oznacza zgadnięcie jednej pary (_:_) w funkcji VMPC. 2. Wzięcie kolumny klocków jest możliwe, gdy znamy wszystkie pary (X:_)(_:_)(_:Y) tworzące tę kolumnę. Uwaga dla wnikliwych: Jeśli jedna para jest nieznana (jak w zasadach Permutu), możemy ją wywnioskować zgodnie ze schematem funkcji VMPC (X:A)(A:B)(B+1:Y) i wszystkie pary stają się znane.

Do dzieła!



W pierwszym ruchu weźmy pojedynczy klocek . Oznacza to zgadnięcie pary (2:4).






Gdy parę (2:4) wstawimy do wiersza (2:_)(_:_)(_:4), otrzymamy (2:4)(_:_)(2:4).
Zgodnie ze schematem (X:A)(A:B)(B+1:Y) mamy A=4, B=1, więc (2:4)(4:1)(2:4).
Znamy już obie pary (2:4) , (4:1) tworzące zaznaczoną kolumnę, możemy więc ją wziąć.






Znamy już pary (2:4) , (4:1) . W żadnej kolumnie nie występują one jednak razem.
Weźmy więc kolejny pojedynczy klocek , co oznacza zgadnięcie pary (1:2).






Gdy pary (1:2), (2:4) wstawimy do wiersza (1:_)(_:_)(_:3), otrzymamy (1:2)(2:4)(_:3).
Zgodnie ze schematem (X:A)(A:B)(B+1:Y) odczytujemy B+1=5, więc (1:2)(2:4)(5:3).
Znamy już obie pary (2:4) , (5:3) tworzące zaznaczoną kolumnę, możemy więc ją wziąć.






Gdy pary (5:3), (4:1) wstawimy do wiersza (3:_)(_:_)(_:1), otrzymamy (3:_)(5:3)(4:1).
Zgodnie ze schematem (X:A)(A:B)(B+1:Y) odczytujemy A=5, więc (3:5)(5:3)(4:1).
Znamy wszystkie pary (3:5) , (5:3) , (4:1) tworzące zaznaczoną kolumnę, możemy więc ją wziąć.






Gdy pary (4:1), (1:2), (3:5) wstawimy do wiersza (4:_)(_:_)(_:5),
zgodnie ze schematem (X:A)(A:B)(B+1:Y) otrzymamy (4:1)(1:2)(3:5).
Znamy wszystkie pary (4:1) , (1:2) , (3:5) tworzące zaznaczoną kolumnę, możemy więc ją wziąć.






Gdy pary (5:3), (3:5), (1:2) wstawimy do wiersza (5:_)(_:_)(_:2),
zgodnie ze schematem (X:A)(A:B)(B+1:Y) otrzymamy (5:3)(3:5)(1:2).
Znamy wszystkie pary (5:3) , (3:5) , (1:2) tworzące zaznaczoną kolumnę, możemy więc ją wziąć.




I to już koniec!

Odwracając funkcję VMPC rozegraliśmy partię Permutu.

Odwróciliśmy funkcję VMPC, gdyż znaleźliśmy wszystkie pięć par (1:2), (2:4), (3:5), (4:1), (5:3),
które pasują do szablonu zgodnie ze schematem funkcji VMPC f(f(f(x))+1) - (X:A)(A:B)(B+1:Y):

(1:2)(2:4)(5:3)
(2:4)(4:1)(2:4)
(3:5)(5:3)(4:1)
(4:1)(1:2)(3:5)
(5:3)(3:5)(1:2)

Jednocześnie zgodnie z zasadami gry zbieraliśmy z planszy Permutu symbole ujawnianych kolejno par
aż zebraliśmy wszystkie symbole i ukończyliśmy partię Permutu!