]> git.immae.eu Git - perso/Immae/Projets/Cryptomonnaies/BIP39.git/blob - src/js/entropy.js
Merge pull request #287 from sui77/master
[perso/Immae/Projets/Cryptomonnaies/BIP39.git] / src / js / entropy.js
1 /*
2 * Detects entropy from a string.
3 *
4 * Formats include:
5 * binary [0-1]
6 * base 6 [0-5]
7 * dice 6 [1-6]
8 * decimal [0-9]
9 * hexadecimal [0-9A-F]
10 * card [A2-9TJQK][CDHS]
11 *
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
14 * entropy.
15 */
16
17 window.Entropy = new (function() {
18
19 var TWO = new BigInteger(2);
20
21 // matchers returns an array of the matched events for each type of entropy.
22 // eg
23 // matchers.binary("010") returns ["0", "1", "0"]
24 // matchers.binary("a10") returns ["1", "0"]
25 // matchers.hex("a10") returns ["a", "1", "0"]
26 var matchers = {
27 binary: function(str) {
28 return str.match(/[0-1]/gi) || [];
29 },
30 base6: function(str) {
31 return str.match(/[0-5]/gi) || [];
32 },
33 dice: function(str) {
34 return str.match(/[1-6]/gi) || []; // ie dice numbers
35 },
36 base10: function(str) {
37 return str.match(/[0-9]/gi) || [];
38 },
39 hex: function(str) {
40 return str.match(/[0-9A-F]/gi) || [];
41 },
42 card: function(str) {
43 // Format is NumberSuit, eg
44 // AH ace of hearts
45 // 8C eight of clubs
46 // TD ten of diamonds
47 // JS jack of spades
48 // QH queen of hearts
49 // KC king of clubs
50 return str.match(/([A2-9TJQK][CDHS])/gi) || [];
51 }
52 }
53
54 // Convert array of cards from ["ac", "4d", "ks"]
55 // to numbers between 0 and 51 [0, 16, 51]
56 function convertCardsToInts(cards) {
57 var ints = [];
58 var values = "a23456789tjqk";
59 var suits = "cdhs";
60 for (var i=0; i<cards.length; i++) {
61 var card = cards[i].toLowerCase();
62 var value = card[0];
63 var suit = card[1];
64 var asInt = 13 * suits.indexOf(suit) + values.indexOf(value);
65 ints.push(asInt);
66 }
67 return ints;
68 }
69
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") {
76 var newParts = [];
77 var newInts = [];
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];
83 }
84 else {
85 newParts[i] = "0";
86 newInts[i] = 0;
87 }
88 }
89 base.str = "base 6 (dice)";
90 base.ints = newInts;
91 base.parts = newParts;
92 base.matcher = matchers.base6;
93 }
94 // Detect empty entropy
95 if (base.parts.length == 0) {
96 return {
97 binaryStr: "",
98 cleanStr: "",
99 cleanHtml: "",
100 base: base,
101 };
102 }
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);
112 }
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;
122 }
123 // Calculate the number of bits per event
124 var bitsPerEvent = Math.log2(base.asInt);
125 // Cards binary must be handled differently, since they're not replaced
126 if (base.asInt == 52) {
127 var cardEntropy = processCardEntropy(base.parts);
128 entropyBin = cardEntropy.binaryStr;
129 bitsPerEvent = cardEntropy.bitsPerEvent;
130 }
131 // Supply a 'filtered' entropy string for display purposes
132 var entropyClean = base.parts.join("");
133 var entropyHtml = base.parts.join("");
134 if (base.asInt == 52) {
135 entropyClean = base.parts.join(" ").toUpperCase();
136 entropyClean = entropyClean.replace(/C/g, "\u2663");
137 entropyClean = entropyClean.replace(/D/g, "\u2666");
138 entropyClean = entropyClean.replace(/H/g, "\u2665");
139 entropyClean = entropyClean.replace(/S/g, "\u2660");
140 entropyHtml = base.parts.join(" ").toUpperCase();
141 entropyHtml = entropyHtml.replace(/C/g, "<span class='card-suit club'>\u2663</span>");
142 entropyHtml = entropyHtml.replace(/D/g, "<span class='card-suit diamond'>\u2666</span>");
143 entropyHtml = entropyHtml.replace(/H/g, "<span class='card-suit heart'>\u2665</span>");
144 entropyHtml = entropyHtml.replace(/S/g, "<span class='card-suit spade'>\u2660</span>");
145 }
146 // Return the result
147 var e = {
148 binaryStr: entropyBin,
149 cleanStr: entropyClean,
150 cleanHtml: entropyHtml,
151 bitsPerEvent: bitsPerEvent,
152 base: base,
153 }
154 return e;
155 }
156
157 function getSortedDeck() {
158 var s = [];
159 var suits = "CDHS";
160 var values = "A23456789TJQK";
161 for (var i=0; i<suits.length; i++) {
162 for (var j=0; j<values.length; j++) {
163 s.push(values[j]+suits[i]);
164 }
165 }
166 return s;
167 }
168
169 function getBase(str) {
170 // Need to get the lowest base for the supplied entropy.
171 // This prevents interpreting, say, dice rolls as hexadecimal.
172 var binaryMatches = matchers.binary(str);
173 var hexMatches = matchers.hex(str);
174 // Find the lowest base that can be used, whilst ignoring any irrelevant chars
175 if (binaryMatches.length == hexMatches.length && hexMatches.length > 0) {
176 var ints = binaryMatches.map(function(i) { return parseInt(i, 2) });
177 return {
178 ints: ints,
179 parts: binaryMatches,
180 matcher: matchers.binary,
181 asInt: 2,
182 str: "binary",
183 }
184 }
185 var cardMatches = matchers.card(str);
186 if (cardMatches.length >= hexMatches.length / 2) {
187 var ints = convertCardsToInts(cardMatches);
188 return {
189 ints: ints,
190 parts: cardMatches,
191 matcher: matchers.card,
192 asInt: 52,
193 str: "card",
194 }
195 }
196 var diceMatches = matchers.dice(str);
197 if (diceMatches.length == hexMatches.length && hexMatches.length > 0) {
198 var ints = diceMatches.map(function(i) { return parseInt(i) });
199 return {
200 ints: ints,
201 parts: diceMatches,
202 matcher: matchers.dice,
203 asInt: 6,
204 str: "dice",
205 }
206 }
207 var base6Matches = matchers.base6(str);
208 if (base6Matches.length == hexMatches.length && hexMatches.length > 0) {
209 var ints = base6Matches.map(function(i) { return parseInt(i) });
210 return {
211 ints: ints,
212 parts: base6Matches,
213 matcher: matchers.base6,
214 asInt: 6,
215 str: "base 6",
216 }
217 }
218 var base10Matches = matchers.base10(str);
219 if (base10Matches.length == hexMatches.length && hexMatches.length > 0) {
220 var ints = base10Matches.map(function(i) { return parseInt(i) });
221 return {
222 ints: ints,
223 parts: base10Matches,
224 matcher: matchers.base10,
225 asInt: 10,
226 str: "base 10",
227 }
228 }
229 var ints = hexMatches.map(function(i) { return parseInt(i, 16) });
230 return {
231 ints: ints,
232 parts: hexMatches,
233 matcher: matchers.hex,
234 asInt: 16,
235 str: "hexadecimal",
236 }
237 }
238
239 // Assume cards are NOT replaced.
240 // Additional entropy decreases as more cards are used. This means
241 // total possible entropy is measured using n!, not base^n.
242 // eg the second last card can be only one of two, not one of fifty two
243 // so the added entropy for that card is only one bit at most
244 function processCardEntropy(cards) {
245 // Track how many instances of each card have been used, and thus
246 // how many decks are in use.
247 var cardCounts = {};
248 var numberOfDecks = 0;
249 // Work out number of decks by max(duplicates)
250 for (var i=0; i<cards.length; i++) {
251 // Get the card that was drawn
252 var cardLower = cards[i];
253 var card = cardLower.toUpperCase();
254 // Initialize the count for this card if needed
255 if (!(card in cardCounts)) {
256 cardCounts[card] = 0;
257 }
258 cardCounts[card] += 1;
259 // See if this is max(duplicates)
260 if (cardCounts[card] > numberOfDecks) {
261 numberOfDecks = cardCounts[card];
262 }
263 }
264 // Work out the total number of bits for this many decks
265 // See http://crypto.stackexchange.com/q/41886
266 var gainedBits = 0;
267 // Equivalent of Math.log2(factorial(52*numberOfDecks))
268 // which becomes infinity for numberOfDecks > 4
269 for (var i=1; i<=52*numberOfDecks; i++) {
270 gainedBits = gainedBits + Math.log2(i);
271 }
272 var lostBits = 52 * Math.log2(factorial(numberOfDecks));
273 var maxBits = gainedBits - lostBits;
274 // Convert the drawn cards to a binary representation.
275 // The exact technique for doing this is unclear.
276 // See
277 // http://crypto.stackexchange.com/a/41896
278 // "I even doubt that this is well defined (only the average entropy
279 // is, I believe)."
280 // See
281 // https://github.com/iancoleman/bip39/issues/33#issuecomment-263021856
282 // "The binary representation can be the first log(permutations,2) bits
283 // of the sha-2 hash of the normalized deck string."
284 //
285 // In this specific implementation, the first N bits of the hash of the
286 // normalized cards string is being used. Uppercase, no spaces; eg
287 // sha256("AH8DQSTC2H")
288 var totalCards = numberOfDecks * 52;
289 var percentUsed = cards.length / totalCards;
290 // Calculate the average number of bits of entropy for the number of
291 // cards drawn.
292 var numberOfBits = Math.floor(maxBits * percentUsed);
293 // Create a normalized string of the selected cards
294 var normalizedCards = cards.join("").toUpperCase();
295 // Convert to binary using the SHA256 hash of the normalized cards.
296 // If the number of bits is more than 256, multiple hashes
297 // are used until the required number of bits is reached.
298 var entropyBin = "";
299 var iterations = 0;
300 while (entropyBin.length < numberOfBits) {
301 var hashedCards = sjcl.hash.sha256.hash(normalizedCards + ":" + iterations);
302 var hashHex = sjcl.codec.hex.fromBits(hashedCards);
303 for (var i=0; i<hashHex.length; i++) {
304 var decimal = parseInt(hashHex[i], 16);
305 var binary = decimal.toString(2);
306 while (binary.length < 4) {
307 binary = "0" + binary;
308 }
309 entropyBin = entropyBin + binary;
310 }
311 iterations = iterations + 1;
312 }
313 // Truncate to the appropriate number of bits.
314 entropyBin = entropyBin.substring(0, numberOfBits);
315 // Get the number of bits per event
316 bitsPerEvent = maxBits / totalCards;
317 return {
318 binaryStr: entropyBin,
319 bitsPerEvent: bitsPerEvent,
320 }
321 }
322
323 // Polyfill for Math.log2
324 // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill
325 Math.log2 = Math.log2 || function(x) {
326 // The polyfill isn't good enough because of the poor accuracy of
327 // Math.LOG2E
328 // log2(8) gave 2.9999999999999996 which when floored causes issues.
329 // So instead use the BigInteger library to get it right.
330 return BigInteger.log(x) / BigInteger.log(2);
331 };
332
333 // Depends on BigInteger
334 function factorial(n) {
335 if (n == 0) {
336 return 1;
337 }
338 f = BigInteger.ONE;
339 for (var i=1; i<=n; i++) {
340 f = f.multiply(new BigInteger(i));
341 }
342 return f;
343 }
344
345 })();