tinymt.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TinyMTにおいてLINEARITY_CHECKがONのときに連続する4つの乱数値からstateを得るためのSageMathのプログラムです"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mat1 = 0x8f7011ee\n",
    "mat2 = 0xfc78ff1f\n",
    "tmat = 0x3793fdff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "F2 = GF(2)\n",
    "\n",
    "def int_to_f2(x):\n",
    "    return vector([F2((x >> i) & 1) for i in range(32)])\n",
    "\n",
    "def ints_to_f2(xs):\n",
    "    return vector([F2((xs[floor(i / 32)] >> (i % 32)) & 1) for i in range(32*len(xs))])\n",
    "\n",
    "def f2_to_int(vec):\n",
    "    x = 0\n",
    "    for i in range(32):\n",
    "        x |= Integer(vec[i]) << i\n",
    "    return x\n",
    "\n",
    "def f2_to_ints(vec):\n",
    "    return [f2_to_int(vec[i*32:i*32+32]) for i in range(floor(len(vec) / 32))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def join_matrix_yoko(mats):\n",
    "    m = mats[0].nrows()\n",
    "    n = mats[0].ncols()\n",
    "    return matrix([[mats[floor(j / n)][i, j % n] for j in range(n*len(mats))] for i in range(m)])\n",
    "\n",
    "def join_matrix_tate(mats):\n",
    "    m = mats[0].nrows()\n",
    "    n = mats[0].ncols()\n",
    "    return matrix([[mats[floor(i / m)][i % m, j] for j in range(n)] for i in range(m*len(mats))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def elem_matrix(i):\n",
    "    mats = [Mat(GF(2), 32, 32).zero() for j in range(4)]\n",
    "    mats[i] = Mat(GF(2), 32, 32).identity_matrix()\n",
    "    return join_matrix_yoko(mats)\n",
    "\n",
    "def xi(x):\n",
    "    if x:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "def rshift_matrix(k):\n",
    "    return matrix([[F2(xi(j - i == k)) for j in range(32)] for i in range(32)])\n",
    "\n",
    "def lshift_matrix(k):\n",
    "    return rshift_matrix(-k)\n",
    "\n",
    "def constant_matrix(a):\n",
    "    m = [[F2(0) for j in range(32)] for i in range(32)]\n",
    "    for i in range(32):\n",
    "        m[i][0] = a[i]\n",
    "    return matrix(m)\n",
    "\n",
    "def mask_matrix(a):\n",
    "    return matrix([[F2(a[i] * xi(i == j)) for j in range(32)] for i in range(32)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def temper_matrix():\n",
    "    t0 = elem_matrix(3)\n",
    "    t1 = elem_matrix(0) + rshift_matrix(8) * elem_matrix(2)\n",
    "    return t0 + t1 + constant_matrix(int_to_f2(tmat)) * t1\n",
    "\n",
    "temper = temper_matrix()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def next_state_matrix():\n",
    "    y = elem_matrix(3)\n",
    "    x = mask_matrix(int_to_f2(0x7fffffff)) * elem_matrix(0) + elem_matrix(1) + elem_matrix(2)\n",
    "    x += lshift_matrix(1) * x\n",
    "    y += rshift_matrix(1) * y + x\n",
    "    st0 = elem_matrix(1)\n",
    "    st1 = elem_matrix(2) + constant_matrix(int_to_f2(mat1)) * y\n",
    "    st2 = x + lshift_matrix(10) * y + constant_matrix(int_to_f2(mat2)) * y\n",
    "    st3 = y\n",
    "    return join_matrix_tate([st0, st1, st2, st3])\n",
    "\n",
    "next_state = next_state_matrix()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def genrand_matrix():\n",
    "    r0 = temper_matrix()\n",
    "    r1 = temper_matrix() * next_state_matrix()\n",
    "    r2 = temper_matrix() * next_state_matrix() * next_state_matrix()\n",
    "    r3 = temper_matrix() * next_state_matrix() * next_state_matrix() * next_state_matrix()\n",
    "    return join_matrix_tate([r0, r1, r2, r3])\n",
    "\n",
    "genrand = genrand_matrix()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['5740a11a', '3cfe1de3', 'a5083b98', '14ef46dc']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x.str(16) for x in f2_to_ints(next_state * ints_to_f2([0x63B07A71, 0x5740A11A, 0x3CFE1DE3, 0x08A80987]))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['3cfe1de3', '2a782a76', 'a21332bc', '4d436c11']"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x.str(16) for x in f2_to_ints(next_state * ints_to_f2([0x5740A11A, 0x3CFE1DE3, 0xA5083B98, 0x14EF46DC]))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['deadbeef', '12345678', '11235813', '31415926']"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x.str(16) for x in f2_to_ints(genrand.solve_right(ints_to_f2([0xd86e396e, 0xddb8558b, 0x73d760e1, 0x488d524d])))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.4",
   "language": "",
   "name": "sage-7.4"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}