]>
Commit | Line | Data |
---|---|---|
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 | // 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 | |
140 | // as needed. | |
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. | |
146 | var cardCounts = {}; | |
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; | |
159 | } | |
160 | // Get the deck this card is from | |
161 | var deckIndex = cardCounts[card]; | |
162 | while (deckIndex > sortedDecks.length-1) { | |
163 | sortedDecks.push(getSortedDeck()); | |
164 | } | |
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; | |
178 | if (!useBigInt) { | |
179 | minPossibleNewEntropy = Math.round(Math.pow(2, nextTotalBitsLeft)-1); | |
180 | maxPossibleNewEntropy = Math.round(Math.pow(2, totalBitsLeft)-1); | |
181 | diff = maxPossibleNewEntropy - minPossibleNewEntropy; | |
182 | } | |
183 | // Scale the value between possible min and max depending on | |
184 | // this card value | |
185 | var thisCardIndex = deckForCard.indexOf(card); | |
186 | var toAdd = BigInteger.ZERO; | |
187 | if (cardsLeftInDeck > 1) { | |
188 | if (useBigInt) { | |
189 | toAdd = diff.multiply(thisCardIndex) | |
190 | .divide(deckForCard.length - 1) | |
191 | .add(minPossibleNewEntropy); | |
192 | } | |
193 | else { | |
194 | var ratio = thisCardIndex / (deckForCard.length -1); | |
195 | var f = diff * ratio; | |
196 | toAdd = new BigInteger(f).add(minPossibleNewEntropy); | |
197 | } | |
198 | } | |
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; | |
207 | } | |
208 | // Convert to binary | |
209 | var entropyBin = entropyInt.toString(2); | |
210 | var numberOfBitsInt = Math.floor(numberOfBits); | |
211 | while (entropyBin.length < numberOfBitsInt) { | |
212 | entropyBin = "0" + entropyBin; | |
213 | } | |
214 | } | |
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>"); | |
229 | } | |
230 | // Return the result | |
231 | var e = { | |
232 | binaryStr: entropyBin, | |
233 | cleanStr: entropyClean, | |
234 | cleanHtml: entropyHtml, | |
235 | base: base, | |
236 | } | |
237 | return e; | |
238 | } | |
239 | ||
240 | function getSortedDeck() { | |
241 | var s = []; | |
242 | var suits = "CDHS"; | |
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]); | |
247 | } | |
248 | } | |
249 | return s; | |
250 | } | |
251 | ||
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) }); | |
260 | return { | |
261 | ints: ints, | |
262 | parts: binaryMatches, | |
263 | matcher: matchers.binary, | |
264 | asInt: 2, | |
265 | str: "binary", | |
266 | } | |
267 | } | |
268 | var cardMatches = matchers.card(str); | |
269 | if (cardMatches.length >= hexMatches.length / 2) { | |
270 | var ints = convertCardsToInts(cardMatches); | |
271 | return { | |
272 | ints: ints, | |
273 | parts: cardMatches, | |
274 | matcher: matchers.card, | |
275 | asInt: 52, | |
276 | str: "card", | |
277 | } | |
278 | } | |
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) }); | |
282 | return { | |
283 | ints: ints, | |
284 | parts: diceMatches, | |
285 | matcher: matchers.dice, | |
286 | asInt: 6, | |
287 | str: "dice", | |
288 | } | |
289 | } | |
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) }); | |
293 | return { | |
294 | ints: ints, | |
295 | parts: base6Matches, | |
296 | matcher: matchers.base6, | |
297 | asInt: 6, | |
298 | str: "base 6", | |
299 | } | |
300 | } | |
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) }); | |
304 | return { | |
305 | ints: ints, | |
306 | parts: base10Matches, | |
307 | matcher: matchers.base10, | |
308 | asInt: 10, | |
309 | str: "base 10", | |
310 | } | |
311 | } | |
312 | var ints = hexMatches.map(function(i) { return parseInt(i, 16) }); | |
313 | return { | |
314 | ints: ints, | |
315 | parts: hexMatches, | |
316 | matcher: matchers.hex, | |
317 | asInt: 16, | |
318 | str: "hexadecimal", | |
319 | } | |
320 | } | |
321 | ||
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 | |
326 | // Math.LOG2E | |
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); | |
330 | }; | |
331 | ||
332 | // Depends on BigInteger | |
333 | function factorial(n) { | |
334 | if (n == 0) { | |
335 | return 1; | |
336 | } | |
337 | f = BigInteger.ONE; | |
338 | for (var i=1; i<=n; i++) { | |
339 | f = f.multiply(new BigInteger(i)); | |
340 | } | |
341 | return f; | |
342 | } | |
343 | ||
344 | })(); |