Cryptography: Learn It 6

The One-Way Function

To get public key cryptography to work for computer communication, we need to have the process result in a share common number to act as the common secret encryption key. For this, we need a numerical one-way function.

If you think back to doing division with whole numbers, you may remember finding the whole number result and the remainder after division.

modulus

The modulus is another name for the remainder after division.
 
For example, [latex]17 \text{ mod } 5 = 2[/latex], since if we divide [latex]17[/latex] by [latex]5[/latex], we get [latex]3[/latex] with remainder [latex]2[/latex] .

Modular arithmetic is sometimes called clock arithmetic, since analog clocks wrap around times past [latex]12[/latex], meaning they work on a modulus of [latex]12[/latex]. If the hour hand of a clock currently points to [latex]8[/latex], then in [latex]5[/latex] hours it will point to [latex]1[/latex]. While [latex]8+5=13[/latex], the clock wraps around after [latex]12[/latex], so all times can be thought of as modulus [latex]12[/latex]. Mathematically, [latex]13 \bmod 12 = 1[/latex] .

Compute:

  1. [latex]10 \text{ mod } 3[/latex]
  2. [latex]15 \text{ mod } 5[/latex]
  3. [latex]2^7 \text{ mod } 5[/latex]

How To: Calculate [latex]a \text{ mod }n[/latex] on a Standard Calculator, With or Without a Modulus Function

For calculators without a modulus function:

  1. Input the number [latex]a[/latex] and divide it by the modulus [latex]n[/latex]. Note the result of this division.
  2. Identify and subtract the whole part (integer part) of the division result from the actual division result. This step isolates the fractional part of the division.
  3. Multiply the fractional part by [latex]n[/latex]. The result is [latex]a \text{ mod }n[/latex].

For calculators with a modulus function:

  1. Input the number [latex]a[/latex] into the calculator. 
  2. Use the modulus function on the calculator, often labeled as “mod”.
  3. Input the modulus number [latex]n[/latex]. 
  4. The calculator will display [latex]a \text{ mod }n[/latex]. 

When you use a prime number [latex]p[/latex] as a modulus, you can find a special number called a generator, [latex]g[/latex], so that [latex]g^n \text{ mod } p[/latex] will result in all the values from [latex]1[/latex] to [latex]p−1[/latex] .

[latex]\begin{array}{|l|l|l|}
\hline n & 3^{n} & 3^{n} \mathrm{mod} 7 \\
\hline 1 & 3 & 3 \\
\hline 2 & 9 & 2 \\
\hline 3 & 27 & 6 \\
\hline 4 & 81 & 4 \\
\hline 5 & 243 & 5 \\
\hline 6 & 729 & 1 \\
\hline
\end{array}
[/latex]

In the table above, notice that when we give values of n from [latex]1[/latex] to [latex]6[/latex], we get out all values from [latex]1[/latex] to [latex]6[/latex]. This means [latex]3[/latex] is a generator when [latex]7[/latex] is the modulus. This gives us our one-way function. While it is easy to compute the value of [latex]g^n \text{ mod } p[/latex] when we know [latex]n[/latex], it is difficult to find the exponent n to obtain a specific value.

For example, suppose we use [latex]p=23[/latex] and [latex]g=5[/latex]. If I pick [latex]n[/latex] to be [latex]6[/latex], I can fairly easily calculate:

[latex]5^6 \text{ mod }23=15625 \text{ mod }23=8[/latex].

If someone else were to tell you [latex]5^n\text{ mod }23=7[/latex], it is much harder to find [latex]n[/latex]. In this particular case, we’d have to try [latex]22[/latex] different values for [latex]n[/latex] until we found one that worked – there is no known easier way to find [latex]n[/latex] other than brute-force guessing.

While trying [latex]22[/latex] values would not take too long, when used in practice much larger values for [latex]p[/latex] are used, typically with well over [latex]500[/latex] digits. Trying all possibilities would be essentially impossible.

Before we can begin the key exchange process, we need a couple more important facts about modular arithmetic.

modular exponentiation rule

[latex]\left(a^{b} \bmod n\right)=(a \bmod n)^{b} \bmod n[/latex]

How To: Perform Modular Exponentiation on a Standard Calculator, With or Without a Modulus Function

For calculators without a modulus function:

  1. Divide [latex]a^b[/latex] by [latex]n[/latex] and note the result.
  2. Identify the whole part of this division.
  3. Subtract this whole part from the result of the division to get the fractional part.
  4. Multiply the fractional part by [latex]n[/latex]. The result is [latex]a \text{ mod }n[/latex].

For calculators with a modulus function:

  1. Input the number [latex]a^b[/latex] into the calculator. 
  2. Use the modulus function on the calculator, often labeled as “mod”.
  3. Input the modulus number [latex]n[/latex] after [latex]a^b[/latex]. 
  4. The calculator will display [latex]a \text{ mod }n[/latex]. 
Compute [latex]12^5 \text{ mod } 7[/latex] using the exponentiation rule.

You may remember a basic exponent rule from algebra:

[latex]\left(a^{b}\right)^{c}=a^{b c}=a^{c b}=\left(a^{c}\right)^{b} \nonumber[/latex]

For example:

[latex]64^{2}=\left(4^{3}\right)^{2}=4^{6}=\left(4^{2}\right)^{3}=16^{3} \nonumber[/latex]

We can combine the modular exponentiation rule with the algebra exponent rule to define the modular exponent power rule.

modular exponent power rule

[latex]\left(a^{b} \bmod n\right)^{c} \bmod n=\left(a^{b c} \bmod n\right)=\left(a^{c} \bmod n\right)^{b} \bmod n \nonumber[/latex]
Verify the rule above if [latex]a=3, b=4, c=5, \text{ and } n=7[/latex] .