Cryptography - Cours no. 4

CryptographyCours no. 4Jean-Sébastien CoronUniversity of LuxembourgMarch 18, 2010Jean-Sébastien Coron CryptographySecurity proofsWhat is cryptography ?Cryptography’s aim is to contruct schemes that achievesome goal despite the presence of an adversary.Example: encryption, key-exchange, signature, electronicvoting...Scientific approach:To be rigorous, one must specify what it means to besecure.Then one tries to construct schemes that achieve thedesired goal, in a provable way.Plain RSA encryption and signature cannot be used !Jean-Sébastien Coron CryptographyThe RSA signature schemeKey generation :Public modulus: N = p q where p and q are large primes.Public exponent : ePrivate exponent: d, such that d e = 1 mod φ(N)To sign a message m, the signer computes :ds = m mod NOnly the signer can sign the message.To verify the signature, one checks that:em = s mod NAnybody can verify the signatureJean-Sébastien Coron CryptographyHash-and-sign paradigmThere are many attacks on basic RSA signatures:eExistential forgery: r = m mod Nd d dChosen-message attack: (m m ) = m m mod N1 2 1 2To prevent from these attacks, one usually uses a hashfunction. The message is first hashed, then padded.m−→ H(m)−→1001...0101kH(m)Example: PKCS#1 v1.5:μ(m) =0001 FF....FF00||c ||SHA(m)SHAISO 9796-2: μ(m) =6Akm[1]kH(m)kBCJean-Sébastien Coron CryptographyProofs for signature schemesStrongest security notion (Goldwasser, Micali and Rivest,1988):It must be ...