# RSA basic principle and common attack methods

2022-01-15 02:27:46

## 1 Preface

Cryptography is the processing of data 、 Storage and communication procedures provide additional levels of security . In recent years , Mathematicians and computer scientists have developed a series of increasingly complex algorithms , These algorithms are designed to ensure confidentiality 、 integrity 、 Authentication and non repudiation . While cryptologists spend a lot of time developing strong encryption algorithms , Hackers and the government have invested considerable resources to crack these cryptographic algorithms . This gives rise to the field of cryptography " The arms race ", And led to the continuous development of extremely sophisticated algorithms used today .

## 2 In modern cryptography RSA

“ Modern cryptography ” The subject of can be divided into “ symmetric cryptography ” and “ Asymmetric cryptography ”.

The symmetric key algorithm relies on a " Shared secrets " Encryption key , The key will be distributed to all members participating in the communication . All communication members use this key to encrypt and decrypt messages , Therefore, both sender and receiver have copies of the shared key . Both sides of the communication will use the same key to encrypt and decrypt the message . When using a long key , Symmetric encryption is difficult to crack . Symmetric key algorithm is mainly used to perform batch encryption , And only provide confidentiality for security services . Symmetric key cryptography is also called secret key cryptography 、 Private key cryptography 、 Session key cryptography 、 Shared secret key cryptography .

The following figure shows the encryption and decryption process of symmetric key .

Symmetric key cryptography has the following weaknesses :

Key distribution is a major problem . Before establishing communication using symmetric key protocol , Communication participants must have a method of securely exchanging keys . If there is no secure electronic channel available , Then you often have to use offline key distribution methods ( Is no longer part of the exchange ) .

Symmetric key cryptography well does not realize non repudiation . Because any communication party can use the shared key to encrypt and decrypt the message , Therefore, the source of the specified message cannot be distinguished .

This algorithm is not scalable . For large user groups , It is very difficult to communicate with symmetric key cryptography . Only if each possible combination of users shares a private key , Only secure and proprietary communication between individuals in the group can be achieved .

The key must be updated frequently . Whenever a member leaves the user group , All keys involving this member must be discarded .

Asymmetric key algorithm is also called public key algorithm , It provides a solution to the weakness of symmetric key encryption . In this system , Each user has two keys : A public key shared among all users , And another private key that only the user knows and keeps . But the unexpected thing is : The opposite and related keys must be applied successively to encryption and decryption . let me put it another way , If you use a public key to encrypt a message , Then only the relevant private key can be decrypted , vice versa .

chart 6.4 This paper explains the encryption and decryption of messages in public key cryptosystem 、 The algorithm used .

sender                                                             The recipient

Consider this example : If Alice Want to use public key cryptography to Bob Send a message , She first generated this message , Subsequent use Bob The public key of the message is encrypted . The only possible way to decrypt this ciphertext is to use Bob The private key , And the only user who has the right to use this key is Bob, therefore , Alice After encrypting the message , You can't even decrypt this message . If Bob Hope to Alice Send a response message , He can use Ali The response message is encrypted with the public key of the socket , Alice The message can then be decrypted using her own private key , To read these messages .

Once the sender encrypts the message with the recipient's public key , So in Don't know the recipient's private key ( The public key used to generate the message / The other half of the private key pair ) Under the circumstances , No users ( Including the sender ) Can decrypt this information . This is the advantage of public key cryptography , That is, the public key can be freely shared using an insecure communication channel , And create a secure communication channel between previously unknown users .

RSA It is the most widely used asymmetric encryption algorithm . It plays an extremely important role in modern cryptography , If you want to choose a representative cryptography algorithm for in-depth research , I recommend you study RSA Algorithm .

## 3 Fundamentals of Mathematics

RSA Summary of mathematical knowledge about algorithms

### 3.1 Mutual relationship

If two positive integers , except 1 There is no common factor other than , We call these two numbers Mutual relationship , such as 4 and 15

### 3.2 Euler function

Any given positive integer n, If it is less than or equal to n In the positive integer of , How many are related to n Constitute a reciprocal relationship ？ such as 10 How many positive integers within are associated with 10 What about mutuality ？ The way to calculate this value is called Euler function , With φ(n) Express ,φ(10)=4. If p,q All prime numbers ,φ(p*q) = (p-1)(q-1).

