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




Generator liczb pseudolosowych VMPC-R



Źródłowa praca naukowa opisująca algorytm VMPC-R:

Implementacje algorytmu VMPC-R:



Algorytm VMPC-R jest kryptograficznie bezpiecznym generatorem liczb pseudolosowych (Cryptographically Secure Pseudo-Random Number Generator - CSPRNG). Stanowi element Technologii Szyfrowania VMPC. Badania nad algorytmem oraz jego dokumentację ukończyłem w 2012 roku. Podobnie jak szyfr strumieniowy VMPC wykorzystuje on funkcję jednokierunkową VMPC jako źródło dodatkowej warstwy bezpieczeństwa kryptograficznego.

Stworzenie algorytmu było możliwe dzięki bezinteresownej pomocy ponad 100 ochotników, którzy użyczyli mocy obliczeniowej swoich komputerów do przeprowadzenia badań statystycznych nad nowym algorytmem.

Zobacz dziennik z przebiegu badań podczas tworzenia VMPC-R z 2010

Algorytm VMPC-R opublikowałem w elektronicznym archiwum ePrint Międzynarodowego Stowarzyszenia Badań Kryptologicznych IACR w roku 2013.



Prawdziwa losowość, zwłaszcza w dużych ilościach i na żądanie, jest w przyrodzie trudna do uzyskania. Jednocześnie wiele badań i symulacji wymaga dużych porcji losowych liczb. Skąd więc szybko wziąć np. 100 miliardów losowych liczb? Gdybyśmy rzucali monetą (reszka=1, orzeł=0), 100 miliardów 8-bitowych liczb (z zakresu {0,1,...,255}) zebralibyśmy po 800 miliardach rzutów. Wykonując jeden rzut na sekundę zajęłoby nam to... ponad 25 tysięcy lat.

Do badań najczęściej wystarczą liczby wyglądające na losowe, czyli pseudolosowe. Wyglądają "tak samo" jak losowe (nie da się ich odróżnić od idealnie losowych), ale pochodzą ze źródła deterministycznego - z algorytmu - generatora liczb pseudolosowych. Wymagania dla takiego algorytmu są bardzo duże, gdyż musi on generować liczby jednocześnie wyglądające na chaotyczne, a z drugiej strony zgodne z teoretycznym modelem prawdopodobieństwa.

Dla przykładu ciąg liczb 0 1 0 1 0 1... nie jest losowy, gdyż prawdopodobieństwo, że dwie sąsiednie liczby są równe wynosi zero, a powinno wynosić 50%. Ciąg 0 1 0 0 1 0 pod tym względem wyglądałby lepiej. Idealny generator liczb pseudolosowych powinien generować ciąg, w którym wszelkie możliwe sytuacje pojawiają się z częstotliwością zgodną z teoretycznym modelem prawdopodobieństwa dla zjawiska losowego.

Algorytm VMPC-R w dużej mierze powstał metodą ewolucji. Kolejne modyfikacje algorytmu były wprowadzane i weryfikowane w testach statystycznych. Jeśli zmierzone częstotliwości odbiegały od modelu losowego, algorytm był ponownie modyfikowany.

W projekt zaangażowało się ponad 100 ochotników, którzy bezinteresownie wykonywali testy statystyczne na swoich komputerach.

W całym projekcie w około miesiąc wspólnie wykonaliśmy obliczenia, które na jednym komputerze pracującym non-stop 24 godziny na dobę zajęłyby 2 lata.

Zobacz dziennik z przebiegu tych badań, pisany spontanicznie w 2010

Dzięki pomocy zaangażowanych osób i po przetestowaniu ponad 200 ewolucyjnych etapów powstała finalna wersja algorytmu VMPC-R, która przeszła pomyślnie wszystkie testy.



Algorytmu VMPC-R można również użyć do bezpiecznego szyfrowania danych (poprzez dodawanie generowanych przez algorytm liczb do wiadomości lub użycie operacji logicznej xor). VMPC-R jest bowiem kryptograficznie bezpiecznym generatorem liczb pseudolosowych (Cryptographically Secure Pseudo-Random Number Generator - CSPRNG).

