Public Key Crypto #pocketbook

readme.md

Click here to view this pocketbook

index.html

  <div class="metadata" style="display: none;"></div>
  <div data-lang="md" data-visibility="output" data-autorun="false" class="block hide-source" data-source-visibility="hidden">
    <pre class="source hljs coffeescript" contenteditable="true"><span class="hljs-comment"># A Tour Through Public Key Cryptography</span>

If you are familiar with modern crypto <span class="hljs-keyword">then</span> there<span class="hljs-string">'s a high likelihood that you'</span>re aware <span class="hljs-keyword">of</span> the importance <span class="hljs-keyword">of</span> prime numbers <span class="hljs-keyword">and</span> an ability to find them.
There are a lot <span class="hljs-keyword">of</span> fancy different algorithms to find them, but <span class="hljs-keyword">for</span> the moment we<span class="hljs-string">'ll leave understanding those as an exercise to the reader and do something relatively dumb:</span></pre>
    <div class="result"><h1 id="atourthroughpublickeycryptography">A Tour Through Public Key Cryptography</h1>
<p>If you are familiar with modern crypto then there's a high likelihood that you're aware of the importance of prime numbers and an ability to find them.</p>
<p>There are a lot of fancy different algorithms to find them, but for the moment we'll leave understanding those as an exercise to the reader and do something relatively dumb:</p></div>
  </div><div data-lang="js" data-visibility="source" data-autorun="false" class="block">
    <pre class="source hljs cs" contenteditable="true"><span class="hljs-keyword">let</span> checkIsPrime = function(number) {
  <span class="hljs-keyword">for</span> (<span class="hljs-keyword">var</span> i = <span class="hljs-number">2</span>; i &lt; number/<span class="hljs-number">2</span>; i++) {
    <span class="hljs-keyword">if</span> ((number % i) === <span class="hljs-number">0</span>) {
      <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
    }
  }
  <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
}

window.findRandomPrime = () =&gt; {
  <span class="hljs-comment">// Pick a random starting point to count down from</span>
  <span class="hljs-keyword">var</span> start = Math.round(Math.random()*<span class="hljs-number">10000</span>);
  <span class="hljs-keyword">while</span> (<span class="hljs-number">1</span>) {
    <span class="hljs-keyword">if</span> (checkIsPrime(start)) <span class="hljs-keyword">return</span> start;
    start -= <span class="hljs-number">1</span>;
  }
}

findRandomPrime()
</pre>
    <div class="result">1291</div>
  </div><div data-lang="md" data-source-visibility="hidden" data-result-visibility="visible" data-autorun="false" class="block hide-source"><pre class="source hljs coffeescript" contenteditable="true">Okay, great, now we need to build out RSA to generate public <span class="hljs-keyword">and</span> private keypairs:</pre><div class="result"><p>Okay, great, now we need to build out RSA to generate public and private keypairs:</p></div></div><div data-lang="js" data-source-visibility="visible" data-result-visibility="visible" data-autorun="false" class="block"><pre class="source hljs javascript" contenteditable="true"><span class="hljs-comment">// <span class="hljs-doctag">NOTE:</span> This one can take a while</span>

<span class="hljs-keyword">let</span> p = findRandomPrime();
<span class="hljs-keyword">let</span> q = findRandomPrime();
<span class="hljs-keyword">let</span> n = p*q; <span class="hljs-comment">// With big enough primes this becomes intractably hard to factor</span>

<span class="hljs-comment">// We need to find integers d and e for:</span>
<span class="hljs-comment">//   d*e&nbsp;% ((p - 1)(q - 1)) == 1</span>
<span class="hljs-comment">// With the constraint that&nbsp;</span>
<span class="hljs-comment">//   1 &lt; d &lt; n - 1</span>
<span class="hljs-comment">// We can rewrite the first equation, with a random integer k</span>
<span class="hljs-comment">//   e == (1 + k*(p - 1)(q - 1))/d</span>

