A quick look at a modular arithmetic encryption scheme

encrypted-otps.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Note: GitHub does not render LaTeX embedded in Jupyter Notebooks at the time of writing.  Please paste the Github URL of this document into http://nbviewer.jupyter.org/ if your view is missing mathematics._\n",
    "\n",
    "### Introduction\n",
    "I was recently asked the following questions.\n",
    ">I want to send a 4 digit OTP to a client app.  I want to obscure it.  If I multiply it by a 10 digit prime, divide that by a 6 digit prime, and take the remainder, will there be only one OTP value that yields a given remainder?  i.e. no collisions.  And would it be hardish to work out the values of the 10 digit and 6 digit primes even given a few examples of OTPs and their remainders?\n",
    "\n",
    "My notes follow.  I'm sure a much more comprehensive cryptanalysis is possible.\n",
    "\n",
    "### Collision free\n",
    "Let $n_1$ and $n_2$ be clear OTPs, $p$ the prime multiplier and $q$ the prime divisor.  With $q$ prime, arithmetic mod $q$ is a [finite field](https://en.wikipedia.org/wiki/Field_%28mathematics%29) so quotients always exist and are always unique.  So, whether $p$ is composite or prime, the division through by $p$ is allowed in the following equation\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "n_1p & \\equiv n_2p \\mod q \\\\\n",
    "\\iff n_1 & \\equiv n_2 \\mod q.\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "We see that the multiplier $p$ has no bearing on whether or not the encryption scheme is 1-1.  Instead we need only choose the prime $q$ large enough that any distinct pair of four digit OTPs $n_1$ and $n_2$ are unequal mod $q$.  This happens exactly when $q >= 10^4$ so 6 digits for $q$ are plenty.\n",
    "\n",
    "### Strength of the scheme\n",
    "As a general remark factorising large \"semi-primes\", large integers that are the product of two large primes, is computationally hard (runs in exponential time) while [searching for primes themselves is less hard](https://en.wikipedia.org/wiki/Generating_primes).\n",
    "\n",
    "Now to the specifics of the proposed scheme.  Let's say I have seen the source code and know the scheme but have not discovered $p$ or $q$.  Firstly after having seen a number of encrypted OTPs, I have a pretty good idea of the size of $q$.  [There are only ~70k primes of six digits](https://primes.utm.edu/howmany.html) to start with and the largest encrypted OTP I've seen so far lets me discount all possibilities for $q$ smaller than that OTP.  So there are not many values of $q$ that I'll have to test, let's call it $10^4$.\n",
    "\n",
    "Beyond that, the following calculation shows that I do not need $p$ itself, but instead only the smaller number $p^{-1} \\mod q$ (or equivalently $p \\mod q$) to be able to reverse any encrypted OTP back to clear text.\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "& (np \\mod q) \\times (p^{-1} \\mod q) \\mod q \\\\\n",
    "&= npp^{-1} \\mod q \\\\\n",
    "&= n \\mod q \\\\\n",
    "&= n\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "With one compromised OTP and having seen a few encrypted OTPs, brute force checking $q$ and $p^{-1} \\mod q$ amounts to less than $10^4 \\times 10^6 = 10^{10}$ integer multiplications, mods and compares and is trivially parallelisable.  The Raspberry Pi 3 delivers $\\sim 2500$ Dhrystone MIPS, or $\\sim 0.25 \\times 10^{10}$ integer operations per second.  So there's a problem here, and the required search space may well be smaller than the one I'm using here.  Then there's the question of how quickly the search space shrinks if a *few OTPs* are compromised..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sample Code\n",
    "This doesn't implement any of the attack, just checks the formula above on a single example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Clear OTP:\t\t1234\n",
      "Encrypted OTP:\t\t408908\n",
      "P inverse mod q:\t150259\n",
      "Decrypted OTP:\t\t1234\n"
     ]
    }
   ],
   "source": [
    "# initialise\n",
    "otp = 1234\n",
    "p = 30012000019 # prime but needn't be\n",
    "q = 500009 # prime\n",
    "\n",
    "print(\"Clear OTP:\\t\\t{}\".format(otp))\n",
    "\n",
    "# encrypt\n",
    "crypt = otp * p % q\n",
    "print(\"Encrypted OTP:\\t\\t{}\".format(crypt))\n",
    "\n",
    "# find p^{-1} mod q using Fermat's Little Theorem\n",
    "p_inv_mod_q = pow(p, q-2, q)\n",
    "print(\"P inverse mod q:\\t{}\".format(p_inv_mod_q))\n",
    "\n",
    "# check we found it\n",
    "assert p * p_inv_mod_q % q == 1\n",
    "\n",
    "# reverse the OTP\n",
    "print(\"Decrypted OTP:\\t\\t{}\".format(crypt * p_inv_mod_q % q))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "© James Turton 2016\n",
    "[MIT License](https://opensource.org/licenses/MIT)"
   ]
  }
 ],
 "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.5.2+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}