|
|
|
|
Próbujemy zgłębić wielką zagadkę matematyki:
Projekt badawczy "Funkcja VMPC - czy P=NP?"
www.szyfrowanie.com/p
Bartosz Żółtak
1. Cel projektu
2. Aktualności
3. Jak działa funkcja VMPC
4. Dlaczego funkcja VMPC prawdopodobnie jest jednokierunkowa
5. Publikacje
6. Szczegółowy opis funkcji VMPC (język angielski)
7. Kontakt
1. Cel projektu
Pytanie, czy P=NP, jest jedną z wielkich zagadek matematyki.
Clay Mathematics Institute
z USA zaliczył ją do grupy siedmiu Problemów Milenijnych.
Za rozwiązanie każdego z nich Instytut ufundował nagrodę w wysokości miliona dolarów.
Pytanie, czy P=NP, ma złożoną matematyczną definicję, ale jego istota sprowadza się do pytania,
czy istnieją w przyrodzie problemy, których rozwiązanie jest trudne do znalezienia,
ale łatwe do sprawdzenia.
Od dziesięcioleci żadnego problemu takiego nie znaleziono.
Nie udało się także udowodnić, że problemu takiego nie ma...
Teoretycznie problemem takim mogłoby być odwracanie funkcji jednokierunkowej.
Funkcja jednokierunkowa to takie przekształcenie, które łatwo wykonać (obliczyć wartość na podstawie argumentu),
ale trudno odwrócić (znaleźć argument na podstawie wartości).
Nie wiadomo jednak, czy funkcje jednokierunkowe w ogóle istnieją...
Jeśli udałoby się znaleźć choć jedną, wielka zagadka zostałaby rozwiązana -
wykazalibyśmy, że P jest różne od NP, a milenijny problem Instytutu Clay'a zostałby rozstrzygnięty.
W 1998 roku odkryłem pewne przekształcenie matematyczne.
Okazało się ono tak ciekawe, że do dziś, nieprzerwanie od 10 lat, zajmuję się jego badaniem.
W 2004 roku zostałem zaproszony do zaprezentowania go na prestiżowej międzynarodowej konferencji naukowej FSE,
na którą mój wyjazd sponsorowała Kancelaria Prezydenta RP oraz Prezydent Wrocławia.
Przekształcenie to nazwałem jako "funkcja VMPC".
Funkcję tę wyróżniają dwie wyraźne cechy: ma ona niezwykle prostą budowę oraz
zgodnie z wszelką posiadaną przeze mnie wiedzą - jest właśnie funkcją jednokierunkową...
Funkcja VMPC - odkryta w Polsce, przez Polaka - czy okaże się pierwszą na świecie funkcją jednokierunkową?
Aby tak się stało, potrzebny jest matematyczny dowód jej jednokierunkowości.
Próba zbudowania takiego dowodu jest celem tego projektu.
- "I tak nikomu dotychczas nie dało się udowodnić, że jakakolwiek funkcja jest jednokierunkowa, więc tu na pewno też się nie uda",
mówi zdecydowana większość matematyków.
- "Jeśli czegoś nie da się zrobić, potrzebny jest ktoś, kto o tym nie wie - i on to zrobi", mawiał Albert Einstein.
Nazywam się Bartosz Żółtak i wierzę całym sercem i umysłem, że
możliwe jest udowodnienie, że funkcja VMPC jest jednokierunkowa.
Nie wiem, czy wystarczy mi życia, aby zdążyć tego dowieść. Jeśli nie, jestem przekonany, że w ciągu 100 lat
dokona tego ktoś inny.
2. Aktualności
22.07.2008 - Uruchomienie strony poświęconej projektowi
3. Jak działa funkcja VMPC
Nazwa funkcji pochodzi z angielskiego: Variably Modified Permutation Composition, czyli zmiennie modyfikowane złożenie permutacji.
Funkcja VMPC to pewne przekształcenie permutacji. Permutacja to ciąg potasowanych kolejnych liczb.
(2,0,3,4,1) to przykładowa permutacja. Nazwijmy tę jako "F".
VMPC przekształci permutację "F" w nową permutację "FF", wg
następującego algorytmu, określonego wzorem FF(x) = F(F(F(x))+1):
Wartość funkcji VMPC obliczamy w czterech krokach:
krok 1) 0 przechodzi w 2. Odczytujemy to z tabeli - pozycja 0 przechodzi w liczbę 2.
krok 2) 2 przechodzi w 3. Sprawdziliśmy, w co przechodzi liczba uzyskana w poprzednim kroku (liczba 2).
krok 3) 3+1=4. Krok najprostszy, a zarazem najważniejszy i najbardziej tajemniczy.
To ten krok nadaje funkcji niezwykłych właściwości...
krok 4) 4 przechodzi w 1 - odczytujemy z tabeli, w co przechodzi liczba uzyskana w poprzednim kroku (liczba 4).
Obliczyliśmy właśnie pierwszy element funkcji VMPC! Wiemy już, że permutacja FF będzie miała postać FF=(1, ?,?,?,?).
Powyższe cztery kroki powtarzamy teraz dla pozostałych czterech
pozycji (zaczynamy "skakanie" po tabeli od pozycji 1, potem od 2,3 oraz 4) i gotowe! Otrzymujemy wynik, że
funkcja VMPC dla permutacji F=(2,0,3,4,1) ma wartość FF=(1,4,2,3,0).
4. Dlaczego funkcja VMPC prawdopodobnie jest jednokierunkowa
Uwaga. Poniższy tekst nie jest ścisły matematycznie.
Jego celem jest przedstawienie istoty funkcji w sposób zrozumiały dla możliwie najszerszego grona czytelników.
Fizyk Richard Feynman mawiał, że naukowiec, który nie potrafi wytłumaczyć przedmiotu swoich badań 8-latkowi, jest szarlatanem...
Do głębszej analizy funkcji zapraszam do
rozdziału 6. Szczegółowy opis funkcji VMPC (język angielski)
oraz do rozdziału 5. Publikacje, gdzie można zapoznać się
z pracą o funkcji VMPC opublikowaną na konferencji FSE'04 oraz z innym publikacjami naukowymi.
Popatrzmy na początku na funkcję FF(x)=F(F(F(x))), która różni się od VMPC tylko brakiem dodania jedynki w
kroku 3.
Niech dwa przykładowe elementy permutacji FF mają tu postać:
FF(7) = (7→9, 9→5, 5→2) oraz FF(9) = (9→5, 5→2, 2→4).
Zauważmy, że dwa elementy permutacji F - 9→5 oraz 5→2 - występują zarówno w FF(7), jak i w FF(9).
Możemy wykorzystać ten fakt do odwracania funkcji.
Załóżmy, że element FF(7) = (7→9, 9→5, 5→2) jest ujawniony.
Wtedy jak po sznurku możemy dojść do nowego elementu FF(9) = (9→5, 5→2, 2→4),
ponieważ znamy dwa (9→5 i 5→2) z trzech elementów F, które tworzą FF(9).
Mając tak namierzony FF(9) odczytujemy z niego trzeci - nowy - element permutacji F (2→4).
Dalej postępujemy analogicznie - namierzamy jak po sznurku kolejne elementy FF i odczytujemy z nich
nowe elementy F aż do ujawnienia całej permutacji F.
W przypadku funkcji VMPC=F(F(F(x))+1) sytuacja wygląda inaczej.
W wyniku operacji dodania liczby 1
trudno jest znaleźć dwa elementy F, które występują razem w dwóch różnych elementach FF, jak było to możliwe powyżej.
W funkcji VMPC elementy F rozchodzą się bowiem w permutacji FF jak po pajęczynie.
Załóżmy, że jeden element FF ma postać
FF(7) = (7→9, 9→5, 6→1). Trudno jest znaleźć nowy element FF, który używałby
dwóch spośród tych trzech elementów F.
Zwykle znaleźć można najwyżej taki element FF, który używa tylko jednego z nich.
Np. FF(9) = (9→5, 5→2, 3→0).
Wartość jednego z dwóch brakujących elementów F (np. 5→2) trzeba zgadnąć.
Dopiero wtedy można odczytać wartość drugiego (3→0)...
Zgadywanie trzeba powtarzać zwykle dla każdego kolejnego elementu FF.
Jeśli zgadnięcie okaże się błędne, trzeba zmienić albo je albo któreś z wcześniejszych zgadnięć.
Liczba możliwych kombinacji rośnie bardzo szybko. A zwykle jest tylko jedna prawidłowa kombinacja, na którą trzeba trafić...
Stąd bierze się trudność odwracania funkcji VMPC.
Jeśli uda się matematycznie udowodnić, że te zgadnięcia są niezbędne, funkcja VMPC okaże się faktycznie
jednokierunkowa, a wielki problem - czy P=NP - rozwiązany.
Mimo że przeprowadzenie takiego dowodu jest trudnym zadaniem, to wierzę, że jest to możliwe.
Wszystkie dotychczasowe badania oraz intuicja mówią, że tak jest.
Będę dążył do tego z wielką determinacją.
Tak, nikt dotychczas nie udowodnił jednokierunkowości jakiejkolwiek funkcji...
Jednak dopiero od niedawna znana jest funkcja
prawdopodobnie-jednokierunkowa o tak prostej budowie - odkryta w Polsce funkcja VMPC.
5. Publikacje
1) VMPC One-Way Function and Stream Cipher, Bartosz Żółtak.
Międzynarodowa konferencja kryptograficzna
Fast Software Encryption (FSE),
Delhi, Indie, 5-7 lutego 2004. Publikacja w Springer LNCS nr 3017, 2004.
Mój wyjazd na konferencję sponsorowany był przez Kancelarię Prezydenta Rzeczpospolitej Polskiej
oraz przez Prezydenta Wrocławia. Pobierz pracę.
2) On inverting the VMPC one-way function, Kamil Kulesza, University of Cambridge.
Informacja,
cała praca.
3) On inverting the VMPC one-way function, Kamil Kulesza, Wystąpienie na seminarium
Zakładu Złożoności Obliczeniowej i Algorytmów Instytutu Matematycznego Uniwersytetu Wrocławskiego, 21.05.2008.
Informacja.
4) Funkcja jednokierunkowa i szyfr strumieniowy VMPC, Bartosz Żółtak. Seminarium Kryptologiczne w Instytucie Matematycznym Polskiej Akademii Nauk, sala 106, Warszawa, 18.03.2004.
Informacja.
5) Some Words on Cryptanalysis of Stream Ciphers, Alexander Maximov. Praca doktorska, Department of Information Technology, Lund University, Szwecja, strony 127-144, 16.06.2006.
6) Funkcja jedokierunkowa VMPC i system uwierzytelnionego szyfrowania VMPC-Tail-MAC,
Bartosz Żółtak. Krajowa Konferencja Zastosowań Kryptografii
Enigma 2004,
Warszawa, 10-13.05.2004.
7) Rok w kryptoanalizie VMPC, schemat uwierzytelnionego szyfrowania VMPC-MAC oraz algorytm VMPC-HASH",
Bartosz Żółtak. Krajowa Konferencja Zastosowań Kryptografii
Enigma 2005,
Warszawa, 30.05-02.06.2005.
8) VMPC - szyfr oparty o permutacje, Dobromir Matusiewicz, 2. Warsztaty Kryptograficzne organizowane przez Katolicki Uniwersytet Lubelski, 14-15.05.2004.
9) Funkcja jednokierunkowa i szyfr strumieniowy VMPC, Bartosz Żółtak, artykuł w magazynie komputerowym
SOFTWARE 2.0 (obecnie Software Developer's Journal).
numer 9 (117), wrzesień 2004, strony 26-29. Okładka magazynu.
Skontaktuj się z nami w sprawie projektu!
Tel. (Bartosz Żółtak): +48 888 422 122
Formularz zapytania:
|
