X-Git-Url: https://git.immae.eu/?a=blobdiff_plain;f=src%2Fjs%2Fentropy.js;h=a709c782a171855e3f3ba875af1c39ef73890ab4;hb=e5c4aa40984d427444ff21db93d32be85af95f28;hp=f41cf80c6a3bff677d59163d2a7e60401e735b69;hpb=0fdcf2eb538d9092a1abeb181f9a98bc0aa402b3;p=perso%2FImmae%2FProjets%2FCryptomonnaies%2FBIP39.git

diff --git a/src/js/entropy.js b/src/js/entropy.js
index f41cf80..a709c78 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -16,6 +16,8 @@
 
 window.Entropy = new (function() {
 
+    var TWO = new BigInteger(2);
+
     // matchers returns an array of the matched events for each type of entropy.
     // eg
     // matchers.binary("010") returns ["0", "1", "0"]
@@ -118,39 +120,13 @@ window.Entropy = new (function() {
         while (entropyBin.length < expectedBits) {
             entropyBin = "0" + entropyBin;
         }
-        // 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
+        // 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) {
-            // Get the maximum value WITHOUT replacement
-            var totalDecks = Math.ceil(base.parts.length / 52);
-            var totalCards = totalDecks * 52;
-            var totalCombos = factorial(52).pow(totalDecks);
-            var totalRemainingCards = totalCards - base.parts.length;
-            var remainingDecks = Math.floor(totalRemainingCards / 52);
-            var remainingCards = totalRemainingCards % 52;
-            var remainingCombos = factorial(52).pow(remainingDecks).multiply(factorial(remainingCards));
-            var currentCombos = totalCombos.divide(remainingCombos);
-            var numberOfBits = Math.log2(currentCombos);
-            var maxWithoutReplace = BigInteger.pow(2, numberOfBits);
-            // aggresive flooring of numberOfBits by BigInteger.pow means a
-            // more accurate result can be had for small numbers using the
-            // built-in Math.pow function.
-            if (numberOfBits < 32) {
-                maxWithoutReplace = BigInteger(Math.round(Math.pow(2, numberOfBits)));
-            }
-            // Get the maximum value WITH replacement
-            var maxWithReplace = BigInteger.pow(52, base.parts.length);
-            // Calculate the new value by scaling the original value down
-            var withoutReplace = entropyInt.multiply(maxWithoutReplace).divide(maxWithReplace);
-            // Left pad with zeros based on number of bits
-            var entropyBin = withoutReplace.toString(2);
-            var numberOfBitsInt = Math.floor(numberOfBits);
-            while (entropyBin.length < numberOfBitsInt) {
-                entropyBin = "0" + entropyBin;
-            }
+            var cardEntropy = processCardEntropy(base.parts);
+            entropyBin = cardEntropy.binaryStr;
+            bitsPerEvent = cardEntropy.bitsPerEvent;
         }
         // Supply a 'filtered' entropy string for display purposes
         var entropyClean = base.parts.join("");
@@ -172,11 +148,24 @@ window.Entropy = new (function() {
             binaryStr: entropyBin,
             cleanStr: entropyClean,
             cleanHtml: entropyHtml,
+            bitsPerEvent: bitsPerEvent,
             base: base,
         }
         return e;
     }
 
+    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) {
         // Need to get the lowest base for the supplied entropy.
         // This prevents interpreting, say, dice rolls as hexadecimal.
@@ -247,6 +236,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) {