02.08.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




Odwracanie funkcji VMPC

Tu możesz zobaczyć, jak przebiega obliczanie wartości funkcji VMPC



Co właściwie oznacza, że funkcja jest jednokierunkowa?

Spójrzmy na funkcję "+1". Znając jej wartość (np. 8), wiemy, że argumentem było 7 (bo 7+1=8).

Funkcję "+1" łatwo jest odwrócić, a więc znaleźć argument (7) na podstawie wartości (8).

Funkcja jednokierunkowa to taka, której nie da się łatwo odwrócić, a więc
znając wartość funkcji jednokierunkowej trudno jest znaleźć argument, z którego wartość ta powstała.

Jak dotąd na świecie nie jest znana żadna funkcja, której jednokierunkowość byłaby udowodniona.

VMPC ma szansę być pierwszą taką funkcją.



Aby dostrzec, dlaczego funkcja VMPC f(f(f(x))+1) jest trudna do odwrócenia,
zobaczmy najpierw, jak łatwo można odwrócić funkcję f(f(f(x))).

Przypomnijmy, jak pary wyznaczały wartości funkcji f(f(f(x))):



Funkcja f(f(f(x))) dla liczby 1:

Pary (1:2)(2:6)(6:3) wyznaczyły, że f(f(f(1)))=3.



Funkcja f(f(f(x))) dla liczby 2:

Pary (2:6)(6:3)(3:7) wyznaczyły, że f(f(f(2)))=7.



Zauważmy, że pary (2:6)(6:3)wspólne - wystąpiły w obydwu wartościach: f(f(f(1))) oraz f(f(f(2))).

Czy to przypadek?
Zbierzmy wszystkie siedem wartości funkcji f(f(f(x))):

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



Pary w funkcji f(f(f(x))) układają się według schematu:

(X:A)(A:B)(B:Y)

Wynika z niego, że pary (A:B)(B:Y) z prawej strony wiersza (_:A)(A:B)(B:Y)
pojawią się również z lewej strony w wierszu (A:B)(B:Y)(Y:_).

Na przykład:
(1:2)(2:6)(6:3)
(2:6)(6:3)(3:7)

Własność ta pozwoli łatwo odwrócić funkcję f(f(f(x))).

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

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



Do dzieła! Przed nami 4 identyczne kroki.

  Załóżmy, że pierwszy wiersz jest nam już znany: (1:2)(2:6)(6:3).
Wiemy więc, że wiersz (2:_)(_:_)(_:7) ma postać (2:6)(6:3)(_:7).  
(ponieważ przenieśliśmy pary (2:6)(6:3) z prawej strony na lewą).

Znając schemat (X:A)(A:B)(B:Y) wiemy, że brakującą liczbą jest B=3: (2:6)(6:3)(3:7),
co ujawnia nową parę (3:7).



Znajdźmy kolejną parę - (7:4)

W poprzednim kroku odtworzyliśmy wiersz (2:6)(6:3)(3:7)
  Wiemy więc, że wiersz (6:_)(_:_)(_:4) ma postać (6:3)(3:7)(_:4).

Według schematu (X:A)(A:B)(B:Y) brakującą liczbą jest B=7: (6:3)(3:7)(7:4), co ujawnia parę (7:4).



Teraz znajdźmy parę (4:5)

W poprzednim kroku odtworzyliśmy wiersz (6:3)(3:7)(7:4)
  Wiemy więc, że wiersz (3:_)(_:_)(_:5) ma postać (3:7)(7:4)(4:5), co ujawnia parę (4:5).



A teraz znajdźmy parę (5:1)

W poprzednim kroku odtworzyliśmy wiersz (3:7)(7:4)(4:5)
  Wiemy więc, że wiersz (7:_)(_:_)(_:1) ma postać (7:4)(4:5)(5:1), co ujawnia parę (5:1).



Gotowe!
Funkcja f(f(f(x))) została odwrócona.

Znaleźliśmy siedem par: (1:2), (2:6), (3:7), (4:5), (5:1), (6:3), (7:4),
które pasują do szablonu zgodnie ze schematem funkcji f(f(f(x))) - (X:A)(A:B)(B:Y):

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




Schemat funkcji f(f(f(x))) (X:A)(A:B)(B:Y) gwarantował nam, że dwie pary (w tym jedna nowo ujawniona) z jednego wiersza pojawią się wspólnie w innym wierszu ujawniając kolejną nową parę i tak wkoło aż do ujawnienia wszystkich par.

