[Cryptohack] RSA (Marin`s Secret, Fast Primes)

Marin`s Secret

문제

저는 제 비밀 목록에서 소수를 생성하는 초고속 방법을 찾았습니다.

풀이

 

#!/usr/bin/env python3

import random
from Crypto.Util.number import bytes_to_long, inverse
from secret import secrets, flag


def get_prime(secret):
    prime = 1
    for _ in range(secret):
        prime = prime << 1
    return prime - 1


random.shuffle(secrets)

m = bytes_to_long(flag)
p = get_prime(secrets[0])
q = get_prime(secrets[1])
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

output.txt

factordb.com에서 n값 분해의 결과

n의 값이 두소수로 분해가 가능하니

저번 문제처럼 풀면된다.

from Crypto.Util.number import long_to_bytes

n= 658416274830184544125027519921443515789888264156074733099244040126213682497714032798116399288176502462829255784525977722903018714434309698108208388664768262754316426220651576623731617882923164117579624827261244506084274371250277849351631679441171018418018498039996472549893150577189302871520311715179730714312181456245097848491669795997289830612988058523968384808822828370900198489249243399165125219244753790779764466236965135793576516193213175061401667388622228362042717054014679032953441034021506856017081062617572351195418505899388715709795992029559042119783423597324707100694064675909238717573058764118893225111602703838080618565401139902143069901117174204252871948846864436771808616432457102844534843857198735242005309073939051433790946726672234643259349535186268571629077937597838801337973092285608744209951533199868228040004432132597073390363357892379997655878857696334892216345070227646749851381208554044940444182864026513709449823489593439017366358869648168238735087593808344484365136284219725233811605331815007424582890821887260682886632543613109252862114326372077785369292570900594814481097443781269562647303671428895764224084402259605109600363098950091998891375812839523613295667253813978434879172781217285652895469194181218343078754501694746598738215243769747956572555989594598180639098344891175879455994652382137038240166358066403475457 
e= 65537
c=400280463088930432319280359115194977582517363610532464295210669530407870753439127455401384569705425621445943992963380983084917385428631223046908837804126399345875252917090184158440305503817193246288672986488987883177380307377025079266030262650932575205141853413302558460364242355531272967481409414783634558791175827816540767545944534238189079030192843288596934979693517964655661507346729751987928147021620165009965051933278913952899114253301044747587310830419190623282578931589587504555005361571572561916866063458812965314474160499067525067495140150092119620928363007467390920130717521169105167963364154636472055084012592138570354390246779276003156184676298710746583104700516466091034510765027167956117869051938116457370384737440965109619578227422049806566060571831017610877072484262724789571076529586427405780121096546942812322324807145137017942266863534989082115189065560011841150908380937354301243153206428896320576609904361937035263985348984794208198892615898907005955403529470847124269512316191753950203794578656029324506688293446571598506042198219080325747328636232040936761788558421528960279832802127562115852304946867628316502959562274485483867481731149338209009753229463924855930103271197831370982488703456463385914801246828662212622006947380115549529820197355738525329885232170215757585685484402344437894981555179129287164971002033759724456
p=1475979915214180235084898622737381736312066145333169775147771216478570297878078949377407337049389289382748507531496480477281264838760259191814463365330269540496961201113430156902396093989090226259326935025281409614983499388222831448598601834318536230923772641390209490231836446899608210795482963763094236630945410832793769905399982457186322944729636418890623372171723742105636440368218459649632948538696905872650486914434637457507280441823676813517852099348660847172579408422316678097670224011990280170474894487426924742108823536808485072502240519452587542875349976558572670229633962575212637477897785501552646522609988869914013540483809865681250419497686697771007
q=446087557183758429571151706402101809886208632412859901111991219963404685792820473369112545269003989026153245931124316702395758705693679364790903497461147071065254193353938124978226307947312410798874869040070279328428810311754844108094878252494866760969586998128982645877596028979171536962503068429617331702184750324583009171832104916050157628886606372145501702225925125224076829605427173573964812995250569412480720738476855293681666712844831190877620606786663862190240118570736831901886479225810414714078935386562497968178729127629594924411960961386713946279899275006954917139758796061223803393537381034666494402951052059047968693255388647930440925104186817009640171764133172418132836351

euler = (p-1)*(q-1)                       
d = pow(e, -1, euler)  

answer = pow(c, d, n)
print(long_to_bytes(answer))

플래그 값은 crypto{Th3se_Pr1m3s_4r3_t00_r4r3}이다.

Fast Primes

문제

수백만 개의 RSA 키를 신속하게 생성해야 하지만 일반적인 방법으로는 부족합니다. 여기 수년간의 검토에 실제로 저항해온 소수를 생성하는 또 다른 빠른 방법이 있습니다.

풀이

#!/usr/bin/env python3

import math
import random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, inverse
from gmpy2 import is_prime


FLAG = b"crypto{????????????}"

primes = []


def sieve(maximum=10000):
    # In general Sieve of Sundaram, produces primes smaller
    # than (2*x + 2) for a number given number x. Since
    # we want primes smaller than maximum, we reduce maximum to half
    # This array is used to separate numbers of the form
    # i+j+2ij from others where 1 <= i <= j
    marked = [False]*(int(maximum/2)+1)

    # Main logic of Sundaram. Mark all numbers which
    # do not generate prime number by doing 2*i+1
    for i in range(1, int((math.sqrt(maximum)-1)/2)+1):
        for j in range(((i*(i+1)) << 1), (int(maximum/2)+1), (2*i+1)):
            marked[j] = True

    # Since 2 is a prime number
    primes.append(2)

    # Print other primes. Remaining primes are of the
    # form 2*i + 1 such that marked[i] is false.
    for i in range(1, int(maximum/2)):
        if (marked[i] == False):
            primes.append(2*i + 1)


def get_primorial(n):
    result = 1
    for i in range(n):
        result = result * primes[i]
    return result


def get_fast_prime():
    M = get_primorial(40)
    while True:
        k = random.randint(2**28, 2**29-1)
        a = random.randint(2**20, 2**62-1)
        p = k * M + pow(e, a, M)

        if is_prime(p):
            return p


sieve()

e = 0x10001
m = bytes_to_long(FLAG)
p = get_fast_prime()
q = get_fast_prime()
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
ciphertext = cipher.encrypt(FLAG)

assert cipher.decrypt(ciphertext) == FLAG

exported = key.publickey().export_key()
with open("key.pem", 'wb') as f:
    f.write(exported)

with open('ciphertext.txt', 'w') as f:
    f.write(ciphertext.hex())

문제에서 제공하는 key.pem

 

문제에서 제공하는 ciphertext.txt

 

https://www.dlitz.net/software/pycrypto/api/2.6/Crypto.PublicKey.RSA-module.html

먼저 공키값은 n, e, d값을 RSA모듈에서의 construct함수로 사용하여 만들어 졌다.

n값을 구해야, p와 q을 알수 있고 이를 통해 개인 지수를 알수 있기에

n을 구하는 방법을 알려고 하던 중(chatgpt를 통)

cryptography를 통해

e값과 모듈러스 값인 n값을 구할수 있는 방법을 찾았다.

 

바로 알려주는게 진짜 놀랍다.

그래서 문제 코드에선 e값은 공개 되었기 때문에

위 코드를 통해 n값을 구해보았다. 

from cryptography.hazmat.primitives import serialization



# PEM 형식의 공개 키 가져오기
public_key = serialization.load_pem_public_key(open("key_17a08b7040db46308f8b9a19894f9f95.pem", "rb").read())

# 공개 키 구성 요소 가져오기
public_numbers = public_key.public_numbers()

# 모듈러스 (N) 출력
print("Modulus (N):", public_numbers.n)

# 공개 지수 (e) 출력
print("Public Exponent (e):", public_numbers.e)

진짜 깔끔하게 알려준다.

n값을 구했으니 이제 p,q를 통해 개인지수를 만들고,

이를 통해 다시 키를 만들어 평문을 구해본다.

from Crypto.Util.number import long_to_bytes
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from cryptography.hazmat.primitives import serialization


c=0x249d72cd1d287b1a15a3881f2bff5788bc4bf62c789f2df44d88aae805b54c9a94b8944c0ba798f70062b66160fee312b98879f1dd5d17b33095feb3c5830d28

public_key = serialization.load_pem_public_key(open("key_17a08b7040db46308f8b9a19894f9f95.pem", "rb").read())
public_numbers = public_key.public_numbers()

n=public_numbers.n
e=public_numbers.e
print("n값 : %d" %n)
print("e값 : %d" %e)
#factordb.com에 n값을 넣어 나온결과
p = 51894141255108267693828471848483688186015845988173648228318286999011443419469
q = 77342270837753916396402614215980760127245056504361515489809293852222206596161

euler = (p-1)*(q-1)                       
d = pow(e, -1, euler)  

key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
plaintext=cipher.decrypt(bytes.fromhex(hex(c)[2:]))
print(plaintext)

 

 플래그 값은 crypto{p00R_3570n14}이다.