give an example ： p=3,q=5, And 15 The number of Coprime is 1,2,4,7,8,11,13,14, You can count out a total of 8 individual , At the same time, it can also be calculated by formula φ(15) = (3-1)*(5-1)=8.

### 3.3 Euler theorem

Euler theorem ： If two positive integers a and n Coprime , be n The Euler function of φ(n) Let the following equation hold ：

in other words ,a Of φ(n) The inferior is n The remainder of the division is 1. Or say ,a Of φ(n) To the power of 1, Can be n to be divisible by .

give an example ：3 and 7 Coprime , and 7 The Euler function of φ(7) be equal to 6, therefore 3 Of 6 Power （729） subtract 1, Can be 7 to be divisible by （728/7=104）.

### 3.4 Modular inverse elements

If two positive integers e and n Coprime , Then we can find the whole number d, bring e * d - 1 By n to be divisible by , Or say e * d By n The remainder of the division is 1. At this time ,d It's called e Of “ Modular inverse elements ”. Euler's theorem can be used to prove the existence of module anti elements .(python: d = gmpy2.invert(e,φ(n)))

## 4RSA Algorithm

The most famous public key cryptosystem is named after its Creator .1 977 year , Ronald Rivest、Adi Shamir and Leonard Adleman Put forward RSA Public key algorithm , This algorithm has become the standard still used all over the world today . They patented the algorithm and set up a commercial company (RSA Safety company ), The company develops mainstream products using its security technology . today , RSA Algorithms have formed many well-known security infrastructures ( for example Microsoft、Nokia and Cisco The company's corresponding products ) The security framework .RSA The length of the secret key is not fixed .

### 4.1RSA Algorithm calculation steps

RSA The algorithm relies on the inherent computational difficulty of large numbers in factorization . Each user's public key and system's private key are described in the following steps :

（1） Choose two large prime numbers , Calculate the modulus N = p * q

（2） Calculating Euler function φ(N) = (p-1) * (q-1), Then choose one e(1<e<φ), also e and φ Coprime

（3） seek e The modulo inverse of d, The calculation method is as follows :e * d ≡ 1 (mod φ)

（4） The clear m To encrypt ：c = m^e mod N, You can get ciphertext c.

（5） To ciphertext c To decrypt ：m = c^d mod N, You can get plaintext m.

Arrangement ：

p and q： Two large prime numbers , It's another parameter N Two factors of .

N： Large integer , It can be called modulus

e and d： Modular inverse number

c and m： Ciphertext and plaintext

(N, e)： Public key

(N, d)： Private key

Key length ：n The number of bits in binary , For example, the key length is 512 representative n The length expressed in binary is 512bit.

Verify the calculation ：

1. Suppose the ciphertext Xiao Ming wants to send is m=12

2. Then Xiao Ming randomly selects two coprime numbers p=3,q=5, be n=15, φ(n)=(3-1)*(5-1)=8

3. stay 1~8 Choose one at random from 8 Coprime number as public key e, Suppose Xiao Ming chooses e=3, be (15, 3) For public key

4. So according to e *d%8=1, You can work out d=19, be (15,3) For public key ,(15,19) For private key

5. When encrypting ：

The ciphertext actually sent is ：12^3%15=3

7. When decrypting ：

The received ciphertext is 3 after , Decipherment : 3^19%15=1162261467%15=12

### 4.2 RSA Some questions about the algorithm

problem 1:  If everyone needs a different prime number , Won't you run out of prime numbers ？

answer ： Can't , according to “ Prime number theorem ”, Less than n The total number of prime numbers of is about n/ln(n).

problem 2：: Will two people accidentally choose the same prime number ？

answer ： It seldom happens . from M Choose from a prime number q Prime number , The probability that at least two prime numbers are the same reaches 1/2,q Need to achieve 1.17 *M^(1/2).

problem 3： Is it difficult to produce prime numbers ？

answer ： No difficulty . Consult the information to know , Generally, an odd number is randomly generated first n, Then use some prime detection algorithm （ Such as Miller-Rabin） Yes n Perform one-time prime detection , If n If it fails, the random number is regenerated , If n If the test passes, repeat the test for many times , If both pass, then n Select as ideal prime .

give an example ：e=3 n=7,e and n It's reciprocal . Can find d=5 , send e*d-1 By n to be divisible by （3*5-1 By 7 to be divisible by ）.

## 5 RSA Common attack algorithms

5.1 Modulus decomposition

5.2 Direct decomposition N

windows Platform RSATool

Online website http://factordb.comhttp://factordb.com/

5.3 greatest common divisor

5.4 Low encryption index attack （ Low encryption index broadcast attack ）

5.5 Low decryption index attack

5.6 Common mode attack

5.7

There is a blog that is easy to read .

RSA Common attack algorithms _ Remembrance _ Past blogs -CSDN Blog _rsa attack RSA Algorithm description RSA The algorithm involves three parameters ,n,e,d, The private key is n,d, The public key is n,e. among n Are two large prime numbers p,q The product of the . d yes e model \$ varphi(n) \$ Inverse element ,\$ varphi(n) \$ yes n The Euler function of . c For the cipher ,m In plain text , Then the encryption process is as follows ： \$ cequiv m^e mod n \$ The decryption process is as follows ：...https://blog.csdn.net/qq_24966613/article/details/84571123

## 6 It is known that x.509 certificate , Steps to obtain the private key

### 6.1 from x.509 Extract public key information from .

The format of public key information is ：

``````-----BEGIN PUBLIC KEY-----
MIIB*********************************************
-----END PUBLIC KEY-----``````

For the method of obtaining, refer to the following blog 3.1 chapter

android apk In the signature file MANIFEST.MF、CERT.SF、CERT.RSA The relationship among the three _ Xiaoxiangzi's blog -CSDN Blog

### 6.2  Extract... From the public key file 16 Base number N,E

Remove -----BEGIN PUBLIC KEY----- and -----END PUBLIC KEY----- Paste the public key after two lines , You can get N,e Of base64 Code file . Then through the counter base64f Method can obtain 16 It's binary N and e.

### 6.3 utilize N and e Calculate private key

Now we have N and e, Calculate the private key d There is already a theoretical possibility . The following code is the code that can calculate the private key . If N The length of the shorter , The results can be calculated in a short time . If N Longer than 512, Then our method can only help you learn .

Compute private key with known public key python Code

``````import random

def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a

def getpq(n, e, d):
p = 1
q = 1
while p == 1 and q == 1:
k = d * e - 1
g = random.randint(0, n)
while p == 1 and q == 1 and k % 2 == 0:
k /= 2
y = pow(g, int(k), n)
if y != 1 and gcd(y - 1, n) > 1:
p = gcd(y - 1, n)
q = n / p
return p, q

#  Decomposition modulus n
def rsa_moder(n):
base = 2
while base < n:
if n % base == 0:
return base, n // base
base += 1

#  Find Euler functions f(n)
def rsa_get_euler(prime1, prime2):
return (prime1 - 1) * (prime2 - 1)

#  Private key
def rsa_get_key(e, euler):
k = 1
while True:
if (((euler * k) + 1) % e) == 0:
return (euler * k + 1) // e
k += 1

#  according to n,e Calculation d( Or according to n,d Calculation e)
def get_rsa_e_d(n, e=None, d=None):
if e is None and d is None:
return

arg = e
if arg is None:
arg = d

primes = rsa_moder(n)
p = primes[0]
q = primes[1]

d = rsa_get_key(arg, rsa_get_euler(p, q))

return d

def main():
# n = 25777
# e = 3
# print("input n is ",n)
# print("input e is ",e)
# d = get_rsa_e_d(n, e, None)
# print("result: d is ",d)

n = 0xBB012883****( length 2048bit,16 Hexadecimal length 256)
e = 0x10001
print("input n is ",n)
print("input e is ",e)
d = get_rsa_e_d(n, e, None)
print("result: d is ",d)

p, q = getpq(n, e, d)
print("result: p = ", p)
print("result: q = ", int(q))

if __name__ == '__main__':
main()
``````

We test the correctness of the code with the public key information of the small module .

``````D:\Users\PycharmProjects\pythonProject\venv\Scripts\python.exe D:/Users/PycharmProjects/pythonProject/main.py
input n is  25777
input e is  3
result: d is  16971
result: p =  149
result: q =  173

Process finished with exit code 0``````

https://chowdera.com/2021/12/202112122244406563.html