[2021/02/07][짤막한 이야기 - 생일 문제]

[2021/02/07][짤막한 이야기 - 생일 문제]
“생일 문제”는 임의의 수의 사람이 모였을 때 생일이 같은 두 명이 존재할 확률에 대한 이야기이며, “생일 역설”이라고도 알려져 있다.
상상하는 것과는 달리 “23명”의 사람이 모여있다면, 그 중 생일이 같은 사람이 존재할 확률이 50%를 넘어간다(=50.73%).
생일이란 365일(윤년 제외) 중 하나에 들어가기 때문에 366명이 모이면 100% 확률로 생일이 겹치는 사람이 존재한다.
이는 앞선 “비둘기집의 원리”에서도 확인하였다.
그러나 366명이 아니라 23명만 모여도 생일이 겹치는 사람이 50% 확률이 넘게 존재하게되는데, 이는 중요한 문제를 시사하게 된다.
“생일 문제”를 다시 잘 상상해보면 해쉬 함수에서 “충돌쌍”(입력값이 다르지만 동일한 해쉬값을 출력하게 하는 두 입력쌍)을 만드는 것도 아주 불가능할 것 같지는 않다.
그러나 충돌쌍을 만드는 것이 어렵지 않다면 이는 암호학에서 매우 큰 문제를 야기하게 된다.
충돌쌍을 만들기 어려운 해쉬 함수를 “충돌 저항성”을 보장한다고 표현한다.
[관련된 짤막한 이야기 - 해쉬 함수[2021/02/04]]
[관련된 짤막한 이야기 - 비둘기집의 원리[2021/02/05]]
#이야기 #루니프 #생일 #문제 #역설 #해쉬 #충돌쌍 #충돌 #저항성

[2021/02/07][Short Story - Birthday Problem]
“Birthday Problem” is a story of the probability that two people with the same birthday will exist when an arbitrary number of people are gathered, and is also known as the “Birthday Paradox”.
Contrary to imagination, if “23” people are gathered, the probability of having a person with the same birthday among them exceeds 50%(=50.73%).
Since a birthday falls on one of 365 days(excluding leap year), if 366 people gather, there is a 100% chance that the birthdays overlap.
This was confirmed in the previous "Pigeon Principle".
However, even if only 23 people rather than 366 people gather, there is a 50% chance that people with overlapping birthdays will exist, suggesting an important problem.
Reimagining the “Birthday Problem” again, it is unlikely that it would be very impossible to create a “Collision Pair”(two input pairs that have different input values but output the same hash value) in a hash function.
However, if it is not difficult to create a collision pair, this is a problem because it causes a big problem in cryptography.
The hash function, which is difficult to make a collision pair, is expressed as guaranteeing "Collision Resistance".
[Related Short Story - Hash Function[2021/02/04]]
[Related Short Story - Pigeonhole Principle[2021/02/05]]
#Story #LootNiP #Birthday #Problem #Paradox #Hash #CollisionPair #Collision #Resistance