Hash functions 曹天杰 Tianjie Cao ticao(cumt. edu. cn College of Computer science and echnology, China University of Mining and Technology Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.526
1 曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.5.26 Hash Functions
Hash functions Introduction Cryptographic hash functions Input- any length Output-fixed length [(x)-easy H(x)-one way · hard to invert X)colliSion free 2
2 Hash Functions: Introduction • Cryptographic hash functions – Input – any length – Output – fixed length – H(x) – easy – H(x) – one way • “hard to invert” – H(x) collision free
Purposes for hash functions Data Integrity Ex: Tripwire Message digest h(x). y is called the message digest 160 bits in size -"birthday attack Message source Digital signatures Message Authentication Codes(mac)
3 Purposes for hash functions • Data Integrity – Ex: Tripwire – Message digest • y = h(x). y is called the message digest. • 160 bits in size – “birthday attack” • Message Source • Digital Signatures • Message Authentication Codes (MAC)
Digital Signatures and message Authentication Code(Mac)overview Suppose alice and Bob share a secret key k which determines hash function hk Alice sends(x, y) to Bob where y=hk(x) Bob receives(x, y) and verifies with y h, (x). If condition holds, neither x nor y was modified in transit
4 Digital Signatures and Message Authentication Code (MAC) overview • Suppose Alice and Bob share a secret key k which determines hash function hk • Alice sends (x, y) to Bob where y = hk (x) • Bob receives (x,y) and verifies with y = hk (x). If condition holds, neither x nor y was modified in transit
Keyed hash functions (X,I, K, H)is a keyed hash family, where X is a set of possible messages Y is the set of possible message digests, or authentication tags K is the keyspace h is a set of hash functions For each key K there is a hash function hx: X>Y H Assume x>= Y(even better 2X|>=Y
5 Keyed hash functions (X,Y,K,H) is a keyed hash family, where • X is a set of possible messages • Y is the set of possible message digests, or authentication tags • K is the keyspace • H is a set of hash functions • For each key K there is a hash function hK: X → Y in H • Assume |X| >= |Y| (even better, 2|X| >= |Y|)