birthdayParadox.

 

See a more interesting probability algorithm in the introduction to algorithm book, add my own understanding here to share:

Last time, I just saw my classmate’s wechat moments and said, “Two people share the same dormitory and were born on the same day in the same year and month, so the fate is really drunk.” AT that time, I was also drunk. After reading the algorithm, I found that there were 23 people in the room, so there was a 50% probability that the birthdays would be the same.

It is proved like this:

First, suppose there are K people in the room and number them 1,2,3… K number. Not counting leap years, there would be n=365 days in a year, assuming that birthdays are evenly distributed over n days of the year, and then assuming that two people are born independently of each other.

So the probability that two people have the same birthday (on a specific day) is 1/n2, so the probability that two people have the same birthday (on any day in 365) is 1/n.

So if there are two people in the room, the probability that they have the same birthday is 1/365, and now the question is, how many people do I have to have in the room for that probability to rise to 1/2?

Using the opposite of the event, if P={at least two people in the room have the same birthday} and Q={everyone in the room has a different birthday}, then P= 1-q

So if you know the probability of Q, you know the probability of P, and if BK is equal to the first K, and Ai is equal to the first I, and Ai is equal to the first I minus one, then you get the recurrence

Bk=Bk-1^Ak

Its equivalent form is zero

P{Bk}=P{Bk-1}P{ Ak | Bk-1}

Application of recursion can get P = P {Bk} {B1} {A2 B1} | P P {A3 | B2}… P{ Ak-1 | Bk-2} P{ Ak | Bk-1}

= 1 * (n – 1 / n) (n – 2 / n)… (n – k + 1 / n) (B1 is a regulation of 1, then P {A2 B1} | is one day in 365 has been for B1, then n – 1 day left, so the probability of/n) (n – 1)

P {Bk} = 1 * (1-1 / n) (1-2 / n)… (1-k-1/n)

And then we know that 1+x is less than =ex.

So 1*() ()… (a) < = (e – 1 / n) – 2 (e/n)… (e-(k-1/n))= (e-k(k-1)/2n))<=1/2

When n=365, k must be greater than =23, so the conclusion is that there are at least 23 people in a room, so the probability that at least two people have the same birthday is at least 1/2.

In a program, it is sometimes possible to consider generating n random numbers, such as 1000 random numbers ranging from 0 to 100 million. What is the probability that no two random numbers will repeat? Traditional calculation methods cannot calculate too large a number of digits. Here is an approximate solution:

 

