**Category:** Crypto

**Difficulty:** Baby

**Author:** black-simon

This is an introductory challenge for beginners which want to dive into the world of Cryptography. The three stages of this challenge will increase in difficulty.

I learned my lesson from the mistakes made in the last challenge! Now p and q are huge, I promise!

The author provided a `message.txt`

and a `pubkey.pem`

The `message.txt`

contains just a number and the `pubkey.pem`

is a public key. All we have to do is to decrypt the `message.txt`

.

We need to factor `N`

. `Factordb`

has not factored it. From the description I expected, that they have roughly the same length and used `Fermat's factorization method`

Wikipedia

import OpenSSL.crypto as crypto from factordb.factordb import FactorDB key = open("pubkey.pem","rb").read() message = open("message.txt","rb").read() key = crypto.load_publickey(crypto.FILETYPE_PEM, key) numbers = key.to_cryptography_key().public_numbers() N = numbers.n E = numbers.e C = int(message) def fermat(n): a = isqrt(n) while True: b = a**2-n if b > 0 and b.is_square(): p = int(str(a-isqrt(b))) return p,n/p a +=1 factors = fermat(N) P = factors[0] Q = factors[1] D = xgcd(E,(P - 1) * (Q - 1))[1] M = pow(C,D,N) print(hex(int(str(M))).replace("L","")[2:].decode('hex'))

- never roll your own crypto
- use large primes of different length

CSCG{Ok,_next_time_I_choose_p_and_q_random...}