Big-O 표기법 : 암호화 알고리즘

Question

현재 다양한 암호화 알고리즘을 통한 데이터 암호화에 관한 논문을 작성 중입니다.

저널과 논문을 읽는 데 많은 시간을 할애했지만 아직 실적이 복잡하지는 않습니다.

누구나 다음 알고리즘의 Big-O 복잡성에 대한 아이디어가 있습니까?

• RSA
• DES
• 삼중 DES

가 사전에 감사

복어

AES (I는 DES와 같은 순서 될 것으로 기대 것이다); 매우 평판이 좋으면 평판이 좋고 가능한 소스에 대한 링크를 제공 할 수 있습니다.

Answer 1

부분 않음 : RSA 연구소 암호화, 복호화, 서명 또는 검증 여부를 필수적으로 누승 잉여 인 "RSA 동작"

DES

대 이러한 분석을 http://www.rsa.com/rsalabs/node.asp?id=2215 비교 RSA 동작들을 제공한다. 이 계산은 일련의 모듈러 곱셈에 의해 수행됩니다.

실제 응용 프로그램에서는 공개 키에 작은 공개 지수를 선택하는 것이 일반적입니다. 사실, 전체 사용자 그룹은 각각 다른 모듈러스를 가진 동일한 공개 지수를 사용할 수 있습니다. (공개 지수가 고정 될 때 모듈러스의 주요 요소에는 몇 가지 제한이 있습니다.) 이렇게하면 서명보다 암호 해독 및 검증이 빠릅니다. RSA 알고리즘을 구현하는 데 사용되는 일반적인 모듈러 지수 알고리즘을 사용하여 공개 키 작업은 O (k2) 단계를 수행합니다., 개인 키 작업은 O (k3) 단계를 취하고 키 생성은 O (k4) 모듈의 비트 수는입니다. Fast Fourier Transform (FFT) 기반의 방법과 같은 "빠른 곱셈 (Fast multiplication)"기술은 점진적으로 적은 단계가 필요합니다. 그러나 실제로는 소프트웨어 복잡성이 증가하고 일반적인 키 크기의 경우 실제로 느려질 수 있으므로 일반적이지 않습니다.

RSA 알고리즘의 많은 상업적으로 사용 가능한 소프트웨어 및 하드웨어 구현의 속도와 효율성이 빠르게 증가하고 있습니다. 최신 수치는 http://www.rsasecurity.com/을 참조하십시오.

비교해 보면, DES (3.2 절 참조)와 다른 블록 암호는 RSA 알고리즘보다 훨씬 빠릅니다. DES는 일반적으로 소프트웨어에 따라 100 배, 하드웨어에 따라 1,000 ~ 10,000 배의 속도로 구현됩니다. RSA 알고리즘의 구현은 높은 수요로 인해 향후 몇 년 동안 약간의 격차를 좁힐 수 있지만 블록 암호도 더 빨라질 것입니다.

Answer 2

대칭 암호 복잡성은 한 블록에 대해 O (1)입니다.

목록의 RSA를 떠나

하고, 대답은 큰 정수의 곱셈 구현 얼마나 잘에 따라 매우 구현 의존, 지수의 선택, 등 ...

Answer 3

한 가지주의 할 (경우에 따라 당신의 논문을 코딩하고 있습니다.) RSA의 실제 구현은 실제로 RSA를 사용하여 AES 키 교환을 수행합니다.따라서 암호화/복호화를위한 O (k^2) 및 O (k^3) 연산은 각각 AES 키의 암호화 측면에서만 있습니다. AES는 소프트웨어/하드웨어에서 100-10K 배 빠르며 교환되는 데이터의 실제 블록 암호를 사용합니다. 이렇게하면 과도한 계산 가격을 지불하지 않고도 PKI (RSA를 통해)를 이용할 수 있습니다.