RSA 암호화 시스템

안전하지 않은 채널을 통한 Diffie-Hellman 키 교환 프로토콜은 공개 키 암호화 시스템이라는 흥미로운 분야를 불러 일으켰습니다. 첫 번째 실용적인 계획은 Rivest, Shamir 및 Adleman이 1977 년에 충분히 큰 정수를 소인수로 분해하는 것이 어렵다는 가정에 기초하여 고안되었습니다. 엔지니어이자 보안 실무자로서 RSA 암호화 시스템을 철저히 이해하는 것은 매우 중요합니다. 이 기사에서는 RSA 암호화 프리미티브, 정확성 증명 및 다양한 알려진 공격에 대해 설명합니다. 또한 벤치마킹 결과를 제시하고 RSA 암호화 프리미티브의 성능을 강조합니다.

모듈 식 산술을 기억하려면 https://medium.com/@prathyusha756/math-primer-to-understand-rsa-cryptographic-primitives-1e8e02760e7f를 방문하세요.

o u는 https://github.com/prathyusha756/Cryptography/tree/master/%20RSA

에서이 문서의 pdf를 찾을 수 있습니다.

암호화의 기본 적용은 두 당사자가 데이터를 기밀로 공유 할 수 있도록하는 것입니다.

i) 기밀 유지 : 채널을 관찰하는 모든 적에게 메시지가 보이지 않도록합니다.
ii) 무결성 : 채널을 제어하는 ​​공격자가 메일을 변조하지 않도록합니다.
iii) 인증 : 수신 엔티티가 전송을 확인할 수 있도록합니다. 엔티티.
iv) 거부 방지 : 수신자가 보낸 메시지를 나중에 거부 할 수 없도록합니다.

암호화 시스템에는 실제로 배포되는 대칭 비대칭 의 두 가지 유형이 있습니다. 대칭 암호화에서 당사자는 먼저 키를 공유하고 동일한 키를 사용하여 채널을 통해 메시지를 암호화 / 복호화합니다. 예를 들어 사용자가 삽입 / 탭을 통해 칩 카드를 사용하여 결제 할 때 칩은 비밀 키를 사용하여 암호 (MAC)를 준비하고 승인을 위해 POS 단말기로 전송합니다. 이 기사에서는 비대칭 암호화에 중점을두고 RSA 암호화 시스템을 철저히 설명하려고합니다.

1.1 비대칭 암호화
비대칭 암호화는 공개 키 암호화라고도합니다 (그림 .1 참조). 두 당사자 (예 : Alice와 Bob)는 개별적으로 키 쌍 (비밀 및 공개 키)을 생성하고 서로 공개 키를 공유합니다. Alice는 Bob의 공개 키를 사용하여 메시지를 암호화하고 Bob은 자신의 비밀 키를 사용하여 메시지를 해독합니다.

대칭 키 암호화의 경우 Alice와 Bob은 보안 채널을 통해 비밀 키를 공유합니다. 비밀 키는 암호 텍스트에서 메시지를 암호화하고 해독하는 데 사용할 수 있습니다. 일반적으로 대칭 키 암호화는 비대칭 암호화보다 훨씬 빠릅니다.

1.1.1 비대칭 암호화의 장점
1. 비대칭 키 암호화에서는 사전에 당사자간에 비밀 키를 공유 할 필요가 없으므로 키 배포 문제를 제거합니다.
2 비대칭 키 암호화에서 각 사용자는 키 쌍 ​​(공개 키, 개인 키)을 유지해야합니다. 공개 키는 공개적으로 액세스 할 수 있으므로 누구나 수신자의 공개 키를 사용하여 수신자에게 메시지를 보낼 수 있습니다. ‘n’사용자 수에 대한 대칭 키 암호화와 마찬가지로 각 사용자는 (n-1) 개의 키를 관리해야합니다. 비대칭 키 암호화에서는 하나의 개인 키만 안전하게 관리해야합니다.

