Python은 RSA 알고리즘을 구현합니다.

이 문서의 예에서는 Python에서 RSA 알고리즘을 구현하는 방법을 설명합니다. 참고를 위해 모든 사람과 공유하세요. 세부 사항은 다음과 같습니다.

1. 기본 정수 이론

1. 역소수 관계

• 두 양의 정수에 1 외에 다른 공통 인수가 없는 경우, 이 두 숫자를 coprime이라고 합니다. 예를 들어 15와 32는 공통인수가 없으므로 서로 소수입니다. 이는 소수가 아닌 숫자라도 서로소 관계를 형성할 수 있음을 보여줍니다.

2. 오일러 함수

• 정의: n보다 작거나 같은 양의 정수 중에서 n과 서로소 관계에 있는 것은 몇 개입니까? (예를 들어 1부터 8까지 중에서 8과 서로소 관계에 있는 숫자는 몇 개일까요?) 이 값을 계산하는 방법을 Euler 함수라고 하며, Φ(n)으로 표시합니다.

• 오일러 함수와 해당 속성을 찾는 방법:

1. 소수 p의 경우 ψ(p)=p-1, 두 개의 소수 p, q, ф의 경우 (pq)= pq-1, 오일러 함수는 적분 함수이지만 완전한 적분 함수는 아닙니다.

2. 양의 정수 N의 소수 거듭제곱 분해의 경우 N=P1^q1* P2^q2*.. .*Pn^qn, 그러면 Φ(N)=N*(1-1/P1)*(1-1/P2)*…*(1-1/Pn).

3. N= 2를 제외하고 ψ(N)은 모두 짝수입니다.

4. n을 상대적으로 소수인 두 정수의 곱으로 분해할 수 있다면 n = p1 × p2이면 ψ(n) = ψ( p1p2) = Φ(p1) Φ(p2)

2. RSA 암호화

첫 번째 단계는 두 개의 서로 다른 소수 p와 q를 무작위로 선택하는 것입니다.

앨리스는 61과 53을 선택했어요. (실제 응용에서는 이 두 소수가 클수록 해독하기가 더 어렵습니다.)

두 번째 단계는 p와 q의 곱 n을 계산하는 것입니다.

앨리스는 방금 61과 53을 곱했습니다.

　n = 61×53 = 3233

n의 길이가 키 길이입니다. 2진수로 쓴 3233은 110010100001로 총 12자리이므로 키는 12자리입니다. 실제 애플리케이션에서 RSA 키는 일반적으로 1024비트이고 중요한 경우에는 2048비트입니다.

세 번째 단계는 n의 오일러 함수 ψ(n)을 계산하는 것입니다.

공식에 따르면:

　Φ(n) = (p-1)(q-1)

Alice는 Φ(3233)이 60×52, 즉 3120과 같다고 계산했습니다.

네 번째 단계는 정수 e를 무작위로 선택하는 것입니다. 조건은 1< e < ψ(n)이며 e와 ψ(n)은 상대적으로 소수입니다.

앨리스는 1에서 3120 사이에서 무작위로 17을 선택했습니다. (실제 응용에서는 65537이 선택되는 경우가 많습니다.)

다섯 번째 단계는 ψ(n)에 대해 e의 모듈러 역원 요소 d를 계산하는 것입니다.

소위 "모듈형 역원소"는 ed를 ψ(n)으로 나눈 나머지를 1과 동일하게 만들 수 있는 정수 d가 있음을 의미합니다.

　ed ל 1 (mod Φ(n))

이 공식은

　ed - 1 = kΦ(n)

과 동일합니다. 따라서 모듈러 역원소 d를 구하는 것은 본질적으로 다음과 같습니다. 선형 방정식 풀기 두 가지 변수로.

　ex + Φ(n)y = 1

e=17, Φ(n)=3120,

　17x + 3120y = 1

이 방정식은 "확장"으로 사용할 수 있습니다. 유클리드 알고리즘" "해결을 위해 여기서는 구체적인 과정을 생략한다. 요약하면 Alice는 정수 해 집합을 (x,y)=(2753,-15), 즉 d=2753으로 계산합니다.

이제 모든 계산이 완료되었습니다.

6번째 단계는 n과 e를 공개 키로 캡슐화하고, n과 d를 개인 키로 캡슐화하는 것입니다.

Alice의 예에서는 n=3233, e=17, d=2753이므로 공개 키는 (3233,17)이고 개인 키는 (3233, 2753)입니다.

