Skip to main
RSA에 대하여
- Ron Rivest, Adi Shamir, Leonard Adleman에 의해서 만들어졌으며, 이름의 앞글자를 따서 RSA가 되었다 (c:BLUERivest, c:BLUEShamir, c:BLUEAdleman)
- RSA의 제안 이유
- 당시에 NBS (National Breau of Standards)에서 Data Encryption Standard라는 표준을 제정함
- 그러나 이 방식은 비밀키 방식이라 키 교환에 안전한 통신 채널이 필요했음
- 비밀키 방식 = 비밀키 한 개로 암호화와 복호화를 진행함.
- 따라서 전화선을 감청해서 비밀키를 알아낸다면, 이후의 모든 암호화를 깰 수 있다.
- 따라서 “안전하지 않은 통신 채널에서 비밀키를 교환하는 방법"을 찾기 위해 RSA가 제안됨
- 공개키 방식을 사용하면 모든 대화 내용을 감청해도 복호화가 불가능하다
- 공개키 암호화 방식으로 공개키와 개인키 두 개의 키를 사용한다
- 공개키 (public key)는 모두가 알고있고 모든 사람들이 메시지를 암호화하는데 사용된다.
- 공개키로 암호화된 메시지는 개인키(private key)을 사용해야만 합리적인 시간 내에 복호화가 가능하다
- 반대로 개인키는 혼자만 알고있고, 스스로 암호화하는데 사용된다.
- 개인키로 암호화된 메시지는 공개키로만 복호화가 가능하다.
- 이를 통해서 전자서명을 구현한 가능한 최초의 알고리즘이다.
- 자신이 미리 공개한 공개키로만 풀리는 내용이 있다면, 서명된 것으로 본다.
- 다른 사람은 개인키를 볼 수 없고, 공개키로 암호화를 해도 다시 공개키로는 복호화되지 않기 때문에 서명이 유효하다.
- 공개키 방식에서 키 교환이 안전한 이유
- 양쪽의 A, B는 자신의 공개키를 교환한다.
- A가 메시지를 B의 공개키로 암호화한다 (이후 m_b으로 호칭)
- B가 m_a를 송신받고 자신의 개인키로 복호화해서 메시지를 읽는다.
- 다시 B가 메시지를 A의 공개키로 암호화한다. (이후 m_a로 호칭)
- A가 m_a를 송신받고 자신의 개인키로 복호화해서 메시지를 읽는다.
- 이 과정에서 송신된 A의 공개키, B의 공개키, m_b, m_a 모두 노출되었다고 해도 공격자는 읽을 수 없다.
- m_b는 b의 공개키로 암호화했기 때문에 공격자가 가지고 있는 b의 공개키로 복호화할 수 없다.
- 마찬가지로 a의 공개키만 가지고 있기 때문에 m_a를 읽을 수 없다.
- 결정론적 튜링머신으로 큰 숫자를 소인수 분해하기 어렵다는 사실에 기반하고 있다
- 쇼어 알고리즘을 통해 양자 컴퓨터에서는 다항시간 내에 소인수 분해가 가능한 것이 증명되었다
- 따라서 이론상 양자 컴퓨터의 상용화와 함께 RSA 암호의 수명이 끝나게된다
- 하지만 양자컴퓨터의 도입이 멀었기 때문에 아직까지는 안전한 암호로 취급된다
- 수학적 개념
- 모듈러 연산을 사용하면 모든 정수 m (0 <= m < n)에 대해 매우 큰 세 개의 양의 정수 e, d, __n__을 구하는 것이 실용적이라는 사실에 기반한다.
- $$(m^e)^d \equiv m \pmod {n}$$
- $$\equiv$$는 모듈러 동치라는 뜻이다. 이는 $$(m^e)^d$$를 __n__으로 나눈것이나 __m__을 __n__으로 나눈것이나 나머지가 같다는 뜻이다.
- C언어 등의 나머지 연산(%)를 사용하자면, 다음과 같다. $$(m^e)^d % n == m % n$$
- $$(m^d)^e \equiv m \pmod {n}$$
- __d__와 __e__의 순서가 바뀌어도 동일하다.
- 이때 e, n 심지어 __m__을 알더라도 __d__를 구하는 것은 매우 어려울 수 있다.
- 여기서 메시지를 __m__이라 보았을때, 공개키는 __e__이고, 개인키는 __d__라고 할 수 있다.
- 예를들어 개인키(d)로 암호화 한다는 것은 메시지(m)을 d 제곱하는 것과 동일하다. ($$m^d$$)
- 공개키(e)로 복호화 하는 경우 $$m^d$$를 e 제곱한 뒤 $$(m^d)^e$$ 이를 $$\mod n$$ 연산하는 것과 동일하다.
- 공개키로 암호화해도 __d__와 __e__의 순서가 다를 뿐 동일한 결과를 얻는다.
- 키 생성
- 두 개의 큰 소수 __p__와 __q__를 선택한다.
- __p__와 __q__는 무작위로 선택되어야 하며, 둘 다 크고 차이도 커야 한다.
- 당연히 두 소수는 비밀로 유지되어야 한다
- $$n=p*q$$을 계산한다
- 개인키로 사용할 __d__를 $$\gcd(d, (p-1)*(q-1)) = 1$$에 따라 구한다
- d는 충분히 크고, 랜덤하며, $$(p-1)*(q-1)$$에 대해 서로소여야 한다
- 마지막으로 공개키로 사용할 __e__를 $$e * d \equiv 1 \pmod {(p-1)*(q-1)}$$에 따라 구한
- 공개키 암호화 -> 개인키 복호화
- message = 15
- 15^e mod n = 15^17 mod 2773 = 1392
- 1392^d mod n = 1392^157 mod 2773 = 15
- 공개키 암호화 -> 공개키 복호화
- message = 16
- 16 ^ e mod n = 16 ^ 17 mod 2773 = 729
- 729 ^ e mod n = 729 ^ 17 mod 2773 = 1051
- 개인키 암호화 -> 개인키 복호화
- message = 17
- 17 ^ 17 mod 2773 = 1071
- 1071 ^ 17 mod 2773 = 2721
- 암호화와 복호화
- 메시지 M을 숫자 m으로 변환한다. $$(m < n)$$
- 이 방법은 어떤 방법이던 상관없다.
- 텍스트를 암호화하는게 아니라, 논리적으로 “숫자"를 암호화하기 위함이다.
- m에서 다시 M으로 만드는 방법이 존재해야 하며, 양쪽 모두 이 방법을 알고 있어야 한다.
- 예) 알파벳을 ascii코드로 변환해서 한 글자씩 암호화/복하화 하는 방식
- $$m^d \pmod {n}$$를 전송한다.
- 복호화
- 전달받은 $$m^d \pmod {n}$$에 대해 e 제곱한다.
- 이는 $$(m^d)^e \pmod {n}$$과 동일한 값을 만들게된다
- 참고자료 (도움이 된 순서로)
Til,
Published,
Area 스터디 rsa