C에서 RSA 알고리즘의 큰 정수를 조작하는 방법은 무엇입니까?

Question

RSA 암호 시스템을 C에 구현하고 싶습니다. 지금은 한 바이트에 들어 맞는 값을 암호화 할 수 있지만 (보안에 비해 너무 작음), 소수의 크기를 늘릴 때 p 및 q (따라서 모듈러스 n = pq) 및 암호화 된 값의 크기는 작동하지 않습니다.

1. (그렇지 않은 경우도 있음) N 값보다 작아야합니다 암호화 할 수있는 값 및
2. 값을 : 내 코드가 실패하는 이유는 생각

   나는 이유를 알고 n = pq 실제 값은 내가 사용하고있는 변수 유형에 저장할 수 없기 때문에 올바르지 않습니다. 대신 오버 플로우됩니다.

내 질문은 어떻게하면 큰 숫자 (256 바이트, 512 바이트 등으로 묶음)를 사용하고 C로 조작 할 수 있습니까? 라이브러리 (예 : GMP)를 사용해야합니까?

Answer 1

C 언어에는 임의 정밀도 정수 ("bignum") 산술 연산에 대한 기본 지원이 없으므로이를 제공하는 라이브러리 (반드시 GMP가 대중적인 선택이라고 들었습니다)를 사용하거나 그것을 처리 할 자체 코드.

당신이 할 - 그것 - 자신의 경로를 선택하면, 나는 K이 비트의 수입니다 each array element representing a digit in base 2^k으로, 합리적으로 큰 고유 부호없는 정수 유형의 배열 (예를 들어 uint32_t 또는 uint64_t)로 숫자를 나타내는 것이 좋습니다 기본 원시 정수로

RSA의 경우 0부터 RSA 모듈러스 n까지의 숫자로 모든 수치가 지정되므로 음수 값을 나타내는 것에 대해 걱정할 필요가 없습니다. 원할 경우 상한값 인 n을 사용하여 특정 RSA 인스턴스의 모든 값에 기본 숫자 2를 ^k 자릿수로 고정하여 명시 적으로 저장할 필요가 없도록 할 수 있습니다 각 디지트 배열 옆에 있습니다.

---

ps. "textbook RSA"은 보안 암호화 체계가 아닙니다. 의미 론적으로 보안을 설정하려면 OAEP과 같은 적절한 무작위 패딩 체계를 포함해야합니다. 덧붙여서 덧붙여 지든 그렇지 않든간에, 일반 RSA는 모듈러스보다 짧은 메시지만을 패딩에 의해 차지 된 길이를 뺀 값으로 암호화 할 수 있습니다. 긴 메시지를 암호화하려면 hybrid encryption을 사용합니다. 먼저 임의의 키로 대칭 암호화 체계 (AES-SIV 권장)를 사용하여 메시지를 암호화 한 다음 RSA로 키를 암호화합니다.