about 50% change of having a same birthday when there are 23 people!
P(n) = prob that at least two have a same BTD when there are n persons
P(n) = 1 - P'(n)
(P'(n) = no one has same BTD)
P(1) = 1
P(2) = 1 * (365-1)/365
P(3) = 1 * (365-1)/365 * (365-2)/365
susceptibility : 민감성
communication theory of secrecy system
similar to "noisy channel problem"
i.e) A user wishing to send a message over a noisy channel must add redundancy to allow detection/correction of errors.
암호화되기전 (pri) Key의 확률, Message의 확률과
암호화 된 후 (post) 공격자가 cipher text를 통해 가능한 key와 message를 계산하는 가능성
🤔 IF P(M|C) = P(M) for all C & M
attacker gain NO info by intercepting C
= c가 강탈되었을때조차 M을 (랜덤) 선택하는 확률과 같다.
= c를 강탈해도 M에 대한 정보를 얻는 것이 없다
🤭 So Perfect Securecy is
1. P(M|C) = P(M) for all C & all M
2. P(C|M) = P(C) for all C & all M
🤭 So Perfect System is
= as many C's as M's
= at least one K transforming any M into these C's.
this works for guessing imppossible XXD
these are neccessary and sufficient condition !
measure of unpredictability in random variable
(높을 수록 예측하기 힘들다!)
1) Political Poll
2) Coin Flipping (fair coin case)
Message Entrophy
= amount of info produced / when a message is chosen
Key Entropy
= amount of info produced / when a key is chosen
the amount of uncertainty introduced into the system / cannot be greater than the key uncertainty.
K uncertanity is at least M uncertainty
(K엔트로피 >= M엔트로피) = M info is perfectly concealed
occurs when all M's are equally probable (i.e. totally random)
Conditional entropies of K and M
(i.e., unpredictability of the K and M given an intercepted C.)
N = intercepted된 C 일부분 길이
H(K, N|C) is a non-increasing function of N
i.e., it's theoretically easier to determine the key as more C is intercepted. C가 많이 intercept될수록 K를 determine 하기 쉬워짐
Mutual Info
- I(M|C) = C가 주어졌을때 M에 대해 얻을수있는 정보의 양
- I(K|C) = C가 주어졌을때 K에 대해 얻을 수 있는 정보의 양
I(M|C) = H(M) - H(M|C)
"new info revealed knowing C"
= "uncertainty" - "uncertainty after knowing C"
How to achieve perfect secrecy?
I(M|C) = H(M) - H(M|C) = 0
H(M) = H(M|C)
= C and M are statistically independent
also
H(M) <= H(K)
= 적어도 K엔트로피는 M엔트로피보다 커야!
= num of M bits <= num of K bits
since..
otherwise,,
like H(M) > H(K) !
Cryptanalyst can obtain a lot of info about plaintext.