Pretty Good Privacy(PGP)
PGP는 중앙에서 인증을 담당하는 TA가 존재하지 않는다. 대신, 각각의 사용자들이 증명서를 가지며, 이 증명서에 의한 신뢰는 다른 사용자의 다양한 검증 정도에 의해 검증된다. 예를 들어, Alice가 Bob을 알고 있다면, Alice는 Bob을 직접적으로 검증할 수 있고, Bob의 공개키를 유효한 것으로 인정할 수 있다. Charles가 Alice와 Alice의 공개키를 신뢰하며 그렇기 때문에, Charles는 Bob의 증명서에 서명된 Alice의 서명을 확인할 수 있고, Bob의 증명서를 신뢰할 수 있다. 그러나, 이것이 Charles가 Bob을 신뢰한다는 것을 의미하는 것은 아니다. Charles는 다만 Bob의 공개키를 신뢰할 뿐이다. 즉, Bob의 서명은 유효하더라도, 이것이 Bob의 증명서 자..
더보기
Hashing and Signing
어떤 메세지 전체에 대해서 서명을 하는 것은, 메세지가 길 경우 불리한 점이 많다. 이와 같은 문제를 해결하기 위해, 해시 함수가 사용된다. 즉, 서명은 메세지 자체보다는 메세지의 해시값에 대해서 이루어진다. 해시 함수 h(m)은 알려져 있으며, Alice는 h(m)을 계산한다. h(m)은 메세지 m에 비해서 크기가 줄어든 결과를 출력하며, h(m)에 대한 서명을 훨씬 빨리 이루어진다. Alice는 sig(h(m))을 계산하며, 이것을 원래의 메세지 m에 대한 서명으로 사용하게 된다. 즉, (m, sig(h(m))은 원래의 메세지의 서명을 대신하게 된다. 이와 같은 방법은 안전한가? 예를 들어, Eve가 Alice의 서명된 메세지 (m, sig(h(m))을 가지고 있다고 해보자. Eve는 Alice의 메..
더보기
ElGamal Signature
ElGamal Encryption 또한 디지털 서명에 응용될 수 있다. 예를 들어, Alice가 어떤 메세지에 서명을 하려고 한다. 먼저, Alice는 큰 Prime Number p와 Primitive Root α를 선택한다. 그리고, 1 ≤ a ≤ p - 2인 a를 선택하고, β ≡ α^a (mod p)를 계산한다. a는 비밀로 유지해야 한다. 공개키는 (p, α, β)가 된다. Alice가 메세지 m에 서명하기 위해서, 다음의 과정을 따른다. 1. 공개되지 않은 임의의, gcd(k, p - 1) = 1을 만족하는 k를 선택한다. 2. r ≡ α^k (mod p) (0 < r < p)를 계산한다. 3. s ≡ k^(-1) * (m - ar) (mod p - 1)을 계산한다. 서명된 메세지는 (m, r,..
더보기
RSA Signature
RSA 디지털 서명은 RSA 암호화와 비슷한데, 상대의 공개키로 메세지를 암호화하는 것이 아니라, 자신의 비밀키로 암호화한다는 점이 다르다. 이 방식으로 디지털 서명을 하게 되는데, 이 서명이 정당한 서명인지 여부를 확인하려면, 공개키로 풀어봐서 원래의 문서와 비교해보면 된다. RSA Signature 과정은 다음과 같다. 서명하고자 하는 Alice는 다음의 과정을 거친다. 1. Alice는 커다란 두 Prime Number p, q를 선택하고, n = pq를 계산한다. 그리고, 1 < e < Φ(n), gcd(e, Φ(n)) = 1인 e를 선택하여 e * d ≡ 1 (mod Φ(n))인 d를 계산한다. Alice는 (e, n)을 공개하고, d는 비밀키로, p, q는 폐기하거나 비밀로 유지한다. 2. A..
더보기
Brirthday Attack on Discrete Logarithm
큰 Prime Number p의 경우, Lα(β)의 경우를 생각해보자. 즉, β ≡ α^x (mod p)에서 x를 구하자는 것인데, 이것은 discrete logarithm 문제를 해결하는 데 Birthday Attack을 적용해본다는 의미이다. 먼저, 일반적인 Birthday Attakc의 경우와 마찬가지로, root(p) 길이를 가지는 두 목록을 만든다. 1. 첫 번째 목록은, 임의로 선택되는 k 값에 대한, α^k (mod p) 2. 두 번째 목록은, 임의로 선택되는 l 값에 대한, βα^(-l) (mod p) 두 목록이 구해졌다면, 계산 결과가 일치하는 값을 찾는다. α^k ≡ βα^l이라면, α^(k + l) ≡ β이고, 구하고자 하는 x 값을 알 수 있다. 이 확률은 50%를 조금 상회할 것이..
더보기
Birthday Attack, Birthday Paradox
만약, 한 방에서 같은 생일을 가진 사람이 존재할 확률이 50% 이상이 되려면, 몇 명의 사람이 있어야 할까? 그 답은 놀랍게도 23명이면 충분하다. 윤년을 생각하지 않더라도 1년이 365일이므로, 23명이란 표본의 수는 일반적으로 생각되는 것보다 훨씬 적은 수이다. 이것을 생일 파라독스(Birthday Paradox)라고 한다. 먼저, 이 사람들이 모두 다른 생일을 가지고 있을 확률을 알아보면, 첫 번째 사람은 365일 중 어떤 날을 선택할 수 있다. 두 번째 사람은 첫 번째 사람과 다른 날을 선택해야 하며, 이 확률은 (1 - 1 / 365)이다. 세 번째 사람은, 365일에서 선택할 수 있는 날이 2개 줄었으며, 따라서 (1 - 2 / 365)이다. 이와 같이 23명까지 전개해보면, 1 * (1 -..
더보기