RSA preface in CTF getprime(5 12)

This paper introduces the commonly used algorithms in RSA in detail, such as modular inverse operation, Euclid, extended Euclid and China remainder theorem, and only introduces the attack methods of CTF problems encountered and the python implementation of these algorithms. The purpose is to make it easy for everyone to solve RSA's problem in CTF's standard questions.

RSA launches getprime(5 12)

First of all, I won't put the lengthy Baidu Encyclopedia here. Let me summarize my views on RSA.

RSA is an algorithm, which is widely used in secure communication in modern times.

RSA algorithm involves three parameters: n, e and d, which are divided into private key and public key. The private keys are n and d, and the public keys are n and e.

N is the product of two prime numbers, which is generally represented by letters P and Q in RSA.

E is a prime number

D is the inverse of e-module varphi(n). From the perspective of CTF, D can be solved by E, P, Q, P and Q.

Generally, CTF takes the logo we want as plaintext and expresses it as m in RSA. Then the ciphertext is obtained by RSA encryption, which is recorded as C in RSA.

Encryption process

C = m e modern

C = power (m, e, n)

1

Decryption process

M = c d modern

M = power (c, d, n)

1

Solving private key d

d = gmpy2.invert(e，(p- 1)*(q- 1))

1

Generally speaking?

Match the knowledge points of the article with the official knowledge files.

Overview of Algorithm Skill Tree Home Page

30,677 people are studying systematically.