<span class="hljs-keyword">var</span> e = <span class="hljs-literal">null</span>;
<span class="hljs-keyword">var</span> d = <span class="hljs-literal">null</span>;

<span class="hljs-keyword">while</span> (e === <span class="hljs-literal">null</span>) {
  <span class="hljs-keyword">let</span> k = <span class="hljs-built_in">Math</span>.round(<span class="hljs-built_in">Math</span>.random()*<span class="hljs-number">1000</span>)
  <span class="hljs-keyword">let</span> numerator = (<span class="hljs-number">1</span> + k*(p - <span class="hljs-number">1</span>)*(q - <span class="hljs-number">1</span>))
  <span class="hljs-keyword">for</span> (<span class="hljs-keyword">var</span> i = n - <span class="hljs-number">2</span>; i &gt; <span class="hljs-number">1</span>; i--) {
    <span class="hljs-keyword">if</span> ((numerator % i) === <span class="hljs-number">0</span>) {
      d = i;
      e = numerator / d;
    }
  }
}

<span class="hljs-built_in">window</span>.publicKey = [e, n];
<span class="hljs-comment">// Technically n is "public" but it's convenient to keep alongside the private bits</span>
<span class="hljs-built_in">window</span>.privateKey = [d, n];

<span class="hljs-built_in">JSON</span>.stringify([<span class="hljs-built_in">window</span>.privateKey, <span class="hljs-built_in">window</span>.publicKey])
</pre><div class="result"><pre>[[1181,15709471],[8360717,15709471]]</pre></div></div><div data-lang="md" data-source-visibility="hidden" data-result-visibility="visible" data-autorun="false" class="block hide-source"><pre class="source hljs php" contenteditable="true">Alright, now we<span class="hljs-string">'ve got our keys, we can define our encryption and decryption functions.&nbsp;
These functions rely on numbers taken to large powers of one another, numbers that are too big for Javascript to naturally work with, so we'</span>ll need to <span class="hljs-keyword">include</span> a library to <span class="hljs-keyword">do</span> the math <span class="hljs-keyword">for</span> us.</pre><div class="result"><p>Alright, now we've got our keys, we can define our encryption and decryption functions. </p>
<p>These functions rely on numbers taken to large powers of one another, numbers that are too big for Javascript to naturally work with, so we'll need to include a library to do the math for us.</p></div></div><div data-lang="deps" data-source-visibility="visible" data-result-visibility="hidden" data-autorun="true" class="block hide-result"><pre class="source hljs ruby" contenteditable="true"><span class="hljs-symbol">https:</span>/<span class="hljs-regexp">/cdnjs.cloudflare.com/ajax</span><span class="hljs-regexp">/libs/big</span>-integer/<span class="hljs-number">1.6</span>.<span class="hljs-number">36</span>/BigInteger.min.js</pre><div class="result" style="display: none;">[object Event]</div></div><div data-lang="js" data-source-visibility="visible" data-result-visibility="visible" data-autorun="false" class="block"><pre class="source hljs javascript" contenteditable="true"><span class="hljs-comment">// Encrypt and Decrypt are actually the same function just with different keys!</span>
<span class="hljs-built_in">window</span>.encryptDecrypt = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">m, key</span>) </span>{
  <span class="hljs-keyword">return</span> bigInt(m).modPow(key[<span class="hljs-number">0</span>], key[<span class="hljs-number">1</span>]).valueOf();
};

<span class="hljs-comment">// Try forwards, backwards and with the same key</span>
[<span class="hljs-number">22</span> == encryptDecrypt(encryptDecrypt(<span class="hljs-number">22</span>, publicKey), privateKey),
 <span class="hljs-number">22</span> == encryptDecrypt(encryptDecrypt(<span class="hljs-number">22</span>, privateKey), publicKey),
 <span class="hljs-number">22</span> == encryptDecrypt(encryptDecrypt(<span class="hljs-number">22</span>, privateKey), privateKey)]
