17.06.2017







Projekt VMPC:


Badania nad funkcją VMPC i problemem matematycznym "czy P=NP?"
pieknafunkcja.pl



Aplikacja do szyfrowania danych VMPCrypt
szyfrowanie.com



Gra Permutu na bazie funkcji VMPC
permutu.pl







Zobacz także:


Gra komputerowa Urban



Multimedialne kursy do nauki języka angielskiego
ADL Publishing




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:

VMPC jest najprawdopodobniej najprostszą znaną na świecie funkcją jednokierunkową. Jednokierunkowość polega na tym, że znając wartość funkcji nie da się znaleźć liczb, z jakich ta wartość powstała.

Od 2004 roku prowadzę projekt naukowy, którego celem jest przeprowadzenie dowodu, że funkcja VMPC jest faktycznie jednokierunkowa. Dotychczas na świecie nie udowodniono jednokierunkowości żadnej funkcji. Niektóre funkcje (jak np. problem faktoryzacji liczb będący podstawą algorytmu szyfrowania RSA) są jedynie uznawane za jednokierunkowe, ale brak jest na to formalnego dowodu.

Badania nad ukończeniem dowodu jednokierunkowości funkcji VMPC są obecnie bardzo blisko osiągnięcia celu.

Gdyby udało się dowód ukończyć, rozwiązałoby to jedną z wielkich zagadek matematyki - problemu "czy P=NP". Clay Mathematics Institute (USA) ufundował nawet za jego rozwiązanie nagrodę w wysokości miliona dolarów.

Funkcja jednokierunkowa VMPC jest zastosowana w Technologii Szyfrowania VMPC - jako element Szyfru Strumieniowego VMPC - oraz w Generatorze Liczb Pseudolosowych VMPC-R. Więcej szczegółów o tych algorytmach można znaleźć na stronie www.szyfrowanie.com.




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
zebraliśmy wszystkie symbole i ukończyliśmy partię Permutu!






FSE 2004
Publikacja na konferencji Międzynarodowego Stowarzyszenia Badań Kryptologicznych (IACR) FSE 2004


Konferencje Enigma
Publikacje na Krajowej Konferencji Zastosowań Kryptografii Enigma w Warszawie


WCTT
Nagroda Wrocławskiego Centrum Transferu Technologii przy Politechnice Wrocławskiej


Software Developer's Journal
Rekomendowany projekt magazynu Software Developer's Journal


Copyright © 1999-2017 by Bartosz Żółtak & OHTON EXPO Okna Wrocław
Aktualizacja: 17.06.2017