]>
Commit | Line | Data |
---|---|---|
6606c50f IC |
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] | |
0fdcf2eb | 10 | * card [A2-9TJQK][CDHS] |
6606c50f IC |
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 | ||
c6624d51 IC |
17 | window.Entropy = new (function() { |
18 | ||
6606c50f IC |
19 | // matchers returns an array of the matched events for each type of entropy. |
20 | // eg | |
21 | // matchers.binary("010") returns ["0", "1", "0"] | |
22 | // matchers.binary("a10") returns ["1", "0"] | |
23 | // matchers.hex("a10") returns ["a", "1", "0"] | |
c6624d51 | 24 | var matchers = { |
6606c50f IC |
25 | binary: function(str) { |
26 | return str.match(/[0-1]/gi) || []; | |
27 | }, | |
28 | base6: function(str) { | |
29 | return str.match(/[0-5]/gi) || []; | |
30 | }, | |
31 | dice: function(str) { | |
32 | return str.match(/[1-6]/gi) || []; // ie dice numbers | |
33 | }, | |
34 | base10: function(str) { | |
35 | return str.match(/[0-9]/gi) || []; | |
36 | }, | |
37 | hex: function(str) { | |
38 | return str.match(/[0-9A-F]/gi) || []; | |
39 | }, | |
adc8ce12 IC |
40 | card: function(str) { |
41 | // Format is NumberSuit, eg | |
42 | // AH ace of hearts | |
43 | // 8C eight of clubs | |
44 | // TD ten of diamonds | |
45 | // JS jack of spades | |
46 | // QH queen of hearts | |
47 | // KC king of clubs | |
48 | return str.match(/([A2-9TJQK][CDHS])/gi) || []; | |
49 | } | |
50 | } | |
51 | ||
52 | // Convert array of cards from ["ac", "4d", "ks"] | |
53 | // to numbers between 0 and 51 [0, 16, 51] | |
54 | function convertCardsToInts(cards) { | |
55 | var ints = []; | |
56 | var values = "a23456789tjqk"; | |
57 | var suits = "cdhs"; | |
58 | for (var i=0; i<cards.length; i++) { | |
59 | var card = cards[i].toLowerCase(); | |
60 | var value = card[0]; | |
61 | var suit = card[1]; | |
62 | var asInt = 13 * suits.indexOf(suit) + values.indexOf(value); | |
63 | ints.push(asInt); | |
64 | } | |
65 | return ints; | |
c6624d51 IC |
66 | } |
67 | ||
68 | this.fromString = function(rawEntropyStr) { | |
69 | // Find type of entropy being used (binary, hex, dice etc) | |
70 | var base = getBase(rawEntropyStr); | |
71 | // Convert dice to base6 entropy (ie 1-6 to 0-5) | |
425b75a9 | 72 | // This is done by changing all 6s to 0s |
c6624d51 | 73 | if (base.str == "dice") { |
a3d78b7d | 74 | var newParts = []; |
0d0f07f9 | 75 | var newInts = []; |
a3d78b7d IC |
76 | for (var i=0; i<base.parts.length; i++) { |
77 | var c = base.parts[i]; | |
425b75a9 | 78 | if ("12345".indexOf(c) > -1) { |
a3d78b7d | 79 | newParts[i] = base.parts[i]; |
0d0f07f9 | 80 | newInts[i] = base.ints[i]; |
c6624d51 IC |
81 | } |
82 | else { | |
a3d78b7d | 83 | newParts[i] = "0"; |
0d0f07f9 | 84 | newInts[i] = 0; |
c6624d51 IC |
85 | } |
86 | } | |
c6624d51 | 87 | base.str = "base 6 (dice)"; |
0d0f07f9 | 88 | base.ints = newInts; |
a3d78b7d | 89 | base.parts = newParts; |
c6624d51 IC |
90 | base.matcher = matchers.base6; |
91 | } | |
c6624d51 | 92 | // Detect empty entropy |
6606c50f | 93 | if (base.parts.length == 0) { |
c6624d51 IC |
94 | return { |
95 | binaryStr: "", | |
c6624d51 | 96 | cleanStr: "", |
b54c1218 | 97 | cleanHtml: "", |
c6624d51 IC |
98 | base: base, |
99 | }; | |
100 | } | |
adc8ce12 IC |
101 | // Convert base.ints to BigInteger. |
102 | // Due to using unusual bases, eg cards of base52, this is not as simple as | |
103 | // using BigInteger.parse() | |
104 | var entropyInt = BigInteger.ZERO; | |
105 | for (var i=base.ints.length-1; i>=0; i--) { | |
106 | var thisInt = BigInteger.parse(base.ints[i]); | |
107 | var power = (base.ints.length - 1) - i; | |
108 | var additionalEntropy = BigInteger.parse(base.asInt).pow(power).multiply(thisInt); | |
109 | entropyInt = entropyInt.add(additionalEntropy); | |
c6624d51 | 110 | } |
1cf1bbaf IC |
111 | // Convert entropy to binary |
112 | var entropyBin = entropyInt.toString(2); | |
113 | // If the first integer is small, it must be padded with zeros. | |
114 | // Otherwise the chance of the first bit being 1 is 100%, which is | |
115 | // obviously incorrect. | |
116 | // This is not perfect for non-2^n bases. | |
117 | var expectedBits = Math.floor(base.parts.length * Math.log2(base.asInt)); | |
118 | while (entropyBin.length < expectedBits) { | |
119 | entropyBin = "0" + entropyBin; | |
120 | } | |
6422c1cd IC |
121 | // Assume cards are NOT replaced. |
122 | // Additional entropy decreases as more cards are used. This means | |
0fdcf2eb | 123 | // total possible entropy is measured using n!, not base^n. |
6422c1cd IC |
124 | // eg the second last card can be only one of two, not one of fifty two |
125 | // so the added entropy for that card is only one bit at most | |
126 | if (base.asInt == 52) { | |
0fdcf2eb | 127 | // Get the maximum value WITHOUT replacement |
6422c1cd IC |
128 | var totalDecks = Math.ceil(base.parts.length / 52); |
129 | var totalCards = totalDecks * 52; | |
130 | var totalCombos = factorial(52).pow(totalDecks); | |
131 | var totalRemainingCards = totalCards - base.parts.length; | |
132 | var remainingDecks = Math.floor(totalRemainingCards / 52); | |
133 | var remainingCards = totalRemainingCards % 52; | |
134 | var remainingCombos = factorial(52).pow(remainingDecks).multiply(factorial(remainingCards)); | |
135 | var currentCombos = totalCombos.divide(remainingCombos); | |
136 | var numberOfBits = Math.log2(currentCombos); | |
137 | var maxWithoutReplace = BigInteger.pow(2, numberOfBits); | |
138 | // aggresive flooring of numberOfBits by BigInteger.pow means a | |
139 | // more accurate result can be had for small numbers using the | |
140 | // built-in Math.pow function. | |
141 | if (numberOfBits < 32) { | |
142 | maxWithoutReplace = BigInteger(Math.round(Math.pow(2, numberOfBits))); | |
143 | } | |
0fdcf2eb | 144 | // Get the maximum value WITH replacement |
6422c1cd IC |
145 | var maxWithReplace = BigInteger.pow(52, base.parts.length); |
146 | // Calculate the new value by scaling the original value down | |
147 | var withoutReplace = entropyInt.multiply(maxWithoutReplace).divide(maxWithReplace); | |
148 | // Left pad with zeros based on number of bits | |
149 | var entropyBin = withoutReplace.toString(2); | |
150 | var numberOfBitsInt = Math.floor(numberOfBits); | |
151 | while (entropyBin.length < numberOfBitsInt) { | |
152 | entropyBin = "0" + entropyBin; | |
153 | } | |
154 | } | |
1cf1bbaf | 155 | // Supply a 'filtered' entropy string for display purposes |
adc8ce12 | 156 | var entropyClean = base.parts.join(""); |
b54c1218 | 157 | var entropyHtml = base.parts.join(""); |
c193ff67 IC |
158 | if (base.asInt == 52) { |
159 | entropyClean = base.parts.join(" ").toUpperCase(); | |
160 | entropyClean = entropyClean.replace(/C/g, "\u2663"); | |
161 | entropyClean = entropyClean.replace(/D/g, "\u2666"); | |
162 | entropyClean = entropyClean.replace(/H/g, "\u2665"); | |
163 | entropyClean = entropyClean.replace(/S/g, "\u2660"); | |
b54c1218 IC |
164 | entropyHtml = base.parts.join(" ").toUpperCase(); |
165 | entropyHtml = entropyHtml.replace(/C/g, "<span class='card-suit club'>\u2663</span>"); | |
166 | entropyHtml = entropyHtml.replace(/D/g, "<span class='card-suit diamond'>\u2666</span>"); | |
167 | entropyHtml = entropyHtml.replace(/H/g, "<span class='card-suit heart'>\u2665</span>"); | |
168 | entropyHtml = entropyHtml.replace(/S/g, "<span class='card-suit spade'>\u2660</span>"); | |
c193ff67 | 169 | } |
0fdcf2eb | 170 | // Return the result |
c6624d51 IC |
171 | var e = { |
172 | binaryStr: entropyBin, | |
c6624d51 | 173 | cleanStr: entropyClean, |
b54c1218 | 174 | cleanHtml: entropyHtml, |
c6624d51 IC |
175 | base: base, |
176 | } | |
177 | return e; | |
178 | } | |
179 | ||
180 | function getBase(str) { | |
181 | // Need to get the lowest base for the supplied entropy. | |
182 | // This prevents interpreting, say, dice rolls as hexadecimal. | |
6606c50f IC |
183 | var binaryMatches = matchers.binary(str); |
184 | var hexMatches = matchers.hex(str); | |
c6624d51 | 185 | // Find the lowest base that can be used, whilst ignoring any irrelevant chars |
adc8ce12 IC |
186 | if (binaryMatches.length == hexMatches.length && hexMatches.length > 0) { |
187 | var ints = binaryMatches.map(function(i) { return parseInt(i, 2) }); | |
c6624d51 | 188 | return { |
adc8ce12 | 189 | ints: ints, |
6606c50f | 190 | parts: binaryMatches, |
c6624d51 IC |
191 | matcher: matchers.binary, |
192 | asInt: 2, | |
193 | str: "binary", | |
194 | } | |
195 | } | |
adc8ce12 IC |
196 | var cardMatches = matchers.card(str); |
197 | if (cardMatches.length >= hexMatches.length / 2) { | |
198 | var ints = convertCardsToInts(cardMatches); | |
199 | return { | |
200 | ints: ints, | |
201 | parts: cardMatches, | |
202 | matcher: matchers.card, | |
203 | asInt: 52, | |
204 | str: "card", | |
205 | } | |
206 | } | |
6606c50f | 207 | var diceMatches = matchers.dice(str); |
adc8ce12 IC |
208 | if (diceMatches.length == hexMatches.length && hexMatches.length > 0) { |
209 | var ints = diceMatches.map(function(i) { return parseInt(i) }); | |
c6624d51 | 210 | return { |
adc8ce12 | 211 | ints: ints, |
6606c50f | 212 | parts: diceMatches, |
c6624d51 IC |
213 | matcher: matchers.dice, |
214 | asInt: 6, | |
215 | str: "dice", | |
216 | } | |
217 | } | |
6606c50f | 218 | var base6Matches = matchers.base6(str); |
adc8ce12 IC |
219 | if (base6Matches.length == hexMatches.length && hexMatches.length > 0) { |
220 | var ints = base6Matches.map(function(i) { return parseInt(i) }); | |
c6624d51 | 221 | return { |
adc8ce12 | 222 | ints: ints, |
6606c50f | 223 | parts: base6Matches, |
c6624d51 IC |
224 | matcher: matchers.base6, |
225 | asInt: 6, | |
226 | str: "base 6", | |
227 | } | |
228 | } | |
6606c50f | 229 | var base10Matches = matchers.base10(str); |
adc8ce12 IC |
230 | if (base10Matches.length == hexMatches.length && hexMatches.length > 0) { |
231 | var ints = base10Matches.map(function(i) { return parseInt(i) }); | |
c6624d51 | 232 | return { |
adc8ce12 | 233 | ints: ints, |
6606c50f | 234 | parts: base10Matches, |
c6624d51 IC |
235 | matcher: matchers.base10, |
236 | asInt: 10, | |
237 | str: "base 10", | |
238 | } | |
239 | } | |
adc8ce12 | 240 | var ints = hexMatches.map(function(i) { return parseInt(i, 16) }); |
c6624d51 | 241 | return { |
adc8ce12 | 242 | ints: ints, |
6606c50f | 243 | parts: hexMatches, |
c6624d51 IC |
244 | matcher: matchers.hex, |
245 | asInt: 16, | |
246 | str: "hexadecimal", | |
247 | } | |
248 | } | |
249 | ||
250 | // Polyfill for Math.log2 | |
251 | // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log2#Polyfill | |
252 | Math.log2 = Math.log2 || function(x) { | |
adc8ce12 IC |
253 | // The polyfill isn't good enough because of the poor accuracy of |
254 | // Math.LOG2E | |
255 | // log2(8) gave 2.9999999999999996 which when floored causes issues. | |
256 | // So instead use the BigInteger library to get it right. | |
257 | return BigInteger.log(x) / BigInteger.log(2); | |
c6624d51 IC |
258 | }; |
259 | ||
6422c1cd IC |
260 | // Depends on BigInteger |
261 | function factorial(n) { | |
262 | if (n == 0) { | |
263 | return 1; | |
264 | } | |
265 | f = BigInteger.ONE; | |
266 | for (var i=1; i<=n; i++) { | |
267 | f = f.multiply(new BigInteger(i)); | |
268 | } | |
269 | return f; | |
270 | } | |
271 | ||
c6624d51 | 272 | })(); |