Foundations of Network and Computer SecurityAnnouncementsBasic RSA CryptosystemKey GenerationKey Generation NotesRSA EncryptionRSA ExampleRSA Example (cont)RSA ProofSecurity of RSAFactoring TechnologyThe Number Field SieveNFS (cont)The RecordOn the ForefrontImplementation NotesImplementation Notes (cont)Note on Primality TestingPrime Number Theorem(n) versus n/ln(n)Sample CalculationDigital SignaturesWe Can Use RSA to SignEfficiencyFoundations of Network and Foundations of Network and Computer SecurityComputer SecurityJJohn BlackLecture #11Oct 4th 2005CSCI 6268/TLEN 5831, Fall 2005Announcements•Quiz #2 is a week from today, Nov 11th –Sorry, another Tuesday quiz!•We could have it this Thurs if you’d prefer??•Project #0 will be assigned next time–Due Oct 18th (a Tuesday!)–Warm up for the main project in the course•Don’t forget to do the reading (RSA)Basic RSA Cryptosystem•Note that after Alice encrypts with pk, she cannot even decrypt what she encrypted–Only the holder of sk can decrypt–The adversary can have a copy of pk; we don’t careAdversaryAliceBob’s Public Key Bob’s Private KeyBobBob’s Public KeyKey Generation•Bob generates his keys as follows–Choose two large distinct random primes p, q–Set n = pq (in Z… no finite groups yet)–Compute (n) = (pq) = (p)(q) = (p-1)(q-1)–Choose some e 2 Z(n)*–Compute d = e-1 in Z(n)*–Set pk = (e,n) and sk = (d,n)•Here (e,n) is the ordered pair (e,n) and does not mean gcdKey Generation Notes•Note that pk and sk share n–Ok, so only d is secret•Note that d is the inverse in the group Z(n)* and not in Zn*–Kind of hard to grasp, but we’ll see why•Note that factoring n would leak d•And knowing (n) would leak d–Bob has no further use for p, q, and (n) so he shouldn’t leave them lying aroundRSA Encryption•For any message M 2 Zn*–Alice has pk = (e,n)–Alice computes C = Me mod n–That’s it•To decrypt–Bob has sk = (d,n)–He computes Cd mod n = M•We need to prove thisRSA Example•Let p = 19, q = 23–These aren’t large primes, but they’re primes!–n = 437– (n) = 396–Clearly 5 2 Z*396, so set e=5–Then d=317•ed = 5 £ 317 = 1585 = 1 + 4 £ 396 X–pk = (5, 437)–sk = (396, 437)RSA Example (cont)•Suppose M = 100 is Alice’s message–Ensure (100,437) = 1 X–Compute C = 1005 mod 437 = 85–Send 85 to Bob•Bob receives C = 85–Computes 85317 mod 437 = 100 X•We’ll discuss implementation issues laterRSA Proof•Need to show that for any M 2 Zn*, Med = M mod n–ed = 1 mod (n) [by def of d]–So ed = k(n) + 1 [by def of modulus]–So working in Zn*, Med = Mk(n) + 1 = Mk(n) M1 = (M(n))k M = 1k M = M•Do you see LaGrange’s Theorem there?•This doesn’t say anything about the security of RSA, just that we can decryptSecurity of RSA•Clearly if we can factor efficiently, RSA breaks–It’s unknown if breaking RSA implies we can factor•Basic RSA is not good encryption–There are problems with using RSA as I’ve just described; don’t do it–Use a method like OAEP•We won’t go into thisFactoring Technology•Factoring Algorithms–Try everything up to sqrt(n)•Good if n is small–Sieving•Ditto–Quadratic Sieve, Elliptic Curves, Pollard’s Rho Algorithm•Good up to about 40 bits–Number Field Sieve•State of the Art for large compositesThe Number Field Sieve•Running time is estimated as•This is super-polynomial, but sub-exponential–It’s unknown what the complexity of this problem is, but it’s thought that it lies between P and NPC, assuming P  NPNFS (cont)•How it works (sort of)–The first step is called “sieving” and it can be widely distributed–The second step builds and solves a system of equations in a large matrix and must be done on a large computer•Massive memory requirements•Usually done on a large supercomputerThe Record•In Dec, 2003, RSA-576 was factored–That’s 576 bits, 174 decimal digits–The next number is RSA-640 which is–Anyone delivering the two factors gets an immediate A in the class (and 10,000 USD)3107418240490043721350750035888567930037346022842727545720161948823206440518081504556346829671723286782437916272838033415471073108501919548529007337724822783525742386454014691736602477652346609On the Forefront•Other methods in the offing–Bernstein’s Integer Factoring Circuits–TWIRL and TWINKLE•Using lights and mirrors–Shamir and Tromer’s methods•They estimate that factoring a 1024 bit RSA modulus would take 10M USD to build and one year to run–Some skepticism has been expressed–And the beat goes on…•I wonder what the NSA knowsImplementation Notes•We didn’t say anything about how to implement RSA–What were the hard steps?!•Key generation:–Two large primes–Finding inverses mode (n)•Encryption–Computing Me mod n for large M, e, n–All this can be done reasonably efficientlyImplementation Notes (cont)•Finding inverses–Linear time with Euclid’s Extended Algorithm•Modular exponentiation –Use repeated squaring and reduce by the modulus to keep things manageable •Primality Testing–Sieve first, use pseudo-prime test, then Rabin-Miller if you want to be sure•Primality testing is the slowest part of all this•Ever generate keys for PGP, GPG, OpenSSL, etc?Note on Primality Testing•Primality testing is different from factoring–Kind of interesting that we can tell something is composite without being able to actually factor it•Recent result from IIT trio–Recently it was shown that deterministic primality testing could be done in polynomial time•Complexity was like O(n12), though it’s been slightly reduced since then–One of our faculty thought this meant RSA was broken!•Randomized algorithms like Rabin-Miller are far more efficient than the IIT algorithm, so we’ll keep using thosePrime Number Theorem•Are there enough primes?–There are plenty, as exhibited by the PNT:•PNT: (n) » n/ln(n) where (n) is the number of primes smaller than n•In other words, lim n! 1 (n) ln(n)/n = 1–What does this mean?•Primes get sparser as we go to the right on the number linen) versus n/ln(n)Sample Calculation•Let’s say we’re generating an RSA modulus and we need two 512-bit primes–This will give us a 1024-bit modulus n•Let’s generate the first prime, p–Question: if I start at some random 512-bit odd candidate c, what is the probability that c is