VMPC

VMPC (ang. Variably Modified Permutation Composition; zmiennie modyfikowane złożenie permutacji) – funkcja jednokierunkowa oraz algorytm szyfrowania opracowane przez Bartosza Żółtaka i opublikowane przez autora na międzynarodowej konferencji kryptograficznej Fast Software Encryption w 2004 (FSE 2004).

Funkcja VMPC to proste przekształcenie permutacji, które - najprawdopodobniej - jest funkcją jednokierunkową, a więc taką, której wartość jest łatwo obliczyć dla dowolnego argumentu, ale trudno jest znaleźć argument na podstawie wartości.

Dotychczas nie jest na świecie znana żadna funkcja jednokierunkowa, której jednokierunkowość została udowodniona. Nie inaczej jest w przypadku VMPC - formalnie jest to kandydatka na funkcję jednokierunkową. Udowodnienie jednokierunkowości jakiejkolwiek funkcji rozwiązałoby sławny problem informatyki teoretycznej - czy P=NP - rozstrzygając, że P≠NP.

Definicja funkcji VMPC dla n-elementowej permutacji f jest następująca:

$g(x) = \operatorname{VMPC}(f(x)) = f(f(f(x))+1) \pmod n\;$

Przekształcenie to - mimo prostej budowy - okazuje się trudne do odwrócenia. Symulacje komputerowe pokazują, że znalezienie permutacji f na podstawie permutacji g dla 16-elementowej permutacji zajmuje około 2¹¹ operacji (ok. 2000), dla 64-elementowej permutacji - około 2⁵³ operacji (ok. 9 biliardów, czyli "9" i 15 zer), a dla 256-elementowej permutacji - około 2²⁶⁰ operacji (ok. "1" i 78 zer).

Wraz z funkcją VMPC na konferencji FSE 2004 opublikowany został algorytm szyfrowania danych bazujący na funkcji VMPC. Jest to szyfr strumieniowy charakteryzujący się dużą wydajnością w implementacjach programowych. Jego budowa - podobnie jak funkcji VMPC - jest bardzo prosta. Algorytm działania szyfru VMPC pozwalający zaszyfrować L-znakową (bajtową) informację przedstawia się następująco:

 1. n = 0
 2. Powtarzaj kroki 3-6 L razy:
 3. s = P[ (s + P[n]) mod 256 ]
 4. Output = P[ (P[P[s]]+1) mod 256 ]
 5. Temp = P[n]
    P[n] = P[s]
    P[s] = Temp
 6. n = (n + 1) mod 256

gdzie P (256-elementowa permutacja) i s (1-bajtowa zmienna) są uzyskane z hasła szyfrującego wg algorytmu VMPC-KSA (VMPC Key Scheduling Algorithm). Implementację VMPC-KSA, a także algorytmu VMPC-MAC, pozwalającego na tworzenie kodów uwierzytelniających wiadomość (Message Authentication Code) dla danych szyfrowanych szyfrem VMPC, można znaleźć na stronie domowej projektu VMPC.

Linki zewnętrzne

• Strona domowa projektu VMPC opisująca funkcję VMPC oraz szyfrowanie algorytmem VMPC
• Kamil Kulesza: On inverting the VMPC one-way function