1.2 보안 가정
공개 키 암호화 시스템의 보안은 다양한 계산적으로 어려운 문제 (RSA), DLP (Discrete Logarithm Problem)를 사용하여 실현할 수 있습니다. 이 기사에서 우리의 주요 관심사는 RSA 비대칭 알고리즘입니다.

2. 보안 정의
2.1 암호문 만 공격 (COA) 또는 알려진 암호문 공격 :
암호문 만 공격에서 공격자는 다음 항목에 액세스 할 수 있습니다. 암호문 세트. 공격자가 사용 가능한 암호 텍스트로 메시지를 해독하는 데 사용되는 일반 텍스트 또는 키를 얻을 수있는 경우 공격을 암호 텍스트 전용 공격이라고합니다. 모든 최신 암호는 공격이 쉽게 수행 될 수 있으므로 암호 텍스트 공격에 대한 보호를 제공하려고합니다. 공격자는 암호 텍스트를 얻기 위해 채널을 도청하기 만하면됩니다.

2.2 알려진 일반 텍스트 공격 :
Attacker는 일부 일반 텍스트 및 해당 암호 텍스트에 액세스 할 수 있습니다. 이 정보를 사용하여 공격자가 동일한 키를 사용하여 생성 된 다른 암호 텍스트를 디코딩 할 수있는 경우 공격을 알려진 일반 텍스트 공격이라고합니다. 이 공격을 수행하기 위해 공격자는 암호화 텍스트를 얻기 위해 공공 통신 채널을 도청하기 만하면됩니다. 경우에 따라 해당하는 일반 텍스트를 추측 할 수 있습니다. 예를 들어 모든 대화는 hi 또는 hello로 시작됩니다.
모든 기존 암호는 알려진 일반 텍스트 공격에 취약합니다. 예를 들어 shift cipher (Ceaser cipher), 암호 텍스트에서 한 글자를 해독 할 수 있다면 전체 암호 텍스트를 간단히 해독 할 수 있습니다.

2.3 선택된 일반 텍스트 공격 :
발신자가 선택한 일반 텍스트를 암호화하는 데 어떤 영향을 미치는지 공격합니다. 해당 암호문은 통신 채널을 통해 전송 될 때 공격자가 관찰 할 수 있습니다. 이 정보로 공격자는 개인 키와 시스템에 대한 정보를 얻으려고합니다.

2.4 선택된 암호 텍스트 공격 :
선택된 암호 텍스트 공격은 선택한 일반 텍스트 공격보다 훨씬 더 강력합니다. 선택한 암호 텍스트 공격에서 공격자는 자신이 선택한 일반 텍스트의 암호화 외에도 자신이 선택한 암호 텍스트의 암호 해독을 얻을 수 있습니다. 공격자는 시간 제한없이 이러한 암호화 및 암호 해독 블록에 액세스 할 수 있습니다. 그러나 공격자는 이러한 암호 해독 오라클을 요청하여 챌린지 된 암호 텍스트의 일반 텍스트를 가져올 수 없습니다.
선택된 암호 텍스트 보안 (CCA-secure)은 비 악성 속성을 보유합니다. 비 악성 시스템은 공격자가 주어진 암호 텍스트를 수정하면 (도전 된 암호 텍스트처럼 보이지 않음) 해독 오라클에 전송하는 것입니다. 암호 해독 오라클은 잘못된 암호 텍스트 또는 암호 텍스트 (일반 텍스트)의 암호 해독 메시지를 생성합니다. 그러나 생성 된 일반 텍스트는 원본 일반 텍스트와 관련이 없어야합니다.

3. RSA 가정 :
RSA의 보안은 큰 정수를 인수 분해하는 어려움에 따라 달라집니다.

