● videoCrypto

Hashing and Asymmetric Encryption

Unlock CS Fundamentals on Video

6+ hours across 72 lessons — Data Structures, Algorithms, Cryptography, Binary, Software Design, and Essential Unix Skills.

Subscribe — full access →Buy Now$79

SECTION

Crypto

NEXT UP

Functional Programming

COURSE

Computer Science Fundamentals

34 lessons

About this lesson

I've used hashes for a long time and had a general understanding of what they do... but that's about it. I knew I needed to hash passwords (and other secure data) if I was going to store them in my database... but that's about all.

I was never sure which algorithms to use nor why... so I dug in and found out. That's the first part of this video.

The second is asymmetric encryption: encoding with a public key and decoding with a second, private key. Absolutely ground-breaking idea! The math is amazingly straightforward too... although I will admit to struggling to explain some of it.

The Code

To produce a simple hash using Node:

<span class="hljs-keyword">const</span> crypto = <span class="hljs-built_in">require</span>(<span class="hljs-string">&quot;crypto&quot;</span>);

<span class="hljs-keyword">const</span> hash = crypto.<span class="hljs-title function_">createHash</span>(<span class="hljs-string">&quot;sha256&quot;</span>)
.<span class="hljs-title function_">update</span>(<span class="hljs-string">&quot;hi&quot;</span>)
.<span class="hljs-title function_">digest</span>(<span class="hljs-string">&quot;hex&quot;</span>);

<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(hash);

Hashing a password with PBKDF2 using a million rounds to slow things down:

<span class="hljs-keyword">const</span> crypto = <span class="hljs-built_in">require</span>(<span class="hljs-string">&quot;crypto&quot;</span>);

<span class="hljs-keyword">const</span> hashPassword = <span class="hljs-keyword">function</span>(<span class="hljs-params">pw</span>){
  <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> <span class="hljs-title class_">Promise</span>(<span class="hljs-keyword">function</span>(<span class="hljs-params">resolve, reject</span>){
    crypto.<span class="hljs-title function_">pbkdf2</span>(pw,<span class="hljs-string">&quot;super-secret-salt&quot;</span>,<span class="hljs-number">1000000</span>,<span class="hljs-number">32</span>,<span class="hljs-string">&quot;sha512&quot;</span>, <span class="hljs-keyword">function</span>(<span class="hljs-params">err, buffer</span>){
      <span class="hljs-keyword">if</span>(err) <span class="hljs-title function_">reject</span>(err);
      <span class="hljs-keyword">else</span> <span class="hljs-title function_">resolve</span>(buffer.<span class="hljs-title function_">toString</span>(<span class="hljs-string">&quot;hex&quot;</span>))
    });
  })
}

Hashing using scrypt, assigning a cost:

<span class="hljs-keyword">const</span> hashPassword = <span class="hljs-keyword">function</span>(<span class="hljs-params">pw</span>){
  <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> <span class="hljs-title class_">Promise</span>(<span class="hljs-keyword">function</span>(<span class="hljs-params">resolve, reject</span>){
    crypto.<span class="hljs-title function_">scrypt</span>(pw,<span class="hljs-string">&quot;super-secret-salt&quot;</span>,<span class="hljs-number">32</span>, {<span class="hljs-attr">cost</span>: <span class="hljs-number">2</span>**<span class="hljs-number">14</span>}, <span class="hljs-keyword">function</span>(<span class="hljs-params">err, buffer</span>){
      <span class="hljs-keyword">if</span>(err) <span class="hljs-title function_">reject</span>(err);
      <span class="hljs-keyword">else</span> <span class="hljs-title function_">resolve</span>(buffer.<span class="hljs-title function_">toString</span>(<span class="hljs-string">&quot;hex&quot;</span>))
    });
  })
}

Creating a checksum using MD5:

<span class="hljs-keyword">const</span> crypto = <span class="hljs-built_in">require</span>(<span class="hljs-string">&quot;crypto&quot;</span>);
<span class="hljs-keyword">const</span> fs = <span class="hljs-built_in">require</span>(<span class="hljs-string">&quot;fs&quot;</span>);

<span class="hljs-keyword">const</span> data = fs.<span class="hljs-title function_">readFileSync</span>(<span class="hljs-string">&quot;./message.txt&quot;</span>);

<span class="hljs-keyword">const</span> checksum = <span class="hljs-keyword">function</span>(<span class="hljs-params">data</span>){
  <span class="hljs-keyword">return</span> crypto.<span class="hljs-title function_">createHash</span>(<span class="hljs-string">&quot;md5&quot;</span>).<span class="hljs-title function_">update</span>(data, <span class="hljs-string">&quot;utf8&quot;</span>).<span class="hljs-title function_">digest</span>(<span class="hljs-string">&quot;hex&quot;</span>)
}

