대수학 공개키 RSA

▶ 작은 e를 사용한 경우
암호화 과정에서 효율성 향상을 위하여 작은 지수 e(예를 들어 e=3)를 사용하는 경우에 대하여 생각해 보자. 만약 사용자 A가 같은 메시지 m을 3명의 사용자에게 보낸다면 다음과 같은 암호문을 보내야 한다. 각 사용자의 공개키는 3)이라 하자.

〓 mod , i 〓 1, 2, 3

, , 는 높은 확률로 서로 소이므로 Gauss 알고리즘을 사용하여 다음 식을 만족하는 x를 구할 수 있다.

x 〓 mod
x 〓 mod
x 〓 mod

이므로 x 〓이다. 그러므로 3차 방정식을 풀어 m을 구할 수 있다. 따라서, 작은 e를 사용하는 것은 문제가 생길 수 있다. 이러한 문제를 해결하기 위해서는 메시지 m에 랜덤비트(64비트 정도)를 패딩하는 것도 한 가지 방법이 될 수 있다. 이러한 경우 Broacasting 시 각각 다른 랜덤 수를 사용하면 문제가 없다. 또한 작은 메시지 m을 쓰는 것도 문제가 될 수 있으나, 이러한 문제도 랜덤 비트를 패딩하여 해결할 수 있다.

▶ Forward Search 공격
만약 메시지 공간이 작거나 예상 가능한 경우 전수조사 공격(brute force attack)이 가능하다. 이런 문제 또한 랜덤 비트를 패딩하여 해결할 수 있다.
…