골드바서-미칼리

Goldwasser-Micali cryptosystem, GM

이차 잉여 판정의 어려움을 이용해 만든 최초의 확률 공개키 암호

1982년 셰피 골드바서와 실비오 미칼리가 제안했다. 같은 평문을 암호화해도 매번 다른 암호문이 나오므로 암호문에서 평문의 어떤 부분 정보도 얻을 수 없다. 이 성질을 의미론적 안전성이라 하며, 그것을 증명한 최초의 공개키 암호다.

바탕이 되는 문제

• 합성수 n = pq 의 소인수를 모르면 어떤 수가 이차 잉여(제곱 잉여)인지 판정하기 어렵다.
• 정확히는 야코비 기호가 1 인 수 중에서 이차 잉여와 비잉여를 구분하는 문제다.
• 소인수를 알면(개인키) 판정이 쉬우므로 복호화가 가능하다.

동작

• 키 생성 : 큰 소수 p, q 로 n = pq 를 만들고, 야코비 기호가 1 이면서 이차 잉여는 아닌 x 를 고른다. 공개키는 (n, x), 개인키는 (p, q)
• 암호화 : 평문을 비트 단위로 나누고, 비트마다 난수 r 을 뽑아 0 이면 r² mod n, 1 이면 x·r² mod n 을 보낸다
• 복호화 : 개인키로 암호문이 이차 잉여인지 판정한다. 이차 잉여면 0, 아니면 1

특징

• 확률 암호 : 난수 r 때문에 같은 평문의 암호문이 매번 달라진다.
• 배타적 논리합에 대해 준동형이다.
• 평문 1비트가 n 크기의 암호문이 되어 암호문이 매우 커진다. 그래서 실무에는 쓰이지 않고 이론적 기준으로 쓰인다.

같이 보기

• 공개키 암호화
• 엘가말
• 동형 암호