1 /* 2 * Function: the probability that k random numbers in range R are different from each other (r>k). 3 * if k>=r, it is obvious that the probability is 0. 4 * cases 1: the probability of distinct birthdays among 50 people (365,50) is about 0.0296. 5 * Example 2: Randomly generate 10,000 files whose names are integers within integer. MAX_VALUE. Distinct (integer. MAX_VALUE, 10000) about 0.977 6 * 7 */ 8 package com.copy; 9 import static Java.lang.Math.*; 10 public class Distinct { 11 12 13 public static void main(String[] args) { 14 15 System.out.println(distinct(Integer.MAX_VALUE ,10000)); 16 } 17 18 public static double distinct(double r, double k) { 19 return sqrt(2 * PI * r) / sqrt(2 * PI * (r - k)) * pow( r/E, r - (r - k) * (log((r - k) / E) / log(r / E)) - k * log(r) / log(r / E) ); 20}} 21Copy the code

 

  1 以下是从2 人到364人生日互不相同的概率：
  2 
  3 人数2 0.997261528435304
  4 人数3 0.9917977106686194
  5 人数4 0.9836465759145728
  6 人数5 0.9728675112354711
  7 人数6 0.9595411777338625
  8 人数7 0.9437685100361304
  9 人数8 0.9256694435439302
 10 人数9 0.9053813918576331
 11 人数10 0.8830575014579024
 12 人数11 0.8588647147768872
 13 人数12 0.83298167612227
 14 人数13 0.8055965174604536
 15 人数14 0.7769045627622481
 16 人数15 0.7471059904296959
 17 人数16 0.7164034932666513
 18 人数17 0.6849999745275132
 19 人数18 0.6530963168239327
 20 人数19 0.6208892581770326
 21 人数20 0.5885694063080312
 22 人数21 0.5563194185097445
 23 人数22 0.5243123702121542
 24 人数23 0.4927103307922907
 25 人数24 0.4616631603810471
 26 人数25 0.43130753655505705
 27 人数26 0.40176621494015163
 28 人数27 0.37314752306698046
 29 人数28 0.3455450823793965
 30 人数29 0.3190377492123028
 31 人数30 0.293689761912032
 32 人数31 0.2695510781270815
 33 人数32 0.24665788369766528
 34 人数33 0.22503325255723464
 35 人数34 0.20468793562709864
 36 人数35 0.18562125583950176
 37 人数36 0.1678220861466564
 38 人数37 0.15126988761627422
 39 人数38 0.13593578544669332
 40 人数39 0.12178366188891603
 41 人数40 0.1087712465818115
 42 人数41 0.09685118661702039
 43 人数42 0.08597208068851865
 44 人数43 0.0760794638681576
 45 人数44 0.06711673182514903
 46 人数45 0.05902599560048669
 47 人数46 0.051748860305991407
 48 人数47 0.04522712328390563
 49 人数48 0.03940338929763275
 50 人数49 0.034221602187752664
 51 人数50 0.029627494094956967
 52 人数51 0.025568954802279956
 53 人数52 0.0219963249737199
 54 人数53 0.018862618059882787
 55 人数54 0.016123676408139682
 56 人数55 0.013738267663700484
 57 人数56 0.011668127892545042
 58 人数57 0.009877958015770329
 59 人数58 0.008335380137448146
 60 人数59 0.0070108601977503845
 61 人数60 0.005877603112454998
 62 人数61 0.004911426193103169
 63 人数62 0.004090616201315916
 64 人数63 0.003395774897958958
 65 人数64 0.002809657422794226
 66 人数65 0.0023170073006054163
 67 人数66 0.0019043913313614204
 68 人数67 0.0015600370976016945
 69 人数68 0.001273675322755735
 70 人数69 0.0010363888477753058
 71 人数70 8.404695663190771E-4
 72 人数71 6.79284274773569E-4
 73 人数72 5.47150054743283E-4
 74 人数73 4.3921951284882056E-4
 75 人数74 3.513759548782414E-4
 76 人数75 2.801383666838221E-4
 77 人数76 2.225759099077254E-4
 78 人数77 1.762315133316221E-4
 79 人数78 1.390540466029231E-4
 80 人数79 1.0933849833405421E-4
 81 人数80 8.567354107899968E-5
 82 人数81 6.689584752449988E-5
 83 人数82 5.2050521631153776E-5
 84 人数83 4.035702192591879E-5
 85 人数84 3.11799784969191E-5
 86 人数85 2.400433763667517E-5
 87 人数86 1.8414306049359104E-5
 88 人数87 1.4075607966145631E-5
 89 人数88 1.0720611641437018E-5
 90 人数89 8.135925100205447E-6
 91 人数90 6.152103542702944E-6
 92 人数91 4.635151631013028E-6
 93 人数92 3.479542361035658E-6
 94 人数93 2.6025099468439285E-6
 95 人数94 1.9394068652623725E-6
 96 人数95 1.4399448193644152E-6
 97 人数96 1.06516588303459E-6
 98 人数97 7.850135719021647E-7
 99 人数98 5.763941980275251E-7
