Colab_プログラム入門(1).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Colab プログラム入門(1)",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.7"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/nagae/ICL_B_2021/blob/main/Colab_%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E5%85%A5%E9%96%80(1).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h2JIY9IQ94d-"
      },
      "source": [
        "# Colabプログラム入門(1) 変数と四則演算\n",
        "\n",
        "Colaboratory では， **Python** という言語を使ったプログラムが実行できる． プログラムが使えるようになることで， 複雑な科学技術計算や膨大な反復処理が可能になる．このノートブックでは，変数と四則演算について練習しよう．"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h2oDPijuFDi9"
      },
      "source": [
        "# 変数と四則演算\n",
        "Python においては，**変数** とは，値を格納する「箱」のようなものだ(正確には，変数は「値を格納する箱の場所」を表す)．次のセルを実行すると，`a`と`b`という2つの変数が準備され，それぞれに`10`と`6`という値が格納される．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hKC5sp1Y9-6a"
      },
      "source": [
        "## 2つの変数 a, b に値を格納する\n",
        "a = 10 # a ← 10 \n",
        "b = 6"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7M1mJ9LMFDjB"
      },
      "source": [
        "変数の中身を確認するには，変数を[`print`関数](https://docs.python.org/ja/3/library/functions.html#print)の引数として渡す．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tm1lnDBzFDjB",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c359f1b1-bb7f-4579-813b-a422df375e1c"
      },
      "source": [
        "## 変数の中身を確認する\n",
        "print(a) # a の中身だけを表示\n",
        "print(\"a=\", a) # \"a=\"という文字列のあとに a の中身を表示\n",
        "print(a, b) # a と b の中身を並べて表示\n",
        "print(\"a=\", a, \"b=\", b) # \"a=\"の後に a の中身, \"b=\" の後に b の中身を表示"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "10\n",
            "a= 10\n",
            "10 6\n",
            "a= 10 b= 6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wTpny_czFDjF"
      },
      "source": [
        "変数 `a` と `b` に対する **四則演算** は以下のように記述できる．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OfscqgWYFDjF",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f6e58ef7-a1ac-4815-e5c8-75a490a290f8"
      },
      "source": [
        "## 四則演算\n",
        "print(\"a+b=\", a+b) # 和\n",
        "print(\"a-b=\", a-b) # 差\n",
        "print(\"a*b=\", a*b) # 積\n",
        "print(\"a/b=\", a/b) # 除\n",
        "## 整数の商と剰余\n",
        "print(\"a//b=\", a//b) # 商\n",
        "print(\"a%b=\", a%b) # 剰余"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "a+b= 16\n",
            "a-b= 4\n",
            "a*b= 60\n",
            "a/b= 1.6666666666666667\n",
            "a//b= 1\n",
            "a%b= 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iLI95Tvj-tiJ"
      },
      "source": [
        "## 【練習】 四則演算と商・剰余\n",
        "上述の四則演算と商・剰余を，下記の組み合わせに対して実行してみよう．\n",
        "\n",
        "| a | b | \n",
        "|---|---|\n",
        "| 2 | 5 |\n",
        "| -4 | 7 |\n",
        "| 11 | -3|\n",
        "| -8 | -5|"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iC-FflWDOn1P",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b0da06d9-62ef-460e-f9ef-145479b8a08e"
      },
      "source": [
        "a = 2\n",
        "b = 5\n",
        "print(\"a + b = \", a + b)\n",
        "print(\"a - b = \", a - b)\n",
        "print(\"a * b = \", a * b)\n",
        "print(\"a / b = \", a / b)\n",
        "print(\"a // b = \", a // b)\n",
        "print(\"a % b = \", a % b)"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "a + b =  7\n",
            "a - b =  -3\n",
            "a * b =  10\n",
            "a / b =  0.4\n",
            "a // b =  0\n",
            "a % b =  2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vKPHfIIx_ylJ"
      },
      "source": [
        "## 【余談】 負の数に対する商・剰余\n",
        "負の数に対する商・剰余は，**プログラム言語によって異なる結果を返す**ため，極力，使わない方がよい．\n",
        "\n",
        "例えば，同じ式であっても，C言語と呼ばれるプログラム言語と Python とでは，以下のように評価結果が異なる：\n",
        "\n",
        "| 計算式 | C言語 | Python |\n",
        "|---|---|---|\n",
        "|`   11 % 3` | ` 2` | ` 2`|\n",
        "|`(-11) % 3` | `-2`  | ` 1` |\n",
        "|`   11 % (-3)` |` 2` | `-1` |\n",
        "|`(-11) % (-3)`| `-2` | `-2` |\n",
        "\n",
        "その理由は「[だって，そういう仕様だから](https://ja.stackoverflow.com/questions/66236/python-%E3%81%A7-%E8%B2%A0%E3%81%AE%E6%95%B0%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%9F%E5%89%B0%E4%BD%99%E7%AE%97%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)」以外には無い．文句を言っても仕方ないので，極力使わないのが賢明．\n",
        "\n",
        "以降では，実際にC言語プログラムとPythonを実行してみて，その結果の違いを確認してみよう．\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ug1tO_oKFOpY"
      },
      "source": [
        "### C言語の場合\n",
        "下記のセルを実行することで，C言語のソースコードが書かれた `mod.c` というファイルが生成される．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "izpYA8blAoMV",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "10485d36-d945-49f6-f5dd-23a544415fe1"
      },
      "source": [
        "%%file mod.c \n",
        "#include <stdio.h>\n",
        "#include <stdlib.h>\n",
        "int main(int argc, char **argv){\n",
        "    int a, b;\n",
        "    if (argc < 2){ fprintf(stderr, \"Error: insufficient argument\"); return(-1); }\n",
        "    else{\n",
        "        a = atoi(argv[1]);\n",
        "        b = atoi(argv[2]);\n",
        "    }\n",
        "    printf(\"(%d)%%(%d)=%d\\n\", a, b, (a%b) );\n",
        "    return(a%b);\n",
        "}"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Writing mod.c\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "m7YjicbNFDjL"
      },
      "source": [
        "C言語では，`mod.c` というソースファイルはそのまま実行できず，これを**コンパイル**して実行ファイルを作る必要がある．以下のセルを実行すると，`mod.c` から実行ファイル `mod` が生成される．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Z1IIS2MTBg1X",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9a1bc285-6be5-40ce-f6d2-53063f88a6a7"
      },
      "source": [
        "# C言語で計算する (-11)%3, 11%(-3) および (-11)%(-3)\n",
        "!gcc mod.c -o mod # C言語プログラムをコンパイルして実行ファイルを作成\n",
        "!chmod 755 ./mod # 作成した実行ファイルに実行権限を与える\n",
        "# 以下，それぞれ実行ファイルを呼び出して計算結果を表示\n",
        "!./mod  11  3\n",
        "!./mod -11  3\n",
        "!./mod  11 -3\n",
        "!./mod -11 -3"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(11)%(3)=2\n",
            "(-11)%(3)=-2\n",
            "(11)%(-3)=2\n",
            "(-11)%(-3)=-2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n0b69qN1FDjO"
      },
      "source": [
        "### Python の場合\n",
        "Python はC言語のようなコンパイルの必要がない(**インタプリタ言語**と呼ばれる)．以下のセルを実行すれば，計算結果が得られる"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WjKlwKfLBxSX",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "25b58150-9021-4843-ca0e-51e14ead3fe2"
      },
      "source": [
        "# Pythonで計算する (-11)%3, 11%(-3) および (-11)%(-3)\n",
        "print( \"(11) %(3) =\",    11%  3  )\n",
        "print( \"(-11)%(3) =\", (-11)%  3  )\n",
        "print( \"(11) %(-3)=\",    11%(-3) )\n",
        "print( \"(-11)%(-3)=\", (-11)%(-3) )"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(11) %(3) = 2\n",
            "(-11)%(3) = 1\n",
            "(11) %(-3)= -1\n",
            "(-11)%(-3)= -2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RKP_2mAAM0bt"
      },
      "source": [
        "# 百五減算\n",
        "和算の一種で，江戸時代の数学の本「塵劫記」に載っているらしい．0以上105未満のある不明な数 (例えば他人の年齢) $x$ について，\n",
        "- $x$ を3で割った余り $a$\n",
        "- $x$ を5で割った余り $b$\n",
        "- $x$ を7で割った余り $c$\n",
        "\n",
        "のみから元の数$x$を当てる計算方法．\n",
        "\n",
        "計算式をPython風に表せば，\n",
        "```python\n",
        "x = (70 * a + 21 * b + 15 * c) % 105\n",
        "```\n",
        "となる．\n",
        "\n",
        "もとの和算では，これを計算するのに「括弧内が 105 を超えている場合には，105を繰返し引く」という操作をしたため **百五減算** と呼ばれている．\n",
        "\n",
        "## 【練習】\n",
        "以下のセルの `x=19` の部分を色々書き換えてみて，どんな場合にも, $a, b, c$だけから正しくもとの$x$が求められるかやってみよう．\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SAYOQwzx-Qin",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f22d8073-ab57-46dc-a0ed-68bf83084a34"
      },
      "source": [
        "#### xから a, b, c を求める\n",
        "x=19 # もとの数 ← これを他の数値に変えてセルを実行してみよう\n",
        "a = x % 3 # 3で割った余り\n",
        "b = x % 5 # 5で割った余り\n",
        "c = x % 7 # 7で割った余り\n",
        "print(\"a=\", a, \"b=\", b, \"c=\", c) # それぞれの余りを表示\n",
        "\n",
        "#### a, b, c から x を求める\n",
        "x =  (70 * a + 21 * b + 15 * c) % 105 # 百五減算でもとの数\n",
        "print(\"x=\", x)"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "a= 1 b= 4 c= 5\n",
            "x= 19\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "b4V4JjkxXm2U"
      },
      "source": [
        "## 【余談】\n",
        "今回の講義の範疇ではないが，`for` を使うと，全ての`x`について正しく計算できるかどうかが調べられる．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "juWWMfIaXmI1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7c2da525-3e1d-4281-9574-a106559911bb"
      },
      "source": [
        "for x in range(105): # range(1,105)は0以上105未満の整数集合を作り出す\n",
        "    a = x % 3\n",
        "    b = x % 5\n",
        "    c = x % 7\n",
        "    X = (70*a + 21*b + 15*c) % 105 # 複合化された数値\n",
        "    print(x, \"=\", X, end=', ') # 元の数値xと複合化された数値Xを並べて表示(鬱陶しいので改行しないようにしている)"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0 = 0, 1 = 1, 2 = 2, 3 = 3, 4 = 4, 5 = 5, 6 = 6, 7 = 7, 8 = 8, 9 = 9, 10 = 10, 11 = 11, 12 = 12, 13 = 13, 14 = 14, 15 = 15, 16 = 16, 17 = 17, 18 = 18, 19 = 19, 20 = 20, 21 = 21, 22 = 22, 23 = 23, 24 = 24, 25 = 25, 26 = 26, 27 = 27, 28 = 28, 29 = 29, 30 = 30, 31 = 31, 32 = 32, 33 = 33, 34 = 34, 35 = 35, 36 = 36, 37 = 37, 38 = 38, 39 = 39, 40 = 40, 41 = 41, 42 = 42, 43 = 43, 44 = 44, 45 = 45, 46 = 46, 47 = 47, 48 = 48, 49 = 49, 50 = 50, 51 = 51, 52 = 52, 53 = 53, 54 = 54, 55 = 55, 56 = 56, 57 = 57, 58 = 58, 59 = 59, 60 = 60, 61 = 61, 62 = 62, 63 = 63, 64 = 64, 65 = 65, 66 = 66, 67 = 67, 68 = 68, 69 = 69, 70 = 70, 71 = 71, 72 = 72, 73 = 73, 74 = 74, 75 = 75, 76 = 76, 77 = 77, 78 = 78, 79 = 79, 80 = 80, 81 = 81, 82 = 82, 83 = 83, 84 = 84, 85 = 85, 86 = 86, 87 = 87, 88 = 88, 89 = 89, 90 = 90, 91 = 91, 92 = 92, 93 = 93, 94 = 94, 95 = 95, 96 = 96, 97 = 97, 98 = 98, 99 = 99, 100 = 100, 101 = 101, 102 = 102, 103 = 103, 104 = 104, "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5eS1wMbeTKPz"
      },
      "source": [
        "## 百五減算が機能する仕組み\n",
        "百五減算のポイントは，$x$の評価式\n",
        "$$\n",
        "x = (70a + 21b + 15c)\n",
        "$$\n",
        "における$a$, $b$および$c$の係数を，それぞれ，\n",
        "- $a$ の係数は，5でも7でも割り切れるが，3で割ると1余る数(この場合, 70)\n",
        "- $b$ の係数は，3でも7でも割り切れるが，5で割ると1余る数(この場合, 21)\n",
        "- $c$ の係数は，3でも5でも割り切れるが，7で割ると1余る数(この場合, 15)\n",
        "\n",
        "となるように与えることである．このとき，式\n",
        "$x = (70a + 21b + 15c)$は，\n",
        "$$\\begin{align}\n",
        "x &= (70a + 21b + 15c) \\\\\n",
        "&= a + 3(23a + 7b+5c) && \\text{($x$を3で割った余りは$a$)}\\\\\n",
        "&= b + 5(14a + 4b + 3c) && \\text{($x$を5で割った余りは$b$)}\\\\\n",
        "&= c + 7(10a + 3b + 2c) && \\text{($x$を7で割った余りは$c$)}\n",
        "\\end{align}$$\n",
        "となり，ツジツマが合うわけだ．"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JhcEqoxASfl5"
      },
      "source": [
        "## 百五減算と暗号\n",
        "百五減算は **暗号の一種** と捉えることもできる．もとの数$x$ から $a, b, c$を求める部分が**暗号化**に相当し，与えられた$a, b, c$からもとの数$x$ を求めるのが**複合化** に相当する．例えば，戦争中に自国の作戦コード$x$を前線にいる味方に伝える場合，メッセージとして$a, b, c$だけを送ることにすれば，たとえそのメッセージが漏れても，($x$の計算方法が伝わらない限りは)もとの$x$が相手にバレることはない．\n",
        "\n",
        "上述の暗号・復号が正しく機能するためには，\n",
        "- 暗号化($x \\rightarrow a, b, c$ の計算)は，容易\n",
        "- 複合化($a, b, c \\rightarrow x$ の計算)は，極めて困難\n",
        "\n",
        "という非対称性が必要．\n",
        "\n",
        "ただし，百五減算の場合には，どんなに除数を大きくしても，計算機を使えば複合化が容易にできてしまうため，実用的な暗号にはなり得ない．\n",
        "\n",
        "**じゃあ，実用的な暗号ってどうなってるの?** "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r5y_jxDjZgiZ"
      },
      "source": [
        "# RSA暗号ことはじめ\n",
        "1977に米国MITの Rivest, Shamir および Adleman という3人の学者が **数理暗号** という暗号化の手法(**RSA暗号**)を発表した．この手法は「**公開鍵**」と「**秘密鍵**」という2つの情報を用いることで，**暗号化**(元の数値$x$から暗号化された値$y$を求める)の方法と**複合化**(暗号化された数値$y$から元の数値$x$を求める)の方法を**非対称にした点**が画期的である．\n",
        "\n",
        "### RSA暗号を使うための準備\n",
        "RSA暗号を使うためには，暗号の**受信者**が，以下の手順に従って**公開鍵**と**秘密鍵**を準備する必要がある．\n",
        "\n",
        "まず，2つの大きな素数$p, q$を用意する．ここでは，簡単のために小さい素数$(p,q)=(3,11)$を使おう．この2つの素数に対して，\n",
        "- $N = pq$\n",
        "- $M = (p-1)(q-1)$\n",
        "\n",
        "を計算する．上述の例では，$N=33, M = 20$である．\n",
        "\n",
        "次に，\n",
        "- $M$と**互いに素**な(i.e. $M$と$r$の最大公約数が1となる)整数 $r>1$\n",
        "\n",
        "を求める．上述の例では $M=20$なので，$r=3$ である．この$r$ を用いて，\n",
        "- $rs \\mod M = 1$ となる(i.e. $rs$ を$M$で割った余りが1になる)ような整数 $s$ \n",
        "\n",
        "を求める．上述の例では，$s=7$ である．以上の準備のもと，暗号の**受信者**は，$(N, r)$ を **公開鍵**, $s$を **秘密鍵**とする．\n",
        "\n",
        "公開鍵$(N, r)$は，メールで送っても構わないし，ホームページで公開しても構わない．例えば，長江の公開鍵は[こんな感じ](https://github.com/nagae.keys)で公開されている．一方，秘密鍵$s$は，決して公開してはならない．\n",
        "\n",
        "### 暗号化と複合化\n",
        "暗号の**送信者** が数値$x$を暗号化して送りたい場合，公開鍵$(N, r)$を用いた以下の式で暗号化された数値を計算する．\n",
        "$$\n",
        "y = x^{r} \\mod N\n",
        "$$\n",
        "こうして暗号化された数値$y$は，$(N, r)$の情報を用いるだけでは，どうやっても解読できない(と信じられている)ため，メールとかに貼り付けるなどして受信者に送ればいい．\n",
        "\n",
        "**受信者**は，受け取った暗号$y$に対して，秘密鍵$s$(と$N$を用いた)以下の計算を行うことで，元の数値$x$を容易に求められる．\n",
        "$$\n",
        "x = y^{s} \\mod N\n",
        "$$\n",
        "\n",
        "Python では「べき乗」と「剰余」を求める演算子として，それぞれ，`**`および`%`が用意されているから，これを使って\n",
        "```python\n",
        "y = x ** r % N # もとの数→暗号コード\n",
        "x = y ** s % N # 暗号コード→もとの数\n",
        "```\n",
        "とすることもできるが，[`pow`関数](https://docs.python.org/ja/3/library/functions.html#pow)を用いて，\n",
        "```python\n",
        "y = pow( x, r, N ) # もとの数→暗号コード\n",
        "x = pow( y, s, N ) # 暗号コード→もとの数\n",
        "```\n",
        "とする方がエレガントである．\n",
        "\n",
        "以下のセルの`x=19`の部分を書き換えて，実際に暗号化と複合化を行なってみよう．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SAsfoiIQPhdI",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "42aa2d65-7880-40f1-85ff-e94abc33ea65"
      },
      "source": [
        "(p, q) = (3, 11)\n",
        "(r, s) = (3, 7)\n",
        "N = p * q\n",
        "print(\"N=\", N)\n",
        "\n",
        "### 暗号化(xから暗号化された数値yを計算)\n",
        "x = 19 # もとの数値\n",
        "y = pow( x, r, N ) # (x ** r) % N を求める\n",
        "### 複合化(yから元の数値xを求める)\n",
        "X = pow( y, s, N ) # (y ** s) % N を求める\n",
        "\n",
        "print(x, \"→\", y, \"→\", X) # もとの値，暗号化された値，複合化された値を表示"
      ],
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "N= 33\n",
            "19 → 28 → 19\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vFdKhD69x-o2"
      },
      "source": [
        "# 文字の暗号化\n",
        "## Unicode による文字の数値化\n",
        "RSA暗号は整数から整数への変換なので，文字を数値に直せば，やはり暗号化できる．\n",
        "\n",
        "ここでは，日本語を含む汎用的な文字コードである [Unicode](https://ja.wikipedia.org/wiki/Unicode)の符号化方式として一般的に使われている [UTF-8](https://ja.wikipedia.org/wiki/UTF-8) を用いる方法を示そう． \n",
        "\n",
        "UTF-8方式では，1つ1つの文字に対して，以下のように個別の数値(コードポイント)が割り当てられており，この数値をRSA方式で暗号化することで，秘密のメッセージを送ることができる．\n",
        "\n",
        "|文字| 数値 | \n",
        "|---|----|\n",
        "|東|26481|\n",
        "|北|21271|\n",
        "|大|22823|\n",
        "|学|23398|\n",
        "|👍|128077|\n",
        "\n",
        "ある文字に対応する数値(コードポイント)を求めるには[`ord`関数](https://docs.python.org/ja/3/library/functions.html#ord)を，数値に対応する文字を求めるには[`chr`関数](https://docs.python.org/ja/3/library/functions.html#chr)を使う．\n",
        "例えば， 「東」に対応する数値を変数`x`， `128077`に対応する文字を変数 `c`に格納し，それらを表示させるには，以下のようなコードを使う．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8swG7TKqPdZM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "63a20d15-15a6-4350-fd97-a9dc2c99e180"
      },
      "source": [
        "x = ord(\"東\") # 「東」に対応する数値を x に格納\n",
        "c = chr(128077) # 128077 (thumbs up) に対応する文字を c に格納\n",
        "print(x, c) # 数値x と文字 c を表示"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "26481 👍\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r8jX8dbtQrzb"
      },
      "source": [
        "## UTF-8 コードポイントをRSA暗号化するためには\n",
        "UTFのコードポイントは21ビットのため，その値は 0 から 2097151(=$2^{21}-1$)の範囲を取り得る． RSA暗号の性質から，全ての文字を暗号化するには$N=pq$ が 2097151より大きくなるような $p$ と$q$ を選ぶ必要がある(ただし，現時点では文字が割り当てられていない数値も多いため， $(20000)_{16}=131072$ ぐらい扱えれば十分なようだ[[参考資料]](http://www.asahi-net.or.jp/~ax2s-kmtn/ref/unicode/index_u.html))．\n",
        "\n",
        "例えば，[Prime number list](https://www.mathsisfun.com/numbers/prime-numbers-to-10k.html)から適当な素数 $(p, q) = (1051, 1999)$ を選んだとしよう．このとき，"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yqwKBsOpQ7q0",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1343625e-60fc-4635-8262-26a8d4577825"
      },
      "source": [
        "(p, q) = (1051, 1999)\n",
        "N = p * q\n",
        "M = (p-1) * (q-1)\n",
        "print(\"N=\", N)\n",
        "print(\"M=\", M)"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "N= 2100949\n",
            "M= 2097900\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JO4fiaAiTk3g"
      },
      "source": [
        "であるから，全ての文字(に対応するコードポイント)をRSA暗号化できる．\n",
        "\n",
        "次に， 公開鍵と秘密鍵になる $r$ と $s$ を求めよう．まず，$r$は，$M = 2097900$と**互いに素となる**($M$との最大公約数が1となる)ように選べばよい． 2つの整数の最大公約数は[`math`モジュール](https://docs.python.org/ja/3/library/math.html)内の[`math.gcd`関数](https://docs.python.org/ja/3/library/math.html#math.gcd)を使えば簡単に求められるから， 以下のセルの `r=3` の部分を色々書き換えて実行すれば， `M`との最大公約数が1となるような `r` が見付けられる．\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y5UeS90JVPSk",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f8797078-34fd-4ba0-e09f-84e5bf0b3c11"
      },
      "source": [
        "import math # math モジュールをインポートすることで， gcd関数が使えるようになる\n",
        "r = 3\n",
        "math.gcd(M, r)"
      ],
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 20
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "68DHxovrVe-4"
      },
      "source": [
        "ここでは，そのような$r$として`r=11` を採用しよう．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GgUZ6Kl8Ti7A",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ae244cd2-901d-42d6-c30f-000c1e7730b1"
      },
      "source": [
        "r = 11\n",
        "math.gcd(M, r)"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zelZ1xy1VuX0"
      },
      "source": [
        "次に，秘密鍵$s$は，$rs$を$M$で割った余りが1になるような値である． これを手作業で求めるのはちょっと大変である．そこで，以下のチートコードを使ってしまおう："
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qx67dCnpWHx7",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1d5b3b80-3d0e-4924-a8e2-e3d38f3b9566"
      },
      "source": [
        "# (for を使った繰返しは次回以降解説します)\n",
        "# for 文を使った繰返しによって， (r*s) を M で割った余りが 1 となる s を探す\n",
        "for s in range(2,M): # 2以上M未満の候補を次々と s に代入して繰返す\n",
        "    if (r*s) % M ==1: # (r*s) % M が 1 となるなら, s を表示して繰返しを終了する\n",
        "        print(\"s=\", s)\n",
        "        break"
      ],
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "s= 953591\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SNMs8HFabpAK"
      },
      "source": [
        "以上の手続きにより，\n",
        "\n",
        "- **公開鍵** `(N, r) = (2100949, 11)` \n",
        "- **秘密鍵** `s = 953591`\n",
        "\n",
        "が求められた．\n",
        "\n",
        "\n",
        "この公開鍵`(N, r)`を使えば，「東北大学👍」という文章は，以下のように暗号化できる：\n",
        "\n",
        "|文字| 数値 |  暗号コード |\n",
        "|---|----| ---- |\n",
        "|東|26481|1203178|\n",
        "|北|21271|1163952|\n",
        "|大|22823|2059934|\n",
        "|学|23398|355494|\n",
        "|👍|128077|1350391|\n",
        "\n",
        "以下のようなコードにすれば，暗号化の手続きが(多少)スッキリ書けるだろう．\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RfEbQwIcPPXX",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1a743e80-590a-4cd8-b211-dcf850073894"
      },
      "source": [
        "# pow と ord を組み合わせると暗号化の手続きがスッキリ書ける．\n",
        "# ここでは，ord(文字)で求められた数値を pow関数の第1引数として渡している．\n",
        "print( pow( ord(\"東\"), r, N ) )\n",
        "print( pow( ord(\"北\"), r, N ) )\n",
        "print( pow( ord(\"大\"), r, N ) )\n",
        "print( pow( ord(\"学\"), r, N ) )\n",
        "print( pow( ord(\"👍\"), r, N ) )"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1203178\n",
            "1163952\n",
            "2059934\n",
            "355494\n",
            "1350391\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wsw6L09pXmRp",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "94383520-5fcf-40db-efe4-b0a9d700a018"
      },
      "source": [
        "pow( 1203178, s, N )"
      ],
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "26481"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 24
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DjPNr9DpXrgO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "331939cd-dc16-44c6-9fa8-a6d22e420045"
      },
      "source": [
        "chr( 26481 )"
      ],
      "execution_count": 25,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'東'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 25
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LaWQlEEndRo0"
      },
      "source": [
        "同様にすれば，複合化の手続きも簡単に書ける．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VoUbIrFndQqv",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fdd8a457-c290-44f5-d112-54a0e7864960"
      },
      "source": [
        "# chr と pow を組み合わせるた複合化の手続き． chr と pow の順番に注意．\n",
        "# ここでは，pow( 暗号化された数値, s, N ) で求めた「複合化された数値」を chr関数に渡している．\n",
        "print( chr( pow( 1203178, s, N ) ) )\n",
        "print( chr( pow( 1163952, s, N ) ) )\n",
        "print( chr( pow( 2059934, s, N ) ) )\n",
        "print( chr( pow( 355494, s, N ) ) )\n",
        "print( chr( pow( 1350391, s, N ) ) )"
      ],
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "東\n",
            "北\n",
            "大\n",
            "学\n",
            "👍\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "19ac1F_8uWXu"
      },
      "source": [
        "次回以降で解説する `for` 文を使えば， もっと簡単に暗号化・符号化できる.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pdNgj58YujIN",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3b2cbd2f-5b0b-4f41-fcf1-31db8921a9f6"
      },
      "source": [
        "# for 文を使った暗号化\n",
        "text = \"情報基礎B😩\" # 暗号化したい文章\n",
        "for c in text: # text 内の文字を順に変数 c に格納し, cのコードポイントを暗号コードに変換して表示するブロックを実行\n",
        "    print( pow( ord(c), r, N ) )\n",
        "\n",
        "# for 文を使った複合化\n",
        "codes = [1997045, 1735770, 21926, 1254593, 1565615, 293423] # 暗号化されたコード(カンマで区切る)\n",
        "for y in codes: # codes 内の暗号コードを順に変数 y に格納し，yを複合化したコードポイントに対応する文字を表示するブロックを実行\n",
        "    print( chr( pow(y, s, N) ) )"
      ],
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1997045\n",
            "1735770\n",
            "21926\n",
            "1254593\n",
            "1565615\n",
            "293423\n",
            "情\n",
            "報\n",
            "基\n",
            "礎\n",
            "B\n",
            "😩\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GgFZYwryFDjs"
      },
      "source": [
        "## 【余談】 RSA暗号の鍵長\n",
        "RSA暗号の$N$の鍵長としては2048ビット程度が望ましいとされている．今回の例で使った $N$ は高々20ビット程度なので，簡単に因数分解できてしまう．ちなみに，次のセルを実行すれば$2^{2048}$ がどれくらい大きいかが判るだろう．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EL3QssHIFDjs",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8bed5dca-58b3-4cb7-f201-33f44c366082"
      },
      "source": [
        "print(\"鍵の長さ:\", 2**2048)\n",
        "print(\"「鍵の長さ」の桁数:\", math.ceil(math.log10(2**2048)))"
      ],
      "execution_count": 30,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "鍵の長さ: 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656\n",
            "「鍵の長さ」の桁数: 617\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wjIg75bozH-s"
      },
      "source": [
        "# 課題5 三百八十五減算とRSA暗号"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_9K2VwJGWuRK"
      },
      "source": [
        "## 【課題5-1】三百八十五減算\n",
        "百五減算より大きな数を扱うために，0以上385未満の任意の数$x$に対して，\n",
        "- $x$を5で割った余り$a$\n",
        "- $x$を7で割った余り$b$\n",
        "- $x$を11で割った余り$c$\n",
        "\n",
        "から$x$を求める式を求めよ．求めた式を用いて，以下のそれぞれのケースに対して，正しくもとの数$x$が復号できるか確認せよ．\n",
        "\n",
        "|a | b | c | x |\n",
        "|---|----|---|---|\n",
        "|2 | 6 | 5 | 27 |\n",
        "|3 | 2 | 10 | 373 |\n",
        "|4 | 2 | 1 | 254 |"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iqVAzR2T0erP"
      },
      "source": [
        "## 【課題5-2】 RSA暗号\n",
        "$N$が少なくとも$132000$程度となるように，上述の例とは異なる素数 $p, q$を用いて，自分で公開鍵$(N, r)$と秘密鍵$s$を作成せよ． \n",
        "素数については，以下のサイトに掲載されているものを使ってよい：\n",
        "https://www.mathsisfun.com/numbers/prime-numbers-to-10k.html\n",
        "\n",
        "求めた公開鍵と秘密鍵を用いて，以下の漢詩の暗号化(漢字→暗号コード)と複合化(暗号コード→漢字)を行え：\n",
        "\n",
        "> 国破山河在  \n",
        "> 城春草木深  \n",
        "> 感時花濺涙  \n",
        "> 恨別鳥驚心\n",
        "\n",
        "上述の例(`(N, r) = (2100949, 11), s = 953591`)の場合， 暗号コードは以下の通り：\n",
        "```text\n",
        "1649451, 1712564, 520074, 374329, 1033149\n",
        "1978913, 790664, 1401088, 1127747, 631168\n",
        "140273, 1827109, 814736, 266160, 1996365\n",
        "1143597, 1163429, 902879, 1062966, 1560799\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "szE54RpU3jVH"
      },
      "source": [
        "## 【おまけ】 暗号通信してみよう\n",
        "Microsoft Teams の[「暗号通信」チャンネル](https://teams.microsoft.com/l/channel/19%3ad47d166eba2f4af68cd824e10920c896%40thread.tacv2/%25E6%259A%2597%25E5%258F%25B7%25E9%2580%259A%25E4%25BF%25A1?groupId=59469621-b62a-403f-8e6f-f41273ea6e2b&tenantId=f848e92a-65fa-4729-b2e6-eac667dd1bc3)を使って暗号通信してみよう．\n",
        "\n",
        "まず，暗号を受信したい人は，チャットルームで以下のように発言する(暗号鍵は適宜変えて下さい)：\n",
        "\n",
        "> 私の公開鍵は (2100949, 11) です． 誰か暗号を送って下さい．\n",
        "\n",
        "メッセージを送信したい人は，その公開鍵を元に，送りたい文章の暗号コードを，以下のようにして送る：\n",
        "\n",
        " > ◯◯さん，暗号を送ります: 1576653, 174297, 538933, \n",
        "715971, 1655843, 1509974, 1689836, 524070\n",
        "\n",
        "暗号コードをもらったら，秘密鍵を使って複合化し，**リアクション**しよう．\n",
        "\n",
        "> □□さん，ありがとう．頑張ろうね!\n",
        "\n",
        "もちろん暗号化されているからといって，公序良俗に反するメッセージやクレジット・カード番号などの金融情報は送ってはいけない．また，[【余談】](#scrollTo=GgFZYwryFDjs&line=1&uniqifier=1)にも書いたように，そもそも7〜8桁程度の鍵長では，大して苦もなく因数分解できてしまうことにも注意されたい．"
      ]
    }
  ]
}