{"id":2328,"date":"2023-05-08T19:12:45","date_gmt":"2023-05-08T19:12:45","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&p=2328"},"modified":"2024-10-18T20:53:31","modified_gmt":"2024-10-18T20:53:31","slug":"cryptography-learn-it-6","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/cryptography-learn-it-6\/","title":{"raw":"Cryptography: Learn It 6","rendered":"Cryptography: Learn It 6"},"content":{"raw":"

The One-Way Function<\/h2>\r\n

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.<\/p>\r\n

If you think back to doing division with whole numbers, you may remember finding the whole number result and the remainder after division.<\/p>\r\n

\r\n
\r\n

modulus<\/h3>\r\n

The modulus<\/strong> is another name for the remainder after division.
\r\n\u00a0
\r\nFor 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] .<\/p>\r\n<\/div>\r\n<\/section>\r\n

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] .<\/p>\r\n

Compute:\r\n\r\n
    \r\n\t
  1. [latex]10 \\text{ mod } 3[\/latex]<\/li>\r\n\t
  2. [latex]15 \\text{ mod } 5[\/latex]<\/li>\r\n\t
  3. [latex]2^7 \\text{ mod } 5[\/latex]<\/li>\r\n<\/ol>\r\n

    [reveal-answer q=\"4330\"]Show Solution[\/reveal-answer]
    \r\n[hidden-answer a=\"4330\"]<\/p>\r\n

      \r\n\t
    1. \r\n
        \r\n\t
      1. Since [latex]10[\/latex] divided by [latex]3[\/latex] is [latex]3[\/latex] with remainder [latex]1[\/latex], [latex]10 \\text{ mod }3=1[\/latex]<\/li>\r\n\t
      2. Since [latex]15[\/latex] divided by [latex]5[\/latex] is [latex]3[\/latex] with no remainder, [latex]15 \\text{ mod }5=0[\/latex]<\/li>\r\n\t
      3. [latex]2^7=128.128[\/latex] divide by [latex]5[\/latex] is [latex]25[\/latex] with remainder [latex]3[\/latex], so [latex]2^7 \\text{ mod }5=3[\/latex]<\/li>\r\n<\/ol>\r\n<\/li>\r\n<\/ol>\r\n

        [\/hidden-answer]<\/p>\r\n<\/section>\r\n

        \r\n

        How To:<\/strong> Calculate [latex]a \\text{ mod }n[\/latex] on a Standard Calculator, With or Without a Modulus Function<\/strong>
        \r\n
        \r\nFor calculators without a modulus function:<\/p>\r\n

          \r\n\t
        1. Input the number [latex]a[\/latex] and divide it by the modulus [latex]n[\/latex]. Note the result of this division.<\/li>\r\n\t
        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.<\/li>\r\n\t
        3. Multiply the fractional part by [latex]n[\/latex]. The result is [latex]a \\text{ mod }n[\/latex].<\/li>\r\n<\/ol>\r\n

          For calculators with a modulus function:<\/p>\r\n

            \r\n\t
          1. Input the number [latex]a[\/latex] into the calculator.\u00a0<\/li>\r\n\t
          2. Use the modulus function on the calculator, often labeled as \"mod\".<\/li>\r\n\t
          3. Input the modulus number [latex]n[\/latex].\u00a0<\/li>\r\n\t
          4. The calculator will display [latex]a \\text{ mod }n[\/latex].\u00a0<\/li>\r\n<\/ol>\r\n<\/section>\r\n

            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\u22121[\/latex] .<\/p>\r\n

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

            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.<\/p>\r\n

            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:<\/p>\r\n

            [latex]5^6 \\text{ mod }23=15625 \\text{ mod }23=8[\/latex].<\/p>\r\n

            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\u2019d have to try [latex]22[\/latex] different values for [latex]n[\/latex] until we found one that worked \u2013 there is no known easier way to find [latex]n[\/latex] other than brute-force guessing.<\/p>\r\n

            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.<\/p>\r\n

            Before we can begin the key exchange process, we need a couple more important facts about modular arithmetic.<\/p>\r\n

            \r\n
            \r\n

            modular exponentiation rule<\/h3>\r\n
            [latex]\\left(a^{b} \\bmod n\\right)=(a \\bmod n)^{b} \\bmod n[\/latex]<\/center><\/div>\r\n<\/section>\r\n
            \r\n

            How To:<\/strong> Perform Modular Exponentiation on a Standard Calculator, With or Without a Modulus Function<\/strong>
            \r\n
            \r\nFor calculators without a modulus function:<\/p>\r\n

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

              For calculators with a modulus function:<\/p>\r\n

                \r\n\t
              1. Input the number [latex]a^b[\/latex] into the calculator.\u00a0<\/li>\r\n\t
              2. Use the modulus function on the calculator, often labeled as \"mod\".<\/li>\r\n\t
              3. Input the modulus number [latex]n[\/latex] after [latex]a^b[\/latex].\u00a0<\/li>\r\n\t
              4. The calculator will display [latex]a \\text{ mod }n[\/latex].\u00a0<\/li>\r\n<\/ol>\r\n<\/section>\r\n
                Compute [latex]12^5 \\text{ mod } 7[\/latex] using the exponentiation rule.
                \r\n[reveal-answer q=\"4331\"]Show Solution[\/reveal-answer]
                \r\n[hidden-answer a=\"4331\"]
                \r\nEvaluated directly: [latex]12^{5}=248,832[\/latex], so [latex]12^{5}\\text{ mod } 7 = 5^5\\text{ mod } 7=3125\\text{ mod } 7=3[\/latex]
                \r\n[\/hidden-answer]<\/section>\r\n

                You may remember a basic exponent rule from algebra:<\/p>\r\n

                [latex]\\left(a^{b}\\right)^{c}=a^{b c}=a^{c b}=\\left(a^{c}\\right)^{b} \\nonumber[\/latex]<\/p>\r\n

                For example:<\/p>\r\n

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

                We can combine the modular exponentiation rule with the algebra exponent rule to define the modular exponent power rule.<\/p>\r\n

                \r\n
                \r\n

                modular exponent power rule<\/h3>\r\n
                [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]<\/center><\/div>\r\n<\/section>\r\n
                Verify the rule above if [latex]a=3, b=4, c=5, \\text{ and } n=7[\/latex] .
                \r\n[reveal-answer q=\"4332\"]Show Solution[\/reveal-answer]
                \r\n[hidden-answer a=\"4332\"]
                \r\n[latex]\\left(3^{4} \\bmod 7\\right)^{5} \\bmod 7=(81 \\bmod 7)^{5} \\bmod 7=4^{5} \\bmod 7=1024 \\bmod 7=2[\/latex]
                \r\n[latex]\\left(3^{5} \\bmod 7\\right)^{4} \\bmod 7=(243 \\bmod 7)^{4} \\bmod 7=5^{4} \\bmod 7=625 \\bmod 7=2[\/latex], the same result.
                \r\n[\/hidden-answer]<\/section>","rendered":"

                The One-Way Function<\/h2>\n

                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.<\/p>\n

                If you think back to doing division with whole numbers, you may remember finding the whole number result and the remainder after division.<\/p>\n

                \n
                \n

                modulus<\/h3>\n

                The modulus<\/strong> is another name for the remainder after division.
                \n\u00a0
                \nFor 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] .<\/p>\n<\/div>\n<\/section>\n

                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] .<\/p>\n

                Compute:<\/p>\n
                  \n
                1. [latex]10 \\text{ mod } 3[\/latex]<\/li>\n
                2. [latex]15 \\text{ mod } 5[\/latex]<\/li>\n
                3. [latex]2^7 \\text{ mod } 5[\/latex]<\/li>\n<\/ol>\n