# Intro to Crypto 2 - localo

Category: Crypto
Difficulty: Baby
Author: black-simon

## Description

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!

## Summery

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.

## Solution

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

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'))



## Mitigation

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

## Flag

CSCG{Ok,_next_time_I_choose_p_and_q_random...}