예 : p = 885320963, q = 238855417 then
n = p * q = 211463707796206571.
’n’이 주어지면 p와 q를 찾기위한 알려진 다항식 시간 알고리즘이 존재하지 않습니다.
n을 주면 곱이 n과 같은 두 개의 고유 한 소수가 나오는 것은 매우 어렵습니다. ’n’값이 증가함에 따라 인수 분해의 어려움이 증가하면 그 숫자는 기하 급수적으로 증가합니다.
인텔 코어 머신 i5 (@ 1.8GHz)에서 20 비트 수를 분해하는 데 34ms가 걸립니다. 1024 비트 숫자를 인수하려면
(2¹⁰²⁴ / 2²⁰) * 34ms = 5.83 * 10³⁰⁰ 년 정도 걸립니다.

3.1 교과서 RSA

3.1.1 키 생성 :
1. 두 개의 큰 소수 p, q를 선택합니다.
2. n, ɸ (n)을 계산합니다. 여기서 n = p * q. ɸ (n) = (p-1) (q-1) 여기서 ɸ (n)은 오일러의 토 텐트 함수입니다.
3. ‘e'(암호화 지수)를 무작위로 선택하여 1 & lt; e & lt; ɸ (n) 및 gcd (e, ɸ (n)) = 1.
4. e * d = 1 (mod ɸ (n))이되도록‘d’(복호화 지수)를 계산합니다.
5. 공개 키 pk = (n, e).
6. 개인 키 sk = (n, d).

3.1.2 암호화 :
Alice가 Bob에게 메시지 ‘m’을 보내고 싶다고 가정 해 보겠습니다. Alice는 Bob의 공개 키 (pk)를 사용하여 메시지‘m’을 암호화합니다.

암호 텍스트 (c) = mᵉ (mod n).

3.1.3 복호화 :
Bob은 Alice로부터 메시지를받은 후 개인 키 (sk)를 사용하여 메시지를 복호화합니다.

message (m) = cᵈ (mod n).

3.1.4 RSA의 정확성
암호 텍스트‘c’를 살펴 보겠습니다. 메시지‘m’을 복구하기 위해 Bob은
1을 계산합니다. cᵈ = (mᵉ) ᵈ = mᵉᵈ (mod n).
우리는 알고 있습니다, e * d = 1 (mod ɸ (n)) = 1 + k ɸ (n). 여기서 k는 정수입니다.

2. 여기서 cᵈ = mᵉᵈ (mod n) = m ^ {1 + k ɸ (n)} (mod n) = m (m ^ {kɸ (n)}) (mod n).

x = a (mod p) 및 x = a (mod q)이면 x = a (mod p * q) 여기서 p, q는 고유 한 소수입니다. .

3. 따라서 cᵈ = mᵉᵈ (mod p) = m (mod p) 및 cᵈ = mᵉᵈ (mod q) = m (mod q) 자동으로 cᵈ = mᵉᵈ (mod n ) = m (mod n).

4. cᵈ = mᵉᵈ (mod p)

case i : 오일러의 정리에서, gcd (a, n) = 1이면 a ^ {ɸ (n)} (mod n) = 1 (mod n).

따라서 gcd (m, p) = 1이면 m ^ {ɸ (p)} (mod p) = 1 ( mod p).

cᵈ = m (m ^ {kɸ (n)}) (mod p) = m (m ^ {k * ɸ (p) * ɸ (q)}) (mod p) = m * (1) ^ {k * ɸ (q)} (mod p) = m.

case ii : 만약 gcd (m, p) = p이면 m = 0 (mod p).

따라서 cᵈ = m (m ^ {kɸ (n)}) (mod p) = 0 (mod p) = m.

따라서 cᵈ = m ^ {ed} (mod p) = m (mod p).

유사하게 cᵈ = m ^ {ed} (mod q) = m (mod q)

마지막으로 cᵈ = mᵉᵈ (mod p * q ) = m (mod n).

