CSC15005/RSA/RSA.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8efab8e5",
   "metadata": {},
   "source": [
    "# Tóm tắt kiến thức RSA\n",
    "\n",
    "Các bước thực hiện:\n",
    "1. Tính $n = p \\times q$, với $p, q$ **nguyên tố** và **lớn**.\n",
    "\n",
    "  Bước này áp dụng Định lý nhỏ Fermat để kiểm tra nhanh nguyên tố.\n",
    "\n",
    "  Định lý nhỏ Fermat: $p \\in P \\Rightarrow \\forall b: b^{p-1} \\equiv 1 \\pmod \\phi$ (với $P$ là tập số nguyên tố)\n",
    "  \n",
    "  Để tạo một số nguyên tố **lớn**, tham khảo thuật toán tạo số nguyên tố lớn bên dưới.\n",
    "\n",
    "2. Tính $\\phi = (p - 1) \\times (q - 1)$\n",
    "3. Tính khóa giải $d$ và khóa mã $e$ sao cho $de \\equiv 1 \\pmod \\phi$\n",
    "\n",
    "  Từ công thức bên trên, $d \\equiv e^{-1} \\pmod \\phi$.\n",
    "  \n",
    "  **Quan trọng**:\n",
    "  - NÊN tạo khóa $d$ trước rồi tạo khóa $e$ theo $d$.\n",
    "  - $\\text{gcd}(d, \\phi) = 1$ để tránh trường hợp message bị nhập nhằng sau khi mã hóa / giải mã. [Tham khảo](https://crypto.stackexchange.com/a/12256)\n",
    "  \n",
    "  Khi đó ta dùng [Extended Euclidean Algorithm](#Extended-Euclidean-Algorithm) để tìm nghịch đảo của $d$ trong modulo $\\phi$.\n",
    "\n",
    "4. Khóa giải $d$ giữ bí mật (private key), khóa $e$ công khai (public key):\n",
    "  - $c \\equiv m^e \\pmod n$\n",
    "  - $m^{*} \\equiv c^d \\pmod n$\n",
    "  \n",
    "  Quá trình này có sử dụng Định lý thặng dư Trung Hoa (cho nhanh).\n",
    "  \n",
    "Với các quá trình tính toán bên trên cần [thuật toán tính nhân + mũ modulo nhanh và hiệu quả](#Fast-multiply-and-exponential-modular).\n",
    "\n",
    "Một số thuật toán bổ trợ:\n",
    "- [Extended Euclidean Algorithm](#Extended-Euclidean-Algorithm) - tìm nhanh modulo nghịch đảo.\n",
    "- [Fast multiply and Expotential Modular](#Fast-multiply-and-exponential-modular) - tính nhanh số mũ & nhân trong modulo.\n",
    "- [Chinese Remainder Theorem](#Chinese-remainder-theorem) - định lý thặng dư Trung Hoa.\n",
    "- [Large Prime Generator](#Large-prime-generator) - Tạo số nguyên tố lớn"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc0ef525",
   "metadata": {},
   "source": [
    "# Extended Euclidean Algorithm\n",
    "\n",
    "Thuật toán Euclide mở rộng - XEuclidean\n",
    "\n",
    "Bổ đề Bézout: $\\exists x, y \\in \\mathbb{Z}: ax + by = \\text{gcd}(a, b)$. Trong trường hợp $a, b$ nguyên tố thì $ax + by = 1$.\n",
    "\n",
    "Ở đây ta quan tâm đến trường hợp $a, b$ nguyên tố. Khi đó, $ax \\equiv 1 \\pmod b \\Rightarrow x \\equiv a^{-1} \\pmod b$. Thuật toán XEuclidean sẽ trả về $\\text{gcd}(a, b), x, y$ tương ứng với biểu diễn Bézout $ax + by = \\text{gcd}(a, b)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "375854b3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.9 + 31.-2 = 1\n",
      "9\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "# Extended Euclidean Algorithm\n",
    "def extended_gcd(a, b):\n",
    "  if a == 0:\n",
    "    return b, 0, 1\n",
    "\n",
    "  g, y, x = extended_gcd(b % a, a)\n",
    "  return g, x - (b // a) * y, y\n",
    "\n",
    "# Example: Tìm và in biểu diễn Bézout với a = 7, b = 31;\n",
    "a, b = 7, 31\n",
    "g, x, y = extended_gcd(a, b)\n",
    "print('{0}.{1} + {2}.{3} = {4}'.format(a, x, b, y, g))\n",
    "\n",
    "# Finding inverse modulo with extended_gcd:\n",
    "def inverse_modulo(a, m):\n",
    "  g, x, y = extended_gcd(a, m)\n",
    "\n",
    "  if g != 1:\n",
    "    raise Exception('Inverse modular does not exists!')\n",
    "\n",
    "  return x % m\n",
    "\n",
    "# Example: Tìm nghịch đảo của 7 trong Z_{31}, 8 trong Z_{31}\n",
    "print(inverse_modulo(7, 31))\n",
    "print(inverse_modulo(8, 31))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "308a60a1",
   "metadata": {},
   "source": [
    "# Fast multiply and exponential modular\n",
    "\n",
    "Nhân naive có vẻ hơi \"chậm\". Vậy giờ ta xài bit manipulation!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f4364cc0",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "def add_mod(a, b, m):\n",
    "  return (a + b) % m\n",
    "\n",
    "# Các thuật toán tính nhanh modulo.\n",
    "\n",
    "# (x * y) % m\n",
    "def mul_mod(x, y, n):\n",
    "  p = 0\n",
    "\n",
    "  x %= n\n",
    "    \n",
    "  while y > 0:\n",
    "    if y & 1:\n",
    "      p = add_mod(p, x, n)\n",
    "    \n",
    "    x = (x << 1) % n\n",
    "\n",
    "    y = y >> 1\n",
    "\n",
    "  return p\n",
    "\n",
    "# x^p % m\n",
    "def pow_mod(x, p, n):\n",
    "  y = 1\n",
    "\n",
    "  x %= n\n",
    "    \n",
    "  if p == 0:\n",
    "    return y\n",
    "\n",
    "  while p > 0:\n",
    "    if p & 1: \n",
    "      y = mul_mod(y, x, n)\n",
    "    \n",
    "    p = p >> 1\n",
    "    \n",
    "    x = mul_mod(x, x, n)\n",
    "    \n",
    "  return y\n",
    "\n",
    "# Example:\n",
    "# 3 * 50 = 14 (mod 17)\n",
    "print(mul_mod(3, 50, 17))\n",
    "\n",
    "# 3 ^ 50 = 9 (mod 17)\n",
    "print(pow_mod(3, 50, 17))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf8f7cae",
   "metadata": {},
   "source": [
    "# Chinese Remainder Theorem\n",
    "\n",
    "Định lý thặng dư Trung Hoa (Tầu-khựa) - CRT\n",
    "\n",
    "Cho hệ phương trình đồng dư\n",
    "$$\\begin{cases}\n",
    "x \\equiv b_1 \\pmod{m_1} \\\\ \n",
    "x \\equiv b_2 \\pmod{m_2} \\\\\n",
    ".. \\\\\n",
    "x \\equiv b_n \\pmod{m_n}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "yêu cầu đặt ra là tìm $x$?\n",
    "\n",
    "## Phương pháp giải\n",
    "1. Tính $N = m_1 \\times m_2 \\times .. \\times m_n$\n",
    "2. Tính $\\displaystyle N_1 = \\frac{N}{m_1}, N_2 = \\frac{N}{m_2}, .., N_n = \\frac{N}{m_n}$\n",
    "3. Tính $x_1 \\equiv N_1^{-1} \\pmod{m_1}, x_2 \\equiv N_2^{-1} \\pmod{m_2}, .., x_n \\equiv N_n^{-1} \\pmod{m_n}$\n",
    "\n",
    "  Tìm modulo nghịch đảo của $N_i$ trong modulo $m_i$, $i \\in [1, n]$). Gợi ý: xài thuật Extended Euclidean bên trên.\n",
    "  \n",
    "4. Đáp án của bài toán: $\\displaystyle x \\equiv \\sum_{i = 1}^{n} (x_i \\times N_i \\times b_i) \\pmod N$\n",
    "\n",
    "  Hay, $\\displaystyle x = Nk + \\sum_{i = 1}^{n} (x_i \\times N_i \\times b_i), k \\in \\mathbb{N}$\n",
    "  \n",
    "## Áp dụng trong RSA\n",
    "Ta có thể sử dụng CRT để giải mã nhanh RSA cipher. Xét $c^d \\pmod{n} \\equiv c^d \\pmod{pq}$. \n",
    "\n",
    "Đặt $d_1 \\equiv d \\pmod{p - 1}, d_2 \\equiv d \\pmod{q - 1}$. $\\exists n_1, n_2: d = n_1(p - 1) + d_1 = n_2(q - 1) + d_2$.\n",
    "\n",
    "Áp vào công thức ban đầu, ta có $c^d \\pmod{pq} \\equiv c^{d_1}c^{(p - 1)} \\pmod{p}$. Mà theo định lý nhỏ Fermat, $c^{p - 1} \\equiv 1 \\pmod{p}$. Vậy $c^{d} \\equiv c^{d_1} \\pmod{p}$\n",
    "\n",
    "Tương tự, $c^{d} \\equiv c^{d_2} \\pmod{q}$. Vậy ta có hệ phương trình đồng dư\n",
    "\n",
    "$$\\begin{cases}\n",
    "c^{d} \\equiv c^{d_1} \\pmod{p} \\\\\n",
    "c^{d} \\equiv c^{d_2} \\pmod{q} \n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "Ưu điểm của phương pháp này là thực hiện ít phép mũ hơn so với việc phải tính $c^d$.\n",
    "\n",
    "Code (naive) và ví dụ bên dưới lần lượt giải các hệ\n",
    "\n",
    "$$\n",
    "1.\n",
    "\\begin{cases}\n",
    "x \\equiv 1 \\pmod{2} \\\\\n",
    "x \\equiv 2 \\pmod{3} \n",
    "\\end{cases}\n",
    "\\\\\n",
    "2.\n",
    "\\begin{cases}\n",
    "x \\equiv 2 \\pmod{3} \\\\\n",
    "x \\equiv 0 \\pmod{2} \\\\\n",
    "x \\equiv 0 \\pmod{5} \n",
    "\\end{cases}\n",
    "\\\\\n",
    "3.\n",
    "\\begin{cases}\n",
    "x \\equiv 2 \\pmod{3} \\\\\n",
    "x \\equiv 1 \\pmod{7} \n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "434a4575",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6k + 5\n",
      "30k + 20\n",
      "21k + 8\n"
     ]
    }
   ],
   "source": [
    "# Naive solution to the Chinese Remainder Theorem\n",
    "def chinese_remainder(b, m):\n",
    "  # Calculate N\n",
    "  N = 1\n",
    "  for i in m: N *= i\n",
    "    \n",
    "  # Calculate N_i\n",
    "  Ni = [N // i for i in m]\n",
    "\n",
    "  # Calculate x^{-1}_i\n",
    "  reverse_x = [inverse_modulo(n, m[i]) for i, n in enumerate(Ni)]\n",
    "\n",
    "  result = 0\n",
    "\n",
    "  for i, x in enumerate(reverse_x):\n",
    "    result = add_mod(mul_mod(Ni[i], mul_mod(b[i], x, N), N), result, N)\n",
    "    \n",
    "  return N, result\n",
    "        \n",
    "print('{0[0]}k + {0[1]}'.format(chinese_remainder([1, 2], [2, 3])))\n",
    "print('{0[0]}k + {0[1]}'.format(chinese_remainder([2, 0, 0], [3, 2, 5])))\n",
    "print('{0[0]}k + {0[1]}'.format(chinese_remainder([2, 1], [3, 7])))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3deb60b0",
   "metadata": {},
   "source": [
    "# Large prime generator\n",
    "\n",
    "## 1. Định lý: \n",
    "Cho $p$ là một số nguyên tố lẻ, $k \\in \\mathbb{N+}$ thỏa $1 < k < 2(p+1), k \\nmid p$. Đặt $n = 2kp + 1$, các phát biểu sau là tương đương:\n",
    "\n",
    "1. $n$ là số nguyên tố\n",
    "2. $\\exists a: 2 < a < N$ sao cho\n",
    "\n",
    "$$\n",
    "\\begin{cases}\n",
    "a^{kp} \\equiv -1 \\pmod{n} \\\\\n",
    "\\text{gcd}(a^k + 1, n) = 1\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "## 2. Thuật toán\n",
    "1. Chọn số **nguyên tố** $p_1$ có $d_1$ chữ số.\n",
    "2. Tìm $k_1 < 2(p_1 + 1)$ sao cho $p_2 = 2k_1p_1 + 1$ có $d_2$ chữ số và $\\exists a_1 < p_2$ thỏa\n",
    "$$\n",
    "\\begin{cases}\n",
    "a^{k_1p_1} \\equiv -1 \\pmod{p_2} \\\\\n",
    "\\text{gcd}(a_1^{k_1} + 1, p_2) = 1\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "Khi đó $p_2$ là một số nguyên tố. Tiếp tục thay $p_1 \\leftarrow p_2$ và thực hiện lại từ bước 2 đến khi đạt được số nguyên tố có số chữ số $d_1$ cần tạo. \n",
    "\n",
    "**Quan trọng**: Đây là phương pháp brute-force để tìm một số nguyên tố lớn. Vì vậy, nên generate trước 1 cặp nguyên tố lớn trước khi xài trong RSA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "aeffd517",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "19319\n",
      "34679\n"
     ]
    }
   ],
   "source": [
    "def large_prime_generator(expected_length, seed, collision = 1):\n",
    "  p1 = seed\n",
    "  d1 = len(str(p1))\n",
    "\n",
    "  while (d1 <= expected_length):\n",
    "    found = 0\n",
    "    for k1 in range(2, 2 * (p1 + 1) + 1):\n",
    "      p2 = 2 * k1 * p1 + 1\n",
    "      d2 = len(str(p2))\n",
    "\n",
    "      if d2 > expected_length: break\n",
    "      if p2 % 10 == 5: continue\n",
    "\n",
    "      # print('Testing {0} (k = {1})'.format(p2, k1))\n",
    "      for a1 in range(2, p2 + 1, collision):\n",
    "        power_mod = pow_mod(a1, k1 * p1, p2)\n",
    "        egcd = extended_gcd(a1**k1 + 1, p2)[0]\n",
    "\n",
    "        if power_mod == p2 - 1 and egcd == 1:\n",
    "          # print(p2, ' valid')\n",
    "          found = 1\n",
    "          break\n",
    "\n",
    "      if found == 1: break\n",
    "\n",
    "    if found == 1:\n",
    "      p1 = p2\n",
    "      d1 = len(str(p1))\n",
    "\n",
    "    if d2 >= expected_length: break\n",
    "\n",
    "  return p1\n",
    "\n",
    "# Generate a prime with 5 digits, but with different seed\n",
    "print(large_prime_generator(5, 13))\n",
    "print(large_prime_generator(5, 17))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}