69
Proseminar über Algorithmen (SS09) Fingerprinting Proseminar über Algorithmen Sommersemester 2009 04. Juni 2009 Tim Mecking

Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprinting

Proseminar über AlgorithmenSommersemester 2009

04. Juni 2009Tim Mecking

Page 2: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Übersicht● Einleitung● Fingerprint Algorithmus● Hashing● Fazit

Page 3: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Einleitung● Alice wohnt in

Adelaide (Australien)● Bob wohnt in

Barnsley (UK)● Kommunikation nur

über Telefon möglich

Page 4: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Einleitung● Beide haben sich das gleiche

Lexikon gekauft.

● Sind die Texte identisch?

● 12 Bände

● 1500 Seiten / Band

● 2800 Zeichen / Seite

● 50000000 Zeichen insgesamt

● Text auch auf CD-ROM

Page 5: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Texte als Folge von Zahlen

Page 6: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus

ASCII Code20 30 40 60 70

+ 32 48 64 96 1120 0 20 32 30 48 0 40 64 @ 60 96 ` 70 112 p1 1 21 33 ! 31 49 1 41 65 A 61 97 a 71 113 q2 2 22 34 " 32 50 2 42 66 B 62 98 b 72 114 r3 3 23 35 # 33 51 3 43 67 C 63 99 c 73 115 s4 4 24 36 $ 34 52 4 44 68 D 64 100 d 74 116 t5 5 25 37 % 35 53 5 45 69 E 65 101 e 75 117 u6 6 26 38 & 36 54 6 46 70 F 66 102 f 76 118 v7 7 27 39 ' 37 55 7 47 71 G 67 103 g 77 119 w8 8 28 40 ( 38 56 8 48 72 H 68 104 h 78 120 x9 9 29 41 ) 39 57 9 49 73 I 69 105 i 79 121 yA 10 2A 42 * 3A 58 : 4A 74 J 6A 106 j 7A 122 zB 11 2B 43 + 3B 59 ; 4B 75 K 6B 107 k 7B 123 {C 12 2C 44 , 3C 60 < 4C 76 L 6C 108 l 7C 124 |D 13 2D 45 - 3D 61 = 4D 77 M 6D 109 m 7D 125 }E 14 2E 46 . 3E 62 > 4E 78 N 6E 110 n 7E 126 ~F 15 2F 47 / 3F 63 ? 4F 79 O 6F 111 o 7F 127 �

Page 7: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Texte als Folge von Zahlenmacbookpro:~ sptim$ echo -n "Adelaide" | hexdump -C00000000 41 64 65 6c 61 69 64 65 |Adelaide|00000008

● TAd = (65,100,101,108,97,105,100,101)

macbookpro:~ sptim$ echo -n "Barnsley" | hexdump -C00000000 42 61 72 6e 73 6c 65 79 |Barnsley|00000008

● TBa = (66,97,114,110,115,108,101,121)

Page 8: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Modulare Arithmetik

● x ist kongruent zu y modulo m wenn x – y durch m teilbar ist:

● Für eine ganze Zahl x ist [x] die Kongruenzklasse modulo m.

● Eine Kongruenzklasse kann verschiedene Notationen haben:

● Es gelten:

x≡ y mod m⇔m∣x− y

∀ x∈ℤ ,∀ n∈ℕ : [ x]=[xmn]

[ x ][ y ] = [x y ][ x] [ y ] = [ xy]

Page 9: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Formel zur Berechnung eines Fingerabdrucks

des Textes T=(a1,a

2,...,a

n-1,a

n) bezüglich modulo m:

● Die zufällig gewählte Zahl r sollte größer als 0 und kleiner als m sein

● Es lassen sich m – 1 sinnvolle Fingerabdrücke berechnen

FPmT , r =a1⋅rna2⋅r

n−1an−1⋅r2an⋅r

1mod m

Page 10: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Pseudocode

procedure FP(m,T,r):

fp=0

for i from 1 to length(T):

fp=((fp + T[i]) * r) mod m

return fp

Page 11: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=16

A 65 ((0+65)*16) mod 17 = (14*16) mod 17 = 3d 100 ((3+100)*16) mod 17 = (1*16) mod 17 = 16e 101 ((16+101)*16) mod 17 = (15*16) mod 17 = 2l 108 ((2+108)*16) mod 17 = (8*16) mod 17 = 9a 97 ((9+97)*16) mod 17 = (4*16) mod 17 = 13i 105 ((13+105)*16) mod 17 = (16*16) mod 17 = 1d 100 ((1+100)*16) mod 17 = (16*16) mod 17 = 1e 101 ((1+101)*16) mod 17 = (0*16) mod 17 = 0

FP 17

(T Ad

, 16)

T Ad

ai

Page 12: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=15

A 65 ((0+65)*15) mod 17 = (14*15) mod 17 = 6d 100 ((6+100)*15) mod 17 = (4*15) mod 17 = 9e 101 ((9+101)*15) mod 17 = (8*15) mod 17 = 1l 108 ((1+108)*15) mod 17 = (7*15) mod 17 = 3a 97 ((3+97)*15) mod 17 = (15*15) mod 17 = 4i 105 ((4+105)*15) mod 17 = (7*15) mod 17 = 3d 100 ((3+100)*15) mod 17 = (1*15) mod 17 = 15e 101 ((15+101)*15) mod 17 = (14*15) mod 17 = 6

FP 17

(T Ad

, 15)

T Ad

ai

Page 13: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=14

A 65 ((0+65)*14) mod 17 = (14*14) mod 17 = 9d 100 ((9+100)*14) mod 17 = (7*14) mod 17 = 13e 101 ((13+101)*14) mod 17 = (12*14) mod 17 = 15l 108 ((15+108)*14) mod 17 = (4*14) mod 17 = 5a 97 ((5+97)*14) mod 17 = (0*14) mod 17 = 0i 105 ((0+105)*14) mod 17 = (3*14) mod 17 = 8d 100 ((8+100)*14) mod 17 = (6*14) mod 17 = 16e 101 ((16+101)*14) mod 17 = (15*14) mod 17 = 6

FP 17

(T Ad

, 14)

T Ad

ai

Page 14: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=13

A 65 ((0+65)*13) mod 17 = (14*13) mod 17 = 12d 100 ((12+100)*13) mod 17 = (10*13) mod 17 = 11e 101 ((11+101)*13) mod 17 = (10*13) mod 17 = 11l 108 ((11+108)*13) mod 17 = (0*13) mod 17 = 0a 97 ((0+97)*13) mod 17 = (12*13) mod 17 = 3i 105 ((3+105)*13) mod 17 = (6*13) mod 17 = 10d 100 ((10+100)*13) mod 17 = (8*13) mod 17 = 2e 101 ((2+101)*13) mod 17 = (1*13) mod 17 = 13

FP 17

(T Ad

, 13)

T Ad

ai

Page 15: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=12

A 65 ((0+65)*12) mod 17 = (14*12) mod 17 = 15d 100 ((15+100)*12) mod 17 = (13*12) mod 17 = 3e 101 ((3+101)*12) mod 17 = (2*12) mod 17 = 7l 108 ((7+108)*12) mod 17 = (13*12) mod 17 = 3a 97 ((3+97)*12) mod 17 = (15*12) mod 17 = 10i 105 ((10+105)*12) mod 17 = (13*12) mod 17 = 3d 100 ((3+100)*12) mod 17 = (1*12) mod 17 = 12e 101 ((12+101)*12) mod 17 = (11*12) mod 17 = 13

FP 17

(T Ad

, 12)

T Ad

ai

Page 16: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=11

A 65 ((0+65)*11) mod 17 = (14*11) mod 17 = 1d 100 ((1+100)*11) mod 17 = (16*11) mod 17 = 6e 101 ((6+101)*11) mod 17 = (5*11) mod 17 = 4l 108 ((4+108)*11) mod 17 = (10*11) mod 17 = 8a 97 ((8+97)*11) mod 17 = (3*11) mod 17 = 16i 105 ((16+105)*11) mod 17 = (2*11) mod 17 = 5d 100 ((5+100)*11) mod 17 = (3*11) mod 17 = 16e 101 ((16+101)*11) mod 17 = (15*11) mod 17 = 12

FP 17

(T Ad

, 11)

T Ad

ai

Page 17: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=10

A 65 ((0+65)*10) mod 17 = (14*10) mod 17 = 4d 100 ((4+100)*10) mod 17 = (2*10) mod 17 = 3e 101 ((3+101)*10) mod 17 = (2*10) mod 17 = 3l 108 ((3+108)*10) mod 17 = (9*10) mod 17 = 5a 97 ((5+97)*10) mod 17 = (0*10) mod 17 = 0i 105 ((0+105)*10) mod 17 = (3*10) mod 17 = 13d 100 ((13+100)*10) mod 17 = (11*10) mod 17 = 8e 101 ((8+101)*10) mod 17 = (7*10) mod 17 = 2

FP 17

(T Ad

, 10)

T Ad

ai

Page 18: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=9

A 65 ((0+65)*9) mod 17 = (14*9) mod 17 = 7d 100 ((7+100)*9) mod 17 = (5*9) mod 17 = 11e 101 ((11+101)*9) mod 17 = (10*9) mod 17 = 5l 108 ((5+108)*9) mod 17 = (11*9) mod 17 = 14a 97 ((14+97)*9) mod 17 = (9*9) mod 17 = 13i 105 ((13+105)*9) mod 17 = (16*9) mod 17 = 8d 100 ((8+100)*9) mod 17 = (6*9) mod 17 = 3e 101 ((3+101)*9) mod 17 = (2*9) mod 17 = 1

FP 17

(T Ad

, 9)

T Ad

ai

Page 19: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=8

A 65 ((0+65)*8) mod 17 = (14*8) mod 17 = 10d 100 ((10+100)*8) mod 17 = (8*8) mod 17 = 13e 101 ((13+101)*8) mod 17 = (12*8) mod 17 = 11l 108 ((11+108)*8) mod 17 = (0*8) mod 17 = 0a 97 ((0+97)*8) mod 17 = (12*8) mod 17 = 11i 105 ((11+105)*8) mod 17 = (14*8) mod 17 = 10d 100 ((10+100)*8) mod 17 = (8*8) mod 17 = 13e 101 ((13+101)*8) mod 17 = (12*8) mod 17 = 11

FP 17

(T Ad

, 8)

T Ad

ai

Page 20: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=7

A 65 ((0+65)*7) mod 17 = (14*7) mod 17 = 13d 100 ((13+100)*7) mod 17 = (11*7) mod 17 = 9e 101 ((9+101)*7) mod 17 = (8*7) mod 17 = 5l 108 ((5+108)*7) mod 17 = (11*7) mod 17 = 9a 97 ((9+97)*7) mod 17 = (4*7) mod 17 = 11i 105 ((11+105)*7) mod 17 = (14*7) mod 17 = 13d 100 ((13+100)*7) mod 17 = (11*7) mod 17 = 9e 101 ((9+101)*7) mod 17 = (8*7) mod 17 = 5

FP 17

(T Ad

, 7)

T Ad

ai

Page 21: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=6

A 65 ((0+65)*6) mod 17 = (14*6) mod 17 = 16d 100 ((16+100)*6) mod 17 = (14*6) mod 17 = 16e 101 ((16+101)*6) mod 17 = (15*6) mod 17 = 5l 108 ((5+108)*6) mod 17 = (11*6) mod 17 = 15a 97 ((15+97)*6) mod 17 = (10*6) mod 17 = 9i 105 ((9+105)*6) mod 17 = (12*6) mod 17 = 4d 100 ((4+100)*6) mod 17 = (2*6) mod 17 = 12e 101 ((12+101)*6) mod 17 = (11*6) mod 17 = 15

FP 17

(T Ad

, 6)

T Ad

ai

Page 22: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=5

A 65 ((0+65)*5) mod 17 = (14*5) mod 17 = 2d 100 ((2+100)*5) mod 17 = (0*5) mod 17 = 0e 101 ((0+101)*5) mod 17 = (16*5) mod 17 = 12l 108 ((12+108)*5) mod 17 = (1*5) mod 17 = 5a 97 ((5+97)*5) mod 17 = (0*5) mod 17 = 0i 105 ((0+105)*5) mod 17 = (3*5) mod 17 = 15d 100 ((15+100)*5) mod 17 = (13*5) mod 17 = 14e 101 ((14+101)*5) mod 17 = (13*5) mod 17 = 14

FP 17

(T Ad

, 5)

T Ad

ai

Page 23: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=4

A 65 ((0+65)*4) mod 17 = (14*4) mod 17 = 5d 100 ((5+100)*4) mod 17 = (3*4) mod 17 = 12e 101 ((12+101)*4) mod 17 = (11*4) mod 17 = 10l 108 ((10+108)*4) mod 17 = (16*4) mod 17 = 13a 97 ((13+97)*4) mod 17 = (8*4) mod 17 = 15i 105 ((15+105)*4) mod 17 = (1*4) mod 17 = 4d 100 ((4+100)*4) mod 17 = (2*4) mod 17 = 8e 101 ((8+101)*4) mod 17 = (7*4) mod 17 = 11

FP 17

(T Ad

, 4)

T Ad

ai

Page 24: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=3

A 65 ((0+65)*3) mod 17 = (14*3) mod 17 = 8d 100 ((8+100)*3) mod 17 = (6*3) mod 17 = 1e 101 ((1+101)*3) mod 17 = (0*3) mod 17 = 0l 108 ((0+108)*3) mod 17 = (6*3) mod 17 = 1a 97 ((1+97)*3) mod 17 = (13*3) mod 17 = 5i 105 ((5+105)*3) mod 17 = (8*3) mod 17 = 7d 100 ((7+100)*3) mod 17 = (5*3) mod 17 = 15e 101 ((15+101)*3) mod 17 = (14*3) mod 17 = 8

FP 17

(T Ad

, 3)

T Ad

ai

Page 25: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=2

A 65 ((0+65)*2) mod 17 = (14*2) mod 17 = 11d 100 ((11+100)*2) mod 17 = (9*2) mod 17 = 1e 101 ((1+101)*2) mod 17 = (0*2) mod 17 = 0l 108 ((0+108)*2) mod 17 = (6*2) mod 17 = 12a 97 ((12+97)*2) mod 17 = (7*2) mod 17 = 14i 105 ((14+105)*2) mod 17 = (0*2) mod 17 = 0d 100 ((0+100)*2) mod 17 = (15*2) mod 17 = 13e 101 ((13+101)*2) mod 17 = (12*2) mod 17 = 7

FP 17

(T Ad

, 2)

T Ad

ai

Page 26: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=1

A 65 ((0+65)*1) mod 17 = (14*1) mod 17 = 14d 100 ((14+100)*1) mod 17 = (12*1) mod 17 = 12e 101 ((12+101)*1) mod 17 = (11*1) mod 17 = 11l 108 ((11+108)*1) mod 17 = (0*1) mod 17 = 0a 97 ((0+97)*1) mod 17 = (12*1) mod 17 = 12i 105 ((12+105)*1) mod 17 = (15*1) mod 17 = 15d 100 ((15+100)*1) mod 17 = (13*1) mod 17 = 13e 101 ((13+101)*1) mod 17 = (12*1) mod 17 = 12

FP 17

(T Ad

, 1)

T Ad

ai

Page 27: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=16

B 66 ((0+66)*16) mod 17 = (15*16) mod 17 = 2a 97 ((2+97)*16) mod 17 = (14*16) mod 17 = 3r 114 ((3+114)*16) mod 17 = (15*16) mod 17 = 2n 110 ((2+110)*16) mod 17 = (10*16) mod 17 = 7s 115 ((7+115)*16) mod 17 = (3*16) mod 17 = 14l 108 ((14+108)*16) mod 17 = (3*16) mod 17 = 14e 101 ((14+101)*16) mod 17 = (13*16) mod 17 = 4y 121 ((4+121)*16) mod 17 = (6*16) mod 17 = 11

FP 17

(T Ba

, 16)

T Ba

ai

Page 28: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=15

B 66 ((0+66)*15) mod 17 = (15*15) mod 17 = 4a 97 ((4+97)*15) mod 17 = (16*15) mod 17 = 2r 114 ((2+114)*15) mod 17 = (14*15) mod 17 = 6n 110 ((6+110)*15) mod 17 = (14*15) mod 17 = 6s 115 ((6+115)*15) mod 17 = (2*15) mod 17 = 13l 108 ((13+108)*15) mod 17 = (2*15) mod 17 = 13e 101 ((13+101)*15) mod 17 = (12*15) mod 17 = 10y 121 ((10+121)*15) mod 17 = (12*15) mod 17 = 10

FP 17

(T Ba

, 15)

T Ba

ai

Page 29: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=14

B 66 ((0+66)*14) mod 17 = (15*14) mod 17 = 6a 97 ((6+97)*14) mod 17 = (1*14) mod 17 = 14r 114 ((14+114)*14) mod 17 = (9*14) mod 17 = 7n 110 ((7+110)*14) mod 17 = (15*14) mod 17 = 6s 115 ((6+115)*14) mod 17 = (2*14) mod 17 = 11l 108 ((11+108)*14) mod 17 = (0*14) mod 17 = 0e 101 ((0+101)*14) mod 17 = (16*14) mod 17 = 3y 121 ((3+121)*14) mod 17 = (5*14) mod 17 = 2

FP 17

(T Ba

, 14)

T Ba

ai

Page 30: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=13

B 66 ((0+66)*13) mod 17 = (15*13) mod 17 = 8a 97 ((8+97)*13) mod 17 = (3*13) mod 17 = 5r 114 ((5+114)*13) mod 17 = (0*13) mod 17 = 0n 110 ((0+110)*13) mod 17 = (8*13) mod 17 = 2s 115 ((2+115)*13) mod 17 = (15*13) mod 17 = 8l 108 ((8+108)*13) mod 17 = (14*13) mod 17 = 12e 101 ((12+101)*13) mod 17 = (11*13) mod 17 = 7y 121 ((7+121)*13) mod 17 = (9*13) mod 17 = 15

FP 17

(T Ba

, 13)

T Ba

ai

Page 31: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=12

B 66 ((0+66)*12) mod 17 = (15*12) mod 17 = 10a 97 ((10+97)*12) mod 17 = (5*12) mod 17 = 9r 114 ((9+114)*12) mod 17 = (4*12) mod 17 = 14n 110 ((14+110)*12) mod 17 = (5*12) mod 17 = 9s 115 ((9+115)*12) mod 17 = (5*12) mod 17 = 9l 108 ((9+108)*12) mod 17 = (15*12) mod 17 = 10e 101 ((10+101)*12) mod 17 = (9*12) mod 17 = 6y 121 ((6+121)*12) mod 17 = (8*12) mod 17 = 11

FP 17

(T Ba

, 12)

T Ba

ai

Page 32: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=11

B 66 ((0+66)*11) mod 17 = (15*11) mod 17 = 12a 97 ((12+97)*11) mod 17 = (7*11) mod 17 = 9r 114 ((9+114)*11) mod 17 = (4*11) mod 17 = 10n 110 ((10+110)*11) mod 17 = (1*11) mod 17 = 11s 115 ((11+115)*11) mod 17 = (7*11) mod 17 = 9l 108 ((9+108)*11) mod 17 = (15*11) mod 17 = 12e 101 ((12+101)*11) mod 17 = (11*11) mod 17 = 2y 121 ((2+121)*11) mod 17 = (4*11) mod 17 = 10

FP 17

(T Ba

, 11)

T Ba

ai

Page 33: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=10

B 66 ((0+66)*10) mod 17 = (15*10) mod 17 = 14a 97 ((14+97)*10) mod 17 = (9*10) mod 17 = 5r 114 ((5+114)*10) mod 17 = (0*10) mod 17 = 0n 110 ((0+110)*10) mod 17 = (8*10) mod 17 = 12s 115 ((12+115)*10) mod 17 = (8*10) mod 17 = 12l 108 ((12+108)*10) mod 17 = (1*10) mod 17 = 10e 101 ((10+101)*10) mod 17 = (9*10) mod 17 = 5y 121 ((5+121)*10) mod 17 = (7*10) mod 17 = 2

FP 17

(T Ba

, 10)

T Ba

ai

Page 34: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=9

B 66 ((0+66)*9) mod 17 = (15*9) mod 17 = 16a 97 ((16+97)*9) mod 17 = (11*9) mod 17 = 14r 114 ((14+114)*9) mod 17 = (9*9) mod 17 = 13n 110 ((13+110)*9) mod 17 = (4*9) mod 17 = 2s 115 ((2+115)*9) mod 17 = (15*9) mod 17 = 16l 108 ((16+108)*9) mod 17 = (5*9) mod 17 = 11e 101 ((11+101)*9) mod 17 = (10*9) mod 17 = 5y 121 ((5+121)*9) mod 17 = (7*9) mod 17 = 12

FP 17

(T Ba

, 9)

T Ba

ai

Page 35: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=8

B 66 ((0+66)*8) mod 17 = (15*8) mod 17 = 1a 97 ((1+97)*8) mod 17 = (13*8) mod 17 = 2r 114 ((2+114)*8) mod 17 = (14*8) mod 17 = 10n 110 ((10+110)*8) mod 17 = (1*8) mod 17 = 8s 115 ((8+115)*8) mod 17 = (4*8) mod 17 = 15l 108 ((15+108)*8) mod 17 = (4*8) mod 17 = 15e 101 ((15+101)*8) mod 17 = (14*8) mod 17 = 10y 121 ((10+121)*8) mod 17 = (12*8) mod 17 = 11

FP 17

(T Ba

, 8)

T Ba

ai

Page 36: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=7

B 66 ((0+66)*7) mod 17 = (15*7) mod 17 = 3a 97 ((3+97)*7) mod 17 = (15*7) mod 17 = 3r 114 ((3+114)*7) mod 17 = (15*7) mod 17 = 3n 110 ((3+110)*7) mod 17 = (11*7) mod 17 = 9s 115 ((9+115)*7) mod 17 = (5*7) mod 17 = 1l 108 ((1+108)*7) mod 17 = (7*7) mod 17 = 15e 101 ((15+101)*7) mod 17 = (14*7) mod 17 = 13y 121 ((13+121)*7) mod 17 = (15*7) mod 17 = 3

FP 17

(T Ba

, 7)

T Ba

ai

Page 37: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=6

B 66 ((0+66)*6) mod 17 = (15*6) mod 17 = 5a 97 ((5+97)*6) mod 17 = (0*6) mod 17 = 0r 114 ((0+114)*6) mod 17 = (12*6) mod 17 = 4n 110 ((4+110)*6) mod 17 = (12*6) mod 17 = 4s 115 ((4+115)*6) mod 17 = (0*6) mod 17 = 0l 108 ((0+108)*6) mod 17 = (6*6) mod 17 = 2e 101 ((2+101)*6) mod 17 = (1*6) mod 17 = 6y 121 ((6+121)*6) mod 17 = (8*6) mod 17 = 14

FP 17

(T Ba

, 6)

T Ba

ai

Page 38: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=5

B 66 ((0+66)*5) mod 17 = (15*5) mod 17 = 7a 97 ((7+97)*5) mod 17 = (2*5) mod 17 = 10r 114 ((10+114)*5) mod 17 = (5*5) mod 17 = 8n 110 ((8+110)*5) mod 17 = (16*5) mod 17 = 12s 115 ((12+115)*5) mod 17 = (8*5) mod 17 = 6l 108 ((6+108)*5) mod 17 = (12*5) mod 17 = 9e 101 ((9+101)*5) mod 17 = (8*5) mod 17 = 6y 121 ((6+121)*5) mod 17 = (8*5) mod 17 = 6

FP 17

(T Ba

, 5)

T Ba

ai

Page 39: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=4

B 66 ((0+66)*4) mod 17 = (15*4) mod 17 = 9a 97 ((9+97)*4) mod 17 = (4*4) mod 17 = 16r 114 ((16+114)*4) mod 17 = (11*4) mod 17 = 10n 110 ((10+110)*4) mod 17 = (1*4) mod 17 = 4s 115 ((4+115)*4) mod 17 = (0*4) mod 17 = 0l 108 ((0+108)*4) mod 17 = (6*4) mod 17 = 7e 101 ((7+101)*4) mod 17 = (6*4) mod 17 = 7y 121 ((7+121)*4) mod 17 = (9*4) mod 17 = 2

FP 17

(T Ba

, 4)

T Ba

ai

Page 40: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=3

B 66 ((0+66)*3) mod 17 = (15*3) mod 17 = 11a 97 ((11+97)*3) mod 17 = (6*3) mod 17 = 1r 114 ((1+114)*3) mod 17 = (13*3) mod 17 = 5n 110 ((5+110)*3) mod 17 = (13*3) mod 17 = 5s 115 ((5+115)*3) mod 17 = (1*3) mod 17 = 3l 108 ((3+108)*3) mod 17 = (9*3) mod 17 = 10e 101 ((10+101)*3) mod 17 = (9*3) mod 17 = 10y 121 ((10+121)*3) mod 17 = (12*3) mod 17 = 2

FP 17

(T Ba

, 3)

T Ba

ai

Page 41: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=2

B 66 ((0+66)*2) mod 17 = (15*2) mod 17 = 13a 97 ((13+97)*2) mod 17 = (8*2) mod 17 = 16r 114 ((16+114)*2) mod 17 = (11*2) mod 17 = 5n 110 ((5+110)*2) mod 17 = (13*2) mod 17 = 9s 115 ((9+115)*2) mod 17 = (5*2) mod 17 = 10l 108 ((10+108)*2) mod 17 = (16*2) mod 17 = 15e 101 ((15+101)*2) mod 17 = (14*2) mod 17 = 11y 121 ((11+121)*2) mod 17 = (13*2) mod 17 = 9

FP 17

(T Ba

, 2)

T Ba

ai

Page 42: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmusr=1

B 66 ((0+66)*1) mod 17 = (15*1) mod 17 = 15a 97 ((15+97)*1) mod 17 = (10*1) mod 17 = 10r 114 ((10+114)*1) mod 17 = (5*1) mod 17 = 5n 110 ((5+110)*1) mod 17 = (13*1) mod 17 = 13s 115 ((13+115)*1) mod 17 = (9*1) mod 17 = 9l 108 ((9+108)*1) mod 17 = (15*1) mod 17 = 15e 101 ((15+101)*1) mod 17 = (14*1) mod 17 = 14y 121 ((14+121)*1) mod 17 = (16*1) mod 17 = 16

FP 17

(T Ba

, 1)

T Ba

ai

Page 43: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Ein Algorithmus der Zufallszahlen benutzt ist

ein randomisierter Algorithmus● Zwei Klassen von randomisierten Algorithmen:

● Las Vegas: Laufzeit abhängig von Zufallszahl (Beispiel: randomisiertes Quicksort)

● Monte Carlo: Ergebnis abhängig von Zufallszahl (Beispiel: randomisierter Primzahltest)

Page 44: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Monte Carlo Algorithmen

● Korrektes Ergebnis (viel) wahrscheinlicher● Mehrfaches Anwenden mit verschiedenen

Zufallswerten erhöht diese Wahrscheinlichkeit● Oftmals Bool'sches Ergebnis● Oftmals ein Ergebnis sicher korrekt

Page 45: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Fingerprinting Satz:

Wenn TA und T

B verschiedene Texte

(Zahlenfolgen) der Länge n sind, und wenn m eine Primzahl ist, die größer ist als die größte Zahl in T

A und T

B, dann können von den m

Zahlenpaaren

höchstens n viele aus gleichen Zahlen bestehen

FPmT A , r ,FPmT B , r , r=0,1 , ,m−1

Page 46: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Nach dem Fingerprinting Satz liegt die

Wahrscheinlichkeit einen Unterschied nicht zu erkennen bei höchstens

● Durch Einschränkung des Wertebereichs von r auf Werte >0 verringert sich die Wahrscheinlichkeit auf höchstens

● Errechnet man k Fingerabdrücke für verschiedene r Werte ergibt sich eine Wahrscheinlichkeit von höchstens

nm

n−1m−1

nm

n−1m−1

k

nm k

Page 47: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Beispiel Alice und Bob

● Textgröße (ca.) n = 50.000.000 Zeichen bzw. 50 MB● Primzahl m = 1.037.482.333● Zufallszahl r min. 1 und max. m – 1 = 1.037.482.332

● Fingerabdruck FPr min. 0 und max. m – 1 =

1.037.482.332● Anzahl der zu übermittelnden Ziffern max. 38● Wahrscheinlichkeit Unterschiede nicht zu finden

max. n−1m−1

≈50000000

1000000000=

5100

Page 48: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● 1 Fingerabdruck:

● Weniger als 40 Dezimalziffern mitzuteilen● Irrtumswahrscheinlichkeit kleiner als 5%

● 2 Fingerabdrücke:● Weniger als 60 Dezimalziffern mitzuteilen● Irrtumswahrscheinlichkeit kleiner als 0,25%

● 3 Fingerabdrücke:● Weniger als 80 Dezimalziffern mitzuteilen● Irrtumswahrscheinlichkeit kleiner als 0,0125%

Page 49: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus

„n ist _“

n=n'„k ist _“

„FP ist _“

ja

„m ist _, r1 ist _, ..., r

k ist _“

FP=FP'

mehr FPs

ja

ja

„ungleich“

nein

nein

„kein Unterschiedgefunden“nein

Sucht m und r1-r

k

Berechnen FPs

Page 50: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Ergebnis wenn m > 10n und...

● ...Texte identisch:● Immer „Kein Unterschied gefunden“

● ...Texte verschieden:● Wahrscheinlichkeit für „Kein Unterschied gefunden“

ist höchstens

● daher „Ungleich“ sehr wahrscheinlich

n−110 n−1

k

n10 n k

=1

10k

Page 51: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Mitzuteilende Dezimalziffern wenn m > 10n und

Irrtumswahrscheinlichkeit höchstens 10-k

● Bei 10-facher Textlänge erhöht sich die Anzahl der Dezimalziffern um 2 + 2k

⌊ log10n⌋2⋅22k

Page 52: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fingerprint Algorithmus● Optimierung: Alle k Fingerabdrücke während einer

Iteration über den Text berechnen● Pseudocode:

procedure FP(m,T,R): for i from 1 to length(R): fp[i]=0 for i from 1 to length(T): for j from 1 to length(R): fp[j]=((fp[j] + T[i]) * R[j]) mod m return fp

Page 53: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Zur Verifikation sowie Identifikation von Daten

und Dateien werden oftmals Fingerabdrücke verwendet.

Jedoch...

Page 54: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing

Page 55: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing

Page 56: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing

Page 57: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Hash Tabellen

● Dynamische Verwaltung von Daten● Ein Datum wird über einen Schlüssel angesprochen● Hash Funktion berechnet Schlüssel aus Datum● Wörterbuch Operationen: INSERT, DELETE,

SEARCH

Page 58: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Hash Tabelle mit

Verkettung● Werte: 12, 20, 46, 66,

72, 106 und 1003● Hash Funktion:

0123456789

20

12 721003

66 46 106

f x =xmod 10

Page 59: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Liefert die Hash Funktion für verschiedene

Daten den gleichen Schlüssel liegt eine Hash Kollision vor

● Beim Hash Verfahren mit Verkettung werden die Daten in einer verketteten Liste (Linked List) abgelegt. Dadurch können mehrere Werte unter einem Schlüssel eingefügt werden

● Offene Hash Verfahren berechnen beim Auftreten von Kollisionen alternative Schlüssel

f x = f x ' ∧x≠ x '

Page 60: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Bei offenem Hashing benutzt man eine

Funktion fi(x) um den Schlüssel zu finden, wobei

man i so lange inkrementiert bis man einen offenen Platz in der Hash Tabelle gefunden hat

● Mögliche Kollisionsstrategien bei offenem Hashing (m ist die Größe der Hash Tabelle):● Lineares Sondierenc ist Konstante, c und m sind teilerfremd

● Quadratisches Sondieren

f i x= f x c⋅i mod m

f i x= f x i2mod m

Page 61: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Hash Funktion: Abbildung einer Bitfolge

beliebiger Länge auf eine Bitfolge fester Länge

● Kollisionsfreie Hash Funktion nicht möglich, da Eingabemenge unendlich und Ausgabemenge endlich

● Anzahl möglicher Kollisionen schrumpft bei Erhöhung von k

f : {0 ,1}*{0 ,1}k

Page 62: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Einfache Hash Funktionen wie f(x)=x mod m

eignen sich nicht zur Erstellung von Fingerabdrücken

● „Sichere“ Hash Funktionen verhindern, dass die Eingabedaten gezielt manipuliert werden können, ohne dass ein anderer Schlüssel berechnet wird

Page 63: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Anforderungen an sichere Hash Algorithmen

1) Effizienz f(x) muss für jedes x effizient zu berechnen sein

2) Eingabebeständigkeit

3) Zweiteingabebeständigkeit

4) Kollisionsbeständigkeit

Page 64: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Anforderungen an sichere Hash Algorithmen

1) Effizienz

2) Eingabebeständigkeit Es darf nicht (leicht) möglich sein für ein gegebenen Hash Schlüssel h die Eingabe x zu berechnen, so dass

3) Zweiteingabebeständigkeit

4) Kollisionsbeständigkeit

f x =h

Page 65: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Anforderungen an sichere Hash Algorithmen

1) Effizienz

2) Eingabebeständigkeit

3) Zweiteingabebeständigkeit Es darf nicht (leicht) möglich sein für eine gegebene Eingabe x eine zweite Eingabe x' zu berechnen, die zu einer Hash Kollision führt:

4) Kollisionsbeständigkeit

x≠ x '∧ f x = f x '

Page 66: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● Anforderungen an sichere Hash Algorithmen

1) Effizienz

2) Eingabebeständigkeit

3) Zweiteingabebeständigkeit

4) Kollisionsbeständigkeit Es darf nicht (leicht) möglich sein für ein gegebenen Hash Schlüssel h zwei Eingaben x und x' zu berechnen, so dass x≠ x '∧ f x =h∧ f x ' =h

Page 67: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● MD5 Message Digest

● RFC 1321● 128 Bit = 16 Byte Hash Schlüssel● Erster Kollisionsangriff 2004 von Xiaoyun Wang and

Hongbo Yu● Verbesserter Angriff 2007 von Marc Stevens● NICHT (MEHR) SICHER

Page 68: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Hashing● US Secure Hash Algorithm

● RFC 3174● 160 Bit = 20 Byte Hash Schlüssel● Bisher keine Angriffe bekannt● Nachfolger SHA-2 Familie und SHA-3

Page 69: Proseminar über Algorithmen Sommersemester 2009 04. Juni ...page.mi.fu-berlin.de/brittadb/lehre/proseminar09/FingerprintingSlide… · Proseminar über Algorithmen (SS09) Einleitung

Proseminar über Algorithmen (SS09)

Fazit● Keine absolute Sicherheit

● Wenn eine gewisse Fehlerwahrscheinlichkeitwerden kann, kann man den FingerprintAlgorithmus für Dateivergleiche verwenden● Die Wahrscheinlichkeit lässt sich beeinflussen durch

geschickte Wahl der Primzahl m, sowie durch das Berechnen von k verschiedenen Fingerabdrücken

● Soll die gezielte Manipulation an den zu überprüfenden Daten verhindert werden, kann ein Hash Algorithmus verwendet werden● MD5 Fingerprints sind jedoch nicht geeignet

nm k