Cwnresearch.com

The amazing story of how 200 year old results in the the-ory of numbers form the security basis for billions of dol-lars in internet commercial transactions today.
Verbatim copying and redistribution of this document ispermitted in any medium provided this notice and thecopyright notice are preserved.
“Tenure track position in mathematics at the assistant orassociate professor level. Strong preference given to appli-cants in a field of applied or applicable mathematics. Noalgebraists need apply.” Job ad in The Notices of the American Mathe-matical Society, circa 1977.
The very year that ads like this were appearing, Rivest,Shamir and Adelman filed their patent on the fundamen-tal method used to secure billions of dollars in internetcommercial transactions. Their method makes essentialuse of the abstract algebra and elementary number theorydeemed so useless by so many. This is the story of howthat came to be.
A Brief Introduction to Various Sorts of Codes.
The classical situation: Knowing the key and the method,one can both encode and decode.
Simplest Example: A Simple Substitution Cipherlike 1. The WWII German Enigma Code.
2. IBM’s Lucifer Cipher.
3. The U.S. Data Encryption Standard (DES).
These are Much More Complex and Much Harderto Break than a simple substitution cipher, but theyshare with it the following trait: If an enemy managesto steal the encoding key and the method, he or she caneasily decode your messages. Thus Key Security is ofparamount importance in all these methods.
A recent (1970’s) development: There are two keys, 1. A Public Encryption Key.
2. A Separate Private Decryption Key.
You may let the whole world know the method and your Public Key so they may send you coded messages.
You must keep your private key very secret. An enemycan learn your Public Key and the method (perhaps be-cause he or she sent you a message, but he Cannot UseThis Knowledge to Decode Messages sent to you byothers.
4. The Foundations of Public Key Cryptography Public key cryptographic methods are based on a recent(1970’s) development in theoretical computer science, thenotion of Computational Complexity.
Key Idea: Some problems are Very Hard. Base yourcryptographic method on a Very Hard problem.
Sample Hard Problem: Factorization.
This is probably easy: Factor 323. Answer: 17×19.
5. The Foundations of Public Key Cryptography 740688775158586756925179514305923619344747707748672819740657949691729762288900220375880252441280568103664278331468595649569390171433605684377695257131673900054953125746900622800624571610888100289505957 6. The Foundations of Public Key Cryptography I’ll bet you would be hard pressed to come up with 740688775158586756925179514305923619344747707748672819740657949691729762288900220375880252441280568103664278331468595649569390171433605684377695257131673900054953125746900622800624571610888100289505957 15094024972934452609983659962770474511394934358673838804258766915495884704113536038134442386798911221×49071654279540277781080595974987892694117655801994904744272398370915479278320344512623315863583551217 7. The Foundations of Public Key Cryptography By the way, here’s the Mathematica code I used to findthe above: p = Random[Integer, {10∧100, 10∧101}];While[!PrimeQ[p], p = p+1];Print[p];q = Random[Integer, {10∧100, 10∧101}];While[!PrimeQ[q], q = q+1];Print[q];Print[p∗q]; Note the direction: I found two large primes and multi-plied them together to get my 200 digit challenge number.
Factoring was easy for me because I already knew the an-swer. Was it easy for you? 8. The Foundations of Public Key Cryptography To review, I found two large primes, we’ll call them pand q, and I multiplied them together to get my 200 digitnumber p×q. This is easy, at least with a computer. Butit is Very Hard to go in the reverse direction and factora given 200 digit number into the product of two 100 digitprimes. It is Very Hard even with a computer. In fact,it would probably take a fast workstation a billion years todo it.
This asymmetry – multiplication is easy, factorization isnot, forms the basis of the And the RSA method solves the Key Security problem.
It is easy and legal to listen in to internet transactions be-cause the internet is a Dynamically Routed PacketSwitched Network. Thus we have to Encrypt trans-actions we want to keep confidential.
2. Digression – Packet Switched Networks Unlike telephone calls, there is no direct dedicated connec-tion for internet messages. Instead, messages are dividedinto packets, and each packet is dynamically routed fromsource to destination.
3. Digression – Packet Switched Networks Messages are divided into packets, and each packet is dy-namically routed from source to destination. One packetmay go via London, another through Boston, all part ofthe same message from here to LA.
4. Digression – Packet Switched Networks Packets are dynamically routed according to available in-termediate points. The intermediate points Have To Lis-ten In to forward their packets. This makes it easy andlegal for anyone to listen in.
5. Reprise – The Need for Internet Security It is easy and legal to listen in to internet transactions be-cause the internet is a Dynamically Routed PacketSwitched Network. Thus we have to Encrypt trans-actions we want to keep confidential.
Both use the DES (U.S. Data Encryption Standard) toencode transmissions.
Alice’s web browser generates a random DES key whichis sent to Store.com.
Question: “Sed quis custodiet ipsos Custodes?” Who shallguard the guardsman? (Juvenal, circa 60 – 130 AD). Howdo we guard the DES key? Answer: We encode the key itself with a code so securethat even the nasty folks at Evil.Wicked.Hackers.org can’tbreak the code, Even If They Intercept the Key! 8. Public Key Cryptography – The RSA Method The server at Store.com generates a random public RSAkey and sends it to Alice. Alice uses Store.com’s publickey to encode her DES key transmission.
The nasty folks at Evil.Wicked.Hackers.org are stymied,because they can’t break the RSA code, even knowing theRSA public key, to get at the DES key.
9. Public Key Cryptography – The RSA Method The public RSA key is (essentially) the product of two Very large prime numbers (say of 100 or more decimaldigits each). To break the RSA code (it is thought), thefolks at Evil.Wicked.Hackers.org have to Factor the key.
This is so computationally difficult that it will take themmillions of years to do it.
As part of his Elements, Euclid describes the algorithminvolving successive remainders that we now know as TheEuclidean Algorithm, for finding the greatest common di-visor of two numbers.
Two consequences: Suppose N ∈ Z, the set of integers,and N = 0.
a. Given a number e ∈ Z, there exists another numberd ∈ Z such that ed = 1 mod N if and only if the greatestcommon divisor of e and N is 1.
b. By reading the process of applying the Euclidean algo-rithm backwards, one can find d given e.
Leonhard Euler figures out the laws of exponents for mod-ular arithmetic: This is more commonly stated as Euler’s Theorem: Here, φ(N ) is the Euler φ function, φ(N ) = the number ofintegers coprime to N in the range 1 . . . N , and, of course,k must be coprime to N in the above.
Leonhard Euler also figures out how to express φ(N ) as aformula: Def: φ(N ) = the number of integers coprime to N in therange 1 . . . N .
Theorem: φ(N ) = N (1 − 1/p1)(1 − 1/p2) · · · (1 − 1/pk),where p1, p2, . . . pk are the distinct prime factors of N .
In particular, if N = pq, where p and q are distinct primes,then φ(N ) = (p − 1)(q − 1). Two hundred years later,Rivest, Shamir and Adelman will make essential use ofthis in their public key encryption method, and you and Iwill use it every time we buy something over the internet.
Recall the inclusion – exclusion principle from combina-torics: Ai = Σ|Ai| − Σ|Ai ∩ Aj| + Σ|Ai ∩ Aj ∩ Ak| · · · Here |A| is the number of elements in the set A.
Consider the definition of φ(N ), φ(N ) = |A|, where the setA = {k : k is coprime to N, 1 ≤ k ≤ N }. Obtain theformula for φ(N ) by applying the inclusion – exclusionprinciple to the complement of A. Here, Ai = will be theset of multiples of i in the range 1 . . . N , and the subscripti will run over the set of integers which evenly divide N(not including 1 and N ).
Joseph-Louis Lagrange writes one of the first treatises ongroup theory, and he proves what today is known as Lagrange’s Theorem: The order of a subgroup dividesthe order of the group.
Proof Sketch of Euler’s Theorem: Consider the setUN of invertible elements (with respect to multiplication)in ZN , the ring of integers mod N . The set UN forms anAbelian group under multiplication. The set UN consistsexactly of the (equivalence classes of) integers coprimeto N . Thus, the order of the group UN is φ(N ). If [k] ∈UN , the order of the subgroup generated by [k] divides theorder of UN , by Lagrange’s Theorem. Therefore, kφ(N) =1 mod N .
No, there is a very clever and more elementary group the-oretic proof of Euler’s theorem that uses simply provedfacts about Abelian groups, and which avoids the use ofLagrange’s theorem, and thus the use of quotient groups.
(cf. Biggs, Discrete Mathematics.) However, we are headed towards the applications of num-ber theory and abstract algebra to public key cryptog-raphy. The most recent methods, such as elliptic curvemethods, are heavily algebraic, and require an enormousamount of abstract algebra and algebraic geometry.
Fermat’s Theorem (circa 1650): Let p be a prime. Thenkp−1 = 1 mod p, for every integer k between 1 and p − 1.
Proof: φ(p) = p − 1. Apply Euler’s theorem.
Application (Fermat): To find a large prime, pick alarge candidate prime p at random. Pick several integersk and test if kp−1 = 1 mod p . If so, p is probably prime.
If not, pick another large candidate prime at random andrepeat the process.
Modern methods, such as the Rabin – Solovay – Strassenalgorithm actually used by your favorite internet store’sserver, are elaborations of Fermat’s method.
e coprime to φ(N ) = (p − 1)(q − 1).
Store.com’s Public Key Pair: (N, e).
M Alice’s message, C the coded message,C = M e mod N . (e is called the encoding exponent.) Store.com’s Private Key: d, chosen so ed = 1 mod φ(N ).
Store.com decodes Alice’s message using the formula, It is why Store.com’s decoding method works: since, by Euler’s theorem, M φ(N ) = 1.
4. Where Euclid’s 300 BC Algorithm Is Used It is how Store.com finds the private decoding exponent d: Store.com knows the two large prime factors of N , p andq, so it can easily compute φ(N ) = (p − 1)(q − 1). Af-ter choosing its public encoding exponent e, Store.comapplies the Euclidean Algorithm to compute d so thated = 1 mod φ(N ).
5. Where Fermat’s 1650 Little Theorem Is Used It forms a large part of the basis of modern methods fortesting whether a given number is prime.
Example methods: The one implemented in Mathemat-ica’s PrimeQ function we used, or in Store.com’s SecureSockets Protocol software.
Important use: To find the two large randomly gener-ated primes p and q needed for the RSA method.
To find a large prime: Generate a large random num-ber. Test consecutive integers until we find one that isprime, just as we did using Mathematica, or as Store.com’sSecure Sockets Protocol software does.
There is a remote chance that the decoding method will fail because M is not coprime to N . (Remember, Eu-ler’s Theorem requires this.) But we can ignore this possi-bility in the real world because it is so improbable.
Exercise: Use inclusion-exclusion to show the probabilityof failure is (p + q − 1)/(p − 1)(q − 1) Why you can’t compute d even knowing N and e: If ed = 1 mod N , it would be easy for you compute theprivate decoding exponent d from the public N and e.
But, ed = 1 mod φ(N ), and φ(N ) = (p − 1)(q − 1). Itis strongly believed that computing d is equivalent to fac-toring N (remember N = pq), and it is strongly believedthat factoring N is a very hard problem.
(Rivest, Shamir and Adelman, Comm ACM, 1978.) Private key: d = 157 (for decoding).
Alphabet encoding: Space = 00, A = 01, B = 02, . . .
(Note the division into blocks of 4 digits, so each block (RSA-129 Challenge Message, Scientific American, 1977.) C = 9686 9613 7546 2206 1477 1409 2225 4355 N = 114,381,625,757,888,867,669,235,779,976, 5. The First Real RSA Message – continued Published in Martin Gardner’s “Mathematical Recre-ations” column in Scientific American, August, 1977, asa challenge problem.
Known as RSA-129, because the encryption modulus Nwas a 129 (decimal) digit number.
Rivest estimated it would take “40 Quadrillion Years”to factor N and break the code.
In the summer of 1993, A. Lenstra organized a team of600 volunteers and 1600 machines from All over the in-ternet to tackle the RSA-129 challenge using a new ellipticcurve factorization method.
Key Length in bits vs Time for all 100 million Pentiumcomputers sold in 1995, working together, to break thekey. Divide all these figures by 2 to 5 today (1999).
Source: S. Garfinkel, PGP: Pretty Good Privacy, O’Reilly,1995.
The two primes p and q whose product forms the encryp-tion modulus N must be chosen Randomly.
If you could make even imperfect predictions about theprimes the encoding software’s Random Number Gen-erator makes, you might be able to break the code.
So encryption software times your keystrokes to get astart (provide a seed) for the Random Number Generator.
Is it random? “Beats me, but people think it is.”(S. Garfinkel, 1995) Answer: Empirically, very secure. RSA has remainedunbroken (for large keys) for 20 years. (But then, again, ifthe National Security Agency broke it, they wouldn’t tellus.) Answer: Exactly and beyond doubt, we don’t know. Thesecurity of RSA rests on these assumptions, None OfWhich Have Ever Been Proved: 1. There is no fast algorithm for solving problems in theclass of maximally hard problems in which factorizationof large numbers lies. (This is the famous, Is N P <> Pproblem.) Unproved Assumptions on which RSA rests – con-tinued 2. There is no fast algorithm for factoring large numbers.
We don’t know of any, but we Cannot Prove that nosuch algorithm exists. Can you find one? 3. Breaking the RSA code is equivalent to the factoriza-tion problem. Even this, the weakest of the assumptionsunderlying the RSA method, has never been proved. So itremains possible that you can find a method for breakingthe RSA code without factoring the encryption modulusN . Why don’t you try? (But don’t be disappointed if youdon’t succeed.) The RSA method is over 20 years old.
More recent methods, areas of Active Research: Advantages: Shorter keysDisadvantages: Relatively untested, could be breakable.
Characteristics: Highly algebraic, based on AlgebraicGeometry, and integer points on Elliptic Curves, that iscurves of the form 6. Internet Security and the Secure Sockets Layer N. Biggs, Discrete Mathematics, Oxford, 1987.
W. Diffie and M. Hellman, “New Directions in Cryptogra-phy”, IEEE Trans. Info. Theory 22 (1976), pp. 644–654.
M. Gardner, “A New Kind of Cipher that Would TakeMillions of Years to Break”, “Mathematical Recreations”column, Scientific American, August, 1977.
S. Garfinkel, PGP: Pretty Good Privacy, O’Reilly, 1995.
J. Hunter and W. Crawford, Java Servelet Programming,O’Reilly, 1998.
N. Koblitz, Algebraic Aspects of Cryptography, SpringerVerlag, 1998.
M. Rabin, “Probabilistic Algorithms”, in J. Traub (ed.),Algorithms and Complexity, Academic Press, 1976, pp.
21–39.
R. Rivest, A. Shamir and L. Adelman, “CryptographicCommunications System and Method”, U.S. Patent #4,405,829, filed 1977, granted 1983.
R. Rivest, A. Shamir and L. Adelman, “A Method for Ob-taining Digital Signatures and Public Key Cryptography”,Comm ACM 21 (1978), pp. 120–126.
R. Solovay and V. Strassen, “A Fast Monte Carlo Test forPrimality”, SIAM J. Comp. 6 (1977), pp. 84–85. (Erra-tum, 7 (1978), p. 118.) D. Welsh, Codes and Cryptography, Oxford, 1990.
S. Garfinkel, PGP: Pretty Good Privacy, O’Reilly, 1995.
4. Additions to the Web Version, (February 2002) http://home.netscape.com/eng/ssl3/draft302.txt The Secure Sockets Layer actually allows the use of anumber of public key encryption methods in addition tothe RSA method. The Diffie Hellman method, which in-volves the discrete logarithm, is a frequently used choice.

Source: http://www.cwnresearch.com/research/talks/RSA/rsa.pdf