Obydwa algorytmy (szyfr strumieniowy VMPC i generator liczb pseudolosowych VMPC-R) bazują na podobnej architekturze - wykorzystują 256-elementowe permutacje do generowania strumienia liczb. Różnią się budową i priorytetami. VMPC-R jest algorytmem bardziej złożonym i około czterokrotnie wolniejszym niż szyfr VMPC. Niska wydajność VMPC-R utrudnia stosowanie go jako efektywnego algorytmu szyfrującego, zwłaszcza dla dużych wiadomości rzędu kilkuset megabajtów.

Jednocześnie strumień liczb generowanych przez VMPC-R jest bliższy modelowi idealnie losowemu. Ponieważ jednak losowość, jaką uzyskuje szyfr VMPC, jest całkowicie wystarczająca do zapewnienia bezpieczeństwa (znalezienie jakichkolwiek odchyleń od idealnie losowego modelu dla szyfru VMPC wymaga przetestowania ponad 1000 miliardów liczb, ale nawet to nie pozwoli złamać zaszyfrowanej wiadomości), nie ma potrzeby stosować do szyfrowania algorytmu bardziej skomplikowanego kosztem obniżenia wydajności.

Do szyfrowania optymalnie jest użyć szyfru VMPC, który jest wyważonym kompromisem między wydajnością a losowością, a jednocześnie pozostaje całkowicie bezpieczny.

Tam, gdzie potrzebna jest ogromna ilość liczb bezkompromisowo zgodnych z modelem losowym, należy użyć czterokrotnie wolniejszego algorytmu VMPC-R.



W dwóch tabelach poniżej przedstawiono pseudokod generatora liczb pseudolosowych VMPC-R oraz algorytmu inicjowania klucza VMPC-R KSA. Algorytm wykorzystuje dwie 256-elementowe permutacje (P i S). Permutacje te powstają z tzw. zarodka (seed) - krótkiej liczby, najlepiej pochodzącej z idealnie losowego źródła, lub z hasła (np. w przypadku użycia algorytmu VMPC-R do szyfrowanie). Przekształcenie zarodka lub hasła w permutacje P i S realizowane jest przez algorytm inicjowania klucza (Key Scheduling Algorithm - KSA). Algorytm KSA dla algorytmu VMPC-R został specjalnie zaprojektowany i jest jego integralnym elementem.

Pełną specyfikację algorytmu VMPC-R można znaleźć w poświęconej mu pracy naukowej.

Gotowe implementacje algorytmu VMPC-R dostępne są za darmo w trzech językach programowania - C, Pascal/Delphi oraz Assembler.

Generator liczb pseudolosowych VMPC-R

  N  :  rozmiar słowa; w większości praktycznych zastosowań N=256
  P, S  :  N-elementowe tablice zawierające permutacje liczb całkowitych {0,1,...,N-1}
  a, b, c, d, e, f, n  :  zmienne całkowitoliczbowe
  L  :  ilość pseudolosowych liczb do wygenerowania
  +     oznacza dodawanie modulo N

Tabela 1. Generator liczb pseudolosowych VMPC-R
powtórz kroki 1-10  L  razy:

   1. a = P[a + c + S[n]]
   2. b = P[b + a]
   3. c = P[c + b]

   4. d = S[d + f + P[n]]
   5. e = S[e + d]
   6. f = S[f + e]

   7. wynik = S[S[S[c + d]] + 1]    

   8. zamień P[n] z P[f]
   9. zamień S[n] z S[a]

  10. n = n + 1


W kroku 7 algorytmu VMPC-R (wynik = S[S[S[c + d]] + 1]) mamy bezpośrednie wykorzystanie funkcji jednokierunkowej VMPC. Użycie w tym miejscu funkcji VMPC tworzy dodatkową warstwę bezpieczeństwa kryptograficznego, analogicznie jak ma to miejsce w przypadku szyfru VMPC.


