RSA 使用 pka 找到 p 和 q

Question

我有这个练习：

练习9：（常见的RSA素数） Alice 和 Bob 一起生成了一组 RSA 模块。您的目标是找到用于生成这些模块的素数 p 和 q，可在文件 pk_alice 和 pk_bob 中找到。 有pka_alice：

9314555801759724245105784002000342349206503650571563593907342158487006417883655700743892090556836614127815536329521724 444227012055166556381673146461222584145617490466171901596745769668373658685851391433550192209234589570128168224248932472646 2415020945038049322877151602626496388802926568113827098181488546541

pka_鲍勃： 1306277759758706192651039674618635696853937196232596068344941617613536962311378384855960068504096499166317676587177711423 973278424767668355510885147111087322371344645838340854140904724654656569017185331205262400476727804564831822311714300475816 28792398849389571220237028177673312592572286345009761324975840273

我尝试了这个 python 程序，但它需要很长时间（永远不会从中得到输出）：

import sympy

def factorize(n):
    factors = sympy.ntheory.factorint(n)
    
    # Les clés du dictionnaire factors contiennent les facteurs premiers et les valeurs correspondent à leurs exposants.
    # Si n est le produit de deux nombres premiers, il y aura deux clés avec des exposants de 1.
    prime_factors = [factor for factor in factors if factors[factor] == 1]

    if len(prime_factors) == 2:
        p, q = prime_factors
        return p, q
    else:
        return None, None  # La factorisation a échoué

# Remplacez n par la valeur de n que vous souhaitez factoriser
n = 130627775975870619265103967461863569685393719623259606834494161761353696231137838485596006850409649916631767658717771142397327842476766835551088514711108732237134464583834085414090472465465656901718533120526240047672780456483182231171430047581628792398849389571220237028177673312592572286345009761324975840273

p, q = factorize(n)

if p and q:
    print(f"Les facteurs premiers de {n} sont {p} et {q}")
else:
    print("La factorisation a échoué.")

我该如何解决这个问题？

Answer 1

Alice:
p = 11546228166566908996944683360898685003804727870211092212733704895162284555816549530587425586574198315100684457091938790507073108514058962518074083478643487
q = 8067184943331379055883676674511286075021098911943040287647388643355051515709741724813022793998233351188112736071886443985753058022434276985771666457801843

Bob:
p = 11546228166566908996944683360898685003804727870211092212733704895162284555816549530587425586574198315100684457091938790507073108514058962518074083478643487
q = 11313458740934508371320688917048544848372493637810071784612124974863165934304508093282020336767731785955272382720056869761911762809833915572489801623030479

提示在练习标题中：“CommonRSA primes”。

import math

a = 93145558017597242451057840020003423492065036505715635939073421584870064178836557007438920905568366141278155363295217244442270120551665563816731464612225841456174904661719015967457696683736586858513914335501922092345895701281682242489324726462415020945038049322877151602626496388802926568113827098181488546541
b = 130627775975870619265103967461863569685393719623259606834494161761353696231137838485596006850409649916631767658717771142397327842476766835551088514711108732237134464583834085414090472465465656901718533120526240047672780456483182231171430047581628792398849389571220237028177673312592572286345009761324975840273

g = math.gcd(a, b)
print(f'Alice:\np = {g}\nq = {a//g}\n')
print(f'Bob:\np = {g}\nq = {b//g}')

在线尝试！