쇄도 효과(Avalanche Effect)
-
쇄도 효과(Avalanche Effect, 눈사태 효과)는 암호 알고리즘에서 입력값의 미세한 변화(1비트 변경)가 출력값(암호문/해시값)에 대규모의 무작위적인 변화를 일으키는 특성입니다.
- 이는 암호 시스템의 보안성을 보장하는 핵심적인 성질로, 입력과 출력 간의 연관성을 파악하기 어렵게 만들어 해독을 불가능하게 합니다.
-
핵심 특징 및 원리
-
작은 변화, 큰 결과: 평문이나 키를 단 1비트만 바꿔도 출력값의 약 50%가 완전히 달라져 예측 불가능한 결과를 낳습니다.
-
보안성 향상: DES, AES 같은 대칭키 암호나 SHA-256 같은 해시 함수에서 이 효과가 클수록 보안이 우수합니다.
-
눈사태 비유: 작은 눈덩이가 굴러가면서 대규모 눈사태가 되는 것과 같아, 입력값의 작은 차이가 암호화 과정에서 증폭되어 큰 변화를 만들어냅니다.
-
-
반도체 분야 (애벌랜치 항복)
- 이와 유사하게 반도체 소자에서 높은 역방향 전압이 걸릴 때 전류가 급격히 증가하는 현상을 애벌랜치 항복(Avalanche Breakdown)이라고 합니다.
만약 암호 알고리즘의 쇄도 효과가 크지 않다면, 그러한 성질을 이용하여 암호분석이 더 쉽게 가능할 수 있다. 따라서, 일반적으로 암호 알고리즘은 쇄도 효과가 충분히 강해야 한다.
비둘기 집의 원리
우리나라 전체 국민 중 같은 개수의 머리카락을 가진 사람이 몇 명인지도 산술적으로 추정해 볼 수 있어요
5200만을 20만으로 나누면 260이 되니 적어도 260명은 같은 수의 머리카락을 가지고 있는 셈이 된답니다.
http://newsteacher.chosun.com/site/data/html_dir/2022/03/23/2022032302366.html
-
네 마리의 비둘기를 3곳의 비둘기 집에 넣으려면 어떻게 해야 할까요?
- 이 경우 두 마리 이상 비둘기가 들어간 집이 반드시 생기겠죠.
-
19세기 독일의 수학자 페터 디리클레(1805~1859)는 이런 내용의 '비둘기 집의 원리'를 통해 다양한 수학 원리를 밝혀냈는데요. 지극히 당연하게 보이는 이 원리가 다양한 수학적 문제를 해결하는 데 쓰인다는 사실 알고 있나요?
-
이 원리의 핵심은 'n+1개'의 물건을 'n개'의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어간다는 점인데요.
- 간단한 예를 들면 구슬 30개를 7명의 사람에게 나눠줄 때 적어도 한 명은 5개 이상의 구슬을 받게 된다거나, 엘리베이터에 세 사람이 탔는데 층 버튼이 2개만 눌려 있을 때 적어도 두 사람은 같은 층에 살고 있다거나 하는 등의 경우가 해당돼요.
-
이 원리는 다양한 분야에 응용할 수 있답니다. 예컨대 학생 수가 13명인 학원에서 같은 달에 태어난 사람은 반드시 두 명 이상 존재하게 되는데요. 이것도 이 원리를 이용해서 설명할 수 있어요.
-
1년이 12개월이기 때문에 12개월을 비둘기 집으로 생각하고 이 집에 13마리의 비둘기를 넣는다고 생각하면, 어떤 방에는 적어도 2명이 들어가야 하는 상황이 생기는 거예요.
-
실제로 확인할 방법은 없지만, 이 같은 원리를 이용하면 우리나라 전체 국민 중 같은 개수의 머리카락을 가진 사람이 몇 명인지도 산술적으로 추정해 볼 수 있어요.
-
지난 1월 기준 우리나라 인구는 약 5200만명인데요. 사람의 머리카락은 많으면 약 20만 가닥까지 자란다고 해요. 그러니 계산하기 쉽게 최대 머리카락 수를 20만 가닥으로 가정해 볼게요.
-
처음 설명했던 비둘기 사례에 대입해 보면, 이 경우 5200만명의 사람이 비둘기가 되는 거예요.
-
머리카락이 하나도 없는 사람부터 20만개까지 있는 사람들이 집에 나눠 들어가야 하는 비둘기가 되는 거죠.
-
머리카락 수가 같은 사람이 몇 명이냐는 질문은 집이 같은 비둘기가 몇 마리냐는 질문과 같아져요.
- 즉, 20만개의 비둘기 집에 5200만 마리의 비둘기를 넣는 문제가 되는 거예요.
-
5200만을 20만으로 나누면 260이 되니 적어도 260명은 같은 수의 머리카락을 가지고 있는 셈이 된답니다.
-
-