Algorytm inicjowania klucza VMPC-R KSA

Algorytm inicjowania klucza VMPC-R KSA jest integralnym elementem generatora VMPC-R. Przekształca on zarodek (seed) lub hasło oraz jawny wektor inicjujący (Initialization Vector) w stan wewnętrzny generatora VMPC-R (w permutacje P i S oraz zmienne a, b, c, d, e, f, n).

W zastosowaniach związanych tylko z generowaniem liczb pseudolosowych wektor inicjujący nie jest parametrem o istotnym znaczeniu i można go potraktować jako rozszerzenie zarodka (seed) albo przypisać mu dowolną - stałą lub zmienną - wartość.

W przypadku zastosowania algorytmu VMPC-R do celów kryptograficznych - każda wiadomość szyfrowana tym samym kluczem musi posiadać inną wartość wektora inicjującego. W przeciwnym razie bezpieczeństwo szyfrowania zostanie drastycznie obniżone. Wektor inicjujący jest wartością jawną i należy go dołączyć do szyfrogramu.


Zmienne jak dla generatora VMPC-R oraz:
  a, b, c, d, e, f, n  
  k  :  długość zarodka (seed) lub klucza kryptograficznego; k ∈ {1,2,...,N}
  K  :  k-elementowa tablica zawierająca zarodek (seed) lub klucz kryptograficzny
  v  :  długość wektora inicjującego; v ∈ {1,2,...,N}
  V  :  v-elementowa tablica zawierająca wektor inicjujący
  i  :  tymczasowa zmienna całkowitoliczbowa
   R  =  N * Sufit(k2/(6N))
  +     oznacza dodawanie modulo N

Tabela 2. Algorytm inicjowania klucza VMPC-R KSA
0. a = b = c = d = e = f = n = 0
   P[i] = S[i] = i dla i ∈ {0,1,...,N-1}

1. KSARound(K, k)
2. KSARound(V, v)
3. KSARound(K, k)
4. n = S[S[S[c + d]] + 1]
5. wygeneruj N liczb algorytmem VMPC-R (dla L=N)


Definicja funkcji KSARound(M, m):
  6. i = 0
  7. powtórz kroki 8-18  R  razy:
       8. a = P[a + f + M[i]] + i;   i = (i + 1) mod m   
       9. b = S[b + a + M[i]] + i;   i = (i + 1) mod m
      10. c = P[c + b + M[i]] + i;   i = (i + 1) mod m
      11. d = S[d + c + M[i]] + i;   i = (i + 1) mod m
      12. e = P[e + d + M[i]] + i;   i = (i + 1) mod m
      13. f = S[f + e + M[i]] + i;   i = (i + 1) mod m

      14. zamień P[n] z P[b]
      15. zamień S[n] z S[e]
      16. zamień P[d] z P[f]
      17. zamień S[a] z S[c]

      18. n = n + 1

Funkcja KSARound wykonuje R = N * Sufit(k2/(6N)) iteracji. Wartość ta zapewnia, że każda liczba k-liczbowego klucza modyfikuje stan wewnętrzny algorytmu przynajmniej k razy. Dla N = 256 i rozmiarów klucza k ∈ {2,3,...,39} (klucze do 312 bitów) R = N. Dla N = 256 i rozmiarów klucza k ∈ {40,41,...,55} (klucze od 320 do 440 bitów) R = 2N. I tak dalej.

Przykładowe dane wyjściowe algorytmu VMPC-R (test vectors) można znaleźć w pracy naukowej oraz na stronie specjalistycznej (w języku angielskim):

www.vmpcfunction.com





Publikacje naukowe i popularnonaukowe dotyczące algorytmu VMPC-R:
  • VMPC-R Cryptographically Secure Pseudo-Random Number Generator (VMPC-R - kryptograficznie bezpieczny generator liczb pseudolosowych). Archiwum ePrint Międzynarodowego Stowarzyszenia Badań Kryptologicznych (IACR) (IACR ePrint Archive, Report 2013/768, 25 listopada 2013); [PDF]







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