3.2 디지털 서명
디지털 서명은 전자 문서에 서명하는 데 사용됩니다. 진정성 (즉, 우리가 메시지를받은 사람), 무결성 (메시지는 전송 중에 변경되지 않음)을 제공합니다.
Alice가 Bob에게 메시지 (m)를 보내고 싶다고 가정 해 보겠습니다. Alice는 Bob의 공개 키 (pk)를 사용하여 메시지를 암호화합니다. Bob은 암호 텍스트 (c)를 수신하지만이 시점에서 Bob은 메시지를 보낸 사람을 모를 수 있습니다. Bob의 공개 키 pk는 공개적으로 사용 가능하므로 누구나 메시지를 보낼 수 있습니다. 디지털 서명은 Bob이 암호화 된 메시지를 처리하기 전에 Alice를 인증하는 데 도움이됩니다.

3.2.1 일반 RSA 서명 체계
일반 RSA 서명 체계에 대해 살펴 보겠습니다. 세 단계로 구성됩니다.

i) 키 생성 : 공개 키 pk = (n, e), 개인 키 생성 sk = (n, d).
ii) 서명 생성 : 메시지 (m), 개인 키 sk 및 계산 서명을 가져 오겠습니다.
? = mᵈ (mod n).
iii) 서명 확인 : 공개 키 pk를 사용하여 ?ᵉ (mod n)을 계산하고 메시지 m과 같은지 확인합니다. 아니. 같으면 유효한 서명이라고 말할 수 있습니다.

그러나이 서명 체계는 메시지 없음 공격에 취약하고 공격자가 임의의 메시지에 대해 서명을 위조 할 수 있습니다.

1. 메시지 없음 공격 : 이 공격에서 공격자는 공개 키를 알고있는 것만으로 서명을 위조합니다. 첫 번째 공격자는 uniform ?을 계산 한 다음 공개 키 pk = (n, e)를 m = ?ᵉ (mod n)으로 사용하여 메시지를 계산합니다. 공격자는 수신자에게 (m, ?)을 보냅니다. 여기 ?은 유효한 서명이지만 실제 발신자가 발행 한 것이 아닙니다. 이 공격에서 공격자는 결과 메시지에 영향을 미치는 방식으로 ?를 선택합니다.

2. 임의 메시지에 대한 서명 위조 :이 공격은 이전 공격보다 훨씬 더 강력합니다. 여기서 공격자는 발신자로부터’n’수의 임의 메시지 M = {m1, .., mn}에 대한 서명을 요청합니다. 이 정보를 통해 공격자는 M의 하위 집합 제품에서 생성 된 2ⁿ-n 개의 다른 메시지에 대해 서명을 생성 할 수 있습니다.

3.2.2 RSA-FDH 서명 체계 :
위에 언급 된 공격으로부터 보호하기 위해 메시지 (m)는 서명하기 전에 일부 변형을 거칩니다.

i) 서명 생성 : 처음에는 메시지 (m)가 해시 함수 (H)로 전송됩니다. 생성 된 해시 (H (m))는 Alice의 개인 키 (sk_ {A}} = (n, d))를 사용하여 암호화됩니다. 마지막으로 서명을받습니다. ?.

? = H (m) ᵈ (mod n).

Alice는 메시지, 디지털 서명 (m, ?)을 가져와 Bob의 공개 키 (pk_ {B}})를 사용하여 다시 암호화합니다. 생성 된 암호문 (c)이 Bob에게 전송됩니다.

Bob이 암호 텍스트 (c)를받은 후 Bob의 개인 키를 사용하여 암호 텍스트 (c)를 해독합니다. 그는 메시지 (m), 디지털 서명 (?)을받습니다.

ii) 디지털 서명 확인 :

1 단계 : 메시지 (m)를 가져와 해시 함수에 전달합니다. 마지막으로 해시 코드 (H (m))를 생성합니다.

2 단계 : 디지털 서명 (?)을 가져와 Alice의 공개 키를 사용하여 해독합니다. 마지막으로 해시 코드를 얻습니다.

1 단계와 2 단계에서 생성 된 해시 코드가 같으면 서명이 유효하다고 말할 수 있습니다.
?ᵉ = H (m) (mod n).