Gdyby liczb było o 100 więcej, kroków też by było o 100 więcej. Liczba operacji potrzebna do odwrócenia funkcji f(f(f(x))) rośnie liniowo - jedna dodatkowa operacja na każdą dodatkową liczbę.

Funkcja f(f(f(x))) jest więc łatwa do odwrócenia niezależnie od ilości liczb.*1

[*1]  W pierwszym kroku założyliśmy, że znamy pierwszy wiersz (1:2)(2:6)(6:3). Oznacza to, że zgadliśmy w nim dwie pary (1:2) i (2:6), a trzecią parę (6:3) odczytaliśmy zgodnie ze schematem (X:A)(A:B)(B:Y). Istotą łatwości odwrócenia funkcji f(f(f(x))) jest fakt, że po zgadnięciu dwóch par możliwe jest odtworzenie wszystkich pozostałych par bez względu na ilość liczb w tabeli (zakładając, że liczby w tabeli tworzą permutację jednocyklową; jeśli cykli jest więcej, odwrócenie funkcji f(f(f(x))) jest tylko nieco trudniejsze). Przedstawiony tu sposób na odwracanie funkcji f(f(f(x))) został wybrany jako najlepiej oddający istotę jednokierunkowości funkcji VMPC f(f(f(x))+1).









Teraz spróbujmy odwrócić funkcję VMPC



Odwróciliśmy funkcję f(f(f(x))).
Zobaczmy teraz, dlaczego odwrócenie funkcji VMPC f(f(f(x))+1) jest trudne.

Czy dodanie liczby jeden (+1) może powodować skutki na miarę ilości atomów we Wszechświecie...?

Przypomnijmy, jak pary wyznaczały wartości funkcji VMPC f(f(f(x))+1):



Funkcja VMPC f(f(f(x))+1) dla liczby 1:

Pary (1:2)(2:6)(7:4) wyznaczyły, że VMPC f(f(f(1))+1)=4.



Funkcja VMPC f(f(f(x))+1) dla liczby 2:

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



Tylko jedna para (2:6) jest tu wspólna - wystąpiła w obydwu wartościach: f(f(f(1))+1) oraz f(f(f(2))+1).

Dlaczego tylko jedna?
Zbierzmy wszystkie siedem wartości funkcji VMPC f(f(f(x))+1):

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



Przypomnijmy, że pary w funkcji f(f(f(x))) układały się według schematu:

(X:A)(A:B)(B:Y)

Na przykład:
(1:2)(2:6)(6:3)
(2:6)(6:3)(3:7)

Pary (A:B)(B:Y) z prawej strony wiersza (_:A)(A:B)(B:Y)
pojawiały się również z lewej strony w wierszu (A:B)(B:Y)(Y:_).
Własność tę wykorzystaliśmy do szybkiego odwrócenia funkcji f(f(f(x))).



Ale w funkcji VMPC f(f(f(x))+1) pary układają się według innego schematu:

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

Na przykład:
(1:2)(2:6)(7:4)
(2:6)(6:3)(4:5)

Wynika z niego, że pary (A:B)(B+1:Y) z prawej strony wiersza (_:A)(A:B)(B+1:Y) 
nigdy nie pojawią się z lewej strony w wierszu (A:B)(B:Y)(Y+1:_).

Oznacza to, że w funkcji VMPC dwa wiersze zwykle mogą mieć tylko jedną wspólną parę.

Własność ta jest źródłem jednokierunkowości funkcji VMPC,
a jest konsekwencją wystąpienia niewinnej jedynki w definicji funkcji VMPC f(f(f(x))+1).

Zobaczmy teraz, jak przebiega proces odwracania funkcji VMPC.
Odwrócenie tej funkcji 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:_)(_:_)(_:4)
(2:_)(_:_)(_:5)
(3:_)(_:_)(_:1)
(4:_)(_:_)(_:6)
(5:_)(_:_)(_:7)
(6:_)(_:_)(_:2)
(7:_)(_:_)(_:3)




Spróbujmy znaleźć pierwszą parę (4:5)...


Spójrzmy jeszcze raz na wszystkie pary tworzące wartości funkcji VMPC:

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

Załóżmy, że pierwszy wiersz (1:2)(2:6)(7:4) jest nam już znany.
Spróbujmy znaleźć inny wiersz, który używa dwóch spośród par (1:2), (2:6), (7:4)...

Nie ma takiego!

Znaleźć możemy najwyżej wiersz, który używa jednej spośród naszych par, na przykład wiersz (2:6)(6:3)(4:5).