</pre><div class="result">true,true,false</div></div><div data-lang="md" data-source-visibility="hidden" data-result-visibility="visible" data-autorun="false" class="block hide-source"><pre class="source hljs coffeescript" contenteditable="true">As you can see: it works! Now let<span class="hljs-string">'s spruce up our function to take a string. We could encode each character, but then we'</span>d just have a substitution cyber which provides ~<span class="hljs-literal">no</span> security so instead we<span class="hljs-string">'ll make a big number from a string.
In security parlance, this is called "padding" the message. There'</span>s a lot <span class="hljs-keyword">of</span> different ways to <span class="hljs-keyword">do</span> it <span class="hljs-keyword">and</span> I<span class="hljs-string">'ll just make one up that is probably insecure!</span></pre><div class="result"><p>As you can see: it works! Now let's spruce up our function to take a string. We could encode each character, but then we'd just have a substitution cyber which provides ~no security so instead we'll make a big number from a string.</p>
<p>In security parlance, this is called "padding" the message. There's a lot of different ways to do it and I'll just make one up that is probably insecure!</p></div></div><div data-lang="js" data-source-visibility="visible" data-result-visibility="visible" data-autorun="false" class="block"><pre class="source hljs javascript" contenteditable="true"><span class="hljs-built_in">window</span>.encrypt = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">s, key</span>) </span>{
  <span class="hljs-keyword">var</span> msg = [];
  <span class="hljs-keyword">var</span> n = bigInt(<span class="hljs-number">0</span>);
  <span class="hljs-keyword">for</span> (<span class="hljs-keyword">var</span> i = <span class="hljs-number">0</span>; i &lt; s.length; i++) {
    <span class="hljs-keyword">var</span> c = n.multiply(<span class="hljs-number">255</span>).add(s.charCodeAt(i));

    <span class="hljs-comment">// If this number would bring us bigger than `n` we'd lose data by</span>
    <span class="hljs-comment">// taking the modulus, so break it out into a chunk</span>
    <span class="hljs-keyword">if</span> (c &gt;= key[<span class="hljs-number">1</span>]) {
      msg.push(n);
      n = bigInt(<span class="hljs-number">0</span>);
      i -= <span class="hljs-number">1</span>;
    } <span class="hljs-keyword">else</span> {
      n = c;
    }
  }
  <span class="hljs-keyword">if</span> (n !== <span class="hljs-number">0</span>) msg.push(n);
  <span class="hljs-keyword">return</span> msg.map(<span class="hljs-function"><span class="hljs-params">n</span> =&gt;</span> n.modPow(key[<span class="hljs-number">0</span>], key[<span class="hljs-number">1</span>]));
};

<span class="hljs-built_in">window</span>.decrypt = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">n, key</span>) </span>{
  <span class="hljs-keyword">return</span> n.map(<span class="hljs-function"><span class="hljs-params">n</span> =&gt;</span> {
    n = n.modPow(key[<span class="hljs-number">0</span>], key[<span class="hljs-number">1</span>])
    <span class="hljs-keyword">var</span> chars = [];
    <span class="hljs-keyword">while</span> (n &gt; <span class="hljs-number">0</span>) {
      <span class="hljs-keyword">var</span> m = n.mod(<span class="hljs-number">255</span>);
      chars.push(m);
      n = n.subtract(m).divide(<span class="hljs-number">255</span>);
    }
    <span class="hljs-keyword">return</span> <span class="hljs-built_in">String</span>.fromCharCode.apply(<span class="hljs-literal">null</span>, chars.reverse());
  }).join(<span class="hljs-string">''</span>);
};

[decrypt(encrypt(<span class="hljs-string">"this is a test"</span>,&nbsp;publicKey), privateKey),
 decrypt(encrypt(<span class="hljs-string">"this is a test"</span>,&nbsp;privateKey),&nbsp;publicKey),
 decrypt(encrypt(<span class="hljs-string">"this is a test"</span>,&nbsp;publicKey),&nbsp;publicKey)]
</pre><div class="result">this is a test,this is a test,Îxk&amp;â¢7b0[</div></div>