]>
git.immae.eu Git - perso/Immae/Projets/Cryptomonnaies/BIP39.git/blob - src/js/entropy.js
2 * Detects entropy from a string.
10 * card [A2-9TJQK][CDHS]
12 * Automatically uses lowest entropy to avoid issues such as interpretting 0101
13 * as hexadecimal which would be 16 bits when really it's only 4 bits of binary
17 window
.Entropy
= new (function() {
19 var TWO
= new BigInteger(2);
21 // matchers returns an array of the matched events for each type of entropy.
23 // matchers.binary("010") returns ["0", "1", "0"]
24 // matchers.binary("a10") returns ["1", "0"]
25 // matchers.hex("a10") returns ["a", "1", "0"]
27 binary: function(str
) {
28 return str
.match(/[0-1]/gi) || [];
30 base6: function(str
) {
31 return str
.match(/[0-5]/gi) || [];
34 return str
.match(/[1-6]/gi) || []; // ie dice numbers
36 base10: function(str
) {
37 return str
.match(/[0-9]/gi) || [];
40 return str
.match(/[0-9A-F]/gi) || [];
43 // Format is NumberSuit, eg
50 return str
.match(/([A2-9TJQK][CDHS])/gi) || [];
54 // Convert array of cards from ["ac", "4d", "ks"]
55 // to numbers between 0 and 51 [0, 16, 51]
56 function convertCardsToInts(cards
) {
58 var values
= "a23456789tjqk";
60 for (var i
=0; i
<cards
.length
; i
++) {
61 var card
= cards
[i
].toLowerCase();
64 var asInt
= 13 * suits
.indexOf(suit
) + values
.indexOf(value
);
70 this.fromString = function(rawEntropyStr
) {
71 // Find type of entropy being used (binary, hex, dice etc)
72 var base
= getBase(rawEntropyStr
);
73 // Convert dice to base6 entropy (ie 1-6 to 0-5)
74 // This is done by changing all 6s to 0s
75 if (base
.str
== "dice") {
78 for (var i
=0; i
<base
.parts
.length
; i
++) {
79 var c
= base
.parts
[i
];
80 if ("12345".indexOf(c
) > -1) {
81 newParts
[i
] = base
.parts
[i
];
82 newInts
[i
] = base
.ints
[i
];
89 base
.str
= "base 6 (dice)";
91 base
.parts
= newParts
;
92 base
.matcher
= matchers
.base6
;
94 // Detect empty entropy
95 if (base
.parts
.length
== 0) {
103 // Convert base.ints to BigInteger.
104 // Due to using unusual bases, eg cards of base52, this is not as simple as
105 // using BigInteger.parse()
106 var entropyInt
= BigInteger
.ZERO
;
107 for (var i
=base
.ints
.length
-1; i
>=0; i
--) {
108 var thisInt
= BigInteger
.parse(base
.ints
[i
]);
109 var power
= (base
.ints
.length
- 1) - i
;
110 var additionalEntropy
= BigInteger
.parse(base
.asInt
).pow(power
).multiply(thisInt
);
111 entropyInt
= entropyInt
.add(additionalEntropy
);
113 // Convert entropy to binary
114 var entropyBin
= entropyInt
.toString(2);
115 // If the first integer is small, it must be padded with zeros.
116 // Otherwise the chance of the first bit being 1 is 100%, which is
117 // obviously incorrect.
118 // This is not perfect for non-2^n bases.
119 var expectedBits
= Math
.floor(base
.parts
.length
* Math
.log2(base
.asInt
));
120 while (entropyBin
.length
< expectedBits
) {
121 entropyBin
= "0" + entropyBin
;
123 // Assume cards are NOT replaced.
124 // Additional entropy decreases as more cards are used. This means
125 // total possible entropy is measured using n!, not base^n.
126 // eg the second last card can be only one of two, not one of fifty two
127 // so the added entropy for that card is only one bit at most
128 if (base
.asInt
== 52) {
129 var totalDecks
= Math
.ceil(base
.parts
.length
/ 52);
130 var totalCards
= totalDecks
* 52;
131 var totalCombos
= factorial(52).pow(totalDecks
);
132 var totalRemainingCards
= totalCards
- base
.parts
.length
;
133 var remainingDecks
= Math
.floor(totalRemainingCards
/ 52);
134 var remainingCards
= totalRemainingCards
% 52;
135 var remainingCombos
= factorial(52).pow(remainingDecks
).multiply(factorial(remainingCards
));
136 var currentCombos
= totalCombos
.divide(remainingCombos
);
137 var numberOfBits
= Math
.log2(currentCombos
);
138 var maxWithoutReplace
= BigInteger
.pow(2, numberOfBits
);
139 // Use a bunch of sorted decks to measure entropy from, populated
141 var sortedDecks
= [];
142 // Initialize the final entropy value for these cards
143 var entropyInt
= BigInteger
.ZERO
;
144 // Track how many instances of each card have been used, and thus
145 // how many decks are in use.
147 // Track the total bits of entropy that remain, which diminishes as
148 // each card is drawn.
149 var totalBitsLeft
= numberOfBits
;
150 // Work out entropy contribution of each card drawn
151 for (var i
=0; i
<base
.parts
.length
; i
++) {
152 // Get the card that was drawn
153 var cardLower
= base
.parts
[i
];
154 var card
= cardLower
.toUpperCase();
155 // Initialize the deck for this card if needed, to track how
156 // much entropy it adds.
157 if (!(card
in cardCounts
)) {
158 cardCounts
[card
] = 0;
160 // Get the deck this card is from
161 var deckIndex
= cardCounts
[card
];
162 while (deckIndex
> sortedDecks
.length
-1) {
163 sortedDecks
.push(getSortedDeck());
165 // See how many bits this card contributes (depends on how many
166 // are left in the deck it's from)
167 var deckForCard
= sortedDecks
[deckIndex
];
168 var cardsLeftInDeck
= deckForCard
.length
;
169 var additionalBits
= Math
.log2(cardsLeftInDeck
);
170 // Work out the min and max value for this card
171 var nextTotalBitsLeft
= totalBitsLeft
- additionalBits
;
172 var minPossibleNewEntropy
= TWO
.pow(nextTotalBitsLeft
).subtract(1);
173 var maxPossibleNewEntropy
= TWO
.pow(totalBitsLeft
).subtract(1);
174 var diff
= maxPossibleNewEntropy
.subtract(minPossibleNewEntropy
);
175 // BigInteger aggresively floors numbers which greatly affects
176 // the small numbers. In that case, use native Math library
177 var useBigInt
= totalBitsLeft
>= 32;
179 minPossibleNewEntropy
= Math
.round(Math
.pow(2, nextTotalBitsLeft
)-1);
180 maxPossibleNewEntropy
= Math
.round(Math
.pow(2, totalBitsLeft
)-1);
181 diff
= maxPossibleNewEntropy
- minPossibleNewEntropy
;
183 // Scale the value between possible min and max depending on
185 var thisCardIndex
= deckForCard
.indexOf(card
);
186 var toAdd
= BigInteger
.ZERO
;
187 if (cardsLeftInDeck
> 1) {
189 toAdd
= diff
.multiply(thisCardIndex
)
190 .divide(deckForCard
.length
- 1)
191 .add(minPossibleNewEntropy
);
194 var ratio
= thisCardIndex
/ (deckForCard
.length
-1);
195 var f
= diff
* ratio
;
196 toAdd
= new BigInteger(f
).add(minPossibleNewEntropy
);
199 // Add this card entropy to existing entropy
200 entropyInt
= entropyInt
.add(toAdd
);
201 // Remove this card from the deck it comes from
202 deckForCard
.splice(thisCardIndex
,1);
203 // Ensure the next insance of this card uses the next deck
204 cardCounts
[card
] = cardCounts
[card
] + 1;
205 // Next card drawn has less total remaining bits to work with
206 totalBitsLeft
= nextTotalBitsLeft
;
209 var entropyBin
= entropyInt
.toString(2);
210 var numberOfBitsInt
= Math
.floor(numberOfBits
);
211 while (entropyBin
.length
< numberOfBitsInt
) {
212 entropyBin
= "0" + entropyBin
;
215 // Supply a 'filtered' entropy string for display purposes
216 var entropyClean
= base
.parts
.join("");
217 var entropyHtml
= base
.parts
.join("");
218 if (base
.asInt
== 52) {
219 entropyClean
= base
.parts
.join(" ").toUpperCase();
220 entropyClean
= entropyClean
.replace(/C
/g
, "\u2663");
221 entropyClean
= entropyClean
.replace(/D
/g
, "\u2666");
222 entropyClean
= entropyClean
.replace(/H
/g
, "\u2665");
223 entropyClean
= entropyClean
.replace(/S
/g
, "\u2660");
224 entropyHtml
= base
.parts
.join(" ").toUpperCase();
225 entropyHtml
= entropyHtml
.replace(/C
/g
, "<span class='card-suit club'>\u2663</span>");
226 entropyHtml
= entropyHtml
.replace(/D
/g
, "<span class='card-suit diamond'>\u2666</span>");
227 entropyHtml
= entropyHtml
.replace(/H
/g
, "<span class='card-suit heart'>\u2665</span>");
228 entropyHtml
= entropyHtml
.replace(/S
/g
, "<span class='card-suit spade'>\u2660</span>");
232 binaryStr: entropyBin
,
233 cleanStr: entropyClean
,
234 cleanHtml: entropyHtml
,
240 function getSortedDeck() {
243 var values
= "A23456789TJQK";
244 for (var i
=0; i
<suits
.length
; i
++) {
245 for (var j
=0; j
<values
.length
; j
++) {
246 s
.push(values
[j
]+suits
[i
]);
252 function getBase(str
) {
253 // Need to get the lowest base for the supplied entropy.
254 // This prevents interpreting, say, dice rolls as hexadecimal.
255 var binaryMatches
= matchers
.binary(str
);
256 var hexMatches
= matchers
.hex(str
);
257 // Find the lowest base that can be used, whilst ignoring any irrelevant chars
258 if (binaryMatches
.length
== hexMatches
.length
&& hexMatches
.length
> 0) {
259 var ints
= binaryMatches
.map(function(i
) { return parseInt(i
, 2) });
262 parts: binaryMatches
,
263 matcher: matchers
.binary
,
268 var cardMatches
= matchers
.card(str
);
269 if (cardMatches
.length
>= hexMatches
.length
/ 2) {
270 var ints
= convertCardsToInts(cardMatches
);
274 matcher: matchers
.card
,
279 var diceMatches
= matchers
.dice(str
);
280 if (diceMatches
.length
== hexMatches
.length
&& hexMatches
.length
> 0) {
281 var ints
= diceMatches
.map(function(i
) { return parseInt(i
) });
285 matcher: matchers
.dice
,
290 var base6Matches
= matchers
.base6(str
);
291 if (base6Matches
.length
== hexMatches
.length
&& hexMatches
.length
> 0) {
292 var ints
= base6Matches
.map(function(i
) { return parseInt(i
) });
296 matcher: matchers
.base6
,
301 var base10Matches
= matchers
.base10(str
);
302 if (base10Matches
.length
== hexMatches
.length
&& hexMatches
.length
> 0) {
303 var ints
= base10Matches
.map(function(i
) { return parseInt(i
) });
306 parts: base10Matches
,
307 matcher: matchers
.base10
,
312 var ints
= hexMatches
.map(function(i
) { return parseInt(i
, 16) });
316 matcher: matchers
.hex
,
322 // Polyfill for Math.log2
323 // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
324 Math
.log2
= Math
.log2
|| function(x
) {
325 // The polyfill isn't good enough because of the poor accuracy of
327 // log2(8) gave 2.9999999999999996 which when floored causes issues.
328 // So instead use the BigInteger library to get it right.
329 return BigInteger
.log(x
) / BigInteger
.log(2);
332 // Depends on BigInteger
333 function factorial(n
) {
338 for (var i
=1; i
<=n
; i
++) {
339 f
= f
.multiply(new BigInteger(i
));