|
|
Obliczanie wartości funkcji VMPC
(nieformalna ilustracja na przykładzie)
Tu możesz zobaczyć, jak przebiega odwracanie funkcji VMPC
Niech f oznacza 7-elementową permutację.
Mówiąc obrazowo, permutacja to ciąg kolejnych, ale potasowanych liczb.
Przykładowo: f(1)=2, f(2)=6, f(3)=7, f(4)=5, f(5)=1, f(6)=3, f(7)=4,
co czytamy: "f od 1 równa się 2", "f od 2 równa się 6", itd.
Funkcja VMPC przekształca dowolną permutację f w inną permutację g, określoną wzorem g(x)=f(f(f(x))+1),
w omawianym przykładzie dla x=1,2,3,4,5,6,7.
Funkcję VMPC możemy obliczyć dla permutacji dowolnej wielkości. Permutacja może zatem mieć 7 elementów (jak tu),
ale także np. 15 czy milion elementów.
Istotą funkcji VMPC jest fakt, że trudność jej odwrócenia, czyli znalezienia permutacji f na podstawie permutacji g,
rośnie gwałtownie (niewielomianowo) wraz ze wzrostem wielkości permutacji. Podczas gdy dla 10-elementowej permutacji
domowy komputer odwróci funkcję VMPC w mgnieniu oka, to dla 100-elementowej permutacji zajęłoby mu to już ponad 10 miliardów lat.
Istotę funkcji VMPC f(f(f(x))+1) najłatwiej dostrzec, gdy porównamy ją z funkcją f(f(f(x))).
Rysunek poniżej ilustruje funkcję f(f(f(x))) dla liczby x=1:
Na górze mamy kolejne liczby: 1 2 3 4 5 6 7.
Na dole te same liczby są potasowane: 2 6 7 5 1 3 4.
Linia pionowa | łączy w parę liczbę na górze z liczbą pod nią, np. (1:2).
Linia ukośna / łączy liczbę na górze z taką samą liczbą na dole, np. (2/2).
Aby obliczyć wartość funkcji, wystarczy podążać za niebieską linią.
Zaczynamy od liczby 1 na górze. Pod 1 leży 2.
Idziemy ukośną linią / do liczby 2 na górze. Pod 2 leży 6.
Idziemy ukośną linią / do liczby 6 na górze. Pod 6 leży 3.
I to już koniec! Funkcja f(f(f(x))) dla liczby x=1 ma wartość 3.
A teraz zobaczmy na funkcję VMPC f(f(f(x))+1) dla liczby x=1:
Pierwsze kroki są identyczne:
Zaczynamy od liczby 1 na górze. Pod 1 leży 2.
Idziemy ukośną linią / do liczby 2 na górze. Pod 2 leży 6.
Idziemy ukośną linią / do liczby 6 na górze...
Tu następuje różnica.
Pojawia się jedynka, która jest istotą funkcji VMPC f(f(f(x))+1).
Do 6 dodajemy 1. Otrzymujemy 7.
Pod 7 leży 4.
Gotowe! Funkcja VMPC f(f(f(x))+1) dla liczby x=1 ma wartość 4.
I to już wszystko! To jest cała funkcja VMPC.
Dalsze obliczenia są analogiczne, a niezwykłe własności funkcji są tylko konsekwencją tej niepozornej jedynki.
Obliczmy wartość funkcji f(f(f(x))) dla liczby x=2:
Zaczynamy od liczby 2 na górze.
Pod 2 leży 6, czyli (2:6).
Idziemy ukośną linią / do 6 na górze. Pod 6 leży 3, czyli (6:3).
Idziemy ukośną linią \ do 3 na górze. Pod 3 leży 7, czyli (3:7).
Pary (2:6)(6:3)(3:7) wyznaczyły, że
funkcja f(f(f(x))) dla liczby x=2 ma wartość 7,
czyli f(f(f(2)))=7.
A teraz obliczmy wartość funkcji VMPC f(f(f(x))+1) dla liczby x=2:
Zaczynamy od liczby 2 na górze.
Pod 2 leży 6, czyli (2:6).
Idziemy ukośną linią / do 6 na górze. Pod 6 leży 3, czyli (6:3).
Idziemy ukośną linią \ do 3 na górze...
Do 3 dodajemy 1. Otrzymujemy 4.
Pod 4 leży 5, czyli (4:5).
Pary (2:6)(6:3)(4:5) wyznaczyły, że
funkcja VMPC f(f(f(x))+1) dla liczby x=2 ma wartość 5,
czyli f(f(f(2))+1)=5.
Funkcja f(f(f(x))) dla liczby x=3:
Pary (3:7)(7:4)(4:5) wyznaczyły, że
f(f(f(3)))=5.
Funkcja VMPC f(f(f(x))+1) dla liczby x=3:
Pary (3:7)(7:4)(5:1) wyznaczyły, że
VMPC f(f(f(3))+1)=1.
Funkcja f(f(f(x))) dla liczby x=4:
Pary (4:5)(5:1)(1:2) wyznaczyły, że
f(f(f(4)))=2.
Funkcja VMPC f(f(f(x))+1) dla liczby x=4:
Pary (4:5)(5:1)(2:6) wyznaczyły, że
VMPC f(f(f(4))+1)=6.
Funkcja f(f(f(x))) dla liczby x=5:
Pary (5:1)(1:2)(2:6) wyznaczyły, że
f(f(f(5)))=6.
Funkcja VMPC f(f(f(x))+1) dla liczby x=5:
Pary (5:1)(1:2)(3:7) wyznaczyły, że
VMPC f(f(f(5))+1)=7.
Funkcja f(f(f(x))) dla liczby x=6:
Pary (6:3)(3:7)(7:4) wyznaczyły, że
f(f(f(6)))=4.
Funkcja VMPC f(f(f(x))+1) dla liczby x=6:
7+1=8. Ale w tabeli mamy liczby od 1 do 7.
Co zrobić?
Dodawanie faktycznie odbywa się "modulo 8", co oznacza, że zamiast liczby 8 przyjmujemy liczbę 1.
Pary (6:3)(3:7)(1:2) wyznaczyły, że
VMPC f(f(f(6))+1)=2.
Funkcja f(f(f(x))) dla liczby x=7:
Pary (7:4)(4:5)(5:1) wyznaczyły, że
f(f(f(7)))=1.
Funkcja VMPC f(f(f(x))+1) dla liczby x=7:
Pary (7:4)(4:5)(6:3) wyznaczyły, że
VMPC f(f(f(7))+1)=3.
Zbierzmy wszystkie siedem wartości funkcji f(f(f(x))), które obliczyliśmy:
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
A tu 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
Zobacz teraz, jak przebiega odwracanie funkcji VMPC
|
|
|
|
Publikacja na konferencji Międzynarodowego Stowarzyszenia Badań Kryptologicznych (IACR) FSE 2004
|
|
Publikacje na Krajowej Konferencji Zastosowań Kryptografii Enigma w Warszawie
|
|
Nagroda Wrocławskiego Centrum Transferu Technologii przy Politechnice Wrocławskiej
|
|
Rekomendowany projekt magazynu Software Developer's Journal
|
|
|