I participated in a CTF competition a few months ago. I encountered the RSA encryption and decryption question. It was also a fog at the time. After the game, I found the data and sorted it out.

#### Algorithm Introduction

The RSA encryption algorithm belongs to the public key encryption algorithm and is an asymmetric cryptographic algorithm. The so-called asymmetric is that one password is used for encryption and the other is used for decryption. In general, public key encryption, private key decryption, and of course Other cases.

#### Algorithm Principle

The RSA algorithm is based on the fact that it is very easy to multiply two large prime numbers, but it is extremely difficult to factorize the product, so the product can be exposed as an encryption key. RSA algorithm three parameters: n, e1, e2

n=pq (p, q is 2 large prime numbers) The number of bits occupied by the binary of n is the length of the secret key.
E1 and e2 are a pair of related values, e1 can be arbitrarily taken, but e1 and (p-1)
(q-1) are required to be homogeneous; (e2e1)mod((p-1)(q- 1))=1.
(n, e1), (n, e2) is the key pair, where (n, e1) is the public key and (n, e2) is the private key.

#### Algorithm Formula

Assumption:
A: Clear text
B: ciphertext

——Use public key encryption formula ——
A=B^e2 mod n
B=A^e1 mod n

——Use private key encryption formula ——
A=B^e1 mod n
B=A^e2 mod n

#### Actual demonstration

##### Summary of topics

This is a public key encryption, public key decryption RSA topic
The public key password is given as: {920139713, 19}, where 920139713 is n and 19 is e1.
The ciphertext B to be decrypted is:
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
……
Finally solve the value of private key A?

##### Problem Solving

List formula: public key encryption
Assumption:
A: Clear text
B: ciphertext
A=B^e2 mod n
B=A^e1 mod n

This question gives B, n, e1, and finds the value of A, which can be solved by taking Equation 2.

##### operation result

flag13212je2ue28fy71w8u87y31r78eu1e2 