forked from kjur/jsrsasign
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathecdsamod-new-random.html
203 lines (166 loc) · 7.05 KB
/
ecdsamod-new-random.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta charset="utf-8">
<title>Comparison of old and new getBigRandom implementation</title>
<script type="text/javascript" src="../test/jquery-1.4.2.min.js"></script>
<script src="../ext/jsbn.js"></script>
<script src="../ext/jsbn2.js"></script>
<script src="../ext/prng4.js"></script>
<script src="../ext/rng.js"></script>
<script src="../ext/ec.js"></script>
<script src="../ext/ec-patch.js"></script>
<script type="text/javascript">
$(document).ready(function(){
var _BigInteger = BigInteger;
var rng = new SecureRandom();
var getBigRandom_old = function (limit) {
return new _BigInteger(limit.bitLength(), rng)
.mod(limit.subtract(_BigInteger.ONE))
.add(_BigInteger.ONE)
;
};
var getBigRandom_new1 = function (limit) {
var bitLength = limit.subtract(_BigInteger.ONE).bitLength();
do {
var result = new _BigInteger(bitLength, rng);
} while (result.compareTo(limit) >= 0);
return result;
};
/*
* Generate uniformly distributed big random integer in 0 <= x < limit
*
* This adapts "An optimal algorithm for bounded random integers" by
* Stephen Canon in the Swift language, see:
* https://github.com/swiftlang/swift/pull/39143
*
* In this implementation, we do not use the early out optimization for
* simplicity and to avoid potential side-channel attacks.
*/
var getBigRandom_new2 = function (limit) {
var limitBitLength = limit.subtract(_BigInteger.ONE).bitLength();
var limitBitMask = _BigInteger.ONE.shiftLeft(limitBitLength).subtract(_BigInteger.ONE);
var result = (new _BigInteger(limitBitLength, rng)).multiply(limit);
var frac = result.and(limitBitMask);
result = result.shiftRight(limitBitLength);
// do not use optional early out
var carry = (new _BigInteger(limitBitLength, rng)).multiply(limit).shiftRight(limitBitLength).add(frac).compareTo(limitBitMask) > 0;
return result.add(carry ? _BigInteger.ONE : _BigInteger.ZERO);
};
var randomFunctions = {
getBigRandom_old,
getBigRandom_new1,
getBigRandom_new2
};
var benchmark = function(limit, iterations) {
var results = {};
for (var name in randomFunctions) {
var randomFunction = randomFunctions[name];
var start = new Date();
for (var i = 0; i < iterations; i++) {
randomFunction(limit);
}
var end = new Date();
results[name] = end - start;
if (name !== "getBigRandom_old") {
var ratio = results[name] / results.getBigRandom_old;
results[`ratio_${name}`] = ratio;
}
}
return results;
};
var randomHistogram = function(randomFunction, limit, count) {
var binCount = 100;
var bins = new Array(binCount).fill(0);
var binSize = limit.divide(new _BigInteger(binCount.toString())).max(_BigInteger.ONE);
for (var i = 0; i < count; i++) {
var random = randomFunction(limit);
var bin = random.divide(binSize);
bins[bin.intValue()]++;
}
for (var i = 0; i < binCount; i++) {
bins[i] /= count;
}
return bins;
}
// Show function definitions
$("#output").append("<h1>Function definitions</h1>");
for (var name in randomFunctions) {
$("#output").append(`<h2>${name}</h2>`);
$("#output").append(`<pre>${randomFunctions[name].toString()}</pre>`);
}
function showHistogram(spec) {
var { limit, visualLimit, count } = spec;
$("#output").append(`<h1>Comparison of old and new getBigRandom() implementation</h1>`);
$("#output").append(`<p>Histograms over range: [0, ${visualLimit}), count: ${count}</p>`);
for (var name in randomFunctions) {
var bins = randomHistogram(randomFunctions[name], limit, count);
var output = "<h2>" + name + "</h2>"
+ "<div style='border: 1px solid black; display: inline-block;'>";
for (var i = 0; i < bins.length; i++) {
output += "<div style='width: 10px; height: " + (bins[i] * 10000) + "px; background-color: blue; display: inline-block;'></div>";
}
output += "</div>";
$("#output").append(output);
}
}
var histogramSpecs = [
{ shift: 7, count: 100000 },
{ shift: 4096, count: 10000 }
]
.map((spec) => {
var limit = _BigInteger.ONE.shiftLeft(spec.shift).multiply(new _BigInteger("2")).divide(new _BigInteger("3"));
return {
limit,
visualLimit: limit.compareTo(new _BigInteger("100000")) < 0 ? limit : `2^${spec.shift} * 2/3`,
count: spec.count
};
});
histogramSpecs.forEach(showHistogram);
var bitWidths = [
8,
16,
24,
32,
64,
100,
128,
256,
400,
512,
1024,
2048,
4096
]
$("#output").append("<h1>Comparison of old and new getBigRandom() performance</h1>");
var iterations = 10000;
$("#output").append(`<p>Iterations: ${iterations}</p>`);
var output = "<table><tr><th style='text-align: right;'>Limit</th><th style='text-align: right;'>Old</th><th style='text-align: right;'>New1</th><th style='text-align: right;'>New2</th><th style='text-align: right;'>Ratio New1/Old</th><th style='text-align: right;'>Ratio New2/Old</th></tr>";
bitWidths.forEach(function(bitWidth) {
var limit = _BigInteger.ONE.shiftLeft(bitWidth);
var result = benchmark(limit, iterations);
output += `<tr><td style='text-align: right;'>2^${bitWidth}</td><td style='text-align: right;'>${result.getBigRandom_old}</td><td style='text-align: right;'>${result.getBigRandom_new1}</td><td style='text-align: right;'>${result.getBigRandom_new2}</td><td style='text-align: right;'>${result.ratio_getBigRandom_new1.toFixed(2)}</td><td style='text-align: right;'>${result.ratio_getBigRandom_new2.toFixed(2)}</td></tr>`;
var limit = _BigInteger.ONE.shiftLeft(bitWidth).add(new _BigInteger("10"));
var result = benchmark(limit, iterations);
output += `<tr><td style='text-align: right;'>2^${bitWidth} + 10</td><td style='text-align: right;'>${result.getBigRandom_old}</td><td style='text-align: right;'>${result.getBigRandom_new1}</td><td style='text-align: right;'>${result.getBigRandom_new2}</td><td style='text-align: right;'>${result.ratio_getBigRandom_new1.toFixed(2)}</td><td style='text-align: right;'>${result.ratio_getBigRandom_new2.toFixed(2)}</td></tr>`;
var limit = _BigInteger.ONE.shiftLeft(bitWidth).multiply(new _BigInteger("3")).divide(new _BigInteger("2"));
var result = benchmark(limit, iterations);
output += `<tr><td style='text-align: right;'>2^${bitWidth} * 1.5</td><td style='text-align: right;'>${result.getBigRandom_old}</td><td style='text-align: right;'>${result.getBigRandom_new1}</td><td style='text-align: right;'>${result.getBigRandom_new2}</td><td style='text-align: right;'>${result.ratio_getBigRandom_new1.toFixed(2)}</td><td style='text-align: right;'>${result.ratio_getBigRandom_new2.toFixed(2)}</td></tr>`;
});
output += "</table>";
$("#output").append(output);
});
</script>
<style type="text/css">
table, th, td {
border-collapse: collapse;
border: 1px solid black;
padding: 3px;
}
</style>
</head>
<body>
<div id="output"></div>
</body>
</html>