<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-title function_">checksum</span>(data));

A super-simple mining operation (meant for demonstration only) for blockchain stuff:

<span class="hljs-keyword">const</span> crypto = <span class="hljs-built_in">require</span>(<span class="hljs-string">&quot;crypto&quot;</span>);

<span class="hljs-keyword">const</span> <span class="hljs-title function_">createHash</span> = (<span class="hljs-params">block</span>) =&gt; {
  <span class="hljs-comment">//need to pass a string to our </span>
  <span class="hljs-keyword">const</span> hashValue = <span class="hljs-title class_">JSON</span>.<span class="hljs-title function_">stringify</span>(block)
  <span class="hljs-keyword">return</span> crypto.<span class="hljs-title function_">createHash</span>(<span class="hljs-string">&quot;sha256&quot;</span>)
  .<span class="hljs-title function_">update</span>(hashValue)
  .<span class="hljs-title function_">digest</span>(<span class="hljs-string">&quot;base64&quot;</span>);
}

<span class="hljs-keyword">const</span> <span class="hljs-title function_">mine</span> = (<span class="hljs-params">block, difficulty = <span class="hljs-number">2</span></span>) =&gt; {
  <span class="hljs-keyword">let</span> found = <span class="hljs-literal">false</span>, start = <span class="hljs-keyword">new</span> <span class="hljs-title class_">Date</span>().<span class="hljs-title function_">getTime</span>();
  <span class="hljs-comment">//we&#x27;re looking for a string of 0s so let&#x27;s create the pattern</span>
  <span class="hljs-comment">//I could use Regex but I&#x27;m not that good</span>
  <span class="hljs-keyword">const</span> lookingFor = <span class="hljs-string">&quot;0&quot;</span>.<span class="hljs-title function_">padStart</span>(difficulty, <span class="hljs-string">&quot;0&quot;</span>);
  <span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;Looking for a hash starting with&quot;</span>, lookingFor);
  <span class="hljs-keyword">const</span> duration = <span class="hljs-keyword">new</span> <span class="hljs-title class_">Date</span>().<span class="hljs-title function_">getTime</span>() - start;

  <span class="hljs-keyword">while</span>(!found){
    <span class="hljs-keyword">const</span> possibleHash = <span class="hljs-title function_">createHash</span>(block);  
    <span class="hljs-comment">//does the hash start with zeroes?</span>
    found = possibleHash.<span class="hljs-title function_">substring</span>(<span class="hljs-number">0</span>, difficulty) === lookingFor;
    <span class="hljs-keyword">if</span>(found){
      block.<span class="hljs-property">hashKey</span> = possibleHash;
      <span class="hljs-keyword">return</span> block;
    }
    block.<span class="hljs-property">nonce</span> += <span class="hljs-number">1</span>;
    <span class="hljs-comment">//10 second kill switch</span>
    <span class="hljs-keyword">if</span>(duration &gt; <span class="hljs-number">10000</span>) <span class="hljs-keyword">return</span> <span class="hljs-string">&quot;Didn&#x27;t find it under 10s&quot;</span>
  }
}

<span class="hljs-keyword">const</span> block = {
  <span class="hljs-attr">transactions</span>: [
    {<span class="hljs-attr">from</span>: <span class="hljs-string">&quot;me&quot;</span>, <span class="hljs-attr">to</span>: <span class="hljs-string">&quot;you&quot;</span>, <span class="hljs-attr">amount</span>: <span class="hljs-number">10.00</span>},
    {<span class="hljs-attr">from</span>: <span class="hljs-string">&quot;you&quot;</span>, <span class="hljs-attr">to</span>: <span class="hljs-string">&quot;me&quot;</span>, <span class="hljs-attr">amount</span>: <span class="hljs-number">5.00</span>}
  ],
  <span class="hljs-attr">timestamp</span>: <span class="hljs-number">1609702546153</span>, <span class="hljs-comment">//if this changes the hash changes</span>
  <span class="hljs-attr">nonce</span>: <span class="hljs-number">0</span>,
  <span class="hljs-attr">previousKey</span>: <span class="hljs-string">&quot;00RSDThMVcQAvoocD3klO/6pjJ4a8pRbZ3ykk3XXhXE=&quot;</span>
}
<span class="hljs-comment">//let&#x27;s see how long this takes</span>
<span class="hljs-keyword">const</span> start = <span class="hljs-keyword">new</span> <span class="hljs-title class_">Date</span>().<span class="hljs-title function_">getTime</span>();
<span class="hljs-comment">//let&#x27;s do it!</span>
<span class="hljs-keyword">const</span> result = <span class="hljs-title function_">mine</span>(block, <span class="hljs-number">4</span>);
<span class="hljs-keyword">const</span> duration = <span class="hljs-keyword">new</span> <span class="hljs-title class_">Date</span>().<span class="hljs-title function_">getTime</span>() - start;
<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">`That took duration <span class="hljs-subst">${duration}</span>ms`</span>);
<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(result);