실제 응용에서는 공개키와 개인키의 데이터가 ASN.1 형식으로 표현됩니다(예시).

7. RSA 알고리즘의 신뢰성

위의 키 생성 단계를 검토하면 총 6개의 숫자가 나타납니다.

　p
　q
　n
　Φ(n)
　e
　d

이 6개의 숫자 중 공개키는 2개(n과 e)를 사용하고 나머지 4개의 숫자는 공개되지 않습니다. 가장 중요한 것은 d입니다. n과 d가 개인 키를 구성하기 때문입니다. d가 유출되면 개인 키가 유출된다는 의미입니다.

그렇다면 n과 e를 알 때 d를 추론하는 것이 가능할까요?

　 (1)ed=1 (mod Φ(n)). e와 Φ(n)을 아는 것만으로 d를 계산할 수 있습니다.

　 (2)Φ(n)=(p-1)(q-1). p와 q를 알아야만 Φ(n)을 계산할 수 있습니다.

　 (3) n=pq. n을 인수분해해야만 p와 q를 계산할 수 있습니다.

결론: n을 인수분해할 수 있으면 d도 계산할 수 있으며 이는 개인 키가 해독되었음을 의미합니다.

그러나 큰 정수를 인수분해하는 것은 매우 어려운 일입니다. 현재 무차별 대입 크래킹 외에 다른 효과적인 방법은 발견되지 않았습니다. Wikipedia는 다음과 같이 썼습니다.

　　　매우 큰 정수를 인수분해하는 것이 RSA 알고리즘의 신뢰성을 결정합니다. 즉, 매우 큰 정수를 인수분해하는 것이 어려울수록 RSA 알고리즘의 신뢰성이 높아집니다. 빠른 인수 분해 알고리즘을 찾으면 RSA의 신뢰성은 매우 낮지만 그러한 알고리즘을 찾을 가능성은 매우 적습니다. 2008년 현재 전 세계적으로 짧은 RSA 키만 크랙할 수 있습니다. RSA 알고리즘은 키 길이가 충분히 길면 RSA로 암호화된 정보를 해독할 수 없습니다. "예를 들어 3233.(61×53)은 인수분해할 수 있지만 다음 정수는 인수분해할 수 없습니다.

　12301866845301177551304949

　58384962720772853569595334

　79219732245215172640050726

　36575187452 021997864693899

　56474942774063845925192557

　32630345373154826850791702

　61221429134616704292143116

　0222 8 4821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
　76426760322838157396665112
　79233373417143396810270092

　798736308917

사실 이것은 아마도 인간이 인수분해한 가장 큰 정수(십진수 232자리, 이진수 768자리)일 것입니다. 더 큰 인수분해는 보고되지 않았으므로 지금까지 해독된 가장 긴 RSA 키는 768비트입니다.

8. 암호화 및 복호화

공개 키와 키를 사용하여 암호화 및 복호화할 수 있습니다.

(1) 암호화에는 공개 키 (n,e)가 필요합니다.

Bob이 암호화된 정보 m을 Alice에게 보내고 싶다면 Alice의 공개 키(n,e)를 사용하여 m을 암호화해야 합니다. 여기서 m은 정수여야 하고(문자열은 ASCII 값 또는 유니코드 값을 사용할 수 있음) m은 n보다 작아야 합니다.

소위 "암호화"는 다음 공식의 c를 계산하는 것입니다.

　m^ezzo c (mod n)

Alice의 공개 키는 (3233, 17)이고 Bob의 m은 다음과 같이 가정됩니다. 65, 그러면 다음 등식을 계산할 수 있습니다.

　　65¹⁷ 량 2790 (mod 3233)

그래서 c는 2790이고 Bob은 2790을 Alice에게 보냅니다.

(2) 복호화에는 개인 키(n, d)가 필요합니다

Alice는 Bob이 보낸 2790을 받은 후 자신의 개인 키(3233, 2753)를 사용하여 이를 복호화합니다. 다음 방정식이 참이어야 함을 증명할 수 있습니다.

　c^d zzo m (mod n)

즉, c를 n으로 d제곱으로 나눈 나머지는 m입니다. 이제 c는 2790이고 개인 키는 (3233, 2753)입니다. 그런 다음 Alice는

　2790²⁷⁵³ 65 (mod 3233)

을 계산합니다. 따라서 Alice는 암호화 전 Bob의 원본 텍스트가 65라는 것을 알고 있습니다.

