Entropy library assumes cards are discarded

and removed the duplicate logic from the UI logic.

3 files changed, 81 insertions, 67 deletions

diff --git a/src/js/entropy.js b/src/js/entropy.js
index c28620a..5900346 100644
--- a/src/js/entropy.js
+++ b/src/js/entropy.js
@@ -117,6 +117,40 @@ 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
+        // 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
+        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;
+            }
+        }
         // Supply a 'filtered' entropy string for display purposes
         var entropyClean = base.parts.join("");
         var entropyHtml = base.parts.join("");
@@ -221,4 +255,16 @@ window.Entropy = new (function() {
         return BigInteger.log(x) / BigInteger.log(2);
     };
 
+    // Depends on BigInteger
+    function factorial(n) {
+        if (n == 0) {
+            return 1;
+        }
+        f = BigInteger.ONE;
+        for (var i=1; i<=n; i++) {
+            f = f.multiply(new BigInteger(i));
+        }
+        return f;
+    }
+
 })();
diff --git a/src/js/index.js b/src/js/index.js
index f4163ee..254b62f 100644
--- a/src/js/index.js
+++ b/src/js/index.js
@@ -791,20 +791,21 @@
     }
 
     function showEntropyFeedback(entropy) {
+        var numberOfBits = entropy.binaryStr.length;
         var strength = "extremely weak";
-        if (entropy.binaryStr.length >= 64) {
+        if (numberOfBits >= 64) {
             strength = "very weak";
         }
-        if (entropy.binaryStr.length >= 96) {
+        if (numberOfBits >= 96) {
             strength = "weak";
         }
-        if (entropy.binaryStr.length >= 128) {
+        if (numberOfBits >= 128) {
             strength = "strong";
         }
-        if (entropy.binaryStr.length >= 160) {
+        if (numberOfBits >= 160) {
             strength = "very strong";
         }
-        if (entropy.binaryStr.length >= 192) {
+        if (numberOfBits >= 192) {
             strength = "extremely strong";
         }
         // If time to crack is less than one day, and password is considered
@@ -825,38 +826,17 @@
             console.log("Error detecting entropy strength with zxcvbn:");
             console.log(e);
         }
-        var bitsStr = getNumberOfEntropyBits(entropy);
-        var wordCount = Math.floor(entropy.binaryStr.length / 32) * 3;
         var entropyTypeStr = getEntropyTypeStr(entropy);
+        var wordCount = Math.floor(numberOfBits / 32) * 3;
+        var bitsPerEvent = Math.log2(entropy.base.asInt).toFixed(2);
         DOM.entropyFiltered.html(entropy.cleanHtml);
         DOM.entropyType.text(entropyTypeStr);
         DOM.entropyStrength.text(strength);
         DOM.entropyEventCount.text(entropy.base.ints.length);
-        DOM.entropyBits.text(bitsStr);
+        DOM.entropyBits.text(numberOfBits);
         DOM.entropyWordCount.text(wordCount);
         DOM.entropyBinary.text(entropy.binaryStr);
-        DOM.entropyBitsPerEvent.text(Math.log2(entropy.base.asInt).toFixed(2));
-    }
-
-    function getNumberOfEntropyBits(entropy) {
-        var bitsStr = entropy.binaryStr.length.toString();
-        // If using cards, assume they are not reused, thus additional entropy
-        // decreases as more cards are used. This means 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
-        if (entropy.base.asInt == 52) {
-            var totalDecks = Math.ceil(entropy.base.parts.length / 52);
-            var totalCards = totalDecks * 52;
-            var totalCombos = factorial(52).pow(totalDecks);
-            var totalRemainingCards = totalCards - entropy.base.parts.length;
-            var remainingDecks = Math.floor(totalRemainingCards / 52);
-            var remainingCards = totalRemainingCards % 52;
-            var remainingCombos = factorial(52).pow(remainingDecks) * factorial(remainingCards);
-            var currentCombos = totalCombos.divide(remainingCombos);
-            bitsStr = currentCombos.toString(2).length.toString();
-        }
-        return bitsStr
+        DOM.entropyBitsPerEvent.text(bitsPerEvent);
     }
 
     function getEntropyTypeStr(entropy) {
@@ -922,18 +902,6 @@
         return typeStr;
     }
 
-    // Depends on BigInteger
-    function factorial(n) {
-        if (n == 0) {
-            return 1;
-        }
-        f = BigInteger.ONE;
-        for (var i=1; i<=n; i++) {
-            f = f.multiply(new BigInteger(i));
-        }
-        return f;
-    }
-
     var networks = [
         {
             name: "Bitcoin",
diff --git a/tests.js b/tests.js
index 13f2c76..03ce9e1 100644
--- a/tests.js
+++ b/tests.js
@@ -2185,10 +2185,9 @@ page.open(url, function(status) {
         try {
             var cards = [
                 [ "ac", "00000" ],
-                [ "acac", "00000000000" ],
-                [ "acac2c", "00000000000000001" ],
-                [ "acks", "00000110011" ],
-                [ "acacks", "00000000000110011" ],
+                [ "acqs", "00000110001" ],
+                [ "acks", "00000110010" ],
+                [ "2cac", "00000110011" ],
                 [ "2c", "00001" ],
                 [ "3d", "01111" ],
                 [ "4h", "11101" ],
@@ -2201,8 +2200,8 @@ page.open(url, function(status) {
                 [ "jd", "10111" ],
                 [ "qh", "100101" ],
                 [ "ks", "110011" ],
-                [ "ks2c", "101001011101" ],
-                [ "KS2C", "101001011101" ],
+                [ "ks2c", "101000101001" ],
+                [ "KS2C", "101000101001" ],
             ];
             for (var i=0; i<cards.length; i++) {
                 var card = cards[i][0];
@@ -2503,7 +2502,7 @@ page.open(url, function(status) {
         [ "222F", "16" ],
         [ "FFFF", "16" ],
         [ "0000101017", "33" ], // 10 events at 3.32 bits per event
-        [ "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks", "226" ], // cards are not replaced, so a full deck is not 52^52 entropy which is 296 bits, it's 52!, which is 226 bits
+        [ "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks", "225" ], // cards are not replaced, so a full deck is not 52^52 entropy which is 296 bits, it's 52!, which is 225 bits
     ]
     // use entropy
     page.evaluate(function(e) {
@@ -2636,41 +2635,42 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (full deck)",
             events: 52,
-            bits: 226,
-            words: 27,
+            bits: 225,
+            words: 21,
             strength: "extremely strong",
         },
         {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks3d",
             type: "card (full deck, 1 duplicate: 3d)",
             events: 53,
-            bits: 232,
-            words: 27,
+            bits: 231,
+            words: 21,
             strength: "extremely strong",
         },
         {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqs3d4d",
             type: "card (2 duplicates: 3d 4d, 1 missing: KS)",
             events: 53,
-            bits: 232,
-            words: 27,
+            bits: 231,
+            words: 21,
             strength: "extremely strong",
         },
         {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqs3d4d5d6d",
             type: "card (4 duplicates: 3d 4d 5d..., 1 missing: KS)",
             events: 53,
-            bits: 243,
-            words: 27,
+            bits: 242,
+            words: 21,
             strength: "extremely strong",
         },
         // Next test was throwing uncaught error in zxcvbn
+        // Also tests 451 bits, ie Math.log2(52!)*2 = 225.58 * 2
         {
             entropy: "ac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsksac2c3c4c5c6c7c8c9ctcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (full deck, 52 duplicates: ac 2c 3c...)",
             events: 104,
-            bits: 452,
-            words: 54,
+            bits: 451,
+            words: 42,
             strength: "extremely strong",
         },
         // Case insensitivity to duplicate cards
@@ -2695,24 +2695,24 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c  tcjcqckcad2d3d4d5d6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (1 missing: 9C)",
             events: 51,
-            bits: 226,
-            words: 27,
+            bits: 225,
+            words: 21,
             strength: "extremely strong",
         },
         {
             entropy: "ac2c3c4c5c6c7c8c  tcjcqckcad2d3d4d  6d7d8d9dtdjdqdkdah2h3h4h5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (2 missing: 9C 5D)",
             events: 50,
-            bits: 225,
-            words: 24,
+            bits: 224,
+            words: 21,
             strength: "extremely strong",
         },
         {
             entropy: "ac2c3c4c5c6c7c8c  tcjcqckcad2d3d4d  6d7d8d9dtdjd  kdah2h3h  5h6h7h8h9hthjhqhkhas2s3s4s5s6s7s8s9stsjsqsks",
             type: "card (4 missing: 9C 5D QD...)",
             events: 48,
-            bits: 221,
-            words: 24,
+            bits: 220,
+            words: 18,
             strength: "extremely strong",
         },
         // More than six missing cards does not show message
@@ -2720,8 +2720,8 @@ page.open(url, function(status) {
             entropy: "ac2c3c4c5c6c7c8c  tcjcqckcad2d3d4d  6d  8d9d  jd  kdah2h3h  5h6h7h8h9hthjhqhkh  2s3s4s5s6s7s8s9stsjsqsks",
             type: "card",
             events: 45,
-            bits: 214,
-            words: 24,
+            bits: 213,
+            words: 18,
             strength: "extremely strong",
         },
     ];