3.3 교과서 RSA에 대한 공격 :
3.3.1 가단성 공격 :
교과서 RSA는 가단성입니다. 공격자가 관련 일반 텍스트를 생성 할 수있는 방식으로 암호 텍스트 (c)를 변경할 수있는 경우 암호화 알고리즘은 가단성이라고합니다. 공격자는 일반 텍스트에 대한 지식이 없습니다. cipher text (c) = mᵉ이라고합시다. 공격자는이를 c’= (2ᵉ) * c = (2 * m) ᵉ로 변경했습니다. 마지막으로 수신자는 c’를 해독하고 2m의 일반 텍스트를받습니다.
가해 성은 바람직한 속성이 아닙니다. 예를 들어 메시지 (m)가 은행 거래 인 경우 공격자는 단순히 금액을 변경할 수 있습니다. 따라서이 공격은 특히 민감한 애플리케이션의 경우 심각한 문제를 야기합니다.

3.3.2 Chosen cipher text Attack :
공격자가 cipher text (c) = mᵉ에 대한 정보를 가지고 있다고 가정 해 보겠습니다. 공격자는 암호문 (c)을 c’= mᵉ * rᵉ으로 변경하려고합니다. 여기서‘r’은 임의의 숫자입니다. 공격자는 개인 키 (d)를 가진 사람에게 악의적으로 보이는 암호 텍스트 (c ‘)를 해독하도록 요청할 수 있습니다. 공격자는 c’ᵈ = m * r을 얻습니다. 위의 방정식을 ‘r’로 나누면 공격자는 마침내 메시지 ‘m’을 얻을 수 있습니다.

3.3.3 타이밍 공격 :
이것은 부 채널 공격 중 하나입니다. 부 채널 공격은 암호화 알고리즘이 실행되는 컴퓨터 시스템의 세부 정보를 알고있는 경우에만 수행 할 수 있습니다. 이 정보 공격자는 여러 암호 텍스트를 해독하는 데 필요한 시간을 찾아 마침내 비밀 키를 찾을 수 있습니다.

이 공격으로부터 보호하기 위해 우리는 모든 암호 해독을 확인할 수 있습니다. 텍스트는 일정한 시간이 걸립니다. 그러나 시스템 성능에 영향을 미칩니다. 언급 된 접근 방식 대신 RSA 구현은 ‘암호화 블라 인 딩’기술을 사용합니다. 다음과 같이 작동합니다. 암호문 (c)을 해독하는 대신 먼저 rᵉ을 곱합니다. 여기서‘r’은 난수이고’e’는 암호화 상수입니다. c’= c * rᵉ, c’ᵈ = m * r을 해독 한 후 얻을 수 있습니다. c’ᵈ에 r⁻¹을 곱하면 메시지 (m)가 나타납니다.

3.4 실용적인 RSA

3.4.1 RSA PKCS # 1 v1.5 패딩 체계
암호화 시스템은 의미 론적으로 안전하다고합니다. , 동일한 일반 텍스트에 대해 다른 암호 텍스트를 생성 할 수있는 경우. 평문 (m)이 암호화되어 암호문 (c)을 생성한다고 가정 해 봅시다.‘m’을 다시 암호화하면 다른 암호문 (c)을 생성해야합니다. 따라서 공격자는 일반 텍스트에 대해 배울 기회를 얻지 못합니다. 교과서 RSA는 동일한 일반 텍스트를 암호화하면 동일한 암호 텍스트가 생성되기 때문에 의미 상 안전하지 않습니다.

이 문제를 해결하기 위해 PKCS와 같은 표준이 개발되어 메시지 (m)를 임의의 비트 수로 채 ​​웁니다. RSA 암호화로 이동하기 전에.

우리는 RSA 공개 키가 pk = (e, n)이라는 것을 알고 있습니다. 여기서 ‘e’는 암호화 지수이고 n은 큰 소수입니다. k는’n’의 길이 (바이트)를 나타냅니다. 메시지‘m’을 길이 (l)의 배수 바이트로 1 ~ k-11 바이트 범위로 암호화 해 보겠습니다. ‘r’은 무작위로 생성 된 바이트 문자열입니다. ‘s 길이는 kl-3과 같고 해당 바이트는 0x00이 아니어야합니다.