100 人数99 4.216367984872279E-7
101 人数100 3.0727539996626477E-7
102 人数101 2.2309062461503145E-7
103 人数102 1.613588920166524E-7
104 人数103 1.1626695869354567E-7
105 人数104 8.345748027381826E-8
106 人数105 5.967788794695045E-8
107 人数106 4.251032895224462E-8
108 人数107 3.016490117628953E-8
109 人数108 2.1322066533069384E-8
110 人数109 1.5013090519920495E-8
111 人数110 1.052974268310542E-8
112 人数111 7.356405037887832E-9
113 人数112 5.119258363505299E-9
114 人数113 3.548422079017974E-9
115 人数114 2.44987271782621E-9
116 人数115 1.6847092295825918E-9
117 人数116 1.15391197594619E-9
118 人数117 7.871903280805647E-10
119 人数118 5.348588135548078E-10
120 人数119 3.6194604967979793E-10
121 人数120 2.4394205844381303E-10
122 人数121 1.6374215789642276E-10
123 人数122 1.094606648758393E-10
124 人数123 7.287391577494481E-11
125 人数124 4.8316473468394486E-11
126 人数125 3.1902155842246264E-11
127 人数126 2.0976790481129164E-11
128 人数127 1.3735507588484367E-11
129 人数128 8.956316810132223E-12
130 人数129 5.8154801275045396E-12
131 人数130 3.760151704975162E-12
132 人数131 2.4209232595975476E-12
133 人数132 1.5520463249241352E-12
134 人数133 9.907598662867073E-13
135 人数134 6.29744236698989E-13
136 人数135 3.985510872476768E-13
137 人数136 2.5114217835601535E-13
138 人数137 1.5756616612369978E-13
139 人数138 9.842505128717587E-14
140 人数139 6.121239160155489E-14
141 人数140 3.790143335118387E-14
142 人数141 2.336393590201922E-14
143 人数142 1.433843937796741E-14
144 人数143 8.76021195500924E-15
145 人数144 5.3281379650841086E-15
146 人数145 3.226083584972268E-15
147 人数146 1.9444920993801484E-15
148 人数147 1.1666972960842728E-15
149 人数148 6.968231742088301E-16
150 人数149 4.142764318879114E-16
151 人数150 2.451612872872876E-16
152 人数151 1.4441033488887312E-16
153 人数152 8.466813195809865E-17
154 人数153 4.940916544803405E-17
155 人数154 2.8697979695469803E-17
156 人数155 1.658982220223549E-17
157 人数156 9.544847334855884E-18
158 人数157 5.46541621106069E-18
159 人数158 3.114544581221222E-18
160 人数159 1.76633421435653E-18
161 人数160 9.968919621327157E-19
162 人数161 5.598993409966635E-19
163 人数162 3.1293067234718916E-19
164 人数163 1.7404124817288055E-19
165 人数164 9.631891585541229E-20
166 人数165 5.3041485533584616E-20
167 人数166 2.906388854346236E-20
168 人数167 1.584582480111398E-20
169 人数168 8.595835653650936E-21
170 人数169 4.63940624234323E-21
171 人数170 2.4913030305441853E-21
172 人数171 1.330973044114597E-21
173 人数172 7.074228636805817E-22
174 人数173 3.7406279378378165E-22
175 人数174 1.9676772495856125E-22
176 人数175 1.029663610098081E-22
177 人数176 5.359905203129384E-23
178 人数177 2.7754094773481293E-23
179 人数178 1.4295293658983514E-23
180 人数179 7.323907723068574E-24
181 人数180 3.732192152171627E-24
182 人数181 1.8916636669956916E-24
183 人数182 9.536081538054923E-25
184 人数183 4.781115856971393E-25
185 人数184 2.3840144855204884E-25
186 人数185 1.1822129468156427E-25
187 人数186 5.830106323404897E-26
188 人数187 2.8591555105072787E-26
189 人数188 1.3943315807841226E-26
190 人数189 6.761571232667588E-27
191 人数190 3.260382895176333E-27
192 人数191 1.5632015565451854E-27
193 人数192 7.451995173278288E-28
194 人数193 3.5320514395422914E-28
195 人数194 1.6644234763571782E-28
196 人数195 7.797732338337783E-29
197 人数196 3.63183107546654E-29
198 人数197 1.6815924746677324E-29
199 人数198 7.739955475628124E-30
200 人数199 3.5413053423047515E-30
201 人数200 1.61057116536134E-30
202 人数201 7.280686593494693E-31
203 人数202 3.2713323933076926E-31
204 人数203 1.4609009942182749E-31
205 人数204 6.484019649905391E-32
206 人数205 2.860083673207741E-32
207 人数206 1.2537394156314248E-32
208 人数207 5.461513105172664E-33
209 人数208 2.3641697794601874E-33
210 人数209 1.0169203240639937E-33
211 人数210 4.346304583123179E-34
212 人数211 1.845697430889915E-34
213 人数212 7.787353688669575E-35
214 人数213 3.2642996814747587E-35
215 人数214 1.3593845289569194E-35
216 人数215 5.6237758653215976E-36
217 人数216 2.311149383776688E-36
218 人数217 9.434590671291894E-37
219 人数218 3.825547308889449E-37
220 人数219 1.540705857348351E-37
221 人数220 6.162847688590297E-38
222 人数221 2.448264332325108E-38
223 人数222 9.65894494734862E-39
224 人数223 3.7842049201358714E-39
225 人数224 1.4722173566589267E-39
226 人数225 5.687219824825991E-40
227 人数226 2.1814087262180283E-40
228 人数227 8.307318636057621E-41
229 人数228 3.140863081846686E-41
230 人数229 1.1789045664531903E-41
231 人数230 4.3926506507983883E-42
232 人数231 1.6246864920466093E-42
233 人数232 5.964630353558949E-43
234 人数233 2.1734235686582143E-43
235 人数234 7.860090236801233E-44
236 人数235 2.8210324918437226E-44
237 人数236 1.0047562912485759E-44
238 人数237 3.551074402931366E-45
239 人数238 1.2453146675840465E-45
240 人数239 4.333035243861282E-46
241 人数240 1.495795423030422E-46
242 人数241 5.12261460585867E-47
243 人数242 1.7402950184095124E-47
244 人数243 5.864588383174268E-48
245 人数244 1.960229648503839E-48
246 人数245 6.498332842028368E-49
247 人数246 2.1364506621318907E-49
248 人数247 6.965455824118345E-50
249 人数248 2.251859584591692E-50
250 人数249 7.218333948093835E-51
251 人数250 2.294060188035423E-51
252 人数251 7.227906809894806E-52
253 人数252 2.257497826352238E-52
254 人数253 6.989011891945552E-53
255 人数254 2.1445878873395627E-53
256 人数255 6.521941922595186E-54
257 人数256 1.9655304045358402E-54
258 人数257 5.869707690407385E-55
259 人数258 1.7368027451077907E-55
260 人数259 5.09148655151868E-56
261 人数260 1.4786345624715487E-56
262 人数261 4.253638735795503E-57
263 人数262 1.212005123175935E-57
264 人数263 3.420205969367417E-58
265 人数264 9.557913172920543E-59
266 人数265 2.644814233825782E-59
267 人数266 7.246127387510261E-60
268 人数267 1.9654048575328666E-60
269 人数268 5.277023685478768E-61
270 人数269 1.402399666335672E-61
271 人数270 3.6885369352189833E-62
272 人数271 9.600391200109067E-63
273 人数272 2.4724530828879777E-63
274 人数273 6.299736335181651E-64
275 人数274 1.5878945528375195E-64
276 人数275 3.958900673165118E-65
277 人数276 9.761774449141333E-66
278 人数277 2.3802936164636327E-66
279 人数278 5.738852553593375E-67
280 人数279 1.3679061178710478E-67
281 人数280 3.22304841672974E-68
282 人数281 7.505816790809824E-69
283 人数282 1.7273867022622438E-69
284 人数283 3.928078130054646E-70
285 人数284 8.824834187987433E-71
286 人数285 1.9584130456989745E-71
287 人数286 4.292468752695527E-72
288 人数287 9.290674449052923E-73
289 人数288 1.9854319500577967E-73
290 人数289 4.1885051271614915E-74
291 人数290 8.721398452363574E-75
292 人数291 1.7920950827914942E-75
293 人数292 3.63334470890731E-76
294 人数293 7.26680462913946E-77
295 人数294 1.433475239216766E-77
296 人数295 2.7884506433561695E-78
297 人数296 5.3478058270752784E-79
298 人数297 1.0109730292337928E-79
299 人数298 1.8834910520811563E-80
300 人数299 3.4574322905015665E-81
301 人数300 6.251916814200046E-82
302 人数301 1.1133773515771803E-82
303 人数302 1.9522636493420678E-83
304 人数303 3.369732435059139E-84
305 人数304 5.724055188006599E-85
306 人数305 9.56644702516075E-86
307 人数306 1.5726036526515317E-86
308 人数307 2.54207876591672E-87
309 人数308 4.039569447862928E-88
310 人数309 6.308533415953783E-89
311 人数310 9.679107657439067E-90
312 人数311 1.458536596603439E-90
313 人数312 2.1578977935991347E-91
314 人数313 3.1334805796466244E-92
315 人数314 4.4642769889133005E-93
316 人数315 6.237960732218878E-94
317 人数316 8.54544233246896E-95
318 人数317 1.1472370130425093E-95
319 人数318 1.5087509775790893E-96
320 人数319 1.942850112793478E-97
321 人数320 2.4486219988417057E-98
322 人数321 3.0189760918612455E-99
323 人数322 3.639473933982971E-100
324 人数323 4.287797263191564E-101
325 人数324 4.934142460106241E-102
326 人数325 5.542743012662612E-103
327 人数326 6.074563384431801E-104
328 人数327 6.4909943254637144E-105
329 人数328 6.758148030622761E-106
330 人数329 6.851153981072421E-107
331 人数330 6.7577494475310795E-108
332 人数331 6.480487478442585E-109
333 人数332 6.03706680229222E-110
334 人数333 5.458600688642653E-111
335 人数334 4.786024515931745E-112
336 人数335 4.0652069499352986E-113
337 人数336 3.341586009428232E-114
338 人数337 2.655231198781569E-115
339 人数338 2.0371141942921878E-116
340 人数339 1.50708525796149E-117
341 人数340 1.073677804760819E-118
342 人数341 7.354978850568769E-120
343 人数342 4.836880495131281E-121
344 人数343 3.048399199819024E-122
345 人数344 1.8377226764725207E-123
346 人数345 1.057529652618079E-124
347 人数346 5.795953596854461E-126
348 人数347 3.017806763933968E-127
349 人数348 1.4886386877339791E-128
350 人数349 6.935509412587238E-130
351 人数350 3.0412786807910636E-131
352 人数351 1.2503363845348714E-132
353 人数352 4.798005970719257E-134
354 人数353 1.7097913604314834E-135
355 人数354 5.6247790605897E-137
356 人数355 1.6964224108450512E-138
357 人数356 4.652033303088953E-140
358 人数357 1.1484032661324103E-141
359 人数358 2.5207899688523915E-143
360 人数359 4.843970484385247E-145
361 人数360 7.984766959369045E-147
362 人数361 1.098347996087053E-148
363 人数362 1.2119876239193127E-150
364 人数363 1.0098578391715748E-152
365 人数364 5.757684771147015E-155
Copy the code

 

 

 

