[2021/02/05][짤막한 이야기 - 비둘기집의 원리]

[2021/02/05][짤막한 이야기 - 비둘기집의 원리]
“비둘기집의 원리”는 N+1마리의 비둘기를 N개의 집에 넣는 경우 최소한 한 집에는 비둘기가 두 마리 이상 들어가게 된다는 원리이다.
해당 원리는 귀류법으로 쉽게 증명할 수 있으며, 암호학에서는 매우 기본적이며 중요한 원리에 해당한다.
특히, 손실 압축(Lossy Compression)과 비손실 압축(Lossless Compression)에 대한 이야기에서 매우 중요하게 다루어진다.
앞선 포스팅에서의 해쉬 함수는 대표적인 손실 압축 함수에 해당하는데, 손실된 부분은 복원이 되지 않기 때문이다.
임의 길이의 입력값으로부터 고정 길이의 출력값을 출력하는 것이 해쉬 함수인데, 이 고정 길이가 N개의 비둘기집이 되는 것이다.
임의 길이의 입력값이라는 것은 입력값의 가능 개수가 무한하다는 의미이기 때문에, 해쉬 함수는 무한한 입력값을 유한한 출력값의 수에 매핑시키게 된다.
이 경우 특정한 집에 두 마리의 비둘기가 들어가는 경우, 즉 두 개의 서로 다른 입력값이 동일한 출력값(해쉬값)을 출력하는 경우도 있다.
이를 해쉬 함수에서는 “충돌쌍”이라고 한다.
[관련된 짤막한 이야기 - 일방향 함수[2021/02/03]]
[관련된 짤막한 이야기 - 해쉬 함수[2021/02/04]]
#이야기 #루니프 #비둘기집 #원리 #귀류법 #손실 #비손실 #압축 #해쉬 #충돌

[2021/02/05][Short Story - Pigeonhole Principle]
“Pigeonhole Principle” is the principle that if N+1 pigeons are placed in N houses, at least two pigeons will fit in at least one house.
This principle can be easily proved by the proof by contradiction, and it is a very basic and important principle in cryptography.
In particular, it is very important in the story of “Lossy Compression” and “Lossless Compression”.
The hash function in the previous posting corresponds to a representative lossy compression function because the lost part cannot be restored.
It is a hash function that outputs a fixed length output value from an input value of an arbitrary length, and this fixed length becomes an N pigeonhole.
Since an input value of arbitrary length means that the possible number of input values ​​is infinite, the hash function maps an infinite number of input values ​​to a finite number of output values.
In this case, when two pigeons enter a specific house, that is, two different input values ​​can output the same output value (hash value).
This is called a "Collision Pair" in the hash function.
[Related Short Story- One-Way Function[2021/02/03]]
[Related Short Story- Hash Function[2021/02/04]]
#Story #LootNiP #Pigeon #Principle #ProofByContradiction #Lossy #Lossless #Compression #Hash #Collision