X-Git-Url: https://git.immae.eu/?a=blobdiff_plain;f=src%2Fjs%2Fentropy.js;h=92300afa352f27b48a1f600705fe5e04fe1383bc;hb=adc8ce127d4f8ea0d7e5ede6a82c2791d60ff4d2;hp=1e556ce2343b8d52dc761a4ce8458602f6bd217b;hpb=c6624d51f4e5607202e48903352574c47571baab;p=perso%2FImmae%2FProjets%2FCryptomonnaies%2FBIP39.git

diff --git a/src/js/entropy.js b/src/js/entropy.js
index 1e556ce..92300af 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -1,11 +1,67 @@
+/*
+ * Detects entropy from a string.
+ *
+ * Formats include:
+ * binary [0-1]
+ * base 6 [0-5]
+ * dice 6 [1-6]
+ * decimal [0-9]
+ * hexadecimal [0-9A-F]
+ *
+ * Automatically uses lowest entropy to avoid issues such as interpretting 0101
+ * as hexadecimal which would be 16 bits when really it's only 4 bits of binary
+ * entropy.
+ */
+
 window.Entropy = new (function() {
 
+    // matchers returns an array of the matched events for each type of entropy.
+    // eg
+    // matchers.binary("010") returns ["0", "1", "0"]
+    // matchers.binary("a10") returns ["1", "0"]
+    // matchers.hex("a10") returns ["a", "1", "0"]
     var matchers = {
-        binary: /[0-1]/gi,
-        base6: /[0-5]/gi,
-        dice: /[1-6]/gi, // ie dice numbers
-        base10: /[0-9]/gi,
-        hex: /[0-9A-F]/gi,
+        binary: function(str) {
+            return str.match(/[0-1]/gi) || [];
+        },
+        base6: function(str) {
+            return str.match(/[0-5]/gi) || [];
+        },
+        dice: function(str) {
+            return str.match(/[1-6]/gi) || []; // ie dice numbers
+        },
+        base10: function(str) {
+            return str.match(/[0-9]/gi) || [];
+        },
+        hex: function(str) {
+            return str.match(/[0-9A-F]/gi) || [];
+        },
+        card: function(str) {
+            // Format is NumberSuit, eg
+            // AH ace of hearts
+            // 8C eight of clubs
+            // TD ten of diamonds
+            // JS jack of spades
+            // QH queen of hearts
+            // KC king of clubs
+            return str.match(/([A2-9TJQK][CDHS])/gi) || [];
+        }
+    }
+
+    // Convert array of cards from ["ac", "4d", "ks"]
+    // to numbers between 0 and 51 [0, 16, 51]
+    function convertCardsToInts(cards) {
+        var ints = [];
+        var values = "a23456789tjqk";
+        var suits = "cdhs";
+        for (var i=0; i<cards.length; i++) {
+            var card = cards[i].toLowerCase();
+            var value = card[0];
+            var suit = card[1];
+            var asInt = 13 * suits.indexOf(suit) + values.indexOf(value);
+            ints.push(asInt);
+        }
+        return ints;
     }
 
     this.fromString = function(rawEntropyStr) {
@@ -25,69 +81,68 @@ window.Entropy = new (function() {
             }
             rawEntropyStr = newRawEntropyStr;
             base.str = "base 6 (dice)";
+            base.parts = matchers.base6(rawEntropyStr);
             base.matcher = matchers.base6;
         }
-        var entropyParts = rawEntropyStr.match(base.matcher) || [];
-        var entropyStr = entropyParts.join("");
         // Detect empty entropy
-        if (entropyStr.length == 0) {
+        if (base.parts.length == 0) {
             return {
                 binaryStr: "",
-                hexStr: "",
                 cleanStr: "",
                 base: base,
             };
         }
         // Pull leading zeros off
-        var leadingZeros = "";
-        while (entropyStr[0] == "0") {
-            leadingZeros += "0";
-            entropyStr = entropyStr.substring(1);
+        var leadingZeros = [];
+        while (base.ints[0] == "0") {
+            leadingZeros.push("0");
+            base.ints.shift();
         }
         // Convert leading zeros to binary equivalent
-        var numBinLeadingZeros = Math.ceil(Math.log2(base.asInt) * leadingZeros.length);
+        var numBinLeadingZeros = Math.floor(Math.log2(base.asInt) * leadingZeros.length);
         var binLeadingZeros = "";
         for (var i=0; i<numBinLeadingZeros; i++) {
             binLeadingZeros += "0";
         }
-        // Convert leading zeros to hex equivalent
-        var numHexLeadingZeros = Math.floor(numBinLeadingZeros / 4);
-        var hexLeadingZeros = "";
-        for (var i=0; i<numHexLeadingZeros; i++) {
-            hexLeadingZeros += "0";
-        }
         // Handle entropy of zero
-        if (entropyStr == "") {
+        if (base.ints.length == 0) {
             return {
                 binaryStr: binLeadingZeros,
-                hexStr: hexLeadingZeros || "0",
                 cleanStr: leadingZeros,
                 base: base,
             }
         }
-        // If using hex, should always be multiples of 4 bits, which can get
-        // out of sync if first number has leading 0 bits, eg 2 in hex is 0010
-        // which would show up as 10, thus missing 2 bits it should have.
-        if (base.asInt == 16) {
-            var firstDigit = parseInt(entropyStr[0], 16);
-            if (firstDigit >= 4 && firstDigit < 8) {
-                binLeadingZeros += "0";
-            }
-            else if (firstDigit >= 2 && firstDigit < 4) {
-                binLeadingZeros += "00";
-            }
-            else if (firstDigit >= 1 && firstDigit < 2) {
-                binLeadingZeros += "000";
-            }
+        // If the first integer is small, it must be padded with zeros.
+        // Otherwise the chance of the first bit being 1 is 100%, which is
+        // obviously incorrect.
+        // This is not perfect for unusual bases, eg base 6 has 2.6 bits, so is
+        // slightly biased toward having leading zeros, but it's still better
+        // than ignoring it completely.
+        // TODO: revise this, it seems very fishy. For example, in base 10, there are
+        // 8 opportunities to start with 0 but only 2 to start with 1
+        var firstInt = base.ints[0];
+        var firstIntBits = Math.floor(Math.log2(firstInt))+1;
+        var maxFirstIntBits = Math.floor(Math.log2(base.asInt-1))+1;
+        var missingFirstIntBits = maxFirstIntBits - firstIntBits;
+        var firstIntLeadingZeros = "";
+        for (var i=0; i<missingFirstIntBits; i++) {
+            binLeadingZeros += "0";
+        }
+        // Convert base.ints to BigInteger.
+        // Due to using unusual bases, eg cards of base52, this is not as simple as
+        // using BigInteger.parse()
+        var entropyInt = BigInteger.ZERO;
+        for (var i=base.ints.length-1; i>=0; i--) {
+            var thisInt = BigInteger.parse(base.ints[i]);
+            var power = (base.ints.length - 1) - i;
+            var additionalEntropy = BigInteger.parse(base.asInt).pow(power).multiply(thisInt);
+            entropyInt = entropyInt.add(additionalEntropy);
         }
-        // Convert entropy to different foramts
-        var entropyInt = BigInteger.parse(entropyStr, base.asInt);
+        // Convert entropy to different formats
         var entropyBin = binLeadingZeros + entropyInt.toString(2);
-        var entropyHex = hexLeadingZeros + entropyInt.toString(16);
-        var entropyClean = leadingZeros + entropyStr;
+        var entropyClean = base.parts.join("");
         var e = {
             binaryStr: entropyBin,
-            hexStr: entropyHex,
             cleanStr: entropyClean,
             base: base,
         }
@@ -97,41 +152,67 @@ window.Entropy = new (function() {
     function getBase(str) {
         // Need to get the lowest base for the supplied entropy.
         // This prevents interpreting, say, dice rolls as hexadecimal.
-        var binaryMatches = str.match(matchers.binary) || [];
-        var base6Matches = str.match(matchers.base6) || [];
-        var diceMatches = str.match(matchers.dice) || [];
-        var base10Matches = str.match(matchers.base10) || [];
-        var hexMatches = str.match(matchers.hex) || [];
+        var binaryMatches = matchers.binary(str);
+        var hexMatches = matchers.hex(str);
         // Find the lowest base that can be used, whilst ignoring any irrelevant chars
-        if (binaryMatches.length == hexMatches.length) {
+        if (binaryMatches.length == hexMatches.length && hexMatches.length > 0) {
+            var ints = binaryMatches.map(function(i) { return parseInt(i, 2) });
             return {
+                ints: ints,
+                parts: binaryMatches,
                 matcher: matchers.binary,
                 asInt: 2,
                 str: "binary",
             }
         }
-        if (diceMatches.length == hexMatches.length) {
+        var cardMatches = matchers.card(str);
+        if (cardMatches.length >= hexMatches.length / 2) {
+            var ints = convertCardsToInts(cardMatches);
+            return {
+                ints: ints,
+                parts: cardMatches,
+                matcher: matchers.card,
+                asInt: 52,
+                str: "card",
+            }
+        }
+        var diceMatches = matchers.dice(str);
+        if (diceMatches.length == hexMatches.length && hexMatches.length > 0) {
+            var ints = diceMatches.map(function(i) { return parseInt(i) });
             return {
+                ints: ints,
+                parts: diceMatches,
                 matcher: matchers.dice,
                 asInt: 6,
                 str: "dice",
             }
         }
-        if (base6Matches.length == hexMatches.length) {
+        var base6Matches = matchers.base6(str);
+        if (base6Matches.length == hexMatches.length && hexMatches.length > 0) {
+            var ints = base6Matches.map(function(i) { return parseInt(i) });
             return {
+                ints: ints,
+                parts: base6Matches,
                 matcher: matchers.base6,
                 asInt: 6,
                 str: "base 6",
             }
         }
-        if (base10Matches.length == hexMatches.length) {
+        var base10Matches = matchers.base10(str);
+        if (base10Matches.length == hexMatches.length && hexMatches.length > 0) {
+            var ints = base10Matches.map(function(i) { return parseInt(i) });
             return {
+                ints: ints,
+                parts: base10Matches,
                 matcher: matchers.base10,
                 asInt: 10,
                 str: "base 10",
             }
         }
+        var ints = hexMatches.map(function(i) { return parseInt(i, 16) });
         return {
+            ints: ints,
+            parts: hexMatches,
             matcher: matchers.hex,
             asInt: 16,
             str: "hexadecimal",
@@ -141,7 +222,11 @@ window.Entropy = new (function() {
     // Polyfill for Math.log2
     // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
     Math.log2 = Math.log2 || function(x) {
-        return Math.log(x) * Math.LOG2E;
+        // The polyfill isn't good enough because of the poor accuracy of
+        // Math.LOG2E
+        // log2(8) gave 2.9999999999999996 which when floored causes issues.
+        // So instead use the BigInteger library to get it right.
+        return BigInteger.log(x) / BigInteger.log(2);
     };
 
 })();