Podczas odwracania funkcji widzimy ten wiersz jako: (2:_)(_:_)(_:5).
Możemy wstawić do niego tylko jedną z naszych par - (2:6).
Zgodnie ze schematem (X:A)(A:B)(B+1:Y) wiersz przyjmie postać: (2:6)(6:_)(_:5).

Aby móc kontynuować, musimy zgadnąć, jaką postać ma para (6:_).
Zgadując mamy niewielkie szanse, że trafimy w prawidłową wartość...

Zgadnijmy prawidłowo: (6:3). Teraz wiersz przyjmuje postać (2:6)(6:3)(_:5).

Zgodnie ze schematem (X:A)(A:B)(B+1:Y) widzimy, że B=3, więc brakującą liczbą jest B+1=4
i wiersz ostatecznie przyjmuje postać (2:6)(6:3)(4:5), co ujawnia parę (4:5).

Znalezienie pary (4:5) kosztowało nas jednak zgadnięcie pary (6:3).



Znajdźmy teraz kolejną parę - (3:7)

W funkcji VMPC zwykle dopiero zestawienie par z dwóch różnych wierszy pozwala dobrać
dwie pary - tu (1:2), (6:3) - które występują wspólnie w którymś nowym wierszu - tu (6:3)(3:7)(1:2).

Z poprzedniego kroku znamy wiersze (1:2)(2:6)(7:4) oraz (2:6)(6:3)(4:5).
Dopiero teraz wiemy, że nowy wiersz (6:_)(_:_)(_:2) ma postać (6:3)(_:_)(1:2).

Możemy go uzupełnić według schematu (X:A)(A:B)(B+1:Y), widząc, że A=3 oraz B+1=1, więc B=7
(B=7, gdyż pamiętamy, że dodawanie wykonujemy modulo 8, więc zamiast 7+1=8 przyjmujemy 7+1=1).

Wiersz ostatecznie przyjmuje postać: (6:3)(3:7)(1:2), co ujawnia parę (3:7).



Znajdźmy ostatnią parę - (5:1)

Z poprzednich kroków znamy wiersze (1:2)(2:6)(7:4) oraz (6:3)(3:7)(1:2).
Wiemy więc, że nowy wiersz (3:_)(_:_)(_:1) ma postać (3:7)(7:4)(_:1).

Możemy go uzupełnić według schematu (X:A)(A:B)(B+1:Y), widząc, że B=4, zatem B+1=5.

Wiersz ostatecznie przyjmuje postać: (3:7)(7:4)(5:1), co ujawnia parę (5:1).



Gotowe!
Funkcja VMPC f(f(f(x))+1) została odwrócona,
ale kosztowało nas to zgadnięcie pary (6:3).

Znaleźliśmy siedem par: (1:2), (2:6), (3:7), (4:5), (5:1), (6:3), (7:4),
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:6)(7:4)
(2:6)(6:3)(4:5)
(3:7)(7:4)(5:1)
(4:5)(5:1)(2:6)
(5:1)(1:2)(3:7)
(6:3)(3:7)(1:2)
(7:4)(4:5)(6:3)




Odwróciliśmy funkcję VMPC dla liczb 1..7 zgadując trzy pary: (1:2), (2:6) oraz (6:3).*1

Para (1:2) mogła przyjąć 7 postaci, para (2:6) - 6 postaci, a para (6:3) - 5 postaci.*2

Mieliśmy zatem 7*6*5 = 210 możliwych kombinacji tych trzech par. Wiedzieliśmy, która jest prawidłowa, gdyż wcześniej sami wyliczyliśmy wartości funkcji, ale podczas prawdziwego odwracania funkcji nie wiemy, która z 210 kombinacji jest prawidłowa.

Cierpliwy człowiek poradziłby sobie jednak z przetestowaniem wszystkich 210 kombinacji.

Ale co by było, gdyby liczb było nie 7, a 15? Wówczas nawet po zgadnięciu jednej pary nie można kontynuować odwracania funkcji. Wciąż nie można bowiem łatwo znaleźć dwóch par występujących wspólnie w nowym wierszu. Niezbędne jest zgadnięcie jeszcze jednej pary.

Pierwsza zgadywana para może mieć 15 postaci, druga 14, trzecia 13, czwarta 12. Wszystkich kombinacji jest więc 15*14*13*12 = 32.760.