â = [(0x00 || 0x02 || r || 0x00 || m)]

결과 메시지 â는 길이가 2 바이트 (0x00 || 0x02) 인 초기 2 개 블록으로 생성 된 다음 무작위로 생성 된 바이트 문자열 ‘r’및 1 바이트의 0과 연결됩니다. message ‘m’.

Cipher text c = (â) ᵉ (mod n).

무작위 패딩이 너무 짧으면 PKCS # 1 v 1.5는 CPA 보안 및 책임이 없습니다. 많은 공격에. 따라서 랜덤 패딩‘r’의 길이는 최소한

‖n‖ / e.

암호문 해독 : cᵈ (mod n) = â. 메시지‘m’은 â의 최하위 비트 (k 길이‘r’-2)로 복구 할 수 있습니다.수신자가 암호 텍스트를 해독 할 때 첫 번째 수신자는 가장 중요한 두 바이트 값을 확인하고 그 값은 0x00 ‖ 0x02와 같아야합니다. 그렇지 않은 경우 수신자는 ‘잘못된 암호 텍스트’오류 메시지를 보냅니다. 이 오류 메시지가 심각한 결과를 초래하는 방법을 살펴 보겠습니다.

공격자가 공개 커뮤니케이션 채널을 도청하고 암호를 해독하려는 암호 텍스트 ‘c’를 받았다고 가정 해 보겠습니다. 공격자는 난수 r’을 선택하고 c’= r’c를 계산합니다. 결과 암호 텍스트 c ‘가 수신자에게 전송됩니다. 수신자는 c ‘형식이 올바른지 확인합니다. 그렇지 않은 경우 수신자는 오류 메시지를 보냅니다.
수신자 응답을 기반으로 공격자는 c’의 복호화가 0x00 ‖ 0x02와 동일한 두 개의 중요한 바이트 값을 생성 할 수 있는지 여부를 알게됩니다. 공격자는 또한 c의 가장 중요한 두 바이트의 복호화가 0x00 ‖ 0x02와 같은지 확인하는 복호화 오라클을 보유하고 있습니다. Bleichenbacher는 공격자가이 해독 오라클을 사용하여 ‘c’를 해독 할 수 있음을 증명합니다.

이러한 유형의 공격으로부터 보호하기 위해 새로운 표준 최적 비대칭 암호화 패딩 (OAEP) 은 개발되었습니다.

3.4.2 RSA OAEP
RSA OAEP 체계는 RSA PKCS # 1 v1.5에서와 동일한 아이디어를 따르며 ‘m’메시지를 받아 ‘m’을 â로 변환합니다. 그런 다음 â를 암호화하여 암호 텍스트 (c)를 생성합니다. 그러나 message (m)을 â로 변환하는 것은 RSA PKCS # 1 v1.5보다 복잡한 절차를 따릅니다.

1) Let l은 비트 단위의 message (m) 길이입니다. 메시지 (m)를 0의 k1 수와 연결합니다.
m’= m ‖ 0 ^ k1을 얻습니다.
2)‘r’을 길이‘k0’의 임의의 비트 문자열이라고 가정합니다. l + k0 + k1의 길이는 RSA 모듈러스의 비트 수보다 작아야합니다. 여기서 ‘r’은 해시 함수 (G)로 보내지고, 길이가 l + k1 인 임의의 비트 문자열 G (r)를 얻습니다.
3) s = m ‘⊕ G (r)을 계산합니다.
4) 여기서 계산 된 s는 다른 해시 함수 (H)로 전송됩니다. 해시 함수의 출력은 길이가 k0 인 H (s)입니다.
5) t = r ⊕ H (s)를 계산합니다.
6) â = s ‖ t를 계산합니다.
7) Encrypt â with 암호화 키 ‘e’, ​​암호문 c = (â) ᵉ (mod n)을 얻습니다.
8) 메시지를 복구하기 위해 수신자는 암호문 cᵈ (mod n) = â를 해독합니다. 수신자는 s와 t의 길이를 알고 있으므로 â에서 s와 t를 복구 할 수 있습니다.
8) r = H (s) ⊕ t, m ‘= G (r) ⊕ s를 계산합니다.
9 ) m ‘을 복구 한 후 수신자는 테일링 비트의 k1 개수가 0인지 확인합니다. 그렇지 않은 경우 수신자는 ‘유효하지 않은 암호 텍스트’라는 오류 메시지를 보냅니다. 그렇다면 수신기는 최하위 0의 k1 수를 제거합니다. m ‘의 나머지 l 비트는 실제 메시지 (m)입니다.

