29:null 2a:["$","title",null,{"children":"Public Key Cryptography Part 1: RSA | Jeff Jacobs | Observable"}] 30:T8b5,## 3️⃣ Construct a "Multiplication Table" Mod ${tex`n`} Next up we do something a bit weird, and it's definitely the most complex step in the procedure, but it's crucial for the remaining steps! We're going to compute the value of **Euler's totient function** for the ${tex`n`} value computed in Step 2, for reasons we'll explain in this section! Euler's totient function looks as follows: ${tex.block` \varphi(n) = n\prod_{p | n}\left(1 - \frac{1}{p}\right) = ${totientN} `} which looks terrifying at first (and you have no way of knowing what the resulting value of ${totientN} means yet) but actually has an "intuitive" meaning from the perspective of **group theory**, which we'll explain in the sub-sections below. If you want to skip over all that, you can jump right to the last sub-section, which contains the "multiplication table" representing the elements of the **multiplicative group mod ${tex`n`}** (and their products), which is exactly the "algebraic system" in which all of RSA's computations are carried out! In other words, there are a bunch of equations in the remaining steps which look like they contain "normal" multiplications, but in fact **don't** work in general if we use "standard" multiplication in the (infinite) set of integers ${tex`\mathbb{Z}`}... But, remember that **computers can't represent infinitely many numbers anyways**, so constructing this **finite "version"** of the integers ${tex`\mathbb{Z}^{\times}_n`} lets us kill two birds with one stone: * We can use the finite ${tex`\mathbb{Z}^{\times}_n`} "equivalent" to multiplication in ${tex`\mathbb{Z}`} to ensure that we never exceed the maximum integer value possibly in Python, **and** * We can actually **exploit** the fact that some mathematical operations in ${tex`\mathbb{Z}^{\times}_n`} are extremely **easy** for computers to carry out (here, multiplying two primes), while others are extremely **difficult** for computers to carry out (here, factoring a composite number into its prime factors), to construct an **encryption scheme** where: * Encryption/decryption if you **have the key** is **easy** for a computer, whereas * Encryption/decryption if you **don't have the key** is **difficult** for a computer!31:T527,## Group Theory Intuition ${tex`\varphi(n)`} turns out to be just the **size** of the **finite multiplicative group of integers mod ${tex`n`}, that is, ${tex`|\mathbb{Z}^{\times}_n|`}** To understand what that means, let's start with the simpler, more intuitive **additive** group of integers mod ${tex`n`}, which is denoted ${tex`\mathbb{Z}_n`}, and see why things get slightly more complicated when we try to move from *addition* to *multiplication* within these groups. ### The Finite [*Additive* Group](https://proofwiki.org/wiki/Definition:Additive_Group_of_Integers_Modulo_m) of Integers mod n In group theory you usually first learn about the finite [*additive* group](https://proofwiki.org/wiki/Definition:Additive_Group_of_Integers_Modulo_m) of integers mod ${tex`n`}, which is denoted ${tex`\mathbb{Z}_n`}. This additive group is easier to get a handle on, since its elements are just **all** of the integers ${tex`\{0, 1, \ldots, n - 1\}`}, and they add (and subtract!) as normal. In other words, the "addition table" for this finite additive group ${tex`\mathbb{Z}_n`} is very boring! You can use the following slider to see how, no particular difficulties come up relative to "standard" addition you learned in elementary school, except for the "wrapping around" back to 0 when the sums hit ${tex`n`}:32:T978,### The Naïve [*Multiplicative*](https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) "Group" mod *n* The problem, if we try to naïvely extend this intuition to create the [**multiplicative** group](https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) mod ${tex`n`}, is that if we want to form a **valid group**, we need to satisfy the part of the group definition that says: **Every element ${tex`x`} in a group ${tex`G`} must have an *inverse* ${tex`x^{-1}`} – that is, a corresponding element ${tex`y`} such that ${tex`xy = yx = e`} relative to the group's operation (in this case, ${tex`\times_n`})** In this definition, ${tex`e`} denotes the **"unit"** or **"identity element"** within the group. When you first learned **negative numbers**, for example, those exist precisely so that **every integer has a unique additive inverse**: given some integer ${tex`x`}, its additive inverse is ${tex`-x`}, since ${tex.block` x + (-x) = 0 `} Thus, in the **finite additive** group above, we think about inverses by analogy to the "normal" case of integer arithmetic. The identity is still "zero" – that is ${tex`e = [0]_n`} – and so we say that two elements are **additive inverses** here as well if adding them produces zero. The only difficulty is that we **don't have negative numbers** as such as elements of our group (otherwise finding the inverse would be "instant", derived by just putting a minus sign in front of the number like ${tex`-[i]_n`}, but unfortunately ${tex`-[i]_n`} is not well-defined here^[1]), but as you can see using the slider, for any element ${tex`[i]_n`} we might choose, there is always **some other positive number** that "does the same thing" For example, if ${tex`n = 6`}, then [4]_n and [2]_n are inverses, since we can look at the above table to find that: ${tex.block` \begin{aligned} [4]_n +_n [2]_n = [0]_n ~ \small{✅} \\ [2]_n +_n [4]_n = [0]_n ~ \small{✅} \end{aligned} `} And, if we repeated this step for every **row** ${tex`[i]_n`} of the **addition table** above, for example, we would always be able to find a **unique** element ${tex`[j]_n`} such that ${tex`[i]_n + [j]_n = 0`} (that is, for every row ${tex`i`}, we can find exactly **one** value ${tex`[0]_n`} somewhere). However, let's see what happens if we just take the "standard" multiplication table and "mod-ify" it by ${tex`n`}:33:T47f,The core insight – the only insight you really need in order to get the gist of the RSA algorithm! – is the following, which you can verify for yourself by using the slider above: * When ${tex`n_\times`} is **prime** ✅, **every non-zero element has a unique *multiplicative* inverse**, whereas * When ${tex`n_\times`} is **composite** 🔲, there will **always be some non-zero elements that do *not* have multiplicative inverses** (the rows highlighted in grey) You can see the simplest case of this if you set the slider to ${tex`n_\times = 4`}: in this case, although we have ${tex.block` \begin{aligned} 1 \cdot 1 = 1 \implies [1]_n \times_n [1]_n &= [1]_n ~ \small{✅} \\ 3 \cdot 3 = 9 \equiv 1 \text{ mod } 4 \iff [3]_n \times_n [3]_n &= [1]_n ~ \small{✅} \end{aligned} `} meaning that ${tex`[1]_n`} and ${tex`[3]_n`} are **their own inverses** within this group, there is **no** element in the group that we can multiply ${tex`[2]_n`} by to obtain the identity element ${tex`e = [1]_n`}! Therefore, ${tex`[2]_n`} **has no inverse** within this group, and we have a more complex task than the task we faced with **additive** groups!34:Tfaa,### The *Actual* (Non-Naïve) Multiplicative Group mod *n* However, the solution to this issue can also be discerned by looking at the above tables: a conspicuous fact about this "failed" non-zero element ${tex`[2]_n`} is that **2 shares a non-trivial divisor with our ${tex`n_\times`} value of 4, namely, 2!** This is not true for the other elements which **do** have multiplicative inverses, 1 and 3, since these share only the "trivial" divisor of 1 with ${tex`n_\times = 4`}. Next, move the slider to ${tex`n_\times = 6`} and look at which non-zero elements fail to have multiplicative inverses... You should see that ${tex`[2]_n`}, ${tex`[3]_n`}, and ${tex`[4]_n`} all fail to have multiplicative inverses... and these are again exactly the three non-zero elements in ${tex`\{0, 1, \ldots, 5\}`} that **share a non-trivial divisor with the ${tex`n_\times`} value 6!** Lastly, just to keep it interesting, skip past ${tex`n_\times = 8`} (though this fact holds for that case as well!) and move the slider to ${tex`n_\times = 9`}, then note which non-zero elements fail to have multiplicative inverses... You should see that ${tex`[3]_n`} and ${tex`[6]_n`} are the two non-zero elements that fail to have multiplicative inverses here, and once again, these are the two elements that **share a non-trivial divisor with 9** (which is **3** in both cases). This leads us to our solution, it turns out, because all we need to do to obtain the **valid** multiplicative group mod ${tex`n`} is to consider the multiplicative group whose elements are the **subset of all elements listed above** which **do not share any non-trivial divisors with ${tex`n_\times`}!** This idea is so important that there's a specific term, **co-prime**, for when two numbers have 1 as their only common divisor: that is, ${tex`x`} and ${tex`y`} are called **co-prime** if ${tex`\text{gcd}(x,y) = 1`}. With this "co-prime" idea in hand, we finally have what we need to compute the **real** (non-naïve) multiplicative group ${tex`\mathbb{Z}^{\times}_n`}: take the above "naïve" group and **remove all elements ${tex`[i]_n`} which are co-prime with ${tex`n_\times`}** (that is, all elements for which ${tex`\text{gcd}(x,n_\times) = 1`}). Once we carry this out (the book has an algorithm, *Euclid*, which computes this GCD in efficient polynomial time!), how many elements will we be left with? ...That's right folks, we'll be left with exactly ${tex`\varphi(n_\times)`} elements, where ${tex`\varphi(\cdot)`} is **Euler's totient function** from Step 3 above: ${tex.block` \varphi(n) = n\prod_{p | n}\left(1 - \frac{1}{p}\right) `} It's worth computing the value of this function **by hand** for a few cases, since it shows exactly what that weird product term is doing! For example, if we consider the ${tex`n_\times = 6`} case from above, ${tex`\varphi(6)`} gives us: ${tex.block` \begin{aligned} \varphi(6) &= 6\prod_{p | 6}\left(1 - \frac{1}{p}\right) = 6\prod_{p \in \{2, 3\}}\left(1 - \frac{1}{p}\right) = 6\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) \\ &= (6 - 3)\left(1 - \frac{1}{3}\right) = 3\left(1 - \frac{1}{3}\right) = 3 - 1 = 2 \end{aligned} `} I included all the individual steps and did the multiplications one-by-one (rather than, for example, simplifying ${tex`1 - \frac{1}{3}`} to be ${tex`\frac{2}{3}`}) to try and show how you can really just look at Euler's totient function as a step-by-step "algorithm" where, for each prime ${tex`p`} that divides ${tex`n_\times`}, the ${tex`(1 - \frac{1}{p})`} term produces a fraction that then "crosses out" exactly the portion of the original ${tex`n_\times`} elements which share that non-trivial divisor ${tex`p`}! *(If that last statement about "crossing out" the right portion makes no sense to you, don't worry, I've wrestled with it ever since my first Number Theory class, so don't feel bad, I promise I will not judge you if you want to just take this totient function as "magical" and move on. This is mostly what I do as well 😜)*35:T5be,Unfortunately for us, learning-wise, the **smallest** pair of primes ${tex`p`} and ${tex`q`} that actually "work" (in terms of, e.g., allowing Ana and Bina to actually have separate unique keys) is ${tex`(p = 3, q = 11)`}. This means that, even in the smallest possible case, we need to construct a multiplication table with ${tex.block` \begin{aligned} \varphi(3\cdot 11) &= \varphi(33) = 33\prod_{p | 33}\left(1 - \frac{1}{p}\right) = 33\prod_{p \in \{3, 11\}🤔}\left(1 - \frac{1}{p}\right) \\ &= 33\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{11}\right) = \left(33 - 11\right)\left(1 - \frac{1}{11}\right) \\ &= 22\left(1 - \frac{1}{11}\right) = 22 - 2 = 20 \end{aligned} `} elements. In theory this is not too much worse than a table with e.g. 10 elements, but we're in algorithms class which means we need to worry about efficiency as ${tex`n`} grows larger and larger! So, if you chose ${tex`p`} and ${tex`q`} in Step 1 to be large values, here I recommend going back up and choosing ${tex`p = 3`} and ${tex`q = 11`} for now... You can go back and change them to larger values later, though I don't recommend it as it might make your browser run much slower. Either way, the following table is **the** RSA multiplication table that will be used for encrypting and decrypting messages! To make it slightly easier to read, I've dropped the ${tex`[i]_n`} notation, but please keep in mind here that the "numbers" here are still actually **equivalence classes!**36:T76b,Notice how, as we wanted, **every remaining element has a multiplicative inverse**. This is what enables RSA to work! It ensures that: * If we **encrypt** some **message** ${tex`m`} using an **encryption key** ${tex`e`} (we'll see how to choose this, as well as the decryption key ${tex`d`}, in the next step) via ${tex.block` c = m^e `} * Then this encrypted "ciphertext" message ${tex`c`} can be **decrypted** using a **decryption key** ${tex`d`} via the exact same exponentiation step(!): ${tex.block` m = c^d = (m^e)^d = m^{ed} = m^{1} = m ~ \small{✅} `} Meaning, as long as the multiplication happening in the **exponent** of ${tex`m`} is the same as the multiplication represented in this RSA Multiplication Table (which it is, and which you can prove 😸), this encryption-decryption scheme will work as intended! In fact, it will be **"unbreakable"**, in the sense that the task of **decryption of ${tex`c`} *without* the key** is as hard as the hardest possible problem for a computer to solve! *Keep in mind our **asymptotic** approach to algorithmic complexity in this class! This statement really means something like:* *The best known algorithm for decrypting an RSA-encrypted message will still requires ${tex`\Omega(2^n)`} time, and if you did manage to come up with some new polynomial-time algorithm... it would in fact break every known cryptosystem ever and you'd [win a million dollars](https://www.claymath.org/millennium/p-vs-np/) and become the most famous computer scientist of all time, because your algorithm could be used to "reduce" every problem in ${tex`\text{NP}`} to a problem in ${tex`\text{P}`}, where ${tex`\text{P}`} is the class of "efficient" polynomial-time algorithms.* *PS: Someone who lives right near Georgetown's campus has a custom DC license plate with "${tex`\text{P} \neq \text{NP}`}" on it and I'm dying to find out who it is...*37:T5f1,## 5️⃣ Encrypting and Decrypting Messages This is the moment you've been waiting for! Assume **Ana** wants to send a message ${tex`m`} to **Bina**, by encoding ${tex`m`} so that it is **difficult for anyone else** to decrypt but **easy for Bina** to decrypt... We have the solution to this problem now! By encrypting her message as ${tex.block` c = m^e \text{ mod }n, `} Ana can now send ${tex`c`} over any sort of **public** channel, without needing to worry about the message being decrypted (see above italicized discussion for why). Then, once it is received by Bina, she simply decrypts it by computing ${tex.block` m = c^d = (m^e)^d = m^{ed} = m^{1} = m \text{ mod }n ~ \small{✅} `} *(We saw these encryption and decryption equations above, but now you know exactly how ${tex`e`} and ${tex`d`} are chosen to make them "just work"!)* For proofs of all the things we've asserted here, my favorite resource right now is [this "primer" on RSA](https://math.mit.edu/research/highschool/primes/circle/documents/2024/Honglin.pdf) by two high school students Joshua Pité and Yiying Zhong (I'm biased because, I think it may be from the same program I did when I was in high school 🤯). However, once we move to the **second** cryptosystem in the course, the Diffie-Hellman / El-Gamal system, you should switch over to [this paper](https://math.uchicago.edu/~may/REU2021/REUPapers/Xu,Richard.pdf) (from a 2021 REU program at UChicago!) which outlines and compares the strengths/weaknesses of both systems.38:Ta05,## Footnotes 1\. I'm trying not to make this scarier by adding lots of details, but for wrapping your head around group theory stuff, it may help to think about how: * (a) What I said up there is true, that ${tex`-[i]_n`} is not well-defined here. However, * (b) I'm secretly hiding the fact that an alternative thing you could try, ${tex`[-i]_n`}, *is* well-defined 🤯 And that's because, those brackets ${tex`[\cdot]_n`} don't actually denote numbers but **equivalence classes mod *n***, which I'll describe here quickly: Consider the additive group ${tex`\mathbb{Z}_{12}`} for example, which I choose because it is isomorphic to how an **analog clock** works: if we treat "midnight" as 0, then as each hour ticks by, we reach 1, then 2, and so on until we reach 11, but if one more hour passes, the clock returns to where it started, at 0! So, say we now want to define **addition** on clocks. Meaning, if the clock is currently pointing to the number ${tex`x`} we want to use arithmetic to figure out **not what ${tex`x + n`} is, in "standard" arithmetic,** but rather **where the clock hand will be** ${tex`d`} hours after ${tex`x`}. And, this is exactly ${tex`[x + d]_n`}, that is, addition as defined by the addition tables above! So, if we look at that expression ${tex`[x + d]_n`}, it tells us that we can carry out the **addition operation** in the **"standard"** way we learned in school, without any fancy mod stuff. Then, once we've computed the sum of ${tex`x`} and ${tex`d`}, we can "reduce" it down to its so-called **representative element**, and that will tell us where the clock hand is. That's why we take the "standard" addition but "wrap" it in those ${tex`[\cdot]_n`} brackets. So, to bring this all together: the bracket notation ${tex`[x]_n`} is really **the set of numbers in the original non-mod space ${tex`\mathbb{Z}`} that "reduce" to ${tex`x`} once we divide by ${tex`n`} and take the remainder!** Thus, for example, if we're working in ${tex`\mathbb{Z}_{12}`} as above, what's really happening is that the ${tex`[\cdot]_{12}`} notation is "chopping" the set of integers into **12 equivalence classes:** ${tex.block` \begin{aligned} [0]_{12} &= \{\ldots, -24, -12, 0, 12, 24, \ldots\} = \{0 + 12k \mid k \in \mathbb{Z}\} \\ [1]_{12} &= \{\ldots, -23, -11, 1, 13, 25, \ldots\} = \{1 + 12k \mid k \in \mathbb{Z}\} \\ &\vdots \\ [10]_{12} &= \{\ldots, -14, -2, 10, 22, 34, \ldots\} = \{10 + 12k \mid k \in \mathbb{Z}\} \\ [11]_{12} &= \{\ldots, -13, -1, 11, 23, 35, \ldots\} = \{11 + 12k \mid k \in \mathbb{Z}\} \end{aligned} `}39:T542,function genRadio(varLabel, varValues, defaultVal) { var radioElt = Inputs.radio(varValues, { value: defaultVal, label: varLabel }); var styleStr = `--label-width: 35px; font-size: 12pt; min-width: 100%; max-width: 100%;`; Object.assign(radioElt, {style: styleStr}); // console.log("genRadio"); // console.log(radioElt); const buttonElts = radioElt.children[1]; const buttonLabelElts = buttonElts.children; // Remove the circles, selection = clicking the label for (let i = 0; i < buttonLabelElts.length; i = i + 1) { const curLabelElt = buttonLabelElts[i]; Object.assign(curLabelElt, {style: `margin-left: 4px; margin-right: 4px; padding-left: 3px; padding-right: 3px; border: 1px solid lightgrey; font: 12pt/1.2 var(--serif); flex: 1 1 0px;`}); curLabelElt.classList.add('prime-button'); const curLabel = curLabelElt.textContent; const curPrime = parseInt(curLabel); if (curPrime == defaultVal) { curLabelElt.classList.add('selected-prime'); } if (curPrime < 10) { curLabelElt.classList.add('single-digit'); } // console.log(curLabel); const curInputElt = curLabelElt.firstChild; // console.log(curInputElt); Object.assign(curInputElt, {style: `display: none;`}); // console.log(radioElt.children[1].children[0].children); } return(radioElt); }3a:[] 2d:{"id":"2a85d8c557cec2f1","slug":"rsa","title":"Public Key Cryptography Part 1: RSA","thumbnail":"78b60e6199a47f100a9933be988eb6839d8f279f865cee91db6de278181ed477","access_level":"public","create_time":"$D2026-03-23T00:23:28.449Z","update_time":"$D2026-03-23T10:13:37.562Z","view_time":null,"first_public_time":"$D2026-03-23T00:24:00.862Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"38d71e6f34a30993","login":"jpowerj","name":"Jeff Jacobs","avatar_url":"https://avatars-next.observableusercontent.com/cf34f4139c8c0841a9701629ca7d66e8ddcc88b7623f62f05e243b8980480f1c","tier":"starter_2024"},"version":1169,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"3d6a884a9195123e","login":"jpowerj","name":"Jeff Jacobs","avatar_url":"https://avatars-next.observableusercontent.com/cf34f4139c8c0841a9701629ca7d66e8ddcc88b7623f62f05e243b8980480f1c","tier":null}],"members":[{"type":"team","id":"38d71e6f34a30993","login":"jpowerj","name":"Jeff Jacobs","avatar_url":"https://avatars-next.observableusercontent.com/cf34f4139c8c0841a9701629ca7d66e8ddcc88b7623f62f05e243b8980480f1c","tier":"starter_2024","role":"editor"},{"type":"individual","id":"3d6a884a9195123e","login":"jpowerj","name":"Jeff Jacobs","avatar_url":"https://avatars-next.observableusercontent.com/cf34f4139c8c0841a9701629ca7d66e8ddcc88b7623f62f05e243b8980480f1c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"8a1625abed100262","slug":"dsan-5500-data-structures-objects-and-algorithms-i","title":"DSAN 5500: Data Structures, Objects, and Algorithms in Python","owner":{"id":"38d71e6f34a30993","login":"jpowerj","name":"Jeff Jacobs"}},"type":"notebook","body":{"title":"Public Key Cryptography Part 1: RSA","cells":[{"id":0,"value":"# Public Key Cryptography Part 1: RSA","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"*(Very very inspired by the RSA visualization [here](https://legacy.cryptool.org/en/cto/rsa-visual)!)*","pinned":false,"hidden":false,"mode":"md"},{"id":312,"value":"## 1️⃣ Choose two (non-equal) primes, ${tex`p`} and ${tex`q`}","pinned":false,"hidden":false,"mode":"md"},{"id":1107,"value":"Here you can choose any two primes you want by clicking on the number! But, for learning purposes, I **strongly recommend choosing ${tex`p = 3`} and ${tex`q = 11`}** (the default values), for reasons you'll see later on – once you understand how RSA works with this pair of primes, you can scroll back up and choose any pair you'd like 🙂","pinned":false,"hidden":false,"mode":"md"},{"id":92,"value":"viewof p = genRadio(tex`\\Large p = `, firstPrimes, globs.defaultP)","pinned":false,"hidden":false,"mode":"ojs"},{"id":290,"value":"viewof q = genRadio(tex`\\Large q = `, firstPrimes, globs.defaultQ)","pinned":false,"hidden":false,"mode":"ojs"},{"id":323,"value":"## 2️⃣ Compute ${tex`n`} as the product of these primes:","pinned":false,"hidden":false,"mode":"md"},{"id":328,"value":"tex`n = \\underbrace{${p}}_{\\mathclap{p}} \\cdot \\underbrace{${q}}_{\\mathclap{q}} = ${n}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":333,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":361,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":376,"value":"viewof nAdd = genSlider([2,10], tex`\\Large n_+ = `, 6, 1)\n// Inputs.range([2,10], { label: tex`\\Large n`, value: 6, step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":368,"value":"additionTable = html`

