lab1/lab1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cded31fe",
   "metadata": {},
   "source": [
    "<h1 align=\"center\"> Лабораторная работа №1 </h1>\n",
    "\n",
    "---\n",
    "\n",
    "<h1 align=\"center\"> Университет ИТМО </h1>\n",
    "<h2 align=\"center\"> Факультет систем управления и робототехники </h2>\n",
    "\n",
    "---\n",
    "\n",
    "### Выполнили:\n",
    "- **Соколов Никита**  \n",
    "- **Минеев Кирилл**\n",
    "- **Соловьев Дмитрий**\n",
    "- **Семёнов Евгений**\n",
    "\n",
    "---\n",
    "\n",
    "### Проверил:\n",
    "- **Догадин Егор Витальевич**\n",
    "\n",
    "---\n",
    "\n",
    "### 23 сентября 2024 г.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e19f8b57447c7cda",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Задание 1. Шифр Хилла."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8617fb4eaee0d9d2",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Установка необходимых библиотек:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "d3e134b76b67985b",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:53.791095600Z",
     "start_time": "2024-09-23T17:34:52.441458700Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: numpy in /Users/nvoron/Documents/GitHub/practical-linear-algebra/venv/lib/python3.8/site-packages (1.24.4)\n",
      "\u001b[33mWARNING: You are using pip version 19.2.3, however version 24.2 is available.\n",
      "You should consider upgrading via the 'pip install --upgrade pip' command.\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "!pip install numpy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7c5ef487646171c8",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:53.798086100Z",
     "start_time": "2024-09-23T17:34:53.791095600Z"
    },
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "75f26207d2ebe879",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:53.805587700Z",
     "start_time": "2024-09-23T17:34:53.795587400Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "34\n"
     ]
    }
   ],
   "source": [
    "alphabet = \"АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ \"\n",
    "print(len(alphabet))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e64b28f431b250c",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Ценное сообщение из 12 символов:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6ef8934148d63832",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:53.807596600Z",
     "start_time": "2024-09-23T17:34:53.803588100Z"
    },
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "message = \"Я ЛЮБЛЮ ХЛЕБ\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf0e2533834c1e42",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### 3 матрицы-ключа:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ba12188efece7c44",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:55.924192900Z",
     "start_time": "2024-09-23T17:34:53.808959Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Матрица 2x2:\n",
      "[[ 6  3]\n",
      " [ 7 16]]\n",
      "Матрица 3x3:\n",
      "[[32 10  1]\n",
      " [ 8 13  0]\n",
      " [19 28 27]]\n",
      "Матрица 4x4:\n",
      "[[ 8  1 14 10]\n",
      " [28  7  5 20]\n",
      " [ 0 30 18 29]\n",
      " [21  9 32 13]]\n"
     ]
    }
   ],
   "source": [
    "def get_minor(matrix, i, j):\n",
    "    # Возвращает минор, исключая i-ю строку и j-й столбец\n",
    "    return np.delete(np.delete(matrix, i, axis=0), j, axis=1)\n",
    "\n",
    "\n",
    "def inverse_matrix(matrix):\n",
    "    # Находит обратную матрицу\n",
    "    matrix = np.array(matrix)\n",
    "    det = round(np.linalg.det(matrix))\n",
    "    if det == 0:\n",
    "        raise ValueError(\"Матрица вырожденная и не имеет обратной\")\n",
    "    for x in range(0, len(alphabet)):\n",
    "        if ((x * round(np.linalg.det(matrix))) % len(alphabet)) == 1:\n",
    "            break\n",
    "    if matrix.shape == (2, 2):\n",
    "        return np.array([[matrix[1, 1], \n",
    "                          -matrix[0, 1]],\n",
    "                          [-matrix[1, 0],\n",
    "                           matrix[0, 0]]]) * x\n",
    "    else:\n",
    "        alg_dop = np.zeros(matrix.shape)\n",
    "        for i in range(matrix.shape[0]):\n",
    "            for j in range(matrix.shape[1]):\n",
    "                minor = get_minor(matrix, i, j)\n",
    "                alg_dop[i, j] = ((-1) ** (i + j)) * round(np.linalg.det(minor))\n",
    "        return alg_dop.T * x\n",
    "\n",
    "def create_matrix(key_size):\n",
    "    while True:\n",
    "        matrix = np.random.randint(0, 33, size=(key_size, key_size))\n",
    "        if math.gcd(round(np.linalg.det(matrix)), len(alphabet)) == 1:\n",
    "            return matrix\n",
    "\n",
    "key_matrix2 = create_matrix(2)\n",
    "key_matrix3 = create_matrix(3)\n",
    "key_matrix4 = create_matrix(4)\n",
    "print(f\"Матрица 2x2:\\n{key_matrix2}\")\n",
    "print(f\"Матрица 3x3:\\n{key_matrix3}\")\n",
    "print(f\"Матрица 4x4:\\n{key_matrix4}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c28b1eaf2504d2bd",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Убедимся, что определители матриц не имеют общих делителей с длиной алфавита:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5a20ca4614676b39",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:55.927456Z",
     "start_time": "2024-09-23T17:34:55.923193700Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Определители для матриц: 2x2: 75, 3x3: 9049, 4x4: -176947\n",
      "Условие выполнено: True\n"
     ]
    }
   ],
   "source": [
    "det_matrix2 = round(np.linalg.det(key_matrix2))\n",
    "det_matrix3 = round(np.linalg.det(key_matrix3))\n",
    "det_matrix4 = round(np.linalg.det(key_matrix4))\n",
    "\n",
    "print(f\"Определители для матриц: 2x2: {det_matrix2}, 3x3: {det_matrix3}, 4x4: {det_matrix4}\")\n",
    "print(f\"Условие выполнено: {all(np.gcd(det_matrix_i, len(alphabet)) == 1 for det_matrix_i in (det_matrix2, det_matrix3, det_matrix4))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d314ac5c08380f2c",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Зашифруем сообщение с помощью каждого из ключей:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "1d55e309d6a5a3de",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:55.938429300Z",
     "start_time": "2024-09-23T17:34:55.927456Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Сообщения:\n",
      "1. ТДЬВЗЬМЮЯЁ Р\n",
      "2. ЁЕУЫЦЦСЮ ЪШФ\n",
      "3. ТЕЮХВИЕУЭЮГЬ\n"
     ]
    }
   ],
   "source": [
    "def encrypt(key_matrix, msg):\n",
    "    message_indices = [alphabet.index(char) for char in msg]\n",
    "    key_size = len(key_matrix)\n",
    "    \n",
    "    while len(message_indices) % key_size != 0:\n",
    "        message_indices.append(alphabet.index(\" \"))\n",
    "\n",
    "    encrypted_indices = []\n",
    "    for i in range(0, len(message_indices), key_size):\n",
    "        block = np.array(message_indices[i : i + key_size])\n",
    "        encrypted_block = np.dot(key_matrix, block) % len(alphabet)\n",
    "        encrypted_indices.extend(encrypted_block)\n",
    "        \n",
    "    return \"\".join([alphabet[i] for i in encrypted_indices])\n",
    "\n",
    "enc2 = encrypt(key_matrix2, message)\n",
    "enc3 = encrypt(key_matrix3, message)\n",
    "enc4 = encrypt(key_matrix4, message)\n",
    "print(f\"Сообщения:\\n1. {enc2}\\n2. {enc3}\\n3. {enc4}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6807d6454e899348",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Теперь расшифруем сообщения: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d9e4af9df7c6eb02",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:55.942618800Z",
     "start_time": "2024-09-23T17:34:55.939380100Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Сообщения:\n",
      "1. Я ЛЮБЛЮ ХЛЕБ\n",
      "2. Я ЛЮБЛЮ ХЛЕБ\n",
      "3. Я ЛЮБЛЮ ХЛЕБ\n"
     ]
    }
   ],
   "source": [
    "def decrypt(key_matrix, enc):\n",
    "    inv_key_matrix = np.round(inverse_matrix(key_matrix)).astype(int)\n",
    "    return encrypt(inv_key_matrix, enc)\n",
    "    \n",
    "dec2 = decrypt(key_matrix2, enc2)\n",
    "dec3 = decrypt(key_matrix3, enc3)\n",
    "dec4 = decrypt(key_matrix4, enc4)\n",
    "\n",
    "print(f\"Сообщения:\\n1. {dec2}\\n2. {dec3}\\n3. {dec4}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b6fbf965032c2e1",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Сымитируем вредоносное вмешательство в зашифрованные сообщения:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "fa4f153d9229cb6a",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.011944200Z",
     "start_time": "2024-09-23T17:34:55.943618900Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Сообщения:\n",
      "1. ТЖЬУЗЬМЮЯЁЛР\n",
      "2. ЁЦУЫЦЦСЭЦЪШФ\n",
      "3. ТАЗХВИЕУЭЧГЬ\n"
     ]
    }
   ],
   "source": [
    "def hack(enc):\n",
    "    indexes = []\n",
    "    chars = []\n",
    "    listed_mes = list(enc)\n",
    "\n",
    "    while len(indexes) != 3:\n",
    "        index = np.random.randint(0, len(enc))\n",
    "        char = alphabet[np.random.randint(0, len(alphabet))]\n",
    "        if (index not in indexes) and (char != enc[index]):\n",
    "            indexes.append(index)\n",
    "            chars.append(char)\n",
    "\n",
    "    for i in range(0, 3):\n",
    "        listed_mes[indexes[i]] = chars[i]\n",
    "\n",
    "    return \"\".join(listed_mes)\n",
    "\n",
    "\n",
    "hacked_enc2, hacked_enc3, hacked_enc4 = (hack(enc_i) for enc_i in (enc2, enc3, enc4))\n",
    "print(f\"Сообщения:\\n1. {hacked_enc2}\\n2. {hacked_enc3}\\n3. {hacked_enc4}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43ee92d8c6986440",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Расшифруем получившиеся сообщения: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "87161b9e89c53224",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.011944200Z",
     "start_time": "2024-09-23T17:34:55.954056400Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Сообщения:\n",
      "1. ФФНЪБЛЮ ХЛШХ\n",
      "2. ДОАЮБЛРСЗЛЕБ\n",
      "3. Ж КЯБЛЮ ЛЁСЕ\n"
     ]
    }
   ],
   "source": [
    "hacked_dec2, hacked_dec3, hacked_dec4 = (decrypt(key_matrix_i, enc_i) for key_matrix_i, enc_i in zip((key_matrix2, key_matrix3, key_matrix4), (hacked_enc2, hacked_enc3, hacked_enc4)))\n",
    "\n",
    "print(f\"Сообщения:\\n1. {hacked_dec2}\\n2. {hacked_dec3}\\n3. {hacked_dec4}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93256e7afdff1efc",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Задание 2. Взлом шифра Хилла."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43f6f894e652212f",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Ключ размера 2x2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "65366dcd8a6e03eb",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.014381900Z",
     "start_time": "2024-09-23T17:34:55.955545500Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[21 27]\n",
      " [ 2 23]]\n"
     ]
    }
   ],
   "source": [
    "matrix_key_hidden = create_matrix(2)\n",
    "print(matrix_key_hidden)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a5f521b34d44b52",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### 2 сообщения из 12 символов:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "a5df5c1937f53e03",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.014896300Z",
     "start_time": "2024-09-23T17:34:55.957541300Z"
    },
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "message1 = \"Я ЛЮБЛЮ БОРЩ\"\n",
    "message2 = \"Я ЛЮБЛЮ ХЛЕБ\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c14ff98c61f15b9",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Шифруем 2 сообщения: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "7042e8c1d8f536fa",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.015893Z",
     "start_time": "2024-09-23T17:34:55.961100700Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Сообщения:\n",
      "1.  ЖБЦЕЁЛЕСЖЕУ\n",
      "2.  ЖБЦЕЁЛЕДНЭ \n"
     ]
    }
   ],
   "source": [
    "enc1 = encrypt(matrix_key_hidden, message1)\n",
    "enc2 = encrypt(matrix_key_hidden, message2)\n",
    "print(f\"Сообщения:\\n1. {enc1}\\n2. {enc2}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7cbec0aebfef94b",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Забыли одно исходное сообщение:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "8c078eaa76a0f068",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.026197200Z",
     "start_time": "2024-09-23T17:34:55.964398Z"
    },
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "message1 = None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5547356ed5bba963",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Восстанавливаем ключ по исходному и шифрованному сообщению:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "2db02d4a332c4cf0",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.028198400Z",
     "start_time": "2024-09-23T17:34:55.970414100Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[21 27]\n",
      " [ 2 23]]\n"
     ]
    }
   ],
   "source": [
    "encr_message_indices = [alphabet.index(char) for char in enc2]\n",
    "orig_message_indices = [alphabet.index(char) for char in message2]\n",
    "matrix_key = None\n",
    "flag = False\n",
    "\n",
    "for i in range(0, len(orig_message_indices)):\n",
    "    for j in range(i, len(orig_message_indices)-3):\n",
    "        orig_block = np.array([orig_message_indices[i:i+2],\n",
    "                               orig_message_indices[j+2:j+4]]).T\n",
    "        encr_block = np.array([encr_message_indices[i:i+2], encr_message_indices[j+2:j+4]]).T\n",
    "        inv_orig_block = inverse_matrix(orig_block) % len(alphabet)\n",
    "        if np.allclose(inv_orig_block, np.round(inv_orig_block)):\n",
    "            matrix_key = (np.dot(encr_block, inv_orig_block) % len(alphabet)).astype(int)\n",
    "            flag = (encrypt(matrix_key, message2) == enc2)\n",
    "        if flag:\n",
    "            break\n",
    "    if flag:\n",
    "        break\n",
    "if matrix_key is not None:\n",
    "    print(matrix_key)\n",
    "    \n",
    "else:\n",
    "    print(\"Не получилось расшифровать\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7bf42ad9f0cc5e9",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Расшифровываем забытое сообщение:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "1f1d997f19797efb",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.131535500Z",
     "start_time": "2024-09-23T17:34:55.975296500Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Я ЛЮБЛЮ БОРЩ'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decrypt(matrix_key, enc1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9f72bf26baa47e5",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Задание 3. Код Хэмминга"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e672eb6d44603125",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Русский алфавит:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "8452de2ca9847d86",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.132535100Z",
     "start_time": "2024-09-23T17:34:55.981296900Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "russian_alphabet = \"абвгдежзийклмнопрстуфхцчшщъыьэюя\"\n",
    "n = len(russian_alphabet)\n",
    "n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "113dbc23cca8ed43",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Присвоим каждой букве пятибитовый двоичный номер:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "5769f65c0d71592d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.133535400Z",
     "start_time": "2024-09-23T17:34:55.985194200Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'а': '00000',\n",
       " 'б': '00001',\n",
       " 'в': '00010',\n",
       " 'г': '00011',\n",
       " 'д': '00100',\n",
       " 'е': '00101',\n",
       " 'ж': '00110',\n",
       " 'з': '00111',\n",
       " 'и': '01000',\n",
       " 'й': '01001',\n",
       " 'к': '01010',\n",
       " 'л': '01011',\n",
       " 'м': '01100',\n",
       " 'н': '01101',\n",
       " 'о': '01110',\n",
       " 'п': '01111',\n",
       " 'р': '10000',\n",
       " 'с': '10001',\n",
       " 'т': '10010',\n",
       " 'у': '10011',\n",
       " 'ф': '10100',\n",
       " 'х': '10101',\n",
       " 'ц': '10110',\n",
       " 'ч': '10111',\n",
       " 'ш': '11000',\n",
       " 'щ': '11001',\n",
       " 'ъ': '11010',\n",
       " 'ы': '11011',\n",
       " 'ь': '11100',\n",
       " 'э': '11101',\n",
       " 'ю': '11110',\n",
       " 'я': '11111'}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def convert_to_five_bit_number(number):\n",
    "    return f\"{number:05b}\"\n",
    "\n",
    "\n",
    "russian_bin_alphabet = {russian_alphabet[i]: convert_to_five_bit_number(i) for i in range(n)}\n",
    "russian_bin_alphabet"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48264d609de44b31",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Интересное слово из 4 букв:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "408bef816ba444a4",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.133535400Z",
     "start_time": "2024-09-23T17:34:55.990197200Z"
    },
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "word = \"ядро\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "641a9343fc9e19ae",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Закодируем двоичным кодом:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "8fe3ca032058a381",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.134535900Z",
     "start_time": "2024-09-23T17:34:55.992484Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'11111001001000001110'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "encrypted_bin_word = \"\".join([russian_bin_alphabet[letter] for letter in list(word)])\n",
    "encrypted_bin_word"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "188f2513626d2719",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Составим матрицы G и H:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "b93a0d87b8a77b3d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.146534600Z",
     "start_time": "2024-09-23T17:34:55.997797100Z"
    },
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "G = np.array([[1, 1, 0, 1],\n",
    "              [1, 0, 1, 1], \n",
    "              [1, 0, 0, 0],\n",
    "              [0, 1, 1, 1],\n",
    "              [0, 1, 0, 0],\n",
    "              [0, 0, 1, 0],\n",
    "              [0, 0, 0, 1]])\n",
    "H = np.array([[1, 0, 1, 0, 1, 0, 1],\n",
    "              [0, 1, 1, 0, 0, 1, 1],\n",
    "              [0, 0, 0, 1, 1, 1, 1]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8d7e9335b9b8e07",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "* Матрица G (матрица-генератор кодов) преобразует входное сообщение векторного размера (4,1) в закодированное сообщение размером (7,1), добавляя три бита четности. Таким образом, размерность матрицы составляет (7,4).\n",
    "* Матрица H служит для проверки наличия ошибок в закодированном сообщении. Она принимает вектор размером (7,1) и возвращает вектор размером (3,1). Размерность матрицы H равна (3,7). Если сообщение не содержит ошибок, результат будет нулевым вектором; в противном случае матрица укажет на испорченные биты.\n",
    "* H * G^T = 0 - так выбирается матрицы"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17cdfa7601f2f845",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Закодируем слово с помощью матрицы G:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "33b2b7d8c7ef12c7",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.147534700Z",
     "start_time": "2024-09-23T17:34:56.001545Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'11111110011001010101000000000010110'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "encoded_word = ''\n",
    "for i in range(0, len(encrypted_bin_word), 4):\n",
    "    p = np.array([int(c) for c in encrypted_bin_word[i : i + 4]])\n",
    "    x = np.dot(G, p) % 2\n",
    "    encoded_word += ''.join([str(i) for i in x])\n",
    "\n",
    "encoded_word"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8be7bc3fd3f7ad3c",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Сымитируем вредоносное вмешательство:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "17a5c6a5c8f56875",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.148752500Z",
     "start_time": "2024-09-23T17:34:56.005946800Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Сообщения с ошибками:\n",
      "['11111110011101010101000000000010110', '11111010011001010101000000000011110', '11111110011001110100010000000010110', '11110110011101010101011000000010110']\n"
     ]
    }
   ],
   "source": [
    "def break_bits(encoded_word, num_errors):\n",
    "    broken = list(encoded_word)\n",
    "    indices = set()\n",
    "    while len(indices) < num_errors:\n",
    "        i = np.random.randint(0, len(broken) - 1)\n",
    "        if i not in indices:\n",
    "            broken[i] = '1' if broken[i] == '0' else '0'\n",
    "            indices.add(i)\n",
    "    return ''.join(broken)\n",
    "\n",
    "\n",
    "broken_words = [break_bits(encoded_word, num_errors) for num_errors in range(1, 5)]\n",
    "print(\"Сообщения с ошибками:\")\n",
    "print(broken_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7658e879d5fab206",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Находим и исправляем ошибки с помощью матрицы H и декодируем сообщение:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "9e76a9bc30ff1849",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.159830800Z",
     "start_time": "2024-09-23T17:34:56.011944200Z"
    },
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "R = np.array([[0, 0, 1, 0, 0, 0, 0],\n",
    "              [0, 0, 0, 0, 1, 0, 0],\n",
    "              [0, 0, 0, 0, 0, 1, 0],\n",
    "              [0, 0, 0, 0, 0, 0, 1]])\n",
    "decoded_words = []\n",
    "for broken in broken_words:\n",
    "    word_bin = ''\n",
    "    for i in range(0, len(broken), 7):\n",
    "        r = np.array([int(c) for c in broken[i:i + 7]])\n",
    "        z = H.dot(r) % 2  # Синдром ошибки\n",
    "        if np.any(z):  # Если есть ошибка\n",
    "            idx = int(''.join(map(str, z[::-1])), 2) - 1  # Индекс ошибочного бита\n",
    "            if idx >= 0:  # Проверка на валидный индекс\n",
    "                r[idx] = 1 - r[idx]  # Исправляем ошибочный бит\n",
    "        p = R.dot(r) % 2  # Извлекаем информационные биты\n",
    "        word_bin += ''.join(map(str, p))\n",
    "    decoded_words.append(word_bin)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de1a66db6e59e7dc",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "### Переводим полученный результат в слово из 4-х букв"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "3332e0e31b68692e",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-09-23T17:34:56.160830300Z",
     "start_time": "2024-09-23T17:34:56.016892900Z"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ядро\n",
      "ядро\n",
      "ядио\n",
      "ядфо\n"
     ]
    }
   ],
   "source": [
    "for word_bin in decoded_words:\n",
    "    result = ''\n",
    "    for i in range(0, len(word_bin), 5):\n",
    "        result += russian_alphabet[list(russian_bin_alphabet.values()).index(word_bin[i : i + 5])]\n",
    "    print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7cbe36f5",
   "metadata": {},
   "source": [
    "### Вывод: \n",
    "#### В данной лабораторной работе мы узнали о разных видах шифров.\n",
    "Шифр Хилла:\n",
    "1) Научились шифровать и расшифровывать сообщения. Также попробовали испортить шифр и расшифровать, в итоге поняли, что даже 1 \"помеха\" может испортить шифр.\n",
    "2) Научились применять Линейную алгебру для находения ключа, зная фразу и его шифр.\n",
    "\n",
    "Код Хэмминга:\n",
    "1) Узнали о наличии данного типа шифрования\n",
    "2) Попробовали использовать данный шифр, испортить и декодировать. В итоге пришли к выводу, чем больше \"помех\", тем больше шанс, что сообщение может испортиться."
   ]
  }
 ],
 "metadata": {
  "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}