So I am very confused with this lesson. I am not sure how to explain it to my students when I don’t understand it for myself.
I have a Master’s degree in computer science and I don’t understand all the math involved in this. I freely admit that to my students. I think the key take away is that you can have a public key that’s used to encode a message but unless you have the private key you can’t decode it. The internet is secure because it would take far too long to guess the private key and decode the message.
What do others think?
2 Likes
The math is hard to understand and students do not need to know the math. I don’t spend too much time on the activity guide except demonstrating the beans and cups activity. I stress on how the mod function is a one-way function that makes it hard to solve the problem backwards, i.e. determine the divisor based on knowing the remainder. Here is a video that has a simple explanation of public and private key encryption. I hope this helps.
7 Likes
Sangeeta (@bhatnagars) is right. Student’s don’t need to know the math, only that asymmetric encryption is a thing that allows anyone to encrypt things with a public key, but only the person in possession of a private key can decrypt.
As an author of this lesson I SO WANT people to understand the math though – actually what I want is really just for anyone to take one step further to understand why/how it’s possible (with math) to create these public and private keys, because I find it unsatisfying any time someone says what I just said above 
So it kills me that we haven’t been able to convey it easily, but I totally understand why it’s hard. To repeat: it’s beyond the scope of what students have to know. But I hate hate hate it when there is “magic” that we’re supposed to just trust and rely on.
I don’t think it’s not the math itself that is hard to understand, it’s just multiplication + modulo, but the application and certain properties of numbers and how they work. Also, there are a lot of steps and ideas you have to string together, and I can see how it’s easy to get lost in the steps. So this is making me want to take another crack at it, just for the satisfaction.
Would it be worth it to do this?
-Baker
3 Likes
Maybe if there was just a video solving a few simple versions of this problem without the widget it would be helpful
2 Likes
I can appreciate your passion for the math involved, and what students’ understanding of that math might accomplish, but I personally feel that that level of complexity should be explored in an actual math class. My understanding has always been that CSP is more of a survey course, one that allows students to be exposed to the “big ideas” of computer science, with the hope that they will get excited about what they’re learning and possibly go on to major in CS or pursue some related degree, where perhaps understanding concepts like these at a much deeper level is necessitated. My 2¢ anyhow.
I am a first time AP CSP teacher. In the beginning I was very excited to teach this lesson and my kids very excited too. But even with my degree in computer science and engineering and it took me one week to wrap my head around the math and the properties of modulo operation.
So I focused more on Modulo operation and the takeaways from the worksheet. I thought its fine as long as the students understand the MOD operation, prime factorization and how the use of large numbers makes the public key encryption possible.
I had the students play around the public key crypto widget and had them see the difference when they choose small numbers Vs big numbers for the public modulus. I didnt go into the algorithm and math itself but I did put out the resource included in the lesson “How and Why Does the Public Key Crypto Really Work?”. It is actually explains the math behind very well.
With all this being said I too agree that just like “TSP” and “MST”, it is very complicated topic to be handled in an High School Computer Science class.
The problem I’m having with this lesson has less to do with the math and more to do with how all of the discussion, activities and their associated parts are all supposed to tie nicely together to make kids say, ‘oh, I get it’.
For instance, before getting into the math, the last abstract vision of encryption came from the cup and beans activity. In that activity, there was a private key and a public ‘cup’, so the kids are primed to make connections back to that activity once modulo makes an appearance.
Thing seem promising when doing the clock arithmetic thought experiment. They totally get that there are infinite possibilities for the amount of time that has passed between 4:00 and 3:00. And then they (and I) get lost in the modulus clock rabbit hole. My kids understand the modulo operation, and can calculate it without the widget. They breeze through Step 1 of the Multiplication + Modulo activity guide. At this point everyone is still trusting that we’re going someplace with this…
The kids move on to Step 2 of the activity guide. The first part (top half, labelled ‘Experiment’) is just a calculator exercise. And the point was that…um…there is no pattern to the computation of each modulus problem even after holding either A or B constant and incrementing the other one up in a pattern? Not sure, so let’s go finish out the second part (bottom half, labelled ‘Experiment 2’). The first question I always get is, “What was so hard about that?” The kids easily figure out that they need to find a number that when divided by 101 will leave a remainder of 1, and start to generate a list before even reading the ‘Takeaways’ section: 102, 203, 304, etc. So then they use logic to tackle the first problem: Is there a number that when multiplied by 2 will give a result of 102 or 203, or 304, etc? Since they get a nice whole number of 51 on the first try, they stop there and move on to the next problem, using the same logic.
However, the confusion comes in when they read the Takeaway. It says, “Thanks to some special properties of prime numbers with a prime clock size there’s only one solution to each modulus equation.” Huh? Why can’t 152 also be a solution to the first problem? Reading further there is an implication that the solution has to be less than the clock size (which would then jibe with the theorem that the above bolded statement is based on), but since they didn’t know where the activity was taking them, there is no ‘aha’ moment. They’re just confused. They don’t know why solving the equations was supposed to be hard, especially since none of them just randomly guessed answers. They also have no clue how all the arithmetic relates to private and public keys (i.e. How is the private and public key generated?), although there still seems to be a promise that the explanation is coming. In other words, we get so far into the weeds that by the time Activity 3 rolls around, everyone is so exhausted from trying to figure out where it’s all going that no one cares anymore. Keep in mind that it’s not the complexity of the math (with such small numbers), but with trying to connect it back to a cup and beans. After 2 years of doing this part of the lesson, I’m thinking that just giving them a quicker intro to the modulus, along with having them entertain the thought of a prime clock size of 50 digits, would help to get their minds in a better place for the last activity with the public key crypto widget.
Just trying to make sense of it all. I suspect many teachers would rather skip this lesson than try to do the same and risk coming up short in a classroom full of kids (you can only do so much hand-waving), but I’m going to keep trying.
@asalas thanks for your take on the task! I also notice that students feel comfortable with cups/beans as a demo and they can see that modulo is kinda cool and that it is a “one way function” which makes it harder to “undo” than simple addition/subtraction from cups and beans.
I have moved to demoing the widget in class where the whole class is “Eve” and myself and another student play Alice and Bob. I focus on the takeaway as “see, Eve has no idea what is going on!” and then I share the “How does this actually work?” handout with the class as optional reading.
Again, this is just another “twist” in the lesson. If you open up the purple book, this is what it says about the knowledge needed for the AP test:
So… as a math teacher, I am thinking “WHAT?! But the math is the fun part!” But I also know that by spending too much time talking math, some of my students will think “This is NOT for me, I am not a math person” (unfortunately, student identities as “mathematicians” have already been formed by the time they get to me… and that identity is hard to change, BUT their identities as computer scientists are being formed in my class each day).
Again, I am always tweaking this lesson too - I haven’t found the perfect balance but I do think students get what they need to out of the lesson for the AP test. I also know my die-hard math kids will read the document that talks about how it really works and feel fulfilled.
I am wondering how others adapt this lesson for their contexts. What do you add, take out, tweak or ignore?
Thanks again Ms. Salas - your “making sense of it” helped me think about the lesson too - I am sure I will tweak it again next year based on your thoughts here!
Thanks!
KT
2 Likes
Thanks so much for responding Kaitie. It’s always great to meet a fellow math teacher --I like the math too!!! It’s fun to introduce kids who have taken calculus to an operation they have never heard of and to be able to answer the proverbial question, ‘when is anyone ever going to use this?’ They all agree at this point that encryption is fundamentally important to their lives, and they have been hooked enough over the previous weeks to actually care (or at least be curious) about the mathematical detail.
However, I am a curriculum writer at heart. And I love, love, love this curriculum. Even all the typos are charming to me, and I interpret them as a sign that the writers care more about content than spelling (although one day I might just submit every spelling correction to this forum in one big file). Occasionally though, there is a gap. And my brain wants to fill that gap. Such is the case with parts of this lesson.
The irony is that there are more addendums and resources for this lesson than any other one in the entire curriculum! All, I’m sure, in an attempt to fill gaps and answer questions. The resources are great, and you can tell they are well researched and someone probably spent days laboring over how to present the ideas in them. But there are a few key unaddressed parts that remain that if I understood conceptually, I could then edit the activity guide and make this lesson one that both teachers and kids find both powerful and empowering.
So I presented this lesson today. It wasn’t bad, but I wouldn’t say it was good. There was some side-eye from the kids. Mostly there was obedient respect. That might be the dream of some teachers, but I prefer the opportunity to answer the targeted questions of kids who mostly understand the concept while just needing a few points of clarification. If that’s not happening, it means they mostly don’t understand the concept and don’t want to look dumb by asking too many questions. I can relate 
2 Likes
Hi Baker,
So I have finally pored through the entire lesson again and I can now articulate something that is really bothering me. I’m hoping you can help me out.
The equation for finding Alice’s public key is: (private * public) mod clock = 1.
An example given in the ‘How and Why does Public Key Crypto Work?’ resource is the equation:
(x * 5) mod 17 = 1.
The narrative goes on to say that the only way to solve this is through brute force trial and error, that there is no way to approximate or get close to or narrow down the answer in any way. (The same language was used for the examples in the ‘Multiplication + Modulo Activity Guide’, going so far as to state that solving these types of equations was ‘hard’).
However, what I see is an equation that can be solved by using a little more than trial and error. For instance, you can start by calculating (1 times 17) + 1 to get a value that would yield a result of 1 when moded. Then you would check to see if this value is divisible by 5. It is not, so the next step is to try (2 times 17) + 1 and check for divisibility by 5 again. Bingo, I found x.
Almost every kid used this method to solve the equations in the activity guide, which were: (2 * x) mod 101 =1 and (3 * x) mod 101 =1 and (4 * x) mod 101 = 1. If they hadn’t read ahead to the Takeaway, they generated the list 102, 203, 304, etc. by calculating (1 times 101) + 1, (2 times 101) + 1, (3 times 101) + 1, etc and then checking to see if these values were divisible by the 2, 3, and 4 in the equations.
I know this process is much more laborious with large numbers, but since the language used in the narrative made it seem like wild guesses were the only way to solve these, I keep thinking that I’m missing something.
Thank you for any insight you can provide.
I think you’ve pretty much got it. The process you are describing IS simply trial and error. You’re using a little human intuition along the way, but if you had to write a program to try to find a solution, you would do something that would run through a set of possibilities. And for very small modulus(es) you can do this very easily. However, you are not “solving for x” using any formula. You are using a procedure (an algorithm) for trying out some possibilities until you find a solution. Even if you have some way to cut down the possible values quickly, it’s still brute force. The number of possibilities you have to try to crack the secret value is at least proportional to the size of the modulus, whereas Alice and Bob’s calculations stay the same in terms of the amount of time they need to compute.
So as your adversary here I would ask: (1) did you try some of the 4-digit values for modulus? (2) what if the public modulus was a 20-digit number, or even a 100-digit number? It would take Alice & Bob just about the same amount of time to do their calculations with big numbers but it would take Eve much much much longer. It might be unreasonable, in fact.
As mentioned in that doc I think you were referring to, this procedure of using (private * public) mod clock = 1 is actually NOT how the real thing works – it is a function that shares many of the same properties as RSA encryption. You can see the real math here: https://simple.wikipedia.org/wiki/RSA_algorithm At it’s core you’ll see that RSA uses multiplication + modulo, but also properties of exponentiation and prime numbers and a few more calculations to arrive at the public/private key pair. Not to mention, much much, larger numbers.
However, we think that using the modular multiplicative inverse is a good facsimile of the public-private key scenario that is accessible to high schoolers. That said, this lesson is indeed complicated because to understand what’s happening you do need to daisy-chain a lot of ideas together. The whole notion that Bob can send Alice a secret message using publicly available info that only Alice can decrypt takes a while to wrap your head around in the first place. We see a lot of videos for novices (including our own!) that use analogies for how public and private keys work, that don’t use numbers at all. Our aim here was to make a widget that shows some numbers and allows a student to see what it takes to crack some simple values. It’s not too bad on a small scale, but hopefully you could imagine with some really big numbers (as real encryption works) it would be hard.
Anyway, I hope that helps. Happy to keep chatting about it. Let me know if you have questions.
Baker
1 Like
This was my second year trying this lesson. I pretty much did what you did and had two students be Alice and Bob. I first had Alice guess Bob’s number and we did this a few times with small numbers, each time using slightly larger numbers. Then I had the rest of the class be Eve, and made Alice and Bob use small numbers again. Each time we gradually increased the size of the numbers.
I made this Walk Through, this helped me visualize the instructions.
For the cups and beans activity, although it seems like every time I do this, the students miscount!!! BUT I can’t even count how many times I have referred back to this activity.
If we don’t worry about the modulo being a prime number, there’s an easy (and non trial & error) approach to this problem. Pick the prikey and pubkey and solve for the modulo (clock).
Set some value for pubkey and prikey (I picked these out of the air)
prikey = 29
pubkey = 39
clock = prikey * pubkey -1
So, clock = 1130
If you want to select a pubkey and generate a modulo such that the modulo is a prime number, it’s a bit more work. You can write a program that sets a prikey and solves for a pubkey with a prime number modulo. I wrote this up in Python, if anyone is interested (I think it works reliably 
)