Cryptonia prospered thanks to the new gold mine, the security provided by the dragon, and the convenience of the DragonBucks system.
This brought an influx of non-native Cryptonians to the area, who provided fresh energy and industry to the burgeoning city. It also drove the dishonest outsiders out of the town in search of easier prey, since DragonBucks made theft impossible for them.
However, it also introduced a problem: while newcomers could receive DragonBucks, they couldn’t sign their own notes, as they weren’t born with the ability to cast a unique spell. The members of the newly formed Cryptonian Academy of Scholars gathered to come up with a solution.
They figured that their best shot to integrate the non-magical denizens of Cryptonia into the new currency would be to use one of the closest things the rest of us have to magic: mathematics.
The Cryptonian scholars need to find mathematical replacements for the functions of DragonBucks. In particular, they need something to replace the dragon so that people can verify that a transaction is valid, and they need replacements for spells as personal identities.
To make it easier to talk about these replacements, we can give names to each part of the system. Since a Cryptonian’s spellcasting ability is personal to them, it's called a The visual spell effect is connected to this spellcasting ability but can be publicly shared, so it's a A transaction note is a and the enchanted wax seal is a since it's used to prove who sent a message.
The crucial step is being able to verify a while hiding the that generated it. In this quiz, you'll learn about a mathematical function that hides information and can help us towards this goal.
We're borrowing these names from public-key cryptography, but you don't need to be familiar with public-key cryptography to understand this quiz.
The Cryptonian scholars start by considering a very simple mathematical system that uses numbers in place of spells and transaction notes and also uses multiplication to move between each step. Here's how user identities and sending messages would work in this system:
- Everyone picks a number for their which they don't reveal, but they share as their .
- Each is converted into a number .*
- The person sending the produces a to prove they're the one who sent it by calculating .
For example, Alice has a of and wants to send the (a real message would be much longer, but we've truncated it so that you don't need to find your calculator):
The last piece of the system is that we need to be able to verify that Alice was the one to produce her .
What equation must be true if Alice's of was calculated from the product of her and ?
*An example of how to perform this conversion is examined later in the chapter. You'd need to be careful about the details of how to convert a message to a number when building a real system, but for now we can just trust that it's possible.
In the proposed system, we can verify a by checking that the following equation is true: because if we substitute in the and used to generate the and , it produces The order of multiplication doesn't matter and both these expressions have the exact same factors and , so they'll be equal for a valid .
When Alice sends the with the this will check out since
But this belies the real problem with the system: it isn't secure. What is Alice's ?
Your needs to be something that only you can produce. The simple multiplication scheme doesn't work because anyone who understands the rules of the system can steal your just by dividing!
To replace DragonBucks, we need to be able to verify a without compromising the security of the associated with it.
Which of the following ways of calculating a would prevent you from immediately determining the exact value of the used to generate it?
Assume that the is always a positive integer.
Most ordinary functions don't hide their inputs very well: you can reverse addition with subtraction, division with multiplication, squaring with taking the square root, and so on.
Fortunately, there are some functions that can't be easily reversed. For example, if we share the remainder after dividing a by it doesn't reveal the : there are infinite possibilities. If the remainder of divided by is , could be or or or or
The modulo operation for short divides by a number (the "modulus") and returns the remainder, so we can write the situation above as
Consider
We can view as its remainder plus some multiple of keeps the remainder, but the multiples of are lost, so that part of the original number remains hidden.
If we can use to verify a while hiding the that generated it, that will help us mathematize the DragonBucks system.
Taking the remainder of a lone number hides information about that number, so perhaps taking the remainder after multiplication will hide information about the factors that went into that multiplication.
This could make especially helpful for hiding the used to generate a .
If we multiplied the by the and then took the remainder after dividing by using this value as the instead of might hide our better.
Alice is going to send the and generates a by calculating . If her is , could we calculate Alice's ?
Using to generate a does a much better job of hiding the used to produce it — simple division will no longer reveal .
Graphically, is the area of a rectangle with side lengths and If we apply to that area, any multiples of in it are lost, and it becomes much harder to find or from that remainder:
This is because as long as is bigger than at least one multiple of will get thrown out when is applied. Losing any part of means that dividing by will not recover
Instead of just dividing the to find , a would-be impostor now has a lot more work ahead of them. The simplest approach they could use would be to try different values of until they found one such that The value of satisfying this equation would be a candidate for .
But if we make the numbers big enough (, in particular), then we can make this search take a long time and therefore keep safe. This approach lets someone publish a without revealing their one of the key properties that will allow us to mathematize DragonBucks!
With in our toolbox, we're ready to take another crack at the mathematization of DragonBucks. Supercharged with modular arithmetic, our naive multiplication scheme might not be so bad after all.
Since allows us to hide inputs, we can integrate modular arithmetic into an updated version of the system. Here's how user identities and sending messages could work after the update:
- Everyone agrees on a number to use as the modulus of the system.
- Everyone picks a which they don't reveal, but they share as their .
- Each is converted into a number .
- The for a is .
The last step of the system is that we need to be able to verify each , confirming that it used the correct when it was created. What needs to be true of in order for it to be possible to verify a in this new scheme using only public information?
For our system to work, we also need to be able to verify each . Helping us achieve this is the fact that even though the modular product hides the factors going into it, associativity and commutativity still apply.
In simpler terms, this means that the order in which you multiply the numbers and apply doesn't matter. You'll always get the same result after applying a final at the end.
Consider an example where and . Whether we apply at every step, or only apply after multiplying the message and secret key, we'll get the same result:
| Apply at every step | Apply only at the end |
It's not crucial for you to understand why this is the case, but if you're curious, it's because whether you apply before or after multiplying, it still has the effect of removing multiples of from the product. Any multiples of that make it through to the end will be removed by the final , leading to the same result:
Since the order of modular products doesn't change the final outcome, we can add the final step of verification to our system. Anyone can verify a by confirming that it equals . This works because And whether you take the modular product of and or the modular product of and you'll get the same result.
Here's an overview of all the steps:
With this implementation of into our system, are all the steps secure?
For the purposes of multiplication in , knowing the remainder of the is equivalent to knowing the itself, so a of isn't secure.
Fortunately, the fix isn't far off. We just saw that even if we know one number of a product, it's still hard to find the other one: hides even if we know .
With this in mind, we can change our scheme just a little bit:
Suppose everybody agrees on a common number . They still pick a as before, but now they share as their . The for a is still , but now the verification happens by confirming that These will be equal for a valid because both sides of the equation contain only and as factors.
Suppose we use this system with and If you receive the from Alice, whose is , and the included is was the really sent by Alice? Assume Alice is the only person with access to her .
The calculator below (recovered from Cryptonia) is programmed with the modular arithmetic of the DragonBucks system. You can use it to help to answer the question:
With this new system, the Cryptonians have successfully divorced their DragonBucks scheme from spellcasting, and can open it up to everyone regardless of their magical abilities. Their modular products scheme has three key features:
- Everyone has an identity that no one else can fake.
- Everyone can sign transactions.
- Everyone can verify that transactions are valid.
A serviceable mathematician herself, the dragon is satisfied with the security of mathematically signed DragonBucks and is happy to process them, allowing the magically challenged newcomers to fully participate in the Cryptonian economy.
To facilitate the spread of the system, the Cryptonian scholars made calculators that could quickly calculate large modular products and distributed these calculators among the townsfolk.
If you're a number theory wizard yourself, you've probably noticed a problem with the security of DragonBucks. Don't worry, this will be addressed later in the course.