Addition Table for ${tex`n_+ = ${nAdd}`} ${[2,3,5,7].includes(nAdd) ? \"(Prime)\" : \"(Composite)\"}

\n\n\n\n \n ${nAddEquivClasses.map(x => ``).join(\"\\n\")}\n\n\n\n${nAddEquivClasses.map(x => `\n\n${genAddRow(x).join(\"\\n\")}\n`).join(\"\\n\")}\n\n

${tex`+_{${nAdd}}`}	[${x}]_n
[${x}]_n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":693,"value":"To foreshadow a bit: specifically, there's no noticeable difference in the patterns we see when ${tex`n_+`} is **prime** vs. when it is **composite**.\n\nNotice also how the cells highlighted in orange within each table indicate where the pair of numbers ${tex`[i]_n`} (the row value) and ${tex`[j]_n`} (the column value) **sum to zero** within this group. When this happens, we call ${tex`[i]_n`} and ${tex`[j]_n`} **additive inverses**.\n\nIn every **additive** group, like the ones you can generate using the slider above, **every element ${tex`[i]_n`} has a unique additive inverse ${tex`[j]_n`}**, which you can confirm by example using the slider (and which is provable using group theory!)","pinned":false,"hidden":false,"mode":"md"},{"id":556,"value":"$32","pinned":false,"hidden":false,"mode":"md"},{"id":606,"value":"viewof nMult = genSlider([2,9], tex`\\Large n_\\times = `, 4, 1)\n// Inputs.range([2,10], { label: tex`\\Large n`, value: 6, step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":593,"value":"multTable = html`

Naïve Multiplication Table for ${tex`n_\\times = ${nMult}`} ${[2,3,5,7].includes(nMult) ? \"(Prime)\" : \"(Composite)\"}

\n\n\n\n \n ${nMultEquivClasses.map(x => ``).join(\"\\n\")}\n\n\n\n${nMultEquivClasses.map(x => `\n\n${genMultRow(x).join(\"\\n\")}\n`).join(\"\\n\")}\n\n

${tex`\\times_{${nMult}}`}	[${x}]_n
[${x}]_n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":665,"value":"$33","pinned":false,"hidden":false,"mode":"md"},{"id":768,"value":"$34","pinned":false,"hidden":false,"mode":"md"},{"id":870,"value":"viewof nGroupMult = genSlider([2,9], tex`\\Large n = `, 4, 1)\n// Inputs.range([2,10], { label: tex`\\Large n`, value: 6, step: 1})","pinned":false,"hidden":false,"mode":"ojs"},{"id":859,"value":"groupMultTable = html`

Group Multiplication Table for ${tex`n = ${nGroupMult}`} ${[2,3,5,7].includes(nGroupMult) ? \"(Prime)\" : \"(Composite)\"}

\n\n\n\n \n ${nGroupMultEquivClasses.map(x => ``).join(\"\\n\")}\n\n\n\n${nGroupMultEquivClasses.map(x => `\n\n${genGroupMultRow(x).join(\"\\n\")}\n`).join(\"\\n\")}\n\n

${tex`\\times_{${nGroupMult}}`}	[${x}]_n
[${x}]_n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":883,"value":"Now we see that, thanks to Euler's totient function, for every possible ${tex`n`} value we can construct the **valid** multiplicative group mod ${tex`n`}!\n\nSome of them may look very weird – for example, the multiplication table for ${tex`n = 6`} has now just \"collapsed\" down to two elements – but alas, that is the price we have to pay if we want to be able to carry out **well-defined multiplications *and* divisions** (which RSA's encyption and decryption schemes require) within a *restricted* finite set of integers between 1 and ${tex`n`}.","pinned":false,"hidden":false,"mode":"md"},{"id":1017,"value":"### The Multiplicative Group Used By RSA: ${tex`\\mathbb{Z}^{\\times}_{pq}`}","pinned":false,"hidden":false,"mode":"md"},{"id":895,"value":"$35","pinned":false,"hidden":false,"mode":"md"},{"id":975,"value":"rsaMultTable = html`

RSA Multiplication Table for ${tex`n = ${p}\\cdot ${q}`} (${tex`\\varphi(n) = ${totientN}`} elements)

\n\n\n\n \n ${rsaEquivClasses.map(x => ``).join(\"\\n\")}\n\n\n\n${rsaEquivClasses.map(x => `\n\n${genRSAMultRow(x).join(\"\\n\")}\n`).join(\"\\n\")}\n\n

${tex`\\times_{${n}}`}	${x}
${x}

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1071,"value":"$36","pinned":false,"hidden":false,"mode":"md"},{"id":843,"value":"## 4️⃣ Choosing Encryption and Decryption Keys","pinned":false,"hidden":false,"mode":"md"},{"id":1008,"value":"We're finally done with what is probably the most complicated part, mathematically, in terms of *using* RSA!\n\nBecause, now we just need to choose **an encryption key ${tex`e`} and a decryption key ${tex`d`}** (with ${tex`e \\neq d`}) which satisfy the following properties:\n\n* Both are **greater than 1** but **less than ${tex`\\varphi(n)`}** and\n* Both are **co-prime** to ${tex`\\varphi(n)`}\n\nIn the following table, therefore, we \"collapse\" the full RSA multiplication table from above, by **removing 1**, **removing all terms greater than or equal to ${tex`\\varphi(n)`}**, and then re-computing the products mod ${tex`\\varphi(n)`} to form the **subgroup mod ${tex`\\varphi(n)`}**. Key pairs which technically \"work\", but produce identical encryption and decryption keys (violating the ${tex`e \\neq d`} requirement above), are greyed out, so that the remaining orange-highlighted cells indicate **pairs which we can use as valid RSA key-pairs! 🥳**","pinned":false,"hidden":false,"mode":"md"},{"id":1027,"value":"totientMultTable = html`

Totient Subgroup Multiplication Table for ${tex`n = ${p}\\cdot ${q} \\implies \\varphi(n) = ${totientN}`}

\n\n\n\n \n ${totientEquivClasses.map(x => ``).join(\"\\n\")}\n\n\n\n${totientEquivClasses.map(x => `= totientN ? 'lightgrey' : 'white'}\">\n\n${genTotientMultRow(x).join(\"\\n\")}\n`).join(\"\\n\")}\n\n

${tex`\\times_{${totientN}}`}	${x}
${x}

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1113,"value":"For ease of computation, we'll pick the **smallest** non-equal pair ${tex`(e,d)`}, though in real-world settings you should do the **opposite**! Larger keys usually provide more security, for somewhat-complicated reasons.\n\nIn this case, that gives us:\n\n${tex.block`\ne = ${totientSmallestPair[0]}, \\; d = ${totientSmallestPair[1]}\n`}\n\nWhich we can now use to encrypt and decrypt messages!","pinned":false,"hidden":false,"mode":"md"},{"id":1150,"value":"$37","pinned":false,"hidden":false,"mode":"md"},{"id":715,"value":"$38","pinned":false,"hidden":false,"mode":"md"},{"id":283,"value":"## JS Calculations","pinned":false,"hidden":false,"mode":"md"},{"id":900,"value":"n = p*q","pinned":false,"hidden":false,"mode":"ojs"},{"id":924,"value":"// For students: note that this *includes* n itself!\nprimesUpToN = Array.from({length: n+1}, (_,i) => i).filter(x => firstPrimes.includes(x))","pinned":false,"hidden":false,"mode":"ojs"},{"id":939,"value":"findPrimeFactors = (nVal) => {\n // Note that this is *not* the efficient way to do this! The efficient way is in the book.\n // This is the \"brute force\" approach, only for teaching/learning purposes :P\n const primeFactors = primesUpToN.filter(x => (n % x) == 0);\n return primeFactors;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":922,"value":"computeTotient = (nVal) => {\n // Note that this is *not* the efficient way to do this! The efficient way is in the book.\n // This is the \"brute force\" approach, only for teaching/learning purposes :P\n const primeFactors = findPrimeFactors(nVal);\n const productTerms = primeFactors.map(x => ((x - 1)/x));\n const totientProduct = productTerms.reduce((acc,num) => acc * num, nVal)\n return totientProduct;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":929,"value":"totientN = computeTotient(n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":792,"value":"// https://stackoverflow.com/a/17445322/3721846\ncomputeGCD = (a, b) => {\n a = Math.abs(a);\n b = Math.abs(b);\n while (b) {\n // Swap a and b, setting b to the remainder of a / b\n [a, b] = [b, a % b]; \n }\n return a;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":115,"value":"update_p = {\n p\n const allLabels = Array.from(viewof p.querySelectorAll('label'));\n allLabels.forEach(el => el.textContent == p ? el.classList.add('selected-prime') : el.classList.remove('selected-prime'))\n return p\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":288,"value":"update_q = {\n q\n const allLabels = Array.from(viewof q.querySelectorAll('label'));\n allLabels.forEach(el => el.textContent == q ? el.classList.add('selected-prime') : el.classList.remove('selected-prime'))\n return q\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":423,"value":"// https://www.colors.tools/lighten-and-darken/?currentColor=e69f00¤tColorMixed=df4e74¤tSteps=12.5¤tHarmony=180¤tHarmonyDominance=50,50,50,50\ngenAddRow = (x) => {\n const modSums = nAddEquivClasses.map(y => (x + y) % nAdd);\n return modSums.map(s => `[${s}]_n`)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":615,"value":"genMultRow = (x) => {\n const modProducts = nMultEquivClasses.map(y => (x * y) % nMult);\n return modProducts.map(s => `[${s}]_n`)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":879,"value":"genGroupMultRow = (x) => {\n const modProducts = nGroupMultEquivClasses.map(y => (x * y) % nGroupMult);\n return modProducts.map(s => `[${s}]_n`)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":994,"value":"genRSAMultRow = (x) => {\n const modProducts = rsaEquivClasses.map(y => (x * y) % n);\n return modProducts.map(s => `${s}`)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1047,"value":"getTotientColor = (x,y,s) => {\n if (s == 1) {\n if (x == y) {\n return 'lightgrey';\n } else {\n return '#e69f0055';\n }\n }\n return 'white';\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1118,"value":"getTotientInfo = (x) => {\n return totientEquivClasses.map(y => [x,y,(x * y) % totientN, getTotientColor(x,y,(x*y)%totientN)]);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1123,"value":"totientSmallestPair = {\n const validRows = totientEquivClasses.flatMap(x => getTotientInfo(x)).filter(x => x[3] == \"#e69f0055\");\n const smallestRow = validRows[0];\n return [smallestRow[0], smallestRow[1]]\n}\n// .reduce((acc,elt) => (acc || elt[3] == \"#e69f0055\"),false)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1037,"value":"genTotientMultRow = (x) => {\n const modProductResults = getTotientInfo(x);\n return modProductResults.map(sInfo => `${sInfo[2]}`)\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":383,"value":"nAddEquivClasses = Array.from({length: nAdd}, (_,i) => i)","pinned":false,"hidden":false,"mode":"ojs"},{"id":619,"value":"nMultEquivClasses = Array.from({length: nMult}, (_,i) => i)","pinned":false,"hidden":false,"mode":"ojs"},{"id":867,"value":"nGroupMultEquivClasses = Array.from({length: nGroupMult}, (_,i) => i).filter(x => computeGCD(x, nGroupMult) == 1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":986,"value":"rsaEquivClasses = Array.from({length: n}, (_,i) => i).filter(x => computeGCD(x, n) == 1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":1031,"value":"totientEquivClasses = Array.from({length: totientN}, (_,i) => i).filter(x => x != 1 && computeGCD(x, totientN) == 1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":11,"value":"firstPrimes = [\n 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,\n // 53, 59, 61, 67, 71, 73, 79, 83, 89, 97\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":89,"value":"## UI Pieces / Globals","pinned":false,"hidden":false,"mode":"md"},{"id":14,"value":"$39","pinned":true,"hidden":false,"mode":"ojs"},{"id":531,"value":"function genSlider(varRange, varLabel, defaultVal, varStep) {\n var sliderElt = Inputs.range(varRange, {\n label: varLabel,\n value: defaultVal,\n step: varStep,\n });\n var styleStr = `--label-width: 45px;`;\n Object.assign(sliderElt, {style: styleStr});\n const sliderInputBox = sliderElt.querySelector('input');\n console.log(sliderInputBox);\n // allLabels.forEach(el => el.textContent == p ? el.classList.add('selected-prime') : el.classList.remove('selected-prime'))\n sliderInputBox.classList.add('two-digit-slider');\n return(sliderElt);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":303,"value":"globs = ({\n defaultP: 3,\n defaultQ: 11,\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":54,"value":"function set(input, value) {\n input.value = value;\n input.dispatchEvent(new Event(\"input\"));\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":78,"value":"## Failed attempt with Bootstrap","pinned":false,"hidden":false,"mode":"md"},{"id":25,"value":"// html`bootstrap.min.css `","pinned":true,"hidden":false,"mode":"ojs"},{"id":74,"value":"## Failed attempt with Vue.js","pinned":false,"hidden":false,"mode":"md"},{"id":61,"value":"// viewof chosenP = html``","pinned":true,"hidden":false,"mode":"ojs"},{"id":59,"value":"// viewof app_holding_state = {\n// const el = htl.html`

\n// {{ message }}\n//

`\n// yield el\n \n// const app = Vue.createApp({\n// data() {\n// return {\n// message: `${viewof chosenP.value}`\n// }\n// },\n// created() {\n// viewof chosenP.addEventListener(\"input\", e => {\n// const updatedInput = viewof chosenP.value\n// this.message = updatedInput\n// })\n// }\n// })\n \n// app.mount(el)\n\n// el.value = app\n// }","pinned":true,"hidden":false,"mode":"ojs"},{"id":63,"value":"// Vue = import(\"https://unpkg.com/vue@3/dist/vue.esm-browser.js\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":156,"value":"","pinned":true,"hidden":false,"mode":"html"}],"files":"$W3a","stdlib":"1","titling":"auto"}} 2e:"$2d:body"