当前位置:网站首页>RSA basic principle and common attack methods

RSA basic principle and common attack methods

2022-01-15 02:27:46 Xiao Xiangzi

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.comicon-default.png?t=LA92http://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

Use the online toolbox Website The-X Online toolbox Base64 decode AES RAS decode encryption Base64,DES,AES,RSA,BASE16,Hex Such as conventional encryption / Decryption tools . Original data inspection technology, fully automatic recognition results . Provide accurate handling suggestions .https://the-x.cn/

         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

版权声明
本文为[Xiao Xiangzi]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/12/202112122244406563.html

随机推荐