X-Git-Url: https://git.immae.eu/?p=perso%2FImmae%2FProjets%2FCryptomonnaies%2FBIP39.git;a=blobdiff_plain;f=src%2Fjs%2Fentropy.js;h=62b271125a4939ac8d2249cd9d1508cadf966ae9;hp=c28620adcf115f2961f51b715d5b144a6a42fe0b;hb=22f8766947313324c4acda2de4f170475d3c5ded;hpb=b6dbc2a1aea8eeab2d41a4d44f9d7522ecc59a50

diff --git a/src/js/entropy.js b/src/js/entropy.js
index c28620a..62b2711 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -7,6 +7,7 @@
  * dice 6 [1-6]
  * decimal [0-9]
  * hexadecimal [0-9A-F]
+ * card [A2-9TJQK][CDHS]
  *
  * 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
@@ -15,6 +16,8 @@
 
 window.Entropy = new (function() {
 
+    var TWO = new libs.BigInteger.BigInteger(2);
+
     // matchers returns an array of the matched events for each type of entropy.
     // eg
     // matchers.binary("010") returns ["0", "1", "0"]
@@ -64,9 +67,9 @@ window.Entropy = new (function() {
         return ints;
     }
 
-    this.fromString = function(rawEntropyStr) {
+    this.fromString = function(rawEntropyStr, baseStr) {
         // Find type of entropy being used (binary, hex, dice etc)
-        var base = getBase(rawEntropyStr);
+        var base = getBase(rawEntropyStr, baseStr);
         // Convert dice to base6 entropy (ie 1-6 to 0-5)
         // This is done by changing all 6s to 0s
         if (base.str == "dice") {
@@ -100,11 +103,11 @@ window.Entropy = new (function() {
         // 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;
+        var entropyInt = libs.BigInteger.BigInteger.ZERO;
         for (var i=base.ints.length-1; i>=0; i--) {
-            var thisInt = BigInteger.parse(base.ints[i]);
+            var thisInt = libs.BigInteger.BigInteger.parse(base.ints[i]);
             var power = (base.ints.length - 1) - i;
-            var additionalEntropy = BigInteger.parse(base.asInt).pow(power).multiply(thisInt);
+            var additionalEntropy = libs.BigInteger.BigInteger.parse(base.asInt).pow(power).multiply(thisInt);
             entropyInt = entropyInt.add(additionalEntropy);
         }
         // Convert entropy to binary
@@ -117,6 +120,14 @@ window.Entropy = new (function() {
         while (entropyBin.length < expectedBits) {
             entropyBin = "0" + entropyBin;
         }
+        // Calculate the number of bits per event
+        var bitsPerEvent = Math.log2(base.asInt);
+        // Cards binary must be handled differently, since they're not replaced
+        if (base.asInt == 52) {
+            var cardEntropy = processCardEntropy(base.parts);
+            entropyBin = cardEntropy.binaryStr;
+            bitsPerEvent = cardEntropy.bitsPerEvent;
+        }
         // Supply a 'filtered' entropy string for display purposes
         var entropyClean = base.parts.join("");
         var entropyHtml = base.parts.join("");
@@ -132,22 +143,37 @@ window.Entropy = new (function() {
             entropyHtml = entropyHtml.replace(/H/g, "<span class='card-suit heart'>\u2665</span>");
             entropyHtml = entropyHtml.replace(/S/g, "<span class='card-suit spade'>\u2660</span>");
         }
+        // Return the result
         var e = {
             binaryStr: entropyBin,
             cleanStr: entropyClean,
             cleanHtml: entropyHtml,
+            bitsPerEvent: bitsPerEvent,
             base: base,
         }
         return e;
     }
 
-    function getBase(str) {
+    function getSortedDeck() {
+        var s = [];
+        var suits = "CDHS";
+        var values = "A23456789TJQK";
+        for (var i=0; i<suits.length; i++) {
+            for (var j=0; j<values.length; j++) {
+                s.push(values[j]+suits[i]);
+            }
+        }
+        return s;
+    }
+
+    function getBase(str, baseStr) {
         // Need to get the lowest base for the supplied entropy.
         // This prevents interpreting, say, dice rolls as hexadecimal.
         var binaryMatches = matchers.binary(str);
         var hexMatches = matchers.hex(str);
+        var autodetect = baseStr === undefined;
         // Find the lowest base that can be used, whilst ignoring any irrelevant chars
-        if (binaryMatches.length == hexMatches.length && hexMatches.length > 0) {
+        if ((binaryMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "binary") {
             var ints = binaryMatches.map(function(i) { return parseInt(i, 2) });
             return {
                 ints: ints,
@@ -158,7 +184,7 @@ window.Entropy = new (function() {
             }
         }
         var cardMatches = matchers.card(str);
-        if (cardMatches.length >= hexMatches.length / 2) {
+        if ((cardMatches.length >= hexMatches.length / 2 && autodetect) || baseStr === "card") {
             var ints = convertCardsToInts(cardMatches);
             return {
                 ints: ints,
@@ -169,7 +195,7 @@ window.Entropy = new (function() {
             }
         }
         var diceMatches = matchers.dice(str);
-        if (diceMatches.length == hexMatches.length && hexMatches.length > 0) {
+        if ((diceMatches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "dice") {
             var ints = diceMatches.map(function(i) { return parseInt(i) });
             return {
                 ints: ints,
@@ -180,7 +206,7 @@ window.Entropy = new (function() {
             }
         }
         var base6Matches = matchers.base6(str);
-        if (base6Matches.length == hexMatches.length && hexMatches.length > 0) {
+        if ((base6Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 6") {
             var ints = base6Matches.map(function(i) { return parseInt(i) });
             return {
                 ints: ints,
@@ -191,7 +217,7 @@ window.Entropy = new (function() {
             }
         }
         var base10Matches = matchers.base10(str);
-        if (base10Matches.length == hexMatches.length && hexMatches.length > 0) {
+        if ((base10Matches.length == hexMatches.length && hexMatches.length > 0 && autodetect) || baseStr === "base 10") {
             var ints = base10Matches.map(function(i) { return parseInt(i) });
             return {
                 ints: ints,
@@ -211,6 +237,90 @@ window.Entropy = new (function() {
         }
     }
 
+    // Assume cards are NOT replaced.
+    // Additional entropy decreases as more cards are used. This means
+    // total possible entropy is measured using n!, not base^n.
+    // eg the second last card can be only one of two, not one of fifty two
+    // so the added entropy for that card is only one bit at most
+    function processCardEntropy(cards) {
+        // Track how many instances of each card have been used, and thus
+        // how many decks are in use.
+        var cardCounts = {};
+        var numberOfDecks = 0;
+        // Work out number of decks by max(duplicates)
+        for (var i=0; i<cards.length; i++) {
+            // Get the card that was drawn
+            var cardLower = cards[i];
+            var card = cardLower.toUpperCase();
+            // Initialize the count for this card if needed
+            if (!(card in cardCounts)) {
+                cardCounts[card] = 0;
+            }
+            cardCounts[card] += 1;
+            // See if this is max(duplicates)
+            if (cardCounts[card] > numberOfDecks) {
+                numberOfDecks = cardCounts[card];
+            }
+        }
+        // Work out the total number of bits for this many decks
+        // See http://crypto.stackexchange.com/q/41886
+        var gainedBits = 0;
+        // Equivalent of Math.log2(factorial(52*numberOfDecks))
+        // which becomes infinity for numberOfDecks > 4
+        for (var i=1; i<=52*numberOfDecks; i++) {
+            gainedBits = gainedBits + Math.log2(i);
+        }
+        var lostBits = 52 * Math.log2(factorial(numberOfDecks));
+        var maxBits = gainedBits - lostBits;
+        // Convert the drawn cards to a binary representation.
+        // The exact technique for doing this is unclear.
+        // See
+        // http://crypto.stackexchange.com/a/41896
+        // "I even doubt that this is well defined (only the average entropy
+        // is, I believe)."
+        // See
+        // https://github.com/iancoleman/bip39/issues/33#issuecomment-263021856
+        // "The binary representation can be the first log(permutations,2) bits
+        // of the sha-2 hash of the normalized deck string."
+        //
+        // In this specific implementation, the first N bits of the hash of the
+        // normalized cards string is being used. Uppercase, no spaces; eg
+        // sha256("AH8DQSTC2H")
+        var totalCards = numberOfDecks * 52;
+        var percentUsed = cards.length / totalCards;
+        // Calculate the average number of bits of entropy for the number of
+        // cards drawn.
+        var numberOfBits = Math.floor(maxBits * percentUsed);
+        // Create a normalized string of the selected cards
+        var normalizedCards = cards.join("").toUpperCase();
+        // Convert to binary using the SHA256 hash of the normalized cards.
+        // If the number of bits is more than 256, multiple hashes
+        // are used until the required number of bits is reached.
+        var entropyBin = "";
+        var iterations = 0;
+        while (entropyBin.length < numberOfBits) {
+            var hashedCards = sjcl.hash.sha256.hash(normalizedCards + ":" + iterations);
+            var hashHex = sjcl.codec.hex.fromBits(hashedCards);
+            for (var i=0; i<hashHex.length; i++) {
+                var decimal = parseInt(hashHex[i], 16);
+                var binary = decimal.toString(2);
+                while (binary.length < 4) {
+                    binary = "0" + binary;
+                }
+                entropyBin = entropyBin + binary;
+            }
+            iterations = iterations + 1;
+        }
+        // Truncate to the appropriate number of bits.
+        entropyBin = entropyBin.substring(0, numberOfBits);
+        // Get the number of bits per event
+        bitsPerEvent = maxBits / totalCards;
+        return {
+            binaryStr: entropyBin,
+            bitsPerEvent: bitsPerEvent,
+        }
+    }
+
     // 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) {
@@ -218,7 +328,19 @@ window.Entropy = new (function() {
         // 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);
+        return libs.BigInteger.BigInteger.log(x) / libs.BigInteger.BigInteger.log(2);
     };
 
+    // Depends on BigInteger
+    function factorial(n) {
+        if (n == 0) {
+            return 1;
+        }
+        f = libs.BigInteger.BigInteger.ONE;
+        for (var i=1; i<=n; i++) {
+            f = f.multiply(new libs.BigInteger.BigInteger(i));
+        }
+        return f;
+    }
+
 })();