The example in this article describes the implementation of RSA algorithm in python. Share it with everyone for your reference, the details are as follows:
1. Basic number theory
1. Reciprocal prime relationship
If two positive integers have no other common factors except 1, we call the two numbers coprime relationship (coprime). For example, 15 and 32 have no common factors, so they are mutually prime. This shows that even non-prime numbers can form a coprime relationship.
2. Euler function
Definition: given any positive integer n, Among the positive integers less than or equal to n, how many are relatively prime to n? (For example, among 1 to 8, how many numbers are in a mutually prime relationship with 8?) The method of calculating this value is called Euler function, represented by φ(n).
How to find the Euler function and its properties:
For the prime number p, φ(p)=p-1, For two prime numbers p, q, φ(pq)=pq-1, The Euler function is the product sexual function, but not a complete product function.
For the prime power decomposition of a positive integer N N=P1^q1*P2^q2* ...*Pn^qn, then φ(N)=N*(1-1/P1)*(1-1/P2)*…*(1-1/Pn).
Except N=2, φ(N) are all even numbers.
If n can be decomposed into two coprime The product of integers, n = p1 × p2, then φ(n) = φ(p1p2) = φ(p1)φ(p2)
2. RSA encryption
The first step is to randomly select two unequal prime numbers p and q.
Alice chose 61 and 53. (In practical applications, the larger these two prime numbers are, the more difficult it is to crack.)
The second step is to calculate the product n of p and q.
Alice multiplies 61 and 53.
n = 61×53 = 3233
The length of n is the key length. 3233 written in binary is 110010100001, which has 12 digits in total, so the key is 12 digits. In practical applications, the RSA key is generally 1024 bits, and in important cases it is 2048 bits.
The third step is to calculate the Euler function φ(n) of n.
According to the formula:
φ(n) = (p-1)(q-1)
Alice calculated that φ(3233) is equal to 60×52, which is 3120.
The fourth step is to randomly select an integer e, the condition is 1< e < φ(n), and e and φ(n) are relatively prime.
Alice was between 1 and 3120 and randomly selected 17. (In practical applications, 65537 is often chosen.)
The fifth step is to calculate the modular inverse element d of e with respect to φ(n).
The so-called "modular inverse element" means that there is an integer d that can make the remainder of ed divided by φ(n) equal to 1.
ed ≡ 1 (mod φ(n))
This formula is equivalent to
ed - 1 = kφ(n )
So, finding the modular inverse element d is essentially solving the following linear equation of two variables.
ex φ(n)y = 1
It is known that e=17, φ(n)=3120,
17x 3120y = 1
This equation can be solved using the "extended Euclidean algorithm", and the specific process is omitted here. In summary, Alice calculates a set of integer solutions as (x,y)=(2753,-15), which is d=2753.
Now all calculations are completed.
The sixth step is to encapsulate n and e into public keys, and encapsulate n and d into private keys.
In Alice’s example, n=3233, e=17, d=2753, so the public key is (3233,17) and the private key is (3233, 2753).
In actual applications, the data of public and private keys are expressed in ASN.1 format (example).
7. Reliability of RSA algorithm
Looking back at the above key generation steps, a total of six numbers appear:
p
q
n
φ(n)
e
d
Of these six numbers, two are used in the public key (n and e), the remaining four numbers are not public. The most critical one is d, because n and d form the private key. Once d is leaked, it means the private key is leaked.
So, is it possible to deduce d when n and e are known?
(1) ed≡1 (mod φ(n)). Only by knowing e and φ(n) can we calculate d.
(2)φ(n)=(p-1)(q-1). Only by knowing p and q can we calculate φ(n).
(3)n=pq. Only by factoring n can we calculate p and q.
Conclusion: If n can be factored, d can be calculated, which means the private key has been cracked.
However, factoring large integers is a very difficult thing. At present, apart from brute force cracking, no other effective method has been found. Wikipedia writes:
"The difficulty of factoring a very large integer determines the reliability of the RSA algorithm. In other words, the more difficult it is to factor a very large integer, the more reliable the RSA algorithm is." .
If someone finds a fast factoring algorithm, then the reliability of RSA will be extremely reduced. But the possibility of finding such an algorithm is very small. Today it is only possible with short RSA keys Being cracked by brute force. As of 2008, there is no reliable way to attack the RSA algorithm in the world.
As long as the key length is long enough, information encrypted with RSA cannot actually be cracked."
For example, you can factor 3233 (61×53), but you cannot factor the following integer.
12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864 693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
022212404792747377940 80665
351419597459856902143413
It is equal to the product of two prime numbers like this:
33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
022876147 11652531743087737
814467999489
# 76426760322838157396665112
79233373417143396810270092
798736308917
In fact, this is probably the largest integer that humans have factored into (232 decimal digits, 768 binary digits). Larger factorizations have not been reported, so the longest RSA key that has been cracked is 768 bits.
8. Encryption and decryption
With the public key and key, you can encrypt and decrypt.
(1) Encryption requires public key (n,e)
Assuming that Bob wants to send encrypted information m to Alice, he must use Alice’s Public key (n,e) encrypts m. It should be noted here that m must be an integer (the string can take an ascii value or unicode value), and m must be less than n.
The so-called "encryption" is to calculate c of the following formula:
me ≡ c (mod n)
爱利Silk's public key is (3233, 17), and Bob's m is assumed to be 65, then the following equation can be calculated:
6517 ≡ 2790 (mod 3233)
So, c equals 2790, and Bob sends 2790 to Alice.
(2) Decryption requires the private key (n,d)
After Alice gets the 2790 sent by Bob, she uses her own private key (3233 , 2753) for decryption. It can be proved that the following equation must be true:
cd ≡ m (mod n)
That is to say, c divided by the dth power Let the remainder of n be m. Now, c is equal to 2790 and the private key is (3233, 2753). Then, Alice calculates
27902753 ≡ 65 (mod 3233)
Therefore, Alice knows that Bob’s original text before encryption is 65.
At this point, the entire process of "encryption-decryption" is completed.
We can see that if d is not known, there is no way to find m from c. As mentioned before, to know d, you must decompose n, which is extremely difficult to do, so the RSA algorithm ensures communication security.
You may ask, the public key (n,e) can only encrypt an integer m less than n, so what should you do if you want to encrypt an integer greater than n? There are two solutions: one is to divide the long message into several short messages and encrypt each segment separately; the other is to first choose a "symmetric encryption algorithm" (such as DES) and use the key of this algorithm Encrypt the message and then use the RSA public key to encrypt the DES key.
9. Proof of private key decryption
Finally, we will prove why m can be obtained correctly by decrypting with private key. That is to prove the following formula:
cd ≡ m (mod n)
Because, according to the encryption rules
ｍe ≡ c (mod n)
So, c can be written in the following form:
c = me - kn
Substituting c into the decryption rule we want to prove:
(me - kn)d ≡ m (mod n)
It is equivalent to verification
med ≡ m (mod n)
Because
ed ≡ 1 (mod φ(n))
So
ed = hφ(n) 1
Substitute ed into:
mhφ(n) 1 ≡ m (mod n)
Next, prove the above formula in two cases.
(1) m and n are relatively prime.
According to Euler’s theorem, at this time
mφ(n) ≡ 1 (mod n)
Get
(mφ(n))h × m ≡ m (mod n)
Original formula Get proven.
(2) m and n are not mutually prime.
At this time, since n is equal to the product of prime numbers p and q, m must be equal to kp or kq.
Take m = kp as an example. Considering that k and q must be mutually prime at this time, according to Euler’s theorem, the following formula holds:
(kp)q-1 ≡ 1 (mod q)
further get
[(kp)q-1] h(p-1) × kp ≡ kp (mod q)
ie
(kp)ed ≡ kp (mod q)
Rewrite it into the following equation
(kp)ed = tq kp
At this time, t must be divisible by p, that is, t=t'p
(kp)ed = t'pq kp
because m =kp, n=pq, so
med ≡ m (mod n)
The original formula is proved.
python implementation
Powerful python has a dedicated implementation The pycrypto third-party library of cryptographic technology. However, if we want to implement rsa, we do not need such a sophisticated tool. We only need to load a third-party library of rsa.
Show you the code, 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)Related recommendations:
Take you to thoroughly understand the principle of RSA algorithm
25 lines of code to implement the complete RSA algorithm
Detailed explanation of RSA algorithm and C language implementation
The above is the detailed content of python implements RSA algorithm. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
