RSA_revised.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "RSA_revised.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNt+1jKIs0F5FhhVuxGRRpp",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "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/RSA_revised.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kwUVsi4XUXAu"
      },
      "source": [
        "# Euclid 互除法を用いたRSA暗号の秘密鍵生成\n",
        "RSA暗号では，2つの素数 $p$ と $q$ を選んだとき，\n",
        "$M = (p-1)(q-1)$ に対して，以下の2つの整数 $r, s$ を求める必要がある：\n",
        "1. $M$ と素である(最大公約数が1となる)ような整数 $r$\n",
        "2. $rs \\mod M = 1$ となるような整数$s$\n",
        "\n",
        "このうち，$r$ は総あたりでも簡単に求められるが，$M$が非常に大きな場合には $s$ を総当たりで探すのは非効率的である． そこで，下記に示す**拡張 Euclid 互除法**を用いる．\n",
        "\n",
        "## 拡張 Euclid 互助法\n",
        "\n",
        "$rs \\mod M = 1$というのは「$rs$ は $M$ の倍数に1を加えたものに等しい」ということだから， $M$ の倍数を $u$ で表せば，\n",
        "$$\n",
        "rs = 1 + Mu\n",
        "$$\n",
        "を満足する，\n",
        "$$\n",
        "rs - Mu = 1\n",
        "$$\n",
        "を満足する $(s, u)$ を求めればよい． いま，明らかに $M > r$ だから，\n",
        "$M$ を $r$ で割った商と余りを $c$および$d$ とすれば， $M=rc+d$ より\n",
        "$$\\begin{align}\n",
        "rs - (rc + d)u &= 1 &\\Leftrightarrow && r(su-c) - du &=1\n",
        "\\end{align}$$\n",
        "である． $(su-c)$も$u$ も整数なのだから， $(M, r)$に関する問題が，より小さい$(r, d)$についての問題になっている．"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0umn6MOSKPAA"
      },
      "source": [
        "import math"
      ],
      "execution_count": 72,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OwJ0F6obKWK8"
      },
      "source": [
        "# 素数を2つ選ぶ\n",
        "p = 2147483647 \n",
        "q = 200560490131"
      ],
      "execution_count": 78,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "12iDTXmcKoci"
      },
      "source": [
        "#\n",
        "# N と M を計算する\n",
        "#\n",
        "N = p*q\n",
        "M = (p-1)*(q-1)\n",
        "#\n",
        "# r を求める\n",
        "#\n",
        "for r in range(2, M):\n",
        "    if math.gcd(M, r) == 1:\n",
        "        break\n",
        "#\n",
        "# s を求める\n",
        "# \n",
        "# 拡張 Euclid 互除法 (a > b であるとき, a*x + b*y = gcd(a, b) となる gcd, x, y を求める)\n",
        "def ext_gcd(a, b):\n",
        "    if b:\n",
        "        d, y, x = ext_gcd(b, a % b) # 再帰呼び出しを使う\n",
        "        y -= (a // b) *x\n",
        "        return d, x, y\n",
        "    return a, 1, 0\n",
        "# 拡張 Euclid 互除法を用いて s をもとめる\n",
        "s = ext_gcd(M, r)[-1] % M "
      ],
      "execution_count": 77,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "QJ13-4GVLQ0U",
        "outputId": "6237b05a-61af-4a68-9ef0-190bd4e76fda"
      },
      "source": [
        "print(\"p={}\\nq={}\\nN={}\\nM={}\\nr={}\\ns={}\".format(p, q, N, M, r, s))"
      ],
      "execution_count": 80,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "p=2147483647\n",
            "q=200560490131\n",
            "N=430700372790627387757\n",
            "M=430700372587919413980\n",
            "r=37\n",
            "s=221170461599201861233\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}