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




Formalna definicja funkcji VMPC i problemu jej odwracania



VMPC to skrót od Variably Modified Permutation Composition (Zmiennie Modyfikowane Złożenie Permutacji).*1

Funkcja VMPC jest przekształceniem permutacji P według wzoru:

V(x)=(P ∘ M2 ∘ P ∘ M1 ∘ P)(x)

dla x ∈ {0,1,...,N-1}, gdzie P i V są permutacjami zbioru {0,1,...,N-1};
M1 i M2 są dowolnymi permutacjami takimi, że M1(x) ≠ M2(x) dla każdego x ∈ {0,1,...,N-1}.

Przykład funkcji VMPC dla M1(x)=x oraz M2(x)=(x+1) modulo N:

V(x)=P(P(P(x))+1)
przyjmując, że + oznacza dodawanie modulo N.

Co to znaczy, że funkcja jest jednokierunkowa? Ogólnie - jej odwrócenie, a więc znalezienie argumentów (permutacji P) na podstawie wartości (permutacji V), jest obliczeniowo niewykonalne.

W funkcji VMPC permutacje M1 i M2 zakłócają strukturę cykli permutacji P, w wyniku czego podczas obliczania wartości V(x)=P(M2(P(M1(P(x))))) elementy permutacji P zostają rozlokowane w poszczególnych elementach permutacji V (każdy element V używa dwóch lub trzech elementów P) w sposób przypominający losowy. W efekcie nie ma niezawodnego sposobu na znalezienie dwóch elementów V, które używają dwóch wspólnych elementów P. Odtworzenie P na podstawie V możliwe jest dopiero po zgadnięciu pewnej (zależnej od N) liczby elementów P. Odwrócenie funkcji VMPC sprowadza się do przeszukania wszystkich możliwych kombinacji tych zgadywanych elementów.

Odwracanie funkcji VMPC przypomina znajdowanie części wspólnych N zbiorów zawierających po 3 losowo wybrane liczby spośród {0,1,...,N-1}. Nie ma niezawodnego sposobu na wybranie zbioru, w którym znajdują się dwie liczby występujące również w innym zbiorze.

Permutacje M1 i M2, gdzie M1(x) ≠ M2(x), decydują o jednokierunkowości funkcji VMPC. Każde wystąpienie M1(x)=M2(x) (wbrew definicji) osłabia jednokierunkowe własności funkcji. Zwykłe złożenie permutacji C(x)=P(P(P(x))) jest funkcją łatwą do odwrócenia. Możemy ją zapisać w terminologii VMPC przy pomocy M1(x)=M2(x)=x. Funkcja D(x)=P(P(P(x)+1)+1), gdzie M1(x)=M2(x)=(x+1) modulo N byłaby tak łatwa do odwrócenia jak C(x)=P(P(P(x))).



Z przeprowadzonych badań wynika, że liczba elementów permutacji P, których zgadnięcie jest niezbędne do odwrócenia funkcji VMPC, rośnie liniowo ze wzrostem rozmiaru permutacji - o 1 zgadywany element na każde 8 elementów permutacji.

Przekłada się to na przybliżony wzór na średnią ilość obliczeń K niezbędną do odwrócenia funkcji VMPC:

K=N! / (N*0,875)!

Powtórzmy, jest to wzór przybliżony, który oddaje istotę zjawiska i rząd wielkości liczby K. Wzór jest określony dla N podzielnych przez 8.



Jednokierunkowość funkcji precyzyjniej definiujemy następująco: Funkcja VMPC byłaby jednokierunkowa, gdyby średnia ilość obliczeń niezbędna do odtworzenia N-elementowej losowo wybranej permutacji P na podstawie permutacji V była niewielomianowym przekształceniem liczby N.

Obrazowo - przekształcenie niewielomianowe to takie, którego wartości gwałtownie rosną. Intuicyjnie sens definicji jest taki, że funkcja jednokierunkowa to taka, której trudność odwrócenia (mierzona ilością obliczeń) rośnie gwałtownie (niewielomianowo) ze wzrostem wielkości zadania (u nas - ze wzrostem rozmiaru permutacji P mierzonego liczbą N).

Gdyby odwrócenie funkcji wymagało średnio np. N100 obliczeń, to mimo że jest to liczba ogromna, funkcja taka nie byłaby jednokierunkowa, gdyż N100 jest przekształceniem wielomianowym.

Dopiero gdyby odwrócenie funkcji wymagało średnio np. 2N albo N! obliczeń, funkcja taka byłaby jednokierunkowa, bowiem funkcja potęgowa (2N) czy silnia (N!) są przekształceniami niewielomianowymi.

