首页 > 代码库 > 密码学经典之生日悖论与生日攻击【详解】
密码学经典之生日悖论与生日攻击【详解】
生日悖论
在算法导论书上看到个比较有意思的概率算法，在这里加上自己的理解分享下：
上次刚看同学发的朋友圈说道：“两个人同一间宿舍，而且同年同月同日生，这个缘分真的是醉了”，当时我也是醉醉的，看了这个算法后才发现，屋里有23个人，那么就可以50%的概率生日是一样的。
是这样子证明的：
首先，假设屋子里有K个人，分别对他们编号1,2,3….k号。不考虑闰年的情况，那么一年就有n=365天，首先还是要假设生日是均匀分布在一年的n天中（喜欢在春天生就都在春天生这就不均匀了），然后还要假设两个人生日相互独立（什么双胞胎那些还用得着算么），
那么两个人同一天（具体的一天）生日的概率就1/n2 (生日的概率是1/n,两个人同一天生日当然就相乘了~)，那么两个人同一天生日（365天随便一天）的概率就是1/n (n个1/n2相加)
也就是说假如屋里面有两个人，那么他们同一天生日的概率是1/365,那现在要解决的问题是，屋里要有多少人，才能使这个概率上升到1/2 ?
用事件的对立面来求，假设事件P={屋里至少两个人生日一样}，Q={屋里每个人生日都不一样}，那么P=1-Q
那么知道Q的概率就能知道P的概率了，设BK为前K个人的生日都有一样，Ai为前第i个人与前i-1一个人的生日都不一样，那么就可以得到递推式子
Bk=Bk-1^Ak
它的等价形式为
P{Bk}=P{Bk-1}P{ Ak | Bk-1}
应用递归式可以得到P{Bk}=P{B1} P{ A2 | B1} P{ A3 | B2}… P{ Ak-1 | Bk-2} P{ Ak | Bk-1}
=1*(n-1/n) (n-2/n)… (n-k+1/n)(B1是规定为1的，然后P{ A2 | B1}就是365中有一天已经给B1用了，那么就剩下n-1天了，所以概率为(n-1/n))
P{Bk}=1*(1-1/n) (1-2/n)… (1-k-1/n)
然后已知 1+x<=ex(两个都是单调增函数，取0时为相等，过了就ex 大了，高中学的嘿嘿)
那么有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-7100 人数99 4.216367984872279E-7101 人数100 3.0727539996626477E-7102 人数101 2.2309062461503145E-7103 人数102 1.613588920166524E-7104 人数103 1.1626695869354567E-7105 人数104 8.345748027381826E-8106 人数105 5.967788794695045E-8107 人数106 4.251032895224462E-8108 人数107 3.016490117628953E-8109 人数108 2.1322066533069384E-8110 人数109 1.5013090519920495E-8111 人数110 1.052974268310542E-8112 人数111 7.356405037887832E-9113 人数112 5.119258363505299E-9114 人数113 3.548422079017974E-9115 人数114 2.44987271782621E-9116 人数115 1.6847092295825918E-9117 人数116 1.15391197594619E-9118 人数117 7.871903280805647E-10119 人数118 5.348588135548078E-10120 人数119 3.6194604967979793E-10121 人数120 2.4394205844381303E-10122 人数121 1.6374215789642276E-10123 人数122 1.094606648758393E-10124 人数123 7.287391577494481E-11125 人数124 4.8316473468394486E-11126 人数125 3.1902155842246264E-11127 人数126 2.0976790481129164E-11128 人数127 1.3735507588484367E-11129 人数128 8.956316810132223E-12130 人数129 5.8154801275045396E-12131 人数130 3.760151704975162E-12132 人数131 2.4209232595975476E-12133 人数132 1.5520463249241352E-12134 人数133 9.907598662867073E-13135 人数134 6.29744236698989E-13136 人数135 3.985510872476768E-13137 人数136 2.5114217835601535E-13138 人数137 1.5756616612369978E-13139 人数138 9.842505128717587E-14140 人数139 6.121239160155489E-14141 人数140 3.790143335118387E-14142 人数141 2.336393590201922E-14143 人数142 1.433843937796741E-14144 人数143 8.76021195500924E-15145 人数144 5.3281379650841086E-15146 人数145 3.226083584972268E-15147 人数146 1.9444920993801484E-15148 人数147 1.1666972960842728E-15149 人数148 6.968231742088301E-16150 人数149 4.142764318879114E-16151 人数150 2.451612872872876E-16152 人数151 1.4441033488887312E-16153 人数152 8.466813195809865E-17154 人数153 4.940916544803405E-17155 人数154 2.8697979695469803E-17156 人数155 1.658982220223549E-17157 人数156 9.544847334855884E-18158 人数157 5.46541621106069E-18159 人数158 3.114544581221222E-18160 人数159 1.76633421435653E-18161 人数160 9.968919621327157E-19162 人数161 5.598993409966635E-19163 人数162 3.1293067234718916E-19164 人数163 1.7404124817288055E-19165 人数164 9.631891585541229E-20166 人数165 5.3041485533584616E-20167 人数166 2.906388854346236E-20168 人数167 1.584582480111398E-20169 人数168 8.595835653650936E-21170 人数169 4.63940624234323E-21171 人数170 2.4913030305441853E-21172 人数171 1.330973044114597E-21173 人数172 7.074228636805817E-22174 人数173 3.7406279378378165E-22175 人数174 1.9676772495856125E-22176 人数175 1.029663610098081E-22177 人数176 5.359905203129384E-23178 人数177 2.7754094773481293E-23179 人数178 1.4295293658983514E-23180 人数179 7.323907723068574E-24181 人数180 3.732192152171627E-24182 人数181 1.8916636669956916E-24183 人数182 9.536081538054923E-25184 人数183 4.781115856971393E-25185 人数184 2.3840144855204884E-25186 人数185 1.1822129468156427E-25187 人数186 5.830106323404897E-26188 人数187 2.8591555105072787E-26189 人数188 1.3943315807841226E-26190 人数189 6.761571232667588E-27191 人数190 3.260382895176333E-27192 人数191 1.5632015565451854E-27193 人数192 7.451995173278288E-28194 人数193 3.5320514395422914E-28195 人数194 1.6644234763571782E-28196 人数195 7.797732338337783E-29197 人数196 3.63183107546654E-29198 人数197 1.6815924746677324E-29199 人数198 7.739955475628124E-30200 人数199 3.5413053423047515E-30201 人数200 1.61057116536134E-30202 人数201 7.280686593494693E-31203 人数202 3.2713323933076926E-31204 人数203 1.4609009942182749E-31205 人数204 6.484019649905391E-32206 人数205 2.860083673207741E-32207 人数206 1.2537394156314248E-32208 人数207 5.461513105172664E-33209 人数208 2.3641697794601874E-33210 人数209 1.0169203240639937E-33211 人数210 4.346304583123179E-34212 人数211 1.845697430889915E-34213 人数212 7.787353688669575E-35214 人数213 3.2642996814747587E-35215 人数214 1.3593845289569194E-35216 人数215 5.6237758653215976E-36217 人数216 2.311149383776688E-36218 人数217 9.434590671291894E-37219 人数218 3.825547308889449E-37220 人数219 1.540705857348351E-37221 人数220 6.162847688590297E-38222 人数221 2.448264332325108E-38223 人数222 9.65894494734862E-39224 人数223 3.7842049201358714E-39225 人数224 1.4722173566589267E-39226 人数225 5.687219824825991E-40227 人数226 2.1814087262180283E-40228 人数227 8.307318636057621E-41229 人数228 3.140863081846686E-41230 人数229 1.1789045664531903E-41231 人数230 4.3926506507983883E-42232 人数231 1.6246864920466093E-42233 人数232 5.964630353558949E-43234 人数233 2.1734235686582143E-43235 人数234 7.860090236801233E-44236 人数235 2.8210324918437226E-44237 人数236 1.0047562912485759E-44238 人数237 3.551074402931366E-45239 人数238 1.2453146675840465E-45240 人数239 4.333035243861282E-46241 人数240 1.495795423030422E-46242 人数241 5.12261460585867E-47243 人数242 1.7402950184095124E-47244 人数243 5.864588383174268E-48245 人数244 1.960229648503839E-48246 人数245 6.498332842028368E-49247 人数246 2.1364506621318907E-49248 人数247 6.965455824118345E-50249 人数248 2.251859584591692E-50250 人数249 7.218333948093835E-51251 人数250 2.294060188035423E-51252 人数251 7.227906809894806E-52253 人数252 2.257497826352238E-52254 人数253 6.989011891945552E-53255 人数254 2.1445878873395627E-53256 人数255 6.521941922595186E-54257 人数256 1.9655304045358402E-54258 人数257 5.869707690407385E-55259 人数258 1.7368027451077907E-55260 人数259 5.09148655151868E-56261 人数260 1.4786345624715487E-56262 人数261 4.253638735795503E-57263 人数262 1.212005123175935E-57264 人数263 3.420205969367417E-58265 人数264 9.557913172920543E-59266 人数265 2.644814233825782E-59267 人数266 7.246127387510261E-60268 人数267 1.9654048575328666E-60269 人数268 5.277023685478768E-61270 人数269 1.402399666335672E-61271 人数270 3.6885369352189833E-62272 人数271 9.600391200109067E-63273 人数272 2.4724530828879777E-63274 人数273 6.299736335181651E-64275 人数274 1.5878945528375195E-64276 人数275 3.958900673165118E-65277 人数276 9.761774449141333E-66278 人数277 2.3802936164636327E-66279 人数278 5.738852553593375E-67280 人数279 1.3679061178710478E-67281 人数280 3.22304841672974E-68282 人数281 7.505816790809824E-69283 人数282 1.7273867022622438E-69284 人数283 3.928078130054646E-70285 人数284 8.824834187987433E-71286 人数285 1.9584130456989745E-71287 人数286 4.292468752695527E-72288 人数287 9.290674449052923E-73289 人数288 1.9854319500577967E-73290 人数289 4.1885051271614915E-74291 人数290 8.721398452363574E-75292 人数291 1.7920950827914942E-75293 人数292 3.63334470890731E-76294 人数293 7.26680462913946E-77295 人数294 1.433475239216766E-77296 人数295 2.7884506433561695E-78297 人数296 5.3478058270752784E-79298 人数297 1.0109730292337928E-79299 人数298 1.8834910520811563E-80300 人数299 3.4574322905015665E-81301 人数300 6.251916814200046E-82302 人数301 1.1133773515771803E-82303 人数302 1.9522636493420678E-83304 人数303 3.369732435059139E-84305 人数304 5.724055188006599E-85306 人数305 9.56644702516075E-86307 人数306 1.5726036526515317E-86308 人数307 2.54207876591672E-87309 人数308 4.039569447862928E-88310 人数309 6.308533415953783E-89311 人数310 9.679107657439067E-90312 人数311 1.458536596603439E-90313 人数312 2.1578977935991347E-91314 人数313 3.1334805796466244E-92315 人数314 4.4642769889133005E-93316 人数315 6.237960732218878E-94317 人数316 8.54544233246896E-95318 人数317 1.1472370130425093E-95319 人数318 1.5087509775790893E-96320 人数319 1.942850112793478E-97321 人数320 2.4486219988417057E-98322 人数321 3.0189760918612455E-99323 人数322 3.639473933982971E-100324 人数323 4.287797263191564E-101325 人数324 4.934142460106241E-102326 人数325 5.542743012662612E-103327 人数326 6.074563384431801E-104328 人数327 6.4909943254637144E-105329 人数328 6.758148030622761E-106330 人数329 6.851153981072421E-107331 人数330 6.7577494475310795E-108332 人数331 6.480487478442585E-109333 人数332 6.03706680229222E-110334 人数333 5.458600688642653E-111335 人数334 4.786024515931745E-112336 人数335 4.0652069499352986E-113337 人数336 3.341586009428232E-114338 人数337 2.655231198781569E-115339 人数338 2.0371141942921878E-116340 人数339 1.50708525796149E-117341 人数340 1.073677804760819E-118342 人数341 7.354978850568769E-120343 人数342 4.836880495131281E-121344 人数343 3.048399199819024E-122345 人数344 1.8377226764725207E-123346 人数345 1.057529652618079E-124347 人数346 5.795953596854461E-126348 人数347 3.017806763933968E-127349 人数348 1.4886386877339791E-128350 人数349 6.935509412587238E-130351 人数350 3.0412786807910636E-131352 人数351 1.2503363845348714E-132353 人数352 4.798005970719257E-134354 人数353 1.7097913604314834E-135355 人数354 5.6247790605897E-137356 人数355 1.6964224108450512E-138357 人数356 4.652033303088953E-140358 人数357 1.1484032661324103E-141359 人数358 2.5207899688523915E-143360 人数359 4.843970484385247E-145361 人数360 7.984766959369045E-147362 人数361 1.098347996087053E-148363 人数362 1.2119876239193127E-150364 人数363 1.0098578391715748E-152365 人数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值的伪造文件，这非常困难。
密码学经典之生日悖论与生日攻击【详解】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。