3.5 RSA 구현 문제
RSA 기반 암호화 시스템에서 암호 텍스트 (c)를 가진 수신자 효율적인 복호화를 위해 중국어 나머지 정리 를 사용할 수 있습니다.

암호 해독 텍스트 (c) = cᵈ (mod n) ⟺ (cᵈ (mod p), cᵈ (mod q)), 여기서 n = p * q.

m_ {p} = cᵈ (mod p) = c ^ {d (mod (p-1))} (mod p),

m_ { q} = cᵈ (mod q) = c ^ {d (mod (q-1))} (mod q).

중국어 나머지 정리를 사용하면 m⟺ (m_ {p}, m_ {큐}).

m- 비트 정수의 경우 지수 모듈로는 k * m³ 연산을 취합니다. 여기서 k는 상수입니다. 우리는 n = p * q라는 것을 알고 있으며, 각각의 p, q는 m- 비트 길이라고 가정합니다. 따라서’n’은 2m 비트 길이이고 cᵈ (mod n)에는 k * (2m) ³ = k * 8m³ 연산이 필요합니다. 중국 나머지 정리 cᵈ (mod p), cᵈ (mod q)를 사용하면 각각 k * m³ 연산이 필요하며 총 k * 2m³ 연산이 필요합니다. 여기서 중국어 나머지 정리를 사용하여 3/4의 시간을 절약합니다.

암호화 상수 e = 65537 = 2¹⁶ + 1의 경우 암호화 작업에는 무작위로 선택한 ‘e’에 필요한 곱셈보다 훨씬 적은 총 17 개의 곱셈이 필요합니다. 언급 된‘e’값을 사용하여 암호화 체계의 효율성을 높일 수 있습니다.

3.6 벤치마킹
Intel 컴퓨터 (i5, @ 1.8GHz)에서 JAVA를 사용하여 RSA 암호화 시스템을 구현했습니다. 다음 그림은 암호화, 암호 해독, 서명 생성 및 확인의 성능을 강조합니다. 결과는 키 크기가 512 비트에서 4096 비트로 증가함에 따라 RSA가 제대로 수행되지 않음을 보여줍니다. 아래 그림에서 X 축은 키 길이를, Y 축은 초당 작업 (암호화 / 복호화 / 서명 생성 및 확인) 수를 나타냅니다.

3.7 결론
RSA 암호화 시스템은 광범위하게 배포되며 소프트웨어 엔지니어, 실무자 및 보안 애호가가 시스템을 완전히 이해하는 것이 좋습니다. 이 기사에서는 교과서 RSA 프리미티브, 보안 정의, 다양한 공격 및 RSA의 실제 구현에 대해 설명했습니다.

참조 :

[1] Lindell, Yehuda, Jonathan Katz. 최신 암호화 소개 . Chapman and Hall / CRC, 2014.
[2] Boneh, Dan. RSA 암호화 시스템에 대한 20 년의 공격 .
AMS 46.2 (1999) 고지 : 203–213.
[3] https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Padding_schemes}
[4] https : / /en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding
[5] https://en.wikipedia.org/wiki/Padding_(cryptography)}
[6] https://crypto.stackexchange.com/questions / 1448 / definition-of-textbook-rsa