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.

Cryptographic Signatures


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 secretKey.\tt secretKey. The visual spell effect is connected to this spellcasting ability but can be publicly shared, so it's a publicKey.\tt publicKey. A transaction note is a message,\tt message, and the enchanted wax seal is a signature\tt signature since it's used to prove who sent a message.

The crucial step is being able to verify a signature\tt signature while hiding the secretKey\tt secretKey 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.

Cryptographic Signatures


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:

  1. Everyone picks a number ss for their secretKey\tt secretKey which they don't reveal, but they share 5×s5\times s as their publicKey\tt publicKey.
  2. Each message\tt message is converted into a number mm.*
  3. The person sending the message\tt message produces a signature\tt signature to prove they're the one who sent it by calculating m×sm \times s.

For example, Alice has a publicKey\tt publicKey of 3535 and wants to send the message\tt message 101101 (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 signature\tt signature.

What equation must be true if Alice's signature\tt signature of 707707 was calculated from the product of her secretKey\tt secretKey and message\tt message?

*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.

Cryptographic Signatures


In the proposed system, we can verify a signature\tt signature by checking that the following equation is true: signature×5=publicKey×m, \texttt{signature}\times 5 = \texttt{publicKey}\times m, because if we substitute in the secretKey s\texttt{secretKey}\ s and message m\texttt{message}\ m used to generate the signature\tt signature and publicKey\tt publicKey, it produces (m×s)signature×5=(5×s)publicKey×m.\overbrace{\left(m\times s\right)}^\texttt{signature}\times 5 = \overbrace{\left(5 \times s\right)}^\texttt{publicKey} \times m. The order of multiplication doesn't matter and both these expressions have the exact same factors (5,m,(5, m, and s)s), so they'll be equal for a valid signature\tt signature.

When Alice (publicKey=35)(\texttt{publicKey} = 35) sends the message\tt message 101101 with the signature\tt signature 707,707, this will check out since 707×5=35×101.707 \times 5 = 35 \times 101.

But this belies the real problem with the system: it isn't secure. What is Alice's secretKey\tt secretKey?

Cryptographic Signatures


Your signature\tt signature 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 secretKey\tt secretKey just by dividing!

To replace DragonBucks, we need to be able to verify a signature\tt signature without compromising the security of the secretKey\tt secretKey associated with it.

Which of the following ways of calculating a publicKey\tt publicKey would prevent you from immediately determining the exact value of the secretKey\tt secretKey used to generate it?

Assume that the secretKey\tt secretKey is always a positive integer.

Cryptographic Signatures


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 secretKey\tt secretKey by 17,17, it doesn't reveal the secretKey\tt secretKey: there are infinite possibilities. If the remainder of ss divided by 1717 is 55, ss could be 55 or 2222 or 3939 or 5656 or \ldots

The modulo operation (mod(\bmod{} for short)) divides by a number (the "modulus") and returns the remainder, so we can write the situation above as (remainder)=smod17.(\text{remainder}) = s\bmod{17}.

Consider 63mod17:63 \bmod{17}:

We can view 6363 as its remainder plus some multiple of 17:17: 63=12+3×17=(remainder)+(some number)×17.63 = 12 + 3 \times 17 = (\text{remainder}) + (\text{some number}) \times 17. mod17\bmod{\>17} keeps the remainder, but the multiples of 1717 are lost, so that part of the original number remains hidden.

If we can use mod\bmod{} to verify a signature\tt signature while hiding the secretKey\tt secretKey that generated it, that will help us mathematize the DragonBucks system.

Cryptographic Signatures


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 mod\bmod{} especially helpful for hiding the secretKey\tt secretKey used to generate a signature\tt signature.

If we multiplied the message\tt message by the secretKey\tt secretKey and then took the remainder after dividing by n:n: (m×s)modn,(m\times s) \bmod{n}, using this value as the signature\tt signature instead of m×sm\times s might hide our secretKey\tt secretKey better.

Alice is going to send the message\tt message 101101 and generates a signature\tt signature by calculating (m×s)mod17(m\times s) \bmod{17}. If her signature\tt signature is 1212, could we calculate Alice's secretKey\tt secretKey?

Cryptographic Signatures


Using (m×s)modn(m \times s)\bmod{n} to generate a signature\tt signature does a much better job of hiding the secretKey\tt secretKey used to produce it — simple division will no longer reveal ss.

Graphically, m×sm \times s is the area of a rectangle with side lengths mm and s.s. If we apply modn\bmod{\>n} to that area, any multiples of nn in it are lost, and it becomes much harder to find mm or ss from that remainder:

This is because as long as m×sm \times s is bigger than n,n, at least one multiple of nn will get thrown out when modn\bmod{\>n} is applied. Losing any part of m×sm \times s means that dividing by mm will not recover s.s.

Cryptographic Signatures


Instead of just dividing the signature\tt signature to find ss, 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 tt until they found one such that (m×t)modn=signature=(m×s)modn.\begin{aligned} (m\times t)\bmod{n} &= \texttt{signature} \\ &= (m\times s)\bmod{n}. \end{aligned} The value of tt satisfying this equation would be a candidate for ss.

But if we make the numbers big enough (nn, in particular), then we can make this search take a long time and therefore keep secretKey\tt secretKey safe. This approach lets someone publish a signature\tt signature without revealing their secretKey,\tt secretKey, one of the key properties that will allow us to mathematize DragonBucks!

Cryptographic Signatures


With mod\bmod{} 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 mod\bmod{} 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:

  1. Everyone agrees on a number nn to use as the modulus of the system.
  2. Everyone picks a secretKey\tt secretKey ss which they don't reveal, but they share smodns\bmod{n} as their publicKey\tt publicKey.
  3. Each message\tt message is converted into a number mm.
  4. The signature\tt signature for a message\tt message mm is (m×s)modn(m \times s)\bmod{n}.

The last step of the system is that we need to be able to verify each signature\tt signature, confirming that it used the correct secretKey\tt secretKey when it was created. What needs to be true of (m×s)modn(m \times s)\bmod{n} in order for it to be possible to verify a signature\tt signature in this new scheme using only public information?

Cryptographic Signatures


For our system to work, we also need to be able to verify each signature\tt signature. 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 modn\bmod{\>n} doesn't matter. You'll always get the same result after applying a final modn\bmod{\>n} at the end.

Consider an example where m=569,s=1187,m = 569, s = \num{1187}, and n=447n=447. Whether we apply mod\bmod{} at every step, or only apply mod\bmod{} after multiplying the message and secret key, we'll get the same result:

Apply mod\bmod{} at every stepApply mod\bmod{} only at the end
569mod447=122569\bmod{447} = 122569×1187=675403569 \times \num{1187} = \num{675403}
1187mod447=293\num{1187}\bmod{447} = 293675403mod447=433\num{675403}\bmod{447} = 433
122×293=35746122 \times 293 = \num{35746}
35746mod447=433\num{35746}\bmod{447} = 433

It's not crucial for you to understand why this is the case, but if you're curious, it's because whether you apply modn\bmod{\>n} before or after multiplying, it still has the effect of removing multiples of nn from the product. Any multiples of nn that make it through to the end will be removed by the final modn\bmod{\>n}, leading to the same result:

Cryptographic Signatures


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 signature\tt signature by confirming that it equals (publicKey×m)modn(\texttt{publicKey} \times m)\bmod{n}. This works because signature=(publicKey×m)modn(m×s)modn=((smodn)×m)modn.\begin{aligned} \texttt{signature} &= (\texttt{publicKey} \times m)\bmod{n} \\ (m\times s)\bmod{n} &= \big((s\bmod{n}) \times m\big)\bmod{n}. \end{aligned} And whether you take the modular product of mm and ss or the modular product of (smodn)(s\bmod{n}) and m,m, you'll get the same result.

Here's an overview of all the steps:

With this implementation of mod\bmod into our system, are all the steps secure?

Cryptographic Signatures


For the purposes of multiplication in modn\bmod{\>n}, knowing the remainder of the secretKey\tt secretKey is equivalent to knowing the secretKey\tt secretKey itself, so a publicKey\tt publicKey of smodns \bmod{n} 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: (m×s)modn{(m \times s) \bmod{n}} hides ss even if we know mm.

With this in mind, we can change our scheme just a little bit:

Suppose everybody agrees on a common number gg. They still pick a secretKey\tt secretKey ss as before, but now they share (g×s)modn(g \times s) \bmod{n} as their publicKey\tt publicKey. The signature\tt signature for a message\tt message mm is still (m×s)modn(m \times s)\bmod{n}, but now the verification happens by confirming that (publicKey×m)modn=(signature×g)modn.(\texttt{publicKey} \times m)\bmod{n} = (\texttt{signature} \times g)\bmod{n}. These will be equal for a valid signature\tt signature because both sides of the equation contain only g,s,g, s, and mm as factors.

Suppose we use this system with n=179n = 179 and g=59.g = 59. If you receive the message\tt message 101101 from Alice, whose publicKey\tt publicKey is 2424, and the included signature\tt signature is 123,123, was the message\tt message really sent by Alice? Assume Alice is the only person with access to her secretKey\tt secretKey.

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:

Cryptographic Signatures


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:

  1. Everyone has an identity that no one else can fake.
  2. Everyone can sign transactions.
  3. 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.

Cryptographic Signatures


Problem Loading...

Note Loading...

Set Loading...