Inny chwyt do obliczania a

b

mod n

Przedstawiamy liczbą m. jako liczbą binarną b

k

b

k-1

b

k-2

...b

0

∑

≠

=

0

2

i

b

i

m

czyli

[

]

n

a

a

n

a

i

i

i

b

i

b

m

mod

mod

2

0

2

0

≠

∏

=

∑

=

≠

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:
a.

komunikat(M) zaszyfrować i przesłać

b.

tylko szyfrujemy H(M) metodą konwencjonalną

c.

szyfrujemy H(M) metodą klucza jawnego

d.

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

e.

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)

f.

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

im

i

i

i

i

b

b

b

b

C

⊕

⊕

⊕

=

...

3

2

1

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

.