Inny chwyt do obliczania a^b mod n

Przedstawiamy liczbą m. jako liczbą binarną b_kb_k-1b_k-2...b₀

czyli

algorytm do liczenia a^b mod n

liczba m w postaci binarnej b_i oznacza kolejny bit

c:=0; d:=1;

FOR i=k DOWNTO 0 do

begin

c:=c*2;

d:= (d*d) mod n;

IF b_i =1 then

begin

c:=c+1;

d:=(d*a) mod n;

end;

end;

Funkcje mieszające.

Jednokierunkowa funkcja haszująca bierze komunikat M o dowolnej długości i generuje wynik wyjściowy H(M) o stałym rozmiarze. Zmiana jednego bitu w M daje oczywiście zmianę wartości H(M) i dalej możemy:

1. komunikat(M) zaszyfrować i przesłać

2. tylko szyfrujemy H(M) metodą konwencjonalną

3. szyfrujemy H(M) metodą klucza jawnego

4. komunikat szyfrujemy konwencjonalnie , H(M) z kluczem jawnym czyli mamy poufność i uwierzytelnienie

5. Jeśli obie strony znają tajną wartość S to nadawca oblicza H(M+S) dołącza do M odbiorca B też zna S i może zweryfikować poprawność otrzymanego H(M+S)

6. Punkt e można szyfrować

Ponieważ szyfrowanie jest czasochłonne i czasami wymaga użycia opatentowanych algorytmów(ograniczenia eksportowe) rośnie zainteresowanie technikami bez szyfrowania

Najpopularniejsza kryptograficzna suma kontrolna (standard ANSI X9.17) oparta jest o algorytm DES z zerowym wektorem początkowym. Dane są grupowane w 64-bitowe bloki

kod uwierzytelnienia oblicza się za pomocą DES oraz tajnego klucza

Funkcja haszująca

logiczny(bit po bicie) XOR każdego bloku, b_ij i-ty bit w j-tym bloku, m -liczba n-bitowych bloków. Dla tej funkcji haszujące prawdopodobieństwo, że błąd w danych nie spowoduje zmiany wartości wynosi 2^-n.

---