CONFidence 2014: NSA for dummies ...methods to break RSA - Aluc Dracul

This talk is meant to show the possibilities of breaking eMail encryption based on ECDH RSA. Part I: What is crypto? Y = {e(x, k) | x ∈ X, k ∈ K} a short recap of the RSA theorem (xed = x(xϕ(n))z ≡x mod n) and the Diffie Hellman sheme, DSA and how it works in practice. Part II: Linear algebra Euler's totient theorem Number theory computation What is factoring? Trial Division Pollard p-1 method Pollard roh Lenstra's elyptic curve methode Quadratic sive Part III Breaking keys using lattices Lattices low exponents Partial keys Coppersmith's method Conclusion: So how far can a 3 letter service use that? Where are the computational limitations?