proc_ranking.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "HW: 4, Block size: 128 bits\n",
      "  Total combinations: 10668000 = 162.78 MB stream size\n",
      "\n",
      "Partitioning to 4 parts, partition size: 2667000, sequence size: 40.70 MB\n",
      "\n",
      "  state[0]: [0, 1, 2, 3]\n",
      "  state[1]: [8, 55, 92, 114]\n",
      "  state[2]: [20, 25, 69, 91]\n",
      "  state[3]: [37, 39, 63, 70]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/xklinec/.pyenv/versions/3.6.5/lib/python3.6/site-packages/ipykernel_launcher.py:18: DeprecationWarning: `comb` is deprecated!\n",
      "Importing `comb` from scipy.misc is deprecated in scipy 1.0.0. Use `scipy.special.comb` instead.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(2667000, [[0, 1, 2, 3], [8, 55, 92, 114], [20, 25, 69, 91], [37, 39, 63, 70]])"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import sys\n",
    "from scipy import misc\n",
    "\n",
    "if sys.version_info >= (3, 2):\n",
    "    from functools import lru_cache\n",
    "else:\n",
    "    from repoze.lru import lru_cache\n",
    "    \n",
    "if hasattr(scipy.misc, 'comb'):\n",
    "    scipy_comb = scipy.misc.comb\n",
    "else:\n",
    "    import scipy.special\n",
    "    scipy_comb = scipy.special.comb\n",
    "   \n",
    "\n",
    "@lru_cache(maxsize=1024)\n",
    "def comb(n, k, exact=False):\n",
    "    return scipy_comb(n, k, exact=exact)\n",
    "\n",
    "\n",
    "def rank(s, n):\n",
    "    \"\"\"\n",
    "    Returns index of the combination s in (N,K)\n",
    "    https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/\n",
    "    :param s:\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    k = len(s)\n",
    "    r = 0\n",
    "    for i in range(0, k):\n",
    "        for v in range(s[i-1]+1 if i > 0 else 0, s[i]):\n",
    "            r += comb_cached(n - v - 1, k - i - 1)\n",
    "    return r\n",
    "\n",
    "\n",
    "@lru_cache(maxsize=8192)\n",
    "def unrank(i, n, k):\n",
    "    \"\"\"\n",
    "    returns the i-th combination of k numbers chosen from 0,2,...,n-1, indexing from 0\n",
    "    \"\"\"\n",
    "    c = []\n",
    "    r = i+0\n",
    "    j = 0\n",
    "    for s in range(1, k+1):\n",
    "        cs = j+1\n",
    "\n",
    "        while True:\n",
    "            if n-cs < 0:\n",
    "                raise ValueError('Invalid index')\n",
    "            decr = comb(n-cs, k-s)\n",
    "            if r > 0 and decr == 0:\n",
    "                raise ValueError('Invalid index')\n",
    "            if r - decr >= 0:\n",
    "                r -= decr\n",
    "                cs += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        c.append(cs-1)\n",
    "        j = cs\n",
    "    return c\n",
    "\n",
    "\n",
    "def partition_space(hw, bits, partitions):\n",
    "    comb_space = int(comb(bits, hw))\n",
    "    total_size = bits * comb_space\n",
    "    total_size_mb = total_size / 8 / 1024 / 1024\n",
    "    \n",
    "    chunk_size = int(comb_space // partitions)\n",
    "    print('HW: %s, Block size: %s bits\\n  Total combinations: %s = %.2f MB stream size' \n",
    "          % (hw, bits, comb_space, total_size_mb))\n",
    "    print('\\nPartitioning to %s parts, partition size: %s, sequence size: %.2f MB\\n' \n",
    "          % (partitions, chunk_size, bits * chunk_size / 8 / 1024 / 1024))\n",
    "    \n",
    "    res = []\n",
    "    for i in range(partitions):\n",
    "        offset = i*chunk_size\n",
    "        state = unrank(offset, bits, hw)\n",
    "        res.append(state)\n",
    "        print('  state[%s]: %s' % (i, state))\n",
    "    return chunk_size, res\n",
    "\n",
    "partition_space(4, 128, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/xklinec/.pyenv/versions/3.6.5/lib/python3.6/site-packages/ipykernel_launcher.py:18: DeprecationWarning: `comb` is deprecated!\n",
      "Importing `comb` from scipy.misc is deprecated in scipy 1.0.0. Use `scipy.special.comb` instead.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[124, 125, 126, 127]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unrank(10668000-1, 128, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from rtt_tools import dump_data\n",
    "L = dump_data.Loader()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Einfo(id=16, m='hw', s='1fe40505e131963c', si=10485760, osi='10MiB', fname=None, fr=None, fb=None, k='1212313', off='1212', der='121233')\n",
      "('16', 'hw', '1fe40505e131963c', '10MiB', '1212313', '1212', '121233', 'AES_r03_b16', '.bin')\n",
      "AES_r03_b16\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "Einfo(id=16, m='hw', s='1fe40505e131963c', si=10485760, osi='10MiB', fname='AES', fr=3, fb='16', k='1212313', off='1212', der='121233')"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L.break_exp('SECMARGINPAPER16_hw_seed_1fe40505e131963c_10MiB_key_1212313_off_1212_der_121233__AES_r03_b16.bin')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Einfo(id=16, m='hw', s='1fe40505e131963c', si=10485760, osi='10MiB', fname=None, fr=None, fb=None, k=None, off=None, der=None)\n",
      "('16', 'hw', '1fe40505e131963c', '10MiB', None, None, None, 'AES_r03_b16', '.bin')\n",
      "AES_r03_b16\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "Einfo(id=16, m='hw', s='1fe40505e131963c', si=10485760, osi='10MiB', fname='AES', fr=3, fb='16', k=None, off=None, der=None)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L.break_exp('SECMARGINPAPER16_hw_seed_1fe40505e131963c_10MiB__AES_r03_b16.bin')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}