이제 '암호화-복호화'의 모든 과정이 완료됩니다.

d를 모른다면 c에서 m을 찾을 방법이 없다는 것을 알 수 있습니다. 앞서 언급한 것처럼 d를 알려면 n을 분해해야 하는데, 이는 매우 어려운 일이므로 RSA 알고리즘은 통신 보안을 보장합니다.

공개 키 (n,e)는 n보다 작은 정수 m만 암호화할 수 있는데, n보다 큰 정수를 암호화하려면 어떻게 해야 할까요? 두 가지 해결책이 있습니다. 하나는 긴 메시지를 여러 개의 짧은 메시지로 나누고 각 세그먼트를 별도로 암호화하는 것입니다. 다른 하나는 먼저 "대칭 암호화 알고리즘"(예: DES)을 선택하고 이 알고리즘의 키를 사용하는 것입니다. 그런 다음 RSA 공개 키를 사용하여 DES 키를 암호화합니다.

9. 개인키 복호화 증명

마지막으로 개인키로 복호화하면 왜 m을 정확하게 얻을 수 있는지 증명하겠습니다. 이는 다음 공식을 증명하는 것입니다.

　　c^d= m (mod n)

암호화 규칙에 따라

　　미터^e기 c (mod n)

그래서, c 다음과 같은 형식으로 작성할 수 있습니다.

　c = m^e - kn

우리가 증명하려는 암호 해독 규칙에 c를 대입하면:

　(m^e - kn)^dzzo m ( mod n)

이것은

　m^edzzo m (mod n)

Since

　ed ל 1 (mod Φ(n))

So

을 증명하는 것과 같습니다.　ed = h Φ(n) +1

다음 위치에 배치:

　 m^hΦ(n)+1 oli m (mod n)

다음으로 위의 공식을 두 가지 경우로 증명해 보세요.

(1) m과 n은 상대적으로 소수입니다.

오일러의 정리에 따르면 이때

　m^Φ(n)ל 1(mod n)

을 얻습니다

　　(m^Φ(n))^h×m = m ( mod n)

원래 공식이 증명되었습니다.

(2) m과 n은 서로 소수가 아닙니다.

이때 n은 소수 p와 q의 곱이므로 m은 kp 또는 kq와 같아야 합니다.

m = kp를 예로 들면, 이때 k와 q가 서로 소수여야 한다는 점을 고려하면 오일러의 정리에 따라 다음 공식이 성립됩니다. ㅋㅋㅋ 피 (mod q)

다음 방정식으로 다시 써보세요

　　(kp)

ed

= tq + kp

이때 t는 p로 나누어떨어져야 합니다. 즉, t=t'p ^(kp) ed

= t'pq + kp

m=kp, n=pq이므로

　m^ed EMA (mod n)

원래 공식이 증명되었습니다.

python 구현

강력한 Python에는 암호화 기술 구현을 전문으로 하는 pycrypto 타사 라이브러리가 있습니다. 그러나 rsa를 구현하려면 이러한 고급 도구가 필요하지 않습니다. , rsa만 로드하면 됩니다. 타사 라이브러리이면 충분합니다.

코드를 보여주세요, NO bb:

#实现公钥加密 RSA

import rsa
import time
#计算下时间

start_time = time.time()
key = rsa.newkeys(1024) #数字代表 p * q 产生的存储空间 bit 大小, 也就是密文长度，数字越大，时间越长
privateKey = key[1]
publicKey = key[0]
#print(privateKey)
#print(publicKey)
end_time = time.time()
print("make a key:", end_time - start_time)
#产生公钥和私钥

message = 'Taiyuan is the best city of China.'
message = message.encode()

cryptedMessage = rsa.encrypt(message, publicKey)
print("crypted:", cryptedMessage)
print("length of cryptedMessage：", len(cryptedMessage))
# 加密的过程

decrypetdMessage = rsa.decrypt(cryptedMessage, privateKey)
print("decrypet:", decrypetdMessage)
# 解密的过程

now_time = time.time()
print("crypt and decrypt:", now_time - end_time)

관련 추천:

RSA 알고리즘의 원리를 철저하게 이해하도록 안내하세요

RSA 암호화 알고리즘

25줄 코드는 완전한 RSA 알고리즘을 구현합니다

RSA 알고리즘 및 C 언어 구현에 대한 자세한 설명

위 내용은 Python은 RSA 알고리즘을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!