Jeśli zwiększymy rozmiar tabeli o kolejne 8 liczb, do 23, zgadnąć będzie trzeba już 5 par. Liczba ich kombinacji wyniesie 23*22*21*20*19 = 4.037.880.

4 miliony operacji to spore wyzwanie dla człowieka, ale komputerowi wciąż zajmie tylko chwilę.

A jeśli w tabeli będzie 100 liczb? Aby odwrócić funkcję VMPC, zgadnąć będzie trzeba 14 par. Ilość ich kombinacji wyniesie 100*99*98*97*96*95*94*93*92*91*90*89*88*87 = 3.852.142.155.961.424.437.432.320.000, czyli ponad 3 kwadryliardy*3. To ponad trzy miliardy miliardów miliardów albo ponad 3-krotność liczby 1 i 27 zer.

Ta liczba na długi czas zajęłaby największe superkomputery świata.

Jeśli więc potasujemy 100 kart do gry, następnie przemieszamy je funkcją VMPC, to odtworzenie pierwotnej kolejności kart zajmie ponad 3 kwadryliardy operacji.

Trudność odwrócenia funkcji VMPC rośnie w nieskończoność: na każde osiem nowych liczb przybywa jedna zgadywana para*4.

Gdyby w tabeli było 1000 liczb, mielibyśmy 127 par do zgadnięcia. Pary te mogą utworzyć 1000*999*998*...*874 = 10377 kombinacji, czyli 1 i 377 zer. To kwadryliardy kwadryliardów razy więcej niż prawdopodobna ilość atomów we Wszechświecie, szacowana na około 10100.

A to wszystko przez niewinną jedynkę w definicji funkcji VMPC f(f(f(x))+1).







[*1]  W pierwszym kroku założyliśmy, że znamy pierwszy wiersz (1:2)(2:6)(7:4). Oznacza to, że zgadliśmy w nim dwie pary (1:2) i (2:6), a trzecią parę (7:4) odczytaliśmy zgodnie ze schematem (X:A)(A:B)(B+1:Y).


[*2]  W wierszu (1:2)(2:6)(7:4) para (1:2) mogła przyjąć 7 postaci: (1:1), (1:2), (1:3), (1:4), (1:5), (1:6), (1:7).
Para (2:6) mogła mieć 6 postaci: (2:1), (2:2). (2:3), (2:4), (2:5), (2:6), (2:7). Postać (2:2), czyli f(2)=2, byłaby sprzeczna z parą (1:2), czyli f(1)=2 (każdy element f musi mieć inną wartość, ponieważ f jest permutacją).
Para (7:4) została ujawniona zgodnie ze schematem (X:A)(A:B)(B+1:Y).
Para (6:3) mogła przyjąć którąś z 4 postaci niesprzecznych z poprzednimi trzema parami - (1:2), (2:6), (7:4) - czyli: (6:1), (6:3), (6:5), (6:7). Ogólnie - liczba możliwych postaci nowej pary maleje o 1 z każdą ujawnioną parą, co wynika z faktu, że f jest permutacją. Zjawisko zostało tu uproszczone dla klarowniejszego przedstawienia istoty funkcji VMPC i przyjęto, że para (6:3) miała 5 (a nie 4) możliwych postaci. Uproszczenie to nie wpływa w znaczący sposób na zilustrowaną trudność odwrócenia funkcji VMPC. Zjawisko to jest uwzględnione bez uproszczeń dopiero w badaniach naukowych.


[*3]  kwadryliard to 1027, czyli 1 i 27 zer.


[*4]  Dla wnikliwych. W funkcji VMPC mogą wystąpić sytuacje, w których dwie pary użyte w jednym wierszu występują wspólnie w innym wierszu, np. (2:6)(6:3)(4:5) oraz (4:5)(5:1)(2:6). Sytuacje takie ułatwiają odwracanie funkcji poprzez ujawnienie jednej nowej pary bez konieczności zgadywania innej. Jednak o ile występowanie takich sytuacji w funkcji f(f(f(x))) było gwarantowane, co pozwoliło na łatwe jej odwrócenie, o tyle w funkcji VMPC sytuacje takie występują tylko przypadkowo i sporadycznie. Nie wpływają one w znaczący sposób na zilustrowaną trudność odwrócenia funkcji VMPC. Zostały tu pominięte, aby umożliwić klarowniejsze przedstawienie istoty funkcji VMPC. Sytuacje te są uwzględnione dopiero w badaniach naukowych.


Zobacz formalną definicję funkcji VMPC i problemu jej odwracania








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: 02.08.2017