{"id":2430,"date":"2018-08-01T00:55:48","date_gmt":"2018-07-31T21:55:48","guid":{"rendered":"https:\/\/www.lbscience.org\/en\/2026\/01\/31\/the-rsa-encryption-method\/"},"modified":"2026-02-01T00:19:08","modified_gmt":"2026-01-31T22:19:08","slug":"the-rsa-encryption-method","status":"publish","type":"post","link":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/","title":{"rendered":"RSA Encryption"},"content":{"rendered":"

When we shop online, we send the merchant our credit-card details. The information passes through many servers. So, who guarantees that malicious actors will not steal our credit-card data, read our e-mail, or peek at our private conversations?<\/span><\/p>\n

The solution is called encryption: Altering a message before sending it so that a third party sees only meaningless text, while the recipient can decipher it. Encryption is an ancient idea; it is claimed that Julius Caesar used a (simple) encryption method [1]. However, the kind of encryption used on the Internet was invented only in the 1970s: Public-key encryption, and the best-known method of this type is RSA [2], named after its inventors\u2014Ronald Rivest, the Israeli Adi Shamir, and Leonard Adleman.<\/span><\/p>\n

In \u201cclassical\u201d encryption methods, data is encrypted and decrypted using secret information known to both the encrypter and the decrypter, called a \u201ckey\u201d, e.g., a shared password or a large number. The difficulty with this approach is that the two parties must first agree on the password securely. Yet, when we buy something from a random online store, we have never agreed with it on a password beforehand. So, how can we send it encrypted information?<\/span><\/p>\n

In the public-key method, the store prepares two keys in advance: a public key and a private key. It publishes the public key and keeps the private key secret. To encrypt, one needs to know only the public key, but to decrypt one must use the private key\u2014even the person who encrypted the message cannot decrypt what they encrypted!<\/span>
\nYou can imagine it like this: The store buys thousands of padlocks that can all be opened with a single key and ships them to the whole world. It keeps the key for itself. Anyone who wants to send something securely to the store takes a padlock and locks the package they are sending. Once it is locked, only the store can open the package.<\/span>
\nPublic-key encryption is one of many innovations in modern cryptography, which addresses numerous information-security challenges [3]\u2014for example, digital signatures (a way to verify a sender\u2019s identity) and distributed computing [4].<\/span><\/p>\n

Despite its relative simplicity, the idea was proposed only in 1976 in a paper by Whitfield and Hellman [5], without a practical implementation. In 1977, Rivest, Shamir, and Adleman published the RSA method, the first public implementation of the idea. Why \u201cpublic\u201d? There are claims that British intelligence agencies and the NSA had discovered the method earlier. An interesting aspect is that the method relies on basic results in number theory, which until then was considered a \u201cuseless\u201d field. Subsequent public-key encryption methods are also based on number theory [6].<\/span>
\nA nice aspect of RSA is its simplicity. First we encode a message as a large number, denoted X. The public key consists of two numbers\u2014a large number N (hundreds of digits long) and a number e that can be smaller but is still large. Encryption is simply raising X to the power e, dividing by N, and taking the remainder. This requires arithmetic with large numbers, but on modern computers such calculations are done in fractions of a second.
\nThis would be our equation:
\n<\/span>y=xe<\/sup> mod N<\/span><\/p>\n

Decryption is similarly simple. The private key is just a number d, calculated from N and e so that if y is an encrypted message, after raising y to the power d and dividing by N, the remainder is exactly the original message x.
\n<\/span><\/p>\n

The equation:
\n<\/span>x=<\/span>yd <\/sup>mod N<\/span><\/p>\n

So, the encryption system relies on the three numbers N, e, and d. How can we generate them? Here Euler\u2019s totient function \u03c6 [7] comes into play: For each number, it returns how many smaller numbers share no common divisor with it [8]. A basic theorem of Euler states that for any natural number a, if we raise x to the power a\u00b7\u03c6(N)+1, divide by N, and take the remainder, we get x again. Now, if \u03c6(N) is known, it is easy to find e and d whose product has the form a\u00b7\u03c6(N)+1 for some a; the only difficulty is computing \u03c6(N), which is computationally hard when N is large. This difficulty is precisely the strength of the encryption method! If it were easy, anyone who knew N and e could compute d. In other words, anyone sending packages to the store could open other people\u2019s packages.<\/span><\/p>\n

How are the numbers for the encryption system chosen? Here additional information available to the system builder is used. If N is chosen as the product of two prime numbers, N = p*q, then \u03c6 is simple: \u03c6(N) = (p-1)*(q-1). Now the system can be built: Randomly generate two prime numbers p and q (each hundreds of digits long, to prevent cracking by computation). Multiply them to obtain N, and proceed to find e and d using our extra knowledge of \u03c6(N). Finally, publish N and e publicly. The primes p and q are discarded and forgotten, because they are no longer needed.<\/span>
\nHow can we find prime numbers with hundreds of digits, required for building the system? This seemingly difficult problem has a simple mathematical solution (the Miller\u2013Rabin algorithm [9]), but that is a topic for a separate post.<\/span><\/p>\n

We also note that, although modern encryption may seem to rely mainly on number theory, in practice it is a broad field with methods drawn from various areas of mathematics and computer science.<\/span><\/p>\n

It is hard to imagine how the Internet could function without information security. Sometimes, even mathematical methods once considered useless can change our daily lives.<\/span><\/p>\n

English editing: Elee Shimshoni<\/p>\n

\n

References:<\/strong><\/p>\n

    \n
  1. On the Caesar cipher<\/a><\/span><\/li>\n
  2. On RSA<\/span><\/a><\/li>\n
  3. On information-security challenges (from Check Point)<\/a>:<\/span><\/li>\n
  4. On distributed computing<\/a><\/span><\/li>\n
  5. On the Diffie\u2013Hellman protocol<\/a><\/span><\/li>\n
  6. On number theory<\/a><\/span><\/li>\n
  7. On Euler\u2019s totient function<\/a><\/span><\/li>\n
  8. On the greatest common divisor<\/a><\/span><\/li>\n
  9. On the Miller\u2013Rabin algorithm<\/a><\/span><\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    When we shop online, we send the merchant our credit-card details. The information passes through many servers. So, who guarantees that malicious actors will not steal our credit-card data, read our e-mail, or peek at our private conversations? The solution is called encryption: Altering a message before sending it so that a third party sees […]<\/p>\n","protected":false},"author":34,"featured_media":2438,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[20],"tags":[],"class_list":["post-2430","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computer-science"],"acf":[],"yoast_head":"\nRSA Encryption - Little, Big Science<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"RSA Encryption - Little, Big Science\" \/>\n<meta property=\"og:description\" content=\"When we shop online, we send the merchant our credit-card details. The information passes through many servers. So, who guarantees that malicious actors will not steal our credit-card data, read our e-mail, or peek at our private conversations? The solution is called encryption: Altering a message before sending it so that a third party sees […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/\" \/>\n<meta property=\"og:site_name\" content=\"Little, Big Science\" \/>\n<meta property=\"article:published_time\" content=\"2018-07-31T21:55:48+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2026-01-31T22:19:08+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.lbscience.org\/en\/wp-content\/uploads\/sites\/3\/2026\/01\/en_meme-4.jpeg\" \/>\n\t<meta property=\"og:image:width\" content=\"2400\" \/>\n\t<meta property=\"og:image:height\" content=\"1350\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"\u05d2\u05d3\u05d9 \u05d0\u05dc\u05db\u05e1\u05e0\u05d3\u05e8\u05d5\u05d1\u05d9\u05e5\u05f3\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@GadiAleks\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"\u05d2\u05d3\u05d9 \u05d0\u05dc\u05db\u05e1\u05e0\u05d3\u05e8\u05d5\u05d1\u05d9\u05e5\u05f3\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/\",\"url\":\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/\",\"name\":\"RSA Encryption - Little, Big Science\",\"isPartOf\":{\"@id\":\"https:\/\/www.lbscience.org\/en\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/www.lbscience.org\/en\/wp-content\/uploads\/sites\/3\/2026\/01\/en_meme-4.jpeg\",\"datePublished\":\"2018-07-31T21:55:48+00:00\",\"dateModified\":\"2026-01-31T22:19:08+00:00\",\"author\":{\"@id\":\"https:\/\/www.lbscience.org\/en\/#\/schema\/person\/be899eb6c60a1765f90767131a43743c\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#primaryimage\",\"url\":\"https:\/\/www.lbscience.org\/en\/wp-content\/uploads\/sites\/3\/2026\/01\/en_meme-4.jpeg\",\"contentUrl\":\"https:\/\/www.lbscience.org\/en\/wp-content\/uploads\/sites\/3\/2026\/01\/en_meme-4.jpeg\",\"width\":2400,\"height\":1350},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.lbscience.org\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"RSA Encryption\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.lbscience.org\/en\/#website\",\"url\":\"https:\/\/www.lbscience.org\/en\/\",\"name\":\"Little, Big Science\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.lbscience.org\/en\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.lbscience.org\/en\/#\/schema\/person\/be899eb6c60a1765f90767131a43743c\",\"name\":\"\u05d2\u05d3\u05d9 \u05d0\u05dc\u05db\u05e1\u05e0\u05d3\u05e8\u05d5\u05d1\u05d9\u05e5\u05f3\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.lbscience.org\/en\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/6f9733c9bcb6ed9d2ea408d950798184?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/6f9733c9bcb6ed9d2ea408d950798184?s=96&d=mm&r=g\",\"caption\":\"\u05d2\u05d3\u05d9 \u05d0\u05dc\u05db\u05e1\u05e0\u05d3\u05e8\u05d5\u05d1\u05d9\u05e5\u05f3\"},\"description\":\"\u05d2\u05d3\u05d9 \u05dc\u05de\u05d3 \u05dc\u05ea\u05d5\u05d0\u05e8 \u05d3\u05d5\u05e7\u05d8\u05d5\u05e8 \u05d1\u05d8\u05db\u05e0\u05d9\u05d5\u05df \u05d5\u05d1\u05d7\u05d9\u05e4\u05d4. \u05db\u05d9\u05d5\u05dd, \u05d4\u05d5\u05d0 \u05db\u05d5\u05ea\u05d1 \u05d5\u05e2\u05d5\u05e8\u05da \u05d0\u05ea \u05d4\u05d1\u05dc\u05d5\u05d2 \u05d4\u05de\u05ea\u05de\u05d8\u05d9 \\\"\u05dc\u05d0 \u05de\u05d3\u05d5\u05d9\u05d9\u05e7\\\".\",\"sameAs\":[\"https:\/\/x.com\/GadiAleks\"],\"url\":\"https:\/\/www.lbscience.org\/en\/author\/gadial\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"RSA Encryption - Little, Big Science","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/","og_locale":"en_US","og_type":"article","og_title":"RSA Encryption - Little, Big Science","og_description":"When we shop online, we send the merchant our credit-card details. The information passes through many servers. So, who guarantees that malicious actors will not steal our credit-card data, read our e-mail, or peek at our private conversations? The solution is called encryption: Altering a message before sending it so that a third party sees […]","og_url":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/","og_site_name":"Little, Big Science","article_published_time":"2018-07-31T21:55:48+00:00","article_modified_time":"2026-01-31T22:19:08+00:00","og_image":[{"width":2400,"height":1350,"url":"https:\/\/www.lbscience.org\/en\/wp-content\/uploads\/sites\/3\/2026\/01\/en_meme-4.jpeg","type":"image\/jpeg"}],"author":"\u05d2\u05d3\u05d9 \u05d0\u05dc\u05db\u05e1\u05e0\u05d3\u05e8\u05d5\u05d1\u05d9\u05e5\u05f3","twitter_card":"summary_large_image","twitter_creator":"@GadiAleks","twitter_misc":{"Written by":"\u05d2\u05d3\u05d9 \u05d0\u05dc\u05db\u05e1\u05e0\u05d3\u05e8\u05d5\u05d1\u05d9\u05e5\u05f3","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/","url":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/","name":"RSA Encryption - Little, Big Science","isPartOf":{"@id":"https:\/\/www.lbscience.org\/en\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#primaryimage"},"image":{"@id":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#primaryimage"},"thumbnailUrl":"https:\/\/www.lbscience.org\/en\/wp-content\/uploads\/sites\/3\/2026\/01\/en_meme-4.jpeg","datePublished":"2018-07-31T21:55:48+00:00","dateModified":"2026-01-31T22:19:08+00:00","author":{"@id":"https:\/\/www.lbscience.org\/en\/#\/schema\/person\/be899eb6c60a1765f90767131a43743c"},"breadcrumb":{"@id":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#primaryimage","url":"https:\/\/www.lbscience.org\/en\/wp-content\/uploads\/sites\/3\/2026\/01\/en_meme-4.jpeg","contentUrl":"https:\/\/www.lbscience.org\/en\/wp-content\/uploads\/sites\/3\/2026\/01\/en_meme-4.jpeg","width":2400,"height":1350},{"@type":"BreadcrumbList","@id":"https:\/\/www.lbscience.org\/en\/2018\/08\/01\/the-rsa-encryption-method\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.lbscience.org\/en\/"},{"@type":"ListItem","position":2,"name":"RSA Encryption"}]},{"@type":"WebSite","@id":"https:\/\/www.lbscience.org\/en\/#website","url":"https:\/\/www.lbscience.org\/en\/","name":"Little, Big Science","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.lbscience.org\/en\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.lbscience.org\/en\/#\/schema\/person\/be899eb6c60a1765f90767131a43743c","name":"\u05d2\u05d3\u05d9 \u05d0\u05dc\u05db\u05e1\u05e0\u05d3\u05e8\u05d5\u05d1\u05d9\u05e5\u05f3","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.lbscience.org\/en\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/6f9733c9bcb6ed9d2ea408d950798184?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/6f9733c9bcb6ed9d2ea408d950798184?s=96&d=mm&r=g","caption":"\u05d2\u05d3\u05d9 \u05d0\u05dc\u05db\u05e1\u05e0\u05d3\u05e8\u05d5\u05d1\u05d9\u05e5\u05f3"},"description":"\u05d2\u05d3\u05d9 \u05dc\u05de\u05d3 \u05dc\u05ea\u05d5\u05d0\u05e8 \u05d3\u05d5\u05e7\u05d8\u05d5\u05e8 \u05d1\u05d8\u05db\u05e0\u05d9\u05d5\u05df \u05d5\u05d1\u05d7\u05d9\u05e4\u05d4. \u05db\u05d9\u05d5\u05dd, \u05d4\u05d5\u05d0 \u05db\u05d5\u05ea\u05d1 \u05d5\u05e2\u05d5\u05e8\u05da \u05d0\u05ea \u05d4\u05d1\u05dc\u05d5\u05d2 \u05d4\u05de\u05ea\u05de\u05d8\u05d9 \"\u05dc\u05d0 \u05de\u05d3\u05d5\u05d9\u05d9\u05e7\".","sameAs":["https:\/\/x.com\/GadiAleks"],"url":"https:\/\/www.lbscience.org\/en\/author\/gadial\/"}]}},"_links":{"self":[{"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/posts\/2430","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/users\/34"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/comments?post=2430"}],"version-history":[{"count":4,"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/posts\/2430\/revisions"}],"predecessor-version":[{"id":2440,"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/posts\/2430\/revisions\/2440"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/media\/2438"}],"wp:attachment":[{"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/media?parent=2430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/categories?post=2430"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lbscience.org\/en\/wp-json\/wp\/v2\/tags?post=2430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}