Junior RSA

My p and q are generated by an unbreakable algorithm!

task.py

from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)

def gen(bits):
    while True:
        a = getPrime(bits)
        b = getPrime(bits)
        c = getPrime(bits)
        p = (a << (2*bits)) + (b << bits) + c
        q = (c << (2*bits)) + (a << bits) + b
        if isPrime(p) and isPrime(q):
            break
    n = p * q
    e = 65537 * a * b * c
    return n, e

n, e = gen(256)
enc = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'enc = {enc}')

"""
n = 1224562468550864572988516321107388462006452125881847529675226398144888628055678744854491489016309262856785169494723943649344959507818155642772331582922466943539371681776924160647697558836379614689120727659593775446187326222964118917872973684996317614900715927751822277949264379149585370840318817143291878609357893969588131470982041272505875501444442064552286330626234504767040724907034678080283717062342383737341651784574675215207283219694413200065153603535550259
e = 47356701171507751941853094934330097161634963503549196148254287987823089762869775349307331223083118848869825102126184149696632299476124764277876323238594318983922914255635452587035212905468593961720866809724369270149104325019013500377581
enc = 307839781648837102719329833689146078918113606357673952357833605392673923316706392387378621203382529480917019155723632239435123748698548640308486267420983085309284306889248702165586731118889200017606360233948688879034822132551452439147516062116990766999765714755923073387252339782026780490661436777023426366620269445376047876173655782230659201893151372247389482285331969025687842851498151565880029377050013378302485301558801016888957357366922840214729734193614497
"""

读代码发现重点在于：

p = (a << (2*bits)) + (b << bits) + c
q = (c << (2*bits)) + (a << bits) + b
e = 65537 * a * b * c

题中给了e值，大数分解可得

65537
87088466343588588635847974940372253273068357792488684134029598514751137278559
8297251269738402733930932998606283113633384640722023005708172168780629095697962224367339263000080188872297005214222162293678816989184909411666442123917107

将该77位质数mod 2^256后发现与n mod2^256结果相等，得知分解出的质数为a

目前b和c两个未知数，两个方程就可以解

from sympy import *

b,c = symbols("b,c")

a = 87088466343588588635847974940372253273068357792488684134029598514751137278559
bc = 8297251269738402733930932998606283113633384640722023005708172168780629095697962224367339263000080188872297005214222162293678816989184909411666442123917107
n = 1224562468550864572988516321107388462006452125881847529675226398144888628055678744854491489016309262856785169494723943649344959507818155642772331582922466943539371681776924160647697558836379614689120727659593775446187326222964118917872973684996317614900715927751822277949264379149585370840318817143291878609357893969588131470982041272505875501444442064552286330626234504767040724907034678080283717062342383737341651784574675215207283219694413200065153603535550259

mod1 = 2**512
mod2 = 2**256

eq1 = (a*mod2+b*mod1+c)*(c*mod2+a*mod1+b)-n
eq2 = b*c-bc

sol = solve((eq1,eq2),(b,c))
print(sol)
#[(78217646126976775165324659746940679675150517582379374445759075728965034308847, 106079020279756703827552557998407494719356251292716368090373498727784828291581)]

现在a,b,c的值都已知了，常规求解rsa即可

from Crypto.Util.number import *
import gmpy2

a = 87088466343588588635847974940372253273068357792488684134029598514751137278559
b = 106079020279756703827552557998407494719356251292716368090373498727784828291581
c = 78217646126976775165324659746940679675150517582379374445759075728965034308847
n = 1224562468550864572988516321107388462006452125881847529675226398144888628055678744854491489016309262856785169494723943649344959507818155642772331582922466943539371681776924160647697558836379614689120727659593775446187326222964118917872973684996317614900715927751822277949264379149585370840318817143291878609357893969588131470982041272505875501444442064552286330626234504767040724907034678080283717062342383737341651784574675215207283219694413200065153603535550259
e = 47356701171507751941853094934330097161634963503549196148254287987823089762869775349307331223083118848869825102126184149696632299476124764277876323238594318983922914255635452587035212905468593961720866809724369270149104325019013500377581
enc = 307839781648837102719329833689146078918113606357673952357833605392673923316706392387378621203382529480917019155723632239435123748698548640308486267420983085309284306889248702165586731118889200017606360233948688879034822132551452439147516062116990766999765714755923073387252339782026780490661436777023426366620269445376047876173655782230659201893151372247389482285331969025687842851498151565880029377050013378302485301558801016888957357366922840214729734193614497
bits = 256
p = (a << (2*bits)) + (b << bits) + c
q = (c << (2*bits)) + (a << bits) + b
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(enc,d,n)
print(long_to_bytes(m))
# ctfpunk{2ffab167-af57-49d2-ba91-81d9864a98ef}