어려운 문제의 안전성은 여전히 연구가 계속되고 있는 분야다.

공개키 암호 알고리즘은 소인수분해, 이산대수 등 어려운 수학 문제를 근거로 키를 공개해도 개인키 한 쌍을 찾기 어렵다는 특성을 이용한 암호방식이다. 이에 대한 공격은 암호문서에서 직접 검토를 찾기보다는 암호체계의 이론적 근거가 되는 어려운 수학 문제를 해결함으로써 공개키에서 비공개키를 찾아내는 방식으로 진행되어 왔다. 물론 공개키 암호 알고리즘의 안전성과 그 기반이 되는 어려운 문제의 안전성은 여전히 연구가 계속되고 있는 분야다.

예를 들어, 마이크로 디그레이션 문제에 근거한 RSA 알고리즘에서는 2개의 큰 소수점 p와 q를 선택하여 그들의 제품 n=pq를 계산하고, mod(n)에 대한 역수 e와 d를 계산하고, 공개(n, e)를 오픈 키로 공개하고, d를 개인 키로 유지한다. 이때 사용하는 p와 q는 비밀 키로 저장되거나 기억에서 지워진다. 공격자는 공개 키(n, e)를 알고 있으며 개인 키 d를 찾기를 원한다. 공격자가 공개키 n을 하위 인덱싱할 수 있는 경우 p와 q를 찾아 개인키 d를 계산한다.

현재는 1024비트 이상의 공용키를 사용하는 것이 좋다. 국내 최고 인증기관인 전자서명인증센터는 2048비트 RSA 공개키를 활용해 최고 안전성을 추구한다. 공개키 암호의 안전성을 높이기 위해 첫 번째 대책은 키 길이를 늘리는 것이지만 키 길이를 늘리면 그에 따른 계산량이 늘어난다는 단점이 있다.

암호학자들은 미세수화 문제를 해결하기 위해 노력해 왔으며, 사분법, 숫자 필드 시드, GNFS와 같은 미세수화 기술을 연구하고 있다.

한편 이산대수 문제를 기반으로 한 공개키 알고리즘도 널리 사용되고 있으며 이산대수 문제를 푸는 데는 소인자 가수분해 문제 해결과 유사한 수준의 계산이 필요하다고 널리 인식되고 있다.