src/js/entropy.js

   1 /*
   2  * Detects entropy from a string.
   3  *
   4  * Formats include:
   5  * binary [0-1]
   6  * base 6 [0-5]
   7  * dice 6 [1-6]
   8  * decimal [0-9]
   9  * hexadecimal [0-9A-F]
  10  * card [A2-9TJQK][CDHS]
  11  *
  12  * Automatically uses lowest entropy to avoid issues such as interpretting 0101
  13  * as hexadecimal which would be 16 bits when really it's only 4 bits of binary
  14  * entropy.
  15  */
  16
  17 window.Entropy = new (function() {
  18
  19     // matchers returns an array of the matched events for each type of entropy.
  20     // eg
  21     // matchers.binary("010") returns ["0", "1", "0"]
  22     // matchers.binary("a10") returns ["1", "0"]
  23     // matchers.hex("a10") returns ["a", "1", "0"]
  24     var matchers = {
  25         binary: function(str) {
  26             return str.match(/[0-1]/gi) || [];
  27         },
  28         base6: function(str) {
  29             return str.match(/[0-5]/gi) || [];
  30         },
  31         dice: function(str) {
  32             return str.match(/[1-6]/gi) || []; // ie dice numbers
  33         },
  34         base10: function(str) {
  35             return str.match(/[0-9]/gi) || [];
  36         },
  37         hex: function(str) {
  38             return str.match(/[0-9A-F]/gi) || [];
  39         },
  40         card: function(str) {
  41             // Format is NumberSuit, eg
  42             // AH ace of hearts
  43             // 8C eight of clubs
  44             // TD ten of diamonds
  45             // JS jack of spades
  46             // QH queen of hearts
  47             // KC king of clubs
  48             return str.match(/([A2-9TJQK][CDHS])/gi) || [];
  49         }
  50     }
  51
  52     // Convert array of cards from ["ac", "4d", "ks"]
  53     // to numbers between 0 and 51 [0, 16, 51]
  54     function convertCardsToInts(cards) {
  55         var ints = [];
  56         var values = "a23456789tjqk";
  57         var suits = "cdhs";
  58         for (var i=0; i<cards.length; i++) {
  59             var card = cards[i].toLowerCase();
  60             var value = card[0];
  61             var suit = card[1];
  62             var asInt = 13 * suits.indexOf(suit) + values.indexOf(value);
  63             ints.push(asInt);
  64         }
  65         return ints;
  66     }
  67
  68     this.fromString = function(rawEntropyStr) {
  69         // Find type of entropy being used (binary, hex, dice etc)
  70         var base = getBase(rawEntropyStr);
  71         // Convert dice to base6 entropy (ie 1-6 to 0-5)
  72         // This is done by changing all 6s to 0s
  73         if (base.str == "dice") {
  74             var newParts = [];
  75             var newInts = [];
  76             for (var i=0; i<base.parts.length; i++) {
  77                 var c = base.parts[i];
  78                 if ("12345".indexOf(c) > -1) {
  79                     newParts[i] = base.parts[i];
  80                     newInts[i] = base.ints[i];
  81                 }
  82                 else {
  83                     newParts[i] = "0";
  84                     newInts[i] = 0;
  85                 }
  86             }
  87             base.str = "base 6 (dice)";
  88             base.ints = newInts;
  89             base.parts = newParts;
  90             base.matcher = matchers.base6;
  91         }
  92         // Detect empty entropy
  93         if (base.parts.length == 0) {
  94             return {
  95                 binaryStr: "",
  96                 cleanStr: "",
  97                 cleanHtml: "",
  98                 base: base,
  99             };
 100         }
 101         // Convert base.ints to BigInteger.
 102         // Due to using unusual bases, eg cards of base52, this is not as simple as
 103         // using BigInteger.parse()
 104         var entropyInt = BigInteger.ZERO;
 105         for (var i=base.ints.length-1; i>=0; i--) {
 106             var thisInt = BigInteger.parse(base.ints[i]);
 107             var power = (base.ints.length - 1) - i;
 108             var additionalEntropy = BigInteger.parse(base.asInt).pow(power).multiply(thisInt);
 109             entropyInt = entropyInt.add(additionalEntropy);
 110         }
 111         // Convert entropy to binary
 112         var entropyBin = entropyInt.toString(2);
 113         // If the first integer is small, it must be padded with zeros.
 114         // Otherwise the chance of the first bit being 1 is 100%, which is
 115         // obviously incorrect.
 116         // This is not perfect for non-2^n bases.
 117         var expectedBits = Math.floor(base.parts.length * Math.log2(base.asInt));
 118         while (entropyBin.length < expectedBits) {
 119             entropyBin = "0" + entropyBin;
 120         }
 121         // Assume cards are NOT replaced.
 122         // Additional entropy decreases as more cards are used. This means
 123         // total possible entropy is measured using n!, not base^n.
 124         // eg the second last card can be only one of two, not one of fifty two
 125         // so the added entropy for that card is only one bit at most
 126         if (base.asInt == 52) {
 127             // Get the maximum value WITHOUT replacement
 128             var totalDecks = Math.ceil(base.parts.length / 52);
 129             var totalCards = totalDecks * 52;
 130             var totalCombos = factorial(52).pow(totalDecks);
 131             var totalRemainingCards = totalCards - base.parts.length;
 132             var remainingDecks = Math.floor(totalRemainingCards / 52);
 133             var remainingCards = totalRemainingCards % 52;
 134             var remainingCombos = factorial(52).pow(remainingDecks).multiply(factorial(remainingCards));
 135             var currentCombos = totalCombos.divide(remainingCombos);
 136             var numberOfBits = Math.log2(currentCombos);
 137             var maxWithoutReplace = BigInteger.pow(2, numberOfBits);
 138             // aggresive flooring of numberOfBits by BigInteger.pow means a
 139             // more accurate result can be had for small numbers using the
 140             // built-in Math.pow function.
 141             if (numberOfBits < 32) {
 142                 maxWithoutReplace = BigInteger(Math.round(Math.pow(2, numberOfBits)));
 143             }
 144             // Get the maximum value WITH replacement
 145             var maxWithReplace = BigInteger.pow(52, base.parts.length);
 146             // Calculate the new value by scaling the original value down
 147             var withoutReplace = entropyInt.multiply(maxWithoutReplace).divide(maxWithReplace);
 148             // Left pad with zeros based on number of bits
 149             var entropyBin = withoutReplace.toString(2);
 150             var numberOfBitsInt = Math.floor(numberOfBits);
 151             while (entropyBin.length < numberOfBitsInt) {
 152                 entropyBin = "0" + entropyBin;
 153             }
 154         }
 155         // Supply a 'filtered' entropy string for display purposes
 156         var entropyClean = base.parts.join("");
 157         var entropyHtml = base.parts.join("");
 158         if (base.asInt == 52) {
 159             entropyClean = base.parts.join(" ").toUpperCase();
 160             entropyClean = entropyClean.replace(/C/g, "\u2663");
 161             entropyClean = entropyClean.replace(/D/g, "\u2666");
 162             entropyClean = entropyClean.replace(/H/g, "\u2665");
 163             entropyClean = entropyClean.replace(/S/g, "\u2660");
 164             entropyHtml = base.parts.join(" ").toUpperCase();
 165             entropyHtml = entropyHtml.replace(/C/g, "<span class='card-suit club'>\u2663</span>");
 166             entropyHtml = entropyHtml.replace(/D/g, "<span class='card-suit diamond'>\u2666</span>");
 167             entropyHtml = entropyHtml.replace(/H/g, "<span class='card-suit heart'>\u2665</span>");
 168             entropyHtml = entropyHtml.replace(/S/g, "<span class='card-suit spade'>\u2660</span>");
 169         }
 170         // Return the result
 171         var e = {
 172             binaryStr: entropyBin,
 173             cleanStr: entropyClean,
 174             cleanHtml: entropyHtml,
 175             base: base,
 176         }
 177         return e;
 178     }
 179
 180     function getBase(str) {
 181         // Need to get the lowest base for the supplied entropy.
 182         // This prevents interpreting, say, dice rolls as hexadecimal.
 183         var binaryMatches = matchers.binary(str);
 184         var hexMatches = matchers.hex(str);
 185         // Find the lowest base that can be used, whilst ignoring any irrelevant chars
 186         if (binaryMatches.length == hexMatches.length && hexMatches.length > 0) {
 187             var ints = binaryMatches.map(function(i) { return parseInt(i, 2) });
 188             return {
 189                 ints: ints,
 190                 parts: binaryMatches,
 191                 matcher: matchers.binary,
 192                 asInt: 2,
 193                 str: "binary",
 194             }
 195         }
 196         var cardMatches = matchers.card(str);
 197         if (cardMatches.length >= hexMatches.length / 2) {
 198             var ints = convertCardsToInts(cardMatches);
 199             return {
 200                 ints: ints,
 201                 parts: cardMatches,
 202                 matcher: matchers.card,
 203                 asInt: 52,
 204                 str: "card",
 205             }
 206         }
 207         var diceMatches = matchers.dice(str);
 208         if (diceMatches.length == hexMatches.length && hexMatches.length > 0) {
 209             var ints = diceMatches.map(function(i) { return parseInt(i) });
 210             return {
 211                 ints: ints,
 212                 parts: diceMatches,
 213                 matcher: matchers.dice,
 214                 asInt: 6,
 215                 str: "dice",
 216             }
 217         }
 218         var base6Matches = matchers.base6(str);
 219         if (base6Matches.length == hexMatches.length && hexMatches.length > 0) {
 220             var ints = base6Matches.map(function(i) { return parseInt(i) });
 221             return {
 222                 ints: ints,
 223                 parts: base6Matches,
 224                 matcher: matchers.base6,
 225                 asInt: 6,
 226                 str: "base 6",
 227             }
 228         }
 229         var base10Matches = matchers.base10(str);
 230         if (base10Matches.length == hexMatches.length && hexMatches.length > 0) {
 231             var ints = base10Matches.map(function(i) { return parseInt(i) });
 232             return {
 233                 ints: ints,
 234                 parts: base10Matches,
 235                 matcher: matchers.base10,
 236                 asInt: 10,
 237                 str: "base 10",
 238             }
 239         }
 240         var ints = hexMatches.map(function(i) { return parseInt(i, 16) });
 241         return {
 242             ints: ints,
 243             parts: hexMatches,
 244             matcher: matchers.hex,
 245             asInt: 16,
 246             str: "hexadecimal",
 247         }
 248     }
 249
 250     // Polyfill for Math.log2
 251     // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
 252     Math.log2 = Math.log2 || function(x) {
 253         // The polyfill isn't good enough because of the poor accuracy of
 254         // Math.LOG2E
 255         // log2(8) gave 2.9999999999999996 which when floored causes issues.
 256         // So instead use the BigInteger library to get it right.
 257         return BigInteger.log(x) / BigInteger.log(2);
 258     };
 259
 260     // Depends on BigInteger
 261     function factorial(n) {
 262         if (n == 0) {
 263             return 1;
 264         }
 265         f = BigInteger.ONE;
 266         for (var i=1; i<=n; i++) {
 267             f = f.multiply(new BigInteger(i));
 268         }
 269         return f;
 270     }
 271
 272 })();