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. Alice의 서명은 y ≡ m^d (mod n)이다.
3. (m, y)를 공개한다.
서명을 확인하려는 Bob은 다음의 과정을 거친다.
1. Bob은 Alice의 공개키를 가져온다.
2. z = y^e (mod n)을 계산한다. z = m이라면, Bob은 이 서명을 유효한 Alice의 서명으로 받아들일 수 있다.
만약, Eve가 Alice의 메세지 m을 위조하여 새로운 메세지 m1로 대신하려고 한다면, m1 !≡ y^e (mod n)이기 때문에 받아들여지지 못한다.
서명하고자 하는 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. Alice의 서명은 y ≡ m^d (mod n)이다.
3. (m, y)를 공개한다.
서명을 확인하려는 Bob은 다음의 과정을 거친다.
1. Bob은 Alice의 공개키를 가져온다.
2. z = y^e (mod n)을 계산한다. z = m이라면, Bob은 이 서명을 유효한 Alice의 서명으로 받아들일 수 있다.
만약, Eve가 Alice의 메세지 m을 위조하여 새로운 메세지 m1로 대신하려고 한다면, m1 !≡ y^e (mod n)이기 때문에 받아들여지지 못한다.