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

diff --git a/src/js/entropy.js b/src/js/entropy.js
index c28620a..a709c78 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 BigInteger(2);
+
     // matchers returns an array of the matched events for each type of entropy.
     // eg
     // matchers.binary("010") returns ["0", "1", "0"]
@@ -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,15 +143,29 @@ 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 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.
@@ -211,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) {
@@ -221,4 +330,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;
+    }
+
 })();