And finally, our trip through the basics of RSA using super small primes:

<span class="hljs-comment">//resources</span>
<span class="hljs-comment">//https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html</span>
<span class="hljs-comment">//https://www.cryptool.org/en/cto/highlights/rsa-step-by-step</span>
<span class="hljs-comment">//let&#x27;s find two relatively prime numbers, e and d, such that</span>
<span class="hljs-comment">//e % d mod r === 1</span>
<span class="hljs-comment">//this is the cornerstone of RSA</span>
<span class="hljs-keyword">var</span> findEandD = <span class="hljs-keyword">function</span>(<span class="hljs-params">r</span>) {
  <span class="hljs-comment">//These are common candidates for e, which can be autoset</span>
  <span class="hljs-comment">//and typically 65537 is used, but we&#x27;ll</span>
  <span class="hljs-comment">//start small for speed</span>
  <span class="hljs-keyword">const</span> possibleEs = [<span class="hljs-number">3n</span>,<span class="hljs-number">5n</span>,<span class="hljs-number">17n</span>,<span class="hljs-number">257n</span>,<span class="hljs-number">65537n</span>]
  <span class="hljs-comment">//now, loop over the possible e&#x27;s so we can find our d</span>
  <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> e <span class="hljs-keyword">of</span> possibleEs){
    <span class="hljs-comment">//we want to find a coprime for e, so let&#x27;s factor it</span>
    <span class="hljs-comment">//up to r and see if e % r is 1</span>
    <span class="hljs-comment">//if it is, we found our coprime</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> d = <span class="hljs-number">1n</span>; d &lt; r; d++) {
      <span class="hljs-keyword">const</span> candidate = e * d;
      <span class="hljs-keyword">if</span> (candidate % r == <span class="hljs-number">1n</span>) <span class="hljs-keyword">return</span> {<span class="hljs-attr">e</span>: e, <span class="hljs-attr">d</span>: d};
    }
  }
  assert.<span class="hljs-title function_">fail</span>(<span class="hljs-string">&quot;We shouldn&#x27;t reach this point&quot;</span>)
}

<span class="hljs-keyword">const</span> p = <span class="hljs-number">499n</span>;
<span class="hljs-keyword">const</span> q = <span class="hljs-number">491n</span>;
assert.<span class="hljs-title function_">notStrictEqual</span>(p,q, <span class="hljs-string">&quot;p and q must be different primes&quot;</span>);

<span class="hljs-comment">//our public key, N</span>
<span class="hljs-keyword">const</span> N = p * q;

<span class="hljs-comment">//Euler&#x27;s totient for deriving r</span>
<span class="hljs-comment">//r = phi(n) = (p-1) * (q-1)</span>
<span class="hljs-keyword">const</span> r = (p-<span class="hljs-number">1n</span>) * (q-<span class="hljs-number">1n</span>);

<span class="hljs-comment">//now we can calculate e and d for our private key</span>
<span class="hljs-keyword">const</span> {e,d} = <span class="hljs-title function_">findEandD</span>(r);

<span class="hljs-comment">//our message</span>
<span class="hljs-keyword">const</span> M = <span class="hljs-number">25n</span>;

<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;e&quot;</span>,e);
<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;d&quot;</span>,d);
<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;N&quot;</span>,N);
<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;r&quot;</span>,r);

<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;M&quot;</span>, M);

<span class="hljs-comment">//the RSA algorithm</span>
<span class="hljs-keyword">const</span> encrypted = M**e % N;
<span class="hljs-keyword">const</span> decrypted = encrypted**d % N;

<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;Encrypted&quot;</span>,encrypted);
<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-string">&quot;Decrypted&quot;</span>,decrypted);

Links and Resources

I cite a number of articles in this video - hard not to. But here they are if you want to read more:

Unlock CS Fundamentals on Video

6+ hours across 72 lessons — Data Structures, Algorithms, Cryptography, Binary, Software Design, and Essential Unix Skills.

Subscribe — full access →Buy Now$79

← PREVIOUS

Encryption Basics

Functional Programming