Birthday attack

 

Birthday attacks use birthday problems in probability theory to find conflicting Hash values and forge packets to invalidate authentication algorithms.

 

The theoretical description of birthday attack is complicated and not easy to understand, please refer to related materials. This paper introduces the methods of birthday attack and defense by examples.

 

Example scenario

 

The scene that

 

A signs A contract document and sends the contract document with the signature to the recipient. Signature method: calculate the Hash value of the file (m bits), and then use A’s private key to encrypt the Hash value.

 

The receiver decrypts it using A’s public key and compares the Hash value so that he can confirm that the received contract file was sent by A and has not been modified.

 

Attacker B wants to forge A fake contract document and send it to the recipient, convincing the recipient that the received contract document was sent by A and that the contract document has not been modified.

 

Attack methods

 

B Prepare 2^m/2 valid contract documents (set X), each of which contains the same meaning as the original contract documents. B also prepares 2^m/2 forged contract documents (set Y), each of which also means the desired forged contract.

 

Note 1:2 ^m/2 means 2 to the power of m/2.

Note 2: It is not too difficult to produce many files with the same meaning. For example, to generate 2^32 files, find 32 places in the file, each place using two ways to express the same meaning, so that when combined, you have 2^32 files that all want to express the same meaning.

 

Then compare set X and set Y to find two files with the same Hash value, valid contracts and forged contracts.

 

