生日悖論

在算法導論書上看到個比較有意思的概率算法，在這里加上自己的理解分享下：

上次剛看同學發的朋友圈說道：“兩個人同一間宿舍，而且同年同月同日生，這個緣分真的是醉了”，當時我也是醉醉的，看了這個算法后才發現，屋里有23個人，那么就可以50%的概率生日是一樣的。

?? 是這樣子證明的：

?? 首先，假設屋子里有K個人，分別對他們編號1,2,3….k號。不考慮閏年的情況，那么一年就有n=365天，首先還是要假設生日是均勻分布在一年的n天中（喜歡在春天生就都在春天生這就不均勻了），然后還要假設兩個人生日相互獨立（什么雙胞胎那些還用得著算么），

那么兩個人同一天（具體的一天）生日的概率就1/n²(生日的概率是1/n,兩個人同一天生日當然就相乘了~)，那么兩個人同一天生日（365天隨便一天）的概率就是1/n (n個1/n²相加)

?? 也就是說假如屋里面有兩個人，那么他們同一天生日的概率是1/365,那現在要解決的問題是，屋里要有多少人，才能使這個概率上升到1/2 ?

?? 用事件的對立面來求，假設事件P={屋里至少兩個人生日一樣}，Q={屋里每個人生日都不一樣}，那么P=1-Q

?? 那么知道Q的概率就能知道P的概率了，設B_K為前K個人的生日都有一樣，A_i為前第i個人與前i-1一個人的生日都不一樣，那么就可以得到遞推式子

B_k=B_k-1_^A_k

它的等價形式為

P{B_k}=P{B_k-1}P{ A_k | B_k-1}

應用遞歸式可以得到P{B_k}=P{B₁} P{ A₂ | B₁} P{ A₃ | B₂}… P{ A_k-1 | B_k-2} P{ A_k | B_k-1}

?????????????????? ????=1*(n-1/n) (n-2/n)… (n-k+1/n)(B₁是規定為1的，然后P{ A₂ | B₁}就是365中有一天已經給B₁用了，那么就剩下n-1天了，所以概率為(n-1/n))

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

然后已知 1+x<=e^x(兩個都是單調增函數，取0時為相等，過了就e^x大了，高中學的嘿嘿)

那么有1*( ) ( )… ( )<=(e^-1/n)(e^-2/n)…(e^-(k-1/n))= (e^-k(k-1)/2n))<=1/2

求得當n=365時，必有k>=23,所以結論是至少有23個人在一間屋子里，那么至少有兩個人生日相同的概率至少是1/2。

在程序中，有時可能考慮產生n個隨機數，比如產生1000個范圍為0到1億之間的隨機數，任意兩個隨機數都不重復的概率為多大？傳統計算方法無法計算過于大的位數，下面是一個近似解：

 1 /*
 2  * 功能:范圍為r的k個隨機數互不相同的概率(r>k)。
 3  * 若k>=r，顯然概率為0.
 4  * 例1：50個人中生日互不相同的概率為distinct(365,50)約為0.0296。
 5  * 例2：隨機產生名稱為Integer.MAX_VALUE以內整數做文件名的文件1萬個，沒有相同文件名的概率為distinct(Integer.MAX_VALUE, 10000)約為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 }
21 }

  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

生日攻擊

生日攻擊是利用概率論中的生日問題，找到沖突的Hash值，偽造報文，使身份驗證算法失效。

生日攻擊的理論描述有些復雜，不易理解，請參考相關資料。
本文以實例方式介紹生日攻擊方法和防范方法。

實例場景

場景說明

A要對一個合同文件進行簽名，然后把合同文件和簽名一起發送給接收者。
簽名的方法：計算文件的Hash值（m位），然后使用A的私鑰對這個Hash值進行加密。

接收者使用A的公鑰進行解密，然后比較Hash值，這樣他就能確認：
接收到的合同文件是A發送的，并且合同文件未被修改過。

攻擊者B想要偽造一份假合同文件，然后發送給接收者，并使接收者仍然相信：
接收到的合同文件是A發送的，并且合同文件未被修改過。

攻擊方法

B先準備 2^m/2 個有效合同文件（集合X），每個文件包含與原合同文件相同的意思。
B再準備 2^m/2 個偽造合同文件（集合Y），每個文件也都是希望的偽造合同的意思。

注1：2^m/2 表示 2 的 m/2 次方。

注2：要產生包含相同意思的許多文件，也不是很難。
例如要生成 2^32 個文件，方法是：在文件中找到32個地方，每個地方使用兩種方式表達相同意思，這樣組合起來，就有了 2^32 個文件，這些文件要表達的意思都相同。

然后比較集合X和集合Y，找到Hash值相同的兩個文件，分別是有效合同和偽造合同。

B成功的概率會大于0.5，如果沒有找到匹配的文件，就準備更多的有效文件和偽造文件，直到找到一對匹配的文件。

注3：如果使用64位Hash值，那么只需要2^32個不同文件，這無法防住現代計算機系統。

B把找到的有效合同文件提供A，A看了一下，沒什么問題，就做了簽名，然后發送給接收者。

在接收者收到消息之前，B截獲了這個消息，然后使用偽造合同替換有效合同，再把偽造合同和原簽名一起發送給接收者。

因為偽造合同與有效合同的Hash值相同，所以它們產生相同的簽名。
這樣，即使B不知道A的私鑰，他也能成功！！！

遭遇失敗

如果A是一個認真的人，他在對B提供的有效合同文件進行簽名之前，又仔細閱讀了合同，修改了其中的標點符號問題，然后才對文件進行簽名。

這樣，B的計劃就失敗了。
B面臨的問題是：找到一個偽造合同，與新的合同文件具有相同的Hash值。
這幾乎是不可能的！！！

防范方法

- 使用安全的Hash算法：安全的Hash算法生成的Hash值有足夠多的位數。這樣，攻擊者在尋找兩個具有相同Hash值的文件時就會非常困難。
- 加鹽：在為文件簽名之前，先向文件添加一個隨機值，然后計算Hash值，再將文件、簽名和隨機值一起發送給接收者。這樣，攻擊者必須找出具有特定Hash值的偽造文件，這非常困難。
- 改動文件：在為文件簽名之前，對消息或文件做少許改動。這樣，攻擊者必須找出具有特定Hash值的偽造文件，這非常困難。