대수학 공개키 RSA

목차

1. 모델설정

2. 문제점 도출

3. 해답도출

4. 이론 정리 및 보완

5. 관련된 이론

본문내용

perty라 한다. 이러한 성질을 적절히 이용하면 능동적 선택 암호문 공격(adaptively chosen-ciphertext attack)이 가능하다.
공격자가 c 〓 mod n을 복호화하려고 한다고 하자. 그리고 A는 공격자가 원하면 언제든지 복호화해 준다고 하자. 공격자는 c를 숨기기 위하여 랜덤수 x ∈를 생성하고 c mod n을 A에게 보낸다. 그러면 A는 다음을 계산하여 공격자에게 보내준다.
m 〓 〓 mx mod n
공격자는 이를 x로 나누어 m을 구할 수 있다.
이러한 공격을 막는 방법은 평문 m의 구조를 제한하는 것이다. 좀더 좋은 방법은 Bellare-Rogaway의 plaintext-aware encryption 방법이 있다.
▶ 공통의 modulus n을 사용하는 경우
앞에서 언급한 바와 같이 를 아는 사용자는 p와 q를 구할 수 있다. 공격자가 같은 m을 두 명의 사용자 ((n,), (n,))에게 보내는 암호문 과를 도청했다고 하자. 그러면gcd(,) 〓1 이므로 먼저 공격자는 유클리드 알고리즘을 사용하여 다음을 만족하는 r과 s를 구할 수 있다.
＋ ＝ 1
그리고 r을 음수라 가정하면 다시 유클리드 알고리즘을 사용하여 을 구할 수 있고 따라서 평문 m을 다음과 같이 복원할 수 있다.
＝ m mod n
▶ 순환 공격
c 〓 mod n을 암호문이라 하자. 그러면 어떤 k가 존재하여 ＝ c mod n을 만족한다. 그러면 ＝ c mod n이 성립한다. 이러한 공격을 순환 공격(cycling attack)이라 한다.
일반화된 순환 공격을 다음을 만족하는 가장 작은 양의 정수 u를 찾는 문제이다.
f ＝ gcd(－ c, n)＞1
만약 ＝ c mod p이고 ＝ c mod q라면 f ＝ p이고 반대의 경우라면 f ＝ q가 되어 n을 소인수분해할 수 있다. 만약 둘 다 성립한다면 f ＝ n이 되고 ＝ m mod n이므로 공격에 성공한다.
그러나 소인수분해가 어려운 문제라 가정하였으므로 이 문제는 큰 위협이 되지 못한다.
▶ 메시지 숨기기
＝m mod n이 되는 메시지를 노출된 메시지(unconcealed message)라 한다. 실제로 노출된 메시지의 수는 정확히
[1＋gcd(e－1, p－1)][1＋gcd(e－1, q－1)]
이다. e, p, q는 모두 홀수이므로 위의 수는 9이상이지만, p, q가 랜덤하게 선택되었다면 노출된 메시지 공간에서 매우 작은 비율이므로 큰 위협은 되지 못한다.

키워드

대수학,   공개키,   RSA