B has a probability of success greater than 0.5. If no matching file is found, more valid files and forged files are prepared until a matching pair is found.

 

Note 3: If you use a 64-bit Hash value, you only need 2^32 different files, which is not defendable against modern computer systems.

 

B provides A with the valid contract document he finds. A looks at it, finds no problem, makes A signature, and then sends it to the recipient.

 

Before the receiver can receive the message, B intercepts the message, replaces the valid contract with a forged contract, and sends the forged contract along with the original signature to the receiver.

 

Because forged contracts have the same Hash value as valid contracts, they produce the same signature. This way, even if B does not know A’s private key, he can succeed!!

 

failure

 

If A is A serious person, he will read the contract carefully and correct the punctuation problem before signing the valid contract document provided by B.

 

In this way, B’s plan fails. B faces the problem of finding a forged contract with the same Hash value as the new contract file. It’s almost impossible!!

 

Methods to prevent

 

• • Using a secure Hash algorithm: A secure Hash algorithm generates a Hash value with enough digits. This makes it very difficult for an attacker to find two files with the same Hash value.
  • Salt: Before signing a file, add a random value to the file, compute the Hash value, and send the file, signature, and random value to the receiver. Thus, an attacker would have to find a forged file with a particular Hash value, which is very difficult.
  • Modify file: To make a few changes to a message or file before signing the file. Thus, an attacker would have to find a forged file with a particular Hash value, which is very difficult.