{"id":707,"date":"2008-12-01T09:29:57","date_gmt":"2008-12-01T09:29:57","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/12\/01\/public-key-cryptography-using-rsa\/"},"modified":"2008-12-01T09:29:57","modified_gmt":"2008-12-01T09:29:57","slug":"public-key-cryptography-using-rsa","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/12\/01\/public-key-cryptography-using-rsa\/","title":{"rendered":"Public Key Cryptography using RSA"},"content":{"rendered":"

Technorati Tags: cryptography<\/a>, public-key<\/a>, encryption<\/a>, RSA<\/a>, asymmetric encryption<\/a><\/span><\/p>\n

The most successful public key cryptosystem in use today is RSA – named for its inventors Rivest, Shamir, and Adleman. I first learned about RSA in grad school from one of my professors, Errol Lloyd<\/a>, who was one of Ron Rivest’s students. Errol is without a doubt the best teacher<\/em> I’ve ever had (and also a thoroughly nice guy). If you want to go to grad school to study algorithms, you frankly couldn’t do better than heading to Delaware to work with Errol. I have very fond memories of Errol’s class where we talked about this. He’s got a way of teaching where he doesn’t come out and tell<\/em> you anything; what he does is ask questions that lead you through the process of figuring it out yourself. That’s an incredibly effective way to teach if<\/em> you can carry it off. Personally, I can’t<\/em>. And I’ve never known anyone except Errol who could do it for a topic like RSA encryption!<\/p>\n

Anyway, moving on… In general, public key cryptosystems are based on problems that are easy to solve computationally in one direction, but really hard to solve computationally in the other. In the case of RSA, the basic underlying problem involves prime numbers: if you’ve got two really large prime numbers, then multiplying them together is easy; but if you’ve got a number that’s the product of two really large primes, factoring it is very<\/em> hard.<\/p>\n

<\/p>\n

One of the things that makes RSA difficult to explain is that it’s hard to find a starting point. The actual encryption and decryption processes are so simple that
\nthey seem like they can’t possibly work; there’s just no way to make sense out
\nof why<\/em> they work without understanding where the keys come from; but it’s strange to describe an encryption system by starting with how to generate keys, when you don’t yet know how they’re going to get used. <\/p>\n

The reason for this tangling comes back to the fundamental goal of a public key
\nsystem: you’ve got to have two keys which share a complex mathematical relationship.
\nThe encryption system itself is really just a simple expression of the relationship
\nbetween the keys. So the algorithm is (conceptually) very simple; the whole thing is
\nbased on the nature of the keys, their relationship, and the way that they’re
\ngenerate. It’s not like symmetric cryptography, where you can simply chose a key; in
\npublic key systems, the keys have to be generated to satisfy a set of mathematical
\nrelationships.<\/p>\n

With that it mind, we’ll start working through the way that RSA works by showing
\nhow you can create a public\/private key pair. The key generation process is actually
\npretty simple, but most descriptions of it get tangled up because it uses a lot of
\nterminology from number theory. I’ll try to present the standard terms as clearly as I
\ncan.<\/p>\n

The basic structure underlying an RSA key pair is a pair of two large prime
\nnumbers. What’s large? That depends on how hard you want it to be to crack. The
\ntradeoff is that the larger the original pair of primes are, the more complex it is to
\ncompute ciphertext using a key. So you need to choose a key size which makes your keys
\nhard to crack, without making the cost of encryption and decryption unacceptably
\nhigh. Once you’ve decided on a key size, that dictates the size of your two prime numbers, and you’re ready to compute a key pair, as follows.<\/p>\n

    \n
  1. Compute two large primes, which are typically named P and Q. <\/li>\n
  2. Using P and Q, you compute a number N=P×Q, which is called the modulus<\/em> of the keys being generated. <\/li>\n
  3. Compute the totient<\/em> of the modulus. For any integer, I,
    \nthe totient of I (written φ(I)) is the number of integers smaller<\/em>
    \nthan I that are relatively prime to I. Because P and Q are prime, φ(P×Q)=(P-1)×(Q-1). (The totient of P is P-1, because there are P-1 numbers relatively prime to P; the totient of Q is Q-1 for the same reason; and since P and Q are (trivially) relatively prime to each other, the totient of P×Q is (P-1)×(Q-1)).<\/li>\n
  4. Choose an integer, E, smaller than and relatively prime to φ(N). E is
    \ncalled the public key exponent<\/em>.<\/li>\n
  5. Compute an integer D such that D×E=1 mod φ(N). D is called the private key exponent<\/em>.<\/li>\n<\/ol>\n

    The public key is the pair (N, E) of the modulus and the public key exponent; and the private key is the pain (N, D) of the modulus and the private key exponent. So you’ve got your key pair.<\/p>\n

    Encryption and decryption are amazingly simple.<\/p>\n

    Suppose that the ubiquitous Alice and Bob want to communicate. Alice gives Bob her
    \npublic key, (N, E). Now, when Alice wants to send a message to Bob, she encodes the
    \nplaintext of the message as an integer, M. (I’ll leave the exact encoding of plaintext open for now.) To encrypt with her private key, (N, D),
    \nshe takes that integer and computes:<\/p>\n

    Ciphertext = MD<\/sup> mod N<\/p>\n

    Then to decrypt the message, Bob uses his key pair, and computes:<\/p>\n

    M = CiphertextE<\/sup> mod N<\/p>\n

    For Bob to encrypt a message for Alice, he does exactly<\/em> the same thing that he did to the ciphertext – except he does it to the encoded message, M. For Alice to decrypt that, she does exactly what she did to encrypt<\/em> the original M, except that she uses the ciphertext she recieved from Bob instead of the encoded plaintext M. In other words, if you’ve got a ciphertext message encrypted by the private key, decrypting it is exactly<\/em> the same process as encrypting<\/em> a plaintext with the public key, and vice versa. (This point is what used to cause me lots of confusion remembering what was symmetric and what was assymetric – RSA style asymmetric encryption is really very symmetric in how the algorithm works.)<\/p>\n

    How can this possibly work? On the face of it, it looks ridiculous! You encode by exponentiating once; you decode not by taking a root, but by exponentiating again!<\/p>\n

    It all comes back to the way the keys were generated. If we look at the process
    \nin terms of modulo arithmetic, it’s pretty easy to see why it works:<\/p>\n

      \n
    • Take an original message, M. Encrypted, it’s
      \nC = MD<\/sup> mod N.<\/li>\n
    • Now, take the ciphertext, C, and decrypt it.
      \nM’ = CE<\/sup> mod N.<\/li>\n
    • Now, expand C: M’ = (MD<\/sup> mod N)E<\/sup> mod N.<\/li>\n
    • Now, we can combine the exponents: M’ = MD×E<\/sup> mod N.<\/li>\n
    • D×E = 1 mod N.<\/li>\n
    • By some trickiness, related to the fact that D and E are relative primes related to both each other and N by their relation to the
      \ntotient of N, we can show that the fact that D×E = 1 mod N means
      \nthat M’ = MD×E<\/sup> = M1<\/sup> = M.<\/li>\n<\/ul>\n

      Watch how we can walk through a ridiculously simplified example. Let’s start with
      \na pair of primes – 29 and 61.<\/p>\n

        \n
      1. Generate keys:\n
          \n
        • First, we compute the modulus: 29×61=1769.<\/li>\n
        • Then we compute the totient: 1680.<\/li>\n
        • Then we choose an E which is relatively prime with 1680. To make things easy,
          \nI’ll just pick a prime number: E=13.<\/p>\n
        • Now, I need to compute a D, such that D×E=1 mod 1680;
          \nor to pull out a bit of standard terminology, D is the modular multiplicative
          \ninverse of E mod 1680. Doing that is an exercise in modulo arithmetic
          \nwhich gets beyond the scope of what I want to talk about today, so I’ll
          \ncheat: whipping out Mathematica, I get D=517.<\/li>\n
        • So, the public key is (1769,13), and the private key is (1769,517).<\/li>\n<\/ul>\n<\/li>\n
        • Now, let’s encode a message. Say the message is 236. So, encrypted by
          \nthe public key, that’s 23613<\/sup> mod 1769 = 7044595136617487310722334457856 mod 1769 = 573.<\/li>\n
        • And now, let’s decode it. That’s 573517<\/sup> mod 1769 = \t9245694881849602770197401240655288154608138663291308421093411147578949
          \n4462244595981994549450775979702694154377539110666284415651476199963925
          \n1321729713042853618725578035043275339491371655153997356248940804495270
          \n8984801258907252216498797520780679511957335315751292762455167434140192
          \n4399386435156204841871858091160737587648566008200581107378219553124074
          \n9374669246678685272914050993442585237015640426625522901746517901417734
          \n7954757584818934596889432709457570226928654243870833959974236930834811
          \n3204280174093386319717080086558480154647619900966739378086145377566860
          \n9195850562761848872414474511076491179637551417498920992360433000710853
          \n3935087767676514264669956171228256961906386882369681633698604708335082
          \n4532038380922358459546076540454839797340473363177061704334483341984626
          \n0992808331110751927026090969022077767175228102822099312339565763871188
          \n4006940217478961345132678704142880421227822352750998264777937728911493
          \n6283819708613556665220171457755862562705567302041244568283475209225680
          \n3828781673802145987568796646578059853165517716374603716155560308698631
          \n2650416428650673915642280074852668462543146649056536263032788685526436
          \n7863995916605455190338263161582118236712167656565774640875461698797822
          \n0025671340803745351386743506255677806855116853206286798808454276083160
          \n2812779603110688541701764925723493557773173917037390830611160570524069
          \n7471206139919064156642428626093922418127017110711925314998235480530680
          \n56675958655700624098981453 mod 1769 = 236.<\/li>\n<\/ol>\n

          So it works – but computing those results is not exactly trivial. It happens that there is a fast algorithm for doing those sorts of exponentiations – but “fast” is a relative term. RSA encryption is a lot<\/em> slower than most symmetric encryptions, by a significant factor.<\/p>\n

          In real-world use, RSA is rarely used for full-message encryption. It’s used for signatures (where you encrypt a small summary of a message), and for protocol negotiations to allow the two sides to settle on a symmetric encryption key to
          \nuse for the rest of their communication. <\/p>\n

          You’ll notice that I still haven’t gotten back to how you take a message
          \nand convert it to an integer. That’s not<\/em> trivial. The problem is,
          \nfor certain message sizes, or messages with certain numeric properties,
          \nRSA can be easily broken. So you need to protect against those cases. That’s
          \ndone by padding<\/em> the message – adding bits to it in a way that removes
          \nor obscures the properties of the message that would otherwise make it vulnerable.
          \nDiscussing the vulnerabilities of RSA for certain types of messages, and how
          \nto build a padding system that defeats them is a topic for another post.<\/p>\n

          In future posts, I’ll also describe the two most common uses of RSA in more detail – both using RSA for signing a message to prove that you really wrote it; and using
          \nRSA as part of a secure cryptographic protocol where most of the traffic is really
          \nencrypted using a symmetric algorithm.<\/p>\n","protected":false},"excerpt":{"rendered":"

          Technorati Tags: cryptography, public-key, encryption, RSA, asymmetric encryption The most successful public key cryptosystem in use today is RSA – named for its inventors Rivest, Shamir, and Adleman. I first learned about RSA in grad school from one of my professors, Errol Lloyd, who was one of Ron Rivest’s students. Errol is without a doubt […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[84],"tags":[],"class_list":["post-707","post","type-post","status-publish","format-standard","hentry","category-encryption"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-bp","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/707","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=707"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/707\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=707"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=707"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=707"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}