Authentication Methods: From Digital Signatures to Hashes

Authentication Methods: From Digital Signatures to Hashes Lecture Motivation We have looked at confidentiality services, and also examined the information theoretic framework for security. Confidentiality between Alice and Bob only guarantees that Eve cannot read the message, it does not address: – Is Alice really talking to Bob? – Is Bob really talking to Alice? In this lecture, we will look at the following problems: – Entity Authentication: Proof of the identity of an individual – Message Authentication: (Data origin authentication) Proof that the source of information really is what it claims to be – Message Signing: Binding information to a particular entity – Data Integrity: Ensuring that information has not been altered by unknown entities Lecture Outline Discrete Logarithms and ElGamal – Primitive elements and some more number theory (quickly) – DLOG – ElGamal, another Public Key Algorithm… Digital Signatures: – The basic idea – RSA Signatures and ElGamal Signatures – Inefficiencies: Hashing and Signing Hash Functions: – Definitions and terminology – CHP Hash – SHA-1 Message Authentication Codes Note: Some attacks will be discussed. More attacks and cryptanalysis will come later in the semester Primitive Roots Consider the following powers of 3 (mod 7): 31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5, 36 =1 (mod7) Note that we obtain all non-zero numbers mod 7. When this happens, we call 3 a primitive root (or generator) mod 7. Is a number always a primitive root? No. If p is prime there are f(p-1) primitive roots mod p. How to find them? Good homework problem… Proposition: Let g be a primitive root for the prime p 1. If n is an integer, then gn=1 (mod p) if and only if and only if n=0 (mod p-1) . 2. If j and k are integers, then gj=gk (mod p) if and only if j=k (mod p-1). Proof: We sketch (1) on the board. Discrete Logarithms Let p be a prime, and a and b nonzero integers (mod p) with b = ax (modp) The problem of finding x is called the discrete logarithm problem, and is written: x = La (b) Often a will be a primitive root mod p. The discrete log behaves like the normal log in many ways: La (b1b2 ) = La (b1)+La (b2 ) Generally, finding the discrete log is a hard problem. f(x) = ax (mod p) is an example of a one-way function. ... - tailieumienphi.vn