Zawsze da się znaleźć odpowiednio duże N, dla którego wartość przekształcenia niewielomianowego (np. N!) jest większa niż wartość przekształcenia wielomianowego Na.



Szacowana średnia ilość obliczeń niezbędna do odwrócenia funkcji VMPC K=N!/(N*0,875)! jest przekształceniem niewielomianowym. Aby to zilustrować, porównajmy jego wartości z wartościami przykładowego wielomianowego przekształcenia Y=N100.

Wzór K=N! / (N*0,875)! opisuje iloczyn N/8 kolejnych liczb: N*(N-1)*(N-2)*...*(N*7/8+1).

Dla małych N liczba Y będzie znacznie większa od K:

Dla N=16 mamy: Y=16100=10120,4, natomiast K=16!/14!=16*15=240

Wartość Y to ponad 1 i 120 zer, a nasze "wielkie niewielomianowe" K ma wartość zaledwie 240. Zwiększmy jednak N:

Dla N=808 mamy: Y=808100=10290,7, natomiast K=808!/707!=808*807*...*708=10290,8

Dla N=808 wartość K=10290,8, która jest tu iloczynem 101 liczb, przewyższyła już wartość Y=10290,7 (będącą zawsze iloczynem 100 liczb). Jeśli zwiększymy N jeszcze bardziej:

Dla N=1000 mamy: Y=1000100=10300, natomiast K=1000!/875!=1000*999*...*876=10371,4

Dla N=1000 wartość K jest już 1071,4 (ponad sto biliardów kwadryliardów kwadryliardów) razy większa niż Y. K jest tu iloczynem 125 liczb, a Y wciąż pozostaje iloczynem 100 liczb. Niewielomianowa wartość K będzie się coraz bardziej oddalać od wielomianowego Y dla coraz większych N.



Wyniki symulacji odwracania funkcji VMPC wykonanych przy pomocy różnych algorytmów ostatecznie prowadzą do takich samych wyników, zaprezentowanych w tabeli poniżej. Tabela pokazuje ilości elementów permutacji P, których zgadnięcie jest konieczne, oraz wynikające z nich średnie ilości obliczeń niezbędne do odwrócenia funkcji VMPC dla kilku przykładowych rozmiarów permutacji:

N: rozmiar permutacji G: liczba zgadywanych elementów L: średnia ilość obliczeń R = (G-2) / N
8 3 25,5 1/8 = 0,125
16 4 211,5 1/8 = 0,125
32 6 224 1/8 = 0,125
64 10 253 1/8 = 0,125
128 18 2117 1/8 = 0,125
256 34 2260 1/8 = 0,125


Średnie ilości obliczeń wynikające z symulacji (kolumna L w tabeli) są nieco większe od wartości szacowanych niewielomianowym wzorem K=N! / (N*0,875)!. Wynika to z faktu, że wzór nie uwzględnia pierwszych dwóch zgadywanych elementów P (np. dla N=8 wzór zwraca wartość K=8, co odpowiada jednemu zgadywanemu elementowi, podczas gdy wg symulacji dla N=8 zgadywane są 3 elementy P). W wyniku tego uproszczenia wzór ma klarowniejszą postać, a odwrócenie funkcji jest jeszcze trudniejsze niż wzór podaje.





Obecne badania są bardzo blisko osiągnięcia ostatecznego celu, którym jest udowodnienie, że funkcja VMPC jest jednokierunkowa. Dowód będzie stwierdzał, że średnia ilość obliczeń niezbędna do odwrócenia funkcji VMPC jest niewielomianowym przekształceniem liczby N bez względu na zastosowany algorytm odwracania funkcji.

Będzie to oznaczać rozwiązanie problemu "czy P=NP" przez wykazanie, że P ≠ NP, co jest konsekwencją istnienia funkcji jednokierunkowej.

Jak dotąd nie jest bowiem znana na świecie żadna funkcja jednokierunkowa - taka, której jednokierunkowość byłaby udowodniona, a nie tylko domniemana.

Funkcja VMPC byłaby pierwszą taką funkcją.







*1. Skąd pochodzi nazwa funkcji VMPC - Variably Modified Permutation Composition
      (Zmiennie Modyfikowane Złożenie Permutacji)?
  • P oznacza permutację.
  • P(P(P(x))) to złożenie permutacji, czyli jedna z podstawowych operacji na permutacjach.
  • P(M(P(M(P(x))))) to modyfikowane złożenie permutacji - elementy permutacji podczas składania są modyfikowane przez dodatkową permutację M.
  • P(M2(P(M1(P(x))))) to Zmiennie Modyfikowane Złożenie Permutacji. Elementy permutacji podczas składania są modyfikowane przez dwie różne permutacje M1 i M2. Jest to funkcja VMPC.







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